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

【数据结构与算法】双向带头循环链表（附源码）

2023-04-13

next cur prev
 目录一.前言二.双向带头循环链表的结构三.接口实现A.初始化ListNodeinit和销毁Listdestroy1.ListNodeinit2.ListdestroyB.插入1.头插 ListNodepushfront2.尾插 ListNodepushback3.插入

 

目录

一.前言

二.双向带头循环链表的结构

三.接口实现

A.初始化 ListNodeinit 和销毁 Listdestroy

1.ListNodeinit

2.Listdestroy

B.插入

1.头插  ListNodepushfront

2.尾插 ListNodepushback

3.插入 ListNodeinsert

C.删除

1.头删 ListNodepopfront

2.尾删 ListNodepopback

3.删除 ListNodeerase

D.打印  ListNodeprint

四.源码

List.h

List.c

test.c

一.前言

在前面的博客中，我们学习了顺序表和结构最简单的链表——单链表，但是单链表存在在着一些不足，比如单链表的插入和删除的操作，总是要找到指定节点的前驱或是后继，这样就会比较麻烦。

那么本篇文章所讲述的双向带头循环链表（以后简称双链表），就可以很好解决这个问题。

二.双向带头循环链表的结构

1.该链表有一个哨兵位节点，即头节点；

2.每个节点都包含一个prev 指针和 next 指针，分别指向当前节点的前驱和后继；

3.头节点的 prev 指向的是尾节点，尾节点的next 指向的是头节点，这样就实现了循环。

请看图示：

 别看结构这么复杂，但其实它是一个很厉害的结构，代码实现会很简单。

三.接口实现

A.初始化 ListNodeinit 和销毁 Listdestroy

1.ListNodeinit

这个接口用来创建哨兵位头节点，并使该节点的 prev 和 next 都指向自己以实现循环的目的。

  1. LNode* Buynewnode(DLdatatype x)   //定义一个 malloc 新节点的函数，以便后续需要
  2. {
  3. LNode* newnode = (LNode*)malloc(sizeof(LNode));
  4. assert(newnode);
  5. newnode->prev = NULL;
  6. newnode->next = NULL;
  7. newnode->data = x;
  8. return newnode;
  9. }
  10. LNode* ListNodeinit()
  11. {
  12. LNode* phead = (LNode*)malloc(sizeof(LNode));
  13. assert(phead);
  14. phead->prev = phead;  //使其都指向自己
  15. phead->next = phead;
  16. phead->data = -1;
  17. return phead;
  18. }

2.Listdestroy

我们需要遍历链表，并定义一个next 来保存 cur 的下一个节点，在链表都free 完后，再销毁头节点；

注意：应该是从头节点的 next 开始遍历。

  1. void ListNodedestroy(LNode* phead)
  2. {
  3. assert(phead);
  4.  
  5. LNode* cur = phead->next;
  6. while (cur != phead)
  7. {
  8. LNode* next = cur->next;
  9. free(cur);
  10. cur = next;
  11. }
  12.  
  13. free(phead);
  14. phead = NULL;
  15. }

B.插入

1.头插  ListNodepushfront

1.这里要头插就太简单了，但是我们最好保存一下头节点的 next ，这样就不应考虑链接时的顺序问题；

2.使头节点的 next 指向新节点，然后新节点的 prev 指向头节点；

3.新节点的 next 指向保存的节点，保存的节点的 prev 指向新节点；

这里并不需要考虑链表为空的情况，这就是双链表的强大之处。

  1. void ListNodepushfront(LNode* phead, DLdatatype x)
  2. {
  3. assert(phead);
  4.  
  5. LNode* newnode = Buynewnode(x);
  6.  
  7. LNode* first = phead->next;  //保存头节点的下一个
  8.  
  9. phead->next = newnode;
  10. newnode->prev = phead;
  11. newnode->next = first;
  12. first->prev = newnode;
  13. }
  14.

2.尾插 ListNodepushback

1.尾插就需要找尾；

2.这里的找尾很简单，就是头节点的 prev；

3.将尾节点与新节点链接起来。

  1. void ListNodepushback(LNode* phead, DLdatatype x)
  2. {
  3. assert(phead);
  4.  
  5. LNode* newnode = Buynewnode(x);
  6. LNode* tail = phead->prev;
  7. tail->next = newnode;
  8. newnode->prev = tail;
  9. newnode->next = phead;
  10. phead->prev = newnode;
  11.  
  12. }

3.插入 ListNodeinsert

1.再插入前需要写一个 find 函数，用来寻找指定的位置 pos；

2.找到 pos 的前驱 prev ；

3.将前驱，pos，新节点链接起来。

  1. LNode* ListNodefind(LNode* phead,DLdatatype x)
  2. {
  3. assert(phead);
  4.  
  5. LNode* cur = phead->next;
  6. while (cur != phead)
  7. {
  8. if (cur->data == x)
  9. {
  10. return cur;
  11. }
  12.  
  13. cur = cur->next;
  14.  
  15. }
  16.  
  17. return NULL;
  18. }
  19.  
  20. void ListNodeinsert(LNode* pos, LNode* phead, DLdatatype x)
  21. {
  22. assert(phead);
  23. assert(pos);
  24.  
  25. LNode* newnode = Buynewnode(x);
  26. LNode* prev = pos->prev;
  27.  
  28. prev->next = newnode;
  29. newnode->prev = prev;
  30. newnode->next = pos;
  31. pos->prev = newnode;
  32. }

总结：其实可以用一个插入接口就可以实现头插和尾插这两个接口。

C.删除

1.删除时要注意的点是不能把头节点也给删了，如果删了就破坏了双链表的结构；

2.如果是空链表也不能删除。

1.头删 ListNodepopfront

1.删除时保存其下一个节点；

2.链接头节点 phead 和 保存的下一个节点；

3.删除 phead 的next。

  1. void ListNodepopfront(LNode* phead)
  2. {
  3. assert(phead);
  4. assert(ListNodeempty(phead));
  5. if (phead->next == phead)
  6. {
  7. perror("ListNodepopfront");
  8. return;
  9. }
  10.  
  11. LNode* first = phead->next;
  12. LNode* second = first->next;
  13. phead->next = second;
  14. second->prev = phead;
  15.  
  16. free(first);
  17. first = NULL;
  18.  
  20. }

2.尾删 ListNodepopback

1.找尾，即：phead的prev；

2.找尾节点的前驱 prev ，使其next指向phead，phead的prev指向该前驱；

  1. void ListNodepopback(LNode* phead)
  2. {
  3. assert(phead);
  4. assert(ListNodeempty(phead));
  5.  
  6. if (phead->next == phead)
  7. {
  8. perror("ListNodepopback");
  9. exit(-1);
  10. }
  11.  
  12. LNode* tail = phead->prev;
  13. LNode* prev = tail->prev;
  14.  
  15. prev->next = phead;
  16. phead->prev = prev;
  17. free(tail);
  18. tail = NULL;
  19. }

3.删除 ListNodeerase

1.调用 find 函数找到要删除的节点pos；

2.找到 pos 的前驱和后继；

3.链接其前驱，后继；

4.删除pos。

  1. void ListNodeerase(LNode* pos, LNode* phead)
  2. {
  3. assert(phead);
  4. assert(pos);
  5.  
  6. if (phead->next == phead)
  7. {
  8. perror("ListNodeerase");
  9. exit(-1);
  10. }
  11. LNode* prev = pos->prev;
  12. LNode* next = pos->next;
  13.  
  14. prev->next = next;
  15. next->prev = prev;
  16.  
  17. free(pos);
  18. pos = NULL;
  19. }

总结：这里可以复用删除函数去实现头删和尾删。

D.打印  ListNodeprint

注意是从头节点的下一个节点开始遍历，且循环终止条件是看是否等于 phead，因为双链表没有 NULL。

  1. void ListNodeprint(LNode* phead)
  2. {
  3. assert(phead);
  4. LNode* cur = phead->next;
  5. while (cur != phead)
  6. {
  7. printf("%d <=> ", cur->data);
  8. cur = cur->next;
  9. }
  10.  
  11. printf("\n");
  12.  
  14. }

四.源码

List.h

  1. #pragma once
  2.  
  3.  
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <assert.h>
  7. #include <stdbool.h>
  8.  
  9. typedef int DLdatatype;
  10.  
  11. typedef struct ListNode
  12. {
  13. struct ListNode* prev;
  14. struct ListNode* next;
  15. DLdatatype data;
  16. }LNode;
  17.  
  18. LNode* ListNodeinit();
  19.  
  20. void ListNodeprint(LNode* phead);
  21.  
  22. void ListNodepushback(LNode*phead,DLdatatype x);
  23.  
  24. void ListNodepushfront(LNode* phead, DLdatatype x);
  25.  
  26. void ListNodepopback(LNode* phead);
  27.  
  28. void ListNodepopfront(LNode* phead);
  29.  
  30. LNode* ListNodefind(LNode* phead,DLdatatype x);
  31.  
  32. void ListNodeinsert(LNode* pos, LNode* phead, DLdatatype x);
  33.  
  34. void ListNodeerase(LNode* pos, LNode* phead);
  35.  
  36. void ListNodedestroy(LNode* phead);

List.c

  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #include "List.h"
  4.  
  5. LNode* Buynewnode(DLdatatype x)
  6. {
  7. LNode* newnode = (LNode*)malloc(sizeof(LNode));
  8. assert(newnode);
  9. newnode->prev = NULL;
  10. newnode->next = NULL;
  11. newnode->data = x;
  12. return newnode;
  13. }
  14.  
  15. LNode* ListNodeinit()
  16. {
  17. LNode* phead = (LNode*)malloc(sizeof(LNode));
  18. assert(phead);
  19. phead->prev = phead;
  20. phead->next = phead;
  21. phead->data = -1;
  22. return phead;
  23. }
  24.  
  25. void ListNodeprint(LNode* phead)
  26. {
  27. assert(phead);
  28. LNode* cur = phead->next;
  29. while (cur != phead)
  30. {
  31. printf("%d <=> ", cur->data);
  32. cur = cur->next;
  33. }
  34.  
  35. printf("\n");
  36.  
  38. }
  39.  
  40. void ListNodepushback(LNode* phead, DLdatatype x)
  41. {
  42. assert(phead);
  43.  
  44. /*LNode* newnode = Buynewnode(x);
  45. LNode* tail = phead->prev;
  46. tail->next = newnode;
  47. newnode->prev = tail;
  48. newnode->next = phead;
  49. phead->prev = newnode;*/
  50.  
  51. ListNodeinsert(phead, phead, x);
  52.  
  54. }
  55.  
  56. void ListNodepushfront(LNode* phead, DLdatatype x)
  57. {
  58. assert(phead);
  59.  
  60. /*LNode* newnode = Buynewnode(x);
  62. LNode* first = phead->next;
  64. phead->next = newnode;
  65. newnode->prev = phead;
  66. newnode->next = first;
  67. first->prev = newnode;*/
  68.  
  69. ListNodeinsert(phead->next, phead, x);
  70. }
  71.  
  72. bool ListNodeempty(LNode* phead)
  73. {
  74. assert(phead);
  75.  
  76. return phead->next == phead;
  77. }
  78.  
  79. void ListNodepopback(LNode* phead)
  80. {
  81. assert(phead);
  82. //assert(ListNodeempty(phead));
  83.  
  84. if (phead->next == phead)
  85. {
  86. perror("ListNodepopback");
  87. exit(-1);
  88. }
  89.  
  90. /*LNode* tail = phead->prev;
  91. LNode* prev = tail->prev;
  93. prev->next = phead;
  94. phead->prev = prev;
  95. free(tail);
  96. tail = NULL;*/
  97.  
  98. ListNodeerase(phead->prev, phead);
  99. }
  100.  
  101. void ListNodepopfront(LNode* phead)
  102. {
  103. assert(phead);
  104. //assert(ListNodeempty(phead));
  105. if (phead->next == phead)
  106. {
  107. perror("ListNodepopfront");
  108. return;
  109. }
  110.  
  111. /*LNode* first = phead->next;
  112. LNode* second = first->next;
  113. phead->next = second;
  114. second->prev = phead;
  116. free(first);
  117. first = NULL;*/
  118.  
  119. ListNodeerase(phead->next, phead);
  120. }
  121.  
  122. LNode* ListNodefind(LNode* phead,DLdatatype x)
  123. {
  124. assert(phead);
  125.  
  126. LNode* cur = phead->next;
  127. while (cur != phead)
  128. {
  129. if (cur->data == x)
  130. {
  131. return cur;
  132. }
  133.  
  134. cur = cur->next;
  135.  
  136. }
  137.  
  138. return NULL;
  139. }
  140.  
  141. void ListNodeinsert(LNode* pos, LNode* phead, DLdatatype x)
  142. {
  143. assert(phead);
  144. assert(pos);
  145.  
  146. LNode* newnode = Buynewnode(x);
  147. LNode* prev = pos->prev;
  148.  
  149. prev->next = newnode;
  150. newnode->prev = prev;
  151. newnode->next = pos;
  152. pos->prev = newnode;
  153. }
  154.  
  155. void ListNodeerase(LNode* pos, LNode* phead)
  156. {
  157. assert(phead);
  158. assert(pos);
  159.  
  160. if (phead->next == phead)
  161. {
  162. perror("ListNodeerase");
  163. exit(-1);
  164. }
  165. LNode* prev = pos->prev;
  166. LNode* next = pos->next;
  167.  
  168. prev->next = next;
  169. next->prev = prev;
  170.  
  171. free(pos);
  172. pos = NULL;
  173. }
  174.  
  175. void ListNodedestroy(LNode* phead)
  176. {
  177. assert(phead);
  178.  
  179. LNode* cur = phead->next;
  180. while (cur != phead)
  181. {
  182. LNode* next = cur->next;
  183. free(cur);
  184. cur = next;
  185. }
  186.  
  187. free(phead);
  188. phead = NULL;
  189.  
  190. }

test.c

至于test.c 就不贴出来了，这里面主要是一些测试接口的代码，没必要贴出来。

😽本篇文章到此就结束了，若有错误或是建议，欢迎小伙伴们指出；😻

😍请多多支持博主哦~🥰

🤩谢谢你的阅读~😃

 

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