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

链表（数据结构）_链表结构

作者：小蓝xlanll | 2024-06-04 04:38:43

赞

踩

链表结构

目录

链表

链表的分类

1、单向或者双向

2、带头或者不带头

3、循环或者非循环

总结：

单链表

创建链式结构

创建新节点

尾插

尾删

头插

头删

查找节点

在pos位置后插入

删除pos位置后的节点

销毁

总代码

链表

概念：

链表是一种物理结构上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表结构中的指针链接起来的！前一个元素中存放着后一个元素的地址！

结构：

结构中存放着链表下一个元素的地址！用一个指针来存储！

一般情况下一个链表结构中存放的是元素的值以及下一个位置的指针！或者多个链接元素的指针！

链表的分类

1、单向或者双向

单向链表：

链表结构中只有一个指针，该指针是存放的是下一个元素的地址的指针变量！

看图理解：

双向链表：

结构中有两个指针，分别记录它的前一个元素和后一个元素的地址！

看图理解：

2、带头或者不带头

1、带哨兵位的头节点的单向链表：

2、带哨兵位头节点的双向链表：

3、循环或者非循环

1、单向循环链表

2、双向循环链表 

3、单向带头循环链表 

4、带头双向循环链表 

总结：

1、图形

以上图都是链表的逻辑结构，物理上也就是底层并非是这样指向的，而是每个指针里面都存储它所对应节点的地址！

2、种类

链表类型总共有八种，分别是按照以上的三大类来组合：

第一类：单向或双向

第二类：带头或不带头

第三类：循环或不循环

八种链表：

1、单向链表

2、双向链表

3、单向带头链表

4、双向带头链表

5、单向循环链表

6、双向循环链表

7、单向带头循环链表

8、双向带头循环链表

本篇博主只带大家写一种链表：单链表，因为只要会了一种链表，其它链表都是大同小异的！

单链表

概念：

单链表中的节点，后一个节点中存的是前一个节点的地址，最后一个节点的中的地址为空！

逻辑结构：

物理结构：

 

总结：

1、链式结构在逻辑上是连续的，但在物理结构上不一定连续。

2、现实中的节点一般是从堆上申请出来的

3、从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续！

下面我们用代码实现单链表！

创建链式结构

思路：

我们用一个结构体来封装链表节点的值以及该类型结构的地址，值是链表节点中要保存的值，结构体的的地址是用来存储前一个结构节点的地址，若该节点是最后一个则地址里面的值是NULL

代码：

  1. //用typedef重命名，后续可以继续使用
  2. typedef int SLDateType;
  3.  
  4. //创建链表结构
  5. typedef struct SListNode
  6. {
  7. 	SLDateType val;//节点值
  8. 	struct SListNode* next;//下一个节点的位置
  9.  
  10. }SLNode;

创建新节点

思路：

创建新节点，要将链表链起来，我们就得要创造新的节点进行链接，才能形成链接功能。该功能可供我们用于头插，尾插，等功能中！

代码：

  1. //创建新节点
  2. SLNode* CreateNode(SLDateType x)
  3. {
  4. 	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
  5. 	//判断是否开辟成功
  6. 	if (newnode == NULL)
  7. 	{
  8. 		perror("malloc fali:");
  9. 		return NULL;
  10. 	}
  11. 	//开始赋值
  12. 	newnode->val = x;
  13. 	newnode->next = NULL;
  14.  
  15. 	//返回
  16. 	return newnode;
  17. }

尾插

思路：

单链表进行尾插，先要找到单链表的尾节点，随后在创建一个要插入的节点，让找到的尾节点的指针指向要插入的新节点，也就是尾节点中的结构体指针变量中保存要插入的新节点的地址！

代码：

  1. //尾插
  2. void SListPushBank(SLNode** pphead, SLDateType x)
  3. {
  4. 	//创建新节点
  5. 	SLNode* newnode = CreateNode(x);
  6.  
  7. 	//判断是否是空链表，空链表直接进行尾插
  8. 	if (*pphead == NULL)
  9. 	{
  10. 		*pphead = newnode;
  11. 	}
  12. 	else
  13. 	{
  14. 		//找尾
  15. 		SLNode* cur = *pphead;
  16. 		while (cur->next != NULL)
  17. 		{
  18. 			cur = cur->next;
  19. 		}
  20. 		
  21. 		//进行链接
  22. 		cur->next = newnode;
  23. 	}
  24. }

尾删

思路：

单链表进行尾删，先进行循环找尾节点，同时用一个指针来记录尾节点的前一个节点的地址。找到尾节点之后，将尾节点的前一个节点中的指针置为NULL。再将尾节点的空间进行free释放！最后将尾节点结构中的指针置为NULL

代码：

  1. //尾删
  2. void SListPopBank(SLNode** pphead)
  3. {
  4. 	//如果是NULL链表就不能再删
  5. 	assert(*pphead);
  6.  
  7. 	//判断一个的情况
  8. 	if ((*pphead)->next == NULL)
  9. 	{
  10. 		free((*pphead)->next);
  11. 		*pphead= NULL;
  12. 	}
  13. 	else
  14. 	{
  15. 		//找尾
  16. 		SLNode* cur = *pphead;
  17. 		SLNode* tail = NULL;
  18. 		while (cur->next != NULL)
  19. 		{
  20. 			tail = cur;
  21. 			cur = cur->next;
  22. 		}
  23.  
  24. 		//释放节点
  25. 		free(cur);
  26. 		cur = NULL;
  27.  
  28. 		//将前一个节点置为NULL
  29. 		tail->next = NULL;
  30. 	}
  31.  
  32. }

头插

思路：

单链表头插，就是创建一个新节点，让这个新节点结构中的指针指向头节点，再让新节点成为头节点即可！

代码：

  1. //头插
  2. void SListPushFront(SLNode** pphead, SLDateType x)
  3. {
  4. 	SLNode* newnode = CreateNode(x);
  5.  
  6. 	SLNode* tail = *pphead;
  7. 	*pphead = newnode;
  8. 	newnode->next = tail;
  9.  
  10. }

头删

思路：

单链表头删，用一个指针指向头后面的节点，随后将头节点空间释放，再让后面的节点成为头即可！

代码：

  1. //头删
  2. void SListPopFront(SLNode** pphead)
  3. {
  4. 	//如果是空链表就不进行删除
  5. 	assert(*pphead);
  6.  
  7. 	SLNode* cur = (*pphead)->next;
  8. 	SLNode* tail = *pphead;
  9. 	free(tail);
  10. 	tail = NULL;
  11. 	*pphead = cur;
  12. }

查找节点

思路：

循环遍历链表，找到我们要查找的节点，返回该节点的地址即可！若找不到返回NULL

代码：

  1. //节点查找
  2. SLNode* SListFind(SLNode* phead, SLDateType x)
  3. {
  4. 	SLNode* cur = phead;
  5. 	while (cur)
  6. 	{
  7. 		if (cur->val == x)
  8. 		{
  9. 			return cur;
  10. 		}
  11. 		cur = cur->next;
  12. 	}
  13. 	return NULL;
  14. }

在pos位置后插入

思路：

用一个指针记录pos位置的下一个节点，随后让pos节点结构体的指针指向新插入的节点。再让新插入节点结构的指针指向pos位置的下一个节点完成链接！

代码：
 

  1. // 在pos位置之后插入x
  2. void SListInsertAfter(SLNode* pos, SLDateType x)
  3. {
  4. 	//后面插入pos为NULL 不行
  5. 	assert(pos);
  6.  
  7. 	SLNode* newnode = CreateNode(x);
  8. 	SLNode* cur = pos->next;
  9. 	pos->next = newnode;
  10. 	newnode->next = cur;
  11. }

删除pos位置后的节点

思路：

用一个指针记录pos位置的下一个节点。再用一个指针记录pos位置的下下个节点，也就是pos位置的下一个节点的下一个节点，随后将pos位置的下一个节点空间释放。让pos位置节点结构中的指针指向pos位置的下下个节点即可！

代码：

  1. // 删除pos位置之后的值
  2. void SListEraseAfter(SLNode* pos)
  3. {
  4. 	//pos为NULL 不可删后面的
  5. 	assert(pos);
  6. 	SLNode* cur = pos->next;
  7.  
  8. 	if (cur == NULL)
  9. 	{
  10. 		free(cur);
  11. 		cur = NULL;
  12. 		pos->next = NULL;
  13. 	}
  14. 	else
  15. 	{
  16. 		SLNode* tail = cur->next;
  17. 		free(cur);
  18. 		pos->next = tail;
  19. 	}
  20. }

销毁

思路：

循环遍历链表，用一个指针记录销毁节点的后一个节点，一个指针记录销毁节点，让两者都往后走，依次循环进行销毁（释放节点空间）！

代码：

  1. // 销毁
  2. void SListDestroy(SLNode* phead)
  3. {
  4. 	SLNode* cur = phead;
  5. 	SLNode* tail = cur;
  6. 	while (cur)
  7. 	{
  8. 		tail = cur;
  9. 		cur = cur->next;
  10. 		free(tail);
  11. 	}
  12. 	tail = NULL;
  13. 	phead = NULL;
  14. }

总代码

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2.  
  3.  
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <string.h>
  7. #include <assert.h>
  8.  
  9. //用typedef重命名，后续可以继续使用
  10. typedef int SLDateType;
  11.  
  12. //创建链表结构
  13. typedef struct SListNode
  14. {
  15. 	SLDateType val;//节点值
  16. 	struct SListNode* next;//下一个节点的位置
  17.  
  18. }SLNode;
  19.  
  20.  
  21. //打印
  22. void SListPrint(SLNode* phead)
  23. {
  24. 	SLNode* cur = phead;
  25. 	while (cur != NULL)
  26. 	{
  27. 		printf("%d ->", cur->val);
  28. 		cur = cur->next;
  29. 	}
  30. 	printf("NULL\n");
  31. }
  32.  
  33. //创建新节点
  34. SLNode* CreateNode(SLDateType x)
  35. {
  36. 	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
  37. 	//判断是否开辟成功
  38. 	if (newnode == NULL)
  39. 	{
  40. 		perror("malloc fali:");
  41. 		return NULL;
  42. 	}
  43. 	//开始赋值
  44. 	newnode->val = x;
  45. 	newnode->next = NULL;
  46.  
  47. 	//返回
  48. 	return newnode;
  49. }
  50.  
  51. //尾插
  52. void SListPushBank(SLNode** pphead, SLDateType x)
  53. {
  54. 	//创建新节点
  55. 	SLNode* newnode = CreateNode(x);
  56.  
  57. 	//判断是否是空链表，空链表直接进行尾插
  58. 	if (*pphead == NULL)
  59. 	{
  60. 		*pphead = newnode;
  61. 	}
  62. 	else
  63. 	{
  64. 		//找尾
  65. 		SLNode* cur = *pphead;
  66. 		while (cur->next != NULL)
  67. 		{
  68. 			cur = cur->next;
  69. 		}
  70.  
  71. 		//进行链接
  72. 		cur->next = newnode;
  73. 	}
  74. }
  75.  
  76. //尾删
  77. void SListPopBank(SLNode** pphead)
  78. {
  79. 	//如果是NULL链表就不能再删
  80. 	assert(*pphead);
  81.  
  82. 	//判断一个的情况
  83. 	if ((*pphead)->next == NULL)
  84. 	{
  85. 		free((*pphead)->next);
  86. 		*pphead = NULL;
  87. 	}
  88. 	else
  89. 	{
  90. 		//找尾
  91. 		SLNode* cur = *pphead;
  92. 		SLNode* tail = NULL;
  93. 		while (cur->next != NULL)
  94. 		{
  95. 			tail = cur;
  96. 			cur = cur->next;
  97. 		}
  98.  
  99. 		//释放节点
  100. 		free(cur);
  101. 		cur = NULL;
  102.  
  103. 		//将前一个节点置为NULL
  104. 		tail->next = NULL;
  105. 	}
  106.  
  107. }
  108.  
  109. //头插
  110. void SListPushFront(SLNode** pphead, SLDateType x)
  111. {
  112. 	SLNode* newnode = CreateNode(x);
  113.  
  114. 	SLNode* tail = *pphead;
  115. 	*pphead = newnode;
  116. 	newnode->next = tail;
  117.  
  118. 	空链表直接插入
  119. 	//if ((*pphead) == NULL)
  120. 	//{
  121. 	//	*pphead = newnode;
  122. 	//}
  123. 	//else
  124. 	//{
  125. 	//	SLNode* cur = *pphead;
  126. 	//	*pphead = newnode;
  127. 	//	newnode->next = cur;
  128. 	//}
  129. }
  130.  
  131. //头删
  132. void SListPopFront(SLNode** pphead)
  133. {
  134. 	//如果是空链表就不进行删除
  135. 	assert(*pphead);
  136.  
  137. 	SLNode* cur = (*pphead)->next;
  138. 	SLNode* tail = *pphead;
  139. 	free(tail);
  140. 	tail = NULL;
  141. 	*pphead = cur;
  142. }
  143.  
  144. //节点查找
  145. SLNode* SListFind(SLNode* phead, SLDateType x)
  146. {
  147. 	SLNode* cur = phead;
  148. 	while (cur)
  149. 	{
  150. 		if (cur->val == x)
  151. 		{
  152. 			return cur;
  153. 		}
  154. 		cur = cur->next;
  155. 	}
  156. 	return NULL;
  157. }
  158.  
  159. // 在pos位置之后插入x
  160. void SListInsertAfter(SLNode* pos, SLDateType x)
  161. {
  162. 	//后面插入pos为NULL 不行
  163. 	assert(pos);
  164.  
  165. 	SLNode* newnode = CreateNode(x);
  166. 	SLNode* cur = pos->next;
  167. 	pos->next = newnode;
  168. 	newnode->next = cur;
  169. }
  170.  
  171. // 删除pos位置之后的值
  172. void SListEraseAfter(SLNode* pos)
  173. {
  174. 	//pos为NULL 不可删后面的
  175. 	assert(pos);
  176. 	SLNode* cur = pos->next;
  177.  
  178. 	if (cur == NULL)
  179. 	{
  180. 		free(cur);
  181. 		cur = NULL;
  182. 		pos->next = NULL;
  183. 	}
  184. 	else
  185. 	{
  186. 		SLNode* tail = cur->next;
  187. 		free(cur);
  188. 		pos->next = tail;
  189. 	}
  190. }
  191.  
  192. // 销毁
  193. void SListDestroy(SLNode* phead)
  194. {
  195. 	SLNode* cur = phead;
  196. 	SLNode* tail = cur;
  197. 	while (cur)
  198. 	{
  199. 		tail = cur;
  200. 		cur = cur->next;
  201. 		free(tail);
  202. 	}
  203. 	tail = NULL;
  204. 	phead = NULL;
  205. }
  206.  
  207.  
  208. int main()
  209. {
  210. 	SLNode* plist = NULL;
  211.  
  212. 	//尾插
  213. 	printf("开始尾插：\n");
  214. 	SListPushBank(&plist, 1);
  215. 	SListPrint(plist);//打印
  216.  
  217. 	SListPushBank(&plist, 2);
  218. 	SListPrint(plist);//打印
  219.  
  220. 	SListPushBank(&plist, 3);
  221. 	SListPrint(plist);//打印
  222.  
  223. 	SListPushBank(&plist, 4);
  224. 	SListPrint(plist);//打印
  225.  
  226. 	SListPushBank(&plist, 5);
  227. 	SListPrint(plist);//打印
  228.  
  229. 	//尾删
  230. 	printf("开始尾删：\n");
  231. 	SListPopBank(&plist);
  232. 	SListPrint(plist);//打印
  233.  
  234. 	SListPopBank(&plist);
  235. 	SListPrint(plist);//打印
  236.  
  237. 	SListPopBank(&plist);
  238. 	SListPrint(plist);//打印
  239.  
  240. 	SListPopBank(&plist);
  241. 	SListPrint(plist);//打印
  242.  
  243. 	SListPopBank(&plist);
  244. 	SListPrint(plist);//打印
  245.  
  246. 	//头插
  247. 	printf("开始头插：\n");
  248. 	SListPushFront(&plist, 7);
  249. 	SListPrint(plist);//打印
  250.  
  251. 	SListPushFront(&plist, 8);
  252. 	SListPrint(plist);//打印
  253.  
  254. 	SListPushFront(&plist, 9);
  255. 	SListPrint(plist);//打印
  256.  
  257. 	//头删
  258. 	printf("开始头删：\n");
  259. 	SListPopFront(&plist);
  260. 	SListPrint(plist);//打印
  261.  
  262. 	//SListPopFront(&plist);
  263. 	//SListPrint(plist);//打印
  264.  
  265. 	//SListPopFront(&plist);
  266. 	//SListPrint(plist);//打印
  267.  
  268. 	printf("查找节点：\n");
  269. 	SLNode* cur = SListFind(plist, 8);
  270. 	if (cur != NULL)
  271. 	{
  272. 		printf("找到了：%d \n", cur->val);
  273. 	}
  274. 	else
  275. 	{
  276. 		printf("找不到\n");
  277. 	}
  278.  
  279. 	printf("pos位置之后插入:\n");
  280. 	//pos位置之后插入
  281. 	SListInsertAfter(plist->next, 10);
  282. 	SListPrint(plist);//打印
  283. 	SListInsertAfter(plist, 6);
  284. 	SListPrint(plist);//打印
  285.  
  286. 	printf("删除pos位置之后的值：\n");
  287. 	// 删除pos位置之后的值
  288. 	SListEraseAfter(plist);
  289. 	SListPrint(plist);//打印
  290.  
  291. 	SListEraseAfter(plist);
  292. 	SListPrint(plist);//打印
  293.  
  294. 	SListEraseAfter(plist);
  295. 	SListPrint(plist);//打印
  296.  
  297. 	//销毁
  298. 	SListDestroy(plist);
  299. 	return 0;
  300. }

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

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

  

闽ICP备14008679号