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

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

相关代码gitee自取：

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

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

接上期：

【数据结构初阶】二、 线性表里的顺序表_高高的胖子的博客-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 -- 单链表头文件

//链表头文件：
#pragma once//先包含之后要用到的头文件：
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//重命名一个单链表数据类型
typedef int SLTDataType;
//SLT -- single link table//创建一个单链表结点结构体 
//这里数据域是int类型4字节，指针域指针也是4个字节，
//所以一个结点就是8个字节
typedef struct SListNode
{//结点数据域：SLTDataType data;//结点指针域：//因为是指向单链表结点结构体的指针，//所以是单链表结点结构体类型的指针struct SListNode* next;//第一个结点要找到第二个结点，物理空间不连续//通过上个结点指向下个结点，实现逻辑连续}SLTNode; //将struct SListNode重命名为SLTNode//创建遍历打印单链表的函数 -- 接收单链表头指针
void PrintSList(SLTNode* phead);//创建生成结点的函数 -- 接收要存入结点数据域的数据；返回该结点的指针
SLTNode* BuySListNode(SLTDataType x);//创建尾插函数 -- 
//使用二级指针接收单链表头指针的地址 和 接收要插入的值
void SLTPushBack(SLTNode** pphead, SLTDataType x);//创建头插函数 -- 
//使用二级指针接收单链表头指针的地址 和 接收要插入的值
void SLTPushFront(SLTNode** pphead, SLTDataType x);//创建尾删函数 --
//使用二级指针接收单链表头指针的地址
void SLTPopBack(SLTNode** pphead);//创建头删函数 --
//使用二级指针接收单链表头指针的地址
void SLTPopFront(SLTNode** pphead);//创建查找函数 --
//查找指定值(x)所在结点的地址
//接收 链表头指针phead、查找值x
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//创建指定位置插入函数1 --
//在链表指定位置(pos)之前插入一个值(x)
//接收 链表头指针地址pphead、指定结点指针pos、插入值x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//创建指定位置插入函数2 --
//在链表指定位置(pos)之后插入一个值(x)
//接收 指定结点指针pos、插入值x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//创建删除指定结点函数1 --
//在链表删除指定位置(pos)结点
///接收 链表头指针地址pphead、指定结点指针pos
void SLTErase(SLTNode** pphead, SLTNode* pos);//创建删除指定结点函数2 --
//在链表删除指定位置(pos)之后一个结点
//接收 指定结点指针pos
void SLTEraseAfter(SLTNode* pos);//创建销毁链表函数：
void SLTDestroy(SLTNode** pphead);

            

            

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

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

//链表实现文件：
#define _CRT_SECURE_NO_WARNINGS 1//包含链表头文件：
#include "SList.h"//创建遍历单链表的函数：接收单链表结点的头指针
void PrintSList(SLTNode* phead)
{//phead头指针指向第一个结点，//之后还要多次使用phead头指针，//所以不要改变phead头指针，//所以可以创建一个和phead头指针一样类型的指针cur代替phead头指针SLTNode* cur = phead;//因为链表到最后结点的指针域为NULL才结束//所以只要cur不为NULL就继续遍历结点进行打印：while (cur != NULL){//通过cur当前指向的结点打印cur里数据域的内容：printf("%d->", cur->data);//通过结点里指针域指向下一个结点，方便打印下个结点的数据域内容cur = cur->next;}//最后提示已指向NULL指针链表，遍历结束：printf("NULL\n");
}//创建生成结点的函数 -- 接收要存入结点数据域的数据；返回该结点的指针
SLTNode* BuySListNode(SLTDataType x)
{//给结点开辟动态空间（注意开辟空间的大小是SLTNode结点的大小--8个字节）SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); //返回该结点地址//检查是否开辟成功：if (newnode == NULL) //返回空指针，说明开辟失败{//打印错误信息：perror("malloc fail");//开辟失败直接退出程序：exit(-1);}//将接收的值x赋给该结点的数据域：newnode->data = x;//设置新创建结点的指针域：//因为是最新的结点，即最尾部的结点，//所以指针域的指针应是NULL(链表末尾结束)//之后通过指针域连接各个结点的操作要看情况操作，先都初始化为NULLnewnode->next = NULL;//返回该新结点的指针（地址）return newnode;
}//创建尾插函数
//使用二级指针接收单链表头指针的地址 和 接收要插入的值
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{//改变结构体，要用结构体指针//改变结构体指针，要用结构体指针的指针（二级指针）//因为pphead二级指针存储的是plist指针，//plist指针指向的值可能为空，但指针的地址不能为空//pphead是plist的地址，正常情况下一定不为空assert(pphead);//先使用newnode函数为要尾插的值创建一个结点//并返回该结点地址SLTNode* newnode = BuySListNode(x);//判断phead是否是NULL，如果是说明链表还没开辟过一个结点if (*pphead == NULL){//如果为空，则将上面开辟的newnode结点地址赋给phead*pphead = newnode;//要改变结构体的指针，就要用二级指针//这里pphead是二级指针，存放链表头指针plist的地址//因为如果用一级指针SLTNode* phead的话，//phead形参只是plist实参的临时拷贝，两者空间相互独立//改变phead的话不会改变plist，plist还会是空指针//所以要用二级指针pphead存放plist指针的地址，//*pphead解引用就能得到一级指针plist,//即			*pphead = plist//所以实际上上面的代码就相当于：plist = newnode//这样就让本来指向空指针的头指针指向了新创建的结点指针//链表就能够连接起来}else//不为空则往尾部插入新结点：{//创建另一个指针存放单链表头指针SLTNode* tail = *pphead; //*pphead == plist//使用while循环获得最后一个结点的地址while (tail->next != NULL)//如果下个结点的next指针域不为NULL，//则继续往后找，直到tail等于最后结点的地址{//把当前结点指针域里下个结点的地址给到tail，//进行while循环下次判断：tail = tail->next;}//tail找到最后结点地址后，//把尾插的新结点地址给到tail的next指针域，//连接起链表：tail->next = newnode;//要改变结构体，用结构体的指针即可//因为newnode、tail、pphead都是临时(局部)变量，//所以函数运行结束后都会销毁，//但malloc函数开辟的空间(结点)都在堆上不会销毁//通过解引用二级指针pphead改变plist也没有问题}
}//创建头插函数 -- 
//使用二级指针接收单链表头指针的地址 和 接收要插入的值
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{//因为pphead二级指针存储的是plist指针，//plist指针指向的值可能为空，但指针的地址不能为空//pphead是plist的地址，正常情况下一定不为空assert(pphead);//先使用newnode函数为要头插的值创建一个结点//并返回该结点地址SLTNode* newnode = BuySListNode(x);//因为也要用到链表头指针本身，所以也要使用二级指针//因为plist指向原本头结点地址，//所以可以使用plist把原本头结点地址赋给新插入头结点指针域：newnode->next = *pphead;//再把头指针改为指向新插入头结点：*pphead = newnode;
}//创建尾删函数 --
//使用二级指针接收单链表头指针的地址
void SLTPopBack(SLTNode** pphead)
{//尾删需要考虑三种情况：//注：*pphead 就是 plist//因为pphead二级指针存储的是plist指针，//plist指针指向的值可能为空，但指针的地址不能为空//pphead是plist的地址，正常情况下一定不为空assert(pphead);// 第一种情况：链表为空 -- 没有任何结点//没有结点那就删不了了，使用assert接收到空指针就报警告assert(*pphead);// 第二种情况：链表只有一个结点if ((*pphead)->next == NULL)// -> 也是解引用(结构体的)，优先级比 * 高//所以 *pphead 要用() 括起来{//只有一个结点，又要尾删，那就直接把这唯一的结点删掉：free(*pphead); //直接free释放掉plist指向的结点//再把释放掉的plist置为空指针，防止成为野指针：*pphead = NULL;}else// 第三种情况：链表有一个以上结点{//这种情况额外两个指针，//一个tail指针 -- 用来找到最后一个结点地址并将其释放，//还有一个tailPrev指针 -- 指向tail指针的前一个结点地址，//用来改变该结点的指针域，//防止原本指向tail结点的指针域变成野指针//先替代头指针plist：SLTNode* tail = *pphead;//创建tailPrev指针，//之后操作会指向tail结点的前一个结点，//即倒数第二个结点SLTNode* tailPrev = NULL;//再使用while循环找到尾结点：//和尾插的操作类似while (tail->next != NULL){//tail查找之前先把当前指向结点地址给tailPrev//这样最后tail会指向尾结点，//tailPrev会指向倒数第二个结点tailPrev = tail;tail = tail->next;}//结束while循环后tail指向尾结点地址，//因为是尾删，所以free释放掉tail就可以“删掉”尾结点free(tail);//因为tail是局部（临时）变量，出了函数就销毁，//所以不置为指针也可以，不用担心成为野指针//删除原尾结点后，倒数第二个结点成为尾结点，//要把其指针域next置为空指针，成为链表新结尾tailPrev->next = NULL;}
}//创建头删函数 --
//使用二级指针接收单链表头指针的地址
void SLTPopFront(SLTNode** pphead)
{//因为pphead二级指针存储的是plist指针，//plist指针指向的值可能为空，但指针的地址不能为空//pphead是plist的地址，正常情况下一定不为空assert(pphead);//分两种情况：//第一种情况：链表里没有结点（空链表）//没有结点可以删，直接assert断言pass掉：assert(*pphead);//第二种情况：链表有一个和多个结点（非空链表）//因为是删掉头结点，所以不用考虑找尾结点//所以不用细分一个或多个结点的情况：//这种情况要先通过plist拿到第二个结点的地址：SLTNode* newhead = (*pphead)->next;//使用newhead存储第二个结点地址//拿到第二个结点地址后，再释放掉头结点，//实现头删效果：free(*pphead);//这时要让第二个结点成为新的头结点：*pphead = newhead; //头指针指向原本的第二个结点
}//创建查找函数 --
//查找指定值(x)所在结点的地址
//接收 链表头指针phead、查找值x
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{//像SLTFind和PrintSList函数只用头指针遍历//不改变指针本身就不需要用到二级指针//创建个变量代替头指针：SLTNode* cur = phead;//使用while循环对链表进行遍历查找：while (cur != NULL)//只要cur指针指向地址不为空就继续循环
//while遍历时，(cur->next != NULL) 和 (cur != NULL) 的区别：
//(cur->next != NULL)：这个条件最后cur会是最后结点的地址
//(cur != NULL)：这个条件最后cur会是NULL
//(cur->next != NULL) 会比 (cur != NULL) 少一次循环{//遍历过程中依次查找各结点数据域数据是否与x相同：if (cur->data == x){//找到了一个结点数据域数据是x，返回该结点地址return cur;}//这里如果while循环的条件是(cur->next != NULL)//最后一个结点进不来，不能判断最后结点数据域数据是不是xcur = cur->next; //改变循环条件，指向下个结点}//如果能指向到这说明没找到，返回NULL：return  NULL;
}//创建指定位置插入函数1 -- 
//在链表指定位置(pos)之前插入一个值(x)
//接收 链表头指针地址pphead、指定结点指针pos、插入值x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{//因为pphead二级指针存储的是plist指针，//plist指针指向的值可能为空，但指针的地址不能为空//pphead是plist的地址，正常情况下一定不为空assert(pphead);//第一种情况：空指针//先排除空指针的情况：assert(pos);//第二种情况：头插if (pos == *pphead)// *pphead == plist//如果pos是pphead即第一个指针，//则在第一个指针前插入一个值，相当于头插{//直接复用头插函数SLTPustFront：SLTPushFront(pphead, x);//直接传pphead二级指针过去}else//第三种情况：非头插{//从头开始找pos结点的前一个结点：//先获得头指针SLTNode* prev = *pphead;//当前结点的指针域不是指向pos结点则继续循环while (prev->next != pos){prev = prev->next;}//此时prev已指向pos结点的前一个结点//为要插入的结点创建一个结点newnode：//插入位置是pos结点之前，prev结点之后SLTNode* newnode = BuySListNode(x);//让prev结点指针域指向新插入结点地址：prev->next = newnode;//newnode结点指针域指向pos结点：newnode->next = pos;//此时newnode新结点就插入完成了}
}//创建指定位置插入函数2 --
//在链表指定位置(pos)之后插入一个值(x)
//接收 指定结点指针pos、插入值x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{//因为是在pos结点后插入一个值(结点)//所以不可能会有头插的情况，那就不需要头指针plist//pos指针存储结点地址，可能会接收到空指针//使用assert断言pass掉assert(pos);//先为插入值创建一个新结点newnode：SLTNode* newnode = BuySListNode(x);//先让newnode的指针域next指向后一个结点：//这里后一个结点就是pos结点指针域里的地址//因为未插入前pos就是指向后一个地址newnode->next = pos->next;//再让pos的指针域next指向newnode：pos->next = newnode;
}//创建删除指定结点函数1 --
//在链表删除指定位置(pos)结点
///接收 链表头指针地址pphead、指定结点指针pos
void SLTErase(SLTNode** pphead, SLTNode* pos)
{//因为pphead二级指针存储的是plist指针，//plist指针指向的值可能为空，但指针的地址不能为空//pphead是plist的地址，正常情况下一定不为空assert(pphead);//防止要删的pos结点指针为空指针//使用assert断言：assert(pos);//分两种情况：// 1.头删：if (pos == *pphead)//pos结点 == 头结点 --> 头删{//直接复用SLTPopFront头删函数：SLTPopFront(pphead);}else// 2.非头删：//尾删不用单独分出一种情况，因为还得判断是不是尾结点//直接用通用逻辑删除也可以处理尾删的情况{//从头开始找pos结点的前一个结点：//先获得头指针SLTNode* prev = *pphead;//当前结点的指针域不是指向pos结点则继续循环while (prev->next != pos){prev = prev->next;}//此时prev已指向pos结点的前一个结点//因为要删除pos结点，//所以要让pos前一个和后一个结点连接起来：prev->next = pos->next;//连接成功后再把pos结点释放，实现删除效果：free(pos);}
}//创建删除指定结点函数2 --
//在链表删除指定位置(pos)之后一个结点
//接收 指定结点指针pos
void SLTEraseAfter(SLTNode* pos)
{//删除pos结点后的一个结点，//那么就不可能出现头删的情况，//pos结点是尾结点也没用，//因为尾结点后就没有结点可以删了//使用assert断言处理：assert(pos); //防止接收“空结点”assert(pos->next); //防止接收尾结点//将要删的pos结点的下个结点posNext先保存起来：SLTNode* posNext = pos->next;//再把pos结点和下下个结点连接起来：pos->next = posNext->next;//posNext的指针域next就是pos结点的下下个结点地址//最后释放(删除)posNext结点：free(posNext);
}//创建销毁链表函数：
void SLTDestroy(SLTNode** pphead)
{//因为链表释放后，还要把头指针plist给置为空，//要操作到plist，所以要用到二级指针：//plist指向空链表，pphead也不能为空：assert(pphead);//创建一个指针进行遍历：SLTNode* cur = *pphead;//*pphead == plist//进行遍历释放：while (cur != NULL){//创建一个指针保存下个结点地址：SLTNode* next = cur->next;//释放当前结点：free(cur);//cur指针移向下一个结点：cur = next;}//将链表头指针置为空：*pphead = NULL;
}

            

            

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

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

//链表测试文件：
#define _CRT_SECURE_NO_WARNINGS 1/* 链表学习引入小测试：#include <stdio.h>//重命名一个单链表数据类型
typedef int SLTDataType;
//SLT -- single link table//创建一个单链表结点结构体
typedef struct SListNode
{//结点数据域：SLTDataType data; //结点指针域：//因为是指向单链表结点结构体的指针，//所以是单链表结点结构体类型的指针struct SListNode* next; }SLTNode; //将struct SListNode重命名为SLTNode//创建遍历单链表的函数：接收单链表结点的头指针
void PrintSList(SLTNode* phead)
{//phead头指针指向第一个结点，//之后还要多次使用phead头指针，//所以不要改变phead头指针，//所以可以创建一个和phead头指针一样类型的指针cur代替phead头指针SLTNode* cur = phead;//因为链表到最后结点的指针域为NULL才结束//所以只要cur不为NULL就继续遍历结点进行打印：while (cur != NULL){//通过cur当前指向的结点打印cur里数据域的内容：printf("%d->", cur->data);//通过结点里指针域指向下一个结点，方便打印下个结点的数据域内容cur = cur->next;}//最后提示已指向NULL指针链表，遍历结束：printf("NULL\n");
}int main()
{//创建单链表结点：SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));n1->data = 10; //在该结点数据域存放数据SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));n2->data = 20; //在该结点数据域存放数据SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));n3->data = 30; //在该结点数据域存放数据n1->next = n2; //n1的指针域指向结点n2n2->next = n3; //n2的指针域指向结点n3n3->next = NULL; //n3的指针域指向NULL(结束)PrintSList(n1); //调用函数打印单链表return 0;
}*///包含链表头文件：
#include "SList.h"//测试函数1：测试--PrintSList、BuySListNode函数
void TestList1()
{int n; //存放链表长度//打印提示信息：printf("请输入链表的长度：>");//接收链表长度scanf("%d", &n); //打印提示信息：printf("\n请依次输入每个结点的值：>");SLTNode* plist = NULL; //链表头指针，一开始链表没数据所以为NULL//使用for循环，循环创建结点并赋值，形成链表：for (int i = 0; i < n; i++){int val; //存放结点数据域数据scanf("%d", &val); //接收结点数据域数据//使用BuySListNode函数创建结点并给数据域赋值:SLTNode* newnode = BuySListNode(val);//头插: 使用头插把链表连接起来//把链表头指针plist指向的头结点地址赋给新创建结点的指针域next//这样新结点的指针域next就能指向原来的头结点地址newnode->next = plist;//再把新创建结点的地址赋给头指针，//这样头指针就指向了新创建结点地址，让其成为新的头结点plist = newnode;}//使用PrintSList函数打印链表PrintSList(plist); //接收头指针后打印//使用SLTPushBack函数手动向链表尾部插入数据（尾插）：SLTPushBack(plist, 10000);//再使用PrintSList函数打印插入后的链表PrintSList(plist);//plist和phead都是单链表头指针，//但 plist是实参  phead是形参//phead 是 plist 的一份临时拷贝
}//测试函数2：测试--SLTPushBack、SLTPushFront函数
void TestList2()
{//创建单链表头指针：SLTNode* plist = NULL;//使用尾插随机插入几个值: //(此时头指针指向NULL还没有开辟空间创建结点)SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);//使用头插随机插入几个值：SLTPushFront(&plist, 10);SLTPushFront(&plist, 20);SLTPushFront(&plist, 30);SLTPushFront(&plist, 40);//使用SLTPrintf函数打印该链表：PrintSList(plist);
}//测试函数3：测试--SLTPopBack（尾删）函数
void TestList3()
{//创建单链表头指针：SLTNode* plist = NULL;//使用尾插随机插入几个值: //(此时头指针指向NULL还没有开辟空间创建结点)SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);//使用SLTPrintf函数打印该链表：printf("尾删前链表：\n");PrintSList(plist);//使用尾删函数：SLTPopBack(&plist);//使用SLTPrintf函数打印该链表：printf("尾删后链表：\n");PrintSList(plist);SLTPopBack(&plist);//使用SLTPrintf函数打印该链表：printf("尾删后链表：\n");PrintSList(plist);SLTPopBack(&plist);//使用SLTPrintf函数打印该链表：printf("尾删后链表：\n");PrintSList(plist);SLTPopBack(&plist);//使用SLTPrintf函数打印该链表：printf("尾删后链表：\n");PrintSList(plist);//使用SLTPrintf函数打印该链表：printf("尾删后链表：\n");PrintSList(plist);
}//测试函数4：测试--SLTPopFront（头删）函数
void TestList4()
{//创建单链表头指针：SLTNode* plist = NULL;//使用尾插随机插入几个值: //(此时头指针指向NULL还没有开辟空间创建结点)SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);//使用SLTPrintf函数打印该链表：printf("头删前链表：\n");PrintSList(plist);SLTPopFront(&plist);//使用SLTPrintf函数打印该链表：printf("头删后链表：\n");PrintSList(plist);SLTPopFront(&plist);//使用SLTPrintf函数打印该链表：printf("头删后链表：\n");PrintSList(plist);SLTPopFront(&plist);//使用SLTPrintf函数打印该链表：printf("头删后链表：\n");PrintSList(plist);SLTPopFront(&plist);//使用SLTPrintf函数打印该链表：printf("头删后链表：\n");PrintSList(plist);
}//测试函数5：测试 -- SLTFind函数
void TestList5()
{//创建单链表头指针：SLTNode* plist = NULL;//使用尾插随机插入几个值: //(此时头指针指向NULL还没有开辟空间创建结点)SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);//使用SLTPrintf函数打印该链表：printf("操作前链表：\n");PrintSList(plist);//用SLTFind函数查找链表中数据域为3的结点的地址SLTNode* pos = SLTFind(plist, 1);if (pos != NULL){	//找到了可以对该结点进行修改pos->data *= 10;//所以SLTFind查找函数可以负责查找和修改的操作}printf("操作后链表：\n");PrintSList(plist);
}//测试函数6：测试 -- SLTInsert函数
void TestList6()
{//创建单链表头指针：SLTNode* plist = NULL;//使用尾插随机插入几个值: //(此时头指针指向NULL还没有开辟空间创建结点)SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);//使用SLTPrintf函数打印该链表：printf("操作前链表：\n");PrintSList(plist);//用SLTFind函数查找链表中数据域为3的结点的地址SLTNode* pos = SLTFind(plist, 2);if (pos != NULL){int x; //接收要插入的值scanf("%d", &x); //输入要插入的值SLTInsert(&plist, pos, x); //在2前面插入x }printf("操作后链表：\n");PrintSList(plist);
}//测试函数7：测试 -- SLTInsertAfter函数
void TestList7()
{//创建单链表头指针：SLTNode* plist = NULL;//使用尾插随机插入几个值: //(此时头指针指向NULL还没有开辟空间创建结点)SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);//使用SLTPrintf函数打印该链表：printf("操作前链表：\n");PrintSList(plist);//用SLTFind函数查找链表中数据域为3的结点d的地址SLTNode* pos = SLTFind(plist, 2);if (pos != NULL){int x; //接收要插入的值scanf("%d", &x); //输入要插入的值SLTInsertAfter(pos, x); //在2后面插入x }printf("操作后链表：\n");PrintSList(plist);
}//测试函数8：测试 -- SLTErase函数
void TestList8()
{//创建单链表头指针：SLTNode* plist = NULL;//使用尾插随机插入几个值: //(此时头指针指向NULL还没有开辟空间创建结点)SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);//使用SLTPrintf函数打印该链表：printf("操作前链表：\n");PrintSList(plist);//用SLTFind函数查找链表中数据域为3的结点d的地址SLTNode* pos = SLTFind(plist, 2);if (pos != NULL){int x; //接收要插入的值scanf("%d", &x); //输入要插入的值SLTErase(&plist, pos); //删除pos所在结点//pos结点指针删除（释放）后，要将其置为空：pos = NULL;}printf("操作后链表：\n");PrintSList(plist);
}//测试函数9：测试 -- SLTEraseAfter函数
void TestList9()
{//创建单链表头指针：SLTNode* plist = NULL;//使用尾插随机插入几个值: //(此时头指针指向NULL还没有开辟空间创建结点)SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);//使用SLTPrintf函数打印该链表：printf("操作前链表：\n");PrintSList(plist);//用SLTFind函数查找链表中数据域为3的结点d的地址SLTNode* pos = SLTFind(plist, 2);if (pos != NULL){int x; //接收要插入的值scanf("%d", &x); //输入要插入的值SLTEraseAfter(pos); //删除pos结点的下个结点//pos结点指针删除（释放）后，要将其置为空：pos = NULL;}printf("操作后链表：\n");PrintSList(plist);
}//测试函数10：测试 -- SLTDestroy函数
void TestList10()
{//创建单链表头指针：SLTNode* plist = NULL;//使用尾插随机插入几个值: //(此时头指针指向NULL还没有开辟空间创建结点)SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);//使用SLTPrintf函数打印该链表：printf("操作前链表：\n");PrintSList(plist);SLTDestroy(&plist);
}//主函数：
int main()
{//TestList1();//TestList2();//TestList3();//TestList4();//TestList5();//TestList6();//TestList7();//TestList8();//TestList9();TestList10();return 0;
}