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

C数据结构：单链表

news 来源：原创 2024/5/17 10:20:44

目录

链表是什么？

链表的数据结构

单链表的实现

单链表的打印

单链表的尾插

开辟新节点

为什么要使用二级指针？

单链表的头插

单链表的尾删

单链表的头删

单链表的查找

单链表指定位置前插入

单链表指定位置后插入

单链表指定位置删除

单链表指定位置后删除

单链表的销毁

完整代码

链表是什么？

链表是诸多线性表中的一种

链表是一种物理存储结构上非连续、非顺序的存储结构，但是我们人为的可以把它想象成一条线，所以它也是线性表中的一种

链表的结构就类似火车

每一个车厢可以看作是一个个的数据，中间把它们链接起来的东西就是我们的指针，指针存储着下一个“车厢”的地址，只有到达了这个车厢获取到了我们的指针才能获取到下一节车厢的钥匙

这里的每个车厢我们都把它叫做节点（或结点）

如果有点懵就直接来看看下面的代码吧

链表的数据结构

typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;

这里我们将SLTDataType设置为int类型

这么做是方便后续更换数据类型（例如char，double或者struct出来的自定义类型）

在一个结构体里定义了一个同类型的next指针，我们可以使用这个next指针链接我们之后的节点

但是我们从哪里获取节点呢？

当然是我们程序员自己动态申请空间，申请完成后让next指针指向我们申请的那块空间

这样我们的第一个节点就做好了，这个节点里既存放了我们的data数据，还存放了下一个节点的地址，我们就可以通过解引用next找到我们的下一个节点

有关动态内存管理的知识： C语言：动态内存管理（malloc，calloc，realloc，free）-CSDN博客

下面就开始实现单链表吧！

单链表的实现

//创建节点
SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));
n1->data = 1;
SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));
n2->data = 2;
SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));
n3->data = 3;
SLTNode* n4 = (SLTNode*)malloc(sizeof(SLTNode));
n4->data = 4;
//链接
n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = NULL;

前面的代码就是创建了4个节点，并且给每个节点的data都赋值了，但是这样并没有完成链接，所以最下面的四行操作就是完成了链接操作 

大致图形就是这样

内存中不是连续存放的，是随机的一块块空间链接而成 

但是上面的代码我们如果要看到效果的话只能借助调试功能，所以为了后续代码的展示，我们可以先写个单链表的打印方法 

单链表的打印

void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

 这里定义了一个cur来从phead（头节点）开始遍历整个链接

每遍历到一个节点我们就打印一个节点的数据，再让cur往后走即可

循环终止的条件自然就是cur不能走的时候（cur==NULL）

为什么要定义一个cur指针来遍历链表，而不是直接用phead？

因为phead我们需要它一直指向头节点，如果现在只是使用一个SLTPrint函数就要改变它的位置，那我们后续还要使用其他方法需要从链表的头节点开始怎么找到头节点呢？

这样就可以测试前面创建的4个节点了

void Test()
{//创建节点SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));n1->data = 1;SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));n2->data = 2;SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));n3->data = 3;SLTNode* n4 = (SLTNode*)malloc(sizeof(SLTNode));n4->data = 4;//链接n1->next = n2;n2->next = n3;n3->next = n4;n4->next = NULL;SLTPrint(n1);
}

 

可以看到我们要的效果已经完美的展现出来了

单链表的尾插

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);//创建新节点SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail\n");exit(1);}newnode->data = x;newnode->next = NULL;//头节点为空if (*pphead == NULL){*pphead = newnode;}else //头节点不为空{SLTNode* cur = *pphead;while (cur->next != NULL){cur = cur->next;}cur->next = newnode;}
}

 这里函数的第一个参数我们使用了一个类型为SLTNode的二级指针，和一个数据x，后面我们使用这个函数的时候需要传指向链表第一块节点的指针的地址才行，至于为什么要这么做，请往下看

 既然要插入一个数据，那么我们得先开辟一块空间才行

开辟新节点

所以除了assert断言外，我们的第一步就是先创建一个新节点，大小为SLTNode的大小，这样才能装得下一个SLTDataType和一个指针

我们还要先判断这个地方开辟是否成功，如果失败会返回空指针，然后用exit退出程序

最后对newnode初始化即可

但是我们不仅仅需要尾插，后面我们还要写头插、指定位置插入

如果我们每次插入都要写这么一长串相同的代码就会显得代码冗余

所以我们直接写一个函数来创建这个空间即可

SLTNode* BuyListNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail\n");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}

 代码还是和上面一样，函数最后会返回一个SLTNode的指针，这个指针就是指向了这块我们新开辟的内存空间

所以尾插代码如下：

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuyListNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* cur = *pphead;while (cur->next != NULL){cur = cur->next;}cur->next = newnode;}
}

 BuyListNode函数一定要在我们插入函数之前，不然函数会找不到BuyListNode函数

 尾插我们会分为两种情况，一种是头节点为空，一种是不为空，我们需要分开讨论

如果头节点为空，那么我们需要让*pphead头节点这块新创建的节点

这里开始解释为什么函数参数要使用二级指针：

为什么要使用二级指针？

我们如果不使用二级指针会怎么样？

那我们代码里的所有*pphead都不需要解引用就可以拿到了，就是这样：

void SLTPushBack(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* newnode = BuyListNode(x);if (phead == NULL){phead = newnode;}else{SLTNode* cur = phead;while (cur->next != NULL){cur = cur->next;}cur->next = newnode;}
}

它和二级指针的区别就是一个传了一级指针的地址，一个只是一级指针的临时拷贝

就和我们在指针的基础里写到的Swap函数如果不写指针的话，传的只是形参，形参是实参的临时拷贝，改变形参并不会改变实参，只有传地址过去才能改变它

 

第一个Swap1明显是不能交换成功的，只有第二个可以

在刚刚的尾插代码也一样，我们要改变phead，那么必须要传phead的地址，才能改变phead

所以我们函数里使用了二级指针作为参数，传phead的地址，才能改变phead，只不过名字命名为了pphead 

总结：

要改变谁，就要传谁的地址，解引用才能改变它

 回到我们尾插的代码

如果我们的头节点不为空，那么我们定义了一个cur来遍历整个链表，让cur指向最后一个节点，然后让cur的下一个节点为新节点链接即可

刚开始写尾插代码的时候并不一定一开始就能想到我们分为两种情况，一种头节点为空一种不为空，而是我们先把后面的else的代码写完之后才会想如果链表为空会不会影响代码的可行性，如果会影响，那么我们就需要用if语句来控制了

单链表的头插

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuyListNode(x);newnode->next = *pphead;*pphead = newnode;
}

前面的尾插理解了那么头插就很简单了

也是一样先把头插的基本代码写出来：

让newnode的next指针指向头节点，再将头节点设置为newnode即可

这时候我们就可以开始思考如果链表为空是否会影响代码的可行性

我们将*pphead看成NULL代入看看

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuyListNode(x);newnode->next = NULL;*pphead = newnode;
}

 这样看起来是没问题的，最后我们利用前面单链表的打印函数或者调试来看看是否能够与预期符合即可，最终发现这个代码是没什么问题的

单链表的尾删

void SLTPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* cur = *pphead;//只有一个节点时的删除if (cur->next == NULL){free(cur);cur = NULL; //可有可无*pphead = NULL;}else{SLTNode* prev = NULL;while (cur->next != NULL){prev = cur;cur = cur->next;}prev->next = NULL;free(cur);cur = NULL;}
}

删除尾部的节点该怎么做？

我们需要让尾部的前一个和尾部的链接断掉即可

但是这里要分两种情况，一种是链表只有一个节点时的删除，一种是链表有一个以上的节点的删除

如果*pphead的下一个节点是NULL的话，就说明只有一个节点，我们直接free掉头节点指向的空间，然后将*pphead置为NULL即可

如果是多个节点的删除

我们需要再多定义一个prev指针，这个指针会一直紧跟cur在链表中前进的步伐，但会保持一直慢cur一步，这个prev表示的就是cur的前一个节点

那么我们通过循环保持它两的关系，并且让cur走到最后一个节点才停下，那么prev就是倒数第二个节点停下

最后我们只需要让倒数第二个节点断掉与最后一个节点的关系（也就是让它的next指针指向空，不再指向最后一个节点），再free掉最后一个节点防止内存泄漏即可

单链表的头删

void SLTPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* del = *pphead;*pphead = (*pphead)->next;free(del);del = NULL;//可有可无，del出函数作用域自动销毁
}

头删相对来说就比较轻松了

但多出一个断言，防止我们删除的链表为空

创建一个del指针指向头节点，最后让头节点往后走一步（不能先free再走，防止变成NULL指针） 

free掉del指向的空间即可

单链表的查找

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* cur = phead;while (cur != NULL){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

与数组的查找类似，数组的查找要遍历整个数组

那么我们只需要遍历整个链表即可，先定义一个cur指针负责遍历整个链表，如果链表中的data和x相等，则说明单链表中存在当前数据，返回当前cur指针

否则说明没找到，返回NULL

单链表指定位置前插入

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);SLTNode* newnode = BuyListNode(x);//链表只有一个数据if (*pphead == pos){SLTPushFront(pphead, x);}else{SLTNode* cur = *pphead;while (cur->next != pos && cur != NULL){cur = cur->next;}cur->next = newnode;newnode->next = pos;}
}

要先将pos断言了，防止pos为NULL

这里也是要分成两种情况，一种是链表中只有一个数据，另一种是链表中有多个数据

如果只有一个数据，相当于直接头插，我们调用前面写到的头插函数即可

如果有多个数据，我们需要先找到pos的前一个节点，才能在pos前插入

所以我们定义了一个cur负责走到pos的前一个节点，然后将cur的next指针指向我们新创建的节点连接起来，然后让新节点的next指向我们的pos指向的节点即可

单链表指定位置后插入

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuyListNode(x);SLTNode* Next = pos->next;pos->next = newnode;newnode->next = Next;
}

在这个后插入的函数我们就不需要传链表的头节点了，因为根本用不上它

我们定义了一个Next指针指向pos的下一个节点

让pos的next指向新节点newnode，newnode的next指向Next指向的节点即可

单链表指定位置删除

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (*pphead == pos){SLTPopFront(pphead);}else{SLTNode* cur = *pphead;while (cur->next != pos && cur != NULL){cur = cur->next;}cur->next = pos->next;free(pos);}
}

这个指定位置删除函数也是分成两种情况，一种是删除的位置为头节点，一种是不为头节点

如果为头节点我们直接使用前面写到的头删函数即可

如果不为头节点，我们还是定义了一个cur来找到pos位置的前一个节点

这里while循环终止的条件也有两种情况

一种是pos节点正常在链表中，则会被第一个cur->next != pos结束，从而找到pos的前一个节点

另一种是pos节点不在该链表中， 那么我们cur会找不到pos的前一个节点，cur会直接走到NULL，需要后面的 cur != NULL 的条件终止循环

当我们的cur找到了pos的前一个节点时，让cur节点的next指针指向pos的下一个节点，最后把free(pos)即可

单链表指定位置后删除

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

这个函数和指定位置后插入一样都不需要头节点，原因也是用不上头节点

并且需要多断言pos的next节点，不能为NULL，否则怎么删除

这里定义了一个del指针，让del指针指向要删除的那块空间

并且让pos节点的next与del的next节点连接

最后free(del)即可

单链表的销毁

void SListDesTroy(SLTNode** pphead)
{assert(pphead);SLTNode* cur = *pphead;while (cur != NULL){SLTNode* Next = cur->next;free(cur);cur = Next;}*pphead = NULL;
}

销毁相对来说就比顺序表复杂一点

因为链表在内存空间中是随机存放的，不像顺序表是一块连续的空间可以一次性全部释放，链表只能找到一块释放一块

我们先定义一个cur指针遍历整个链表，还需要一个Next指针始终指向下一块内存空间，每次将cur的空间释放掉，让cur重新指向Next即可

最后全部释放完之后不要忘了将头节点*pphead置为NULL

到这里单链表的函数就暂时结束了

完整代码

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//单链表打印
void SLTPrint(SLTNode* phead);//尾部插入
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头部插入
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾部删除
void SLTPopBack(SLTNode** pphead);
//头部删除
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);SLTNode* BuyListNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail\n");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuyListNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* cur = *pphead;while (cur->next != NULL){cur = cur->next;}cur->next = newnode;}
}void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuyListNode(x);newnode->next = *pphead;*pphead = newnode;
}void SLTPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* cur = *pphead;//只有一个节点时的删除if (cur->next == NULL){free(cur);cur = NULL;*pphead = NULL;}else{SLTNode* prev = NULL;while (cur->next != NULL){prev = cur;cur = cur->next;}prev->next = NULL;free(cur);cur = NULL;}
}void SLTPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* del = *pphead;*pphead = (*pphead)->next;free(del);del = NULL;
}SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* cur = phead;while (cur != NULL){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);SLTNode* newnode = BuyListNode(x);//链表只有一个数据if (*pphead == pos){SLTPushFront(pphead, x);}else{SLTNode* cur = *pphead;while (cur->next != pos && cur != NULL){cur = cur->next;}cur->next = newnode;newnode->next = pos;}
}void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (*pphead == pos){SLTPopFront(pphead);}else{SLTNode* cur = *pphead;while (cur->next != pos && cur != NULL){cur = cur->next;}cur->next = pos->next;free(pos);}
}void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);
}void SListDesTroy(SLTNode** pphead)
{assert(pphead);SLTNode* cur = *pphead;while (cur != NULL){SLTNode* Next = cur->next;free(cur);cur = Next;}*pphead = NULL;
}//测试单链表函数代码
void TestSlist1()
{//建立指针指向第一个节点SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);//SLTPushFront(&plist, 8);//SLTPushFront(&plist, 9);//SLTPushFront(&plist, 10);//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);SLTNode* find = SLTFind(plist, 3);//if (find == NULL)//{//	printf("链表没有该数据！\n");//}//else//{//	printf("找到了！\n");//}//SLTInsert(&plist, find, 9);//SLTPrint(plist);//SLTErase(&plist, find);//SLTPrint(plist);//SLTEraseAfter(find);//SLTPrint(plist);SListDesTroy(&plist);SLTPrint(plist);
}int main()
{TestSlist1();return 0;
}

完

相关文章：

  • MySQL innoDB存储引擎多事务场景下的事务执行情况
  • java操作linux
  • Covalent Network（CQT）推出以太坊质押迁移计划，以增强长期结构化数据可用性、塑造万亿级 LLM 参数体系
  • 输入输出系统的发展历程
  • python + jdbc 连接 达梦数据库
  • 在Linux系统上实现TCP（socket）通信
  • c++20协程详解（三）
  • 19、差分矩阵
  • （Oracle）SQL优化技巧（一）：分页查询
  • 计算机基础系列合集
  • 面试准备 集合 List
  • Python 新手最容易踩的坑
  • Scrapy 爬取m3u8视频
  • 基于springboot实现墙绘产品展示交易平台管理系统项目【项目源码+论文说明】
  • 基于BP神经网络的时间序列预测模型matlab代码
  • 【140天】尚学堂高淇Java300集视频精华笔记（86-87）
  • C++入门教程（10）：for 语句
  • es6
  • GitUp, 你不可错过的秀外慧中的git工具
  • gops —— Go 程序诊断分析工具
  • input的行数自动增减
  • linux安装openssl、swoole等扩展的具体步骤
  • Nginx 通过 Lua + Redis 实现动态封禁 IP
  • Ruby 2.x 源代码分析：扩展 概述
  • 阿里云容器服务区块链解决方案全新升级 支持Hyperledger Fabric v1.1
  • 不发不行！Netty集成文字图片聊天室外加TCP/IP软硬件通信
  • 技术攻略】php设计模式(一)：简介及创建型模式
  • 每天10道Java面试题，跟我走，offer有！
  • 入门到放弃node系列之Hello Word篇
  • 首页查询功能的一次实现过程
  • 想使用 MongoDB ，你应该了解这8个方面！
  • 移动端 h5开发相关内容总结(三)
  • nb
  • Java数据解析之JSON
  • #我与Java虚拟机的故事#连载18：JAVA成长之路
  • (4) openssl rsa/pkey(查看私钥、从私钥中提取公钥、查看公钥)
  • （4.10~4.16）
  • （C#）一个最简单的链表类
  • （ZT）出版业改革：该死的死，该生的生
  • (附源码)计算机毕业设计ssm基于Internet快递柜管理系统
  • (收藏）Git和Repo扫盲——如何取得Android源代码
  • (原創) 如何動態建立二維陣列(多維陣列)? (.NET) (C#)
  • （转）JVM内存分配 -Xms128m -Xmx512m -XX:PermSize=128m -XX:MaxPermSize=512m
  • .NET Framework Client Profile - a Subset of the .NET Framework Redistribution
  • .net framework profiles /.net framework 配置
  • .net web项目 调用webService
  • .NET4.0并行计算技术基础（1）
  • .NET6实现破解Modbus poll点表配置文件
  • .Net高阶异常处理第二篇~~ dump进阶之MiniDumpWriter
  • .NET国产化改造探索（一）、VMware安装银河麒麟
  • .NET简谈互操作(五：基础知识之Dynamic平台调用)
  • .NET正则基础之——正则委托
  • /boot 内存空间不够
  • @Bean注解详解
  • @property @synthesize @dynamic 及相关属性作用探究