【数据结构】单链表

发布时间:2024年01月23日

上回我们一起学习了线性表中的顺序表,今天我们将一起来学链表中的单链表。

1. 链表的概念及结构

概念:链表是?种物理存储结构上非连续非顺序的存储结构,数据元素的逻辑顺序通过链表
中的指针链接次序实现的
链表的结构跟火车车厢相似,淡季时车次的车厢会相应减少,旺季时车次的车厢会额外增加几节。只需要将火车的某节车厢去掉/加上,不会影响其他车厢,每节车厢都是独立存在的,且每节车厢都有车门,你只能再火车上移动,车厢是独立存在的,只能从所以前面的车厢一节一节的往后走,从这节车尾到下节车头。
在链表里,每节“车厢”是什么样的呢? 如图:
与顺序表不同的是,链表里的每节"车厢"都是独立申请下来的空间,我们称之为“结点/节点”
节点的组成主要有两个部分:当前节点要保存的数据和保存下?个节点的地址(指针变量)。 图中指针变量 plist保存的是第?个节点的地址,我们称plist此时“指向”第?个节点,如果我们希望plist“指向”第?个节点时,只需要修改plist保存的内容为0x0012FFA0。
链表中每个节点都是独立申请的(即需要插?数据时才去申请一块节点的空间),我们需要通过指针 变量来保存下?个节点位置才能从当前节点找到下?个节点。
再结构体时我们可能会学过每个节点的写法:
//假设保存的是整型的数据类型
struct SListNode
{
 int data; //节点数据
 struct SListNode* next; //指针变量?保存下?个节点的地址
};
当我们想要保存?个整型数据时,实际是向操作系统申请了?块内存,这个内存不仅要保存整型数
据,也需要保存下?个节点的地址(当下?个节点为空时保存的地址为空)。当我们想要从第?个节点走到最后?个节点时,只需要在前?个节点拿上下?个节点的地址就可以了。
注意:
1、链式机构在逻辑上是连续的,在物理结构上不一定连续
2、节点?般是从堆上申请的
3、从堆上申请来的空间,是按照?定策略分配出来的,每次申请的空间可能连续,可能不连续

2.单链表的实现

具体我还是和上篇的顺序表一样写。大家测试的话,可以自己尝试

首先我们要写一个单链表,包含增删查改等操作。

我们先像上回的顺序表定义三个文件

头文件,程序文件,测试文件
首先是头文件,因为我们要完成单链表的增删改查,所以我们先定义一个头文件,声明我们所需要的函数。
#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);

我们逐步来实现

1.打印和开辟

打印

其实很简单,话不多说,直接上代码:

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

就是检查每节”车厢“后面是否还有”车厢“,有的话就打印数据,没有的话就是NULL也就会停止。

开辟空间

其实就和顺序表差不多,检查是否有多鱼的空间,没有就开辟,不过这个是检查最后面的一节车厢,后面是否还有车厢可以用来存放数据,没有的话就加上一节车厢,然后再存放数据。
代码示例:
SLTNode* SLTBuyNode(SLTDataType x) {
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL) {
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

2.头插/尾插

头插

就是再火车前接上一节车厢。

本来有0,1,2,3四节车厢,现在再车头接上4这节车厢,过程如图:

代码思路就是再申请一个节点,然后把原来的第一个节点自身的地址给新的第一个节点。
代码示例:
?
void SLTPushFront(SLTNode** pphead, SLTDataType x) {
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);

	//newnode *pphead
	newnode->next = *pphead;
	*pphead = newnode;
}

尾插

思路和头插差不多只不过这回是把新的车厢接到最后,过程如图

把新的4接到3后面,但是我们要考虑如果本来就是NULL的情况,所以代码示例:

void SLTPushBack(SLTNode** pphead, SLTDataType x) {
	assert(pphead);

	SLTNode* newnode = SLTBuyNode(x);

	//链表为空,新节点作为phead
	if (*pphead == NULL) {
		*pphead = newnode;
		return;
	}
	//链表不为空,找尾节点
	SLTNode* ptail = *pphead;
	while (ptail->next)
	{
		ptail = ptail->next;
	}
	//ptail就是尾节点
	ptail->next = newnode;
}

如果要避免问题,可以再头插也加上一个判断。不过那样的,我们不用下载写个插入,可以偷个懒,直接调用尾插,去给NULL加上数据,感兴趣的可以自己尝试。

3.头删/尾删

有了前面的例子大家想必一下子就想到了写法,头删和尾删的过程如图:

头删就是把第一个节点销毁,尾删就是销毁最后一个节点,并将倒数第二个节点中的next指针,指向NULL

代码示例:

尾删:

void SLTPopBack(SLTNode** pphead) {
	assert(pphead);
	//链表不能为空
	assert(*pphead);

	//链表不为空
	//链表只有一个节点,有多个节点
	if ((*pphead)->next == NULL) {
		free(*pphead);
		*pphead = NULL;
		return;
	}
	SLTNode* ptail = *pphead;
	SLTNode* prev = NULL;
	while (ptail->next)
	{
		prev = ptail;
		ptail = ptail->next;
	}

	prev->next = NULL;
	//销毁尾结点
	free(ptail);
	ptail = NULL;
}

头删:

void SLTPopFront(SLTNode** pphead) {
	assert(pphead);
	//链表不能为空
	assert(*pphead);

	//让第二个节点成为新的头
	//把旧的头结点释放掉
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

4.查找

这个功能就比较有意思了,说白了就是遍历。就航向你去火车上找人一样,你如果不知道他再不在,你是不是得从车头一直往车走,然后一节车厢一节车厢地找他。所以代码写法很明了了。

代码示例:

SLTNode* SLTFind(SLTNode** pphead, SLTDataType x) {
	assert(pphead);

	//遍历链表
	SLTNode* pcur = *pphead;
	while (pcur) //等价于pcur != NULL
	{
		if (pcur->data == x) {
			return pcur;
		}
		pcur = pcur->next;
	}
	//没有找到
	return NULL;
}

5.删除pos后的节点

完成字写我们可以加点难度了,我们要删除一个pos后的节点,我们该怎么办?

解决方法如图:

我们只需要,把pos->next改成pos->next->next,释放删除的空间,因为是pos后一个节点这里我们不用考虑如果只有一个节点的情况

代码示例:

void SLTEraseAfter(SLTNode* pos) {
	assert(pos);
	//pos->next不能为空
	assert(pos->next);

	//pos  pos->next  pos->next->next
	SLTNode* del = pos->next;
	pos->next = pos->next->next;
	free(del);
	del = NULL;
}

6.删除pos节点

思路解析如图

我们只要把pos中pos->next给到上面的一个节点就行,但是,这回我们得讨论当只有一个节点的时候,这是我们可以直接调用头删。

代码示例:

void SLTErase(SLTNode** pphead, SLTNode* pos) {
	assert(pphead);
	assert(*pphead);
	assert(pos);

	//pos刚好是头结点,没有前驱节点,执行头删
	if (*pphead == pos) {
		//头删
		SLTPopFront(pphead);
		return;
	}

	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	//prev pos pos->next
	prev->next = pos->next;
	free(pos);
	pos = NULL;
}

7.在指定位置之后插入数据

也就是类似再某个数组的下标加上一个数据。

思路如图:

也是简单的交换节点中存储的数据的问题
代码示例:
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
	assert(pos);

	SLTNode* newnode = SLTBuyNode(x);

	//pos newnode pos->next
	newnode->next = pos->next;
	pos->next = newnode;
}

8.在指定位置之前插入数据

也是差不多,只是要思考pos为phead的情况
代码示例:
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
	assert(pphead);
	assert(pos);
	//要加上链表不能为空
	assert(*pphead);

	SLTNode* newnode = SLTBuyNode(x);
	//pos刚好是头结点
	if (pos == *pphead) {
		//头插
		SLTPushFront(pphead, x);
		return;
	}

	//pos不是头结点的情况
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	//prev -> newnode -> pos
	prev->next = newnode;
	newnode->next = pos;
}

9.销毁单链表

我们都知道动态内存开辟后是一定要销毁的,那么单链表该怎么销毁呢?

这里我提供了一个方法:从头向尾一个一个节点遍历,释放空间

代码示例:

void SListDesTroy(SLTNode** pphead) {
	assert(pphead);
	assert(*pphead);

	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

注意:我这里定义了一个next来保存节点的地址,不可直接释放pcur不然你就找不到下一个节点了。


这篇我们简单了解了以下单链表,希望大家能够多多练习。

天气越来越冷了,注意保暖。

文章来源:https://blog.csdn.net/2301_80017277/article/details/135770683
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。