• 【数据结构初阶】三、 线性表里的链表（无头+单向+非循环链表）

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

    相关代码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 
    6. #include 
    7. #include 
    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 
    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. }
  • 相关阅读:
    7-3 LVS+Keepalived集群叙述与部署
    「重启程序」的正面和反面
    49从零开始用Rust编写nginx，我竟然在同一个端口上绑定了多少IP
    Golang中的包和模块设计
    Spring面试题15：Spring支持几种bean的作用域？singleton、prototype、request的区别是什么？
    第10章 MySQL（二）
    Python编程 元组的创建
    拯救SQL Server数据库事务日志文件损坏的终极大招
    使用Element进行前端开发
    Jetson NX安装opencv3.2.0报错及问题汇总
  • 原文地址：https://blog.csdn.net/weixin_63176266/article/details/132781490