数据结构之单链表

片头

嗨! 小伙伴们,大家好! 在上一篇中,我们讲解了顺序表,以及用顺序表来实现通讯录,今天我们来学习单链表,准备好了吗? 我们开始咯!

一、链表

链表是线性表的一种。我们在顺序表那一章讲过，线性表（linear list）是一种具有n个相同特性的数据元素的有限序列,是一种被广泛运用的数据结构,常见的线性表有: 顺序表、链表、栈、队列、数组、字符串等等。

1.1 链表的概念及结构

链表是一种在逻辑结构上线性的，而在物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接的顺序来实现的，我们可以想象成一列火车，火车头就是头节点，每一节车厢都是一个节点，“车厢”与“车厢”之间用指针来建立联系。

链表的结构跟火车车厢相似，淡季时车次的车厢会相应减少，旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上,不会影响其他车厢,每一节车厢都是独立存在的。

在链表里，每节“车厢”是什么样的呢？

与顺序表不同的是，链表里的每节“车厢”都是独立申请下来的空间，我们称之为“结点/节点”。

节点的组成主要有2个部分：当前结点要保存的数据和保存下一个节点的地址（指针变量）。

图中指针变量plist保存的是第一个节点的地址,我们称plist此时"指向"第一个节点,如果我们希望plist"指向"第二个节点时,只需要修改plist保存的内容为0x0012FFA0。

Q: 为什么还需要指针变量来保存下一个节点的位置？

A: 链表中每个节点都是独立申请的(即需要插入数据时才去申请一块节点的空间),我们需要通过指针变量来保存下一个节点位置才能从当前节点找到下一个节点。

1.2 链表的分类

本章中虽然只讲解单链表的相关知识，但是实际上链表的结构非常多样，以下情况分别组合就有8种链表结构。

（1）单向/双向

(2)带头/不带头

(3)循环/非循环

所以,细分下来,8种结构分别是:

• 无头单向循环
• 无头单向非循环
• 带头单向循环
• 带头单向非循环
• 带头双向循环
• 带头双向非循环

虽然链表有这么多种结构,但是我们实际上最常用的还是这2种结构:

无头单向非循环链表: 结构简单,一般不会单独用来存数据,而是更多作为其他数据结构的子结构,如哈希表,图的邻接表等,或者作为OJ题出现。

带头双向循环链表：结构最复杂，一般用来单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外，这个结构虽然复杂，但是会带来很多优势，反而化繁为简了。

二、单链表的增删查改接口实现

 接下来，我们将手把手逐步来实现单链表的增删查改接口，此处的单链表指无头单向非循环链表。

我们演示使用vs2019,我们先创建一个新工程,并建立一个头文件"SList.h"和2个源文件"SList.c"和"test.c",它们的作用分别是:

我们首先展示"SList.h"的完整代码,不要忘记在两个源文件中引用"SList.h"

#pragma once			//防止头文件被二次引用
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef int ElemType;	//如果要修改存储的数据类型可直接在此修改
typedef struct SListNode {
	ElemType data;			//每一个结点的数据域
	struct SListNode* next; //每一个结点保存下一个结点的地址(指针域)
}SLTNode;
 
//无头单向非循环链表增删查改接口实现
 
//创建新结点
SLTNode* BuyNode(ElemType x);
 
//头部插入结点
void SLTPushFront(SLTNode** phead, ElemType x);
//尾部插入结点
void SLTPushBack(SLTNode** phead, ElemType x);
//头部删除结点
void SLTPopFront(SLTNode** phead);
//尾部删除结点
void SLTPopBack(SLTNode** phead);
 
//打印单链表
void SLPrint(SLTNode* phead);
 
//在单链表中查找数据
SLTNode* SLTFind(SLTNode* phead, ElemType x);
 
//在指定位置之前插入数据
void SLTInsert(SLTNode** phead, SLTNode* pos, ElemType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, ElemType x);
//删除pos结点
void SLTErase(SLTNode** phead, SLTNode* pos);
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos);
 
//销毁链表
void SListDestroy(SLTNode** phead);

接下来我们按照"SList.h"中的顺序逐步实现各个接口函数,每一步都详细讲解,必须让你学会

(1)创建新节点

//创建新结点
SLTNode* BuyNode(ElemType x) {
	SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));//创建新结点
	if (newNode == NULL) {	//防止空间开辟失败
		perror("malloc fail!\n");
		exit(1);
	}
	newNode->data = x;		//初始化新结点的数据域
	newNode->next = NULL;	//初始化新结点中存放的指针变量
	return newNode;			//返回新结点的地址
}

(2)头部插入节点

//头部插入结点
void SLTPushFront(SLTNode** pphead, ElemType x) {
	assert(pphead);//断言,防止传入空指针
//这里不需要对*pphead进行断言,因为*pphead为NULL时说明链表为空,可以插入节点
	SLTNode* newNode = BuyNode(x);//创建新结点
	newNode->next = *pphead;	  //新结点中存放原来头结点的地址
	*pphead = newNode;			  //再把新结点的地址存放到头结点指针中
}

插入和删除操作都需要对指向节点的指针中存放的地址进行修改,而传入一级指针属于传值调用,形参的改变不会影响到实参,所以需要传入二级指针。

测试一下：

注意： SLPrint可以跳转到<(6)打印单链表>部分查看

(3)尾部插入节点

//尾部插入结点
void SLTPushBack(SLTNode** phead, ElemType x) {
	assert(phead);//断言,防止传入空指针
 
	SLTNode* newNode = BuyNode(x);//创建新结点
	if (*phead == NULL)			  //如果*pphead为空,说明链表为空
	{	
		*phead = newNode;		  //新结点的地址即为头结点的地址
		return;
	}
 
	//链表不为空
	SLTNode* pcur = *phead;		 //创建一个pcur指针用来从头找到尾
	while (pcur->next != NULL)   //当pcur指向结点的next指针域不为空,则没有找到尾结点
	{
		pcur = pcur->next;		 //pcur继续找下一个结点
	}
	pcur->next = newNode;		 //尾结点的指针域存放新结点的地址
	newNode->next = NULL;		 //新结点的next指针域为NULL
}

测试一下:

(4)头部删除节点

//头部删除结点
void SLTPopFront(SLTNode** phead) {
	assert(phead);		//断言,防止传入空指针
	assert(*phead);		//断言,防止链表为空还在执行删除
 
	//如果链表中只有一个结点,那么将该结点释放
	if ((*phead)->next == NULL) 
	{
		free(*phead);
		*phead = NULL;
		return;
	}
 
	SLTNode* del = *phead;//保存头结点的地址
	*phead = (*phead)->next;//更新头结点
	free(del);				//释放原头结点的空间
	del = NULL;
}

测试一下:

(5)尾部删除节点

//尾部删除结点
void SLTPopBack(SLTNode** phead) {
	assert(phead);		//断言,防止传入空指针
	assert(*phead);		//断言,防止链表为空还在执行删除
 
	if ((*phead)->next == NULL) //此时链表中只有1个结点
	{
		free(*phead);			//释放结点空间
		*phead = NULL;			//置空
		return;
	}
 
	SLTNode* prev = *phead; //定义prev指针来保存pcur指针的前一个位置
	SLTNode* pcur = *phead; //用来查找尾结点
	while (pcur->next != NULL) {
		prev = pcur;		//把pcur的地址赋给prev
		pcur = pcur->next;	//pcur指向下一个结点
	}
	prev->next = NULL;		//倒数第二个结点的next指针域为NULL
	free(pcur);				//将最后一个结点释放
	pcur = NULL;			//置空
}

测试一下:

(6)打印单链表

void SLPrint(SLTNode* phead) {
	//这里不需要断言,因为phead有可能为空
	SLTNode* pcur = phead;	//定义pcur,用来遍历单链表
	while (pcur != NULL) 
	{
		printf("%d ", pcur->data);//打印结点的数据域
		pcur = pcur->next;		  //找到下一个结点
	}
	printf("NULL\n");
}

(7)在单链表中查找数据

//查找
SLTNode* SLTFind(SLTNode* phead, ElemType x) {
	assert(phead);			//断言,防止传入空指针
	SLTNode* pcur = phead;  //定义结点指针pcur指向第一个结点
	while (pcur != NULL)	//循环遍历单链表
	{
		if (pcur->data == x) //如果此时结点的数据域为x
		{
			return pcur;	 //将该结点返回
		}
		pcur = pcur->next;	 //继续查找下一个结点
	}
	return NULL;			 //遍历完链表,没找到,返回NULL
}

因为返回了目标数据所在的节点地址,可以将这个函数与后面的几个函数进行搭配。

（8）在pos位置之前插入节点

//在指定位置之前插入数据
void SLTInsert(SLTNode** phead, SLTNode* pos,ElemType x) {
	assert(phead);	//断言,防止传入空指针
	assert(*phead);	//断言,防止第一个结点为空
	assert(pos);	//断言,防止传入空指针
 
	//如果pos是头结点,进行头插
	if (pos == *phead) {
		SLTPopFront(phead);	//进行头插操作
		return;
	}
 
	//pos的位置不是头结点
	SLTNode* newNode = BuyNode(x);	//创建新结点
	SLTNode* pcur = *phead;			//将头结点的地址赋给pcur
	while (pcur->next != pos)		//循环找到pos的前一个结点
	{
		pcur = pcur->next;			//继续寻找下一个结点
	}
	newNode->next = pos;			//将pos位置的结点地址传给新结点的next指针域
	pcur->next = newNode;			//将新结点的地址传给pcur结点的next指针域
}

测试一下：

(9)在pos位置之后插入节点

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, ElemType x) {
	assert(pos);					//断言,防止传入空指针
	SLTNode* newNode = BuyNode(x);  //创建新结点
	newNode->next = pos->next;		//先把pos的后一个结点的地址赋给新结点的next指针域
	pos->next = newNode;			//更新pos的next指针域,指向新结点
}

注意啦! 这里的后两行代码顺序一定不能调换,pos->next先指向newNode的话, newNode->next中存放的就变成自己的地址了,链表此时就变成循环的了。

测试一下：

（10）删除pos位置的节点

//删除pos结点
void SLTErase(SLTNode** phead, SLTNode* pos) {
	assert(phead);				//断言,防止传入空指针
	assert(*phead);				//断言,防止链表为空还进行删除
	assert(pos);				//断言,防止传入空指针
		
	//如果pos是头结点(第一个结点),没有前驱结点,执行头删
	if (pos == *phead) {
		SLTPopFront(phead);		//执行头删
		return;
	}
 
	//pos的位置不是头结点
	SLTNode* pcur = *phead;//把头结点的地址传给pcur
	while (pcur->next != pos) //pcur的下一个结点不是pos时
	{
		pcur = pcur->next;//继续寻找下一个结点
	}
	SLTNode* del = pos;	//将pos结点的地址用del结点指针存储起来
	pcur->next = del->next;//将pcur结点与pos的下一个结点连接
	free(del);			//释放pos结点
	del = NULL;			//置空
}

测试一下:

(11)删除pos位置的下一个节点

//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos) {
	assert(pos);			 //断言,防止传入空指针
	assert(pos->next);		 //pos的next不能为空
	SLTNode* del = pos->next;//保存pos位置的下一个结点地址
	pos->next = del->next;	 //将pos结点与下下个结点连接
	free(del);				 //释放pos位置的下一个结点
	del = NULL;				 //置空
}

测试一下:

(12) 销毁链表

//销毁链表
void SListDestroy(SLTNode** phead) {
	SLTNode* p = *phead;//用p来保存第一个结点的地址
	while (p != NULL)	//如果p不为空,那就继续查找下一个结点
	{
		SLTNode* q = p->next;//结点指针q保存p位置的下一个结点的地址
		free(p);			 //将p结点释放
		p = q;				 //将q的值赋给p
	}
	phead = NULL;			 //将链表置为空
	printf("链表销毁成功!\n");
}

测试一下:

 

OK啦! 单链表的核心接口函数都被我们实现啦,下面是"SList.c"文件的完整代码:

#include"SList.h"
void SLPrint(SLTNode* phead) {
	//这里不需要断言,因为phead有可能为空
	SLTNode* pcur = phead;	//定义pcur,用来遍历单链表
	while (pcur != NULL) 
	{
		printf("%d ", pcur->data);//打印结点的数据域
		pcur = pcur->next;		  //找到下一个结点
	}
	printf("NULL\n");
}
 
//头部插入删除/尾部插入删除
 
//创建新结点
SLTNode* BuyNode(ElemType 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 SLTPushBack(SLTNode** phead, ElemType x) {
	assert(phead);//断言,防止传入空指针
 
	SLTNode* newNode = BuyNode(x);//创建新结点
	if (*phead == NULL)			  //如果*pphead为空,说明链表为空
	{	
		*phead = newNode;		  //新结点的地址即为头结点的地址
		return;
	}
 
	//链表不为空
	SLTNode* pcur = *phead;		 //创建一个pcur指针用来从头找到尾
	while (pcur->next != NULL)   //当pcur指向结点的next指针域不为空,则没有找到尾结点
	{
		pcur = pcur->next;		 //pcur继续找下一个结点
	}
	pcur->next = newNode;		 //尾结点的指针域存放新结点的地址
	newNode->next = NULL;		 //新结点的next指针域为NULL
}
 
//头部插入结点
void SLTPushFront(SLTNode** pphead, ElemType x) {
	assert(pphead);//断言,防止传入空指针
//这里不需要对*pphead进行断言,因为*pphead为NULL时说明链表为空,可以插入节点
	SLTNode* newNode = BuyNode(x);//创建新结点
	newNode->next = *pphead;	  //新结点中存放原来头结点的地址
	*pphead = newNode;			  //再把新结点的地址存放到头结点指针中
}
 
//尾部删除结点
void SLTPopBack(SLTNode** phead) {
	assert(phead);		//断言,防止传入空指针
	assert(*phead);		//断言,防止链表为空还在执行删除
 
	if ((*phead)->next == NULL) //此时链表中只有1个结点
	{
		free(*phead);			//释放结点空间
		*phead = NULL;			//置空
		return;
	}
 
	SLTNode* prev = *phead; //定义prev指针来保存pcur指针的前一个位置
	SLTNode* pcur = *phead; //用来查找尾结点
	while (pcur->next != NULL) {
		prev = pcur;		//把pcur的地址赋给prev
		pcur = pcur->next;	//pcur指向下一个结点
	}
	prev->next = NULL;		//倒数第二个结点的next指针域为NULL
	free(pcur);				//将最后一个结点释放
	pcur = NULL;			//置空
}
 
//头部删除结点
void SLTPopFront(SLTNode** phead) {
	assert(phead);		//断言,防止传入空指针
	assert(*phead);		//断言,防止链表为空还在执行删除
 
	//如果链表中只有一个结点,那么将该结点释放
	if ((*phead)->next == NULL) 
	{
		free(*phead);
		*phead = NULL;
		return;
	}
 
	SLTNode* del = *phead;//保存头结点的地址
	*phead = (*phead)->next;//更新头结点
	free(del);				//释放原头结点的空间
	del = NULL;
}
 
//查找
SLTNode* SLTFind(SLTNode* phead, ElemType x) {
	assert(phead);			//断言,防止传入空指针
	SLTNode* pcur = phead;  //定义结点指针pcur指向第一个结点
	while (pcur != NULL)	//循环遍历单链表
	{
		if (pcur->data == x) //如果此时结点的数据域为x
		{
			return pcur;	 //将该结点返回
		}
		pcur = pcur->next;	 //继续查找下一个结点
	}
	return NULL;			 //遍历完链表,没找到,返回NULL
}
//在指定位置之前插入数据
void SLTInsert(SLTNode** phead, SLTNode* pos,ElemType x) {
	assert(phead);	//断言,防止传入空指针
	assert(*phead);	//断言,防止第一个结点为空
	assert(pos);	//断言,防止传入空指针
 
	//如果pos是头结点,进行头插
	if (pos == *phead) {
		SLTPushFront(phead,x);	//进行头插操作
		return;
	}
 
	//pos的位置不是头结点
	SLTNode* newNode = BuyNode(x);	//创建新结点
	SLTNode* pcur = *phead;			//将头结点的地址赋给pcur
	while (pcur->next != pos)		//循环找到pos的前一个结点
	{
		pcur = pcur->next;			//继续寻找下一个结点
	}
	newNode->next = pos;			//将pos位置的结点地址传给新结点的next指针域
	pcur->next = newNode;			//将新结点的地址传给pcur结点的next指针域
}
 
//删除pos结点
void SLTErase(SLTNode** phead, SLTNode* pos) {
	assert(phead);				//断言,防止传入空指针
	assert(*phead);				//断言,防止链表为空还进行删除
	assert(pos);				//断言,防止传入空指针
		
	//如果pos是头结点(第一个结点),没有前驱结点,执行头删
	if (pos == *phead) {
		SLTPopFront(phead);		//执行头删
		return;
	}
 
	//pos的位置不是头结点
	SLTNode* pcur = *phead;//把头结点的地址传给pcur
	while (pcur->next != pos) //pcur的下一个结点不是pos时
	{
		pcur = pcur->next;//继续寻找下一个结点
	}
	SLTNode* del = pos;	//将pos结点的地址用del结点指针存储起来
	pcur->next = del->next;//将pcur结点与pos的下一个结点连接
	free(del);			//释放pos结点
	del = NULL;			//置空
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, ElemType x) {
	assert(pos);					//断言,防止传入空指针
	SLTNode* newNode = BuyNode(x);  //创建新结点
	newNode->next = pos->next;		//先把pos的后一个结点的地址赋给新结点的next指针域
	pos->next = newNode;			//更新pos的next指针域,指向新结点
}
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos) {
	assert(pos);			 //断言,防止传入空指针
	assert(pos->next);		 //pos的next不能为空
	SLTNode* del = pos->next;//保存pos位置的下一个结点地址
	pos->next = del->next;	 //将pos结点与下下个结点连接
	free(del);				 //释放pos位置的下一个结点
	del = NULL;				 //置空
}
//销毁链表
void SListDestroy(SLTNode** phead) {
	SLTNode* p = *phead;//用p来保存第一个结点的地址
	while (p != NULL)	//如果p不为空,那就继续查找下一个结点
	{
		SLTNode* q = p->next;//结点指针q保存p位置的下一个结点的地址
		free(p);			 //将p结点释放
		p = q;				 //将q的值赋给p
	}
	*phead = NULL;			 //将链表置为空
	printf("链表销毁成功!\n");
}

片尾

今天我们学习了什么是单链表以及如何实现单链表,希望看完这篇文章能对友友们有所帮助 !   !   !

求点赞收藏加关注 !   !   !

谢谢大家 !   !   !