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

(超详细！)【C语言】单链表的增删查改（附图解，源码）_简易单链表及其删除操作c语言程序

作者：Li_阴宅 | 2024-07-09 16:14:13

赞

踩

简易单链表及其删除操作c语言程序

单链表学习导航

一.前言

二.准备工作

1.对单链表运行原理的简单理解

2.区域化编辑

 三.SList.h头文件引用区

1.单链表节点的创建

2.单链表功能函数的声明

四.SListTest.c测试区

五.SList.c功能实现区

1.动态申请一个节点

2.单链表打印

3.单链表尾插

4.单链表头插

5.单链表尾删

6.单链表头删

7.单链表查找

8.单链表在pos(指定)位置之后插入

9.单链表在pos(指定)位置之后删除

10.销毁单链表

六.源码

1.SList.h源码

2.SList.c源码

 七.结语

一.前言

本文为我对链表学习的过程与理解，适合新手学习交流。内容如题，我将结合画图和截图带领大家更好的理解单链表结构，学习和使用它增删查改的功能。（VS2019编译器所展示）

二.准备工作

1.对单链表运行原理的简单理解

 如上图，单链表是通过结构体里面放置一个新的结构体指针的形式，使用下一个结构体的地址来找到该结构体中的数据的，链表相比于顺序表具有存储数据不连续，方便修改的特点。但单链表的缺点也很明显，只能从第一个节点开始遍历，比较局限。

2.区域化编辑

此目的是为了更好的理解代码，在前文中我也提到过，但模块化看起来清晰更有利于我们理解以及使用、修改代码。（还有美观...）

 三.SList.h头文件引用区

1.单链表节点的创建

在该文件中，我们将链表结构体定义，设置int为链表中数据的存储形式（方便展示），同时节点中增加下一个节点的地址。重定义链表方便使用该结构体。

  1. #define SLTDateType int
  2.  
  3. typedef struct SListNode
  4. {
  5. 	SLTDateType Data;
  6. 	struct SListNode* Next;
  7. }SListNode;

2.单链表功能函数的声明

在头文件中声明这些函数后直接使用即可，先列出来目标，后面咱们一一实现。

  1. // 动态申请一个节点
  2. SListNode* BuySListNode(SLTDateType x);
  3.  
  4. // 单链表打印
  5. void SListPrint(SListNode* phead);
  6.  
  7. // 单链表尾插
  8. void SListPushBack(SListNode** pplist, SLTDateType x);
  9.  
  10. // 单链表的头插
  11. void SListPushFront(SListNode** pplist, SLTDateType x);
  12.  
  13. // 单链表的尾删
  14. void SListPopBack(SListNode** pplist);
  15.  
  16. // 单链表头删
  17. void SListPopFront(SListNode** pplist);
  18.  
  19. // 单链表查找
  20. SListNode* SListFind(SListNode* plist, SLTDateType x);
  21.  
  22. // 单链表在pos位置之后插入x
  23. void SListInsertAfter(SListNode* pos, SLTDateType x);
  24.  
  25. // 单链表删除pos位置之后的值
  26. void SListEraseAfter(SListNode* pos);
  27.  
  28. // 单链表的销毁
  29. void SListDestroy(SListNode* plist);

其中，有的函数功能传入的参数为二级指针，为什么呢？因为函数传入的参数是实参的一份临时拷贝，如果传入的是一级指针，那么我们可以改变这个指针指向的数据，而如果我们想要改变这个指针的地址呢？同样的道理，我们需要一个指向这个指针的地址的指针，也就是二级指针。

四.SListTest.c测试区

该区域主要为所写功能函数的测试模块，以此来判断函数的正确性、是否完善。

  1. int main()
  2. {
  3. 	SListNode* List = NULL;
  4.  
  5. 	SListTest1(List);
  6. 	SListTest2(List);
  7. 	SListTest3(List);
  8. 	SListTest4(List);
  9. 	SListTest5(List);
  10. 	SListTest6(List);
  11. 	SListTest7(List);
  12.  
  13. 	return 0;
  14. }

类似于菜单，不过少了些富丽堂皇的界面，因为写了菜单之后很可能会影响到我们调试的效率，将功能函数实现并调试完成之后，再完成菜单界面是个更好的选择。测试区域可以自行定义，我也将在下文中结合该区域来展示函数的实现效果。

五.SList.c功能实现区

1.动态申请一个节点

链表节点的申请可以使用malloc和calloc函数，此处我们使用malloc，记得判断返回值是否为空。

  1. //动态申请链表节点
  2. SListNode* BuySListNode(SLTDateType x)
  3. {
  4. 	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
  5. 	if (newnode == NULL)
  6. 	{
  7. 		perror("BuySListNode::malloc");
  8. 		return;
  9. 	}
  10. 	newnode->Data = x;
  11. 	return newnode;
  12. }

此处还可以在返回节点之前将该节点的下一个地址置空，初始化也是种不错的选择。可以看个人需求选择。

2.单链表打印

将第一个节点传入函数，通过节点中的下一个指针一一遍历每个节点中存储的数据，并打印出来，最后节点为空时停止即可。

  1. //打印链表
  2. void SListPrint(SListNode* phead)
  3. {
  4. 	SListNode* cur = phead;
  5. 	while (cur)
  6. 	{
  7. 		printf("%d->", cur->Data);
  8. 		cur = cur->Next;
  9. 	}
  10. 	printf("NULL\n");
  11. }

3.单链表尾插

尾插需要考虑两种情况，第一种则是链表为空的情况，这种情况直接让该链表指向开辟的节点上即可；第二种情况为非空的情况，这种情况比较复杂，我们来画图解决：

 地址都是瞎编的，原理如此，代码实现如下：

  1. //尾插
  2. void SListPushBack(SListNode** pplist, SLTDateType x)
  3. {
  4.     //判断是否为空链表
  5. 	if (*pplist==NULL)
  6. 	{
  7. 		*pplist = BuySListNode(x);
  8. 		(*pplist)->Next = NULL;
  9. 	}
  10. 	else
  11. 	{
  12. 		//查找尾部
  13. 		SListNode* ptr = *pplist;
  14. 		while (ptr->Next)
  15. 		{
  16. 			ptr = ptr->Next;
  17. 		}
  18. 		//插入
  19. 		ptr->Next = BuySListNode(x);
  20. 		ptr->Next->Next = NULL;
  21. 	}
  22. }

结合打印链表函数效果如图：

4.单链表头插

头插的实现和尾插一样，分空链表和非空链表两种情况。二者区别在于非空情况，头插演示如图：

原来没有头插的非空链表，pplist指向头节点的地址。

插入头节点的非空链表演示如上图，代码实现如下图。

  1. //头插
  2. void SListPushFront(SListNode** pplist, SLTDateType x)
  3. {
  4. 	if (*pplist == NULL)
  5. 	{
  6. 		*pplist = BuySListNode(x);
  7. 		(*pplist)->Next = NULL;
  8. 	}
  9. 	else
  10. 	{
  11. 		SListNode* ptr = BuySListNode(x);
  12. 		ptr->Next = *pplist;
  13. 		*pplist = ptr;
  14. 	}
  15. }

实现效果如图：

5.单链表尾删

尾删分为三种情况：

第一种为链表是否为空，若为空，可以选择报错也可以选择直接return（没有内容咋删...）；

第二种为链表不为空，但只有一个节点的情况，这种情况我们需要直接将链表置空；

第三中为多节点的情况，这时我们要将NULL节点之前的节点置空，其中需要NULL节点前前个节点来判断，因为还要free掉不要用的内存，该情况如下图所示。

具体实现如下：

  1. //尾删
  2. void SListPopBack(SListNode** pplist)
  3. {
  4. 	assert(pplist);
  5. 	assert(*pplist);
  6. 	
  7. 	if ((*pplist)->Next == NULL)
  8. 	{
  9. 		//单个链表块
  10. 		free(*pplist);
  11. 		*pplist = NULL;
  12. 	}
  13. 	else
  14. 	{
  15. 		//2个及以上链表块
  16. 		SListNode* ptr = *pplist;
  17. 		while (ptr->Next->Next)
  18. 		{
  19. 			ptr = ptr->Next;
  20. 		}
  21. 		free(ptr->Next);
  22. 		ptr->Next = NULL;
  23. 	}
  24. }

效果如下：

6.单链表头删

头删只需要考虑两种情况就行了。

第一种为判断链表是否为空；

第二种不论是否为多节点，指向头节点地址的指针都会向后移动到下一个节点的地址上，因此不需要考虑这下一个节点是否为空。

 代码实现如下：

  1. //头删
  2. void SListPopFront(SListNode** pplist)
  3. {
  4. 	assert(pplist);
  5. 	assert(*pplist);
  6.  
  7. 	SListNode* Del = *pplist;
  8. 	*pplist = (*pplist)->Next;
  9. 	free(Del);
  10. 	Del = NULL;
  11. }

具体效果如图：

7.单链表查找

查找目标节点并返回该节点的地址，传值选用一级指针就行了，因为有返回值为一级指针，这类函数的方法也可以代替上面的二级指针的使用（个人觉得这样不好看）。

查找需要遍历，除非找到目标节点，否则到NULL为止停下，直接返回查找节点即可。

  1. //查找
  2. SListNode* SListFind(SListNode* plist, SLTDateType x)
  3. {
  4. 	SListNode* find = plist;
  5. 	while (find && find->Data != x)
  6. 		find = find->Next;
  7. 	return find;
  8. }

实现效果如图：

8.单链表在pos(指定)位置之后插入

这个函数和头插函数多节点的情况很像，不过该函数不需要改变头节点指针的位置，因此传入一级指针即可。

插入前需判断是否传入的为空指针，然后插入就行啦，不过写入的顺序要正确，否则可能会丢失原先的地址哦？

  1. //在pos位置之后插入x
  2. void SListInsertAfter(SListNode* pos, SLTDateType x)
  3. {
  4. 	assert(pos);
  5. 	SListNode* next = pos->Next;
  6.  
  7. 	SListNode* newnode = BuySListNode(x);
  8. 	pos->Next = newnode;
  9. 	newnode->Next = next;
  10. }

效果如下：

9.单链表在pos(指定)位置之后删除

这个函数还比较简单，注意传值是否为空指针和指向的下一节点是否为空就行了。

没有判断后者的话可是会非法访问的...不得不说链表对于初学者而言坑太多了。

  1. //删除pos位置之后的值
  2. void SListEraseAfter(SListNode* pos)
  3. {
  4. 	assert(pos);
  5. 	if (pos->Next == NULL)
  6. 		return;
  7. 	else
  8. 	{
  9. 		SListNode* NNext = pos->Next->Next;
  10. 		free(pos->Next);
  11. 		pos->Next = NNext;
  12. 	}
  13. }

实现效果如下：

10.销毁单链表

类似于顺序表的销毁，不同的是需要free掉前者，且遍历的是链表节点的指针。

  1. //销毁
  2. void SListDestroy(SListNode* plist)
  3. {
  4. 	assert(plist);
  5. 	SListNode* Del = plist;
  6. 	while (Del)
  7. 	{
  8. 		plist = plist->Next;
  9. 		free(Del);
  10. 		Del = plist;
  11. 	}
  12. }

六.源码

1.SList.h源码

  1. #pragma once
  2.  
  3. #include <stdio.h>
  4. #include <assert.h>
  5. #include <stdlib.h>
  6.  
  7. #define int SLTDateType 
  8.  
  9. typedef struct SListNode
  10. {
  11. 	SLTDateType Data;
  12. 	struct SListNode* Next;
  13. }SListNode;
  14.  
  15. // 动态申请一个节点
  16. SListNode* BuySListNode(SLTDateType x);
  17.  
  18. // 单链表打印
  19. void SListPrint(SListNode* phead);
  20.  
  21. // 单链表尾插
  22. void SListPushBack(SListNode** pplist, SLTDateType x);
  23.  
  24. // 单链表的头插
  25. void SListPushFront(SListNode** pplist, SLTDateType x);
  26.  
  27. // 单链表的尾删
  28. void SListPopBack(SListNode** pplist);
  29.  
  30. // 单链表头删
  31. void SListPopFront(SListNode** pplist);
  32.  
  33. // 单链表查找
  34. SListNode* SListFind(SListNode* plist, SLTDateType x);
  35.  
  36. // 单链表在pos位置之后插入x
  37. void SListInsertAfter(SListNode* pos, SLTDateType x);
  38.  
  39. // 单链表删除pos位置之后的值
  40. void SListEraseAfter(SListNode* pos);
  41.  
  42. // 单链表的销毁
  43. void SListDestroy(SListNode* plist);

2.SList.c源码

  1. #include "SList.h"
  2.  
  3. //动态申请链表节点
  4. SListNode* BuySListNode(SLTDateType x)
  5. {
  6. 	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
  7. 	if (newnode == NULL)
  8. 	{
  9. 		perror("BuySListNode::malloc");
  10. 		return;
  11. 	}
  12. 	newnode->Data = x;
  13. 	return newnode;
  14. }
  15.  
  16. //打印链表
  17. void SListPrint(SListNode* phead)
  18. {
  19. 	SListNode* cur = phead;
  20. 	while (cur)
  21. 	{
  22. 		printf("%d->", cur->Data);
  23. 		cur = cur->Next;
  24. 	}
  25. 	printf("NULL\n");
  26. }
  27.  
  28. //尾插
  29. void SListPushBack(SListNode** pplist, SLTDateType x)
  30. {
  31. 	if (*pplist==NULL)
  32. 	{
  33. 		*pplist = BuySListNode(x);
  34. 		(*pplist)->Next = NULL;
  35. 	}
  36. 	else
  37. 	{
  38. 		//查找尾部
  39. 		SListNode* ptr = *pplist;
  40. 		while (ptr->Next)
  41. 		{
  42. 			ptr = ptr->Next;
  43. 		}
  44. 		//插入
  45. 		ptr->Next = BuySListNode(x);
  46. 		ptr->Next->Next = NULL;
  47. 	}
  48. }
  49.  
  50. //头插
  51. void SListPushFront(SListNode** pplist, SLTDateType x)
  52. {
  53. 	assert(pplist);
  54. 	if (*pplist == NULL)
  55. 	{
  56. 		*pplist = BuySListNode(x);
  57. 		(*pplist)->Next = NULL;
  58. 	}
  59. 	else
  60. 	{
  61. 		SListNode* ptr = BuySListNode(x);
  62. 		ptr->Next = *pplist;
  63. 		*pplist = ptr;
  64. 	}
  65. }
  66.  
  67. //尾删
  68. void SListPopBack(SListNode** pplist)
  69. {
  70. 	assert(pplist);
  71. 	assert(*pplist);
  72. 	
  73. 	if ((*pplist)->Next == NULL)
  74. 	{
  75. 		//单个链表块
  76. 		free(*pplist);
  77. 		*pplist = NULL;
  78. 	}
  79. 	else
  80. 	{
  81. 		//2个及以上链表块
  82. 		SListNode* ptr = *pplist;
  83. 		while (ptr->Next->Next)
  84. 		{
  85. 			ptr = ptr->Next;
  86. 		}
  87. 		free(ptr->Next);
  88. 		ptr->Next = NULL;
  89. 	}
  90. }
  91.  
  92. //头删
  93. void SListPopFront(SListNode** pplist)
  94. {
  95. 	assert(pplist);
  96. 	assert(*pplist);
  97.  
  98. 	SListNode* Del = *pplist;
  99. 	*pplist = (*pplist)->Next;
  100. 	free(Del);
  101. 	Del = NULL;
  102. }
  103.  
  104. //查找
  105. SListNode* SListFind(SListNode* plist, SLTDateType x)
  106. {
  107. 	SListNode* find = plist;
  108. 	while (find && find->Data != x)
  109. 		find = find->Next;
  110. 	return find;
  111. }
  112.  
  113. //在pos位置之后插入x
  114. void SListInsertAfter(SListNode* pos, SLTDateType x)
  115. {
  116. 	assert(pos);
  117. 	SListNode* next = pos->Next;
  118.  
  119. 	SListNode* newnode = BuySListNode(x);
  120. 	pos->Next = newnode;
  121. 	newnode->Next = next;
  122. }
  123.  
  124. //删除pos位置之后的值
  125. void SListEraseAfter(SListNode* pos)
  126. {
  127. 	assert(pos);
  128. 	if (pos->Next == NULL)
  129. 		return;
  130. 	else
  131. 	{
  132. 		SListNode* NNext = pos->Next->Next;
  133. 		free(pos->Next);
  134. 		pos->Next = NNext;
  135. 	}
  136. }
  137.  
  138. //销毁
  139. void SListDestroy(SListNode* plist)
  140. {
  141. 	assert(plist);
  142. 	SListNode* Del = plist;
  143. 	while (Del)
  144. 	{
  145. 		plist = plist->Next;
  146. 		free(Del);
  147. 		Del = plist;
  148. 	}
  149. }

 七.结语

链表内容对于新手而言还是比较多的，坑也是无处不在，需要诸位的细心与耐心，除了单链表还有很多其他形式的，不过都大同小异，自己多手搓几遍就能弄清楚了，总之，我会和各位一起加油的！

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

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

  

闽ICP备14008679号