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

【数据结构】 链表_链表需要先清空在销毁吗

作者：运维做开发 | 2024-07-01 18:27:43

赞

踩

链表需要先清空在销毁吗

链表的概念及结构

概念：基于数组的缺点，数据结构中诞生了新的结构就是 链表

当一组数据需要频繁的进行插入、删除操作时候，链表则是首选的数据结构

链表也属于 线性表

链表的组成

链表由结点组成

结点分为两部分：

  • 数据域，保存存储的数据元素

  • 指针域，指向下一个结点的地址

注：链表也属于线性表，拥有线性表的所有特点

结点的创建：

  1. struct Node{
  2.     int data;    //数据域
  3.     struct Node *next;    //指针域
  4. };

结点结构体示意图：

实现单向链表，能够存放整型数据，设计需求如下：

设计需求：

  1. 链表的初始化

  1. 获取链表长度

  1. 插入指定位置结点

  1. 遍历链表

  1. 删除指定位置结点

  1. 清空链表

  1. 释放链表

链表的初始化

链表初始化 核心代码：
  1. typedef struct node
  2. {
  3.     int data;//数据域
  4.     struct node* next; //指针域
  5. }Node, *LinkList;  //Node是struct node的别名， LinkList 代表struct node*数据类型
  6.  
  7. //链表的初始化
  8. LinkList creat_list()
  9. {
  10.     LinkList head  = (Node *)malloc(sizeof(Node));
  11.     if (!head)
  12.     {
  13.         printf("内存分配失败\n");
  14.         return NULL;
  15.     }
  16.  
  17.     head->next = NULL; //带头结点的链表，只维护指针域，无需维护数据域
  18.  
  19.     return head;
  20. }

功能：

创建一个链表的头结点，并返回给使用者

链表长度获取

链表统计 核心代码：
  1. //统计链表长度
  2. int size_list(LinkList head)
  3. {
  4.     if (head == NULL)
  5.     {
  6.         printf("传入链表为空\n");
  7.         return 0;
  8.     }
  9.     Node * pCur = head->next;  //获取第一个有数据的结点
  10.  
  11.     int num = 0;
  12.     while (pCur != NULL)
  13.     {
  14.         num++;
  15.         pCur = pCur->next;
  16.     }
  17.     return num;
  18. }

功能：

统计链表中结点的个数并返回

链表的插入

链表插入 核心代码：
  1. //插入结点  参数1 链表的头结点   参数2  插入位置   参数3 插入数据
  2. void insert_list(LinkList head, int pos , int val)
  3. {
  4.     if (head == NULL)
  5.     {
  6.         printf("传入链表为空\n");
  7.         return;
  8.     }
  9.  
  10.     if (pos < 0 || pos > size_list(head))
  11.     {
  12.         printf("插入位置无效\n");
  13.         return;
  14.     }
  15.  
  16.     //辅助指针，帮助我们找到待插入位置的前驱结点
  17.     Node* pCur = head;
  18.     for (int i = 0; i < pos; i++)
  19.     {
  20.         pCur = pCur->next;
  21.     }
  22.  
  23.     //创建新结点
  24.     Node* newNode = (Node *)malloc(sizeof( Node));
  25.     if (!newNode)
  26.     {
  27.         return;
  28.     }
  29.     newNode->data = val;
  30.     newNode->next = NULL;
  31.  
  32.     //将新结点插入到链表长
  33.     newNode->next = pCur->next;
  34.     pCur->next = newNode;
  35. }

功能：

向指定的位置上，插入新的结点

链表的遍历

链表遍历 核心代码：
  1. //遍历链表
  2. void foreach_list(LinkList head)
  3. {
  4.     if (head == NULL)
  5.     {
  6.         printf("传入链表为空\n");
  7.         return;
  8.     }
  9.  
  10.     Node* pCur = head->next;  //拿到第一个有数据的结点
  11.  
  12.     while (pCur != NULL)
  13.     {
  14.         printf("%d ", pCur->data);
  15.         pCur = pCur->next;
  16.     }
  17.     printf("\n");
  18. }

功能：

打印链表中每个结点的数据域

链表的删除

链表删除 核心代码：
  1. //删除结点  参数1  链表表头   参数2  删除位置
  2. void delete_list(LinkList head, int pos)
  3. {
  4.     if (head == NULL)
  5.     {
  6.         printf("传入链表为空\n");
  7.         return;
  8.     }
  9.  
  10.     if (pos < 0 || pos > size_list(head) - 1)
  11.     {
  12.         
  13.         printf("删除位置无效\n");
  14.         return;
  15.     }
  16.  
  17.     //辅助指针，帮助我们找到待删除位置的前驱结点
  18.     Node* pCur = head;
  19.     for (int i = 0; i < pos; i++)
  20.     {
  21.         pCur = pCur->next;
  22.     }
  23.     //记录待删除结点
  24.     Node* pDel = pCur->next;
  25.     //更改指针，删除结点
  26.     pCur->next = pDel->next;
  27.     //释放待删除的结点
  28.     free(pDel);
  29. }

功能：

删除指定位置上的结点

链表的清空

链表清空 核心代码：
  1. //清空链表
  2. void clear_list(LinkList head)
  3. {
  4. 	if (head == NULL)
  5. 	{
  6. 		printf("传入链表为空\n");
  7. 		return;
  8. 	}
  9.  
  10. 	//指向第一个有数据的结点
  11. 	Node * pCur = head->next;
  12.  
  13. 	while (pCur != NULL)
  14. 	{
  15. 		//先保存住下一个节点的位置
  16. 		Node * pNext = pCur->next;
  17.  
  18. 		//释放节点
  19. 		free(pCur);
  20. 		pCur = pNext;
  21. 	}
  22.  
  23. 	head->next = NULL;
  24.  
  25. }

功能：

删除指定位置上的结点

链表的销毁

链表清空 核心代码：
  1. //销毁链表
  2. void destroy_list(LinkList head)
  3. {
  4.     if (head == NULL)
  5.     {
  6.         printf("传入链表为空\n");
  7.         return;
  8.     }
  9.  
  10.     //先清空链表
  11.     clear_list(head);
  12.  
  13.     //将头结点也释放掉，完成整个链表的销毁
  14.     free(head);
  15.     head = NULL;
  16. }

功能：

删除指定位置上的结点

完整代码：

  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include<stdio.h>
  3. #include<string.h>
  4. #include<stdlib.h>
  5.  
  6. typedef struct node
  7. {
  8. 	int data;//数据域
  9. 	struct node* next; //指针域
  10. }Node, *LinkList;  //Node是struct node的别名， LinkList 代表struct node*数据类型
  11.  
  12. //链表的初始化
  13. LinkList creat_list()
  14. {
  15. 	LinkList head  = (Node *)malloc(sizeof(Node));
  16. 	if (!head)
  17. 	{
  18. 		printf("内存分配失败\n");
  19. 		return NULL;
  20. 	}
  21.  
  22. 	head->next = NULL; //带头结点的链表，只维护指针域，无需维护数据域
  23.  
  24. 	return head;
  25. }
  26.  
  27. //统计链表长度
  28. int size_list(LinkList head)
  29. {
  30. 	if (head == NULL)
  31. 	{
  32. 		printf("传入链表为空\n");
  33. 		return 0;
  34. 	}
  35. 	Node * pCur = head->next;  //获取第一个有数据的结点
  36.  
  37. 	int num = 0;
  38. 	while (pCur != NULL)
  39. 	{
  40. 		num++;
  41. 		pCur = pCur->next;
  42. 	}
  43. 	return num;
  44. }
  45.  
  46. //插入结点  参数1 链表的头结点   参数2  插入位置   参数3 插入数据
  47. void insert_list(LinkList head, int pos , int val)
  48. {
  49. 	if (head == NULL)
  50. 	{
  51. 		printf("传入链表为空\n");
  52. 		return;
  53. 	}
  54.  
  55. 	if (pos < 0 || pos > size_list(head))
  56. 	{
  57. 		printf("插入位置无效\n");
  58. 		return;
  59. 	}
  60.  
  61. 	//辅助指针，帮助我们找到待插入位置的前驱结点
  62. 	Node* pCur = head;
  63. 	for (int i = 0; i < pos; i++)
  64. 	{
  65. 		pCur = pCur->next;
  66. 	}
  67.  
  68. 	//创建新结点
  69. 	Node* newNode = (Node *)malloc(sizeof( Node));
  70. 	if (!newNode)
  71. 	{
  72. 		return;
  73. 	}
  74. 	newNode->data = val;
  75. 	newNode->next = NULL;
  76.  
  77. 	//将新结点插入到链表长
  78. 	newNode->next = pCur->next;
  79. 	pCur->next = newNode;
  80. }
  81.  
  82.  
  83. //遍历链表
  84. void foreach_list(LinkList head)
  85. {
  86. 	if (head == NULL)
  87. 	{
  88. 		printf("传入链表为空\n");
  89. 		return;
  90. 	}
  91.  
  92. 	Node* pCur = head->next;  //拿到第一个有数据的结点
  93.  
  94. 	while (pCur != NULL)
  95. 	{
  96. 		printf("%d ", pCur->data);
  97. 		pCur = pCur->next;
  98. 	}
  99. 	printf("\n");
  100. }
  101.  
  102.  
  103. //删除结点  参数1  链表表头   参数2  删除位置
  104. void delete_list(LinkList head, int pos)
  105. {
  106. 	if (head == NULL)
  107. 	{
  108. 		printf("传入链表为空\n");
  109. 		return;
  110. 	}
  111.  
  112. 	if (pos < 0 || pos > size_list(head) - 1)
  113. 	{
  114. 		
  115. 		printf("删除位置无效\n");
  116. 		return;
  117. 	}
  118.  
  119. 	//辅助指针，帮助我们找到待删除位置的前驱结点
  120. 	Node* pCur = head;
  121. 	for (int i = 0; i < pos; i++)
  122. 	{
  123. 		pCur = pCur->next;
  124. 	}
  125. 	//记录待删除结点
  126. 	Node* pDel = pCur->next;
  127. 	//更改指针，删除结点
  128. 	pCur->next = pDel->next;
  129. 	//释放待删除的结点
  130. 	free(pDel);
  131. }
  132.  
  133. //清空链表
  134. void clear_list(LinkList head)
  135. {
  136. 	if (head == NULL)
  137. 	{
  138. 		printf("传入链表为空\n");
  139. 		return;
  140. 	}
  141.  
  142. 	//指向第一个有数据的结点
  143. 	Node * pCur = head->next;
  144.  
  145. 	while (pCur != NULL)
  146. 	{
  147. 		//先保存住下一个节点的位置
  148. 		Node * pNext = pCur->next;
  149.  
  150. 		//释放节点
  151. 		free(pCur);
  152. 		pCur = pNext;
  153. 	}
  154.  
  155. 	head->next = NULL;
  156.  
  157. }
  158.  
  159.  
  160. //销毁链表
  161. void destroy_list(LinkList head)
  162. {
  163. 	if (head == NULL)
  164. 	{
  165. 		printf("传入链表为空\n");
  166. 		return;
  167. 	}
  168.  
  169. 	//先清空链表
  170. 	clear_list(head);
  171.  
  172. 	//将头结点也释放掉，完成整个链表的销毁
  173. 	free(head);
  174. 	head = NULL;
  175. }
  176. int main() {
  177.  
  178. 	LinkList head = creat_list();  //创建链表，获取表头
  179.  
  180. 	//打印链表长度
  181. 	printf("链表长度为：%d\n", size_list(head));
  182.  
  183. 	//插入结点
  184. 	insert_list(head, 0, 10);
  185. 	insert_list(head, 0, 20);
  186. 	insert_list(head, 1, 30);
  187. 	insert_list(head, 0, 40);
  188.  
  189. 	//遍历链表
  190. 	printf("插入结点后，遍历结果为：\n");  // 40 20 30 10 
  191. 	foreach_list(head);
  192.  
  193. 	//打印链表长度
  194. 	printf("链表长度为：%d\n", size_list(head));
  195.  
  196. 	//删除结点
  197. 	delete_list(head, 2);
  198. 	printf("删除结点后，遍历结果为：\n");  // 40 20 10
  199. 	foreach_list(head);
  200.  
  201. 	//清空链表
  202. 	clear_list(head);
  203. 	printf("清空链表后，遍历结果为：\n");  
  204. 	foreach_list(head);
  205.  
  206. 	//销毁链表
  207. 	destroy_list(head);
  208.  
  209. 	system("pause");
  210. 	return EXIT_SUCCESS;
  211. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/运维做开发/article/detail/777273
推荐阅读
相关标签

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

  

闽ICP备14008679号