• [C语言数据结构]双向循环链表

    目录

    💊1.双向循环链表：

    💊1.1何为双向循环链表

    💊1.2双向循环链表的实现

    💊1.2.1结构体的创建

    💊1.2.2双向循环链表的初始化

    💊1.2.3双向链表的尾插

    void  LTPushBack(LTNode* phead, LTDataType x);

    💊1.2.4双向链表的尾部删除

    💊1.2.5双向链表的头插

    💊1.2.6双向链表的数据的打印

    💊1.2.7双向链表的头部删除数据

    💊1.2.8双向链表寻找数据

    💊1.2.9在双向链表的任意位置插入数据

    💊1.2.10在双向链表的任意位置删除数据

    引:上次我们学习了单链表的实现，相对于双向循环链表来说，单链表的各中操作，比如说增删查改等都显得非常麻烦。所以接下来来学习一下双向循环链表吧！

    💊1.双向循环链表：

    💊1.1何为双向循环链表

     如上所示：每个节点都有包含有两个指针域和一个数据域；
    两个指针域一个存储前一个节点的地址，另一个存储下一个节点的地址；

    这种结构虽然看起来比单链表复杂一些，但是可以简化一系列后来的增删查改的操作；

    💊1.2双向循环链表的实现

    💊1.2.1结构体的创建

    这个结构体的创建和单链表的结构体的创建是大同小异，我们需要两个指针域，一个数据域；

    代码：

    1. typedef int LTDataType;
    2. typedef struct ListNode
    3. {
    4. 	struct ListNode* next;
    5. 	struct ListNode* prev;
    6. 	LTDataType data;
    7. }LTNode;

    💊1.2.2双向循环链表的初始化

    LTNode* InitList(LTNode* Phead);

    这个函数实现的双向循环链表的初始化功能，函数参数的话这边选择了一级指针和单链表的初始化函数不同，单链表所使用的是二级指针；而且初始化函数内部也有所不同；

    代码：

    1. //申请节点函数
    2. LTNode* BuyListNode(LTDataType x)
    3. {
    4. 	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    5. 	if (node == NULL)
    6. 	{
    7. 		perror("malloc fail");
    8. 		exit(-1);
    9. 	}
    10. 	node->data = x;
    11. 	node->next = node->prev = NULL;
    12. 	return node;
    13. }
    14.  
    15. //初始化双向链表
    16. LTNode* InitList(LTNode* phead)
    17. {
    18. 	phead = BuyListNode(-1);
    19. 	phead->next = phead;
    20. 	phead->prev = phead;
    21. 	return phead;
    22. }

    💊1.2.3双向链表的尾插

    void  LTPushBack(LTNode* phead, LTDataType x);

    对于双向循环链表来说，它的尾插非常简单，因为它不需要去遍历链表来找到链表的尾部节点；

    代码：

    1. //双向链表的尾插
    2. void  LTPushBack(LTNode* phead, LTDataType x)
    3. {
    4. 	assert(phead);
    5.  
    6. 	LTNode* newnode = BuyListNode(x);
    7. 	LTNode* tail = phead->prev;
    8.  
    9. 	tail->next = newnode;
    10. 	newnode->prev = tail;
    11. 	phead->prev = newnode;
    12. 	newnode->next = phead;
    13. }

    💊1.2.4双向链表的尾部删除

    双向链表的尾部删除的和尾部插入同样简单，因为它不需要遍历链表，只需要进行相应的链接操作即可。

    代码：

    1. //双向链表的尾部删除
    2. void LTPopBack(LTNode* phead)
    3. {
    4. 	assert(phead);
    5. 	assert(phead->next != phead);
    6.  
    7. 	LTNode* tail = phead->prev;
    8. 	LTNode* tailprev = tail->prev;
    9.  
    10. 	tailprev->next = phead;
    11. 	phead->prev = tailprev;
    12. 	free(tail); 
    13. }

    💊1.2.5双向链表的头插

    链表的头插相对于单链表来说复杂程度不相上下，但也不难，因为有哨兵位节点的存在，在连接节点的时候还是相对方便的；

    代码：

    1. //双向链表的头插
    2. void LTPushFront(LTNode* phead, LTDataType x)
    3. {
    4. 	assert(phead);
    5.  
    6. 	LTNode* newnode = BuyListNode(x);
    7. 	newnode->next = phead->next;
    8. 	phead->next->prev = newnode;
    9.  
    10. 	phead->next = newnode;
    11. 	newnode->prev = phead;
    12. }

    💊1.2.6双向链表的数据的打印

    函数的实现非常简单，简单的遍历链表即可，唯一需要注意到的点就是我们什么时候停下来；

    代码：

    1. //双向链表的打印
    2. void LTPrint(LTNode* phead)
    3. {
    4. 	assert(phead);
    5. 	LTNode* cur = phead->next;
    6. 	while (cur != phead)
    7. 	{
    8. 		printf("%d ", cur->data);
    9. 		cur = cur->next;
    10. 	}
    11. 	printf("\n");
    12. }

    💊1.2.7双向链表的头部删除数据

    双向链表头部删除数据很简单，只需要将phead->next删除之后再将phead->next->next和phead链接起来即可；

    代码：

    1. void LTPopFront(LTNode* phead)
    2. {
    3. 	assert(phead);
    4. 	assert(phead->next != NULL);
    5. 	LTNode* first = phead->next;
    6. 	LTNode* second = first->next;
    7.  
    8. 	free(first);
    9. 	phead->next = second;
    10. 	second->prev = phead;
    11. }

    💊1.2.8双向链表寻找数据

    方法和单链表是类似的，只是判断停止的条件不同；

    代码：

    1. //双向链表中寻找数据
    2. LTNode* LTFind(LTNode* phead, LTDataType x)
    3. {
    4. 	assert(phead);
    5. 	LTNode* cur = phead->next;
    6. 	while (cur != phead)
    7. 	{
    8. 		if (cur->data == x)
    9. 		{
    10. 			return cur;
    11. 		}
    12. 		cur = cur->next;
    13. 	}
    14. 	return NULL;
    15. }

    💊1.2.9在双向链表的任意位置插入数据

    这里我们实现的是在这个位置前进行插入数据，逻辑非常简单。

    分两个步骤：①申请空间；        ②链接节点；

    代码：

    1. //在双向链表的任意位置插入数据
    2. void LTInsert(LTNode* pos, LTDataType x)
    3. {
    4. 	assert(pos);
    5. 	LTNode* newnode = BuyListNode(x);
    6. 	LTNode* pre = pos->prev;
    7.  
    8. 	pre->next = newnode;
    9. 	newnode->prev = pre;
    10. 	newnode->next = pos;
    11. 	pos->prev = newnode;
    12. }

    对此函数我们可以实现复用，重新构建头插和尾插：

    1. //双向链表的头插
    2. void LTPushFront(LTNode* phead, LTDataType x)
    3. {
    4. 	assert(phead);
    5. 	LTInsert(phead->next, x);
    6. }
    7. //双向链表的尾插
    8. void  LTPushBack(LTNode* phead, LTDataType x)
    9. {
    10. 	assert(phead);
    11. 	LTInsert(phead, x);
    12. }

    💊1.2.10在双向链表的任意位置删除数据

    这个函数我们实现的就是删除传入地址的节点，大的步骤也是分两个，先记录这个节点的前一个节点和后一个节点，然后free掉这个节点后，再链接；

    代码：

    1. //在双向链表的任意位置删除数据
    2. void LTErase(LTNode* pos)
    3. {
    4. 	assert(pos);
    5. 	LTNode* pre = pos->prev;
    6. 	LTNode* next = pos->next;
    7. 	free(pos);
    8. 	pre->next = next;
    9. 	next->prev = pre;
    10. }

    对此函数进行复用，改进头删和尾部删除函数：

    代码：

    1. //双向连边头部删除数据
    2. void LTPopFront(LTNode* phead)
    3. {
    4. 	assert(phead);
    5. 	LTErase(phead->next);
    6. }
    7. //双向链表的尾部删除
    8. void LTPopBack(LTNode* phead)
    9. {
    10. 	assert(phead);
    11. 	assert(phead->next != phead);
    12. 	LTErase(phead->prev);
    13. }

    代码汇总：

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5.  
    6. typedef int LTDataType;
    7. typedef struct ListNode
    8. {
    9. 	struct ListNode* next;
    10. 	struct ListNode* prev;
    11. 	LTDataType data;
    12. }LTNode;
    13.  
    14. //初始化双向链表
    15. LTNode* InitList();
    16.  
    17. //获取新的节点
    18. LTNode* BuyListNode(LTDataType x);
    19.  
    20. //双向链表的尾插
    21. void  LTPushBack(LTNode* phead, LTDataType x);
    22.  
    23. //双向链表的尾部删除
    24. void LTPopBack(LTNode* phead);
    25.  
    26.  
    27. //双向链表的头插
    28. void LTPushFront(LTNode* phead, LTDataType x);
    29.  
    30. //双向链表的打印
    31. void LTPrint(LTNode* phead);
    32.  
    33. //双向连边头部删除数据
    34. void LTPopFront(LTNode* phead);
    35.  
    36. //双向链表中寻找数据
    37. LTNode* LTFind(LTNode* phead, LTDataType x);
    38.  
    39. //在双向链表的任意位置插入和删除数据
    40. void LTInsert(LTNode* pos, LTDataType x);
    41. void LTErase(LTNode* pos);
    42.  
    43. //双向链表的判空
    44. bool LTEmpty(LTNode* phead);
    45.  
    46. //双向链表大小的计算
    47. size_t LTSize(LTNode* phead);
    48.  
    49. //双向链表的销毁
    50. void LTDestroy(LTNode* phead);
    51.  
    52. #define _CRT_SECURE_NO_WARNINGS 1
    53. #include"List.h"
    54.  
    55. LTNode* BuyListNode(LTDataType x)
    56. {
    57. 	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    58. 	if (node == NULL)
    59. 	{
    60. 		perror("malloc fail");
    61. 		exit(-1);
    62. 	}
    63. 	node->data = x;
    64. 	node->next = node->prev = NULL;
    65. 	return node;
    66. }
    67.  
    68. //初始化双向链表
    69. LTNode* InitList()
    70. {
    71. 	LTNode* phead = BuyListNode(-1);
    72. 	phead->next = phead;
    73. 	phead->prev = phead;
    74. 	return phead;
    75. }
    76.  
    77. //双向链表的尾插
    78. void  LTPushBack(LTNode* phead, LTDataType x)
    79. {
    80. 	assert(phead);
    81.  
    82. 	//LTNode* newnode = BuyListNode(x);
    83. 	//LTNode* tail = phead->prev;
    84.  
    85. 	//tail->next = newnode;
    86. 	//newnode->prev = tail;
    87. 	//phead->prev = newnode;
    88. 	//newnode->next = phead;
    89. 	LTInsert(phead, x);
    90. }
    91.  
    92. //双向链表的尾部删除
    93. void LTPopBack(LTNode* phead)
    94. {
    95. 	assert(phead);
    96. 	assert(phead->next != phead);
    97.  
    98. 	//LTNode* tail = phead->prev;
    99. 	//LTNode* tailprev = tail->prev;
    100.  
    101. 	//tailprev->next = phead;
    102. 	//phead->prev = tailprev;
    103. 	//free(tail); 
    104. 	LTErase(phead->prev);
    105. }
    106.  
    107. //双向链表的头插
    108. void LTPushFront(LTNode* phead, LTDataType x)
    109. {
    110. 	assert(phead);
    111.  
    112. 	//LTNode* newnode = BuyListNode(x);
    113. 	//newnode->next = phead->next;
    114. 	//phead->next->prev = newnode;
    115.  
    116. 	//phead->next = newnode;
    117. 	//newnode->prev = phead;
    118. 	LTInsert(phead->next, x);
    119. }
    120.  
    121. //双向链表的打印
    122. void LTPrint(LTNode* phead)
    123. {
    124. 	assert(phead);
    125. 	LTNode* cur = phead->next;
    126. 	while (cur != phead)
    127. 	{
    128. 		printf("%d ", cur->data);
    129. 		cur = cur->next;
    130. 	}
    131. 	printf("\n");
    132. }
    133.  
    134. //双向连边头部删除数据
    135. void LTPopFront(LTNode* phead)
    136. {
    137. 	assert(phead);
    138. 	//assert(phead->next != NULL);
    139. 	//LTNode* first = phead->next;
    140. 	//LTNode* second = first->next;
    141.  
    142. 	//free(first);
    143. 	//phead->next = second;
    144. 	//second->prev = phead;
    145. 	LTErase(phead->next);
    146. }
    147.  
    148. //双向链表中寻找数据
    149. LTNode* LTFind(LTNode* phead, LTDataType x)
    150. {
    151. 	assert(phead);
    152. 	LTNode* cur = phead->next;
    153. 	while (cur != phead)
    154. 	{
    155. 		if (cur->data == x)
    156. 		{
    157. 			return cur;
    158. 		}
    159. 		cur = cur->next;
    160. 	}
    161. 	return NULL;
    162. }
    163.  
    164. //在双向链表的任意位置插入和删除数据
    165. void LTInsert(LTNode* pos, LTDataType x)
    166. {
    167. 	assert(pos);
    168. 	LTNode* newnode = BuyListNode(x);
    169. 	LTNode* pre = pos->prev;
    170.  
    171. 	pre->next = newnode;
    172. 	newnode->prev = pre;
    173. 	newnode->next = pos;
    174. 	pos->prev = newnode;
    175. }
    176.  
    177. void LTErase(LTNode* pos)
    178. {
    179. 	assert(pos);
    180. 	LTNode* pre = pos->prev;
    181. 	LTNode* next = pos->next;
    182. 	free(pos);
    183. 	pre->next = next;
    184. 	next->prev = pre;
    185. }
    186.  
    187. //双向链表的判空
    188. bool LTEmpty(LTNode* phead)
    189. {
    190. 	assert(phead);
    191. 	return phead->next != phead;
    192. }
    193.  
    194. //双向链表大小的计算
    195. size_t LTSize(LTNode* phead)
    196. {
    197. 	assert(phead);
    198. 	size_t x = 0;
    199. 	LTNode* cur = phead->next;
    200. 	while (cur != phead)
    201. 	{
    202. 		x++;
    203. 		cur = cur->next;
    204. 	}
    205. 	return x;
    206. }
    207.  
    208. //双向链表的销毁
    209. void LTDestroy(LTNode* phead)
    210. {
    211. 	assert(phead);
    212.  
    213. 	LTNode* cur = phead->next;
    214. 	while (cur != phead)
    215. 	{
    216. 		LTNode* next = cur->next;
    217. 		free(cur);
    218. 		cur = next;
    219. 	}
    220. 	free(phead);
    221. }
    222.  
    223. #define _CRT_SECURE_NO_WARNINGS 1
    224. #include"List.h"
    225.  
    226.  
    227. int main()
    228. {
    229. 	LTNode* phead = InitList();
    230. 	LTPushBack(phead, 1);
    231. 	LTPushBack(phead, 2);
    232. 	LTPushBack(phead, 3);
    233. 	LTPushBack(phead, 4);
    234. 	LTPushBack(phead, 5);
    235. 	LTPrint(phead);
    236. 	LTPrint(phead);
    237. 	LTNode* x = LTFind(phead, 3);
    238. 	if (x)
    239. 	{
    240. 		x->data = 100;
    241. 		LTPrint(phead);
    242. 	}
    243. 	LTPopBack(phead);
    244. 	LTPrint(phead);
    245. 	printf("%d\n", LTSize(phead));
    246. 	LTDestroy(phead);
    247. 	return 0;
    248. }

    以上就是双向循环链表表的实现和各个函数需要注意的细节，如果有错误可以在评论区指正！ 

     

  • 相关阅读:
    glibc: dup/dup2/dup3/F_DUPFD
    3.1 Android eBPF代码仓解读
    《Python编程无师自通》读书笔记
    EM@平面直线方程和直线位置关系判定条件
    Kotlin（十一）Kotlin中的Object关键字
    在内核调试时输出调试信息
    Win10删除文件需要TrustedInstaller权限的解决方法
    JavaScript Web APIs第六天笔记
    网络编程-套接字相关基础知识
    C++中的CopyElision
  • 原文地址：https://blog.csdn.net/weixin_61766635/article/details/127716053