【数据结构 · 初阶】- 带头双向循环链表

目录

1.尾插

2.初始化

3.尾删、头插、头删

4.查找，返回 pos 指针

5.pos 前插入

优化头插，直接复用

优化尾插，直接复用

6.pos 位删除

头删尾删简化

7.销毁

整体代码

List.h

List.c

Test.c

循环：1.尾 next 指向哨兵位的头。2.哨兵位的头的 prev 指向尾

基本结构：

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

1.尾插

  1. void LTPushBack(LTNode* phead, LTDataType x)
  2. {
  3. 	assert(phead);
  4. 	LTNode* newnode = BuyListNode(x);
  5. 	LTNode* tail = phead->prev;
  6. 	//phead             tail  newnode
  7. 	tail->next = newnode;
  8. 	newnode->prev = tail;
  9. 	phead->prev = newnode;
  10. 	newnode->next = phead;
  11. }

为什么要 assert ？
这里的 phead 是结构体指针，存放的是 plist 的值。plist 指向 malloc 的新节点。
malloc 的新节点的地址一定不为空。如果为空，就是传错了，所以要 assert

为什么不用二级指针？
改变的都是结构体的变量，用结构体指针足矣。这也是哨兵位的优势所在。

无头单向不循环（单链表）里面，要遍例来找尾；还要判断链表是否为空，如果为空，先赋值
这里就不用刻意找尾；且可以兼容空的情况，方便很多。下面是单链表的尾插

  1. void SLTPushBack(SLTNode** pphead, SLTDataType x)
  2. {
  3. 	assert(pphead);
  4. 	SLTNode* newnode = BuySLTNode(x);
  5.  
  6. 	if (*pphead == NULL)
  7. 	{
  8. 		*pphead = newnode;
  9. 	}
  10. 	else
  11. 	{
  12. 		// 找尾
  13. 		SLTNode* tail = *pphead;
  14. 		while (tail->next != NULL)
  15. 		{
  16. 			tail = tail->next;
  17. 		}
  18. 		tail->next = newnode;
  19. 	}
  20. }

2.初始化

目标：malloc 一个哨兵位的头节点，让 plist 指向哨兵位头节点
现象：要将头节点的地址传给 plist ，会改变 plist 的值
结论：要用二级指针，不能用一级指针

  1. LTNode* plist = NULL;
  2. LTInit(plist);
  3.  
  4. void LTInit(LTNode** pphead);

后面的插入，删除都是改变结构体成员，用一级指针，只有这里用二级指针。
还有更好的方式：OJ 题中普遍用

List.c

  1. LTNode* BuyListNode(LTDataType x)
  2. {
  3. 	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
  4. 	if (node == NULL)
  5. 	{
  6. 		perror("malloc fail");
  7. 		return NULL;
  8. 	}
  9. 	node->data = x;
  10. 	node->next = NULL;
  11. 	node->prev = NULL;
  12. 	return node;
  13. }
  14.  
  15. LTNode* LTInit()
  16. {
  17. 	LTNode* phead = BuyListNode(-1);
  18. 	phead->next = phead;
  19. 	phead->prev = phead;
  20.  
  21. 	return phead;
  22. }
  23.  
  24. void LTPrint(LTNode* phead)
  25. {
  26. 	assert(phead);
  27. 	LTNode* cur = phead->next;
  28. 	printf("<=head=>");
  29. 	while (cur != phead)
  30. 	{
  31. 		printf("%d<=>", cur->data);
  32. 		cur = cur->next;
  33. 	}
  34. 	printf("\n");
  35. }
  36.  
  37. void LTPushBack(LTNode* phead, LTDataType x)
  38. {
  39. 	assert(phead);
  40. 	LTNode* newnode = BuyListNode(x);
  41. 	LTNode* tail = phead->prev;
  42. 	//phead             tail  newnode
  43. 	tail->next = newnode;
  44. 	newnode->prev = tail;
  45. 	phead->prev = newnode;
  46. 	newnode->next = phead;
  47. }

Test.c

  1. void ListTest1()
  2. {
  3. 	LTNode* plist = LTInit();
  4. 	LTPushBack(plist, 1);
  5. 	LTPushBack(plist, 2);
  6. 	LTPushBack(plist, 3);
  7. 	LTPushBack(plist, 4);
  8. 	LTPrint(plist);
  9. }

3.尾删、头插、头删

空链表不能删（只有哨兵位的头节点），所以要判断链表是否为空

  1. bool LTEmpty(LTNode* phead)
  2. {
  3. 	assert(phead);
  4. 	/*
  5. 	if (phead->next == phead)
  6. 	{
  7. 		return true;
  8. 	}
  9. 	else
  10. 	{
  11. 		return false;
  12. 	}
  13. 	*/
  14. 	return phead->next == phead;
  15. }

尾删

  1. void LTPopBack(LTNode* phead)
  2. {
  3. 	assert(phead);
  4. 	assert(!LTEmpty(phead));
  5. 	LTNode* tail = phead->prev;
  6. 	LTNode* tailPrev = tail->prev;
  7.  
  8. 	tailPrev->next = phead;
  9. 	phead->prev = tailPrev;
  10. 	free(tail);
  11. 	tail = NULL;
  12. }

头插

（1）2个指针的错误写法

  1. void LTPushFront(LTNode* phead, LTDataType x)
  2. {
  3. 	assert(phead);
  4. 	LTNode* newnode = BuyListNode(x);
  5. 	phead->next = newnode;
  6.     newnode->prev = phead;
  7.     ......
  8. }

如果先搞这两步，就不能轻易找到原来的第一个了

（2）2个指针的正确写法

一定先处理离的远的那一边

  1. void LTPushFront(LTNode* phead, LTDataType x)
  2. {
  3. 	assert(phead);
  4. 	LTNode* newnode = BuyListNode(x);
  5.     phead->next->prev = newnode;
  6.     newnode->next = phead->next;
  7. 	phead->next = newnode;
  8.     newnode->prev = phead;
  9. }

（3）3个指针，顺序随便，效率更高

  1. void LTPushFront(LTNode* phead, LTDataType x)
  2. {
  3. 	assert(phead);
  4. 	LTNode* newnode = BuyListNode(x);
  5. 	LTNode* first = phead->next; // 第三个指针
  6. 	first->prev = newnode;
  7. 	newnode->next = first;
  8. 	phead->next = newnode;
  9. 	newnode->prev = phead
  10. }

头删

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

4.查找，返回 pos 指针

  1. LTNode* LTFind(LTNode* phead, LTDataType x); // List.h
  2.  
  3. LTNode* LTFind(LTNode* phead, LTDataType x) // List.c
  4. {
  5. 	assert(phead);
  6. 	LTNode* cur = phead->next;
  7. 	while (cur != phead)
  8. 	{
  9. 		if (cur->data == x)
  10. 		{
  11. 			return cur;
  12. 		}
  13. 		cur = cur->next;
  14. 	}
  15. 	return NULL;
  16. }
  17.  
  18. void ListTest2() // Test.c
  19. {
  20. 	LTNode* plist = LTInit();
  21.     ......
  22. 	LTNode* pos = LTFind(plist, 2);
  23. }

5.pos 前插入

要配合查找使用
单链表要遍例找前一个，现在不需要这么麻烦

要用2个指针，先动离的远的，即 pos->prev 和 newnode 的链接
为高效，我们用3个指针

  1. void LTInsert(LTNode* pos, LTDataType x)
  2. {
  3. 	assert(pos);
  4. 	LTNode* newnode = BuyListNode(x);
  5. 	LTNode* prev = pos->prev; // 第3个指针
  6. 	prev->next = newnode;
  7. 	newnode->prev = prev;
  8. 	newnode->next = pos;
  9. 	pos->prev = newnode;
  10. }

优化头插，直接复用

  1. void LTPushFront(LTNode* phead, LTDataType x)
  2. {
  3. 	assert(phead);
  4. 	LTInsert(phead->next, x);
  5. }

优化尾插，直接复用

  1. void LTPushBack(LTNode* phead, LTDataType x)
  2. {
  3. 	assert(phead);
  4. 	LTInsert(phead, x);
  5. }

 遍例是从 LTNode* cur = phead->next ；开始。从逻辑上就是尾插

6.pos 位删除

配合查找使用

  1. void LTErase(LTNode* pos)
  2. {
  3. 	assert(pos);
  4. 	LTNode* p = pos->prev;
  5. 	LTNode* n = pos->next;
  6. 	p->next = n;
  7. 	n->prev = p;
  8. 	free(pos);
  9. 	//pos = NULL;
  10. }

pos置空没用，形参改变不影响实参。
为保持接口风格一致，没有必要用二级指针，通常由使用的人在外面置空

里面变如果改变外面的话，一定有 解引用 操作

  1. void ListTest2()
  2. {
  3. 	LTNode* plist = LTInit();
  4. 	......
  5.     LTNode* pos = LTFind(plist, 2);
  6. 	if (pos)
  7. 	{
  8. 		LTErase(pos);
  9. 		pos = NULL;
  10. 	}
  11. 	LTPrint(plist);
  12. }

LTErase 肯定不能删哨兵位的头节点
但 C语言中不好检查，所以我们暂且不做处理。删哨兵程序会挂
C++的结构好检查

头删尾删简化

  1. void LTPopBack(LTNode* phead)
  2. {
  3. 	assert(phead);
  4. 	LTErase(phead->prev);
  5. }
  6.  
  7. void LTPopFront(LTNode* phead)
  8. {
  9. 	assert(phead);
  10. 	LTErase(phead->next);
  11. }

7.销毁

  1. void LTDestroy(LTNode* phead)
  2. {
  3. 	assert(phead);
  4. 	LTNode* cur = phead->next;
  5. 	LTNode* next = cur->next;
  6. 	while (cur != phead)
  7. 	{
  8. 		free(cur);
  9. 		cur = next;
  10. 		next = next->next;
  11. 	}
  12. 	free(phead);
  13. 	//phead = NULL;
  14. }
  15.  
  16. void ListTest2()
  17. {
  18. 	LTNode* plist = LTInit();
  19.     ......
  20. 	LTDestroy(plist);
  21. 	plist = NULL;
  22. }

整体代码

List.h

  1. #pragma once
  2. #include 
  3. #include 
  4. #include 
  5. #include 
  6.  
  7. typedef int LTDataType;
  8.  
  9. typedef struct ListNode
  10. {
  11. 	struct ListNode* prev;
  12. 	struct ListNode* next;
  13. 	LTDataType data;
  14.  
  15. }LTNode;
  16.  
  17. LTNode* LTInit();
  18.  
  19. void LTPrint(LTNode* phead);
  20.  
  21. bool LTEmpty(LTNode* phead); // 判断链表是否为空
  22.  
  23. void LTPushBack(LTNode* phead, LTDataType x);
  24. void LTPopBack(LTNode* phead);
  25. void LTPushFront(LTNode* phead, LTDataType x);
  26. void LTPopFront(LTNode* phead);
  27.  
  28. LTNode* LTFind(LTNode* phead, LTDataType x);
  29.  
  30. void LTInsert(LTNode* pos, LTDataType x); // pos前插入
  31. void LTErase(LTNode* pos); // pos位删除
  32.  
  33. void LTDestroy(LTNode* phead);

List.c

  1. #include "List.h"
  2. LTNode* BuyListNode(LTDataType x)
  3. {
  4. 	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
  5. 	if (node == NULL)
  6. 	{
  7. 		perror("malloc fail");
  8. 		return NULL;
  9. 	}
  10. 	node->data = x;
  11. 	node->next = NULL;
  12. 	node->prev = NULL;
  13. 	return node;
  14. }
  15.  
  16. LTNode* LTInit()
  17. {
  18. 	LTNode* phead = BuyListNode(-1);
  19. 	phead->next = phead;
  20. 	phead->prev = phead;
  21.  
  22. 	return phead;
  23. }
  24.  
  25. void LTPrint(LTNode* phead)
  26. {
  27. 	assert(phead);
  28. 	LTNode* cur = phead->next;
  29. 	printf("<=head=>");
  30. 	while (cur != phead)
  31. 	{
  32. 		printf("%d<=>", cur->data);
  33. 		cur = cur->next;
  34. 	}
  35. 	printf("\n");
  36. }
  37.  
  38. bool LTEmpty(LTNode* phead)
  39. {
  40. 	assert(phead);
  41. 	/*
  42. 	if (phead->next == phead)
  43. 	{
  44. 		return true;
  45. 	}
  46. 	else
  47. 	{
  48. 		return false;
  49. 	}
  50. 	*/
  51. 	return phead->next == phead;
  52. }
  53.  
  54. void LTPushBack(LTNode* phead, LTDataType x)
  55. {
  56. 	assert(phead);
  57. 	/*
  58. 	LTNode* newnode = BuyListNode(x);
  59. 	LTNode* tail = phead->prev;
  60. 	//phead             tail  newnode
  61. 	tail->next = newnode;
  62. 	newnode->prev = tail;
  63. 	phead->prev = newnode;
  64. 	newnode->next = phead;
  65. 	*/
  66. 	LTInsert(phead, x);
  67. }
  68.  
  69. void LTPopBack(LTNode* phead)
  70. {
  71. 	assert(phead);
  72. 	/*
  73. 	assert(!LTEmpty(phead));
  74. 	LTNode* tail = phead->prev;
  75. 	LTNode* tailPrev = tail->prev;
  77. 	tailPrev->next = phead;
  78. 	phead->prev = tailPrev;
  79. 	free(tail);
  80. 	tail = NULL;
  81. 	*/
  82. 	LTErase(phead->prev);
  83. }
  84.  
  85. void LTPushFront(LTNode* phead, LTDataType x)
  86. {
  87. 	assert(phead);
  88. 	/*
  89. 	LTNode* newnode = BuyListNode(x);
  90. 	LTNode* first = phead->next;
  91. 	first->prev = newnode;
  92. 	newnode->next = first;
  93. 	phead->next = newnode;
  94. 	newnode->prev = phead
  95. 	*/
  96. 	LTInsert(phead->next, x);
  97. }
  98.  
  99. //void LTPushFront(LTNode* phead, LTDataType x)
  100. //{
  101. //	assert(phead);
  102. //	LTNode* newnode = BuyListNode(x);
  103. //  // 先
  104. //	phead->next->prev = newnode;
  105. //	newnode->next = phead->next;
  106. //  // 后
  107. //	phead->next = newnode;
  108. //	newnode->prev = phead;
  109. //}
  110.  
  111. void LTPopFront(LTNode* phead)
  112. {
  113. 	assert(phead);
  114. 	/*
  115. 	assert(!LTEmpty(phead));
  116. 	LTNode* first = phead->next->next;
  117. 	LTNode* del = phead->next;
  118. 	phead->next = first;
  119. 	first->prev = phead;
  120. 	free(del);
  121. 	del = NULL;
  122. 	*/
  123. 	LTErase(phead->next);
  124. }
  125.  
  126. LTNode* LTFind(LTNode* phead, LTDataType x)
  127. {
  128. 	assert(phead);
  129. 	LTNode* cur = phead->next;
  130. 	while (cur != phead)
  131. 	{
  132. 		if (cur->data == x)
  133. 		{
  134. 			return cur;
  135. 		}
  136. 		cur = cur->next;
  137. 	}
  138. 	return NULL;
  139. }
  140.  
  141. void LTInsert(LTNode* pos, LTDataType x)
  142. {
  143. 	assert(pos);
  144. 	LTNode* newnode = BuyListNode(x);
  145. 	LTNode* prev = pos->prev;
  146. 	prev->next = newnode;
  147. 	newnode->prev = prev;
  148. 	newnode->next = pos;
  149. 	pos->prev = newnode;
  150. }
  151.  
  152. void LTErase(LTNode* pos)
  153. {
  154. 	assert(pos);
  155. 	LTNode* p = pos->prev;
  156. 	LTNode* n = pos->next;
  157. 	p->next = n;
  158. 	n->prev = p;
  159. 	free(pos);
  160. 	//pos = NULL;
  161. }
  162.  
  163. void LTDestroy(LTNode* phead)
  164. {
  165. 	assert(phead);
  166. 	LTNode* cur = phead->next;
  167. 	LTNode* next = cur->next;
  168. 	while (cur != phead)
  169. 	{
  170. 		free(cur);
  171. 		cur = next;
  172. 		next = next->next;
  173. 	}
  174. 	free(phead);
  175. 	//phead = NULL;
  176. }

Test.c

  1. #include "List.h"
  2. void ListTest1()
  3. {
  4. 	LTNode* plist = LTInit();
  5. 	LTPushBack(plist, 1);
  6. 	LTPushBack(plist, 2);
  7. 	LTPushBack(plist, 3);
  8. 	LTPushBack(plist, 4);
  9. 	LTPrint(plist);
  10.  
  11. 	LTPopBack(plist);
  12. 	LTPopBack(plist);
  13. 	LTPopBack(plist);
  14. 	LTPopBack(plist);
  15. 	LTPrint(plist);
  16.  
  17. 	LTPushFront(plist, 1);
  18. 	LTPushFront(plist, 2);
  19. 	LTPushFront(plist, 3);
  20. 	LTPushFront(plist, 4);
  21. 	LTPrint(plist);
  22.  
  23. 	LTPopFront(plist);
  24. 	LTPopFront(plist);
  25. 	LTPrint(plist);
  26. }
  27.  
  28. void ListTest2()
  29. {
  30. 	LTNode* plist = LTInit();
  31. 	LTPushBack(plist, 1);
  32. 	LTPushBack(plist, 2);
  33. 	LTPushBack(plist, 3);
  34. 	LTPushBack(plist, 4);
  35. 	LTPrint(plist);
  36.  
  37. 	LTNode* pos = LTFind(plist, 2);
  38. 	LTInsert(pos, 9);
  39. 	LTPrint(plist);
  40.  
  41. 	if (pos)
  42. 	{
  43. 		LTErase(pos);
  44. 		pos = NULL;
  45. 	}
  46. 	LTPrint(plist);
  47.  
  48. 	LTDestroy(plist);
  49. 	plist = NULL;
  50. }
  51.  
  52. int main()
  53. {
  54. 	ListTest2();
  55. 	return 0;
  56. }

本篇的分享就到这里了，感谢观看，如果对你有帮助，别忘了点赞+收藏+关注。
小编会以自己学习过程中遇到的问题为素材，持续为您推送文章

注：本文转载自blog.csdn.net的祁同伟.的文章"https://blog.csdn.net/HDSTQTW/article/details/147255828"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！