C语言实现单链表（超多配图，这下不得不学会单链表了）
创始人
2025-05-30 01:58:48
0次

目录

一：什么是链表？

二：创建源文件和头文件

(1)头文件

(2)源文件

三：实参和形参

四：一步步实现单向链表

（1）建立一个头指针并置空

（2）打印链表，便于观察测试

（3）创建一个新的结点

（4）尾部插入数据

（5）头部插入

（6）尾部删除

（7）头部删除

（8）查找

（9）指定位置插入

（10）指定删除

（11）清空链表

（12）最终代码

SingleLinkedList.h

SingleLinkedList.c

text.c

五：小结

一：什么是链表？

我们先看下面这个结构体。

6474826145a8496290b457cb48bbbacd.png

这个结构体存储数据的同时保存了一个结构体指针。

链表其实就是一个个结构体（后文把这样的一个结构体称为结点）通过保存地址的方式找到下一个结构体，最后一个结构体保存的地址为空。 

链表的两种实现方式

（1）带头结点

（2）不带头结点

区别:带头结点有一个哨兵结点，这个节点作为第一个节点,它的数据域不存储数据。

两者各有利弊：我们进行结点删除时需要用到待删除结点的前一个结点。对于没有哨兵的单链表,当链表中只存在一个节点,需要进行单独处理。从而代码的复杂性增加。但如果设计了哨兵结点，则第一个结点的处理与其他结点一致。但处理链表数据时这个哨兵结点属于无效数据，我们需要规避这个数据，也需要进行处理。

本文选择的是无哨兵链表。

二：创建源文件和头文件

(1)头文件

头文件SingleLinkedList.h用来包含一些必要的头文件，声明函数以及定义结构体。

(2)源文件

源文件SingleLinkedList.c用来实现链表的具体功能。

源文件text.c用来对各个功能进行测试。

三：实参和形参

在实现链表之前，我们需要先深入的认识一下实参和形参的关系。

我们看下面这个代码:

fae8cca3f2144da48dda0fc6452d7cc4.png

我们可以看到a的值并没有发生变化，那我们如果传入a的地址进行解引用呢？我们看下面这个代码。

61db06269de6433ab8ddfb1f2960a66b.png

我们可以看到a成功被修改为了5，但这是为什么呢？

答:其实在传入参数的时候系统临时开辟了一块空间用来接收数据，函数调用结束时这一块空间就会被释放，这意味着如果我们直接传入a的值，我们只是在对这一块临时开辟的空间内的数据进行修改，无论如何都不会影响到a,但如果我们传入的是a的地址，对a进行解引用就能直接找到并修改a。

图解:2d79ce8bca0e42b8b043c2b04731a85a.png

2deee6f13ae44417a10c9f8dd0ff5f50.png

 这是否意味着只要我们传入的是地址就一定能改变实参的值呢？我们看下面这个代码。

a6b7355468594d23bbf232a78b0e9279.png

我们发现虽然传入的是地址，但p依旧指向a[0],并没有改变。这是为什么呢？

答:与前面的原理一致，我们传入p的时候也临时开辟了一片空间来保存p的值，无论我们怎么改变p值，在函数调用结束后这片空间会被释放，所以p实际上还是指向a[0]的。

图解: 4fba6749c8044d2c87f35ac16b301ee7.png

那如果我们传入p的地址，是不是就能改变p了呢？我们看代码。

6592e55592574087b2244b4673504500.png

图解:5846b45efb21446282113591856afdb5.png 

四：一步步实现单向链表

（1）建立一个头指针并置空

struct SListNode* head = NULL;

（2）打印链表，便于观察测试

我们用头指针的地址是否为空为循环条件。
我们可以分成两种情况讨论，如果链表为空，我们不进行遍历，直接打印NULL。
如果链表中有元素，从头指针（第一个结点）开始，我们打印结点数据，并让头指针指向下一个结点，一直到NULL。

代码:7c4fd64bd4084002a8c160871e547f57.png

图解（以有三个结点为例子）：

44ae685eee3e4f0eac9cd4b553b1cdc0.png

（3）创建一个新的结点

只要插入新结点，我们就一定要生成新的结点，我们可以把生成新结点的功能单独封装成函数BuyListNode()。

代码：b31ae76d3bec44d1b5efc182f3b52a64.png

（4）尾部插入数据

进行数据插入，我们要改变实参的值（即改变指针的指向），必须传入头指针的地址（二级指针）。

基础思路：【1】在进行数据插入之前，我们要先生成一个新的结点。

【2】要进行尾部插入，我们需要找到链表的最后一个结点，并将它存储的指针指向新生成的结构体。

【3】我们设计一个指针tail来找尾部结点，如果tail->next为NULL，我们就找到了尾部结点，结束循环。

图解：4b29d1c243e5473cb673be88da30eb2e.png

 

现阶段代码：

e2ecb7828a5d49fd8cd1c3a5c535d6e4.png

我们对代码进行测试:

6baf6efc94e14f9fb81f4d4781554370.png

可以发现程序崩溃了，这是为什么呢？

答：这是因为我们没有考虑链表为空的情况，如果链表为空，我们会直接对空指针进行解引用，导致程序崩溃。

bf1dee301bff4c10a5fdb295de1b54b7.png

 为了解决这个问题，我们可以对这种情况进行单独处理。

 代码：79c1e38713e64d61a77946d6a8f56edf.png

再次测试，观察结果。

7243601c914648718d1666a3415045a1.png 我们发现数据成功插入了。

（5）头部插入

进行数据插入，我们要改变实参的值（即改变指针的指向），必须传入头指针的地址（二级指针）。

思路：头部插入我们只需要让头指针指向新结点，让新结点的指针域指向原来的头结点。

代码：2705aca8e83a4c909cff010bb6bcd708.png

前面进行尾部插入的时候需要考虑链表为空的情况，那头部插入需不需要单独进行这个临界条件的处理呢？ 

图解：261769f9d5e44d02aef1c66feab4dcba.png

 我们可以发现最后结点的指针域会指向空，所以不需要考虑这个临界情况。

（6）尾部删除

进行数据插入，我们要改变实参的值（即改变指针的指向），必须传入头指针的地址（二级指针）。

思路：和尾部插入一样我们需要使用一个tail指针找到尾部结点（方法与前面一致），然后释放这个结点。

我们看代码和运行结果：

19cd341a061848e7bc25cdf2cb0dfa08.png

ecc2788f069e4c56b3da63998ab1b009.png

 我们发现程序打印的是随机数，这是为什么呢？

答：因为我们释放最后一个结点的时候上一个结点的指针域没有指空，但空间已经被系统回收了，此时我们进行指针的引用是非法的，也就是我们常说的野指针。

解决方案：我们可以设计一个指针prev来记录倒数第二个结点，在释放尾结点后让倒数第二个结点的指针域指向空。

但此时程序依然存在不足。
如果链表为空，我们就会对空指针进行解引用，所以我们需要单独处理这种情况，这里提供两种解决方案
第一，我们可以直接返回空。
第二，我们可以使用断言让程序直接报错。

这里使用第一种方法。
代码和测试结果：ec6c276d5639432885b9fa6f83d5c970.png

8f5af09c05f9409aa39e1ab492f42fb0.png

（7）头部删除

进行数据插入，我们要改变实参的值（即改变指针的指向），必须传入头指针的地址（二级指针）。

思路：进行头部删除，可以将第一个结点释放，然后让头指针指向第二个结点。

代码和运行结果：

65e4af5ed59d4374a50ee445d8e33520.png

699e430580424850b41aa4f7a4a7fbe3.png

（8）查找

查找有两种实现方式，一种返回结点地址，一种返回数据在第几个结点。

思路：遍历整个链表，一直到找到要查找的数据或最后一个结点为止。
如果没有查找到数据，返回NULL或者0。

第一种(我用的)：

0971c2934fdf466ebd30175deeb709b2.png

 第二种：

3d8810c7f62f42dabf5055a2c471f4e1.png

上述函数我们只能找到第一个数，后面相同的找不到，如果我们需要查找链表中所有该数的位置 ，我们可以设计一个pos指针并进行循环，循环结束条件为pos为空，这样就可以实现多次查找，我们看代码。（这个方法只适用于第一种）

8660c2b7711f4983967cbca7ce2cfb51.png

（9）指定位置插入

这里给出两种插入方式，一种是指定在那个结点前插入，一种是指定在那个结点后插入

第一种前插入：c0cedcff8da74f45bb26531cca01ec92.png

 第一种后插入：

d4026db1939a4e6d8d2188a607d95dbc.png

 在进行插入前我们需要找到要插入的那个结点的前面（后面），可以先使用查找函数找到位置，在进行插入。

测试结果：1ada667b6e604c55a536650d3e870f92.png

（10）指定删除

思路：删除的思路同尾删类似，我们需要找到待删除的结点并保存待删除的结点的指针域。

代码：6099e8f0d3754045aeacc4a6d83026d7.png

在进行删除前我们需要找到要删除的那个结点的前一个结点（目的是让前面的结点指针域指向下下个结点），可以先使用查找函数找到位置，再进行删除。

测试：b3cb40c6f02f4a7784af4ae437ea83f7.png

 e195101c84744289a70bcb39f8165f78.png

4c13c10e46784c7cbbe2cbb8369047ee.png

c337b97cbca84d6bb4f8580bd497db5c.png

（11）清空链表

思路：从第一个结点开始，设计一个pos指针，每次循环把头指针指向的结点地址赋给pos，让头指针指向下一个结点地址，调用free（）释放pos指向的结点。

图解(以三个结点为例子):c194c8e3c2fb4d2b9704ac35ae45ab91.png

代码和测试结果：

321c36b131d8475b89ab775d1a6a9b05.png

1e62f5ee1e124f3ea665a50ab4b2a72c.png

046004a7aa3d4b51a0a496c54b8014e4.png

（12）最终代码

SingleLinkedList.h

#pragma once
#include 
#include 
//#include     要使用断言的话注意包含头文件//结构体数据类型重定义，方便我们更改要存储的元素类型
typedef int SLTDataType;struct SListNode
{SLTDataType data;   //要存储的数据(数据域)struct SListNode* next; //用来存储下一个结构体的地址（指针域）
};//打印
void SListPrint(struct SListNode* phead);
//创建一个新节点
struct SListNode* BuyListNode(SLTDataType x);
//尾部插入
void SListPushBack(struct SListNode** pphead, SLTDataType x);
//头部插入
void SListPushFront(struct SListNode** pphead, SLTDataType x);
//尾部删除
void SListPopBack(struct SListNode** pphead);
//头部删除
void SListPopFront(struct SListNode** pphead);
//查找,返回对应结点地址
//int SListFind(struct SListNode* phead, SLTDataType x);
struct SListNode* SListFind(struct SListNode* phead, SLTDataType x);
//指定插入（还有一种按输入位置来插入）（在前面插入）
void SListInsertF(struct SListNode** pphead, struct SListNode* pos, SLTDataType x);
void SListInsertB(struct SListNode** pphead, struct SListNode* pos, SLTDataType x);//指定删除
void SListEarse(struct SListNode** pphead, struct SListNode* pos);
//销毁链表
void SListDestory(struct SListNode** pphead);

SingleLinkedList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SingleLinkedList.h"//打印链表
void SListPrint(struct SListNode* phead)
{//一直循环，直到找到最后一个结点while (phead){printf("%d-> ", phead->data); //依次打印结点存储的数据phead = phead->next; //让phead指向下一个结点}printf("NULL\n");
}//生成新节点
struct SListNode* BuyListNode(SLTDataType x)
{//调用maoolc()函数生成一个结点struct SListNode* newNode = (struct SListNode*)malloc(sizeof(struct SListNode));//如果申请失败，打印错误并结束程序if (newNode == NULL){printf("malloc error\n");exit(-1);}//将要插入的数据赋给新结点newNode->data = x;//新节点的next置空newNode->next = NULL;//返回生成的结点的地址return newNode;
}//尾部插入
void SListPushBack(struct SListNode** pphead, SLTDataType x)
{//生成一个新的结点struct SListNode* newnode = BuyListNode(x);//如果链表为空，直接把新结点地址赋给*ppheadif (*pphead == NULL){*pphead = newnode;}else{	//设置一个指针tail用来找到尾部结点struct SListNode* tail = *pphead;//不断循环，直到找到尾部结点while (tail->next){tail = tail->next;//指向下一个结点}//让原本置空的指针指向新生成的结点tail->next = newnode;}
}//头部插入
void SListPushFront(struct SListNode** pphead, SLTDataType x)
{//生成新结点struct SListNode* newnode = BuyListNode(x);//保存原来第一个结点的地址struct SListNode* prev = *pphead;//让头指向新结点*pphead = newnode;newnode->next = prev;
}//尾部删除
void SListPopBack(struct SListNode** pphead)
{//如果链表为空，就直接返回空，也可以使用assert(*pphead!=NULL)if (*pphead == NULL){	return;}//如果只有一个结点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//找尾部struct SListNode* tail = *pphead;//记录尾部的前一个结点的地址struct SListNode* prev = NULL;//找尾部结点，并保存尾部结点的前一个结点的地址while (tail->next){prev = tail;tail = tail->next;}//找到尾部结点，释放free(tail);//置空tail = NULL;//把尾部的前一个结点保存的地址置空prev->next = NULL;}
}//头部删除
void SListPopFront(struct SListNode** pphead)
{//如果链表为空，返回空，也可以使用assert(*pphead!=NULL)if (*pphead == NULL){return;}else{//找到下一个结点的地址struct SListNode* prev = (*pphead)->next;//释放第一个结点free(*pphead);//头指针指向第二个结点*pphead = prev;}
}//查找
struct SListNode* SListFind(struct SListNode* phead, SLTDataType x)
{struct SListNode* cur = phead;//循环查找while (cur){//找到返回该结点地址if (cur->data == x){return cur;}//没找到指向下一个结点else{cur = cur->next;}}//如果没找到，返回NULLreturn NULL;
}
//第二种
//int SListFind(struct SListNode* phead, SLTDataType x)
//{
//	//记录第几个结点
//	int i = 1;
//	struct SListNode* cur = phead;
//	//循环查找
//	while (cur)
//	{
//		//找到返回该结点地址
//		if (cur->data == x)
//		{
//			return i;
//		}
//		//没找到指向下一个结点,i加1
//		else
//		{
//			i = i + 1;
//			cur = cur->next;
//		}
//	}
//	//如果没找到，返回0
//	return 0;
//}//指定结点前插入
void SListInsertF(struct SListNode**pphead,struct SListNode* pos,SLTDataType x)
{//生成一个新的结点struct SListNode* newnode = BuyListNode(x);//只有一个结点或者链表为空，进行头插if (*pphead == pos){newnode->next = *pphead;*pphead= newnode;}else{//设计一个结构体指针来找pos的前一个结点struct SListNode* posprev = *pphead;while (posprev->next != pos){posprev = posprev->next;}posprev->next = newnode;newnode->next = pos;	}
}
//指定结点后插入
void SListInsertB(struct SListNode**pphead,struct SListNode* pos,SLTDataType x)
{//生成一个新的结点struct SListNode* newnode = BuyListNode(x);//新结点指针域指向该结点的后一个newnode->next = pos->next;//结点的指针域指向新结点pos->next = newnode;
}//指定位置删除
void SListEarse(struct SListNode** pphead, struct SListNode* pos)
{//如果链表为空，返回空，也可以使用assert(*pphead!=NULL)if (*pphead == NULL){return;}//要删除的结点是第一个结点if (pos == *pphead){//找到下一个结点的地址struct SListNode* prev = (*pphead)->next;//释放第一个结点free(*pphead);//头指针指向第二个结点*pphead= prev;}else{//要找到pos结点的前一个结点位置struct SListNode* posprev = *pphead;while (posprev->next != pos){posprev = posprev->next;}//让posprev的指针域指向下下个结点posprev->next = pos->next;//释放结点pos的空间free(pos);pos= NULL;}	
}//清空链表
void SListDestory(struct SListNode** pphead)
{struct SListNode* prev = *pphead;while ((*pphead)!= NULL){//找到头指针指向的结点prev = *pphead;//让头指针指向下一个结点*pphead = (*pphead)->next;//释放前面的结点free(prev);}
}

text.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SingleLinkedList.h"void text1()
{struct SListNode* head = NULL;SListPushFront(&head, 5);SListPushFront(&head, 50);SListPushFront(&head, 50);SListPushFront(&head, 5);struct SListNode* pos = SListFind(head, 50);int i = 1;//查找多个相同的值while (pos){printf("第%d个pos节点:%p->%d\n", i++, pos, pos->data);//pos指向目标结点的下一个结点pos = SListFind(pos->next, 50);}SListPrint(head);//修改pos = SListFind(head, 50);if (pos){pos->data = 30;}SListPrint(head);}void text2()
{struct SListNode* head = NULL;//插入SListPushBack(&head, 2);SListPushBack(&head, 5);SListPushBack(&head, 15);//查找14位置struct SListNode* pos = SListFind(head, 14);//判断是否有14if (pos == NULL){printf("没有该数据\n");}else{//删除14SListEarse(&head, pos);}SListPrint(head);//清空SListDestory(&head);//插入SListPushBack(&head, 2);SListPushBack(&head, 5);SListPrint(head);
}int main()
{/*text1();*/text2();return 0;
}

五：小结

相较于顺序表，链表能够更好的利用零散的空间，并且插入数据不需要大量移动数据，但是单链表在物理层上不是连续存储的，我们只能前找后却无法后找前，而且一旦指针域的数据丢失我们就没法找到后续结点，后续的双向链表可以很好的解决这个问题。

顺序表讲解链接：http://t.csdn.cn/V96aI

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：流程图：yFiles.NET Complete 5.5.0 Crack

下一篇：【NLP】一文读懂Bert模型

相关内容

热门资讯

武汉摩尔影城安卓系统APP,便... 你有没有想过，一部手机就能带你走进电影的世界，享受大屏幕带来的震撼？今天，就让我带你详细了解武汉摩尔...
联想刷安卓p系统,畅享智能新体... 你有没有发现，最近联想的安卓P系统刷机热潮可是席卷了整个互联网圈呢！这不，我就迫不及待地来和你聊聊这...
mac从安卓系统改成双系统,双... 你有没有想过，你的Mac电脑从安卓系统改成双系统后，生活会有哪些翻天覆地的变化呢？想象一边是流畅的苹...
kindke安卓系统激活码,激... 亲爱的读者，你是否在寻找一款能够让你手机焕然一新的操作系统？如果你是安卓用户，那么今天我要给你带来一...
萤石云监控安卓系统,安卓系统下... 你有没有想过，家里的安全可以随时随地掌握在手中？现在，有了萤石云监控安卓系统，这不再是梦想啦！想象无...
手机安卓系统会不会爆炸,系统升... 手机安卓系统会不会爆炸——一场关于安全的探讨在当今这个数字化的世界里，手机已经成为我们生活中不可或缺...
安卓系统双清详图解,恢复出厂设... 你有没有遇到过手机卡顿、运行缓慢的问题？别急，今天就来给你详细解析一下安卓系统的“双清”操作，让你的...
召唤抽奖系统安卓直装,轻松体验... 你知道吗？现在市面上有一种特别火的玩意儿，那就是召唤抽奖系统安卓直装。是不是听起来就让人心动不已？没...
系统工具箱安卓2.3,深度解析... 你有没有发现，手机里的那些小工具，有时候就像是个神奇的百宝箱呢？今天，就让我带你一探究竟，看看安卓2...
华硕平板安卓刷机系统,解锁性能... 亲爱的数码爱好者们，你是否曾为你的华硕平板安卓系统感到厌倦，想要给它来一次焕然一新的体验呢？那就跟着...
鸿蒙系统与安卓怎么区别,差异解... 你有没有发现，最近手机圈子里有个大热门，那就是鸿蒙系统和安卓系统的区别。这两位“系统大侠”各有各的绝...
红帽系统怎么刷回安卓,红帽系统... 你是不是也和我一样，对红帽系统刷回安卓充满了好奇？别急，今天就来给你详细揭秘这个过程，让你轻松上手，...
ios安卓联想三系统,全面解析... 你有没有发现，现在的手机市场真是热闹非凡呢！各种操作系统轮番登场，让人眼花缭乱。今天，就让我带你来聊...
安卓调用系统相机并存盘,And... 你有没有想过，手机里的照片和视频，是怎么被我们随手拍下，又神奇地存到手机里的呢？今天，就让我带你一探...
安卓4.0原生系统下,引领智能... 你有没有发现，安卓4.0原生系统下，手机的使用体验简直就像打开了新世界的大门？今天，就让我带你一起探...
安卓c13系统,创新功能与性能... 你知道吗？最近安卓系统又来了一次大更新，那就是安卓C13系统。这可不是一个小打小闹的更新，而是带来了...
鸿蒙3.0脱离安卓系统,开启全... 你知道吗？最近科技圈可是炸开了锅，因为华为的新操作系统鸿蒙3.0横空出世，竟然宣布要脱离安卓系统，这...
安卓怎么应对苹果系统,安卓系统... 你知道吗？在智能手机的世界里，安卓和苹果就像是一对相爱相杀的恋人。安卓系统，这位多才多艺的“大众情人...
安卓系统如何开橱窗教程,安卓系... 你有没有想过，你的安卓手机里也能开个橱窗，展示那些你心爱的宝贝？没错，就是那种可以随时翻看、随时分享...
安卓系统软件APK,深入探究安... 你有没有发现，手机里的那些好玩的应用，其实都是靠一个小小的文件来“住”进去的？没错，就是安卓系统里的...