【数据结构】单链表之--无头单向非循环链表

前言：前面我们学习了动态顺序表并且模拟了它的实现，今天我们来进一步学习，来学习单链表！一起加油各位，后面的路只会越来越难走需要我们一步一个脚印！

💖 博主CSDN主页:卫卫卫的个人主页 💞
👉 专栏分类:数据结构 👈
💯代码仓库:卫卫周大胖的学习日记💫
💪关注博主和博主一起学习!一起努力！
在这里插入图片描述

单链表

今天我们要实现的全部功能就如下所示，功能很多我们一步一步来，一起来手撕链表吧！加油！

typedef int SLNDataType;

typedef struct SList
{
	int val;
	struct SList* next;
}SLNode;

//单链表的打印
void SLTPrint(SLNode* phead);

//单链表的尾插
void SLTPushBack(SLNode** pphead, SLNDataType x);

//单链表的头插
void SLTPushFront(SLNode** pphead, SLNDataType x);

//单链表的尾删
void SLTPopback(SLNode** pphead);

//单链表的头删
void SLTPopFront(SLNode** pphead);

//单链表的元素查找
SLNode* SLFind(SLNode* phead, SLNDataType x);

//单链表的插入-在pos的前面插入
SLNode* SLInsert(SLNode** pphead,SLNode* pos, SLNDataType x);//需要自己思考一级还是二级

//单链表的删除
void SLTErase(SLNode** pphead, SLNode* pos);


//单链表的销毁
void SLTDestroy(SLNode** pphead);


//单链表的删除-pos之后的元素
void SLTEraseAfter(SLNode* pos,SLNDataType x);

//单链表插入-pos之后插入
void SLTInsertAfter(SLNode* pos,SLNDataType x);

动态申请一个结点

代码思路，首先我们要开辟一个结构体，来开始我们今天的单链表

typedef struct SList
{
	int val;
	struct SList* next;
}SLNode;

当然了，我们肯定得写一个接口，来申请动态开辟的一个结点(这个我们在前面写顺序表的时候就写过了，就不过多介绍这个了)，可以看下图帮助自己理解在这里插入图片描述

SLNode* CreateNewNode(SLNDataType x)//开辟一个新的节点
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)//判断是否有空间
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;
	return newnode;
}

单链表的打印

代码思路：单链表中我们可以知道它是如下图这种形式，每一个结构体中存着下个节点的地址，我们可以通过判断结构体指针是否为空指针来依次打印
在这里插入图片描述

void SLTPrint(SLNode* phead)
{
	SLNode* cur = phead;//通过头节点依次访问
	while (cur != NULL)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}

单链表的尾插

在写代码之前，我们需要重新复习一下，对形参的修改不会改变实参,形参是实参的一个临时拷贝（请牢牢记住，后面有很大的作用），这在后面帮助我们理解单链表有很大的帮助。
我们先来看一串代码

void swap(int* a, int* b)
{
	int tmp = 0;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

int main()
{
	int a = 3;
	int b = 5;
	swap(&a, &b);
	printf("a = %d,b = %d", a, b);
	return 0;
}

我们要想改变
在这里插入图片描述

void swap(int** a, int** b)
{
	int tmp = 0;
	tmp = **a;
	**a = **b;
	**b = tmp;
}

int main()
{
	int arr1[] = { 1 };
	int arr2[] = { 2 };
	int* a = arr1;
	int* b = arr2;
	swap(&a, &b); 
	printf("*a = %d, *b = %d",*a, *b);
	return 0;
}

在这里插入图片描述
由这些可以知道，我们要想修改一级指针里面的值，我们要用二级指针接收。接下来我们就开始上我们的第一盘凉菜了！
代码思路：首先我们肯定要考虑两种情况，即一种是链表是空的什么都没有，另一种即链表中有值，需要我们尾增新的值，我们可以借助下图来帮助我们分析！我们通过循环找到该链表的尾结点，然后让尾部结点中的next，假如链表中没有值是空链表，我们直接指向新的结点即可。
在这里插入图片描述

void SLTPushBack(SLNode** pphead, SLNDataType x)//尾插节点
{
	assert(pphead);//判断传过来的链表是否存在

	SLNode* newnode = CreateNewNode(x);//开辟节点
	if (*pphead == NULL)//判断传来的是否是空指针，如果为空就直接开辟新的节点
	{
		*pphead = newnode;
	}
	else
	{
		SLNode* tail = *pphead;
		while (tail->next != NULL)//只有尾结点的next才是空
		{
			tail = tail->next;//找到尾节点
		}
		tail->next = newnode;//将为节点的值指向新节点
	}
}

这里大家肯定会有很多疑问，为什么是 **phead ,我们来看下图
在这里插入图片描述

函数测试与结果运行图：

void Test1()
{
	SLNode* plist = NULL;
	SLTPushBack(&plist, 1);//尾插
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
}


int main()
{
	Test1();
	return 0;
}

在这里插入图片描述

单链表的头插

代码思路：单链表的头插我们依然得借助图像来帮助我们分析如下图，我们让*phead指向newnode开辟的结点，在让newnode->next指向原本的头结点即可完成头插，当然我们依然得用二级指针接收，因为我们要修改的一级指针。
在这里插入图片描述
代码实现：

void SLTPushFront(SLNode** pphead, SLNDataType x)//单链表的头插
{
	assert(pphead);
	SLNode* newnode = CreateNewNode(x);//开辟一个新的节点
	newnode->next = *pphead;//将头节点地址存放在next中
	*pphead = newnode;  //在让头节点指向Newnode，此时newnode就称为了头节点
}

函数测试与效果图：

void Test2()
{
	SLNode* plist = NULL;
	SLTPushFront(&plist, 2);//头插
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 9);
	SLTPrint(plist);
}

int main()
{
	//Test1();
	Test2();
	return 0;
}

在这里插入图片描述

单链表的尾删

思路分析：在单链表的尾部删除中，我们需要考虑两种情况一种为单节点，一种为多节点，即一种删除完后链表中的值为空，另一种即删除最后一个后仍然还有结点。当然了，我们依然得先画图分析，如下图。我们看图一，可以知道，我们直接找到 *phead这个结点将他free掉即可，然后将 *phead置为空指针，即可完成单结点的删除。我们看图二，我们得找到一个尾结点将它释放，将尾部结点的前一个结点中的next即保留最后一个结点中的地址，让它置为空指针即删除完毕，由此我们可以通过一个快慢指针，一个指针往后走，一个保留前一个结点的地址，因此我们可以找到最后一个结点并保留前一个结点的地址。
在这里插入图片描述

在这里插入图片描述

代码思路：

void SLTPopback(SLNode** pphead)//单链表的尾删
{
	//一个节点
	//多个节点
	assert(pphead);
	assert(*pphead);
	if ((*pphead)->next == NULL)//单节点
	{
		free(*pphead);//释放pphead所在的空间
		*pphead = NULL;//将pphead置为空指针
	}
	else//多节点
	{
		SLNode* tail = *pphead;//铜鼓快慢指针来找到节点
		SLNode* prev = NULL;
		while (tail->next != NULL)//找到尾节点
		{
			//倒数第一步(尾节点的前一个节点时)
			prev = tail;//此时prev就是记录后一个节点的地址
			tail = tail->next;//此时找到了NULL
		}
		free(tail);//释放掉记录尾结点的地址
		prev->next = NULL;//将此时赋值为NULL即删除成功
	}
}

函数测试与运行结果：

void Test3()
{
	SLNode* plist = NULL;
	printf("打印删除之前的\n");
	SLTPushFront(&plist, 2);//头增
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 9);
	SLTPrint(plist);
	printf("打印删除之后的\n");
	SLTPopback(&plist);//尾删
	SLTPopback(&plist);
	SLTPrint(plist);
}

int main()
{
	//Test1();
	//Test2();
	Test3();
	return 0;
}

在这里插入图片描述

单链表的头删

思路分析:实现头删，我们就是把头部中的空间free掉,在将 *phead指向原本的第二个节点即可，因此我们需要用一个结构体指针指向第二个节点将其保留下来传给原本的头指针。可以通过下图帮助自己分析，如下图。
在这里插入图片描述
代码思路实现：

void SLTPopFront(SLNode** pphead)//头删
{
	//空
	assert(pphead);
	//多个节点
	SLNode* tmp = (*pphead)->next;
	free(*pphead);
	*pphead = tmp;	
}

测试函数与运行结果：

void Test4()
{
	SLNode* plist = NULL;
	printf("打印删除之前的\n");
	SLTPushFront(&plist, 2);//尾增
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 9);
	SLTPrint(plist);
	printf("打印删除之后的\n");
	SLTPopFront(&plist);//头删
	SLTPopFront(&plist);
	SLTPrint(plist);
}
int main()
{
	//Test1();
	//Test2();
	//Test3();
	Test4();
	return 0;
}

在这里插入图片描述

单链表的数值查找

思路分析：我们可以通过指针去一次遍历链表中的数据，找到对应值即找到了，返回此时指针的地址，遍历到最后一个NULL也没有找到时，即返回空指针，如下图在这里插入图片描述
代码实现:

SLNode* SLFind(SLNode* phead, SLNDataType x)//查找
{
	assert(phead);
	SLNode* tail = phead;
	while (tail)
	{
		if(tail->val == x)
		{
			return tail;//返回此时指针的值
		}
		tail = tail->next;
	}
	return NULL;
}

函数测试与效果图：

void Test5()
{
	SLNode* plist = NULL;
	printf("打印删除之前的\n");
	SLTPushFront(&plist, 2);//尾增
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 9);
	SLTPrint(plist);
	printf("查找结果:\n");
	printf("%p\n",SLFind(plist, 2));//查找数
	printf("%p\n", SLFind(plist, 99));
}
int main()
{
	//Test1();
	//Test2();
	//Test3();
	//Test4();
	Test5();
	return 0;
}

在这里插入图片描述

单链表的插入- 在pos的前面插入

思路分析：如果是多节点要想实现在pos的前面插入，首先我们要找到pos的前面一个节点让它指向我们新开辟的节点newnode然后再让newnode->next指向我们原本pos的所在的节点就完成了头插，如下图1所示。如果是单节点的时候，就是相当于头插，我们只需要判断是否是单节点，如果是就直接调用头插函数即可。
在这里插入图片描述
代码实现：

SLNode* SLInsert(SLNode** pphead, SLNode* pos, SLNDataType x)//单链表插入
{
	assert(pphead);
	assert(pos);
	assert(*pphead);
	//单节点
	if (*pphead == pos)
	{
		//头插
		SLTPushFront(pphead, x);
	}
	else
	{
		//多节点
		SLNode* tail = *pphead;
		SLNode* newnode = CreateNewNode(x);
		while (tail->next != pos)
		{
			tail = tail->next;
		}
		tail->next = newnode;
		newnode->next = pos;
	}
}

函数测试与效果图：

void Test6()
{
	SLNode* plist = NULL;
	printf("原本的值\n");
	SLTPushFront(&plist, 2);//尾增
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 9);
	SLTPrint(plist);
	printf("插入之后的结果\n");
	SLNode* address = SLFind(plist, 2);//查找数
	SLInsert(&plist, address, 10);
	SLTPrint(plist);
}
int main()
{
	//Test1();
	//Test2();
	//Test3();
	//Test4();
	//Test5();
	Test6();
	return 0;
}

在这里插入图片描述

单链表数值的删除-删除Pos前的值

思路分析：当然了单链表的删除我们依然得采用俩种情况，一种情况为单节点，一种情况为多节点，我们先来分析多节点，如果是多节点的情况，我们应当找到pos的节点将它释放掉，并且我们应当将pos的前一个节点将他记录下来，并让它指向pos之后的一个节点，此时我们即可完成数值的删除。如下图所示，如果是单节点的情况，我们可以直接当成头删，直接调用头删函数即可。
在这里插入图片描述

代码实例：

void SLTErase(SLNode** pphead, SLNode* pos)//数值的删除
{
	assert(pphead);//判断传来的结构体是否存在
	assert(*pphead);//判断是否为空指针
	assert(pos);//判断空地址
	if (*pphead == pos)
	{
		SLTPopFront(pphead);//头删
	}
	else
	{
		SLNode* tail = *pphead;
		while (tail->next != pos)
		{
			tail = tail->next;
		}
		tail->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

函数测试与效果图：

void Test7()
{
	SLNode* plist = NULL;
	printf("原本的值\n");
	SLTPushFront(&plist, 2);//尾增
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 9);
	SLTPrint(plist);
	printf("删除之后的结果\n");
	SLNode* address = SLFind(plist, 2);//查找数
	SLTErase(&plist, address);
	SLTPrint(plist);
}
int main()
{
	//Test1();
	//Test2();
	//Test3();
	//Test4();
	//Test5();
	//Test6();
	Test7();
	return 0;
}

在这里插入图片描述

单链表的销毁

思路分析：要想销毁单链表中的所有值，我们只需要把单链表中的每个节点给它释放，并最后让头节点指向空指针即可，因此我们需要借助两个指针，一个指针指向tail的下一个节点，当释放掉tail后让tail可以指向下一个节点再依次释放，这样就可以达到链表的销毁的作用，如下图所示。
在这里插入图片描述
代码实例：

void SLTDestroy(SLNode** pphead)//单链表的销毁
{
	assert(*pphead);//判断传来的是否已经是空指针
	SLNode* tail = *pphead;
	SLNode* pre = NULL;
	while (tail != NULL)//找到尾节点
	{
		pre = tail->next;
		free(tail);//依次释放
		tail = pre;
	}
	*pphead = NULL;
}

函数测试与效果图:

void Test8()
{
	SLNode* plist = NULL;
	printf("原本的值\n");
	SLTPushFront(&plist, 2);//尾增
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 9);
	SLTPrint(plist);
	printf("删除之后的结果\n");
	SLTDestroy(&plist);
	SLTPrint(plist);
}

int main()
{
	//Test1();
	//Test2();
	//Test3();
	//Test4();
	//Test5();
	//Test6();
	Test8();
	return 0;
}

在这里插入图片描述

结语：今天的内容就到这里吧，谢谢各位的观看，如果有讲的不好的地方也请各位多多指出，作者每一条评论都会读的，谢谢各位。

🫵🫵🫵 祝各位接下来好运连连 💞

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/131296.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

云计算：未来世界的超级英雄

云计算：未来世界的超级英雄

在这个充满奇妙的时代，云计算被赋予了超级英雄的力量。它以其高效、可靠的数据处理能力，成为了推动智能科技发展的核心引擎。想象一下，你的智能家居设备能够通过云计算与你互动，根据你的需求智能调节温度、照明、音乐，…
阅读更多...
数据库安全：MySQL 身份认证漏洞（CVE-2012-2122）

数据库安全：MySQL 身份认证漏洞（CVE-2012-2122）

数据库安全：MySQL 身份认证漏洞（CVE-2012-2122） MySQL 身份认证漏洞是一个身份认证绕过漏洞，该漏洞的核心原理涉及到 MySQL 在处理身份认证时的一个安全缺陷，这个漏洞可以使攻击者可以绕过安全身份认证，从…
阅读更多...
YOLOv8模型ONNX格式INT8量化轻松搞定

YOLOv8模型ONNX格式INT8量化轻松搞定

ONNX格式模型量化 深度学习模型量化支持深度学习模型部署框架支持的一种轻量化模型与加速模型推理的一种常用手段，ONNXRUNTIME支持模型的简化、量化等脚本操作，简单易学，非常实用。 ONNX 模型量化常见的量化方法有三种：动态量化…
阅读更多...
DCMM咨询评估官方解答及各地补贴政策！

DCMM咨询评估官方解答及各地补贴政策！

1、DCMM是什么？ DCMM是国家标准GB/T 36073-2018《数据管理能力成熟度评估模型》（Data management Capability Maturity Model）的简称，是我国数据管理领域首个正式发布的国家标准，旨在帮助企业利用先进的数据管理理念和…
阅读更多...
jeecgboot vue3使用JAreaSelect地区选择组件时返回省市区的编码，如何获取到选择地区的文字

jeecgboot vue3使用JAreaSelect地区选择组件时返回省市区的编码，如何获取到选择地区的文字

JAreaSelect文档地址：添加链接描述 当我们的BasicForm表单组件中使用选择省市区的JAreaSelect组件时，获取到的返回值是地区的编码，如“530304”这样子，但我在小程序中展示数据的时候需要明确的地址，如“云南省昆明市五…
阅读更多...
『Linux升级路』基础开发工具——vim篇

『Linux升级路』基础开发工具——vim篇

🔥博客主页：小王又困了 📚系列专栏：Linux 🌟人之为学，不日近则日退 ❤️感谢大家点赞👍收藏⭐评论✍️ 目录 一、vim的基本概念 📒1.1命令模式 📒1.2插入模式 &…
阅读更多...
JavaFX03(首页搭建)学生管理业务逻辑老师管理登录注册

JavaFX03(首页搭建)学生管理业务逻辑老师管理登录注册

数据库脚本 --创建学生管理系统 create database db_school; --使用当前数据库 use db_school; --创建学生表 create table tb_stu(sid int primary key identity(1,1),sname varchar(50),spwd varchar(50),ssex varchar(10),sage int,shobby varchar(100),saddress varchar(1…
阅读更多...
区块链探秘：从基础到深度，全面解读区块链技术与应用

区块链探秘：从基础到深度，全面解读区块链技术与应用

1.区块链基本概念 1.发展历史 比特币诞生： 2008年，化名为中本聪的人发表了论文《Bitcoin：A Peer-to-Peer Electronic Cash System》 2009年1月3日，中本聪开发运行了比特币客户端程序并进行了首次挖矿，获得了第一批…
阅读更多...
Peter算法小课堂—八皇后问题

Peter算法小课堂—八皇后问题

独立集问题&#xff1a;安排互不冲突的个体 四个斜眼枪手 bool valid(int x,int y){for(int i1;i<min(x,y);i)if(f[x-i][y-i]) return 0;for(int i1;i<min(x,N-1-y);i)if(f[x-i][yi]) return 0;return 1; } void dfs(int x,int y,int c){if(cGUNS){ans;print();return;}i…
阅读更多...
MySQL 常见面试题总结：索引 InnoDB索引 MyISAM索引

MySQL 常见面试题总结：索引 InnoDB索引 MyISAM索引

1.关系型数据库&#xff08;MySQL&#xff09;和非关系型数据库(nosql)区别 存储方式&#xff1a;关系型以表的形式 非关系型以键值对形式 应用场景&#xff1a;关系型一致性要求较高&#xff0c;非关系型并发性要求较高 2. Mysql如何实现的索引机制&#xff1f; MySQL中索…
阅读更多...
Queue 中 poll()和 remove()的区别（详解）

Queue 中 poll()和 remove()的区别（详解）

系列文章目录 1.SpringBoot整合RabbitMQ并实现消息发送与接收 2. 解析JSON格式参数 & 修改对象的key 3. VUE整合Echarts实现简单的数据可视化 4. List&#xff1c;HashMap&#xff1c;String,String&#xff1e;&#xff1e;实现自定义字符串排序&#xff08;key排序、Val…
阅读更多...
YOLOv7改进：RefConv | 即插即用重参数化重聚焦卷积替代常规卷积，无额外推理成本下涨点明显

YOLOv7改进：RefConv | 即插即用重参数化重聚焦卷积替代常规卷积，无额外推理成本下涨点明显

1.该文章属于YOLOV5/YOLOV7/YOLOV8改进专栏，包含大量的改进方式，主要以2023年的最新文章和2022年的文章提出改进方式。 2.提供更加详细的改进方法，如将注意力机制添加到网络的不同位置，便于做实验，也可以当做论文的创新点 3.涨点效果：RefConv,实现有效涨点！ 论文地址 …
阅读更多...
【每日OJ——21. 合并两个有序链表（链表）】

【每日OJ——21. 合并两个有序链表（链表）】

每日OJ——21. 合并两个有序链表&#xff08;链表&#xff09; 1.题目&#xff1a;21. 合并两个有序链表 &#xff08;链表&#xff09;2.方法讲解&#xff1a;2.1.解法一&#xff1a;递归2.1.1.图文解析2.1.2.代码实现2.1.3.提交通过展示 2.2.解法二&#xff1a;迭代(无哨兵位…
阅读更多...
如何下载Linux源码，看这篇就够了！

如何下载Linux源码，看这篇就够了！

文章目录 前言一、linux官网二、查找发布版本三、下载方式 前言 在工作中&#xff0c;我们难免会遇到需要去找某个版本的linux源码的情况&#xff0c;今天这篇文章就手把手教大家如何找到自己想要的linux源码版本 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例…
阅读更多...
程序员千万不能去这些公司，听一下我这个学长的经验。

程序员千万不能去这些公司，听一下我这个学长的经验。

俗话说“条条大路通罗马”&#xff0c;但是对于程序员来说&#xff0c;有些路千万别走&#xff0c;走得越久越难以抽身&#xff0c;甚至说毁掉你的职业生涯。 今天来跟大家讲一下&#xff0c;作为程序员&#xff0c;有些公司千万不要进去&#xff0c;你以为稀松平常&#xff0…
阅读更多...
手机号验证码登录

手机号验证码登录

登录入口 1.app 正常登录入口 2.app 网页登录&#xff0c;比如分享直播卡片时&#xff0c;进入直播间需要先进行登录 3.pc 登录 一&#xff0c;app常见的登录方式 1.手机号验证码登录 2.用户名密码登录 3.一键登录 二&#xff0c;手机验证码登录示意图 三&#xff0c;流程 0.登…
阅读更多...
Windows7+vs2005源码安装subversion

Windows7+vs2005源码安装subversion

Windows源码安装subversion 一、运行环境 windows7 32位系统 VS2005完整安装 二、源码编译环境配置 1、python环境安装 python-2.4.msi2、perl环境安装 ActivePerl-5.8.8.822-MSWin32-x86-280952.msi3、openssl编译 C:>cd openssl-0.9.7f C:>perl Configure VC-W…
阅读更多...
大数据Doris（二十）：数据导入（Broker Load）介绍

大数据Doris（二十）：数据导入（Broker Load）介绍

文章目录 数据导入（Broker Load）介绍 一、​​​​​​​适用场景
阅读更多...
响应式理工实验外语学校学院网站模板源码

响应式理工实验外语学校学院网站模板源码

模板信息&#xff1a; 模板编号&#xff1a;11862 模板编码&#xff1a;UTF8 模板颜色&#xff1a;蓝色 模板分类&#xff1a;学校、教育、培训、科研 适合行业&#xff1a;学校类企业 模板介绍&#xff1a; 本模板自带eyoucms内核&#xff0c;无需再下载eyou系统&#xff0c…
阅读更多...
响应式青少年成长训练营培训网站模板源码

响应式青少年成长训练营培训网站模板源码

模板信息&#xff1a; 模板编号&#xff1a;28503 模板编码&#xff1a;UTF8 模板颜色&#xff1a;黑白 模板分类&#xff1a;学校、教育、培训、科研 适合行业&#xff1a;培训机构类企业 模板介绍&#xff1a; 本模板自带eyoucms内核&#xff0c;无需再下载eyou系统&#x…
阅读更多...
最新文章

Copyright @ 2022~2023