devbox
不正经
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【海贼王的数据航海：利用数据结构成为数据海洋的霸主】链表—双向链表

作者：不正经 | 2024-03-07 16:24:25

赞

踩

【海贼王的数据航海：利用数据结构成为数据海洋的霸主】链表—双向链表

目录

往期

1 -> 带头+双向+循环链表(双链表)

1.1 -> 接口声明

1.2 -> 接口实现

1.2.1 -> 双向链表初始化

1.2.2 -> 动态申请一个结点

1.2.3 -> 双向链表销毁

1.2.4 -> 双向链表打印

1.2.5 -> 双向链表判空

1.2.6 -> 双向链表尾插

1.2.7 -> 双向链表尾删

1.2.8 -> 双向链表头插

1.2.9 -> 双向链表头删

1.2.10 -> 双向链表查找

1.2.11 ->  双向链表在pos的前面进行插入

1.2.12 -> 双向链表删除pos位置的节点

2 -> 顺序表和链表的区别

3 -> 完整代码

3.1 -> List.c

3.2 -> List.h

3.3 -> Test.c

往期

链表-单链表

1 -> 带头+双向+循环链表(双链表)

1.1 -> 接口声明

  1. #pragma once
  2.  
  3. #define  _CRT_SECURE_NO_WARNINGS 1
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <assert.h>
  7. #include <stdbool.h>
  8.  
  9. // 带头+双向+循环链表增删查改实现
  10. typedef int LTDataType;
  11.  
  12. typedef struct LTNode
  13. {
  14. 	LTDataType data;
  15. 	struct LTNode* next;
  16. 	struct LTNode* prev;
  17. }LTNode;
  18.  
  19. // 双向链表初始化
  20. LTNode* LTInit();
  22. // 动态申请一个结点
  23. LTNode* BuyLTNode(LTDataType x);
  25. // 双向链表销毁
  26. void LTDestory(LTNode* phead);
  27.  
  28. // 双向链表打印
  29. void LTPrint(LTNode* phead);
  30.  
  31. // 双向链表判空
  32. bool LTEmpty(LTNode* phead);
  33.  
  34. // 双向链表尾插
  35. void LTPushBack(LTNode* phead, LTDataType x);
  36.  
  37. // 双向链表尾删
  38. void LTPopBack(LTNode* phead);
  39.  
  40. // 双向链表头插
  41. void LTPushFront(LTNode* phead, LTDataType x);
  42.  
  43. // 双向链表头删
  44. void LTPopFront(LTNode* phead);
  45.  
  46. // 双向链表查找
  47. LTNode* LTFind(LTNode* phead, LTDataType x);
  49. // 双向链表在pos的前面进行插入
  50. void LTInsert(LTNode* pos, LTDataType x);
  51.  
  52. // 双向链表删除pos位置的节点
  53. void LTErase(LTNode* pos);

1.2 -> 接口实现

1.2.1 -> 双向链表初始化

  1. // 双向链表初始化
  2. LTNode* LTInit()
  3. {
  4. 	LTNode* phead = BuyLTNode(-1);
  5.  
  6. 	phead->next = phead;
  7. 	phead->prev = phead;
  8.  
  9. 	return phead;
  10. }

1.2.2 -> 动态申请一个结点

  1. // 动态申请一个结点
  2. LTNode* BuyLTNode(LTDataType x)
  3. {
  4. 	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  5. 	if (newnode == NULL)
  6. 	{
  7. 		perror("malloc fail");
  8. 		return NULL;
  9. 	}
  10.  
  11. 	newnode->data = x;
  12. 	newnode->next = NULL;
  13. 	newnode->prev = NULL;
  14.  
  15. 	return newnode;
  16. }

1.2.3 -> 双向链表销毁

  1. // 双向链表销毁
  2. void LTDestory(LTNode* phead)
  3. {
  4. 	assert(phead);
  5. 	LTNode* cur = phead->next;
  6. 	while (cur != phead)
  7. 	{
  8. 		LTNode* next = cur->next;
  9. 		free(cur);
  10. 		cur = next;
  11. 	}
  12.  
  13. 	free(phead);
  14. }

1.2.4 -> 双向链表打印

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

1.2.5 -> 双向链表判空

  1. // 双向链表判空
  2. bool LTEmpty(LTNode* phead)
  3. {
  4. 	assert(phead);
  5.  
  6. 	return phead->next == phead;
  7. }

1.2.6 -> 双向链表尾插

  1. // 双向链表尾插
  2. void LTPushBack(LTNode* phead, LTDataType x)
  3. {
  4. 	assert(phead);
  5.  
  6. 	LTNode* tail = phead->prev;
  7. 	LTNode* newnode = BuyLTNode(x);
  8.  
  9. 	tail->next = newnode;
  10. 	newnode->prev = tail;
  11. 	newnode->next = phead;
  12. 	phead->prev = newnode;
  13.  
  14. 	// 复用
  15. 	// LTInsert(phead, x);
  16. }
  1. // 尾插测试
  2. void Test1()
  3. {
  4. 	LTNode* plist = LTInit();
  5.  
  6. 	LTPushBack(plist, 1);
  7. 	LTPushBack(plist, 2);
  8. 	LTPushBack(plist, 3);
  9. 	LTPushBack(plist, 4);
  10. 	LTPushBack(plist, 5);
  11.  
  12. 	LTPrint(plist);
  13.  
  14. 	LTDestory(plist);
  15. 	plist = NULL;
  16. }

 

1.2.7 -> 双向链表尾删

  1. // 双向链表尾删
  2. void LTPopBack(LTNode* phead)
  3. {
  4. 	assert(phead);
  5. 	assert(!LTEmpty(phead));
  6.  
  7. 	LTNode* tail = phead->prev;
  8. 	LTNode* tailPrev = tail->prev;
  9.  
  10. 	free(tail);
  11. 	tailPrev->next = phead;
  12. 	phead->prev = tailPrev;
  13.  
  14. 	// 复用
  15. 	// LTErase(phead->prev);
  16. }
  1. // 尾删测试
  2. void Test2()
  3. {
  4. 	LTNode* plist = LTInit();
  5.  
  6. 	LTPushBack(plist, 1);
  7. 	LTPushBack(plist, 2);
  8. 	LTPushBack(plist, 3);
  9. 	LTPushBack(plist, 4);
  10. 	LTPushBack(plist, 5);
  11.  
  12. 	LTPrint(plist);
  13.  
  14. 	LTPopBack(plist);
  15. 	LTPrint(plist);
  16. 	LTPopBack(plist);
  17. 	LTPrint(plist);
  18. 	LTPopBack(plist);
  19. 	LTPrint(plist);
  20. 	LTPopBack(plist);
  21. 	LTPrint(plist);
  22. 	LTPopBack(plist);
  23. 	LTPrint(plist);
  24.  
  25. 	LTDestory(plist);
  26. 	plist = NULL;
  27. }

1.2.8 -> 双向链表头插

  1. // 双向链表头插
  2. void LTPushFront(LTNode* phead, LTDataType x)
  3. {
  4. 	assert(phead);
  5. 	LTNode* newnode = BuyLTNode(x);
  6.  
  7. 	newnode->next = phead->next;
  8. 	phead->next->prev = newnode;
  9. 	phead->next = newnode;
  10. 	newnode->prev = phead;
  11.  
  12. 	// 复用
  13. 	// LTInsert(phead->next, x);
  14. }
  1. // 头插测试
  2. void Test3()
  3. {
  4. 	LTNode* plist = LTInit();
  5.  
  6. 	LTPushFront(plist, 1);
  7. 	LTPushFront(plist, 2);
  8. 	LTPushFront(plist, 3);
  9. 	LTPushFront(plist, 4);
  10. 	LTPushFront(plist, 5);
  11.  
  12. 	LTPrint(plist);
  13.  
  14. 	LTDestory(plist);
  15. 	plist = NULL;
  16. }

1.2.9 -> 双向链表头删

  1. // 双向链表头删
  2. void LTPopFront(LTNode* phead)
  3. {
  4. 	assert(phead);
  5. 	assert(!LTEmpty(phead));
  6. 	LTNode* first = phead->next;
  7. 	LTNode* second = first->next;
  8.  
  9. 	phead->next = second;
  10. 	second->prev = phead;
  11.  
  12. 	free(first);
  13.  
  14. 	// 复用
  15. 	// LTErase(phead->next);
  16. }
  1. // 头删测试
  2. void Test4()
  3. {
  4. 	LTNode* plist = LTInit();
  5.  
  6. 	LTPushBack(plist, 1);
  7. 	LTPushBack(plist, 2);
  8. 	LTPushBack(plist, 3);
  9. 	LTPushBack(plist, 4);
  10. 	LTPushBack(plist, 5);
  11.  
  12. 	LTPrint(plist);
  13.  
  14. 	LTPopFront(plist);
  15. 	LTPrint(plist);
  16. 	LTPopFront(plist);
  17. 	LTPrint(plist);
  18. 	LTPopFront(plist);
  19. 	LTPrint(plist);
  20. 	LTPopFront(plist);
  21. 	LTPrint(plist);
  22. 	LTPopFront(plist);
  23. 	LTPrint(plist);
  24.  
  25. 	LTDestory(plist);
  26. 	plist = NULL;
  27. }

1.2.10 -> 双向链表查找

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

1.2.11 ->  双向链表在pos的前面进行插入

  1. // 双向链表在pos的前面进行插入
  2. void LTInsert(LTNode* pos, LTDataType x)
  3. {
  4. 	assert(pos);
  5.  
  6. 	LTNode* prev = pos->prev;
  7. 	LTNode* newnode = BuyLTNode(x);
  8.  
  9. 	prev->next = newnode;
  10. 	newnode->prev = prev;
  11. 	newnode->next = pos;
  12. 	pos->prev = newnode;
  13. }
  1. // 查找插入测试
  2. void Test5()
  3. {
  4. 	LTNode* plist = LTInit();
  5.  
  6. 	LTPushBack(plist, 1);
  7. 	LTPushBack(plist, 2);
  8. 	LTPushBack(plist, 3);
  9. 	LTPushBack(plist, 4);
  10. 	LTPushBack(plist, 5);
  11.  
  12. 	LTPrint(plist);
  13.  
  14. 	LTNode* pos = LTFind(plist, 3);
  15. 	if (pos)
  16. 		LTInsert(pos, 99);
  17. 	LTPrint(plist);
  18.  
  19. 	LTDestory(plist);
  20. 	plist = NULL;
  21. }

1.2.12 -> 双向链表删除pos位置的节点

  1. // 双向链表删除pos位置的节点
  2. void LTErase(LTNode* pos)
  3. {
  4. 	assert(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. }

2 -> 顺序表和链表的区别

不同点顺序表链表
存储空间上物理上一定连续逻辑上连续，但物理上不一定连续
随机访问支持O(1)不支持:O(N)
任意位置插入或者删除元素可能需要搬移元素，效率低O(N)只需修改指针指向
插入动态顺序表，空间不够时需要扩容没有容量的概念
应用场景元素高效存储+频繁访问任意位置插入和删除频繁
缓存利用率高低

注：缓存利用率参考存储体系结构以及局部原理性。

3 -> 完整代码

3.1 -> List.c

  1. #include "List.h"
  2.  
  3. // 双向链表初始化
  4. LTNode* LTInit()
  5. {
  6. 	LTNode* phead = BuyLTNode(-1);
  7.  
  8. 	phead->next = phead;
  9. 	phead->prev = phead;
  10.  
  11. 	return phead;
  12. }
  13.  
  14. // 动态申请一个结点
  15. LTNode* BuyLTNode(LTDataType x)
  16. {
  17. 	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  18. 	if (newnode == NULL)
  19. 	{
  20. 		perror("malloc fail");
  21. 		return NULL;
  22. 	}
  23.  
  24. 	newnode->data = x;
  25. 	newnode->next = NULL;
  26. 	newnode->prev = NULL;
  27.  
  28. 	return newnode;
  29. }
  30.  
  31. // 双向链表销毁
  32. void LTDestory(LTNode* phead)
  33. {
  34. 	assert(phead);
  35. 	LTNode* cur = phead->next;
  36. 	while (cur != phead)
  37. 	{
  38. 		LTNode* next = cur->next;
  39. 		free(cur);
  40. 		cur = next;
  41. 	}
  42.  
  43. 	free(phead);
  44. }
  45.  
  46. // 双向链表打印
  47. void LTPrint(LTNode* phead)
  48. {
  49. 	assert(phead);
  50.  
  51. 	printf("guard<==>");
  52. 	LTNode* cur = phead->next;
  53. 	while (cur != phead)
  54. 	{
  55. 		printf("%d<==>", cur->data);
  56. 		cur = cur->next;
  57. 	}
  58. 	printf("\n");
  59. }
  60.  
  61. // 双向链表判空
  62. bool LTEmpty(LTNode* phead)
  63. {
  64. 	assert(phead);
  65.  
  66. 	return phead->next == phead;
  67. }
  68.  
  69. // 双向链表尾插
  70. void LTPushBack(LTNode* phead, LTDataType x)
  71. {
  72. 	assert(phead);
  73.  
  74. 	LTNode* tail = phead->prev;
  75. 	LTNode* newnode = BuyLTNode(x);
  76.  
  77. 	tail->next = newnode;
  78. 	newnode->prev = tail;
  79. 	newnode->next = phead;
  80. 	phead->prev = newnode;
  81.  
  82. 	// 复用
  83. 	// LTInsert(phead, x);
  84. }
  85.  
  86. // 双向链表尾删
  87. void LTPopBack(LTNode* phead)
  88. {
  89. 	assert(phead);
  90. 	assert(!LTEmpty(phead));
  91.  
  92. 	LTNode* tail = phead->prev;
  93. 	LTNode* tailPrev = tail->prev;
  94.  
  95. 	free(tail);
  96. 	tailPrev->next = phead;
  97. 	phead->prev = tailPrev;
  98.  
  99. 	// 复用
  100. 	// LTErase(phead->prev);
  101. }
  102.  
  103. // 双向链表头插
  104. void LTPushFront(LTNode* phead, LTDataType x)
  105. {
  106. 	assert(phead);
  107. 	LTNode* newnode = BuyLTNode(x);
  108.  
  109. 	newnode->next = phead->next;
  110. 	phead->next->prev = newnode;
  111. 	phead->next = newnode;
  112. 	newnode->prev = phead;
  113.  
  114. 	// 复用
  115. 	// LTInsert(phead->next, x);
  116. }
  117.  
  118. // 双向链表头删
  119. void LTPopFront(LTNode* phead)
  120. {
  121. 	assert(phead);
  122. 	assert(!LTEmpty(phead));
  123. 	LTNode* first = phead->next;
  124. 	LTNode* second = first->next;
  125.  
  126. 	phead->next = second;
  127. 	second->prev = phead;
  128.  
  129. 	free(first);
  130.  
  131. 	// 复用
  132. 	// LTErase(phead->next);
  133. }
  134.  
  135. // 双向链表查找
  136. LTNode* LTFind(LTNode* phead, LTDataType x)
  137. {
  138. 	assert(phead);
  139.  
  140. 	LTNode* cur = phead->next;
  141. 	while (cur != phead)
  142. 	{
  143. 		if (cur->data == x)
  144. 		{
  145. 			return cur;
  146. 		}
  147.  
  148. 		cur = cur->next;
  149. 	}
  150.  
  151. 	return NULL;
  152. }
  153.  
  154. // 双向链表在pos的前面进行插入
  155. void LTInsert(LTNode* pos, LTDataType x)
  156. {
  157. 	assert(pos);
  158.  
  159. 	LTNode* prev = pos->prev;
  160. 	LTNode* newnode = BuyLTNode(x);
  161.  
  162. 	prev->next = newnode;
  163. 	newnode->prev = prev;
  164. 	newnode->next = pos;
  165. 	pos->prev = newnode;
  166. }
  167.  
  168. // 双向链表删除pos位置的节点
  169. void LTErase(LTNode* pos)
  170. {
  171. 	assert(pos);
  172.  
  173. 	LTNode* posPrev = pos->prev;
  174. 	LTNode* posNext = pos->next;
  175.  
  176. 	posPrev->next = posNext;
  177. 	posNext->prev = posPrev;
  178.  
  179. 	free(pos);
  180. }

3.2 -> List.h

  1. #pragma once
  2.  
  3. #define  _CRT_SECURE_NO_WARNINGS 1
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <assert.h>
  7. #include <stdbool.h>
  8.  
  9. // 带头+双向+循环链表增删查改实现
  10. typedef int LTDataType;
  11.  
  12. typedef struct LTNode
  13. {
  14. 	LTDataType data;
  15. 	struct LTNode* next;
  16. 	struct LTNode* prev;
  17. }LTNode;
  18.  
  19. // 双向链表初始化
  20. LTNode* LTInit();
  22. // 动态申请一个结点
  23. LTNode* BuyLTNode(LTDataType x);
  25. // 双向链表销毁
  26. void LTDestory(LTNode* phead);
  27.  
  28. // 双向链表打印
  29. void LTPrint(LTNode* phead);
  30.  
  31. // 双向链表判空
  32. bool LTEmpty(LTNode* phead);
  33.  
  34. // 双向链表尾插
  35. void LTPushBack(LTNode* phead, LTDataType x);
  36.  
  37. // 双向链表尾删
  38. void LTPopBack(LTNode* phead);
  39.  
  40. // 双向链表头插
  41. void LTPushFront(LTNode* phead, LTDataType x);
  42.  
  43. // 双向链表头删
  44. void LTPopFront(LTNode* phead);
  45.  
  46. // 双向链表查找
  47. LTNode* LTFind(LTNode* phead, LTDataType x);
  49. // 双向链表在pos的前面进行插入
  50. void LTInsert(LTNode* pos, LTDataType x);
  51.  
  52. // 双向链表删除pos位置的节点
  53. void LTErase(LTNode* pos);

3.3 -> Test.c

  1. #include "List.h"
  2.  
  3. // 尾插测试
  4. void Test1()
  5. {
  6. 	LTNode* plist = LTInit();
  7.  
  8. 	LTPushBack(plist, 1);
  9. 	LTPushBack(plist, 2);
  10. 	LTPushBack(plist, 3);
  11. 	LTPushBack(plist, 4);
  12. 	LTPushBack(plist, 5);
  13.  
  14. 	LTPrint(plist);
  15.  
  16. 	LTDestory(plist);
  17. 	plist = NULL;
  18. }
  19.  
  20. // 尾删测试
  21. void Test2()
  22. {
  23. 	LTNode* plist = LTInit();
  24.  
  25. 	LTPushBack(plist, 1);
  26. 	LTPushBack(plist, 2);
  27. 	LTPushBack(plist, 3);
  28. 	LTPushBack(plist, 4);
  29. 	LTPushBack(plist, 5);
  30.  
  31. 	LTPrint(plist);
  32.  
  33. 	LTPopBack(plist);
  34. 	LTPrint(plist);
  35. 	LTPopBack(plist);
  36. 	LTPrint(plist);
  37. 	LTPopBack(plist);
  38. 	LTPrint(plist);
  39. 	LTPopBack(plist);
  40. 	LTPrint(plist);
  41. 	LTPopBack(plist);
  42. 	LTPrint(plist);
  43.  
  44. 	LTDestory(plist);
  45. 	plist = NULL;
  46. }
  47.  
  48. // 头插测试
  49. void Test3()
  50. {
  51. 	LTNode* plist = LTInit();
  52.  
  53. 	LTPushFront(plist, 1);
  54. 	LTPushFront(plist, 2);
  55. 	LTPushFront(plist, 3);
  56. 	LTPushFront(plist, 4);
  57. 	LTPushFront(plist, 5);
  58.  
  59. 	LTPrint(plist);
  60.  
  61. 	LTDestory(plist);
  62. 	plist = NULL;
  63. }
  64.  
  65. // 头删测试
  66. void Test4()
  67. {
  68. 	LTNode* plist = LTInit();
  69.  
  70. 	LTPushBack(plist, 1);
  71. 	LTPushBack(plist, 2);
  72. 	LTPushBack(plist, 3);
  73. 	LTPushBack(plist, 4);
  74. 	LTPushBack(plist, 5);
  75.  
  76. 	LTPrint(plist);
  77.  
  78. 	LTPopFront(plist);
  79. 	LTPrint(plist);
  80. 	LTPopFront(plist);
  81. 	LTPrint(plist);
  82. 	LTPopFront(plist);
  83. 	LTPrint(plist);
  84. 	LTPopFront(plist);
  85. 	LTPrint(plist);
  86. 	LTPopFront(plist);
  87. 	LTPrint(plist);
  88.  
  89. 	LTDestory(plist);
  90. 	plist = NULL;
  91. }
  92.  
  93. // 查找插入测试
  94. void Test5()
  95. {
  96. 	LTNode* plist = LTInit();
  97.  
  98. 	LTPushBack(plist, 1);
  99. 	LTPushBack(plist, 2);
  100. 	LTPushBack(plist, 3);
  101. 	LTPushBack(plist, 4);
  102. 	LTPushBack(plist, 5);
  103.  
  104. 	LTPrint(plist);
  105.  
  106. 	LTNode* pos = LTFind(plist, 3);
  107. 	if (pos)
  108. 		LTInsert(pos, 99);
  109. 	LTPrint(plist);
  110.  
  111. 	LTDestory(plist);
  112. 	plist = NULL;
  113. }
  114.  
  115. int main()
  116. {
  117.  
  118.  
  119. 	return 0;
  120. }

感谢大佬们支持！！！

互三啦！！！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/206485
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号