经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » 程序设计 » C 语言 » 查看文章
C语言中单链表(不带头结点)基本操作的实现详解
来源：jb51　　时间：2022/11/17 8:48:31　　对本文有异议

通过对顺序表的学习，我们可以发现顺序表有以下几点缺陷：

1.空间不够时需要扩容，扩容尤其是用realloc进行异地扩容时，是有一定代价的，其次还可能存在一定空间浪费。

2.头部或者中间插入删除，需要挪动数据，效率低下。

那我们可以对其所具有的缺陷进行优化：可以按需申请空间同时插入删除时不挪动数据。而单链表就符合这些优化所具有特点。但是我们要注意的是单链表具有这些优点并不代表链表就可以完全替代顺序表。

一、单链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

从上图可以看出，链式结构在逻辑上是连续的，但是在物理上不一定连续，物理结构中指针域存储的是下一个结点的地址；而且链式结构的结点一般都是从堆上申请出来的；从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。链表存储数据的区域可分为数据域和指针域：

用代码表示链表中的数据域和指针域如下：

  1. typedef int STLDataType;
  2. typedef struct SListNode
  3. {
  4.     SLTDataType data;
  5.     struct SListNode* next;
  6. }STLNode;

思考：为什么在申请的时候需要申请堆上的空间？因为堆上申请的空间存储数据的时候不会因为函数销毁而销毁，堆上的空间需要的时候就申请，不需要的时候就释放；函数栈帧上开辟的空间存储的数据会因为函数栈帧的销毁而释放，后面在进行尾插和头插时候新的结点不能链接到表上。

二、单链表的基本操作

1.创建单个结点

  1. SLTNode* BuySLTNode(SLTDataType x)
  2. {
  3.     SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  4.     if (newnode == NULL)
  5.     {
  6.         perror("BuySLTNode malloc");
  7.         exit(-1);
  8.     }
  9.     newnode->val = x;
  10.     newnode->next = NULL;
  11.     return newnode;
  12. }

2.创建具有n个结点的链表

  1. SLTNode* CreateSList(int n)
  2. {
  3.     int i = 0;
  4.     SLTNode* ptail = NULL,*phead = NULL;
  5.     for (i = 0; i < n; i++)
  6.     {
  7.         SLTNode* newnode = BuySLTNode(i);
  8.         if (phead == NULL)
  9.         {
  10.             ptail = phead = newnode;
  11.         }
  12.         else
  13.         {
  14.             ptail->next = newnode;
  15.             ptail = newnode;
  16.         }
  17.     }
  18.     return phead;
  19. }
  20. //void CreateSList(SLTNode** pphead, int n)
  21. //{
  22. //    int i = 0;
  23. //    SLTNode* ptail = NULL;
  24. //    for (i = 0; i < n; i++)
  25. //    {
  26. //        SLTNode* newnode = BuySLTNode(i);
  27. //        if (*pphead == NULL)
  28. //        {
  29. //            ptail = *pphead = newnode;
  30. //        }
  31. //        else
  32. //        {
  33. //            ptail->next= newnode;
  34. //            ptail = newnode;
  35. //        }
  36. //    }
  37. //}

上述代码中提供了两种实现方式，没有注释的是返回头指针的，注释内容是没有返回值，形参使用的是二级指针改变头指针指向的地址。

3.打印单链表

  1. void SLTPrint(SLTNode* phead)
  2. {
  3.     SLTNode* tail = phead;
  4.     while (tail)
  5.     {
  6.         printf("%d ", tail->val);
  7.         tail = tail->next;
  8.     }
  9.     printf("\n");
  10. }

4.尾插

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

尾插时，要注意当单链表的头结点为空的时候，要先将新结点作为头结点。因为当头结点为空时，需要改变头指针，所以传过来的为二级指针（也可以使用一级指针，不过此时要有返回值），要想改变SLTNode*的值，就要传递它的地址即SLTNode**类型。

5.尾删

  1. void SLTPopBack(SLTNode** pphead)//尾删
  2. {
  3.     assert(*pphead);
  4.     if ((*pphead)->next==NULL)
  5.     {
  6.         free(*pphead);
  7.         *pphead = NULL;
  8.     }
  9.     else
  10.     {
  11.         SLTNode* tail = *pphead;
  12.         SLTNode* prev = NULL;
  13.         while (tail->next)
  14.         {
  15.             prev = tail;
  16.             tail = tail->next;
  17.         }
  18.         free(tail);
  19.         prev->next = NULL;
  20.     }
  21. }

尾删时也要注意区分是否为头结点；同时注意删除后，要将其置空prev->next = NULL。

6.头插

  1. void SLTPushFront(SLTNode** pphead, SLTDataType x)//头插
  2. {
  3.     SLTNode* newnode = BuySLTNode(x);
  4.     newnode->next = *pphead;
  5.     *pphead = newnode;
  6. }

7.头删

  1. void SLTPopFront(SLTNode** pphead)//头删
  2. {
  3.     assert(*pphead);
  4.     SLTNode* nextnode = (*pphead)->next;
  5.     free(*pphead);
  6.     *pphead = nextnode;
  7. }

头插和头删是单链表的优势，尾插和尾删是顺序表的优势。同时在尾删时注意将*pphead加上括号用来区分优先级，否则会报错。

8.查找某个结点

  1. SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找某个数并返回所在位置
  2. {
  3.     SLTNode* tail = phead;
  4.     while (tail)
  5.     {
  6.         if (tail->val == x)
  7.         {
  8.             return tail;
  9.         }
  10.         tail = tail->next;
  11.     }
  12.     return NULL;
  13. }

注意循环条件，当循环条件写为while(tail->next)时，会有空指针的风险，同时还会漏掉最后一个结点。

9.在某个结点后面插入

  1. void SLInsertAfter(SLTNode* pos, SLTDataType x)//在某个结点的后面插入某个数
  2. {
  3.     assert(pos);
  4.     SLTNode* newnode = BuySLTNode(x);
  5.     SLTNode* tail = pos->next;
  6.     pos->next = newnode;
  7.     newnode->next = tail;
  8. }

10.在某个结点前面插入

  1. void SLTInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x)//在某个结点的前面插入某个数
  2. {
  3.     assert(pos);
  4.     SLTNode* newnode = BuySLTNode(x);
  5.     if (pos == *pphead)
  6.     {
  7.         /*newnode->next = *pphead;
  8.         *pphead = newnode;*/
  9.         SLTPushBack(pphead, x);
  10.     }
  11.     else
  12.     {
  13.         SLTNode* tail = *pphead;
  14.         while (tail->next != pos)
  15.         {
  16.             tail = tail->next;
  17.         }
  18.         tail->next = newnode;
  19.         newnode->next = pos;
  20.     }
  21. }

11.删除某个位置后面的结点

  1. void SLTEraseAfter(SLTNode* pos)//删除pos位置之后的那个位置
  2. {
  3.     assert(pos);
  4.     if (pos->next == NULL)
  5.     {
  6.         return;
  7.     }
  8.     else
  9.     {
  10.         SLTNode* tail = pos->next;
  11.         pos->next = tail->next;
  12.         free(tail);
  13.     }
  14. }

12.删除某个结点

  1. void SLTErase(SLTNode** pphead, SLTNode* pos)//删除pos位置
  2. {
  3.     assert(pos);
  4.     SLTNode* tail = *pphead;
  5.     if (pos == *pphead)
  6.     {
  7.         SLTNode* nextNode = (*pphead)->next;
  8.         free(*pphead);
  9.         *pphead = nextNode;
  10.     }
  11.     else
  12.     {
  13.         while (tail->next != pos)
  14.         {
  15.             tail = tail->next;
  16.         }
  17.         tail->next = pos->next;
  18.         free(pos);
  19.     }
  20. }

13.销毁单链表

  1. void SLTDestroy(SLTNode** pphead)//销毁
  2. {
  3.     assert(*pphead);
  4.     SLTNode* tail = *pphead;
  5.     
  6.     while (tail)
  7.     {
  8.         SLTNode* next = tail->next;
  9.         free(tail);
  10.         tail = next;
  11.     }
  12.     *pphead = NULL;
  13. }

注意最后要将头结点置空。

三、测试代码

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <assert.h>
  5. typedef int SLTDataType;
  6. typedef struct SList {
  7. 	struct Slist* next;
  8. 	SLTDataType val;
  9. }SLTNode;
  10. SLTNode* BuySLTNode(SLTDataType x)
  11. {
  12. 	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  13. 	if (newnode == NULL)
  14. 	{
  15. 		perror("BuySLTNode malloc");
  16. 		exit(-1);
  17. 	}
  18. 	newnode->val = x;
  19. 	newnode->next = NULL;
  20. 	return newnode;
  21. }
  22. SLTNode* CreateSList(int n)
  23. {
  24. 	int i = 0;
  25. 	SLTNode* ptail = NULL, * phead = NULL;
  26. 	for (i = 0; i < n; i++)
  27. 	{
  28. 		SLTNode* newnode = BuySLTNode(i);
  29. 		if (phead == NULL)
  30. 		{
  31. 			ptail = phead = newnode;
  32. 		}
  33. 		else
  34. 		{
  35. 			ptail->next = newnode;
  36. 			ptail = newnode;
  37. 		}
  38. 	}
  39. 	return phead;
  40. }
  41. //void CreateSList(SLTNode** pphead, int n)
  42. //{
  43. //	int i = 0;
  44. //	SLTNode* ptail = NULL;
  45. //	for (i = 0; i < n; i++)
  46. //	{
  47. //		SLTNode* newnode = BuySLTNode(i);
  48. //		if (*pphead == NULL)
  49. //		{
  50. //			ptail = *pphead = newnode;
  51. //		}
  52. //		else
  53. //		{
  54. //			ptail->next= newnode;
  55. //			ptail = newnode;
  56. //		}
  57. //	}
  58. //}
  59. void SLTPrint(SLTNode* phead)
  60. {
  61. 	SLTNode* tail = phead;
  62. 	while (tail)
  63. 	{
  64. 		printf("%d ", tail->val);
  65. 		tail = tail->next;
  66. 	}
  67. 	printf("\n");
  68. }
  69. void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
  70. {
  71. 	SLTNode* tail = *pphead;
  72. 	SLTNode* newnode = BuySLTNode(x);
  73. 	if (*pphead == NULL)
  74. 	{
  75. 		*pphead = newnode;
  76. 	}
  77. 	else
  78. 	{
  79. 		while (tail->next)
  80. 		{
  81. 			tail = tail->next;
  82. 		}
  83. 		tail->next = newnode;
  84. 	}
  85. }
  86. void SLTPopBack(SLTNode** pphead)//尾删
  87. {
  88. 	assert(*pphead);
  89. 	if ((*pphead)->next == NULL)
  90. 	{
  91. 		free(*pphead);
  92. 		*pphead = NULL;
  93. 	}
  94. 	else
  95. 	{
  96. 		SLTNode* tail = *pphead;
  97. 		SLTNode* prev = NULL;
  98. 		while (tail->next)
  99. 		{
  100. 			prev = tail;
  101. 			tail = tail->next;
  102. 		}
  103. 		free(tail);
  104. 		prev->next = NULL;
  105. 	}
  106. }
  107. void SLTPushFront(SLTNode** pphead, SLTDataType x)//头插
  108. {
  109. 	SLTNode* newnode = BuySLTNode(x);
  110. 	newnode->next = *pphead;
  111. 	*pphead = newnode;
  112. }
  113. void SLTPopFront(SLTNode** pphead)//头删
  114. {
  115. 	assert(*pphead);
  116. 	SLTNode* nextnode = (*pphead)->next;
  117. 	free(*pphead);
  118. 	*pphead = nextnode;
  119. }
  120. SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找某个数并返回所在位置
  121. {
  122. 	SLTNode* tail = phead;
  123. 	while (tail)
  124. 	{
  125. 		if (tail->val == x)
  126. 		{
  127. 			return tail;
  128. 		}
  129. 		tail = tail->next;
  130. 	}
  131. 	return NULL;
  132. }
  133. void SLInsertAfter(SLTNode* pos, SLTDataType x)//在某个结点的后面插入某个数
  134. {
  135. 	assert(pos);
  136. 	SLTNode* newnode = BuySLTNode(x);
  137. 	SLTNode* tail = pos->next;
  138. 	pos->next = newnode;
  139. 	newnode->next = tail;
  140. }
  141. void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)//在某个结点的前面插入某个数
  142. {
  143. 	assert(pos);
  144. 	SLTNode* newnode = BuySLTNode(x);
  145. 	if (pos == *pphead)
  146. 	{
  147. 		/*newnode->next = *pphead;
  148. 		*pphead = newnode;*/
  149. 		SLTPushBack(pphead, x);
  150. 	}
  151. 	else
  152. 	{
  153. 		SLTNode* tail = *pphead;
  154. 		while (tail->next != pos)
  155. 		{
  156. 			tail = tail->next;
  157. 		}
  158. 		tail->next = newnode;
  159. 		newnode->next = pos;
  160. 	}
  161. }
  162. void SLTEraseAfter(SLTNode* pos)//删除pos位置之后的那个位置
  163. {
  164. 	assert(pos);
  165. 	if (pos->next == NULL)
  166. 	{
  167. 		return;
  168. 	}
  169. 	else
  170. 	{
  171. 		SLTNode* tail = pos->next;
  172. 		pos->next = tail->next;
  173. 		free(tail);
  174. 	}
  175. }
  176. void SLTErase(SLTNode** pphead, SLTNode* pos)//删除pos位置
  177. {
  178. 	assert(pos);
  179. 	SLTNode* tail = *pphead;
  180. 	if (pos == *pphead)
  181. 	{
  182. 		SLTNode* nextNode = (*pphead)->next;
  183. 		free(*pphead);
  184. 		*pphead = nextNode;
  185. 	}
  186. 	else
  187. 	{
  188. 		while (tail->next != pos)
  189. 		{
  190. 			tail = tail->next;
  191. 		}
  192. 		tail->next = pos->next;
  193. 		free(pos);
  194. 	}
  195. }
  196. void SLTDestroy(SLTNode** pphead)//销毁
  197. {
  198. 	assert(*pphead);
  199. 	SLTNode* tail = *pphead;
  200.  
  201. 	while (tail)
  202. 	{
  203. 		SLTNode* next = tail->next;
  204. 		free(tail);
  205. 		tail = next;
  206. 	}
  207. 	*pphead = NULL;
  208. }
  209. void TestSL()
  210. {
  211. 	SLTNode* plist = CreateSList(2);
  212. 	/*SLTNode* plist = NULL;
  213. 	CreateSList(&plist,10);//没有返回值
  214. 	SLTPrint(plist);*/
  215. 	SLTPushBack(&plist, 600);
  216. 	SLTPushBack(&plist, 200);
  217. 	SLTPushBack(&plist, 300);
  218. 	SLTPushBack(&plist, 400);
  219. 	SLTPrint(plist);
  220.  
  221. 	SLTPopBack(&plist);
  222. 	SLTPopBack(&plist);
  223. 	SLTPopBack(&plist);
  224. 	SLTPrint(plist);
  225.  
  226. 	SLTPushFront(&plist, 100);
  227. 	SLTPushFront(&plist, 200);
  228. 	SLTPushFront(&plist, 300);
  229. 	SLTPushFront(&plist, 400);
  230. 	SLTPrint(plist);
  231.  
  232. 	SLTPopFront(&plist);
  233. 	SLTPopFront(&plist);
  234. 	SLTPrint(plist);
  235. 	SLTNode* pos = SLTFind(plist, 600);
  236. 	if (pos)
  237. 	{
  238. 		SLInsertAfter(pos, 700);
  239. 		SLTInsert(&plist, pos, 500);
  240. 		SLTEraseAfter(pos);
  241. 		//SLTErase(&plist, pos);
  242.  
  243. 	}
  244. 	SLTPrint(plist);
  245. 	SLTDestroy(&plist);
  246. 	SLTPrint(plist);
  247. }
  248. int main()
  249. {
  250. 	TestSL();
  251. 	return 0;
  252. }

以上就是C语言中单链表(不带头结点)基本操作的实现详解的详细内容，更多关于C语言单链表的资料请关注w3xue其它相关文章！

 友情链接：直通硅谷 　点职佳 　北美留学生论坛

C 语言热门文章

  • 图形学入门(1)——直线生成算法（DDA和Bresenham）
  • 用C语言制作一个最简单的飞机游戏！
  • MODBUS 超时时间计算
  • zabbix wait for 15s seconds 出现原因及调优建议
  • C/C++知识分享：assert()函数
  • 图形学入门(2)——圆弧生成算法（中点画圆法）
  • C 共享内存封装
  • C语言中break与continue的用法和区别详解
  • GStreamer基础教程09 - Appsrc及Appsink
  • 三元组矩阵行列式的计算（用递归）

    • C 语言推荐文章

  • C语言指针易混淆知识点总结
  • 进程间通信
  • 数组降维、函数栈帧、地址空间、可变参数原理剖析
  • 【Learning eBPF-3】一个 eBPF 程序的深入剖析
  • [apue] 进程控制那些事儿
  • 解密C语言选择结构：掌握条件语句与分支逻辑的利器
  • 精通C语言：打造高效便捷的通讯录管理系统
  • c语言实现内存池
  • [数据结构] 数组与特殊矩阵
  • 探索C语言结构体：编程中的利器与艺术

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号