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

【数据结构初阶】三、 线性表里的链表（无头+单向+非循环链表 -- C语言实现）_无头结点链表

作者：Monodyee | 2024-06-04 03:06:10

赞

踩

无头结点链表

=========================================================================

相关代码gitee自取：

C语言学习日记: 加油努力 (gitee.com)

 =========================================================================

接上期：

【数据结构初阶】二、 线性表里的顺序表（C语言实现顺序表）-CSDN博客

 =========================================================================

                   

引言

通过上期对顺序表的介绍和使用

我们可以知道顺序表有以下优点和缺点：

            

顺序表优点

                  

  • 尾插 和 尾删 操作足够快
                   
  • 能够使用下标的随机访问和修改，这是很方便的

            

-----------------------------------------------------------------------------------------------

            

顺序表缺点

                  

  • 头部/中间的插入和删除操作较慢，时间复杂度为O(N)
                              
  • 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
                         
  • 增容一般是呈2倍的增长，势必会有一定的空间浪费。
    例如：
    当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，
    后面没有数据插入了，那么就浪费了95个数据空间。

            

            

下面将要介绍和实现的链表就不会出现这些问题

         

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

             

1 . 链表

（1）. 链表的概念及结构：

           

链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构，

数据元素的逻辑顺序是通过链表中的指针链接次序实现的，
单链表一般不会单独使用，
只有头插和头删实现简单且效率高

              

链表的结构

  • 链表也属于线性表，线性表在物理上存储时，
    通常以数组（顺序表）和链式结构（链表）的形式存储，
    链式结构在逻辑上是连续的，但在物理上不一定连续
                     
  • 现实中的结点一般是从堆上申请出来的
                  
  • 从堆上申请的空间，是按照一定的策略来分配的，
    两次申请的空间可能连续，也可能不连续
图示：

                     

                    

（2）. 链表的分类：

            

实际中链表的结构非常多样，
以下情况组合起来就有8种链表结构：

           

单向 或 双向 链表

单向链表图示

                

双向链表图示

            

            

---------------------------------------------------------------------------------------------

            

带头(哨兵位) 或 不带头(哨兵位) 链表

带头链表图示

               

不带头链表图示

            

            

---------------------------------------------------------------------------------------------

            

循环 或 非循环 链表

循环链表图示

                  

非循环链表图示

            

            

虽然有这么多的链表的结构，
但是我们实际中最常用还是两种结构：

无头单向非循环链表 和 带头双向循环链表

                     

                    

（3）. 两种常用链表结构：

            

无头单向非循环链表

简介：

结构简单，一般不会单独用来存数据。

实际中更多是作为其他数据结构的子结构，

如哈希桶、图的邻接表等等。

另外这种结构在笔试面试中出现很多。

          

图示：

            

            

---------------------------------------------------------------------------------------------

            

带头双向循环链表

简介：

结构最复杂，一般用在单独存储数据。

实际中使用的链表数据结构，都是带头双向循环链表。

另外这个结构虽然结构复杂，

但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了

          

图示：

         

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

             

2 . 链表的实现
（无头+单向+非循环链表）

（详细解释在图片的注释中，代码分文件放最后）

                  

实现具体功能前的准备工作

  • 创建单链表数据类型 -- 链表结点中数据域里存储的数据的类型
                    
  • 创建单链表结点结构体(类型) -- 结点中应有 数据域 和 指针域
图示

            

            

---------------------------------------------------------------------------------------------

            

PrintSList函数 -- 遍历打印链表

  • 需要使用到链表头指针phead，为了后续使用又不能改变头指针，所以要代替头指针
                     
  • 因为链表到最后结点里指针域的NULL(0x00000000)才结束，
    所以可以使用while循环进行遍历并打印
                  
  • 最后提示已指向NULL指针链表，遍历结束
图示

            

            

---------------------------------------------------------------------------------------------

            

SLTNode函数 -- 生成链表的结点

  • 开辟结点所需的动态空间，要注意一个结点大小要看数据域和指针域的大小
               
  • 检查空间是否开辟成功
               
  • 将要放入结点数据域的数据放入
               
  • 设置新创建结点的指针域
               
  • 返回创建的新结点的指针（地址）
图示

测试 -- PrintSList、SLTNode函数

            

            

---------------------------------------------------------------------------------------------

            

SLTPushBack函数（难） -- 向链表尾部插入一个结点（尾插）

  • 因为要插入一个结点，所以先使用BuySListNode函数创建一个结点
               
  • 尾插时要判断链表是否已经有结点，
    如果没有结点，
    则将新创建结点的地址赋给头指针，
    因为是对指针本身进行操作，所以用二级指针对头指针进行操作
               
  • 如果已经有了结点，
    则先创建一个指针替代头指针，
    （这里是对头指针直线的结点结构体进行操作，所以用指针就够了，不需要二级指针）
    再使用while循环获得最后一个结点的地址，
    最后将尾插的结点连接起来
图示

（可以结合单链表物理图来理解）

↓↓↓↓

测试 -- SLTPushBack函数

            

            

---------------------------------------------------------------------------------------------

            

SLTPushFront函数 -- 向链表头部插入一个结点（头插）

  • 因为要插入一个结点，所以先使用BuySListNode函数创建一个结点
               
  • 使用plist把原本头结点地址赋给新插入头结点指针域
               
  • 再把头指针改为指向新插入头结点
图示

测试 -- SLTPushFront函数

            

            

---------------------------------------------------------------------------------------------

            

SLTPopBack函数 -- 删除链表尾部结点（尾删）

  • 链表尾删要考虑三种情况：
    第一种情况：链表为空，没有任何结点
    这种情况直接assert断言即可
               
  • 第二种情况：链表只有一个结点
    这种情况要释放掉唯一的结点
               
  • 第三种情况：链表有一个以上结点
    这种情况需要两个指针来进行操作
图示

测试 -- SLTPopBack函数

            

            

---------------------------------------------------------------------------------------------

            

SLTPopFront函数 -- 删除链表头部结点（头删）

  • 头删分两种情况就够了：空链表 和 非空链表
               
  • 空链表头删：
    直接assert断言pass掉
    （莫名戳中笑点哈哈哈哈哈哈哈哈）
               
  • 非空链表头删：
    先通过plist头指针获得第二个结点地址，方便头删后让原本的第二个结点做新的头结点
    再free释放掉头指针，
    最后让plist头指针指向原本的第二个结点做新的头结点
图示

测试 -- SLTPopFront函数

            

            

---------------------------------------------------------------------------------------------

            

SLTFind函数 -- 查找指定值(x)所在结点的地址

  • 创建一个变量代替头指针
               
  • 使用while循环在链表中进行遍历，查找指定值(x)
图示

测试 -- SLTFind函数

            

            

---------------------------------------------------------------------------------------------

            

SLTInsert函数 -- 在链表指定位置(pos)之前插入一个值(x)

  • 分三种情况讨论：
    链表为空(空链表)、在第一个结点前插入(头插)、非头插
               
  • 链表为空：
    直接assert断言pass掉
               
  • 在第一个结点前插入(头插)：
    复用头插SLTPushFront函数进行插入
               
  • 非头插：
    使用链表头指针找到pos结点的前一个结点地址prev
  • 再创建一个新结点newnode
    将新结点newnode插入pos结点之前，prev结点之后
图示

测试 -- SLTInsert函数

            

            

---------------------------------------------------------------------------------------------

            

SLTInsertAfter函数 -- 在链表指定位置(pos)之后插入一个值(x)

  • 如果接收的pos结点地址为空，无法继续操作
    要用assert断言继续处理
               
  • 因为要在链表中插入一个值，
    所以要用BuySListNode函数新增一个结点
               
  • 先让newnode结点的指针域next指向后一个结点
               
  • 再让pos结点指向newnode结点，
    将链表连接起来
图示

测试 -- SLTInsertAfter函数

            

            

---------------------------------------------------------------------------------------------

            

SLTErase函数 -- 在链表删除指定位置(pos)结点

  • 为防止要删的pos结点指针为空指针，
    使用assert断言
               
  • 分两种情况：
    头删 和 非头删
               
  • 头删：
    直接复用头删SLTPopFront函数
               
  • 非头删：
    找到pos结点的前一个结点prev，
    将 prev结点 和 pos结点后一个结点 连接起来
               
  • 最后释放(删除)pos结点完成删除操作
图示

测试 -- SLTErase函数

            

            

---------------------------------------------------------------------------------------------

            

SLTEraseAfter函数 -- 在链表删除指定位置(pos)之后一个结点

  • 先使用assert断言分别排除pos结点指针为空和pos结点为尾结点的情况，
    我们是删除pos结点的后一个结点，
    如果pos为尾结点，就会无法操作
               
  • 将要删除的pos结点下个结点posNext地址先保存起来
               
  • 再把pos结点和下下个结点连接起来
               
  • 最后释放（删除）posNext结点
图示

测试 -- SLTEraseAfter函数

            

            

---------------------------------------------------------------------------------------------

            

SLTDestroy函数 -- 销毁链表释放开辟的动态空间

  • 因为链表释放后，还要把头指针plist给置为空，
    要操作到plist，所以要用到二级指针
               
  • 进行assert断言，
    pphead二级指针不为空
    （以上函数中参数带二级指针pphead的都需要进行此操作）
               
  • 创建一个指针进行遍历释放空间
               
  • 最后将链表头指针置为空
图示

         

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

             

3 . 对应代码

SList.h -- 单链表头文件

  1. //链表头文件：
  2. #pragma once
  3.  
  4. //先包含之后要用到的头文件：
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <assert.h>
  8.  
  9.  
  10. //重命名一个单链表数据类型
  11. typedef int SLTDataType;
  12. //SLT -- single link table
  13.  
  14. //创建一个单链表结点结构体 
  15. //这里数据域是int类型4字节，指针域指针也是4个字节，
  16. //所以一个结点就是8个字节
  17. typedef struct SListNode
  18. {
  19. 	//结点数据域：
  20. 	SLTDataType data;
  21.  
  22. 	//结点指针域：
  23. 	//因为是指向单链表结点结构体的指针，
  24. 	//所以是单链表结点结构体类型的指针
  25. 	struct SListNode* next;
  26. 	//第一个结点要找到第二个结点，物理空间不连续
  27. 	//通过上个结点指向下个结点，实现逻辑连续
  28.  
  29. }SLTNode; //将struct SListNode重命名为SLTNode
  30.  
  31.  
  32. //创建遍历打印单链表的函数 -- 接收单链表头指针
  33. void PrintSList(SLTNode* phead);
  34.  
  35.    
  36. //创建生成结点的函数 -- 接收要存入结点数据域的数据；返回该结点的指针
  37. SLTNode* BuySListNode(SLTDataType x);
  38.  
  39.  
  40. //创建尾插函数 -- 
  41. //使用二级指针接收单链表头指针的地址 和 接收要插入的值
  42. void SLTPushBack(SLTNode** pphead, SLTDataType x);
  43.  
  44.  
  45. //创建头插函数 -- 
  46. //使用二级指针接收单链表头指针的地址 和 接收要插入的值
  47. void SLTPushFront(SLTNode** pphead, SLTDataType x);
  48.  
  49.  
  50.  
  51. //创建尾删函数 --
  52. //使用二级指针接收单链表头指针的地址
  53. void SLTPopBack(SLTNode** pphead);
  54.  
  55.  
  56. //创建头删函数 --
  57. //使用二级指针接收单链表头指针的地址
  58. void SLTPopFront(SLTNode** pphead);
  59.  
  60.  
  61. //创建查找函数 --
  62. //查找指定值(x)所在结点的地址
  63. //接收 链表头指针phead、查找值x
  64. SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
  65.  
  66.  
  67. //创建指定位置插入函数1 --
  68. //在链表指定位置(pos)之前插入一个值(x)
  69. //接收 链表头指针地址pphead、指定结点指针pos、插入值x
  70. void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
  71.  
  72.  
  73. //创建指定位置插入函数2 --
  74. //在链表指定位置(pos)之后插入一个值(x)
  75. //接收 指定结点指针pos、插入值x
  76. void SLTInsertAfter(SLTNode* pos, SLTDataType x);
  77.  
  78.  
  79. //创建删除指定结点函数1 --
  80. //在链表删除指定位置(pos)结点
  81. ///接收 链表头指针地址pphead、指定结点指针pos
  82. void SLTErase(SLTNode** pphead, SLTNode* pos);
  83.  
  84.  
  85. //创建删除指定结点函数2 --
  86. //在链表删除指定位置(pos)之后一个结点
  87. //接收 指定结点指针pos
  88. void SLTEraseAfter(SLTNode* pos);
  89.  
  90.  
  91. //创建销毁链表函数：
  92. void SLTDestroy(SLTNode** pphead);

            

            

---------------------------------------------------------------------------------------------

SList.c -- 单链表函数实现文件

  1. //链表实现文件：
  2. #define _CRT_SECURE_NO_WARNINGS 1
  3.  
  4. //包含链表头文件：
  5. #include "SList.h"
  6.  
  7. //创建遍历单链表的函数：接收单链表结点的头指针
  8. void PrintSList(SLTNode* phead)
  9. {
  10. 	//phead头指针指向第一个结点，
  11. 	//之后还要多次使用phead头指针，
  12. 	//所以不要改变phead头指针，
  13. 	//所以可以创建一个和phead头指针一样类型的指针cur代替phead头指针
  14. 	SLTNode* cur = phead;
  15.  
  16. 	//因为链表到最后结点的指针域为NULL才结束
  17. 	//所以只要cur不为NULL就继续遍历结点进行打印：
  18. 	while (cur != NULL)
  19. 	{
  20. 		//通过cur当前指向的结点打印cur里数据域的内容：
  21. 		printf("%d->", cur->data);
  22.  
  23. 		//通过结点里指针域指向下一个结点，方便打印下个结点的数据域内容
  24. 		cur = cur->next;
  25. 	}
  26.  
  27. 	//最后提示已指向NULL指针链表，遍历结束：
  28. 	printf("NULL\n");
  29. }
  30.  
  31.  
  32.  
  33. //创建生成结点的函数 -- 接收要存入结点数据域的数据；返回该结点的指针
  34. SLTNode* BuySListNode(SLTDataType x)
  35. {
  36. 	//给结点开辟动态空间（注意开辟空间的大小是SLTNode结点的大小--8个字节）
  37. 	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); 
  38. 	//返回该结点地址
  39.  
  40. 	//检查是否开辟成功：
  41. 	if (newnode == NULL) //返回空指针，说明开辟失败
  42. 	{
  43. 		//打印错误信息：
  44. 		perror("malloc fail");
  45. 		//开辟失败直接退出程序：
  46. 		exit(-1);
  47. 	}
  48.  
  49. 	//将接收的值x赋给该结点的数据域：
  50. 	newnode->data = x;
  51.  
  52. 	//设置新创建结点的指针域：
  53. 	//因为是最新的结点，即最尾部的结点，
  54. 	//所以指针域的指针应是NULL(链表末尾结束)
  55. 	//之后通过指针域连接各个结点的操作要看情况操作，先都初始化为NULL
  56. 	newnode->next = NULL;
  57.  
  58. 	//返回该新结点的指针（地址）
  59. 	return newnode;
  60. }
  61.  
  62.  
  63.  
  64. //创建尾插函数
  65. //使用二级指针接收单链表头指针的地址 和 接收要插入的值
  66. void SLTPushBack(SLTNode** pphead, SLTDataType x)
  67. {
  68. 	//改变结构体，要用结构体指针
  69. 	//改变结构体指针，要用结构体指针的指针（二级指针）
  70. 	   
  71. 	//因为pphead二级指针存储的是plist指针，
  72. 	//plist指针指向的值可能为空，但指针的地址不能为空
  73. 	//pphead是plist的地址，正常情况下一定不为空
  74. 	assert(pphead);
  75.  
  76. 	//先使用newnode函数为要尾插的值创建一个结点
  77. 	//并返回该结点地址
  78. 	SLTNode* newnode = BuySListNode(x);
  79.  
  80. 	//判断phead是否是NULL，如果是说明链表还没开辟过一个结点
  81. 	if (*pphead == NULL)
  82. 	{
  83. 		//如果为空，则将上面开辟的newnode结点地址赋给phead
  84. 		*pphead = newnode;
  85. 		//要改变结构体的指针，就要用二级指针
  86.  
  87. 		//这里pphead是二级指针，存放链表头指针plist的地址
  88. 		//因为如果用一级指针SLTNode* phead的话，
  89. 		//phead形参只是plist实参的临时拷贝，两者空间相互独立
  90. 		//改变phead的话不会改变plist，plist还会是空指针
  91. 		//所以要用二级指针pphead存放plist指针的地址，
  92. 		//*pphead解引用就能得到一级指针plist,
  93. 		//即			*pphead = plist
  94. 		//所以实际上上面的代码就相当于：plist = newnode
  95. 		//这样就让本来指向空指针的头指针指向了新创建的结点指针
  96. 		//链表就能够连接起来
  97. 	}
  98. 	else
  99. 		//不为空则往尾部插入新结点：
  100. 	{
  101. 		//创建另一个指针存放单链表头指针
  102. 		SLTNode* tail = *pphead; //*pphead == plist
  103.  
  104. 		//使用while循环获得最后一个结点的地址
  105. 		while (tail->next != NULL)
  106. 		//如果下个结点的next指针域不为NULL，
  107. 		//则继续往后找，直到tail等于最后结点的地址
  108. 		{
  109. 			//把当前结点指针域里下个结点的地址给到tail，
  110. 			//进行while循环下次判断：
  111. 			tail = tail->next;
  112. 		}
  113.  
  114. 		//tail找到最后结点地址后，
  115. 		//把尾插的新结点地址给到tail的next指针域，
  116. 		//连接起链表：
  117. 		tail->next = newnode;
  118. 		//要改变结构体，用结构体的指针即可
  119.  
  120. 		//因为newnode、tail、pphead都是临时(局部)变量，
  121. 		//所以函数运行结束后都会销毁，
  122. 		//但malloc函数开辟的空间(结点)都在堆上不会销毁
  123. 		//通过解引用二级指针pphead改变plist也没有问题
  124. 	}
  125. }
  126.  
  127.  
  128.  
  129. //创建头插函数 -- 
  130. //使用二级指针接收单链表头指针的地址 和 接收要插入的值
  131. void SLTPushFront(SLTNode** pphead, SLTDataType x)
  132. {
  133. 	//因为pphead二级指针存储的是plist指针，
  134. 	//plist指针指向的值可能为空，但指针的地址不能为空
  135. 	//pphead是plist的地址，正常情况下一定不为空
  136. 	assert(pphead);
  137.  
  138. 	//先使用newnode函数为要头插的值创建一个结点
  139. 	//并返回该结点地址
  140. 	SLTNode* newnode = BuySListNode(x);
  141.  
  142. 	//因为也要用到链表头指针本身，所以也要使用二级指针
  143. 	//因为plist指向原本头结点地址，
  144. 	//所以可以使用plist把原本头结点地址赋给新插入头结点指针域：
  145. 	newnode->next = *pphead;
  146.  
  147. 	//再把头指针改为指向新插入头结点：
  148. 	*pphead = newnode;
  149. }
  150.  
  151.  
  152.  
  153. //创建尾删函数 --
  154. //使用二级指针接收单链表头指针的地址
  155. void SLTPopBack(SLTNode** pphead)
  156. {
  157. 	//尾删需要考虑三种情况：
  158. 	//注：*pphead 就是 plist
  159. 	
  160. 	//因为pphead二级指针存储的是plist指针，
  161. 	//plist指针指向的值可能为空，但指针的地址不能为空
  162. 	//pphead是plist的地址，正常情况下一定不为空
  163. 	assert(pphead);
  164.  
  165. 	// 第一种情况：链表为空 -- 没有任何结点
  166. 	//没有结点那就删不了了，使用assert接收到空指针就报警告
  167. 	assert(*pphead);
  168.  
  169. 	// 第二种情况：链表只有一个结点
  170. 	if ((*pphead)->next == NULL)
  171. 		// -> 也是解引用(结构体的)，优先级比 * 高
  172. 		//所以 *pphead 要用() 括起来
  173. 	{
  174. 		//只有一个结点，又要尾删，那就直接把这唯一的结点删掉：
  175. 		free(*pphead); //直接free释放掉plist指向的结点
  176.  
  177. 		//再把释放掉的plist置为空指针，防止成为野指针：
  178. 		*pphead = NULL;
  179. 	}
  180. 	else
  181. 	// 第三种情况：链表有一个以上结点
  182. 	{
  183. 		//这种情况额外两个指针，
  184. 		//一个tail指针 -- 用来找到最后一个结点地址并将其释放，
  185. 		//还有一个tailPrev指针 -- 指向tail指针的前一个结点地址，
  186. 		//用来改变该结点的指针域，
  187. 		//防止原本指向tail结点的指针域变成野指针
  188.  
  189. 		//先替代头指针plist：
  190. 		SLTNode* tail = *pphead;
  191.  
  192. 		//创建tailPrev指针，
  193. 		//之后操作会指向tail结点的前一个结点，
  194. 		//即倒数第二个结点
  195. 		SLTNode* tailPrev = NULL;
  196.  
  197. 		//再使用while循环找到尾结点：
  198. 		//和尾插的操作类似
  199. 		while (tail->next != NULL)
  200. 		{
  201. 			//tail查找之前先把当前指向结点地址给tailPrev
  202. 			//这样最后tail会指向尾结点，
  203. 			//tailPrev会指向倒数第二个结点
  204. 			tailPrev = tail;
  205.  
  206. 			tail = tail->next;
  207. 		}
  208.  
  209. 		//结束while循环后tail指向尾结点地址，
  210. 		//因为是尾删，所以free释放掉tail就可以“删掉”尾结点
  211. 		free(tail);
  212. 		//因为tail是局部（临时）变量，出了函数就销毁，
  213. 		//所以不置为指针也可以，不用担心成为野指针
  214.  
  215. 		//删除原尾结点后，倒数第二个结点成为尾结点，
  216. 		//要把其指针域next置为空指针，成为链表新结尾
  217. 		tailPrev->next = NULL;
  218. 	}
  219. }
  220.  
  221.  
  222.  
  223. //创建头删函数 --
  224. //使用二级指针接收单链表头指针的地址
  225. void SLTPopFront(SLTNode** pphead)
  226. {
  227. 	//因为pphead二级指针存储的是plist指针，
  228. 	//plist指针指向的值可能为空，但指针的地址不能为空
  229. 	//pphead是plist的地址，正常情况下一定不为空
  230. 	assert(pphead);
  231.  
  232. 	//分两种情况：
  233. 	
  234. 	//第一种情况：链表里没有结点（空链表）
  235. 	//没有结点可以删，直接assert断言pass掉：
  236. 	assert(*pphead);
  237.  
  238.  
  239. 	//第二种情况：链表有一个和多个结点（非空链表）
  240. 	//因为是删掉头结点，所以不用考虑找尾结点
  241. 	//所以不用细分一个或多个结点的情况：
  242. 	
  243. 	//这种情况要先通过plist拿到第二个结点的地址：
  244. 	SLTNode* newhead = (*pphead)->next;
  245. 	//使用newhead存储第二个结点地址
  246.  
  247. 	//拿到第二个结点地址后，再释放掉头结点，
  248. 	//实现头删效果：
  249. 	free(*pphead);
  250.  
  251. 	//这时要让第二个结点成为新的头结点：
  252. 	*pphead = newhead; 
  253. 	//头指针指向原本的第二个结点
  254. }
  255.  
  256.  
  257.  
  258. //创建查找函数 --
  259. //查找指定值(x)所在结点的地址
  260. //接收 链表头指针phead、查找值x
  261. SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
  262. {
  263. 	//像SLTFind和PrintSList函数只用头指针遍历
  264. 	//不改变指针本身就不需要用到二级指针
  265.  
  266. 	//创建个变量代替头指针：
  267. 	SLTNode* cur = phead;
  268.  
  269. 	//使用while循环对链表进行遍历查找：
  270. 	while (cur != NULL)
  271. 		//只要cur指针指向地址不为空就继续循环
  272. //while遍历时，(cur->next != NULL) 和 (cur != NULL) 的区别：
  273. //(cur->next != NULL)：这个条件最后cur会是最后结点的地址
  274. //(cur != NULL)：这个条件最后cur会是NULL
  275. //(cur->next != NULL) 会比 (cur != NULL) 少一次循环
  276. 	{
  277. 		//遍历过程中依次查找各结点数据域数据是否与x相同：
  278. 		if (cur->data == x)
  279. 		{
  280. 			//找到了一个结点数据域数据是x，返回该结点地址
  281. 			return cur;
  282. 		}
  283. 		//这里如果while循环的条件是(cur->next != NULL)
  284. 		//最后一个结点进不来，不能判断最后结点数据域数据是不是x
  285.  
  286. 		cur = cur->next; //改变循环条件，指向下个结点
  287. 	}
  288.  
  289. 	//如果能指向到这说明没找到，返回NULL：
  290. 	return  NULL;
  291. }
  292.  
  293.  
  294.  
  295. //创建指定位置插入函数1 -- 
  296. //在链表指定位置(pos)之前插入一个值(x)
  297. //接收 链表头指针地址pphead、指定结点指针pos、插入值x
  298. void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
  299. {
  300. 	//因为pphead二级指针存储的是plist指针，
  301. 	//plist指针指向的值可能为空，但指针的地址不能为空
  302. 	//pphead是plist的地址，正常情况下一定不为空
  303. 	assert(pphead);
  304.  
  305. 	//第一种情况：空指针
  306. 	//先排除空指针的情况：
  307. 	assert(pos);
  308.  
  309. 	//第二种情况：头插
  310. 	if (pos == *pphead)
  311. 		// *pphead == plist
  312. 		//如果pos是pphead即第一个指针，
  313. 		//则在第一个指针前插入一个值，相当于头插
  314. 	{
  315. 		//直接复用头插函数SLTPustFront：
  316. 		SLTPushFront(pphead, x);
  317. 		//直接传pphead二级指针过去
  318. 	}
  319. 	else
  320. 	//第三种情况：非头插
  321. 	{
  322. 		//从头开始找pos结点的前一个结点：
  323. 		//先获得头指针
  324. 		SLTNode* prev = *pphead;
  325.  
  326. 		//当前结点的指针域不是指向pos结点则继续循环
  327. 		while (prev->next != pos)
  328. 		{
  329. 			prev = prev->next;
  330. 		}
  331.  
  332. 		//此时prev已指向pos结点的前一个结点
  333.  
  334. 		//为要插入的结点创建一个结点newnode：
  335. 		//插入位置是pos结点之前，prev结点之后
  336. 		SLTNode* newnode = BuySListNode(x);
  337.  
  338. 		//让prev结点指针域指向新插入结点地址：
  339. 		prev->next = newnode;
  340.  
  341. 		//newnode结点指针域指向pos结点：
  342. 		newnode->next = pos;
  343.  
  344. 		//此时newnode新结点就插入完成了
  345. 	}
  346. }
  347.  
  348.  
  349.  
  350. //创建指定位置插入函数2 --
  351. //在链表指定位置(pos)之后插入一个值(x)
  352. //接收 指定结点指针pos、插入值x
  353. void SLTInsertAfter(SLTNode* pos, SLTDataType x)
  354. {
  355. 	//因为是在pos结点后插入一个值(结点)
  356. 	//所以不可能会有头插的情况，那就不需要头指针plist
  357.  
  358. 	//pos指针存储结点地址，可能会接收到空指针
  359. 	//使用assert断言pass掉
  360. 	assert(pos);
  361.  
  362. 	//先为插入值创建一个新结点newnode：
  363. 	SLTNode* newnode = BuySListNode(x);
  364.  
  365. 	//先让newnode的指针域next指向后一个结点：
  366. 	//这里后一个结点就是pos结点指针域里的地址
  367. 	//因为未插入前pos就是指向后一个地址
  368. 	newnode->next = pos->next;
  369.  
  370. 	//再让pos的指针域next指向newnode：
  371. 	pos->next = newnode;
  372. }
  373.  
  374.  
  375.  
  376. //创建删除指定结点函数1 --
  377. //在链表删除指定位置(pos)结点
  378. ///接收 链表头指针地址pphead、指定结点指针pos
  379. void SLTErase(SLTNode** pphead, SLTNode* pos)
  380. {
  381. 	//因为pphead二级指针存储的是plist指针，
  382. 	//plist指针指向的值可能为空，但指针的地址不能为空
  383. 	//pphead是plist的地址，正常情况下一定不为空
  384. 	assert(pphead);
  385.  
  386. 	//防止要删的pos结点指针为空指针
  387. 	//使用assert断言：
  388. 	assert(pos);
  389.  
  390. 	//分两种情况：
  391.  
  392. 	// 1.头删：
  393. 	if (pos == *pphead)
  394. 		//pos结点 == 头结点 --> 头删
  395. 	{
  396. 		//直接复用SLTPopFront头删函数：
  397. 		SLTPopFront(pphead);
  398. 	}
  399. 	else
  400. 	// 2.非头删：
  401. 	//尾删不用单独分出一种情况，因为还得判断是不是尾结点
  402. 	//直接用通用逻辑删除也可以处理尾删的情况
  403. 	{
  404. 		//从头开始找pos结点的前一个结点：
  405. 		//先获得头指针
  406. 		SLTNode* prev = *pphead;
  407.  
  408. 		//当前结点的指针域不是指向pos结点则继续循环
  409. 		while (prev->next != pos)
  410. 		{
  411. 			prev = prev->next;
  412. 		}
  413.  
  414. 		//此时prev已指向pos结点的前一个结点
  415.  
  416. 		//因为要删除pos结点，
  417. 		//所以要让pos前一个和后一个结点连接起来：
  418. 		prev->next = pos->next;
  419.  
  420. 		//连接成功后再把pos结点释放，实现删除效果：
  421. 		free(pos);
  422. 	}
  423. }
  424.  
  425.  
  426.  
  427. //创建删除指定结点函数2 --
  428. //在链表删除指定位置(pos)之后一个结点
  429. //接收 指定结点指针pos
  430. void SLTEraseAfter(SLTNode* pos)
  431. {
  432. 	//删除pos结点后的一个结点，
  433. 	//那么就不可能出现头删的情况，
  434. 	//pos结点是尾结点也没用，
  435. 	//因为尾结点后就没有结点可以删了
  436. 	//使用assert断言处理：
  437. 	assert(pos); //防止接收“空结点”
  438. 	assert(pos->next); //防止接收尾结点
  439.  
  440. 	//将要删的pos结点的下个结点posNext先保存起来：
  441. 	SLTNode* posNext = pos->next;
  442.  
  443. 	//再把pos结点和下下个结点连接起来：
  444. 	pos->next = posNext->next;
  445. 	//posNext的指针域next就是pos结点的下下个结点地址
  446.  
  447. 	//最后释放(删除)posNext结点：
  448. 	free(posNext);
  449. }
  450.  
  451.  
  452.  
  453. //创建销毁链表函数：
  454. void SLTDestroy(SLTNode** pphead)
  455. {
  456. 	//因为链表释放后，还要把头指针plist给置为空，
  457. 	//要操作到plist，所以要用到二级指针：
  458.  
  459. 	//plist指向空链表，pphead也不能为空：
  460. 	assert(pphead);
  461.  
  462. 	//创建一个指针进行遍历：
  463. 	SLTNode* cur = *pphead;//*pphead == plist
  464. 	//进行遍历释放：
  465. 	while (cur != NULL)
  466. 	{
  467. 		//创建一个指针保存下个结点地址：
  468. 		SLTNode* next = cur->next;
  469. 		//释放当前结点：
  470. 		free(cur);
  471. 		//cur指针移向下一个结点：
  472. 		cur = next;
  473. 	}
  474.  
  475. 	//将链表头指针置为空：
  476. 	*pphead = NULL;
  477. }

            

            

---------------------------------------------------------------------------------------------

test.c -- 单链表测试文件

  1. //链表测试文件：
  2. #define _CRT_SECURE_NO_WARNINGS 1
  3.  
  4. /* 链表学习引入小测试：
  6. #include <stdio.h>
  8. //重命名一个单链表数据类型
  9. typedef int SLTDataType;
  10. //SLT -- single link table
  12. //创建一个单链表结点结构体
  13. typedef struct SListNode
  14. {
  15. 	//结点数据域：
  16. 	SLTDataType data; 
  18. 	//结点指针域：
  19. 	//因为是指向单链表结点结构体的指针，
  20. 	//所以是单链表结点结构体类型的指针
  21. 	struct SListNode* next; 
  23. }SLTNode; //将struct SListNode重命名为SLTNode
  25. //创建遍历单链表的函数：接收单链表结点的头指针
  26. void PrintSList(SLTNode* phead)
  27. {
  28. 	//phead头指针指向第一个结点，
  29. 	//之后还要多次使用phead头指针，
  30. 	//所以不要改变phead头指针，
  31. 	//所以可以创建一个和phead头指针一样类型的指针cur代替phead头指针
  32. 	SLTNode* cur = phead;
  34. 	//因为链表到最后结点的指针域为NULL才结束
  35. 	//所以只要cur不为NULL就继续遍历结点进行打印：
  36. 	while (cur != NULL)
  37. 	{
  38. 		//通过cur当前指向的结点打印cur里数据域的内容：
  39. 		printf("%d->", cur->data);
  41. 		//通过结点里指针域指向下一个结点，方便打印下个结点的数据域内容
  42. 		cur = cur->next;
  43. 	}
  45. 	//最后提示已指向NULL指针链表，遍历结束：
  46. 	printf("NULL\n");
  47. }
  49. int main()
  50. {
  51. 	//创建单链表结点：
  52. 	SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));
  53. 	n1->data = 10; //在该结点数据域存放数据
  55. 	SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));
  56. 	n2->data = 20; //在该结点数据域存放数据
  59. 	SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));
  60. 	n3->data = 30; //在该结点数据域存放数据
  62. 	n1->next = n2; //n1的指针域指向结点n2
  63. 	n2->next = n3; //n2的指针域指向结点n3
  64. 	n3->next = NULL; //n3的指针域指向NULL(结束)
  66. 	PrintSList(n1); //调用函数打印单链表
  68. 	return 0;
  69. }
  71. */
  72.  
  73.  
  74. //包含链表头文件：
  75. #include "SList.h"
  76.  
  77. //测试函数1：测试--PrintSList、BuySListNode函数
  78. void TestList1()
  79. {
  80. 	int n; //存放链表长度
  81.  
  82. 	//打印提示信息：
  83. 	printf("请输入链表的长度：>");
  84. 	//接收链表长度
  85. 	scanf("%d", &n); 
  86. 	
  87. 	//打印提示信息：
  88. 	printf("\n请依次输入每个结点的值：>");
  89.  
  90. 	SLTNode* plist = NULL; //链表头指针，一开始链表没数据所以为NULL
  91.  
  92. 	//使用for循环，循环创建结点并赋值，形成链表：
  93. 	for (int i = 0; i < n; i++)
  94. 	{
  95. 		int val; //存放结点数据域数据
  96. 		scanf("%d", &val); //接收结点数据域数据
  97. 		
  98. 		//使用BuySListNode函数创建结点并给数据域赋值:
  99. 		SLTNode* newnode = BuySListNode(val);
  100.  
  101. 		//头插: 使用头插把链表连接起来
  102. 		
  103. 		//把链表头指针plist指向的头结点地址赋给新创建结点的指针域next
  104. 		//这样新结点的指针域next就能指向原来的头结点地址
  105. 		newnode->next = plist;
  106.  
  107. 		//再把新创建结点的地址赋给头指针，
  108. 		//这样头指针就指向了新创建结点地址，让其成为新的头结点
  109. 		plist = newnode;
  110. 	}
  111.  
  112. 	//使用PrintSList函数打印链表
  113. 	PrintSList(plist); //接收头指针后打印
  114.  
  115.  
  116. 	//使用SLTPushBack函数手动向链表尾部插入数据（尾插）：
  117. 	SLTPushBack(plist, 10000);
  118. 	//再使用PrintSList函数打印插入后的链表
  119. 	PrintSList(plist);
  120.  
  121. 	//plist和phead都是单链表头指针，
  122. 	//但 plist是实参  phead是形参
  123. 	//phead 是 plist 的一份临时拷贝
  124. }
  125.  
  126. //测试函数2：测试--SLTPushBack、SLTPushFront函数
  127. void TestList2()
  128. {
  129. 	//创建单链表头指针：
  130. 	SLTNode* plist = NULL;
  131.  
  132. 	//使用尾插随机插入几个值: 
  133. 	//(此时头指针指向NULL还没有开辟空间创建结点)
  134. 	SLTPushBack(&plist, 1);
  135. 	SLTPushBack(&plist, 2);
  136. 	SLTPushBack(&plist, 3);
  137. 	SLTPushBack(&plist, 4);
  138. 	SLTPushBack(&plist, 5);
  139. 	  
  140. 	//使用头插随机插入几个值：
  141. 	SLTPushFront(&plist, 10);
  142. 	SLTPushFront(&plist, 20);
  143. 	SLTPushFront(&plist, 30);
  144. 	SLTPushFront(&plist, 40);
  145.  
  146. 	//使用SLTPrintf函数打印该链表：
  147. 	PrintSList(plist);
  148. }
  149.  
  150. //测试函数3：测试--SLTPopBack（尾删）函数
  151. void TestList3()
  152. {
  153. 	//创建单链表头指针：
  154. 	SLTNode* plist = NULL;
  155.  
  156. 	//使用尾插随机插入几个值: 
  157. 	//(此时头指针指向NULL还没有开辟空间创建结点)
  158. 	SLTPushBack(&plist, 1);
  159. 	SLTPushBack(&plist, 2);
  160. 	SLTPushBack(&plist, 3);
  161. 	//使用SLTPrintf函数打印该链表：
  162. 	printf("尾删前链表：\n");
  163. 	PrintSList(plist);
  164.  
  165. 	//使用尾删函数：
  166. 	SLTPopBack(&plist);
  167. 	//使用SLTPrintf函数打印该链表：
  168. 	printf("尾删后链表：\n");
  169. 	PrintSList(plist);
  170.  
  171. 	SLTPopBack(&plist);
  172. 	//使用SLTPrintf函数打印该链表：
  173. 	printf("尾删后链表：\n");
  174. 	PrintSList(plist);
  175.  
  176. 	SLTPopBack(&plist);
  177. 	//使用SLTPrintf函数打印该链表：
  178. 	printf("尾删后链表：\n");
  179. 	PrintSList(plist);
  180.  
  181. 	SLTPopBack(&plist);
  182. 	//使用SLTPrintf函数打印该链表：
  183. 	printf("尾删后链表：\n");
  184. 	PrintSList(plist);
  185.  
  186. 	//使用SLTPrintf函数打印该链表：
  187. 	printf("尾删后链表：\n");
  188. 	PrintSList(plist);
  189. }
  190.  
  191. //测试函数4：测试--SLTPopFront（头删）函数
  192. void TestList4()
  193. {
  194. 	//创建单链表头指针：
  195. 	SLTNode* plist = NULL;
  196.  
  197. 	//使用尾插随机插入几个值: 
  198. 	//(此时头指针指向NULL还没有开辟空间创建结点)
  199. 	SLTPushBack(&plist, 1);
  200. 	SLTPushBack(&plist, 2);
  201. 	SLTPushBack(&plist, 3);
  202. 	//使用SLTPrintf函数打印该链表：
  203. 	printf("头删前链表：\n");
  204. 	PrintSList(plist);
  205.  
  206. 	SLTPopFront(&plist);
  207. 	//使用SLTPrintf函数打印该链表：
  208. 	printf("头删后链表：\n");
  209. 	PrintSList(plist);
  210.  
  211. 	SLTPopFront(&plist);
  212. 	//使用SLTPrintf函数打印该链表：
  213. 	printf("头删后链表：\n");
  214. 	PrintSList(plist);
  215.  
  216. 	SLTPopFront(&plist);
  217. 	//使用SLTPrintf函数打印该链表：
  218. 	printf("头删后链表：\n");
  219. 	PrintSList(plist);
  220.  
  221. 	SLTPopFront(&plist);
  222. 	//使用SLTPrintf函数打印该链表：
  223. 	printf("头删后链表：\n");
  224. 	PrintSList(plist);
  225. }
  226.  
  227. //测试函数5：测试 -- SLTFind函数
  228. void TestList5()
  229. {
  230. 	//创建单链表头指针：
  231. 	SLTNode* plist = NULL;
  232.  
  233. 	//使用尾插随机插入几个值: 
  234. 	//(此时头指针指向NULL还没有开辟空间创建结点)
  235. 	SLTPushBack(&plist, 1);
  236. 	SLTPushBack(&plist, 2);
  237. 	SLTPushBack(&plist, 3);
  238. 	//使用SLTPrintf函数打印该链表：
  239. 	printf("操作前链表：\n");
  240. 	PrintSList(plist);
  241.  
  242. 	//用SLTFind函数查找链表中数据域为3的结点的地址
  243. 	SLTNode* pos = SLTFind(plist, 1);
  244. 	if (pos != NULL)
  245. 	{	
  246. 		//找到了可以对该结点进行修改
  247. 		pos->data *= 10;
  248. 		
  249. 		//所以SLTFind查找函数可以负责查找和修改的操作
  250. 	}
  251.  
  252. 	printf("操作后链表：\n");
  253. 	PrintSList(plist);
  254. }
  255.  
  256. //测试函数6：测试 -- SLTInsert函数
  257. void TestList6()
  258. {
  259. 	//创建单链表头指针：
  260. 	SLTNode* plist = NULL;
  261.  
  262. 	//使用尾插随机插入几个值: 
  263. 	//(此时头指针指向NULL还没有开辟空间创建结点)
  264. 	SLTPushBack(&plist, 1);
  265. 	SLTPushBack(&plist, 2);
  266. 	SLTPushBack(&plist, 3);
  267. 	//使用SLTPrintf函数打印该链表：
  268. 	printf("操作前链表：\n");
  269. 	PrintSList(plist);
  270.  
  271. 	//用SLTFind函数查找链表中数据域为3的结点的地址
  272. 	SLTNode* pos = SLTFind(plist, 2);
  273. 	if (pos != NULL)
  274. 	{
  275. 		int x; //接收要插入的值
  276. 		scanf("%d", &x); //输入要插入的值
  277. 		SLTInsert(&plist, pos, x); //在2前面插入x 
  278. 	}
  279.  
  280. 	printf("操作后链表：\n");
  281. 	PrintSList(plist);
  282. }
  283.  
  284. //测试函数7：测试 -- SLTInsertAfter函数
  285. void TestList7()
  286. {
  287. 	//创建单链表头指针：
  288. 	SLTNode* plist = NULL;
  289.  
  290. 	//使用尾插随机插入几个值: 
  291. 	//(此时头指针指向NULL还没有开辟空间创建结点)
  292. 	SLTPushBack(&plist, 1);
  293. 	SLTPushBack(&plist, 2);
  294. 	SLTPushBack(&plist, 3);
  295. 	//使用SLTPrintf函数打印该链表：
  296. 	printf("操作前链表：\n");
  297. 	PrintSList(plist);
  298.  
  299. 	//用SLTFind函数查找链表中数据域为3的结点d的地址
  300. 	SLTNode* pos = SLTFind(plist, 2);
  301. 	if (pos != NULL)
  302. 	{
  303. 		int x; //接收要插入的值
  304. 		scanf("%d", &x); //输入要插入的值
  305. 		SLTInsertAfter(pos, x); //在2后面插入x 
  306. 	}
  307.  
  308. 	printf("操作后链表：\n");
  309. 	PrintSList(plist);
  310. }
  311.  
  312. //测试函数8：测试 -- SLTErase函数
  313. void TestList8()
  314. {
  315. 	//创建单链表头指针：
  316. 	SLTNode* plist = NULL;
  317.  
  318. 	//使用尾插随机插入几个值: 
  319. 	//(此时头指针指向NULL还没有开辟空间创建结点)
  320. 	SLTPushBack(&plist, 1);
  321. 	SLTPushBack(&plist, 2);
  322. 	SLTPushBack(&plist, 3);
  323. 	//使用SLTPrintf函数打印该链表：
  324. 	printf("操作前链表：\n");
  325. 	PrintSList(plist);
  326.  
  327. 	//用SLTFind函数查找链表中数据域为3的结点d的地址
  328. 	SLTNode* pos = SLTFind(plist, 2);
  329. 	if (pos != NULL)
  330. 	{
  331. 		int x; //接收要插入的值
  332. 		scanf("%d", &x); //输入要插入的值
  333. 		SLTErase(&plist, pos); //删除pos所在结点
  334. 		//pos结点指针删除（释放）后，要将其置为空：
  335. 		pos = NULL;
  336. 	}
  337.  
  338. 	printf("操作后链表：\n");
  339. 	PrintSList(plist);
  340. }
  341.  
  342. //测试函数9：测试 -- SLTEraseAfter函数
  343. void TestList9()
  344. {
  345. 	//创建单链表头指针：
  346. 	SLTNode* plist = NULL;
  347.  
  348. 	//使用尾插随机插入几个值: 
  349. 	//(此时头指针指向NULL还没有开辟空间创建结点)
  350. 	SLTPushBack(&plist, 1);
  351. 	SLTPushBack(&plist, 2);
  352. 	SLTPushBack(&plist, 3);
  353. 	//使用SLTPrintf函数打印该链表：
  354. 	printf("操作前链表：\n");
  355. 	PrintSList(plist);
  356.  
  357. 	//用SLTFind函数查找链表中数据域为3的结点d的地址
  358. 	SLTNode* pos = SLTFind(plist, 2);
  359. 	if (pos != NULL)
  360. 	{
  361. 		int x; //接收要插入的值
  362. 		scanf("%d", &x); //输入要插入的值
  363. 		SLTEraseAfter(pos); //删除pos结点的下个结点
  364. 		//pos结点指针删除（释放）后，要将其置为空：
  365. 		pos = NULL;
  366. 	}
  367.  
  368. 	printf("操作后链表：\n");
  369. 	PrintSList(plist);
  370. }
  371.  
  372. //测试函数10：测试 -- SLTDestroy函数
  373. void TestList10()
  374. {
  375. 	//创建单链表头指针：
  376. 	SLTNode* plist = NULL;
  377.  
  378. 	//使用尾插随机插入几个值: 
  379. 	//(此时头指针指向NULL还没有开辟空间创建结点)
  380. 	SLTPushBack(&plist, 1);
  381. 	SLTPushBack(&plist, 2);
  382. 	SLTPushBack(&plist, 3);
  383. 	//使用SLTPrintf函数打印该链表：
  384. 	printf("操作前链表：\n");
  385. 	PrintSList(plist);
  386.  
  387. 	SLTDestroy(&plist);
  388. }
  389.  
  390. //主函数：
  391. int main()
  392. {
  393. 	//TestList1();
  394. 	//TestList2();
  395. 	//TestList3();
  396. 	//TestList4();
  397. 	//TestList5();
  398. 	//TestList6();
  399. 	//TestList7();
  400. 	//TestList8();
  401. 	//TestList9();
  402. 	TestList10();
  403.  
  404. 	return 0;
  405. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/670117
推荐阅读
相关标签

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

  

闽ICP备14008679号