【数据结构】从零开始逐步实现带哨兵位循环双向链表 | 学会用 “思路草图“ 将思路转变成代码

简介: 本章节将继续讲解链表,在上一章节中我们学习了单链表,本章将对其他的链表进行简要介绍,旨在让读者理解单链表和双链表各自存在的意义。将着重讲解带哨兵位双向循环链表,对常用的接口函数进行逐个讲解,本章开始引入可以将思路轻松转换成代码的 "思路草图" 方法。站在初学者的角度上进行讲解和分析。通过本章的学习,还能够帮助大家理解解 "代码复用" 的意义。

前言


本章节将继续讲解链表,在上一章节中我们学习了单链表,本章将对其他的链表进行简要介绍,旨在让读者理解单链表和双链表各自存在的意义。将着重讲解带哨兵位双向循环链表,对常用的接口函数进行逐个讲解,本章开始引入可以将思路轻松转换成代码的 "思路草图" 方法。站在初学者的角度上进行讲解和分析。通过本章的学习,还能够帮助大家理解解 "代码复用" 的意义。


一、链表的分类


0x01 链表的分类

① 单向或者双向

07172c1a143801663eab1ee226a015f9_fdf80600963341e8b187c5394453fbe4.png


② 带头或者不带头


4a048ff4bfea75c0ccad2da9a932aa1d_fdd44b7ef8684a45ab8ff879e18b2fdf.png


③ 循环或者非循环

f18069f7d2113a5bc6f8b599e9fbdaf2_fddf6814cc3c4ad1bcaa7146d895eaa6.png

0x02 常用的链表

根据上面的分类我们可以细分出8种不同类型的链表,这么多链表我们一个个讲解这并没有意义。我们实际中最常用的链表是 "无头单向非循环链表" 和 "带头双向循环链表" ,至于 "无头单项非循环链表" 我们在上一章已经讲述过了,我们下面将讲解 "带头双向循环列表" !

a14b12e157294f42a3bce54bcf6f9b23_e36378a989c043208b8ac63188574037.png

📚 解读:


① 无头单向非循环链表:结构简单,一般不会单独用来存储数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等。此外,在笔试中单链表的出现频率较多。


② 带头双向循环链表:结构最复杂,但是实现反而简单。一般用来单独存储数据,实际中使用的链表数据结构都是带头双向链表。另外,这个结构虽然结构复杂,但是使用代码实现后会发现结构会带来很多优势。双向链表严格来说只需要快速的实现两个接口,insert 和 earse 头尾的插入和删除就可以搞定了,这就是结构的优势!


二、双链表的定义


0x00 定义双链表

typedef int DLNodeDataType;       // DLNodeDataType == int
typedef struct DoubleListNode {
    DLNodeDataType data;          // 用来存放结点的数据
    struct DoubleListNode* next;  // 指向后继节点的指针
    struct DoubleListNode* prev;  // 指向前驱节点的指针
} DLNode;  // 重命名为DLNode

🔑 解读:和之前一样,为了方便后续使用我们将类型 typedef 一下。首先创建结构体,因为双链表,所以我们将它取为 DoubleListNode。为了方便后续地使用,我们再把这个结构体重命名成 DLNode(非常合理的简写,DoubleListNode)。


0x01 接口函数

📚 这是需要实现几个接口函数:

DLNode* DListInit();
// DLNode* CreateNewNode(DLNodeDataType x);
void DListPrint(DLNode* pHead);
void DListPushBack(DLNode* pHead, DLNodeDataType x);
void DListPushFront(DLNode* pHead, DLNodeDataType x);
void DListPopBack(DLNode* pHead);
void DListPopFront(DLNode* pHead);
DLNode* DListFind(DLNode* pHead, DLNodeDataType x);
void DListInsert(DLNode* pos, DLNodeDataType x);
void DListEarse(DLNode* pos);

三、详解接口函数的实现


0x00 初始化双链表(DListInit)

我们之前在学习无头非循环单链表时,我们使用的是二级指针的方法来接收参数的。本节我们将采用传递返回值的方法来完成。


💬 DList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int DLNodeDataType;       // DLNodeDataType == int
typedef struct DoubleListNode {
    DLNodeDataType data;          // 用来存放结点的数据
    struct DoubleListNode* next;  // 指向后继节点的指针
    struct DoubleListNode* prev;  // 指向前驱节点的指针
} DLNode;  // 重命名为DLNode
DLNode* DListInit();

🔑 解读:既然要初始化带头的链表,就需要动态内存开辟,所以我们要引入 #include  这个头文件。我们既然要采用返回值的方法,我们就需要把函数类型设定为 DLNode* 。


💬 DList.c

DLNode* DListInit() {
    //哨兵位头节点
    DLNode* pHead = (DLNode*)malloc(sizeof(DLNode));
    pHead->next = pHead;
    pHead->prev = pHead;
    return pHead;
}

🔑 解读:这里我们使用 malloc 函数开辟一块空间作为 "哨兵位" pHead ,最后将其进行一个初始化。最后再将 pHead 作为结果返回回去,外面就可以接收到了。这就是返回值的方法,当然这里也可以采用二级指针的方法来完成。


0x01 双向链表打印(DListPrint)

💬 DList.h

void DListPrint(DLNode* pHead);

🔑 解读:用结构体指针 pHead 接收, 这里的 pHead 表示哨兵位。


💬 DList.c

void DListPrint(DLNode* pHead) {
    assert(pHead != NULL); //防止pHead为空
    DLNode* cur = pHead->next; //因为pHead存的不是有效数据,所以要从pHead的下一个节点开始
    while(cur != pHead) {
        printf("%d ", cur->data); //打印
        cur = cur->next;
    }
    printf("\n"); //换行
}

🔑 解读:


① 我们要防止 pHead 为空,暴力解决方法就是用 assert 断言下即可。


② 创建遍历指针 cur,因为 pHead 是哨兵位所以存的不是有效数据,我们想要遍历链表就需要从 pHead->next 开始(即第一个有效数据节点),当 cur 等于 pHead 就相当于全部走了一遍了,这时就结束。


0x02 创建新节点(CreateNewList)

⚡ 创建新节点要经常用,为了方便复用,根据经验我们先把 CreateNewNode 写好:

DLNode* CreateNewNode(DLNodeDataType x) {
    //动态内存开辟一块 DLNode 大小的空间给 new_node
    DLNode* new_node = (DLNode*)malloc(sizeof(DLNode));
    //检查malloc
    if (new_node == NULL) {
        printf("malloc failed!\n");
        exit(-1);
    }
    //放置数据
    new_node->data = x;
    //初始化
    new_node->next = NULL;
    new_node->prev = NULL;
    //返回
    return new_node;
}

0x03 双向链表尾插(DListPushBack)

💬 DList.h

void DListPushBack(DLNode* pHead, DLNodeDataType x);

🔑 解读:因为不用改变 pList,所以不需要使用二级指针。

DLNode* pList = DListInit();

💬 DList.c

void DListPushBack(DLNode* pHead, DLNodeDataType x) {
    assert(pHead != NULL); //防止pHead为空
    DLNode* tail = pHead->prev; //创建尾指针
    DLNode* new_node = CreateNewNode(x); //创建新节点
    //思路草图: pHead                 tail   new_node(尾插目标)
    tail->next = new_node;
    new_node->prev = tail;
    new_node->next = pHead;
    pHead->prev = new_node;
}

🔑 解读:


① 首先防止 pHead 为空。


② 因为要实现尾插,我们要找出尾部节点。我们这里并不需要像之前学单链表时需要创建寻尾指针找到尾部节点,直接从 pHead->prev 那里取就可以了。是不是非常的方便?找都不用找了直接 O(1) 解决,真的是不爽不要钱!随后创建新节点,直接调用我们刚才写的  CreateNewNode 接口即可。


③ 实现尾插操作,画出来可以更好地写出代码。在注释里写一个简单地思路草图也是可以的,只要画好他们之间的链接关系,再写代码会变得非常简单:


思路草图: pHead                                tail   new_node(尾插目标)


然后再根据尾插的思路,我们就可以轻松写出代码了:


将 tail 与 new_node 相互链接起来:

tail->next = new_node;
    new_node->prev = tail;

将 new_node 与 pHead 相互链接起来:

new_node->next = pHead;
    pHead->prev = new_node;

( "双链表"的尾插就这么写好了,是不是比之前学的 "单链表" 简单多了?)


🔍 如果你没有看懂草图,可以看下面画的更详细的解析图:

07a8fe219877ddeb2c9166ad1d068b56_69c4124993694f14b2d778115df008e5.png


💬 Test.c


我们来测试一下我们刚才写的几个接口:


#include "DList.h"
void TestList1() {
    DLNode* pList = DListInit();
    DListPushBack(pList, 1);
    DListPushBack(pList, 2);
    DListPushBack(pList, 3);
    DListPushBack(pList, 4);
    DListPrint(pList);
}
int main() {
    TestList1();
    return 0;
}


🚩 运行结果:

70000f14c1bae398f0da5d45673d4c9a_0f3b84a6481c4f8f991a94e7f1f8e919.png


0x04 双向链表头插(DListPushFront)

💬 DList.h

void DListPushFront(DLNode* pHead, DLNodeDataType x);

🔑 解读:双向链表头插,即在第一个数据前面,也就是哨兵位和第一个数据之间插入一个数据。


💬 DList.c

void DListPushFront(DLNode* pHead, DLNodeDataType x) {
    assert(pHead != NULL); //防止pHead为空
    DLNode* new_node = CreateNewNode(x); //创建新节点
    DLNode* pHeadNext = pHead->next; //标出第一个节点
    //思路草图: pHead  new_node(头插目标)  pHeadNext
    pHead->next = new_node;
    new_node->prev = pHead;
    new_node->next = pHeadNext;
    pHeadNext->prev = new_node;
}

🔑 解读:


① 首先防止 pHead 为空。


② 既然是插入,那就创建新节点。双向链表头插,我们要找到第一个节点,通过 pHead->next 就可以拿到了,我们将它取名为 pHeadNext(表示第一个节点)。在哨兵位和第一个数据之间插入数据,画出草图就是:


思路草图: pHead  new_node(头插目标)  next


根据草图我们开始写代码,将他们互相链接起来即可!


将 pHead 与 new_node 相互链接起来:

pHead->next = new_node;
    new_node->prev = pHead;

将 new_node 与 pHeadNext 相互链接起来:

new_node->next = pHeadNext;
    pHeadNext->prev = new_node;

💬 Test.c


#include "DList.h"
void TestList2() {
    DLNode* pList = DListInit();
    DListPushFront(pList, 10);
    DListPushFront(pList, 20);
    DListPushFront(pList, 30);
    DListPushFront(pList, 40);
    DListPrint(pList);
}
int main() {
    TestList2();
    return 0;
}


🚩 运行结果:


c9b7997a27a526ecb540a33982bb127f_c4d0e7291c7e44f2b67de050d3cb85ec.png


0x05 双链表尾删(DListPopBack)

💬 DList.h

void DListPopBack(DLNode* pHead);

💬 DList.c

void DListPopBack(DLNode* pHead) {
    assert(pHead != NULL); //防止pHead为空
    //这里要注意下 防止哨兵位也被干掉的情况 pHead->next == pHead 表示链表为空,不能删除了
    assert(pHead->next != pHead);
    //思路草图: pHead          tailPrev  tail(待删目标)
    DLNode* tail = pHead->prev;
    DLNode* tailPrev = tail->prev;
    //释放
    free(tail);
    //链接
    tailPrev->next = pHead;
    pHead->prev = tailPrev;
}

🔑 解读:


① 首先防止 pHead 为空,这里还要预防下哨兵位被不小心干掉的情况,哨兵位指向自己就说明链表为空,链表为空就不能再继续删除了,断言 pHead->next == pHead 就可以了。


② 因为是尾删,我们要把尾部指针和它的前驱指针标出来。我们来画一下思路草图:


思路草图: pHead          tailPrev  tail(待删目标)


另外,这里使用前驱指针是为了避免 free 掉之后就没法链接了。


我们有了 tailPrev 了,所以我们先 free 掉 tail 也关系,此时 tail 已经被释放掉了,我们做一个类似于 "缝针" 的操作即可:


将 tailPrev 与 pHead 相链接起来即可:


tailPrev->next = pHead;
    pHead->prev = tailPrev;

❓ 可能会有人疑惑为什么老是要把他们标出来,这里我来解释一下为什么。标出来可以让代码看起来更清楚,写完思路草图之后可以更好地写出代码,代码也更加好读,多设定几个变量增加可读性是非常值当的事情!当然你非这么干也行:

pHead->prev->prev->next = pHead;
pHead->prev = pHead->prev->prev;
free(pHead->prev);

这位仁兄干嘛要跟自己过不去呢……

乱七八糟的,读起来都费劲!

定义一下好处很多,链接顺序随便换都没有问题。

💬 Test.c

#include "DList.h"
void TestList3() {
    DLNode* pList = DListInit();
    DListPushBack(pList, 1);
    DListPushBack(pList, 2);
    DListPushBack(pList, 3);
    DListPushBack(pList, 4);
    DListPrint(pList);
    DListPopBack(pList);
    DListPrint(pList);
}
int main() {
    TestList3();
    return 0;
}


🚩 运行结果:

80867618c4d444a3d649a58c4489ca22_e1681e8add644f4bb7d1e28c6aa3441c.png


0x06 双链表头删(DListPopFront)

💬 DList.h

void DListPopFront(DLNode* pHead);

💬 DList.c

void DListPopFront(DLNode* pHead) {
    assert(pHead != NULL); // 防止pHead为空
    assert(pHead->next != pHead); // 防止链表为空
    //思路草图:  pHead  pHeadNext(待删目标)  pHeadNextNext
    DLNode* pHeadNext = pHead->next;
    DLNode* pHeadNextNext = pHeadNext->next;
    //链接
    pHead->next = pHeadNextNext;
    pHeadNextNext->prev = pHead;
    //释放
    free(pHeadNext);
}

🔑 解读:


① 断言部分老生常谈的事了,这里就不重复了。


② 头删,直接画思路草图:


思路草图:  pHead    pHeadNext(待删目标)    pHeadNextNext


                                        👆                                     👆


                         第一个节点(有效数据)         即第二个节点


③ 链接完之后删除即可。


💬 Test.c


#include "DList.h"
void TestList4() {
    DLNode* pList = DListInit();
    DListPushBack(pList, 1);
    DListPushBack(pList, 2);
    DListPushBack(pList, 3);
    DListPushBack(pList, 4);
    DListPrint(pList);
    DListPopFront(pList);
    DListPrint(pList);
}
int main() {
    TestList4();
    return 0;
}


🚩 运行结果:

029f51f29d4066b92e61744e23b4c5aa_e0d3f4c96a5148d7bd360dcf801b1ff8.png


0x07 双链表查找(DListFind)

💬 DList.h

DLNode* DListFind(DLNode* pHead, DLNodeDataType x);

💬 DList.c


DLNode* DListFind(DLNode* pHead, DLNodeDataType x) {
    assert(pHead); //防止pHead为空
    DLNode* cur = pHead->next;
    while(cur != pHead) {
        if (cur->data == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}

🔑 解读:很简单,和打印的思路一样。只需要创建一个 cur 从第一个有效节点(pHead->next)开始遍历链表就可以了。如果 cur->data 和传入的 x,即需要查找的值相同就返回 cur,cur 是带有值和地址的。如果整个链表都走完了还没有找到相同的值,就返回 NULL 。


💬 Test.c


没什么测的,懒得测了。自己测去吧。 (划掉)


0x08 双链表pos位置之前插入(DListInsert)

💬 DList.h

void DListInsert(DLNode* pos, DLNodeDataType x);

🔑 解读:根据性质,这里甚至都不需要哨兵位,我们只需要传入 pos 和待插入的值 x 即可。


💬 DList.c

void DListInsert(DLNode* pos, DLNodeDataType x) {
    assert(pos != NULL); // 防止传入的pos为空
    DLNode* new_node = CreateNewNode(x);
    DLNode* posPrev = pos->prev; //pos前驱
    //思路草图: posPrev  newnode(待插目标)   pos
    posPrev->next = new_node;
    new_node->prev = posPrev;
    new_node->next = pos;
    pos->prev = new_node;
}

🔑 解读:


① 防止 pos 传入为空。


② 首先创建新节点。因为是在 pos 位置之前插入,为了方便,我们先标出 pos 的前驱指针 posPrev,随后我们画出草图:


思路草图:posPrev  newnode(待插目标)   pos


将 posPrev 与 new_node 相互链接起来:


posPrev->next = new_node;
    new_node->prev = posPrev;

将 new_node 与 pos 相互链接起来:


 

new_node->next = pos;
    pos->prev = new_node;

⚡ 此时,DListInsert 就大功告成了!它就是双向链表最核心的两个接口之一,我们可以将这个万能的 "pos位置之前插入" 复用到我们刚才写的尾插和头插那里,即 DListPushBack 和 DListPushFront 中:


// 尾插(NEW)
void DListPushBack(DLNode* pHead, DLNodeDataType x) {
    assert(pHead != NULL); //防止pHead为空
    /*
    DLNode* tail = pHead->prev; //创建尾指针
    DLNode* new_node = CreateNewNode(x); //创建新节点
    //思路草图: pHead                 tail   new_node(尾插目标)
    tail->next = new_node;
    new_node->prev = tail;
    new_node->next = pHead;
    pHead->prev = new_node;
    */
    DListInsert(pHead, x);
}


🔑 解读:传入 pHead 进入 DListInsert 中,可以找到尾部节点,即可完成尾插。


// 头插(NEW)
void DListPushFront(DLNode* pHead, DLNodeDataType x) {
    assert(pHead != NULL); //防止pHead为空
    /*
    DLNode* new_node = CreateNewNode(x); //创建新节点
    DLNode* pHeadNext = pHead->next; //提出第一个节点
    //思路草图: pHead  new_node(头插目标)  First
    pHead->next = new_node;
    new_node->prev = pHead;
    new_node->next = pHeadNext;
    pHeadNext->prev = new_node;
    */
    DListInsert(pHead->next, x);
}


🔑 解读:头插,将 pHead->next 传入 DListInsert 中即可完成头插。


0x09 双链表删除pos位置(DListEarse)

💬 DList.h

void DListEarse(DLNode* pos);

💬 DList.c

void DListEarse(DLNode* pos) {
    assert(pos != NULL); //防止传入的pos为空
    DLNode* posPrev = pos->prev; //标出pos的前驱指针
    DLNode* posNext = pos->next; //标出pos的后继指针
    //思路草图: posPrev  pos(待删目标)  posNext
    posPrev->next = posNext;
    posNext->prev = posPrev;
    //释放
    free(pos);
    pos = NULL
}

🔑 解读:


① 防止 pos 传入为空。


② 既然要删除 pos 位置的节点,我们先标出 pos 的前驱指针 posPrev 和 pos 的后继指针 posNext ,随后我们画出草图:


思路草图: posPrev  pos(待删目标)  posNext


之后我们开始 "缝针" ,将 posPrev 与 posNext 相互链接起来:

posPrev->next = posNext;
posNext->prev = posPrev;

最后再将 pos 释放即可。


⚡ 此时,DListEarse 也搞定了!我们可以将这个万能的 "pos位置删除" 复用到之前写的尾删和头删那里,即 DListPopBack 和 DListPopFront 中:

// 尾删(NEW)
void DListPopBack(DLNode* pHead) {
    assert(pHead != NULL); //防止pHead为空
    assert(pHead->next != pHead); //防止链表为空
    /*
    //思路草图: pHead          tailPrev  tail(待删目标)
    DLNode* tail = pHead->prev;
    DLNode* tailPrev = tail->prev;
    //释放
    free(tail);
    //链接
    tailPrev->next = pHead;
    pHead->prev = tailPrev;
    */
    DListEarse(pHead->prev);
}


🔑 解读:尾删,将 pHead->prev 传入 DListEarse 中即可完成尾删。


// 头删(NEW)
void DListPopFront(DLNode* pHead) {
    assert(pHead != NULL); // 防止pHead为空
    assert(pHead->next != pHead); // 防止链表为空
    /*
    //思路草图:  pHead  pHeadNext(待删目标)  pHeadNextNext
    DLNode* pHeadNext = pHead->next;
    DLNode* pHeadNextNext = pHeadNext->next;
    //链接
    pHead->next = pHeadNextNext;
    pHeadNextNext->prev = pHead;
    //释放
    free(pHeadNext);
    */
    DListEarse(pHead->next);
}

🔑 解读:头删,将 pHead->next 传入 DListEarse 中即可完成头删。


四、总结


🔺 所以,双向链表严格来说只需要快速地实现 insert 和 earse 这两个接口就可以搞定了。为什么会这么简单?别问,问就是结构的优势!


如果以后让你快速实现一个双向链表,你把 "pos位置之前插入" 和 "删除pos位置" 这两个接口写好,头尾的插入和删除直接复用就可以搞定了。


五、完整代码


最后附上完整代码(包含测试用地代码)


💬 DList.h

#pragma once
#include 
#include 
#include 
typedef int DLNodeDataType;       // DLNodeDataType == int
typedef struct DoubleListNode {
    DLNodeDataType data;          // 用来存放结点的数据
    struct DoubleListNode* next;  // 指向后继节点的指针
    struct DoubleListNode* prev;  // 指向前驱节点的指针
} DLNode;  // 重命名为DLNode
DLNode* DListInit();
void DListPrint(DLNode* pHead);
void DListPushBack(DLNode* pHead, DLNodeDataType x);
void DListPushFront(DLNode* pHead, DLNodeDataType x);
void DListPopBack(DLNode* pHead);
void DListPopFront(DLNode* pHead);
DLNode* DListFind(DLNode* pHead, DLNodeDataType x);
void DListInsert(DLNode* pos, DLNodeDataType x);
void DListEarse(DLNode* pos);


💬 DList.c


#include "DList.h"
DLNode* DListInit() {
    //哨兵位头节点
    DLNode* pHead = (DLNode*)malloc(sizeof(DLNode));
    pHead->next = pHead;
    pHead->prev = pHead;
    return pHead;
}
DLNode* CreateNewNode(DLNodeDataType x) {
    //动态内存开辟一块 DLNode 大小的空间给 new_node
    DLNode* new_node = (DLNode*)malloc(sizeof(DLNode));
    //检查malloc
    if (new_node == NULL) {
        printf("malloc failed!\n");
        exit(-1);
    }
    //放置数据
    new_node->data = x;
    //初始化
    new_node->next = NULL;
    new_node->prev = NULL;
    //返回
    return new_node;
}
void DListPrint(DLNode* pHead) {
    assert(pHead != NULL); //防止pHead为空
    DLNode* cur = pHead->next; //因为pHead存的不是有效数据,所以要从pHead的下一个节点开始
    while(cur != pHead) {
        printf("%d ", cur->data); //打印
        cur = cur->next;
    }                                          
    printf("\n"); //换行
}
void DListPushBack(DLNode* pHead, DLNodeDataType x) {
    assert(pHead != NULL); //防止pHead为空
    DListInsert(pHead, x);
}
void DListPushFront(DLNode* pHead, DLNodeDataType x) {
    assert(pHead != NULL); //防止pHead为空
    DListInsert(pHead->next, x);
}
void DListPopBack(DLNode* pHead) {
    assert(pHead != NULL); //防止pHead为空
    assert(pHead->next != pHead); //防止链表为空
    DListEarse(pHead->prev);
}
void DListPopFront(DLNode* pHead) {
    assert(pHead != NULL); // 防止pHead为空
    assert(pHead->next != pHead); // 防止链表为空
    DListEarse(pHead->next);
}
DLNode* DListFind(DLNode* pHead, DLNodeDataType x) {
    assert(pHead != NULL); //防止pHead为空
    DLNode* cur = pHead->next;
    while(cur != pHead) {
        if (cur->data == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}
// 在pos位置之前插入
void DListInsert(DLNode* pos, DLNodeDataType x) {
    assert(pos != NULL); // 防止传入的pos为空
    DLNode* new_node = CreateNewNode(x);
    DLNode* posPrev = pos->prev; //pos前驱
    //思路草图:posPrev  newnode(待插目标)   pos
    posPrev->next = new_node;
    new_node->prev = posPrev;
    new_node->next = pos;
    pos->prev = new_node;
}
// 删除pos位置
void DListEarse(DLNode* pos) {
    assert(pos != NULL); //防止传入的pos为空
    DLNode* posPrev = pos->prev; //标出pos的前驱指针
    DLNode* posNext = pos->next; //标出pos的后继指针
    //思路草图: posPrev  pos(待删目标)  posNext
    posPrev->next = posNext;
    posNext->prev = posPrev;
    //释放
    free(pos);
    pos = NULL;
}


💬 Test.c


#include "DList.h"
void TestList1() {
    DLNode* pList = DListInit();
    DListPushBack(pList, 1);
    DListPushBack(pList, 2);
    DListPushBack(pList, 3);
    DListPushBack(pList, 4);
    DListPrint(pList);
}
void TestList2() {
    DLNode* pList = DListInit();
    DListPushFront(pList, 10);
    DListPushFront(pList, 20);
    DListPushFront(pList, 30);
    DListPushFront(pList, 40);
    DListPrint(pList);
}
void TestList3() {
    DLNode* pList = DListInit();
    DListPushBack(pList, 1);
    DListPushBack(pList, 2);
    DListPushBack(pList, 3);
    DListPushBack(pList, 4);
    DListPrint(pList);
    DListPopBack(pList);
    DListPrint(pList);
}
void TestList4() {
    DLNode* pList = DListInit();
    DListPushBack(pList, 1);
    DListPushBack(pList, 2);
    DListPushBack(pList, 3);
    DListPushBack(pList, 4);
    DListPrint(pList);
    DListPopFront(pList);
    DListPrint(pList);
}
int main() {
    TestList1();
    // TestList2();
    // TestList3();
    // TestList4();
    return 0;
}
相关文章
|
3月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
93 1
|
4月前
|
存储 Java 开发者
Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效
【10月更文挑战第19天】在软件开发中,随着项目复杂度的增加,数据结构的组织和管理变得至关重要。Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,帮助开发者告别混乱,提升代码质量。
43 1
|
4月前
|
存储 算法 索引
HashMap底层数据结构及其增put删remove查get方法的代码实现原理
HashMap 是基于数组 + 链表 + 红黑树实现的高效键值对存储结构。默认初始容量为16,负载因子为0.75。当存储元素超过容量 * 负载因子时,会进行扩容。HashMap 使用哈希算法计算键的索引位置,通过链表或红黑树解决哈希冲突,确保高效存取。插入、获取和删除操作的时间复杂度接近 O(1)。
42 0
|
4月前
05(数据结构考研)树相关操作代码
05(数据结构考研)树相关操作代码
39 0
|
4月前
|
算法
04(数据结构考研)串相关操作代码
04(数据结构考研)串相关操作代码
26 0
|
3月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
322 9
|
3月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
50 1
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
139 77
|
1月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
42 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
45 9

热门文章

最新文章