C语言数据结构（3）单链表专题1.单链表概述

1. 链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。

链表的结构跟火车车厢相似，淡季时车划次的车厢会相应减少，旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上，不会影响其他车厢，每节车厢都是独立存在的。

车厢是独立存在的，且每节车厢都有车门。想象一下这样的场景，假设每节车厢的车门都是锁上的状态，需要不同的钥匙才能解锁，每次只能携带一把钥匙的情况下如何从车头走到车尾？

最简单的做法：每节车厢里都放一把下一节车厢的钥匙。

在链表里，每节“车厢”是什么样的呢？

与顺序表不同的是，链表里的每节"车厢"都是独立申请下来的空间，我们称之为“结点/节点”。

结点的组成主要有两个部分：当前结点要保存的数据、下一个结点的地址（指针变量）。

数据域+指针域——数据密度比顺序表低，随机访问速度比顺序表低。

图中指针变量 plist 保存的是第一个节点的地址，我们称plist此时“指向”第一个节点，如果我们希望plist“指向”第二个节点时，只需要修改plist保存的内容为0x0012FFA0。

为什么还需要指针变量来保存下一个节点的位置？

链表中每个节点都是独立申请的（即需要插入数据时才去申请一块节点的空间），我们需要通过指针变量来保存下一个节点位置才能从当前节点找到下一个节点。

（每个存储单元在物理上随机分布，需要在逻辑上使用一条“链条”把分散分布的各个存储空间连成一条线，方便访问）

结合前面学到的结构体知识，我们可以给出每个节点对应的结构体代码：

假设当前保存的节点为整型：

struct SListNode
{int data;                 //节点数据——数据域struct SListNode* next;   //指针变量⽤保存下⼀个节点的地址——指针域
};

当我们想要从第一个节点走到最后一个节点时，只需要在前一个节点拿上下一个节点的地址（下一个节点的钥匙）就可以了。

给定的链表结构中，如何实现节点从头到尾的打印？

思考：当我们想保存的数据类型为字符型、浮点型或者其他自定义的类型时，该如何修改？

补充说明：

1、链式机构在逻辑上是连续的，在物理结构上不一定连续

2、节点一般是从堆上申请的

3、从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续

2. 单链表的实现

2.1 头文件代码

这里只有一个结点类型，那么链表的维护就依赖于一个结点类型的指针。

也可以选择新建一个链表类型，这个结构体类型内部维护链表头结点地址、链表数据量等信息。

用结点类型的指针去维护一个链表——那么函数会改变链表头时，就需要传递二级指针。

用链表结构体类型去维护一个链表——那么函数会改变链表头时，就需要传递链表类型的地址——一级指针。

//单链表
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//重定义链表存储的数据类型
typedef int SLTDataType;//定义链表结点类型
typedef struct SListNode			//链表是由节点(Node)组成
{SLTDataType data;struct SListNode* next;
}SLTNode;//typedef struct SListNode SLTNode;//链表的打印
void SLTPrint(SLTNode* phead);//链表的头插、尾插、头删、尾删都一样：有可能会改变phead
//（即存在*pphead = ?形式的赋值表达式），函数参数就必须是pphead——二级指针//链表的头插、尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//链表的头删、尾删
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x);//可以使用一级指针，但是考虑到保持接口的一致性//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//要保证pos不为空——即不会改变头节点//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);//需要前驱节点，就需要头节点（因为是单链表：只有指向后节点的指针，没有指向前节点的指针，能找后不能找前）
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);//参数只需当前节点//销毁链表
void SListDesTroy(SLTNode** pphead);

//Single_Linked_List.c
void SLTPrint(SLTNode* phead);

//Single_Linked_List.c
#include"SeqList.h"//链表的打印
void SLTPrint(SLTNode* phead) 
{//使用pcur代替phead来移动，保证之后的操作需要phead时能够使用//否则phead移动到链表末尾NULL，就找不到这个链表了，phead要用于维护这个链表SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);		//打印：访问每个结点都是以指针的形式去访问pcur = pcur->next;				//迭代：结点指针的迭代}printf("NULL\n");
}                             

 （2）头插、尾插

函数声明。

//链表的头插、尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);

① 尾插

逻辑梳理

实现尾插

功能相对独立的、在不同函数中多次出现的代码，可以单独封装成一个函数，而不必在头文件中声明。

//链表新节点的申请——两步走：1.动态内存开辟；2.赋数据+赋空指针
SLTNode* SLTBuyNode(SLTDataType x) {SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL) {perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}//链表的尾插——向pphead插入数据 x（三步走：两步走 +  把newnode赋值给pphead / ptail）
void SLTPushBack(SLTNode** pphead, SLTDataType x) //二级指针pphead！！！！！如果只是一级指针，则传入空指针尾插后，链表的首节点还是NULL
{	assert(pphead);//创建新节点——两步走：申请+判断、结点赋值SLTNode* newnode = SLTBuyNode(x);    //功能相对独立的、在不同函数中多次出现的代码，可以单独封装成一个函数，而不必在头文件中声明//情况1：链表pphead为空//则第三步：新节点作为ppheadif (*pphead == NULL) {*pphead = newnode;return;}//情况2：链表不为空://则第三步：从头开始找尾节点，然后给尾结点的指针域赋值，形成新的尾节点SLTNode* ptail = *pphead;	//创建变量获取头节点，代替头结点去迭代找尾节点//while (ptail)while (ptail->next)			//循环找尾节点：尾结点的特点是ptail->next=NULL；而不是ptail = NULL{ptail = ptail->next;					}//ptail就是尾节点——第三步：给尾节点的指针域赋值ptail->next = newnode;
}

测试尾插

测试错误的尾插代码。

测试正确的尾插代码。

单链表由一个结点指针来维护，其初始化只需要给这个结点指针置空就可以了。

极端测试。

SLTPushBack(NULL, 5);    //倒逼代码实现增加健壮性判断

② 头插

逻辑梳理

实现头插

不需要找尾节点，创建好新结点，直接修改结点关系即可。

//链表的头插——四步走：
//①结点创建两步走
//②给新结点的指针域赋值（把pphead赋给newnode->next）
//③表头更换——给链表维护指针phead赋值（把newnode赋值给*pphead）
void SLTPushFront(SLTNode** pphead, SLTDataType x) 
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);//newnode和*pphead的关系newnode->next = *pphead;*pphead = newnode;
}

测试头插

（3）头删、尾删 

函数声明。

//链表的头删、尾删
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);

① 尾删

逻辑梳理

实现尾删

//链表的尾删——两步走：销毁 + 置空
void SLTPopBack(SLTNode** pphead) {assert(pphead);//链表不能为空assert(*pphead);//链表不为空//情况1：链表只有一个节点//两步走：释放该节点、维护链表的指针置空if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return;}//情况2：链表有多个节点//三步走：找尾节点+释放尾节点+尾结点的前置节点的指针域置空，形成新的尾节点//定义尾节点(地址)SLTNode* ptail = *pphead;//定义次尾节点(地址)//把ptail那部分空间释放掉，则那部分空间的地址ptail和prev->next就要置空，避免野指针SLTNode* prev = NULL;//找尾节点——过程中保存尾结点的前置结点while (ptail->next){prev = ptail;ptail = ptail->next;}//置空次尾节点的指针域，使之成为尾节点prev->next = NULL;//销毁尾结点——空间释放，置空尾节点（地址）free(ptail);ptail = NULL;
}

测试尾删

测试正确的尾插代码。

② 头删

逻辑梳理

实现头删

//链表的头删——两步走
void SLTPopFront(SLTNode** pphead) {assert(pphead);//链表不能为空assert(*pphead);//让第二个节点成为新的头//把旧的头结点释放掉//*pphead = (*pphead)->next;        //错误写法//free(*pphead);SLTNode* next = (*pphead)->next;    //->的优先级高于*free(*pphead);*pphead = next;
}

测试头删

（4）查找

函数声明

//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x);//可以使用一级指针，但是考虑到保持接口的一致性

思想：直接for循环遍历查找。——找到了，则返回对应的结点指针；否则返回空指针。

实现代码

//SeqList.c
//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x) {assert(pphead);//遍历链表SLTNode* pcur = *pphead;while (pcur) //等价于pcur != NULL{if (pcur->data == x) {return pcur;}pcur = pcur->next;}//没有找到return NULL;
}

测试代码

（5）在指定位置插入

函数声明

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//要保证pos不为空——即不会改变头节点

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

逻辑梳理

实现在指定位置之前插入数据

//在指定位置之前插入数据——一断连，两重连
//pos：链表中某个节点的地址
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(pos);//直觉上好像链表可以为空，但是要加上链表不能为空——因为pos不为空，则链表必不为空assert(*pphead);SLTNode* newnode = SLTBuyNode(x);//pos刚好是头结点if (pos == *pphead) {//头插SLTPushFront(pphead, x);        //这里若手动写，则头插/尾插都可调用本函数return;}//pos不是头结点的情况，找pos的前驱结点SLTNode* prev = *pphead;while (prev->next != pos)//prev->next 永不为头节点 pos（若POS为头节点则死循环）{prev = prev->next;}//prev -> newnode -> posprev->next = newnode;        newnode->next = pos;        //这两句位置可互换
}

最后两句位置可以互换。 

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

逻辑梳理

实现在指定位置之后插入数据

找前驱结点需要循环找。

找后继结点直接就可以拿到。

//在指定位置之后插入数据——两重连
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode = SLTBuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;pos->next = newnode;            //这两句位置不能交换
}

最后两句的位置不能互换。 

测试指定插入——实践中可以先使用查找函数找某个值的节点指针，再在这个节点指针前/后插入数据。

（6）删除指定位置的节点

思想：让当前节点的前驱结点，指向，当前结点的后继结点。先改指向再释放

 函数声明

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//需要前驱节点，就需要头节点（因为是单链表：只有指向后节点的指针，没有指向前节点的指针，能找后不能找前）

逻辑梳理 

实现代码

找前驱节点：prev->next != pos

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead);assert(*pphead);assert(pos);//pos刚好是头结点，没有前驱节点，执行头删if (*pphead == pos) {//头删SLTPopFront(pphead);return;}SLTNode* prev = *pphead;while (prev->next != pos)    //存在无效的pos位置，然后死循环的bug{prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;                //应该先改指向，再释放
}

存在无效的pos位置，然后死循环的bug。 

本代码假设传递的pos位置除了NULL，都是有效的——因为是SLTFind函数的返回值。

测试代码

总结

对pos位置的结点进行操作——插入、删除，需要传递头结点，因为有了pos位置无法找到pos位置的前驱结点，需要从头结点开始逐步遍历到pos位置的前驱结点。

（7）删除指定位置之后的数据

思想：让当前节点，指向，当前结点的后继结点的后继结点。先改指向再释放，改指向前先保存

 函数声明

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);//参数只需当前节点

逻辑梳理  

实现代码

//删除pos之后的节点
//1.释放pos->next；
//2.把pos->next->next赋给pos->next
//（先释放无法赋值——找不到下下块空间用于赋值，先赋值无法释放——找不到下一块空间将其释放）
//故此需要创建一个临时变量暂时保存pos->next空间，改完指向后，再释放+置空
void SLTEraseAfter(SLTNode* pos) {assert(pos);//pos->next不能为空——断言不能为尾结点assert(pos->next);//pos  pos->next  pos->next->nextSLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}

测试代码

总结

对pos位置之后的结点进行操作——插入、删除，都不需要传递头结点，因为有了pos位置就能找到pos位置的后继结点。

（8）销毁

思想：逐结点地去释放——释放前保存下一结点，释放后当前结点进行迭代。

 函数声明

//销毁链表
void SListDesTroy(SLTNode** pphead);

逻辑梳理  

实现代码

//销毁链表
void SListDesTroy(SLTNode** pphead) {assert(pphead);assert(*pphead);//创建遍历变量pcurSLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;//释放和赋值的不兼容问题——创建临时变量·保存释放值——！！！在销毁pcur之前，使用next先保存下一个待销毁空间，避免找不到下一块待销毁的空间free(pcur);pcur = next;}*pphead = NULL;
}

链表相比于顺序表，每个结点都是独立存在的，空间也是不连续的，只能一个一个地去销毁。

测试代码

3. 链表的分类

链表的结构非常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构：

链表说明

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

（1）单链表——Single Linked List（不带头、单向、不循环，链表）

（2）双链表——Double Linked List（带头、双向、循环，链表）

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表：结构最复杂，功能最全面，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

掌握这两种结构后，其余6种就可以推而广之了。 

完