当前位置：首页 > news >正文

笔记六：链表介绍与模拟实现

news 2025/5/10 9:32:20

在他一生中，从来没有人能够像你们这样，以他的视角看待这个世界。

---------《寻找天堂》

一、什么是链表？

二、为什么要使用链表？

三、链表介绍与使用

3.1 单链表

3.1.1 创建单链表节点

3.1.2 单链表的头插、尾插

单链表的尾插

单链表的头插

打印单链表

3.1.3 单链表的头删、尾删

单链表的尾删编辑

单链表的头删

3.1.4 链表节点的查找

3.1.5 在指定位置插入数据

在指定位置前插入数据

在指定位置之后插入数据

3.1.6 删除pos之后的节点

3.1.7 销毁链表

3.2 双向链表

3.2.1 双向循环链表节点的创建

双向循环链表节点的初始化

3.2.2 双向循环链表的头插、尾插

双向循环链表的尾插

双链表的头插

双链表的打印

3.2.3 双向循环链表的头删、尾删

双向循环链表的头删

双向循环链表的尾删

3.2.4 链表查找找元素位置

3.2.5 在任意位置插入

在pos之前插入

3.2.6 在pos位置之后的插入

3.2.6 链表的销毁

3.3 各种链表的示意图

四、完整代码

SList.h

SList.c

List.h

List.c

一、什么是链表？

链表是一种物理存储上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现的一种线性存储结构。链表由一系列节点（链表中每一个元素称为节点）组成，节点在运行时动态生成（malloc），每个节点包括两个部分：

一个是存储数据元素的数据域
另一个是存储下一个节点地址的指针域

二、为什么要使用链表？

使用链表用于解决动态数量的数据存储。比如说，我们要管理一堆票据，可能有一张，但也可能有一亿张。怎么办呢？申请一个几十G的大数组存储着吗？万一用户只有一百张票据要处理呢？内存较小拒绝运行？可申请少了又不够用啊……

而且，用数组的话，删除然后添加票据，是每次删除让后面五百万张往前移一格呢、还是每次添加从头搜索空闲格子？如何区分空闲格子和值为0的数据？要进行区分的话是多占用空间呢还是占用数据值域？占用了值域会不会使得数据处理变得格外复杂？会不会一不小心就和正常数据混淆？万一拿来区分的字段在某个版本后废弃不用、或者扩充值域了呢？

那么，链表这种东西就是个很有效的数据结构，可以很有效的管理这类不定量的数据。

三、链表介绍与使用

3.1 单链表

单链表的每个节点除了存放数据元素外，还要存储指向下一个节点的指针。与顺序表进行对比：

	优点	缺点
顺序表	可随机存储，存储密度较高	要求大片连续空间，改变容量不方便
单链表	不要求大片连续空间，改变容量方便	不可随机存取，要耗费一定空间存放指针

3.1.1 创建单链表节点

typedef int SLTDataType;
//链表是由节点构成
//逻辑结构：一定连续；物理结构：不一定连续
//不会造成空间的浪费，由独立的节点构成
typedef struct SListNode {  //SList : single linked list 单链表SLTDataType data;  //  一个是存储数据元素的数据域struct SListNode* next;  //   另一个是存储下一个节点地址的指针域
}SLTNode;

上面的结构体仅是单链表节点的定义，要创建一新的节点需要对里面的数据进行初始化：插入数值，节点指向的下一个节点为空

//创建一个节点
struct SListNode* SLTBuyNode(SLTDataType x) {SLTNode* newnode = (struct SListNode*)malloc(sizeof(struct SListNode));newnode->data = x;newnode->next = NULL;return newnode;
}

3.1.2 单链表的头插、尾插

单链表的尾插

这里传递的链表节点的参数，为什么是二级指针呢？

在初始化过程中，需要修改头指针，因此要用到二级指针传递头指针的地址，这样才能修改头指针。这与普通变量类似，当需要修改普通变量的值，需传递其地址。使用二级指针，很方便就修改了传入的结点一级指针的值。如果用一级指针，则只能通过指针修改指针所指内容，却无法修改指针的值，也就是指针所指的内存块。

//链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) { //一级指针传递的为结构体变量地址的值，二级指针接收的是指向结构体变量的指针的地址assert(pphead);SLTNode* newnode = SLTBuyNode(x);//链表为空，新节点作为ppheadif (*pphead == NULL) {*pphead = newnode;return;}//链表不为空，链表的尾指向新节点SLTNode* ptail = *pphead;while (ptail->next) {ptail = ptail->next;}ptail->next = newnode;
}

单链表的头插

void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);//链表为空，新节点指向pphead，pphead再指向新节点；链表不为空，新节点指向pphead，pphead再指向新节点SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}

打印单链表

插入完数据后，想要打印以一下链表的数据，通过从头开始一个一个节点地访问数据，并打印，便实现了链表数据的打印。然后看看插入的情况；

//打印链表
void SLTPrint(SLTNode* phead) {SLTNode* pcur = phead;while (pcur) {printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}

尾插部分数据，观察打印的结果是否符合预期结果；发现运行结果与预期相符，所以链表的插入操作是没什么大问题的

3.1.3 单链表的头删、尾删

如果链表为空，不需要删除；如果删除的是第一个结点，则需要将保存链表首地址的指针保存第一个结点的下一个结点的地址如果删除的是中间结点，则找到中间结点的前一个结点，让前一个结点的指针域保存这个结点的后一个结点的地址即可

单链表的尾删

void SLTPopBack(SLTNode** pphead) {assert(pphead);//链表为空，不删除assert(*pphead); //指向第一个节点的地址//链表不为空，只有一个节点if ((*pphead)->next = NULL) {free(*pphead);*pphead = NULL;return;}//多个节点，释放最后一个节点，其前驱节点指向空SLTNode* ptail = *pphead;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);//链表不为空，释放最后一个节点，其前驱节点指向空SLTNode* pcur = *pphead;*pphead = pcur->next;pcur->next = NULL;free(pcur);pcur = NULL;
}

3.1.4 链表节点的查找

先对比第一个结点的数据域是否是想要的数据，如果是就直接返回，如果不是则继续查找下一个结点，如果到达最后一个结点的时候都没有匹配的数据，说明要查找数据不存在

//查找
SLTNode* STLFind(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* pcur = *pphead;while (pcur) {if (pcur->data == x) {return pcur;}pcur = pcur->next;}return NULL;
}

3.1.5 在指定位置插入数据

在指定位置前插入数据

//在指定位置前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(pos);//头节点不能为空assert(*pphead);SLTNode* newnode = SLTBuyNode(x);//当pos节点指向 头节点时,进行头插if (*pphead == pos) {SLTPushFront(pphead, x);return;}//pos pphead不指向同一节点SLTNode* prev = *pphead;while (prev->next != pos) { //找到pos节点的前驱prev = prev->next;}newnode->next = pos;prev->next = newnode;
}

在指定位置之后插入数据

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}

3.1.6 删除pos之后的节点

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) {assert(pos);assert(pos->next);//pos后不为空SLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}

3.1.7 销毁链表

重新定义一个指针next，保存pcur指向节点的地址，然后next后移保存下一个节点的地址，然后释放pcur对应的节点，以此类推，直到pcur为NULL为止

//销毁链表,由独立的节点构成，需要一个个销毁
void SListDestroy(SLTNode** pphead) {assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur) {SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

3.2 双向链表

这里介绍的双向链表是带头双向循环链表，它主要结构是由prev、next、data，这三个结构组成，通过prev找到前一个节点，next指向下一个节点

3.2.1 双向循环链表节点的创建

//定义双链表的节点结构体
typedef struct ListNode {ListType data;struct ListNode* prev;struct ListNode* next;
}LTNode;//创建循环双链表节点
LTNode* ListBuyNode(ListType x) {LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL) { //是否成功开辟空间perror("malloc");exit(1);}newnode->data = x;newnode->prev = newnode->next = newnode;return newnode;
}

双向循环链表节点的初始化

创建一个哨兵位，让它自己变成一个环形链表，只需要让他自己指向自己就可以

//双链表初始化
void ListInit(LTNode** pphead) {assert(pphead);//*pphead = (LTNode*)malloc(sizeof(LTNode));//if (*pphead == NULL) { //是否成功开辟空间//	perror("malloc");//	exit(1);//}//(*pphead)->data = -1;//(*pphead)->prev = (*pphead)->next = *pphead;*pphead = ListBuyNode(-1);
}

3.2.2 双向循环链表的头插、尾插

双向循环链表的尾插

当需要插入元素时，只需要创建节点，然后直接把值存入，此时哨兵位头节点的prev指向尾节点，

新建节点的prev指向头节点的prev，
头节点的prev（尾节点）的next指向新节点
新建节点的next指向头节点
更新尾节点，头节点的prev指向新节点

//双向循环链表的尾插
void ListPushBack(LTNode* phead, ListType x) {//phead不能为空assert(phead);LTNode* newnode = ListBuyNode(x);//phead newnode phead->prevnewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}

双链表的头插

头插就是将链表上的第一个节点与哨兵位的链接断开，但是在断开之前我们一定要先保存好将要断开的data，在去改变你将要头插的newnode

//头插
void ListPushFront(LTNode* phead, ListType x) {//phead不能为空assert(phead);LTNode* newnode = ListBuyNode(x);//phead newnode phead->nextnewnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}

双链表的打印

//打印双链表
void ListPrint(LTNode* phead) {assert(phead);LTNode* pcur = phead->next;while (pcur->next!= phead) {printf("%d->", pcur->data);pcur = pcur->next;}printf("%d", pcur->data);printf("\n");
}

3.2.3 双向循环链表的头删、尾删

双向循环链表的头删

对于头删来说，我需要删除链表的第一个节点，也就是 哨兵位的 next 节点，我需要改变 哨兵位 和 第二个节点 的链接关系，然后释放 第一个节点 。

void ListPopFront(LTNode* phead) { //删除的是第一个有效节点assert(phead);assert(phead->next != phead);//当双链表中只有哨兵位时，该链表为空//phead phead->next phead->next->nextLTNode* del = phead->next;LTNode* next = del->next;next->prev = phead;phead->next = next;free(del);del = NULL;
}

双向循环链表的尾删

这里还是一样的要找到tail前一个节点tailprev，然后直接释放掉尾节点就好

这里面注意一下，要是只有哨兵位就不能删除

void ListPopBack(LTNode* phead) {assert(phead);assert(phead->next!=phead);//当双链表中只有哨兵位时，该链表为空//phead phead->prev phead->prev->prevLTNode* del = phead->prev;LTNode* prev = del->prev;prev->next = phead;phead->prev = prev;free(del);del = NULL;
}

3.2.4 链表查找找元素位置

对于 双向链表 来说，它是没有指向NULL的节点的，它是一个环，停不下来。所以我们要把循环的截止条件设定为 ! = phead，这个条件就表示，已经遍历过一遍链表了

//找元素位置
LTNode* ListFind(LTNode* phead, ListType x) {assert(phead);LTNode* pcur = phead->next;while (pcur != phead) {if (pcur->data == x) {return pcur;}pcur = pcur->next;}return NULL;
}

3.2.5 在任意位置插入

在pos之前插入

通过 pos 的 prev 找到 pos 位置的上一个节点 posprev ，然后改变 posprev 和新节点 newnode 之间的链接和 newnode 和 pos 之间的链接

//在pos位置之后的插入
void ListInsert(LTNode* pos, ListType x) {assert(pos);LTNode*newnode=ListBuyNode(x);//pos newnode pos->nextnewnode->prev = pos;newnode->next = pos->next;pos->next->prev = newnode;pos->next = newnode;
}

在pos之后插入

//在pos位置之后的插入
void ListInsert(LTNode* pos, ListType x) {assert(pos);LTNode*newnode=ListBuyNode(x);//pos newnode pos->nextnewnode->prev = pos;newnode->next = pos->next;pos->next->prev = newnode;pos->next = newnode;
}

3.2.6 在pos位置之后的插入

在pos位置删除，需找到pos前一个节点posprev，和后一个节点posnext，将prev和next的链接接好，释放pos节点

void ListInsert(LTNode* pos, ListType x) {assert(pos);LTNode*newnode=ListBuyNode(x);//pos newnode pos->nextnewnode->prev = pos;newnode->next = pos->next;pos->next->prev = newnode;pos->next = newnode;
}

3.2.6 链表的销毁

这时直接把链表节点全部删除，在删除过程中记住下一个节点以便于循环

由于在函数中，释放了哨兵位，并要将其置空。释放是可以的，因为知道哨兵位的地址，释放就可以，但是置空却完成不了。因为哨兵位是形参，改变形参并不能影响实参，所以还需要在主函数中将哨兵位置空

void ListDistroy(LTNode* phead) { //保存接口的一致性//哨兵位不能为空assert(phead);LTNode* pcur = phead->next;while (pcur != phead) {LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;
}