C——单链表

2024-06-04 1366阅读

一.前言

我们在前面已经了解了链表中的双向链表，而我们在介绍链表分类的时候就说过常用的链表只有两种——双向带头循环链表和单向不带头不循环链表。下来我来介绍另一种常用的链表——单向不带头不循环链表也叫做单链表。不清楚链表分类的以及不了解双向链表的可以看我之前的博客C——双向链表-CSDN博客。

二.单链表的结构

我们已经了解了单链表的全称叫做单向不带头不循环链表，我们怎么理解这链表前面的修饰词呢？其实，单链表就像是一节节连接起来的火车车厢一样。但是这节车厢只可以向后走，并且火车的车头和车尾是不能连接在一起的。C——单链表 第1张

我们照着这张图再来分析单链表的结构：单向的意思就是只能沿着D->A->C->E->Z->X->W这个方向走，那不带头的意思就是没有头节点即哨兵位，我们在讲双向链表的时候提到了哨兵位，他只是一个没有有效数据的头节点。不循环的意思我们也可以对照这双向链表来看，双向链表的尾节点可以找到头节点，头节点也可以找到尾节点，这就是循环；而单链表的尾节点指向的不是头节点而是NULL，头节点也不能找到尾节点。

那么单链表的节点到底是什么样的呢？C——单链表 第2张

 我们再来与双向链表的节点进行对比一下：C——单链表 第3张

 单链表节点只有两个成员，分别是数据和指向下一个节点的指针，而双向链表的节点有三个成员，分别是数据，指向前一个节点的指针和指向下一个节点的指针。C——单链表 第4张

综上所述：单链表是一个只能指向下一个节点的链表，而且没有头节点，并且是不循环的。 

三.实现单链表

与双向链表的实现相似，实现单链表也需要很多的函数及头文件，所以我们将所有的函数声明和头文件都放到singlelist.h中，函数的实现都放入singlelist.c中。C——单链表 第5张

3.1单链表节点的结构

//链表节点
struct SingleList
{
	int val;
	struct SingleList* next;
};

我们这样写虽然可以完成链表的基本结构，但是难道我们链表只能存储整形嘛？如果我们创建了很多个整型节点，但是有一天我们想利用链表存储字符型或者浮点型数据，那么我们就得一个一个的去修改，费时费力；还有就是这个节点的名称很长，在后面的代码中会重复出现，也很浪费时间。所以我们可以利用typedef关键词，对节点重命名，以及对int重命名。

//节点数据类型
typedef int SingleListdatatype;
//链表节点
typedef struct SingleListNode
{
	SingleListdatatype val;
	struct SingleListNode* next;
}SLNode;

这样我们在多次使用该类型的时候就不需要再写那么长一串了，以后再修改储存的数据类型的时候也就不用一个一个节点的修改了，只需将定义的节点数据类型中的数据类型修改即可。

3.2单链表节点的创建

 我们在创建节点的时候实际上就是创建一个结构体变量，我们可以利用动态内存管理为我们的每一个节点动态开辟一块内存空间。C——单链表 第6张

//节点的创建
SLNode* BuyNode(SingleListdatatype x)
{
	SLNode* node = (SLNode*)malloc(sizeof(SLNode));
	if (node == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	node->val = x;
	node->next = NULL;
	return node;
}

 我们来测试一下节点创建函数是否正确：C——单链表 第7张

我们利用此测试代码来调试发现，我们创建了4个节点，通过调试也确实观察到了这四个节点，并且它们储蓄的数据就是我们传的数据，指向下一个节点的指针也是NULL。与我们想要实现的结果相同。 

那我们现在将这四个节点连接起来：

void test1()
{
	SLNode* plist = NULL;
	SLNode* plist1 = BuyNode(1);
	SLNode* plist2 = BuyNode(2);
	SLNode* plist3 = BuyNode(3);
	SLNode* plist4 = BuyNode(4);
	plist1->next = plist2;
	plist2->next = plist3;
	plist3->next = plist4;
}
int main()
{
	test1();
	return 0;
}

我们再来调试一下： C——单链表 第8张

我们看到将所有节点连接起来之后，我们就可以利用第一个节点找到后面的节点。 

3.3链表的打印

C——单链表 第9张

//链表的打印
void SLNodePrint(SLNode* plist)
{
	while (plist)//plist != NULL
	{
		printf("%d->", plist->val);
		plist = plist->next;
	}
	printf("NULL\n");
}

 我们再来测试一下该函数：C——单链表 第10张

也是没有出现问题，说明我们链表的打印已经完成了。 

3.4尾插

我们现在创建的节点需要我们手动将其连接起来，我们可以利用尾插方法，将新创建的节点直接连接到前一个节点上。 C——单链表 第11张

//尾插
void SLNodepushback(SLNode** plist, SingleListdatatype x)
{
	assert(plist);
	SLNode* newnode = BuyNode(x);//新节点
	if (*plist == NULL)
	{
		//空链表
		*plist = newnode;
	}
	else
	{
		//非空链表
		//遍历原链表，找到尾节点
		SLNode* pcur = *plist;
		while (pcur->next)//(*plist)->next != NULL
		{
			pcur = pcur->next;
		}
		pcur->next = newnode;
	}
}

我们测试下尾插方法：C——单链表 第12张

我们尾插了四次，通过打印方法，将链表打印出来，说明我们的尾插方法也没有问题。但是有些人可能会有疑问：为什么这里传的是二级指针 而不传一级指针？

因为我们是通过一个结构体类型的指针来维护我们的链表，而我们传一级指针的话相当于值传递，而对于值传递来说，形参改变是不影响实参的。简单来说，就说你在函数内部将形参节点的next指针改变了，但是却不影响实参的值。达不到我们的目的。所以要想形参的改变影响实参的话，我们就得地址传递，就得传一级指针的地址，也就是二级指针

3.5头插 

头插从名字就可以听出来是把一个新节点插到链表的头部，我们利用图来分析如何进行头插：C——单链表 第13张

//头插
void SLpushfront(SLNode** plist, SingleListdatatype x)
{
	assert(plist);
	SLNode* newnode = BuyNode(x);
	newnode->next = *plist;
	*plist = newnode;
}

我们测试头插方法：C——单链表 第14张

根据打印结果来看，头插的方法也没有任何问题。 

3.6尾删

尾删就是删除链表中的尾节点，那么前提就是该链表不能为空，如果都是空链表了，怎么执行删除操作呢？我们画图来分析一下：C——单链表 第15张

//尾删
void SLpopback(SLNode** plist)
{
	assert(plist && *plist);//*plist != NULL防止链表为空
	SLNode* pcur = *plist;//记录倒数第二个节点
	SLNode* del = *plist;//记录尾节点
	while (del->next)
	{
		pcur = del;
		del = del->next;
	}
	pcur->next = NULL;
	free(del);
	del = NULL;
}

我们测试之后发现出了错误，这是为什么呢？C——单链表 第16张

我们进行四次尾删，最后一次删除会将1删除掉，此时应该只打印NULL，这里打印了随机值。这是为什么呢？ C——单链表 第17张

//尾删
void SLpopback(SLNode** plist)
{
	assert(plist && *plist);//*plist != NULL防止链表为空
	if (!((*plist)->next))//(*plist)->next == NULL
	{
		//链表只有一个节点
		free(*plist);
		*plist = NULL;
	}
	else
	{
		//链表有多个节点
		SLNode* pcur = *plist;//记录倒数第二个节点
		SLNode* del = *plist;//记录尾节点
		while (del->next)
		{
			pcur = del;
			del = del->next;
		}
		pcur->next = NULL;
		free(del);
		del = NULL;
	}
}

我们现在再来测试一下修改后的尾删代码： C——单链表 第18张

我们看到，现在就没有问题了。

3.7头删

我们实现了尾删，现在来实现头删。头删的前提与尾删的前提相同：链表不能为空。头删实际上就是删除链表中的第一个节点，我们画图分析如何实现头删：C——单链表 第19张

//头删
void SLpopfront(SLNode** plist)
{
	assert(plist && *plist);//链表不能为空
	SLNode* next = (*plist)->next;
	free(*plist);
	*plist = next;
}

我们来测试头删方法：

C——单链表 第20张

没有问题~ 

那如果我们多删一次呢？C——单链表 第21张

我们看到，第五次删除的时候这时候已经是空链表了，我们再看提示的错误信息，说是断言出错了，这就说明了链表为空了。 

3.8查找数据

查找数据非常简单，我们只需要遍历链表，将要查找的数据与链表中的数据进行对比，如果找到了则返回该数据对应节点的地址；如果没找到则返回NULL。

//查找
SLNode* SLFind(SLNode* plist, SingleListdatatype x)
{
	assert(plist);
	SLNode* pcur = plist;
	while (pcur)
	{
		if (pcur->val == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

测试查找：C——单链表 第22张

结果没毛病，老铁OK了！ 

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

我们要在指定位置的前面插入数据，所以我们必须得找到该指定位置，这就需要调用我们的查找方法了。我们来画图分析一下：C——单链表 第23张

//在指定位置之前插入数据
void SLposfront(SLNode** plist, SLNode* pos, SingleListdatatype x)
{
	assert(plist && *plist);//链表不能为空，否则找不到指定位置
	if (pos == *plist)
	{
		//pos节点就是第一个节点
		//调用头插方法
		SLpushfront(plist,x);
	}
	else
	{
		//pos节点不是第一个节点
		SLNode* newnode = BuyNode(x);
		SLNode* pcur = *plist;
		SLNode* prev = *plist;
		while (pcur)
		{
			if (pcur->val == pos->val)
			{
				break;
			}
			prev = pcur;
			pcur = pcur->next;
		}
		// prev newnode pcur/pos
		prev->next = newnode;
		newnode->next = pcur;
	}
}

 我们测试该代码：

我们测试了三种位置的插入，无论是第一个节点之前还是中间节点之前或者是尾节点之前都没有问题。C——单链表 第24张

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

在指定位置之后插入数据与在指定位置之前插入数据有相同点但也有不同点，我们继续来画图分析：C——单链表 第25张

//在指定位置之后插入数据
void SLposback(SLNode* pos, SingleListdatatype x)
{
	assert(pos);
	SLNode* newnode = BuyNode(x);
	//pos newnode pos->next
	newnode->next = pos->next;
	pos->next = newnode;
}

我们对其进行测试来看： 

C——单链表 第26张

3.11删除pos节点

我们现在来删除指定节点，前提肯定是链表不能为空。我们接着来画图分析：C——单链表 第27张

//删除pos节点
void slpoppos(SLNode** plist, SLNode* pos)
{
	assert(plist && *plist);
	assert(pos);
	if (*plist == pos)
	{
		//pos是头节点，调用头删方法
		SLpopfront(plist);
	}
	else
	{
		SLNode* prev = *plist;
		while (prev->next != pos)
		{
			//找到pos的前一个节点
			prev = prev->next;
		}
		//prev pos pos->next
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

测试该代码：C——单链表 第28张 老铁没毛病！

3.12删除pos节点之后的节点

删除pos节点之后的节点我们要改变指向的指针就只有一个了，那就是pos->next指针。要让它指向pos->next->next。我们画图分析：C——单链表 第29张

//删除pos节点后一个节点
void slpopposback(SLNode* pos)
{
	assert(pos && pos->next);//pos->next != NULL避免pos是尾节点
	SLNode* Next = pos->next;
	pos->next = pos->next->next;
	free(Next);
	Next = NULL;
}

 测试代码：

C——单链表 第30张

那如果我们的pos节点就是尾节点程序会发生什么呢？ C——单链表 第31张

我们看到，上面提醒我们断言出错，说明此时pos节点为尾节点。 

3.13销毁链表

C——单链表 第32张

//销毁链表
void DestorySL(SLNode** plist)
{
	assert(plist && *plist);
	SLNode* Next = (*plist)->next;
	while (Next)
	{
		free(*plist);
		*plist = Next;
		Next = Next->next;
	}
	free(*plist);
	*plist = NULL;
}

 我们通过调试来判断我们的销毁方法:没有问题！C——单链表 第33张

到这里，我们单链表的所有方法都已经完成了。下面附上完整代码：

四.完整代码

1.singlelist.h

#pragma once
#include 
#include 
#include 
//节点数据类型
typedef int SingleListdatatype;
//链表节点
typedef struct SingleListNode
{
	SingleListdatatype val;
	struct SingleListNode* next;
}SLNode;
//节点的创建
SLNode* BuyNode(SingleListdatatype x);
//链表的打印
void SLNodePrint(SLNode* plist);
//尾插
void SLNodepushback(SLNode** plist, SingleListdatatype x);
//头插
void SLpushfront(SLNode** plist, SingleListdatatype x);
//尾删
void SLpopback(SLNode** plist);
//头删
void SLpopfront(SLNode** plist);
//查找
SLNode* SLFind(SLNode* plist, SingleListdatatype x);
//在指定位置之前插入数据
void SLposfront(SLNode** plist, SLNode* pos,SingleListdatatype x);
//在指定位置之后插入数据
void SLposback(SLNode* pos, SingleListdatatype x);
//删除pos节点
void slpoppos(SLNode** plist, SLNode* pos);
//删除pos节点后一个节点
void slpopposback(SLNode* pos);
//销毁链表
void DestorySL(SLNode** plist);

2.singlelist.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SingleList.h"
//节点的创建
SLNode* BuyNode(SingleListdatatype x)
{
	SLNode* node = (SLNode*)malloc(sizeof(SLNode));
	if (node == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	node->val = x;
	node->next = NULL;
	return node;
}
//链表的打印
void SLNodePrint(SLNode* plist)
{
	while (plist)//plist != NULL
	{
		printf("%d->", plist->val);
		plist = plist->next;
	}
	printf("NULL\n");
}
//尾插
void SLNodepushback(SLNode** plist, SingleListdatatype x)
{
	assert(plist);
	SLNode* newnode = BuyNode(x);//新节点
	if (*plist == NULL)
	{
		//空链表
		*plist = newnode;
	}
	else
	{
		//非空链表
		//遍历原链表，找到尾节点
		SLNode* pcur = *plist;
		while (pcur->next)//(*plist)->next != NULL
		{
			pcur = pcur->next;
		}
		pcur->next = newnode;
	}
}
//头插
void SLpushfront(SLNode** plist, SingleListdatatype x)
{
	assert(plist);
	SLNode* newnode = BuyNode(x);
	newnode->next = *plist;
	*plist = newnode;
}
//尾删
void SLpopback(SLNode** plist)
{
	assert(plist && *plist);//*plist != NULL防止链表为空
	if (!((*plist)->next))//(*plist)->next == NULL
	{
		//链表只有一个节点
		free(*plist);
		*plist = NULL;
	}
	else
	{
		//链表有多个节点
		SLNode* pcur = *plist;//记录倒数第二个节点
		SLNode* del = *plist;//记录尾节点
		while (del->next)
		{
			pcur = del;
			del = del->next;
		}
		pcur->next = NULL;
		free(del);
		del = NULL;
	}
}
//头删
void SLpopfront(SLNode** plist)
{
	assert(plist && *plist);//链表不能为空
	SLNode* next = (*plist)->next;
	free(*plist);
	*plist = next;
}
//查找
SLNode* SLFind(SLNode* plist, SingleListdatatype x)
{
	assert(plist);
	SLNode* pcur = plist;
	while (pcur)
	{
		if (pcur->val == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
//在指定位置之前插入数据
void SLposfront(SLNode** plist, SLNode* pos, SingleListdatatype x)
{
	assert(plist && *plist);//链表不能为空，否则找不到指定位置
	assert(pos);
	if (pos == *plist)
	{
		//pos节点就是第一个节点
		//调用头插方法
		SLpushfront(plist,x);
	}
	else
	{
		//pos节点不是第一个节点
		SLNode* newnode = BuyNode(x);
		SLNode* pcur = *plist;
		SLNode* prev = *plist;
		while (pcur)
		{
			if (pcur->val == pos->val)
			{
				break;
			}
			prev = pcur;
			pcur = pcur->next;
		}
		// prev newnode pcur/pos
		prev->next = newnode;
		newnode->next = pcur;
	}
}
//在指定位置之后插入数据
void SLposback(SLNode* pos, SingleListdatatype x)
{
	assert(pos);
	SLNode* newnode = BuyNode(x);
	//pos newnode pos->next
	newnode->next = pos->next;
	pos->next = newnode;
}
//删除pos节点
void slpoppos(SLNode** plist, SLNode* pos)
{
	assert(plist && *plist);
	assert(pos);
	if (*plist == pos)
	{
		//pos是头节点，调用头删方法
		SLpopfront(plist);
	}
	else
	{
		SLNode* prev = *plist;
		while (prev->next != pos)
		{
			//找到pos的前一个节点
			prev = prev->next;
		}
		//prev pos pos->next
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
//删除pos节点后一个节点
void slpopposback(SLNode* pos)
{
	assert(pos && pos->next);//pos->next != NULL避免pos是尾节点
	SLNode* Next = pos->next;
	pos->next = pos->next->next;
	free(Next);
	Next = NULL;
}
//销毁链表
void DestorySL(SLNode** plist)
{
	assert(plist && *plist);
	SLNode* Next = (*plist)->next;
	while (Next)
	{
		free(*plist);
		*plist = Next;
		Next = Next->next;
	}
	free(*plist);
	*plist = NULL;
}

3.test.c 

#define _CRT_SECURE_NO_WARNINGS 1
#include "SingleList.h"
//void test1()
//{
//	SLNode* plist1 = BuyNode(1);
//	SLNode* plist2 = BuyNode(2);
//	SLNode* plist3 = BuyNode(3);
//	SLNode* plist4 = BuyNode(4);
//
//	plist1->next = plist2;
//	plist2->next = plist3;
//	plist3->next = plist4;
//
//	SLNodePrint(plist1);
//}
void test2()
{
	SLNode* plist = NULL;
	//测试尾插
	SLNodepushback(&plist, 1);
	SLNodepushback(&plist, 2);
	SLNodepushback(&plist, 3);
	SLNodepushback(&plist, 4);
	SLNodePrint(plist);
	//测试销毁链表
	DestorySL(&plist);
	//测试删除pos节点的下一个节点
	//SLNode* find = SLFind(plist, 4);
	//slpopposback(find);
	//SLNodePrint(plist);
	//测试删除pos节点
	//SLNode* find = SLFind(plist, 4);
	//slpoppos(&plist,find);
	//SLNodePrint(plist);
	//测试在指定位置之后插入数据
	//SLNode* find = SLFind(plist, 1);
	//SLposback(find,66);
	//SLNodePrint(plist);
	//测试在指定位置之前插入数据
	//SLNode* find = SLFind(plist, 4);
	//SLposfront(&plist,find,100);
	//SLNodePrint(plist);
	//测试查找
	//SLNode* find = SLFind(plist,99);
	//if (find == NULL)
	//{
	//	printf("找不到!");
	//}
	//else
	//{
	//	printf("找到了!");
	//}
	//测试头删
	//SLpopfront(&plist);
	//SLNodePrint(plist);//2 3 4
	//SLpopfront(&plist);
	//SLNodePrint(plist);//3 4
	//SLpopfront(&plist);
	//SLNodePrint(plist);//4
	//SLpopfront(&plist);
	//SLNodePrint(plist);//NULL
	//SLpopfront(&plist);
	//SLNodePrint(plist);
	//测试尾删
	//SLpopback(&plist);
	//SLNodePrint(plist);//1 2 3
	//SLpopback(&plist);
	//SLNodePrint(plist);//1 2
	//SLpopback(&plist);
	//SLNodePrint(plist);//1
	//SLpopback(&plist);
	//SLNodePrint(plist);//NULL
	//测试头插
	//SLpushfront(&plist,100);
	//SLNodePrint(plist);
	//SLpushfront(&plist,99);
	//SLNodePrint(plist);
}
int main()
{
	//test1();
	test2();
	return 0;
}

完！


相关阅读：

1、Kali Linux VPS客户端使用指南，一键搭建安全高效的远程访问通道

2、VPS新用户轻松添加指南，一步步操作教程

3、独家揭秘，VPS 125大阳摩托油耗真相，惊人数据曝光！

4、VPS现状深度解析，究竟是否仍值得使用？

5、TY云科技VPS操作指南，轻松上手，一键极速直达！

    高速稳定云服务器25元起
    免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们，邮箱：ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!

    相关阅读

    目录[+]