数据结构之单链表（C语言）

数据结构之单链表（C语言）

1 链表的概念2 节点创建函数与链表打印函数2.1 节点创建函数2.2 链表打印函数 3 单链表尾插法与头插法3.1 尾插函数3.2 头插函数 4 单链表尾删法与头删法4.1 尾删函数4.2 头删函数 5 指定位置的插入与删除5.1 在指定位置之前插入数据5.2 在指定位置之后插入数据5.3 删除指定位置节点5.4 删除指定位置之后节点 6 链表数据的查找与链表的销毁6.1 链表数据的查找6.2 链表的销毁 7 单链表全程序及演示结果7.1 SList.h 文件7.2 SList.c 文件7.3 SList_test.c 文件

1 链表的概念

链表是线性表的一种，其物理存储结构上是非连续、非顺序的存储结构，数据元素的逻辑存储结构是通过链表中指针链接次序实现的。即链表中：
（1）物理结构：不是线性的
（2）逻辑结构：一定是线性的
链表是由一个一个节点（结点）构成的，可以类比春运前与春运后火车的车厢数量，每一个车厢都可看作是一个节点，春运时就增加车厢数（节点数）来运送更多乘客（存储更多数据），非春运时就减少车厢数，可保证基本运作即可。
单链表中每一个节点是由两部分组成，第一是该节点所要存储的数据，第二是该节点所指向的下一个节点的指针（地址）。

具体代码如下：

typedef int SLTDataType;typedef struct SListNode{SLTDataType data;struct SListNode* next;//指向下一节点指针//在指向下一节点指针这里，它的类型要用重命名前的结构体类型}SLTNode;

注意，在指向下一节点指针这里，它的类型之所以不能使用重命名后的结构体类型SLTNode是因为在系统读取到该行时还没完成重命名的操作，故只能使用重命名前的名称struct SListNode来定义类型。

2 节点创建函数与链表打印函数

2.1 节点创建函数

在上面我们只是定义了节点的结构，但并没有真正创建节点。故我们自定义一个函数来完成这部分操作。既然要创建节点，那么就需要申请空间，因为此时不同于数组扩容，链表的物理结构并不是连续的，而是可以通过指针将每一个碎片化的节点连接起来，所以直接使用malloc来进行空间申请即可。这一部分与顺序表中的空间检查函数很相似。

//节点创建函数SLTNode* SLTBuyNode(SLTDataType x)//形参部分为data要初始化的值//下一节点部分也不知道指向哪里，先置为NULL即可{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//malloc申请单链表节点空间if (newnode == NULL)//如果申请失败，跳出函数{perror("malloc fail !");exit(1);}//申请成功则进行对应的初始化newnode->data = x;newnode->next = NULL;//指向下一节点部分置为空return newnode;//将创建的节点作为返回值返回到调用处}

2.2 链表打印函数

在上文中我们已知，链表是靠指针来完成次序的连接，其无法做到任意访问，而是必须先访问前一个节点后再去访问后一个节点。比如，我们将第一个节点所对应的节点地址设为phead，那么下一个节点就是phead->next，再后面一个节点为phead->next->next，以此类推。
在上面的那种访问方式中，当我们要访问第n个节点时，phead后面会跟（n-1）个next。如此就显得非常冗余，所以我们可以另辟蹊径，用一个临时节点来做为过度节点（我们设为pcur），将链表的头节点赋值给pcur，然后通过循环让pcur不断指向后面的next完成对链表的遍历。实现如下：

 SLTPrint(SLTNode* phead){SLTNode* pcur = phead;//通过一个过渡节点的嫁接转换完成对链表的遍历访问while (pcur)//等价于pcur != NULL{printf("%d->", pcur->data);pcur = pcur->next;}//如果传过来的本来就是空节点，那么就无法进入循环，打印为空printf("NULL\n");}

3 单链表尾插法与头插法

3.1 尾插函数

在原链表之尾插入一个新的节点，首先我们要调用节点创建函数建立一个新的节点，然后对原链表进行遍历找尾，最后将尾节点的next指向新创建的节点即可。
请审读下面尾插函数，分析其是否存在问题。

SLTNode* PushBack(SLTNode* phead, SLTDataType x){//判断传参是否为空assert(phead);//创建要尾插的节点SLTNode* newnode = SLTBuyNode(x);//找尾SLTNode* ptail = phead;//思考此处循环判断条件应该是什么while (ptail->next)//若将ptail != NULL 设置为条件，当循环到尾节点时，此时不为空，会继续到后面的空节点，而此时这个空节点就不是链表的尾节点了。//故应设置为ptail->next != NULL，当循环到尾节点时，ptail->next == NULL 跳出循环，然后再将ptail->next赋值为newnode即完成尾插。{ptail = ptail->next;//没找到尾节点就不断向后遍历}ptail->next = newnode;}

上面尾插程序看似十分完美，其实存在两点严重的问题：

当链表为空链表时，phead与ptail都会成为空指针NULL，那么在while中的条件判断就成为了对空指针解引用的非法访问。在尾插函数中，我们想通过修改形参中的链表来完成实参中链表的修改，那么在形参中可以用一级指针接收传参吗？用一级指针接收传参可以保证实参改变吗？

我们先来解决第一个问题，既然有空链表的这种情况，那么就使用一个条件分支来区别二者（空链表与非空链表）。

void PushBack(SLTNode* phead, SLTDataType x){//判断传参是否为空assert(phead);//创建要尾插的节点SLTNode* newnode = SLTBuyNode(x);//空链表与非空链表区分if (phead == NULL){phead = newnode;}else{//找尾SLTNode* ptail = phead;//思考此处循环判断条件应该是什么while (ptail->next)//若将ptail != NULL 设置为条件，当循环到尾节点时，此时不为空，会继续到后面的空节点，而此时这个空节点就不是链表的尾节点了。//故应设置为ptail->next != NULL，当循环到尾节点时，ptail->next == NULL 跳出循环，然后再将ptail->next赋值为newnode即完成尾插。{ptail = ptail->next;//没找到尾节点就不断向后遍历}ptail->next = newnode;}}

然后我们再来解决第二个问题，形参如果想要影响实参的内容，我们传参时就要传地址而不是传数值（即使用传址调用）。测试文件中内容如下：

void Test01(){SLTNode* plist = NULL;SLTDataType x = 1;PushBack(plist, x);SLTPrint(plist);}int main(){Test01();return 0;}

在传参时我们是将plist作为实参，而plist是一个一级指针，其存储的是后面的空地址NULL。所以在传参时phead所接收的是plist所指向的NULL，属于传值调用。在前面函数已经讲过，传值调用时函数会在栈区开创栈帧空间来存储形参及函数内参数，也就是在栈帧空间内某一块空间被置为NULL，然后再由phead来存储。此时无论phead怎么改变，都与原来的plist毫无关系了，形参也就无法影响实参了。
所以在传参时我们不能传plist（等于传值），而是要传plist的地址（&plist）。相应的，因为传递的是一级指针的地址，所以在形参部分接收头节点的形参要使用二级指针（我们将其命名为pphead）。
最终尾插函数如下：

void PushBack(SLTNode** pphead, SLTDataType x){//判断传参是否为空assert(pphead);//创建要尾插的节点SLTNode* newnode = SLTBuyNode(x);//空链表与非空链表区分if (*pphead == NULL)//等同于原来 phead == NULL。也等同于plist == NULL{*pphead = newnode;//等同于原来的phead == newnode。也等同于plist == newnode}else{//找尾SLTNode* ptail = *pphead;//思考此处循环判断条件应该是什么while (ptail->next)//若将ptail != NULL 设置为条件，当循环到尾节点时，此时不为空，会继续到后面的空节点，而此时这个空节点就不是链表的尾节点了。//故应设置为ptail->next != NULL，当循环到尾节点时，ptail->next == NULL 跳出循环，然后再将ptail->next赋值为newnode即完成尾插。{ptail = ptail->next;//没找到尾节点就不断向后遍历}ptail->next = newnode;}}

在经过上面修改后，传参时一级指针的地址&plist作为实参，形参处的二级指针pphead来接收实参，形参实例化后开创栈帧来存储一级指针地址&plist，后续我们对pphead解引用操作时（*pphead），操作的就是测试文件中的一级指针plist，完成形参改变实参的操作。

3.2 头插函数

在原链表之头插入一个节点，我们在调用节点创建函数后只需要将新节点newnode->next赋值为存储链表头节点地址的一级指针plist，然后再将一级指针newnode赋值给plist就完成了头节点的转换。
具体如下：

void PushFront(SLTNode** pphead, SLTDataType x){//判断传参是否为空assert(pphead);//创建要尾插的节点SLTNode* newnode = SLTBuyNode(x);//进行头插newnode->next = *pphead;//将新节点next指向原头节点的地址*pphead = newnode;//将原头节点的地址更改为新节点的地址}

4 单链表尾删法与头删法

4.1 尾删函数

我们先来思考一下，能否从头遍历链表后直接free掉尾节点？
答案肯定是不能的。链表的每一节点间都通过next指针相连，若直接free掉尾节点，那么尾节点前面一个节点的next指针就会指向一块未初始化的空间，成为野指针。所以我们需要定义两个指针，一个是尾节点ptail，另一个是尾节点前面一个节点prev，free掉尾节点后，将ptail置为NULL，再将prev->next置为NULL。

void PopBack(SLTNode** pphead){//不仅要判断参数是否为空，还要判断是否为空链表。assert(pphead && *pphead);//定义需要使用的两个节点指针SLTNode* prev = *pphead;SLTNode* ptail = *pphead;//遍历单链表找尾while (ptail->next){//寻找尾节点和其前一个节点prev = ptail;ptail = ptail->next;}free(ptail);//释放空间后将两处置为NULLptail = NULL;prev->next = NULL;}

在上面的逻辑中，情况是否全面不妨和前面一样，使用极端情况来检验。空链表的情况下会被assert断言发现，故被排除。那在只有一个节点时呢？因为ptail->next为空，故不进入循环。直接free并置为NULL，所以ptail与prev都为NULL。但是后面prev->next却又对空指针进行了非法访问，造成出错。故应在逻辑中分为链表只有一个节点和有多个节点。一个节点时直接free并置空，多个节点使在执行上面程序。
最终程序如下：

void PopBack(SLTNode** pphead)//与前面一样，为了形参能改变实参，使用二级指针来接收头节点指针地址{//不仅要判断参数是否为空，还要判断是否为空链表。assert(pphead && *pphead);//定义需要使用的两个节点指针SLTNode* prev = *pphead;SLTNode* ptail = *pphead;//链表有一个节点if ((*pphead)->next == NULL)// -> 优先级高于 *{free(*pphead);*pphead = NULL;}//链表有多个节点else{//遍历单链表找尾while (ptail->next){//寻找尾节点和其前一个节点prev = ptail;ptail = ptail->next;}free(ptail);//释放空间后将两处置为NULLptail = NULL;prev->next = NULL;}}

4.2 头删函数

删掉单链表头节点只需要将头节点的next指针指向地址保留下来，释放头节点空间，然后将方才保留的地址转换为头节点地址即可。

void PopFront(SLTNode** pphead){//不仅要判断参数是否为空，还要判断是否为空链表。assert(pphead && *pphead);//保留头节点next节点指针SLTNode* next = (*pphead)->next;free(*pphead);//将保留的节点指针作为头节点指针，完成头节点转换*pphead = next;}

5 指定位置的插入与删除

5.1 在指定位置之前插入数据

在指定位置之前插入数据，首先我们思考一下，指定位置若是头节点，此时其就是头插法插入（特殊情况）。除此之外，我们若在指定位置之前直接插入新节点，那么指定位置之前原来的节点就会与pos节点断开。所以我们需要找到前一个节点地址，将前一个节点next指针指向newnode，newnode->next指向pos节点，如此完成连接。
具体见下：

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x){//双判空assert(pphead && *pphead);//插入值判空assert(pos);SLTNode* newnode = SLTBuyNode(x);//若 pos == *pphead ，说明是头插if (pos == *pphead){PushFront(pphead, x);}else//非头插，将前一个节点prev与newnode连接，newnode与pos连接{SLTNode* prev = *pphead;//寻找pos前一个节点while (prev->next != pos){prev = prev->next;}//节点连接newnode->next = pos;prev->next = newnode;}}

5.2 在指定位置之后插入数据

在指定位置之后插入数据我们通过前文的讲述，自然会先考虑到尾插的情况，在pos 在尾节点时，pos->next == NULL，我们将pos->next直接赋值给newnode->next，然后将pos与newnode连接即可（pos->next==newnode）。在尾插情况之外，通过上面的连接操作同样可以完成插入数据，故不需要使用条件分支。
具体见下：

void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x){//双重判空assert(pphead && *pphead);assert(pos);SLTNode* newnode = SLTBuyNode(x);//进行插入操作//将pos节点的下一个节点地址赋值给新节点 newnode 的 next 指针newnode->next = pos->next;//将pos节点的next指针指向新节点newnodepos->next = newnode;}

5.3 删除指定位置节点

在pos节点为头结点，此时删除操作符合头删法，即调用头删函数即可。除此情况之外，我们需要将pos前一个节点与后一个节点连接后再释放pos节点。
具体见下：

//删除指定位置pos节点void SLTErase(SLTNode** pphead, SLTNode* pos){assert(pphead && *pphead);assert(pos);//若 pos == *pphead，此时就是头删法删除if (pos == *pphead){PopFront(pos);}else//删除指定位置节点需要我们将pos之前与pos之后的节点连接起来{SLTNode* prev = *pphead;//寻找pos前一个节点while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}}

5.4 删除指定位置之后节点

与前面操作如出一辙，我们将pos与其后两个节点连接，最后再释放pos后一个节点置空即可。但在此处我们需要考虑pos是不是尾节点，即pos->next是否等于NULL。
具体见下：

void SLTEraseAfter(SLTNode** pphead, SLTNode* pos){assert(pphead && *pphead);//判断传参 pos 是否为空以及 pos 是不是最后一个节点assert(pos && pos->next);//先将pos之后的节点用del存储下来SLTNode* del = pos->next;//将pos与pos后第二个节点连接起来pos->next = del->next;//pos->next = pos->next->nextfree(del);del = NULL;}

6 链表数据的查找与链表的销毁

6.1 链表数据的查找

与顺序表的查找如出一辙，对整个链表遍历即可。找到就返回该节点，没找到就返回NULL。

SLTNode* SLTFind(SLTNode* phead, SLTDataType x){SLTNode* pcur = phead;//查找节点while (pcur){//找到节点直接返回if (pcur->data == x){return pcur;}//没找到向后遍历pcur = pcur->next;}//遍历后不存在，返回空表示没找到return NULL;}

6.2 链表的销毁

在对链表每个节点释放之前，我们需要先保留该节点的next指针的指向，从而能够销毁后续节点。

void SLTDestroy(SLTNode** pphead){assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){//定义 next节点以保留pcur->next的指向SLTNode* next = pcur->next;free(pcur);//将保留的next节点赋值给pcur，进而下一循环销毁后续节点pcur = next;}//全部销毁后将链表置为空*pphead = NULL;}

7 单链表全程序及演示结果

7.1 SList.h 文件

#pragma once#include<stdio.h>#include<stdlib.h>#include<assert.h>//类型重命名typedef int SLTDataType;//定义节点结构//数据 + 指向下一节点指针typedef struct SListNode{SLTDataType data;struct SListNode* next;//指向下一节点指针//在指向下一节点指针这里，它的类型要用重命名前的结构体类型}SLTNode;//节点创建函数SLTNode* SLTBuyNode(SLTDataType x);//链表打印函数void SLTPrint(SLTNode* phead);//尾插函数void PushBack(SLTNode** pphead, SLTDataType x);//头插函数void PushFront(SLTNode** pphead, SLTDataType x);//尾删函数void PopBack(SLTNode** pphead);//头删函数void PopFront(SLTNode** pphead);//在指定位置之前插入数据void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在指定位置之后插入数据void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);//删除pos节点void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos之后节点void SLTEraseAfter(SLTNode** pphead, SLTNode* pos);//链表的查找SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//销毁链表void SLTDestroy(SLTNode** pphead);

7.2 SList.c 文件

#include"SList.h"//节点创建函数SLTNode* SLTBuyNode(SLTDataType x)//形参部分为data要初始化的值//下一节点部分也不知道指向哪里，先置为NULL即可{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//malloc申请单链表节点空间if (newnode == NULL)//如果申请失败，跳出函数{perror("malloc fail !");exit(1);}//申请成功则进行对应的初始化newnode->data = x;newnode->next = NULL;//指向下一节点部分置为空return newnode;//将创建的节点作为返回值返回到调用处}//链表的打印void SLTPrint(SLTNode* phead){SLTNode* pcur = phead;//通过一个过渡节点的嫁接转换完成对链表的遍历访问while (pcur)//等价于pcur != NULL{printf("%d->", pcur->data);pcur = pcur->next;}//如果传过来的本来就是空节点，那么就无法进入循环，打印为空printf("NULL\n");}//链表的尾插法void PushBack(SLTNode** pphead, SLTDataType x){//判断传参是否为空assert(pphead);//创建要尾插的节点SLTNode* newnode = SLTBuyNode(x);//空链表与非空链表区分if (*pphead == NULL){*pphead = newnode;}else{//找尾SLTNode* ptail = *pphead;//思考此处循环判断条件应该是什么while (ptail->next)//若将ptail != NULL 设置为条件，当循环到尾节点时，此时不为空，会继续到后面的空节点，而此时这个空节点就不是链表的尾节点了。//故应设置为ptail->next != NULL，当循环到尾节点时，ptail->next == NULL 跳出循环，然后再将ptail->next赋值为newnode即完成尾插。{ptail = ptail->next;//没找到尾节点就不断向后遍历}ptail->next = newnode;}}//链表的头插法void PushFront(SLTNode** pphead, SLTDataType x){//判断传参是否为空assert(pphead);//创建要尾插的节点SLTNode* newnode = SLTBuyNode(x);//进行头插newnode->next = *pphead;//将新节点next指向原头节点的地址*pphead = newnode;//将原头节点的地址更改为新节点的地址}//链表的尾删法 void PopBack(SLTNode** pphead){//不仅要判断参数是否为空，还要判断是否为空链表。assert(pphead && *pphead);//定义需要使用的两个节点指针SLTNode* prev = *pphead;SLTNode* ptail = *pphead;//链表有一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//链表有多个节点else{//遍历单链表找尾while (ptail->next){//寻找尾节点和其前一个节点prev = ptail;ptail = ptail->next;}free(ptail);//释放空间后将两处置为NULLptail = NULL;prev->next = NULL;}}//链表的头删法void PopFront(SLTNode** pphead){//不仅要判断参数是否为空，还要判断是否为空链表。assert(pphead && *pphead);//保留头节点next节点指针SLTNode* next = (*pphead)->next;free(*pphead);//将保留的节点指针作为头节点指针，完成头节点转换*pphead = next;}//在指定位置之前插入数据void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x){//双判空assert(pphead && *pphead);//插入值判空assert(pos);SLTNode* newnode = SLTBuyNode(x);//若 pos == *pphead ，说明是头插if (pos == *pphead){PushFront(pphead, x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}newnode->next = pos;prev->next = newnode;}}//在指定位置之后插入数据void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x){//双重判空assert(pphead && *pphead);assert(pos);SLTNode* newnode = SLTBuyNode(x);//进行插入操作//将pos节点的下一个节点地址赋值给新节点 newnode 的 next 指针newnode->next = pos->next;//将pos节点的next指针指向新节点newnodepos->next = newnode;}//删除指定位置pos节点void SLTErase(SLTNode** pphead, SLTNode* pos){assert(pphead && *pphead);assert(pos);//若 pos == *pphead，此时就是头删法删除if (pos == *pphead){PopFront(pos);}else//删除指定位置节点需要我们将pos之前与pos之后的节点连接起来{SLTNode* prev = *pphead;//寻找pos前一个节点while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}}//删除指定位置之后的节点void SLTEraseAfter(SLTNode** pphead, SLTNode* pos){assert(pphead && *pphead);//判断传参 pos 是否为空以及 pos 是不是最后一个节点assert(pos && pos->next);//先将pos之后的节点用del存储下来SLTNode* del = pos->next;//将pos与pos后第二个节点连接起来pos->next = del->next;//pos->next = pos->next->nextfree(del);del = NULL;}//销毁链表void SLTDestroy(SLTNode** pphead){assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){//定义 next节点以保留pcur->next的指向SLTNode* next = pcur->next;free(pcur);//将保留的next节点赋值给pcur，进而下一循环销毁后续节点pcur = next;}//全部销毁后将链表置为空*pphead = NULL;}//链表的查找SLTNode* SLTFind(SLTNode* phead, SLTDataType x){SLTNode* pcur = phead;//查找节点while (pcur){//找到节点直接返回if (pcur->data == x){return pcur;}//没找到向后遍历pcur = pcur->next;}//遍历后不存在，返回空表示没找到return NULL;}

7.3 SList_test.c 文件

#include"SList.h"void Test01(){SLTNode* plist = NULL;SLTDataType x = 1;PushBack(&plist, x);PushBack(&plist, 2);PushBack(&plist, 3);PushBack(&plist, 4);PushBack(&plist, 5);SLTPrint(plist);SLTNode* find = SLTFind(plist, 3);if (find == NULL){printf("没有找到！\n");}else{printf("找到了！\n");}}int main(){Test01();return 0;}

运行结果：

全文至此结束！！！
写作不易，不知各位老板能否给个一键三连或是一个免费的赞呢(▽)(▽)，这将是对我最大的肯定与支持！！！谢谢！！！(▽)(▽)