【数据结构】3.单链表

发布于：2025-04-20 ⋅ 阅读:(20) ⋅ 点赞:(0)

文章目录

单链表的实现

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

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;
	}
	//没有找到返回NULL
	return 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和pos
		newnode->next = pos;
		//连接prev和newnode
		prev->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查看完整源代码

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布