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

简介: 【数据结构与算法】双向带头循环链表(附源码)

一.前言

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

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

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

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. 
19. 
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. 
13. 
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. 
37. 
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. 
53. 
54. }
55. 
56. void ListNodepushfront(LNode* phead, DLdatatype x)
57. {
58.   assert(phead);
59. 
60.   /*LNode* newnode = Buynewnode(x);
61. 
62.   LNode* first = phead->next;
63. 
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;
92. 
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;
115. 
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 就不贴出来了,这里面主要是一些测试接口的代码,没必要贴出来。


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

😍请多多支持博主哦~🥰

🤩谢谢你的阅读~😃


目录
相关文章
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
191 9
|
1月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法,并分析时间复杂度,理解链表特点。实验内容包括循环链表应用(约瑟夫回环问题)、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践,加深对链表数据结构的理解和应用能力。
55 4
|
5天前
|
机器学习/深度学习 前端开发 算法
婚恋交友系统平台 相亲交友平台系统 婚恋交友系统APP 婚恋系统源码 婚恋交友平台开发流程 婚恋交友系统架构设计 婚恋交友系统前端/后端开发 婚恋交友系统匹配推荐算法优化
婚恋交友系统平台通过线上互动帮助单身男女找到合适伴侣,提供用户注册、个人资料填写、匹配推荐、实时聊天、社区互动等功能。开发流程包括需求分析、技术选型、系统架构设计、功能实现、测试优化和上线运维。匹配推荐算法优化是核心,通过用户行为数据分析和机器学习提高匹配准确性。
28 3
|
24天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
45 5
|
1月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
81 16
|
1月前
|
搜索推荐 算法 C语言
【排序算法】八大排序(上)(c语言实现)(附源码)
本文介绍了四种常见的排序算法:冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据,详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序,选择排序通过选择最小元素进行交换,插入排序通过逐步插入元素到已排序部分,而希尔排序则是插入排序的改进版,通过预排序使数据更接近有序,从而提高效率。文章最后总结了这四种算法的空间和时间复杂度,以及它们的稳定性。
98 8
|
1月前
|
搜索推荐 算法 C语言
【排序算法】八大排序(下)(c语言实现)(附源码)
本文继续学习并实现了八大排序算法中的后四种:堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现,并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序,快速排序通过递归和多种划分方法实现高效排序,归并排序通过分治法将问题分解后再合并,计数排序则通过统计每个元素的出现次数实现非比较排序。最后,文章还对比了这些排序算法在处理一百万个整形数据时的运行时间,帮助读者了解不同算法的优劣。
111 7
|
1月前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
132 8
|
1月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
48 0
|
1月前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
61 0