深圳幻海软件技术有限公司 欢迎您！
更多

双向链表(数据结构)(C语言)

2023-05-18

next pos 双向
目录概念带头双向循环链表的实现前情提示双向链表的结构体定义双向链表的初始化关于无头单向非循环链表无需初始化函数，顺序表、带头双向循环链表需要的思考双向链表在pos位置之前插入x双向链表的打印双链表删除pos位置的结点双向链表的尾插关于单链表的尾插需要用到二级指针，双向链表不需要用到二级指针的思考双向

目录

概念

带头双向循环链表的实现

前情提示

双向链表的结构体定义

双向链表的初始化

关于无头单向非循环链表无需初始化函数，顺序表、带头双向循环链表需要的思考

双向链表在pos位置之前插入x

双向链表的打印

双链表删除pos位置的结点

双向链表的尾插

关于单链表的尾插需要用到二级指针，双向链表不需要用到二级指针的思考

双向链表的判空

双向链表的尾删

双向链表的头插 

双向链表的头删

双向链表查找值为x的结点

双向链表的销毁 

双向链表的修改

双向链表删除值为x的结点

 双向链表计算结点总数(不计phead)

双向链表获取第i位置的结点

双向链表的清空

总代码（想直接看结果的可以看这里）

概念

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。我们一般构造双向循环链表。循环链表是一种链式存储结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其它结点。

带头双向循环链表的实现

前情提示

List.h  用于  引用的头文件、双向链表的定义、函数的声明。

List.c  用于  函数的定义。

Test.c 用于  双向链表功能的测试。

双向链表的结构体定义

在List.h下

  1. #pragma once//使同一个文件不会被包含(include)多次,不必担心宏名冲突
  2.  
  3. //先将可能使用到的头文件写上
  4. #include<stdio.h>
  5. #include<stdlib.h>
  6. #include<assert.h>
  7. #include<stdbool.h>
  8.  
  9. typedef int LTDataType;//假设结点的数据域类型为 int
  10. //给变量定义一个易于记忆且意义明确的新名字,并且便于以后存储其它类型时方便改动
  11. //（比如我晚点想存double类型的数据，我就直接将 int 改为 double )
  12.  
  13. // 带哨兵位双向循环链表的结构体定义
  14. typedef struct ListNode
  15. {
  16. struct ListNode* prev;//前驱指针域:存放上一个结点的地址
  17. struct ListNode* next;//后继指针域:存放下一个结点的地址
  18. LTDataType data;//数据域
  19. }LTNode;
  20. //struct 关键字和 ListNode 一起构成了这个结构类型
  21. //typedef 为这个结构起了一个别名,叫 LTNode,即：typedef struct ListNode LTNode 
  22. //现在就可以像 int 和 double 那样直接使用 LTNode 来定义变量

双向链表的初始化

在List.h下

  1. // 双向链表的初始化
  2.  
  3. // 如果是单链表直接给个空指针就行，不需要单独写一个函数进行初始化
  4. // 即：LTNode* plist = NULL;
  5. // 那为什么顺序表、带头双向循环链表有呢？
  6. // 因为顺序表、带头双向循环链表的结构并不简单，
  7. // 如:    顺序表顺序表为空size要为0,还要看capacity是否要开空间,
  8. // 若不开空间capacity=0,指针要给空,若开空间,还要检查malloc是否成功
  9. //      带头双向循环链表要开个结点,检查malloc是否成功,然后让结点自己指向自己
  10. // 顺序表和双向循环链表的初始化有点复杂,最好构建一个函数
  11. LTNode* LTInit();

在List.c下

  1. #include"List.h"//别忘了
  2.  
  3. //动态申请一个结点
  4. LTNode* BuyListNode(LTDataType x)
  5. {
  6. LTNode* node = (LTNode*)malloc(sizeof(LTNode));
  7. if (node == NULL)//如果malloc失败
  8. {
  9. perror("malloc fail");
  10. return NULL;
  11. }
  12. //如果malloc成功
  13. //初始化一下，防止野指针，如果看到返回的是空指针，那逻辑可能有些错误
  14. node->next = NULL;
  15. node->prev = NULL;
  16. node->data = x;
  17.  
  18. return node;
  19. }
  20.  
  21. // 双向链表的初始化
  22. LTNode* LTInit()
  23. {
  24. LTNode* phead = BuyListNode(-1);//创建哨兵位
  25. //自己指向自己
  26. phead->next = phead;
  27. phead->prev = phead;
  28.  
  29. return phead;
  30. }

关于无头单向非循环链表无需初始化函数，顺序表、带头双向循环链表需要的思考

无头单向非循环链表结构太简单了，初始化只需直接赋空指针，无需单独写一个函数进行初始化。

即：LTNode* plist = NULL;

那为什么顺序表、带头双向循环链表有单独写一个函数进行初始化呢？
因为顺序表、带头双向循环链表的结构并不简单。
如:

顺序表顺序表为空size要为0,还要看capacity是否要开空间,若不开空间capacity=0,指针要给空，若开空间,还要检查malloc是否成功。

带头双向循环链表要开个结点,检查malloc是否成功,然后让结点自己指向自己。

顺序表和双向循环链表的初始化有点复杂,最好构建一个函数。

双向链表在pos位置之前插入x

在List.h下

  1. // 双向链表在pos位置之前进行插入
  2. void LTInsert(LTNode* pos, LTDataType x);

在List.c下

  1. // 双向链表在pos位置之前进行插入
  2. void LTInsert(LTNode* pos, LTDataType x)
  3. {
  4. assert(pos);//pos肯定不为空
  5.  
  6. LTNode* prev = pos->prev;
  7. LTNode* newnode = BuyListNode(x);//创建一个需要插入的结点
  8.  
  9. prev->next = newnode;
  10. newnode->prev = prev;
  11.  
  12. newnode->next = pos;
  13. pos->prev = newnode;
  14. }

双向链表的打印

在List.h下

  1. // 双向链表打印
  2. void LTPrint(LTNode* phead);

在List.c下

  1. // 双向链表打印
  2. void LTPrint(LTNode* phead)
  3. {
  4. assert(phead);//有哨兵位
  5. printf("<=>phead<=>");
  6. LTNode* cur = phead->next;//cur指向第一个要打印的结点
  7. while (cur != phead)//cur等于头结点时打印就结束了
  8. {
  9. printf("%d<=>", cur->data);
  10. cur = cur->next;
  11. }
  12. printf("\n");
  13. }

在Test.c下

  1. #include"List.h"//别忘了
  2.  
  3. //测试函数
  4. void TestList1()
  5. {
  6. LTNode* plist = LTInit();
  7. LTInsert(plist, 1);
  8. LTInsert(plist, 2);
  9. LTInsert(plist, 3);
  10. LTInsert(plist, 4);
  11. LTPrint(plist);
  12. }
  13.  
  14. int main()
  15. {
  16. TestList1();
  17. return 0;
  18. }

双链表删除pos位置的结点

在List.h下

  1. // 双向链表删除pos位置的结点
  2. void LTErase(LTNode* pos);

在List.c下

  1. // 双向链表删除pos位置的结点
  2. void LTErase(LTNode* pos)
  3. {
  4. assert(pos);//pos肯定不为空
  5.  
  6. LTNode* posprev = pos->prev;
  7. LTNode* posnext = pos->next;
  8.  
  9. posprev->next = posnext;
  10. posnext->prev = posprev;
  11.  
  12. free(pos);
  13. pos = NULL;
  14.     //这个置空其实已经没有意义了，形参的改变不会改变实参
  15. }

在Test.c下

  1. //测试函数
  2. void TestList1()
  3. {
  4. LTNode* plist = LTInit();
  5. LTInsert(plist, 1);
  6. LTInsert(plist, 2);
  7. LTInsert(plist, 3);
  8. LTInsert(plist, 4);
  9. LTPrint(plist);
  10.  
  11. LTErase(plist->next);
  12. LTPrint(plist);
  13.  
  14. }
  15.  
  16. int main()
  17. {
  18. TestList1();
  19. return 0;
  20. }

双向链表的尾插

在List.h下

  1. //双向链表优于单链表的点——不需要找尾、二级指针
  2. //（我们改的不是结构体的指针，改的是结构体的变量）
  3. // 双向链表的尾插
  4. void LTPushBack(LTNode* phead, LTDataType x);

在List.c下

法一:（便于新手更好地理解双向链表的尾插） 

  1. // 双向链表的尾插
  2. void LTPushBack(LTNode* phead, LTDataType x)
  3. {
  4. assert(phead);//有哨兵位
  5.     
  6.     //法一:(便于新手更好地理解双向链表的尾插)
  7. //一步就可完成链表为空/不为空的尾插——因为有哨兵位
  8. LTNode* newnode = BuyListNode(x);//创建一个要插入的结点
  9. LTNode* tail = phead->prev;
  10.  
  11. tail->next = newnode;
  12. newnode->prev = tail;
  13. newnode->next = phead;
  14. phead->prev = newnode;
  15. }

法二：函数复用（简单方便）

  1. // 双向链表的尾插
  2. void LTPushBack(LTNode* phead, LTDataType x)
  3. {
  4. assert(phead);//有哨兵位
  5.  
  6. //法二:函数复用（简单方便）
  7. LTInsert(phead, x);
  8. }

关于单链表的尾插需要用到二级指针，双向链表不需要用到二级指针的思考

单链表改变的是结构体的指针，双向链表改变的是结构体的变量

二级指针和一级指针的区别在于指针所指向变量的层级不同，一级指针指向的是结构体的变量，而二级指针指向的是结构体指针的地址。
单链表中，在进行链表结点的删除或插入操作时，需要更新结点之间的指针指向。若使用一级指针，则操作会直接改变指向结点的指针，很难实现目标。因此需要传递二级指针，让函数能够修改指向结点指针的地址，也就是修改之前结点指针变量存放的地址。
而双向链表中，每个结点除了保存指向下一结点的指针外，还有保存指向上一结点的指针，结点之间的双向指针关系使得结点的插入和删除操作更加方便。双向链表不需要传递二级指针，因为在结点的删除和插入操作中，只需要先修改当前结点前后结点的指针，无需直接改变前后结点指针变量存放的地址。
综上所述，单链表只有指向下一结点的指针，通过传递二级指针来修改结点之间的指针关系，使得操作更加灵活；而双向链表的结点之间有双向指针关系，无需直接改变前后结点指针变量存放的地址，因此只需要传递一级指针即可。

单链表（对比）：

在Test.c下

  1. //测试函数
  2. void TestList2()
  3. {
  4. LTNode* plist = LTInit();
  5. LTPushBack(plist, 5);
  6. LTPushBack(plist, 6);
  7. LTPushBack(plist, 7);
  8. LTPushBack(plist, 8);
  9. LTPrint(plist);
  10. }
  11.  
  12. int main()
  13. {
  14. TestList2();
  15. return 0;
  16. }

双向链表的判空

在尾删/头删之前，我们要先判断链表是否为空。

在List.h下

  1. // 双向链表的判空
  2. bool LTEmpty(LTNode* phead);

在List.c下

  1. // 双向链表的判空
  2. bool LTEmpty(LTNode* phead)
  3. {
  4. assert(phead);
  5.  
  6. return phead->next == phead;
  7. //两者相等就是空链表(返回真),两者不相等就不是空链表(返回假)
  8. }

双向链表的尾删

在List.h下

  1. // 双向链表的尾删
  2. void LTPopBack(LTNode* phead);

在List.c下

法一：（便于新手更好地理解双向链表的尾删）

  1. // 双向链表的尾删
  2. void LTPopBack(LTNode* phead)
  3. {
  4. assert(phead);//有哨兵位
  5. assert(!LTEmpty(phead));//判空
  6.  
  7.     //法一：（便于新手更好地理解双向链表的尾删）
  8. LTNode* tail = phead->prev;
  9. LTNode* tailPrev = tail->prev;
  10.  
  11. tailPrev->next = phead;
  12. phead->prev = tailPrev;
  13. free(tail);
  14. tail = NULL;
  15. }

法二：函数复用（简单方便）

  1. // 双向链表的尾删
  2. void LTPopBack(LTNode* phead)
  3. {
  4. assert(phead);//有哨兵位
  5.     assert(!LTEmpty(phead));//判空
  7.     //法二:函数复用
  8. LTErase(phead->prev);
  9. }

在Test.c下

  1. //测试函数
  2. void TestList2()
  3. {
  4. LTNode* plist = LTInit();
  5. LTPushBack(plist, 5);
  6. LTPushBack(plist, 6);
  7. LTPushBack(plist, 7);
  8. LTPushBack(plist, 8);
  9. LTPrint(plist);
  10.  
  11. LTPopBack(plist);
  12. LTPopBack(plist);
  13. LTPrint(plist);
  14. }
  15.  
  16. int main()
  17. {
  18. TestList2();
  19. return 0;
  20. }

双向链表的头插 

在List.h下

  1. // 双向链表头插
  2. void LTPushFront(LTNode* phead, LTDataType x);

在List.c下

法一:只用phead和newnode两个指针（便于新手更好地理解双向链表的头插）

  1. // 双向链表头插
  2. void LTPushFront(LTNode* phead, LTDataType x)
  3. {
  4. assert(phead);//有哨兵位
  5.  
  6. LTNode* newnode = BuyListNode(x);//创建一个要插入的结点
  7.     
  8.     //法一:只用phead和newnode两个指针（便于新手更好地理解双向链表的头插）
  9.     //顺序很重要！！！
  10. newnode->next = phead->next;
  11. phead->next->prev = newnode;
  12.  
  13. phead->next = newnode;
  14. newnode->prev = phead;
  15. }

法二:多用了first记录第一个结点的位置（便于新手更好地理解双向链表的头插）

  1. // 双向链表头插
  2. void LTPushFront(LTNode* phead, LTDataType x)
  3. {
  4. assert(phead);//哨兵位
  5.  
  6. LTNode* newnode = BuyListNode(x);//创建一个要插入的结点
  7.  
  8. //法二：多用了first先记住第一个结点（便于新手更好地理解双向链表的头插）
  9. LTNode* first = phead->next;
  10. phead->next = newnode;
  11. newnode->prev = phead;
  12.  
  13. newnode->next = first;
  14. first->prev = newnode;
  15. }

法三:函数复用（简单方便）

  1. // 双向链表头插
  2. void LTPushFront(LTNode* phead, LTDataType x)
  3. {
  4. assert(phead);//有哨兵位
  6. //法三:函数复用（简单方便）
  7. LTInsert(phead->next, x);
  8. }

在Test.c下

  1. //测试函数
  2. void TestList3()
  3. {
  4. LTNode* plist = LTInit();
  5. LTPushFront(plist, 1);
  6. LTPushFront(plist, 2);
  7. LTPushFront(plist, 3);
  8. LTPushFront(plist, 4);
  9. LTPrint(plist);
  10. }
  11.  
  12. int main()
  13. {
  14. TestList3();
  15. return 0;
  16. }

双向链表的头删

在List.h下

  1. // 双向链表头删
  2. void LTPopFront(LTNode* phead);

在List.c下

法一:（便于新手更好地理解双向链表的头删）

  1. // 双向链表头删
  2. void LTPopFront(LTNode* phead)
  3. {
  4. assert(phead);//有哨兵位
  5. assert(!LTEmpty(phead));//判空
  7.     //法一:（便于新手更好地理解双向链表的头删）
  8. LTNode* head = phead->next;
  9. LTNode* headnext = head->next;
  10.  
  11. phead->next = headnext;
  12. headnext->prev = phead;
  13.  
  14. free(head);
  15. head = NULL;
  16. }

法二:函数复用（简单方便） 

  1. // 双向链表头删
  2. void LTPopFront(LTNode* phead)
  3. {
  4. assert(phead);//有哨兵位
  5.     assert(!LTEmpty(phead));//判空
  7.     //法二:函数复用（简单方便）
  8. LTErase(phead->next);
  9. }

在Test.c下

  1. //测试函数
  2. void TestList3()
  3. {
  4. LTNode* plist = LTInit();
  5. LTPushFront(plist, 1);
  6. LTPushFront(plist, 2);
  7. LTPushFront(plist, 3);
  8. LTPushFront(plist, 4);
  9. LTPrint(plist);
  10.  
  11. LTPopFront(plist);
  12. LTPopFront(plist);
  13. LTPrint(plist);
  14. }
  15.  
  16. int main()
  17. {
  18. TestList3();
  19. return 0;
  20. }

双向链表查找值为x的结点

在List.h下

  1. // 双向链表查找值为x的结点
  2. LTNode* LTFind(LTNode* phead, LTDataType x);

在List.c下

  1. // 双向链表查找值为x的结点
  2. LTNode* LTFind(LTNode* phead, LTDataType x)
  3. {
  4. assert(phead);//有哨兵位
  5.  
  6. LTNode* cur = phead->next;
  7. while (cur != phead)//让cur去遍历
  8. {
  9. if (cur->data == x)//如果找到
  10. {
  11. return cur;
  12. }
  13. cur = cur->next;
  14. }
  15. return NULL;//如果没找到
  16. }

在Test.c下

  1. //测试函数
  2. TestList4()
  3. {
  4. LTNode* plist = LTInit();
  5. LTInsert(plist, 1);
  6. LTInsert(plist, 2);
  7. LTInsert(plist, 3);
  8. LTInsert(plist, 4);
  9. LTPrint(plist);
  10.  
  11. LTNode* pos = LTFind(plist, 3);
  12. if (pos)
  13. {
  14. LTErase(pos);
  15. pos = NULL;
  16. }
  17.  
  18. LTPrint(plist);
  19. }
  20.  
  21. int main()
  22. {
  23. TestList4();
  24. return 0;
  25. }

双向链表的销毁 

在List.h下

  1. // 双向链表的销毁
  2. void LTDestory(LTNode* phead);

在List.c下

   

  

 

  1. // 双向链表的销毁
  2. void LTDestory(LTNode* phead)
  3. {
  4. assert(phead);
  5.  
  6. LTNode* cur = phead->next;//让cur遍历
  7. while (cur != phead)
  8. {
  9. LTNode* curnext = cur->next;
  10. free(cur);
  11. cur = curnext;
  12. }
  13. free(phead);
  14. phead = NULL;
  15. //这个置空其实已经没有意义了，形参的改变不会改变实参
  16. //我们为了保持接口的一致性,不传二级指针,选择在测试的时候置空
  17. }

在Test.c下

  1. //测试函数
  2. TestList4()
  3. {
  4. LTNode* plist = LTInit();
  5. LTInsert(plist, 1);
  6. LTInsert(plist, 2);
  7. LTInsert(plist, 3);
  8. LTInsert(plist, 4);
  9. LTPrint(plist);
  10.  
  11. LTNode* pos = LTFind(plist, 3);
  12. if (pos)
  13. {
  14. LTErase(pos);
  15. pos = NULL;
  16. }
  17. LTPrint(plist);
  18.  
  19. LTDestory(plist);
  20. plist = NULL;//在这里置空
  21. }

双向链表的修改

在List.h下

  1. // 双向链表的修改,修改pos位置的值为x
  2. void LTModify(LTNode* pos, LTDataType x);

在List.c下

  1. // 双向链表的修改,修改pos位置的值为x
  2. void LTModify(LTNode* pos, LTDataType x)
  3. {
  4. assert(pos);
  5. pos->data = x;
  6. }

在Test.c下

  1. //测试函数
  2. TestList5()
  3. {
  4. LTNode* plist = LTInit();
  5. LTInsert(plist, 1);
  6. LTInsert(plist, 2);
  7. LTInsert(plist, 3);
  8. LTInsert(plist, 4);
  9. LTPrint(plist);
  10.  
  11. LTModify(plist->next,5);
  12. LTPrint(plist);
  13. }
  14.  
  15. int main()
  16. {
  17. TestList5();
  18. return 0;
  19. }

双向链表删除值为x的结点

在List.h下

  1. // 双向链表删除值为x的结点
  2. void LTRemove(LTNode* phead,LTDataType x);

在List.c下

  1. // 双向链表删除值为x的结点
  2. void LTRemove(LTNode* phead, LTDataType x)
  3. {
  4. assert(phead);//有哨兵位
  5. LTNode* pos = phead->next;
  6. while (pos != phead)
  7. {
  8. pos = LTFind(phead, x);
  9. if (pos == NULL)//如果遍历完
  10. {
  11. return NULL;
  12. }
  13. LTErase(pos);
  14. pos = pos->next;
  15. }
  16. }

在Test.c下

  1. TestList6()
  2. {
  3. LTNode* plist = LTInit();
  4. LTInsert(plist, 1);
  5. LTInsert(plist, 3);
  6. LTInsert(plist, 3);
  7. LTInsert(plist, 4);
  8. LTInsert(plist, 3);
  9. LTPrint(plist);
  10.  
  11. LTRemove(plist, 3);
  12. LTPrint(plist);
  13. }
  14.  
  15. int main()
  16. {
  17. TestList6();
  18. return 0;
  19. }

 双向链表计算结点总数(不计phead)

在List.h下

  1. // 双向链表计算结点总数(不计phead)
  2. int LTTotal(LTNode* phead);

在List.c下

  1. // 双向链表计算结点总数(不计phead)
  2. int LTTotal(LTNode* phead)
  3. {
  4. assert(phead);//有哨兵位
  5.  
  6. int count = 0;//count来计数
  7. LTNode* cur = phead->next;//让cur去遍历
  8. while (cur != phead)
  9. {
  10. count++;
  11. cur = cur->next;
  12. }
  13. return count;
  14. }

在Test.c下

  1. TestList6()
  2. {
  3. LTNode* plist = LTInit();
  4. LTInsert(plist, 1);
  5. LTInsert(plist, 3);
  6. LTInsert(plist, 3);
  7. LTInsert(plist, 4);
  8. LTInsert(plist, 3);
  9. LTPrint(plist);
  10.  
  11. LTRemove(plist, 3);
  12. LTPrint(plist);
  13.  
  14. printf("%d\n", LTTotal(plist));
  15. }
  16.  
  17. int main()
  18. {
  19. TestList6();
  20. return 0;
  21. }

双向链表获取第i位置的结点

在List.h下

  1. // 双向链表获取第i位置的结点
  2. LTNode* LTGet(LTNode* phead, int i);

在List.c下

  1. // 双向链表获取第i位置的结点
  2. LTNode* LTGet(LTNode* phead, int i)
  3. {
  4. assert(phead);//有哨兵位
  5.  
  6. int length = LTTotal(phead);
  7. LTNode* cur = phead->next;
  8. if (i == 0)
  9. {
  10. return phead;
  11. }
  12. else if (i<0 || i>length)//位置不合法
  13. {
  14. return NULL;
  15. }
  16. else if (i <= (length / 2))//从表头开始遍历
  17. {
  18. cur = phead->next;
  19. for (int count = 1; count < i; count++)
  20. {
  21. cur = cur->next;
  22. }
  23. }
  24. else//从表尾开始遍历
  25. {
  26. cur = phead->prev;
  27. for (int count = 1; count <= length - i; count++)
  28. {
  29. cur = cur->prev;
  30. }
  31. }
  32. return cur;
  33. }

在Test.c下

  1. //测试函数
  2. TestList7()
  3. {
  4. LTNode* plist = LTInit();
  5. LTInsert(plist, 5);
  6. LTInsert(plist, 6);
  7. LTInsert(plist, 7);
  8. LTInsert(plist, 8);
  9. LTInsert(plist, 9);
  10. LTPrint(plist);
  11.  
  12. LTNode* pos = LTGet(plist,3);
  13. if (pos)
  14. {
  15. LTErase(pos);
  16. pos = NULL;
  17. }
  18. LTPrint(plist);
  19. }
  20.  
  21. int main()
  22. {
  23. TestList7();
  24. return 0;
  25. }

双向链表的清空

在List.h下

  1. // 双向链表的清空
  2. void LTClean(LTNode* phead);

在List.c下

  1. // 双向链表的清空
  2. void LTClear(LTNode* phead)
  3. {
  4. assert(phead);//有哨兵位
  5.  
  6. while (!LTEmpty(phead))//如果不为空就一直头删
  7. {
  8. LTPopFront(phead);
  9. }
  10. }

在Test.c下

  1. //测试函数
  2. TestList8()
  3. {
  4. LTNode* plist = LTInit();
  5. LTInsert(plist, 5);
  6. LTInsert(plist, 6);
  7. LTInsert(plist, 7);
  8. LTInsert(plist, 8);
  9. LTInsert(plist, 9);
  10. LTPrint(plist);
  11.  
  12. LTClear(plist);
  13. LTPrint(plist);
  14. }
  15.  
  16. int main()
  17. {
  18. TestList8();
  19. return 0;
  20. }

总代码（想直接看结果的可以看这里）

在List.h下

  1. #pragma once//使同一个文件不会被包含(include)多次,不必担心宏名冲突
  2.  
  3.  
  4. //先将可能使用到的头文件写上
  5. #include<stdio.h>
  6. #include<stdlib.h>
  7. #include<assert.h>
  8. #include<stdbool.h>
  9.  
  10. typedef int LTDataType;//假设结点的数据域类型为 int
  11. //给变量定义一个易于记忆且意义明确的新名字,并且便于以后存储其它类型时方便改动
  12. //（比如我晚点想存double类型的数据，我就直接将 int 改为 double )
  13.  
  14. // 带哨兵位双向循环链表的结构体定义
  15. typedef struct ListNode
  16. {
  17. struct ListNode* prev;//前驱指针域:存放上一个结点的地址
  18. struct ListNode* next;//后继指针域:存放下一个结点的地址
  19. LTDataType data;//数据域
  20. }LTNode;
  21. //struct 关键字和 ListNode 一起构成了这个结构类型
  22. //typedef 为这个结构起了一个别名,叫 LTNode,即：typedef struct ListNode LTNode 
  23. //现在就可以像 int 和 double 那样直接使用 LTNode 来定义变量
  24.  
  25.  
  26.  
  27. // 双向链表的初始化
  28.  
  29. // 如果是单链表直接给个空指针就行，不需要单独写一个函数进行初始化
  30. // 即：LTNode* plist = NULL;
  31. // 那为什么顺序表、带头双向循环链表有呢？
  32. // 因为顺序表、带头双向循环链表的结构并不简单，
  33. // 如:顺序表顺序表为空size要为0,还要看capacity是否要开空间,
  34. //若不开空间capacity=0,指针要给空,若开空间,还要检查malloc是否成功
  35. // 带头双向循环链表要开个结点,检查malloc是否成功,然后让结点自己指向自己
  36. // 顺序表和双向循环链表的初始化有点复杂,最好构建一个函数
  37. LTNode* LTInit();
  38.  
  39. // 双向链表在pos位置之前进行插入x
  40. void LTInsert(LTNode* pos, LTDataType x);
  41.  
  42. // 双向链表的打印
  43. void LTPrint(LTNode* phead);
  44.  
  45. // 双向链表删除pos位置的结点
  46. void LTErase(LTNode* pos);
  47.  
  48. //双向链表优于单链表的点——不需要找尾、二级指针
  49. // （我们改的不是结构体的指针，改的是结构体的变量）
  50. // 双向链表的尾插
  51. void LTPushBack(LTNode* phead, LTDataType x);
  52.  
  53. // 双向链表的判空
  54. bool LTEmpty(LTNode* phead);
  55.  
  56. // 双向链表的尾删
  57. void LTPopBack(LTNode* phead);
  58.  
  59. // 双向链表头插
  60. void LTPushFront(LTNode* phead, LTDataType x);
  61.  
  62. // 双向链表头删
  63. void LTPopFront(LTNode* phead);
  64.  
  65. // 双向链表查找值为x的结点
  66. LTNode* LTFind(LTNode* phead, LTDataType x);
  67.  
  68. // 双向链表的销毁
  69. void LTDestory(LTNode* phead);
  70.  
  71. // 双向链表的修改,修改pos位置的值为x
  72. void LTModify(LTNode* pos, LTDataType x);
  73.  
  74. // 双向链表删除值为x的结点
  75. void LTRemove(LTNode* phead, LTDataType x);
  76.  
  77. // 双向链表计算结点总数(不计phead)
  78. int LTTotal(LTNode* phead);
  79.  
  80. // 双向链表获取第i位置的结点
  81. LTNode* LTGet(LTNode* phead, int i);
  82.  
  83. // 双向链表的清空
  84. void LTClear(LTNode* phead);

在List.c下

  1. #include"List.h"
  2.  
  3. //动态申请一个结点
  4. LTNode* BuyListNode(LTDataType x)
  5. {
  6. LTNode* node = (LTNode*)malloc(sizeof(LTNode));
  7. if (node == NULL)//如果malloc失败
  8. {
  9. perror("malloc fail");
  10. return NULL;
  11. }
  12. //如果malloc成功
  13. //初始化一下，防止野指针，如果看到返回的是空指针，那逻辑可能有些错误
  14. node->next = NULL;
  15. node->prev = NULL;
  16. node->data = x;
  17.  
  18. return node;
  19. }
  20.  
  21. // 双向链表的初始化
  22. LTNode* LTInit()
  23. {
  24. LTNode* phead = BuyListNode(-1);
  25. //自己指向自己
  26. phead->next = phead;
  27. phead->prev = phead;
  28.  
  29. return phead;
  30. }
  31.  
  32. // 双向链表在pos位置之前进行插入x
  33. void LTInsert(LTNode* pos, LTDataType x)
  34. {
  35. assert(pos);//pos肯定不为空
  36.  
  37. LTNode* prev = pos->prev;
  38. LTNode* newnode = BuyListNode(x);//创建一个需要插入的结点
  39.  
  40. prev->next = newnode;
  41. newnode->prev = prev;
  42.  
  43. newnode->next = pos;
  44. pos->prev = newnode;
  45. }
  46.  
  47. // 双向链表的打印
  48. void LTPrint(LTNode* phead)
  49. {
  50. assert(phead);//有哨兵位
  51. printf("<=>phead<=>");
  52. LTNode* cur = phead->next;//cur指向第一个要打印的结点
  53. while (cur != phead)//cur等于头结点时打印就结束了
  54. {
  55. printf("%d<=>", cur->data);
  56. cur = cur->next;
  57. }
  58. printf("\n");
  59. }
  60.  
  61. // 双向链表删除pos位置的结点
  62. void LTErase(LTNode* pos)
  63. {
  64. assert(pos);//pos肯定不为空
  65.  
  66. LTNode* posprev = pos->prev;
  67. LTNode* posnext = pos->next;
  68.  
  69. posprev->next = posnext;
  70. posnext->prev = posprev;
  71.  
  72. free(pos);
  73. pos = NULL;
  74. //这个置空其实已经没有意义了，形参的改变不会改变实参
  75. }
  76.  
  77. // 双向链表的尾插
  78. void LTPushBack(LTNode* phead, LTDataType x)
  79. {
  80. assert(phead);//有哨兵位
  81.  
  82. //法一:（便于新手更好地理解双向链表的尾插）
  83. //一步就可完成链表为空/不为空的尾插
  84. //LTNode* newnode = BuyListNode(x);
  85. //LTNode* tail = phead->prev;
  86.  
  87. //tail->next = newnode;
  88. //newnode->prev = tail;
  89. //newnode->next = phead;
  90. //phead->prev = newnode;
  91.  
  92. //法二:函数复用（简单方便）
  93. LTInsert(phead, x);
  94. }
  95.  
  96. // 双向链表的判空
  97. bool LTEmpty(LTNode* phead)
  98. {
  99. assert(phead);
  100.  
  101. return phead->next == phead;
  102. //两者相等就是空链表(返回真),两者不相等就不是空链表(返回假)
  103. }
  104.  
  105. // 双向链表的尾删
  106. void LTPopBack(LTNode* phead)
  107. {
  108. assert(phead);//有哨兵位
  109.  
  110. //法一:（便于新手更好地理解双向链表的尾删）
  111. //assert(!LTEmpty(phead));//判空
  112.  
  113. //LTNode* tail = phead->prev;
  114. //LTNode* tailPrev = tail->prev;
  115.  
  116. //tailPrev->next = phead;
  117. //phead->prev = tailPrev;
  118. //free(tail);
  119. //tail = NULL;
  120.  
  121. //法二:函数复用
  122. LTErase(phead->prev);
  123. }
  124.  
  125. // 双向链表头插
  126. void LTPushFront(LTNode* phead, LTDataType x)
  127. {
  128. assert(phead);//有哨兵位
  129.  
  130. //LTNode* newnode = BuyListNode(x);//创建一个要插入的结点
  131.  
  132. //法一:只用phead和newnode两个指针（便于新手更好地理解双向链表的头插）
  133. //newnode->next = phead->next;
  134. //phead->next->prev = newnode;
  135.  
  136. //phead->next = newnode;
  137. //newnode->prev = phead;
  138.  
  139. //法二:多用了first先记住第一个结点（便于新手更好地理解双向链表的头插）
  140. //LTNode* first = phead->next;
  141. //phead->next = newnode;
  142. //newnode->prev = phead;
  143.  
  144. //newnode->next = first;
  145. //first->prev = newnode;
  146.  
  147. //法三:函数复用(简单方便)
  148. LTInsert(phead->next, x);
  149. }
  150.  
  151. // 双向链表头删
  152. void LTPopFront(LTNode* phead)
  153. {
  154. assert(phead);//有哨兵位
  155. assert(!LTEmpty(phead));//判空
  156.  
  157. //法一:（便于新手更好地理解双向链表的头删）
  158. //LTNode* head = phead->next;
  159. //LTNode* headnext = head->next;
  160.  
  161. //phead->next = headnext;
  162. //headnext->prev = phead;
  163.  
  164. //free(head);
  165. //head = NULL;
  166.  
  167. //法二:函数复用（简单方便）
  168. LTErase(phead->next);
  169. }
  170.  
  171. // 双向链表查找值为x的结点
  172. LTNode* LTFind(LTNode* phead, LTDataType x)
  173. {
  174. assert(phead);//有哨兵位
  175.  
  176. LTNode* cur = phead->next;
  177. while (cur != phead)//让cur去遍历
  178. {
  179. if (cur->data == x)
  180. {
  181. return cur;
  182. }
  183. cur = cur->next;
  184. }
  185. return NULL;
  186. }
  187.  
  188. // 双向链表的销毁
  189. void LTDestory(LTNode* phead)
  190. {
  191. assert(phead);
  192.  
  193. LTNode* cur = phead->next;
  194. while (cur != phead)
  195. {
  196. LTNode* curnext = cur->next;
  197. free(cur);
  198. cur = curnext;
  199. }
  200. free(phead);
  201. phead = NULL;
  202. //这个置空其实已经没有意义了，形参的改变不会改变实参
  203. //我们为了保持接口的一致性,不传二级指针,选择在测试的时候置空
  204. }
  205.  
  206. // 双向链表的修改,修改pos位置的值为x
  207. void LTModify(LTNode* pos, LTDataType x)
  208. {
  209. assert(pos);//pos肯定不为空
  210. pos->data = x;
  211. }
  212.  
  213. // 双向链表删除值为x的结点
  214. void LTRemove(LTNode* phead, LTDataType x)
  215. {
  216. assert(phead);//有哨兵位
  217. LTNode* pos = phead->next;
  218. while (pos != phead)
  219. {
  220. pos = LTFind(phead, x);
  221. if (pos == NULL)//如果遍历完
  222. {
  223. return NULL;
  224. }
  225. LTErase(pos);
  226. pos = pos->next;
  227. }
  228. }
  229.  
  230. // 双向链表计算结点总数(不计phead)
  231. int LTTotal(LTNode* phead)
  232. {
  233. assert(phead);//有哨兵位
  234.  
  235. int count = 0;//count来计数
  236. LTNode* cur = phead->next;//让cur去遍历
  237. while (cur != phead)
  238. {
  239. count++;
  240. cur = cur->next;
  241. }
  242. return count;
  243. }
  244.  
  245. // 双向链表获取第i位置的结点
  246. LTNode* LTGet(LTNode* phead, int i)
  247. {
  248. assert(phead);//有哨兵位
  249.  
  250. int length = LTTotal(phead);
  251. LTNode* cur = phead->next;
  252. if (i == 0)
  253. {
  254. return phead;
  255. }
  256. else if (i<0 || i>length)//位置不合法
  257. {
  258. return NULL;
  259. }
  260. else if (i <= (length / 2))//从表头开始遍历
  261. {
  262. cur = phead->next;
  263. for (int count = 1; count < i; count++)
  264. {
  265. cur = cur->next;
  266. }
  267. }
  268. else//从表尾开始遍历
  269. {
  270. cur = phead->prev;
  271. for (int count = 1; count <= length - i; count++)
  272. {
  273. cur = cur->prev;
  274. }
  275. }
  276. return cur;
  277. }
  278.  
  279. // 双向链表的清空
  280. void LTClear(LTNode* phead)
  281. {
  282. assert(phead);//有哨兵位
  283.  
  284. while (!LTEmpty(phead))//如果不为空就一直头删
  285. {
  286. LTPopFront(phead);
  287. }
  288. }

在Test.c下

  1. #include"List.h"
  2.  
  3. //测试函数
  4. void TestList1()
  5. {
  6. LTNode* plist = LTInit();
  7. LTInsert(plist, 1);
  8. LTInsert(plist, 2);
  9. LTInsert(plist, 3);
  10. LTInsert(plist, 4);
  11. LTPrint(plist);
  12.  
  13. LTErase(plist->next);
  14. LTPrint(plist);
  15.  
  16. }
  17.  
  18. //测试函数
  19. void TestList2()
  20. {
  21. LTNode* plist = LTInit();
  22. LTPushBack(plist, 5);
  23. LTPushBack(plist, 6);
  24. LTPushBack(plist, 7);
  25. LTPushBack(plist, 8);
  26. LTPrint(plist);
  27.  
  28. LTPopBack(plist);
  29. LTPopBack(plist);
  30. LTPrint(plist);
  31.  
  32. }
  33.  
  34. //测试函数
  35. void TestList3()
  36. {
  37. LTNode* plist = LTInit();
  38. LTPushFront(plist, 1);
  39. LTPushFront(plist, 2);
  40. LTPushFront(plist, 3);
  41. LTPushFront(plist, 4);
  42. LTPrint(plist);
  43.  
  44. LTPopFront(plist);
  45. LTPopFront(plist);
  46. LTPrint(plist);
  47. }
  48.  
  49. //测试函数
  50. TestList4()
  51. {
  52. LTNode* plist = LTInit();
  53. LTInsert(plist, 1);
  54. LTInsert(plist, 2);
  55. LTInsert(plist, 3);
  56. LTInsert(plist, 4);
  57. LTPrint(plist);
  58.  
  59. LTNode* pos = LTFind(plist, 3);
  60. if (pos)
  61. {
  62. LTErase(pos);
  63. pos = NULL;
  64. }
  65. LTPrint(plist);
  66.  
  67. LTDestory(plist);
  68. plist = NULL;//在这里置空
  69. }
  70.  
  71. //测试函数
  72. TestList5()
  73. {
  74. LTNode* plist = LTInit();
  75. LTInsert(plist, 1);
  76. LTInsert(plist, 2);
  77. LTInsert(plist, 3);
  78. LTInsert(plist, 4);
  79. LTPrint(plist);
  80.  
  81. LTModify(plist->next, 5);
  82. LTPrint(plist);
  83.  
  84. }
  85.  
  86. TestList6()
  87. {
  88. LTNode* plist = LTInit();
  89. LTInsert(plist, 1);
  90. LTInsert(plist, 3);
  91. LTInsert(plist, 3);
  92. LTInsert(plist, 4);
  93. LTInsert(plist, 3);
  94. LTPrint(plist);
  95.  
  96. LTRemove(plist, 3);
  97. LTPrint(plist);
  98.  
  99. printf("%d\n", LTTotal(plist));
  100. }
  101.  
  102. //测试函数
  103. TestList7()
  104. {
  105. LTNode* plist = LTInit();
  106. LTInsert(plist, 5);
  107. LTInsert(plist, 6);
  108. LTInsert(plist, 7);
  109. LTInsert(plist, 8);
  110. LTInsert(plist, 9);
  111. LTPrint(plist);
  112.  
  113. LTNode* pos = LTGet(plist, 3);
  114. if (pos)
  115. {
  116. LTErase(pos);
  117. pos = NULL;
  118. }
  119. LTPrint(plist);
  120.  
  121. LTClear(plist);
  122. LTPrint(plist);
  123. }
  124.  
  125. //测试函数
  126. TestList8()
  127. {
  128. LTNode* plist = LTInit();
  129. LTInsert(plist, 5);
  130. LTInsert(plist, 6);
  131. LTInsert(plist, 7);
  132. LTInsert(plist, 8);
  133. LTInsert(plist, 9);
  134. LTPrint(plist);
  135.  
  136. LTClear(plist);
  137. LTPrint(plist);
  138. }
  139.  
  140. int main()
  141. {
  142. //TestList1();
  143. //TestList2();
  144. //TestList3();
  145. //TestList4();
  146. //TestList5();
  147. //TestList6();
  148. //TestList7();
  149. TestList8();
  150. return 0;
  151. }

欢迎指正❀

 

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览46513 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪