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

【数据结构】——双链表的实现（赋源码）

作者：我家自动化 | 2024-07-30 17:38:41

赞

踩

【数据结构】——双链表的实现（赋源码）

双链表的概念和结构

双链表的全称叫做：带头双向循环链表

它的结构示意图如下

注意：这⾥的“带头”跟前⾯我们说的单链表的“头结点”是两个概念，实际前⾯的在单链表阶段称呼不严谨，但是为了读者们更好的理解就直接称为单链表的头结点。 

带头链表⾥的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这⾥“放哨的”也可以认为是用来占位置滴！！！

双链表的实现

首先先在结构体当中输入需要的数据，则有如下的数据是需要的

结构体中的数据

  1. typedef int LTDataType;//方便对数据类型进行统一的替换
  2. typedef struct ListNode ListNode;//对结构体的名称重新命名交ListNode
  3. struct ListNode
  4. {
  5. 	LTDataType data;
  6. 	ListNode* next;
  7. 	ListNode* prev;
  8. };

则上面的图可以变成这样

双链表新结点的创建及双链表的初始化

  1. ListNode* LTBuyNode(LTDataType x)
  2. {
  3. 	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));//一个结构体的大小
  4. 	if (newnode == NULL)
  5. 	{
  6. 		perror("malloc fail!");
  7. 		exit(1);
  8. 	}
  9. 	newnode->data = x;
  10. 	newnode->next = newnode->prev = newnode;
  11.  
  12. 	return newnode;//返回头结点
  13. }

链表的初始化需要一个创建的新的结点作为哨兵位

  1. //void LTInit(ListNode** pphead)
  2. //{
  3. //	//创建一个头结点即“哨兵位”
  4. //	*pphead = LTBuyNode(-1);
  5. //}
  6.  
  7. ListNode* LTInit()
  8. {
  9. 	ListNode* phead = LTBuyNode(-1);
  10. 	return phead;
  11. }
  12.  
  13. //上面是两种初始化的方法
  14. //第一种需要传递一个二级指针

在上面的代码当中，我们只需要创建一个头结点来保证第一个“头”存在即可。

插入
第一个参数传一级还是二级，要看phead指向的结点会不会改变
如果发生改变，那么pphead的改变要影响实参，传二级
如果不发生改变，pphead不会影响实参，传一级

双链表的尾插

  1. //尾插
  2. void LTPushBack(ListNode* phead, LTDataType x)
  3. {
  4. 	assert(phead);
  5. 	//创建需要插入的结点
  6.     //上面初始化的newnode是头结点，这个newnode是尾插的结点
  7. 	ListNode* newnode = LTBuyNode(x);
  8.  
  9. 	newnode->next = phead;
  10. 	newnode->prev = phead->prev;
  11.  
  12. 	phead->prev->next = newnode;
  13. 	phead->prev = newnode;
  14. }

 上面的顺序是不能改变的，否则无法让新结点找到原来链表的位置

这边测试一下我们的尾插代码依次插入1 2 3 4  

 双链表的头插

  1. //头插
  2. void LTPushFront(ListNode* phead, LTDataType x)
  3. {
  4. 	assert(phead);
  5. 	ListNode* newnode = LTBuyNode(x);
  6.  
  7. 	newnode->next = phead->next;
  8. 	newnode->prev = phead;
  9.  
  10. 	phead->next->prev = newnode;
  11. 	phead->next = newnode;
  12. }

头插和尾插是类似的 ，不过有一个特殊的地方

头插是头插在哨兵位和第一个真正的结点中间

同样的，上面的顺序位置是不能改变的

测试头插代码

这个代码是在上面尾插代码基础上的操作

 双链表的尾删

  1. //尾删
  2. void LTPopBack(ListNode* phead)
  3. {
  4. 	assert(phead);
  5. 	assert(!Empty(phead));
  6.  
  7. 	ListNode* del = phead->prev;
  8. 	ListNode* prev = del->prev;
  9.  
  10. 	prev->next = phead;
  11. 	phead->prev = prev;
  12.  
  13. 	free(del);
  14. 	del = NULL;
  15. }

 这边仍然是在尾插的基础上的操作

这边我们进行了五次尾删，所以代码assert断言了！

将一次尾删注释，下面就是尾删的效果 

双链表的头删 

  1. //头删
  2. void LTPopFront(ListNode* phead)
  3. {
  4. 	assert(phead);
  5. 	assert(!Empty(phead));
  6. 	ListNode* del = phead->next;
  7. 	del->next->prev = phead;
  8. 	phead->next = del->next;
  9.  
  10. 	free(del);
  11. 	del = NULL;
  12. }

这个仍然是在尾插的基础上操作的，如果继续删除，跟上面的情况一样assert断言报错 

以上就是最基础的增删 ，下面开始加大难度！

双链表中查找数据pos

  1. //找相同数据
  2. ListNode* LTFind(ListNode* phead, LTDataType x)
  3. {
  4. 	assert(phead);
  5. 	ListNode* pcur = phead->next;
  6. 	while (pcur != phead)
  7. 	{
  8. 		if (pcur->data == x)
  9. 		{
  10. 			return pcur;
  11. 		}
  12. 		pcur = pcur->next;
  13. 	}
  14. 	return NULL;
  15. }

这边我们查找的是数据3，所以我们可以找到 

 

这个在链表中没有数据6，所以我们没有找到相关的数据 

 在pos之后插入结点

这个和尾插以及头插其实是类似的，这里主要是寻找到pos结点，然后插入想要的数据

  1. //在pos之后插入结点
  2. void LTInsert(ListNode* pos, LTDataType x)
  3. {
  4.     assert(pos);
  5.  
  6.     ListNode* newnode = LTBuyNode(x);
  7.  
  8.     newnode->next = pos->next;
  9.     newnode->prev = pos;
  10.  
  11.     pos->next->prev = newnode;
  12.     pos->next = newnode;
  13. }

在3的后面插入数据10 

 

删除pos结点 

  1. ​//删除指定位置节点
  2. void LTErase(ListNode* pos)
  3. {
  4. 	assert(pos);
  5. 	// pos->prev  pos   pos->next
  6.  
  7. 	pos->prev->next = pos->next;
  8. 	pos->next->prev = pos->prev;
  9.  
  10. 	free(pos);
  11. 	pos = NULL;
  12. }
  13.  
  14. ​

双链表的销毁 

这里我们提供了两种的销毁方法，两种方法基本是类似的

  1. //销毁
  2. void LTDesTroy(ListNode** pphead)
  3. {
  4. 	assert(pphead && *pphead);
  5. 	ListNode* pcur = (*pphead)->next;
  6. 	while (pcur != *pphead)
  7. 	{
  8. 		ListNode* next = pcur->next;
  9. 		free(pcur);
  10. 		pcur = next;
  11. 	}
  12. 	//销毁哨兵位结点
  13. 	free(*pphead);
  14. 	*pphead = NULL;
  15. 	pcur = NULL;
  16. }
  17. //为了更好的记忆，我们让销毁也传递一级指针
  18. void LTDesTroy2(ListNode* phead)//传一级，需要手动将plist置为NULL
  19. {
  20. 	assert(phead);
  21. 	ListNode* pcur = phead->next;
  22. 	while (pcur != phead)
  23. 	{
  24. 		ListNode* next = pcur->next;
  25. 		free(pcur);
  26. 		pcur = next;
  27. 	}
  28. 	free(phead);
  29. 	phead = pcur = NULL;
  30. }

最后我们将双向链表的源码附上

list.h

  1. #pragma once
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<assert.h>
  5. #include<stdbool.h>
  6.  
  7. typedef int LTDataType;
  8. typedef struct ListNode ListNode;
  9. struct ListNode
  10. {
  11. 	LTDataType data;
  12. 	ListNode* next;
  13. 	ListNode* prev;
  14. };
  15.  
  16. ListNode* LTBuyNode(LTDataType x);
  17. //为了保存接口的一致性
  18. //
  19. //初始化
  20. //void LTInit(ListNode** pphead);
  21. ListNode* LTInit();  
  22.  
  23. //
  24. void LTPrint(ListNode* phead);
  25.  
  26. bool Empty(ListNode* phead);
  27.  
  28. //插入
  29. //第一个参数传一级还是二级，要看phead指向的结点会不会改变
  30. //如果发生改变，那么pphead的改变要影响实参，传二级
  31. //如果不发生改变，pphead不会影响实参，传一级
  32.  
  33. //尾插
  34. void LTPushBack(ListNode* phead, LTDataType x);
  35.  
  36. //头插
  37. void LTPushFront(ListNode* phead, LTDataType x);
  38.  
  39. //尾删
  40. void LTPopBack(ListNode* phead);
  41.  
  42. //头删
  43. void LTPopFront(ListNode* phead);
  44.  
  45. //在pos之后插入结点
  46. void LTInsert(ListNode* pos, LTDataType x);
  47.  
  48. //删除指定位置的结点
  49. void LTErase(ListNode* pos);
  50.  
  51. //找数据
  52. ListNode* LTFind(ListNode* phead, LTDataType x);
  53.  
  54. //销毁
  55. void LTDesTroy(ListNode** pphead);
  56. void LTDesTroy2(ListNode* phead);//传一级，需要手动将plist置为NULL

 List.c

  1. #include"List.h"
  2.  
  3. ListNode* LTBuyNode(LTDataType x)
  4. {
  5. 	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
  6. 	if (newnode == NULL)
  7. 	{
  8. 		perror("malloc fail!");
  9. 		exit(1);
  10. 	}
  11. 	newnode->data = x;
  12. 	newnode->next = newnode->prev = newnode;
  13.  
  14. 	return newnode;
  15. }
  16. //初始化
  17.  
  18. //void LTInit(ListNode** pphead)
  19. //{
  20. //	//创建一个头结点即“哨兵位”
  21. //	*pphead = LTBuyNode(-1);
  22. //}
  23. ListNode* LTInit()
  24. {
  25. 	ListNode* phead = LTBuyNode(-1);
  26. 	return phead;
  27. }
  28.  
  29. //打印
  30. void LTPrint(ListNode* phead)
  31. {
  32. 	ListNode* pcur = phead->next;
  33. 	while (pcur != phead)
  34. 	{
  35. 		printf("%d->", pcur->data);
  36. 		pcur = pcur->next;
  37. 	}
  38. 	printf("\n");
  39. }
  40.  
  41. bool Empty(ListNode* phead)
  42. {
  43. 	assert(phead);
  44. 	return phead->next == phead;
  45. }
  46.  
  47. //尾插
  48. void LTPushBack(ListNode* phead, LTDataType x)
  49. {
  50. 	assert(phead);
  51. 	//创建需要插入的结点
  52. 	ListNode* newnode = LTBuyNode(x);
  53.  
  54. 	newnode->next = phead;
  55. 	newnode->prev = phead->prev;
  56.  
  57. 	phead->prev->next = newnode;
  58. 	phead->prev = newnode;
  59. }
  60. //头插
  61. void LTPushFront(ListNode* phead, LTDataType x)
  62. {
  63. 	assert(phead);
  64. 	ListNode* newnode = LTBuyNode(x);
  65.  
  66. 	newnode->next = phead->next;
  67. 	newnode->prev = phead;
  68.  
  69. 	phead->next->prev = newnode;
  70. 	phead->next = newnode;
  71. }
  72.  
  73. //尾删
  74. void LTPopBack(ListNode* phead)
  75. {
  76. 	assert(phead);
  77. 	assert(!Empty(phead));
  78.  
  79. 	ListNode* del = phead->prev;
  80. 	ListNode* prev = del->prev;
  81.  
  82. 	prev->next = phead;
  83. 	phead->prev = prev;
  84.  
  85. 	free(del);
  86. 	del = NULL;
  87. }
  88.  
  89. //头删
  90. void LTPopFront(ListNode* phead)
  91. {
  92. 	assert(phead);
  93. 	assert(!Empty(phead));
  94. 	ListNode* del = phead->next;
  95. 	del->next->prev = phead;
  96. 	phead->next = del->next;
  97.  
  98. 	free(del);
  99. 	del = NULL;
  100. }
  101. //找相同数据
  102. ListNode* LTFind(ListNode* phead, LTDataType x)
  103. {
  104. 	assert(phead);
  105. 	ListNode* pcur = phead->next;
  106. 	while (pcur != phead)
  107. 	{
  108. 		if (pcur->data == x)
  109. 		{
  110. 			return pcur;
  111. 		}
  112. 		pcur = pcur->next;
  113. 	}
  114. 	return NULL;
  115. }
  116.  
  117. //在pos之后插入结点
  118. void LTInsert(ListNode* pos, LTDataType x)
  119. {
  120. 	assert(pos);
  121.  
  122. 	ListNode* newnode = LTBuyNode(x);
  123.  
  124. 	newnode->next = pos->next;
  125. 	newnode->prev = pos;
  126.  
  127. 	pos->next->prev = newnode;
  128. 	pos->next = newnode;
  129. }
  130.  
  131. //删除指定位置节点
  132. void LTErase(ListNode* pos)
  133. {
  134. 	assert(pos);
  135. 	// pos->prev  pos   pos->next
  136.  
  137. 	pos->prev->next = pos->next;
  138. 	pos->next->prev = pos->prev;
  139.  
  140. 	free(pos);
  141. 	pos = NULL;
  142. }
  143.  
  144. //销毁
  145. void LTDesTroy(ListNode** pphead)
  146. {
  147. 	assert(pphead && *pphead);
  148. 	ListNode* pcur = (*pphead)->next;
  149. 	while (pcur != *pphead)
  150. 	{
  151. 		ListNode* next = pcur->next;
  152. 		free(pcur);
  153. 		pcur = next;
  154. 	}
  155. 	//销毁哨兵位结点
  156. 	free(*pphead);
  157. 	*pphead = NULL;
  158. 	pcur = NULL;
  159. }
  160.  
  161. void LTDesTroy2(ListNode* phead)
  162. {
  163. 	assert(phead);
  164. 	ListNode* pcur = phead->next;
  165. 	while (pcur != phead)
  166. 	{
  167. 		ListNode* next = pcur->next;
  168. 		free(pcur);
  169. 		pcur = next;
  170. 	}
  171. 	free(phead);
  172. 	phead = pcur = NULL;
  173. }

test.c 

  1. #include"List.h"
  2. void test()
  3. {
  4. 	创建双向链表变量
  5. 	//ListNode* plist = NULL;
  6. 	//LTInit(&plist);
  7. 	ListNode* plist = LTInit();
  8.  
  9. 	LTPushBack(plist, 1);
  10. 	LTPushBack(plist, 2);
  11. 	LTPushBack(plist, 3);
  12. 	LTPushBack(plist, 4);
  13. 	LTPrint(plist);
  14.  
  15. 	ListNode* pos = LTFind(plist, 3);
  16. 	LTInsert(pos, 10);
  17. 	LTPrint(plist);
  18.  
  19. 	pos = LTFind(plist, 3);
  20. 	LTErase(pos);
  21. 	LTPrint(plist);
  22.  
  23. 	/*LTPopFront(plist);
  24. 	LTPrint(plist);
  25. 	LTPopFront(plist);
  26. 	LTPrint(plist);
  27. 	LTPopFront(plist);
  28. 	LTPrint(plist);
  29. 	LTPopFront(plist);
  30. 	LTPrint(plist);*/
  31.  
  32. 	/*LTPushFront(plist, 1);
  33. 	LTPrint(plist);
  34. 	LTPushFront(plist, 2);
  35. 	LTPrint(plist);
  36. 	LTPushFront(plist, 3);
  37. 	LTPrint(plist);
  38. 	LTPushFront(plist, 4);
  39. 	LTPrint(plist);*/
  40.  
  41. 	/*LTPopBack(plist);
  42. 	LTPrint(plist);
  43. 	LTPopBack(plist);
  44. 	LTPrint(plist);
  45. 	LTPopBack(plist);
  46. 	LTPrint(plist);
  47. 	LTPopBack(plist);
  48. 	LTPrint(plist);
  49. 	LTPopBack(plist);
  50. 	LTPrint(plist);*/
  51.  
  52. 	/*if (pos == NULL)
  53. 	{
  54. 		printf("没有找到\n");
  55. 	}
  56. 	else
  57. 	{
  58. 		printf("找到了\n");
  59. 	}*/
  60.  
  61. 	LTDesTroy(&plist);
  62. 	//LTDesTroy2(plist);
  63. 	//plist = NULL;
  64.  
  65.  
  66. 	
  67. }
  68.  
  69. int main()
  70. {
  71. 	test();
  72. 	return 0;
  73. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/904702
推荐阅读
相关标签

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

  

闽ICP备14008679号