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

【数据结构】3.单链表专题

news 来源：原创 2025/8/22 18:27:00

文章目录

单链表的实现
- 0、准备工作
- 1、链表的打印
- 2、尾插
- 3、头插
- 4、尾删
- 5、头删
- 6、查找指定数据的位置
- 7、在指定位置之前插入数据
- 8、在指定位置之后插入数据
- 9、删除指定位置的数据
- 10、删除指定位置之后的数据
- 11、单链表的销毁

单链表的实现

什么是单链表呢？单链表可以理解为一辆火车，是由一节一节车厢连接起来的，车厢间是有顺序的并且是有紧密联系的，而单链表就是一种这样的线性表结构，让数据存储在这样一个个有顺序的节点之中的。

0、准备工作

先创建三个文件：
SList.h：结构体定义，方法的声明
SList.c：方法的实现
test.c：方法的测试
首先在SList.h需要包含以下头文件：

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

接着在SList.h中定义单链表单个节点的结构体：

//单个节点的结构体
//为类型重新命名
typedef int SLDataType;
typedef struct SListNode
{SLDataType data;//数据struct SListNode* next;//指向下一个节点的指针
}SLTNode;

接下来再在其中进行方法的声明：

//单链表的打印
void SLTPrint(SLTNode* phead);//尾插
void SLTPushBack(SLTNode** pphead, SLDataType x);//头插
void SLTPushFront(SLTNode** pphead, SLDataType x);//尾删
void SLTPopBack(SLTNode** pphead);//头删
void SLTPopFront(SLTNode** pphead);//查找指定数据的位置
SLTNode* SLTFind(SLTNode* phead, SLDataType x);//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x);//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLDataType x);//删除指定位置的数据
void SLTErase(SLTNode** pphead, SLTNode* pos);//删除指定位置之后的数据
void SLTEraseAfter(SLTNode* pos);//销毁单链表
void SListDestroy(SLTNode** pphead);

接下来再在SList.c文件中进行方法的实现，在实现之前我们首先得包含.h文件：#include"SList.h"。
先在我们就可以开始进行方法的实现了。

1、链表的打印

思路：创建指针变量pcur遍历整个单链表，同时打印对应的数据。

void SLTPrint(SLTNode* phead)
{//创建指针来遍历SLTNode* pcur = phead;while (pcur){//打印指针对应的数据printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}

2、尾插

在进行尾插或头插之前我们都要先创建一个新节点，即：

SLTNode* BuyNode(SLDataType x)
{//动态开辟一块地址存放新节点SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//开辟失败if (newnode == NULL){perror("malloc fail!");exit(1);}//赋值newnode->data = x;newnode->next = NULL;//返回新节点地址return newnode;
}

接着再进行尾插，尾插的时候我们可以通过画图来清晰我们的思路：
先创建一个新节点newnode，如果单链表为空，那么新节点直接成为头节点，否则进行尾插：初始化ptail指向头节点，在通过while循环找到ptail，最后ptail连接newnode。
在这里插入图片描述
尾插代码：

void SLTPushBack(SLTNode** pphead, SLDataType x)
{//判空assert(pphead);//创建新节点SLTNode* newnode = SLTBuyNode(x);//如果单链表为空，那么新节点成为头结点if (*pphead == NULL){*pphead = newnode;}//不为空就尾插else{//初始化尾节点指向头结点SLTNode* ptail = *pphead;//while循环找到尾结点while (ptail->next){ptail = ptail->next;}//找到尾结点了，连接新节点ptail->next = newnode;}
}

再上述的代码中，我为什么需要对pphead进行判空呢？原因其实是因为pphead是一个二级指针，在接下来我需要实现*pphead找到头结点，如果pphead为空，那么我就是在对空指针解引用，所以一定要确保pphead不为空指针。
接着在test.c进行尾插测试：

int main()
{//链表的初始化SLTNode* plist = NULL;//尾插SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);return 0;
}

测试结果：
在这里插入图片描述
说明尾插成功！

3、头插

画图展现思路：
在这里插入图片描述
头插代码：

void SLTPushFront(SLTNode** pphead, SLDataType x)
{//判空assert(pphead);//创建新节点SLTNode* newnode = SLTBuyNode(x);//新节点连接头结点newnode->next = *pphead;//新节点成为新的头结点*pphead = newnode;
}

再上述代码中我们没有对单链表为空的情况进行处理是因为：当单链表为空时，*pphead==NULL，因此newnode->next实际上就是指向空指针，符合插入逻辑，而 *pphead=newnode刚好实现了头插并成为头结点。

接着再在test.c中进行头插测试：

int main()
{//链表的初始化SLTNode* plist = NULL;//头插SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist);return 0;
}

测试结果：
在这里插入图片描述
说明头插成功！

4、尾删

画图展现思路：
在这里插入图片描述
尾删代码：

void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);//只有一个节点if ((*pphead)->next == NULL){//释放节点free(*pphead);//指向空指针*pphead = NULL;}//多个节点就进行尾删else{//创建prev指针和ptail先初始化为头结点SLTNode* prev = *pphead;SLTNode* ptail = *pphead;//while循环根据ptail找到尾结点以及前一个节点while (ptail->next != NULL){//prev是ptail移动前的位置prev = ptail;ptail = ptail->next;}//释放尾节点free(ptail);//prev成为新的尾节点prev->next = NULL;}
}

在上面我们讲述了为什么要对pphead进行判空，而在这里我们为什么要对 *pphead进行判空呢？原因是因为如果 *pphead为空说明单链表为空，那么此时进行尾删就没有任何意义了。

接着再在test.c中进行尾删测试：

int main()
{//链表的初始化SLTNode* plist = NULL;//尾插SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);//尾删SLTPopBack(&plist);SLTPrint(plist);return 0;
}

测试结果：
在这里插入图片描述
说明尾删成功！

5、头删

画图演示：
在这里插入图片描述

void SLTPopFront(SLTNode** pphead)
{//判空assert(pphead && *pphead);//记录头结点下一个节点SLTNode* next = (*pphead)->next;//释放头结点free(*pphead);//下一个节点成为新的头结点*pphead = next;
}

注意：这里我们对( *pphead)->next是对 *pphead加了括号的，那是因为->（成员访问操作符）的优先级是高于 *（解引用操作符）的，因此需要加括号（）。

接下来对头插进行测试：

int main()
{//链表的初始化SLTNode* plist = NULL;//尾插SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);//尾删SLTPopFront(&plist);SLTPrint(plist);return 0;
}

运行结果：
在这里插入图片描述
结果显示头删成功！

6、查找指定数据的位置

画图演示：
在这里插入图片描述

SLTNode* SLTFind(SLTNode** pphead, SLDataType x)
{//判空assert(pphead);//创建指针指向第一个头结点SLTNode* pcur = *pphead;//遍历单链表while (pcur){//查看数据是否相同if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到返回NULLreturn NULL;
}

再在test.c进行测试：

int main()
{//链表的初始化SLTNode* plist = NULL;//尾插SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);//查找指定数据的位置SLTNode* find=SLTFind(&plist, 2);if (find!=NULL){printf("找到了!\n");}else{printf("没有找到!\n");}return 0;
}

运行结果：
在这里插入图片描述
结果显示查找指定数据成功！

7、在指定位置之前插入数据

画图演示：
在这里插入图片描述

指定位置前插入代码：

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{assert(pphead && *pphead);assert(pos);//创建新节点SLTNode* newnode = SLTBuyNode(x);//如果单链表只有一个节点 就相当于头插if (*pphead == pos){SLTPushFront(pphead, x);}else{//找到pos前一个节点//先创建指针指向头结点SLTNode* prev = *pphead;//遍历单链表while (prev->next != pos){prev = prev->next;}//连接newnode和posnewnode->next = pos;//连接prev和newnodeprev->next = newnode;}
}

在上述代码中我同样对 *pphead和pos进行了是否为空的检查，为什么呢？如果 *pphead为空，那么说明链表为空，那么pos节点也同样不存在，就会出现问题。但是如果链表不为空，但是pos节点为空，说明查找的位置不在链表内，也会出现问题，因此需要对他们进行判空检查。

再进行测试：

int main()
{//链表的初始化SLTNode* plist = NULL;//尾插SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);//查找指定数据SLTNode* find=SLTFind(&plist, 2);//在指定位置之前插入数据SLTInsert(&plist, find, 10);SLTPrint(plist);return 0;
}

运行结果：
在这里插入图片描述
可以看到插入成功！

8、在指定位置之后插入数据

画图演示：

在这里插入图片描述

void SLTInsertAfter(SLTNode* pos, SLDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;}

在指定位置之后进行插入的时候，是不需要知道头结点地址的，只需要pos即可，因此不用传参pphead。

再进行测试：

int main()
{//链表的初始化SLTNode* plist = NULL;//尾插SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);//查找指定数据的位置SLTNode* find=SLTFind(&plist, 2);//在指定位置之后插入数据SLTInsertAfter(find, 10);SLTPrint(plist);return 0;
}

运行结果：
在这里插入图片描述
观察结果可以发现插入成功！

9、删除指定位置的数据

void SLTEarse(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);assert(pos);//如果pos指向头结点if (pos == *pphead){SLTPopFront(pphead);}	else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos == NULL;}
}

再进行测试：

int main()
{//链表的初始化SLTNode* plist = NULL;//尾插SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);//查找指定数据的位置SLTNode* find=SLTFind(&plist, 2);//删除指定位置的数据SLTErase(&plist, find);SLTPrint(plist);return 0;
}

运行结果：
在这里插入图片描述
结果观察到删除成功！

10、删除指定位置之后的数据

在这里插入图片描述

void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}

在这里我们不需要考虑pos节点指向头结点的情况，因为这里的代码不需要使用到头结点，同时我们注意到这里对pos->next也进行了判空检查，那是因为我们将del定义为了pos->next,并且在后续使用del->next,如果del为空那么就会出现问题。

进行测试：

int main()
{//链表的初始化SLTNode* plist = NULL;//尾插SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);//查找指定数据的位置SLTNode* find=SLTFind(&plist, 2);//删除指定位置之后的数据SLTEraseAfter(find);SLTPrint(plist);return 0;
}

运行结果：
在这里插入图片描述
删除成功！

11、单链表的销毁

在这里插入图片描述

void SListDestroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

再进行测试：

int main()
{//链表的初始化SLTNode* plist = NULL;//尾插SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);//查找指定数据的位置SLTNode* find=SLTFind(&plist, 2);//单链表的销毁SListDestroy(&plist);SLTPrint(plist);return 0;
}

运行结果：
在这里插入图片描述

销毁成功！

点击在gitee查看完整源代码

文章目录

单链表的实现

0、准备工作

1、链表的打印

2、尾插

3、头插

4、尾删

5、头删

6、查找指定数据的位置

7、在指定位置之前插入数据

8、在指定位置之后插入数据

9、删除指定位置的数据

10、删除指定位置之后的数据

11、单链表的销毁

相关文章：