【数据结构】单链表(二)

目录

1.查找数据

2.指定位置插入和删除节点

2.1 指定位置之前插入节点

2.2 指定位置之后插入节点

2.3 删除指定位置节点

2.4 删除指定位置之后的节点

3.销毁链表


我们接着上一篇【数据结构】单链表(一)-CSDN博客 来继续实现单链表

1.查找数据

SList.h中进行函数的声明

SLNode* SLfind(SLNode* pps, Type x);//查找

返回值是一个地址,如果找到,就返回这个数的地址,如果没找到,就返回NULL,参数就是链表首节点地址和要查找的数

SList.c中进行函数的实现

首先我们可以再定义一个指针存放首节点地址,这样的话在后面的遍历链表时就不会改变pps的指向了

SLNode* SLfind(SLNode* pps, Type x)//查找
{
	SLNode* pcur = pps;//新定义一个指针,指向首节点
}

然后就是循环遍历

SLNode* SLfind(SLNode* pps, Type x)//查找
{
	SLNode* pcur = pps;//新定义一个指针,指向首节点
	while (pcur)//pcur不能为空
	{
		if (pcur->data == x) //找到
			return pcur;//直接返回地址
		pcur = pcur->next;//没找到往后找
	}
}

当跳出while循环时,证明没找到,此时pcur为空,我们直接返回NULL

SLNode* SLfind(SLNode* pps, Type x)//查找
{
	SLNode* pcur = pps;//新定义一个指针,指向首节点
	while (pcur)//pcur不能为空
	{
		if (pcur->data == x) //找到
			return pcur;//直接返回地址
		pcur = pcur->next;//没找到往后找
	}
	return NULL;//没找到
}

test.c中测试一下

void SListtest3()
{
	SLNode* plist = NULL;//空链表
	SLPushBack(&plist, 1);//尾插
	SLPushBack(&plist, 2);
	SLPushHead(&plist, 6);//头插
	SLPushHead(&plist, 7);
	SLPrint(plist);//打印
	SLNode* find = SLfind(plist, 2);
	if (find == NULL)
		printf("没找到\n");
	else
		printf("找到了\n");
}
int main()
{
	//SListtest1();
	//SListtest2();
	SListtest3();
	return 0;
}

 自己测试的时候可以多测几次

2.指定位置插入和删除节点

上一篇我们说了头部尾部的插入和删除数据,现在我们来实现一下指定位置的插入和删除数据

2.1 指定位置之前插入节点

SList.h中进行函数的声明

void SLInsert(SLNode** pps, SLNode* pos, Type x);//指定之前插

参数有三个:链表首节点的地址,指定的位置,要插入的数据

SList.c中进行函数的实现

 现在我们要在节点3前面插入一个节点,就要让节点2里面的next指向新节点,新节点里面的next指向节点3

我们先找pos的前一个结点 ,用循环遍历

void SLInsert(SLNode** pps, SLNode* pos, Type x)//指定之前插
{
	assert(pps && *pps);
	assert(pos);
	SLNode* prev = *pps;//再定义一个指针变量初始指向首节点
	while (prev->next != pos)
	{
		prev = prev->next;
	}
}

跳出循环后此时prev指向pos前一个节点,然后让这些节点“手牵手”

void SLInsert(SLNode** pps, SLNode* pos, Type x)//指定之前插
{
	assert(pps && *pps);
	assert(pos);
	SLNode* newnode = SLBuyNode(x);//插入的数据
	SLNode* prev = *pps;//再定义一个指针变量初始指向首节点
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	newnode->next = pos;
    prev->next = newnode;
}

代码写到这里我们在分析一下pos为1时可不可行

 这种情况下prev会一直往后走,直到走到最后一个节点,上面的代码在次情况下行不通

我们再分析一下pos为最后一个节点时可不可行

依旧是让节点3里面的next指向新节点,新节点里面的next指向节点4

经分析,上面的代码在这种情况下可行,所以不可行的就是pos为1的情况,我们单独把这种情况列出来,其实pos为1时也就是头插的情况

void SLInsert(SLNode** pps, SLNode* pos, Type x)//指定之前插
{
	assert(pps && *pps);
	assert(pos);
	SLNode* newnode = SLBuyNode(x);//插入的数据
	if (pos == *pps)
	{
		SLPushHead(pps, x);//直接调用头插代码
	}
	else//其他位置
	{
		SLNode* prev = *pps;//再定义一个指针变量初始指向首节点
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
        prev->next = newnode;
	}
}

这就是完整的代码

test.c中测试一下

void SListtest3()
{
	SLNode* plist = NULL;//空链表
	SLPushBack(&plist, 1);//尾插
	SLPushBack(&plist, 2);
	SLPushHead(&plist, 6);//头插
	SLPushHead(&plist, 7);
	SLPrint(plist);//打印
	SLNode* find = SLfind(plist, 2);//找2
	SLInsert(&plist, find, 11);//直接插在2前面
	SLPrint(plist);//打印
}
int main()
{
	SListtest3();
	return 0;
}

看结果

其他情况有疑惑的话一定要自己测试运行一下

2.2 指定位置之后插入节点

SList.h中进行函数的声明

void SLAfter(SLNode* pos, Type x);//指定之后插

这里只有两个参数,一个是指定位置,一个是要插入的值,这里我们不需要知道头节点,因为可以通过pos找到下一个节点,在指定位置之前插入数据的函数需要头节点是因为我们不能通过pos找到pos的前一个节点

SList.c中进行函数的实现

void SLAfter(SLNode* pos, Type x)//指定之后插
{
	assert(pos);
	SLNode* newnode = SLBuyNode(x);//插入的数据
	newnode->next = pos->next;
	pos->next = newnode;
}

注意:  newnode->next = pos->next;   pos->next = newnode;这两句代码的顺序不可以交换,交换后是错的

test.c中测试一下

void SListtest3()
{
	SLNode* plist = NULL;//空链表
	SLPushBack(&plist, 1);//尾插
	SLPushBack(&plist, 2);
	SLPushHead(&plist, 6);//头插
	SLPushHead(&plist, 7);
	SLPrint(plist);//打印
	SLNode* find = SLfind(plist, 2);//找2
	SLInsert(&plist, find, 11);//直接插在2前面
	SLPrint(plist);//打印
	SLAfter(find, 5);//插在2后面
	SLPrint(plist);//打印
}
int main()
{
	SListtest3();
	return 0;
}

代码没有问题

2.3 删除指定位置节点

SList.h中进行函数的声明

void SLErase(SLNode** pps, SLNode* pos);//删除pos节点

参数是二级指针,接收首节点地址,还有一个参数是要删除的节点

SList.c中进行函数的实现

我们要让pos的前一个节点指向pos的后一个节点,然后把pos这个节点销毁

既然要找pos的前一个节点,我们依旧是定义一个指针prev,初始为*pps,往后一个一个找,直到找到pos前一个节点 

void SLErase(SLNode** pps, SLNode* pos)//删除pos节点
{
	assert(pps && *pps);
	assert(pos);
	SLNode* prev = *pps;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	prev->next = pos->next;
	free(pos);
	pos = NULL;
}

如果此时链表只有一个节点,上面的代码可行吗?来分析一下

发现代码走不通,其实这种情况就是头删的情况,我们直接调用头删的代码就可以了

void SLErase(SLNode** pps, SLNode* pos)//删除pos节点
{
	assert(pps && *pps);
	assert(pos);
	if (pos == *pps)//一个节点
	{
		SLPopHead(pps);
	}
	else//多个节点
	{
		SLNode* prev = *pps;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

test.c中测试一下

void SListtest3()
{
	SLNode* plist = NULL;//空链表
	SLPushBack(&plist, 1);//尾插
	SLPushBack(&plist, 2);
	SLPushHead(&plist, 6);//头插
	SLPushHead(&plist, 7);
	SLPrint(plist);//打印
	SLNode* find = SLfind(plist, 7);//找7
	SLErase(&plist, find);//删除指定位置节点
	SLPrint(plist);//打印
}
int main()
{
	SListtest3();
	return 0;
}

删除成功

2.4 删除指定位置之后的节点

SList.h中进行函数的声明

void SLPushAfter(SLNode* pos);//删除pos之后的节点

pos的后一个节点我们可以直接通过pos找到,就不需要头节点地址,所以一个参数就好了

 在SList.c中进行函数的实现

 

还是先让pos这个节点找到它的下下个节点,然后再销毁pos后面的节点

 这里呢我们需要一个临时变量存放pos->next的地址,然后再连接节点

 我们先写一下代码,让pos和pos下下个节点相连

void SLPushAfter(SLNode* pos)//删除pos之后的节点
{
	assert(pos);
	assert(pos->next);
	SLNode* temp = pos->next;
	pos->next = temp->next;
}

 然后销毁pos下一个节点并置空

void SLPushAfter(SLNode* pos)//删除pos之后的节点
{
	assert(pos);
	assert(pos->next);
	SLNode* temp = pos->next;//临时变量
	pos->next = temp->next;//连接
	free(temp);//销毁
	temp = NULL;//置空
}

test.c中测试一下

void SListtest3()
{
	SLNode* plist = NULL;//空链表
	SLPushBack(&plist, 1);//尾插
	SLPushBack(&plist, 2);
	SLPushHead(&plist, 6);//头插
	SLPushHead(&plist, 7);
	SLPrint(plist);//打印
	SLNode* find = SLfind(plist, 7);//找7
	SLPushAfter(find);//删除指定位置后一个节点
    SLPrint(plist);//打印
}
int main()
{
	SListtest3();
	return 0;
}

3.销毁链表

跟顺序表一样,链表使用完之后也要销毁,链表由一个一个节点组成,所以也要一个一个销毁

SList.h中进行函数的声明

void SLDestroy(SLNode** pps);//销毁

参数就是首节点地址

SList.c中进行函数的实现

我们在销毁当前节点之前要把下一个节点的信息存起来

 销毁空间

pcur后移到提前保存的next处

 

然后next后移,把当前的pcur销毁

就这样一直往后,直到pcur为空

代码来实现一下


void SLDestroy(SLNode** pps)//销毁
{
	assert(*pps && pps);
	SLNode* pcur = *pps;
	while (pcur)
	{
		SLNode* next = pcur->next;//存下节点信息
		free(pcur);//释放
		pcur = next;//往后走
	}
	*pps = NULL;//不要忘了头节点此时没有置空,要置空
}

test.c中测试一下

void SListtest3()
{
	SLNode* plist = NULL;//空链表
	SLPushBack(&plist, 1);//尾插
	SLPushBack(&plist, 2);
	SLPushHead(&plist, 6);//头插
	SLPushHead(&plist, 7);
	SLPrint(plist);//打印
	SLDestroy(&plist);//销毁
	SLPrint(plist);//打印
}
int main()
{
	SListtest3();
	return 0;
}

可以自己通过调试看结果,能看到更详细,打印出来看也可以

单链表实现就分享到这里,拜拜~ 

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

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

相关文章

c# wpf datagrid 简单试验

1.概要 datagrid 一个列表类的控件 2.代码 <Window x:Class"WpfApp2.Window3"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d"http://schemas.mic…

关于 STM32WL LSE 添加反馈电阻后无法起振问题

1. 问题描述 客户调试 STM32WLE5JB 样机的时候遇到这样一个问题&#xff1a;在调试 LPUART&#xff0c;不打开外部时钟的时候&#xff0c;能够正常打印&#xff0c;若开启外部的 HSE 和 LSE 后就没有打印。 2. 问题确认 发现上述问题时&#xff0c;客户使用 STM32CubeMX 生成…

数字图像处理项目——模糊图像边缘检测算法设计及实现(论文/代码)

完整的论文代码见文章末尾 以下为部分内容 摘要 本研究旨在针对大脑核磁图像中的黑色腔体进行有效分割&#xff0c;以提供可靠的腔体定位和分析。为此&#xff0c;采用了三种常用的图像分割方法&#xff1a;8邻域区域生长法、Canny算子边缘检测和8邻域边界跟踪法。 首先&…

ES13:类的新增特性、最外层的await、at...

1-类的新增特性 类私有属性和方法&#xff1a;# class Person{// 不需要传参、一开始就需要初始化的&#xff0c;就可以在类的最外面直接声明这个成员state{a:1,b:2}constructor(name,age){this.namename;this.ageage;}}在属性和方法前加#表示私有 #obj{} #prest(){}静态成员…

数据结构--链式栈

一.链式栈的栈顶在哪里? 二.链栈的结构: typedef struct LSNode{ int data; struct LSNode* next; }LSNode ,*PLStack; //链栈的节点.由于栈顶在第一个数据节点,所以不需要top指针 三.链式栈的实现: //初始化LSNode* p (LSNode*)malloc(sizeof(LSNode));assert(p ! NULL)…

C语言调用Python

目录 1.直接调用python语句 头文件引用 2.调用无参有参函数 1、调用无参函数 1.建立nopara.py文件 2.使用c语言根据上面流程进行调用 2、调用有参函数 1.建立nopara.py文件 2.使用c语言根据上面流程进行调用 C语言调用python需要我们已经安装好了libpython3的 dev依赖…

【Shell语言学堂】数组练习题

数组练习 1、使用数组和循环实现冒泡排序2、将冒泡排序的代码重构为2个函数&#xff0c;2个关系是a函数调用b函数自定义数组参数&#xff1a; 3、声明一个存储的全整数数组&#xff0c;对其中的每一个值进行10处理4、对硬盘使用空间占比的排序5、对当前目录的文件大小进行排序 …

小型企业网络安全指南

许多小型企业刚刚起步&#xff0c;没有大公司所拥有的相同资源来保护其数据。他们不仅可能没有资金来支持多样化的安全计划&#xff0c;而且也可能没有人力或时间。 网络犯罪分子知道小型企业缺乏这些资源&#xff0c;并利用这些资源来谋取利益。遭受网络攻击后&#xff0c;小…

7、configMap

1、configMap是什么 类似与pod的配置中心&#xff0c;不会因为pod的创建销毁&#xff0c;相关配置发生改变 pod定义硬编码意味着需要有效区分⽣产环境与开发过程中的pod 定义。为了能在多个环境下复⽤pod的定义&#xff0c;需要将配置从pod定义描 述中解耦出来。 2、向容器中…

2024年MathorCup数模竞赛C题超详细解题思路

妈妈杯本次比赛报名队伍号高达12500&#xff0c;这也就意味着大概一万只队伍参加报名&#xff0c;仅仅在报名人数这一项&#xff0c;妈妈杯已经成为美赛国赛之后的第三大竞赛。C题作为本次竞赛最简单也最容易获奖的题目&#xff0c;本文将给大家带来手把手超详细解题思路。 注…

【Git教程】(十二)工作流之项目设置 — 何时使用工作流,工作流的结构,项目设置概述、执行过程及其实现 ~

Git教程 工作流之项目设置 1️⃣ 何时使用工作流2️⃣ 工作流的结构3️⃣ 概述4️⃣ 使用要求5️⃣ 执行过程及其实现5.1 基于项目目录创建一个新的版本库5.2 以文件访问的方式共享版本库5.3 用 Git daemon 来共享版本库5.4 用 HTTP 协议来共享版本库5.5 用 SSH 协议来共享版…

KubeSphere 社区双周报|2024.03.29-04.11

KubeSphere 社区双周报主要整理展示新增的贡献者名单和证书、新增的讲师证书以及两周内提交过 commit 的贡献者&#xff0c;并对近期重要的 PR 进行解析&#xff0c;同时还包含了线上/线下活动和布道推广等一系列社区动态。 本次双周报涵盖时间为&#xff1a;2024.03.29-04.11…

【服务器部署篇】Linux下Jenkins安装和配置

作者介绍&#xff1a;本人笔名姑苏老陈&#xff0c;从事JAVA开发工作十多年了&#xff0c;带过刚毕业的实习生&#xff0c;也带过技术团队。最近有个朋友的表弟&#xff0c;马上要大学毕业了&#xff0c;想从事JAVA开发工作&#xff0c;但不知道从何处入手。于是&#xff0c;产…

✌2024/4/1—力扣—按摩师✌

代码实现&#xff1a; 思路&#xff1a;打家劫舍题 int massage(int *nums, int numsSize) {if (nums NULL || numsSize 0) {return 0;}if (numsSize 1) {return nums[0];}int dp[numsSize];memset(dp, 0, sizeof(dp));dp[0] nums[0];dp[1] (nums[0] < nums[1] ? nums…

【网络初识】网络相关概念详解

一.局域网VS广域网 局域网 局域网:Local Area Network~简称LAN.指在某一特定区域内由多台计算机组成的互联网组。局域网内的主机之间能方便的进行网络通信&#xff0c;又称为内网.局域网和局域网之间在没有连接的情况下&#xff0c;是无法通信的。局域网的组建方式: 基于网线…

Docker 集成 redis,并在nacos进行配置时需要注意点

安装redis镜像 docker pull redis:6.0.6redis配置文件 创建相关配置文件 mkdir /apps/redis cd /apps/redis touch redis.conf vim redis.confredis.conf内容&#xff1a; #开启保护 protected-mode yes #开启远程连接 bind 0.0.0.0 #自定义密码 port 6379 timeout 0 # 900s内…

网络协议学习——以太网协议

目录 ​编辑 一&#xff0c;以太网简介 二&#xff0c;以太网通信的过程 为什么不用IP地址&#xff1f; 过程 MAC帧 MAC帧的字段介绍 ARP协议 传输过程的一些问题 RARP协议 提高效率 三&#xff0c;其他问题 ARP诈骗问题 URL解析过程 一&#xff0c;以太网简介 …

【优选算法专栏】专题十:哈希表(一)

本专栏内容为&#xff1a;算法学习专栏&#xff0c;分为优选算法专栏&#xff0c;贪心算法专栏&#xff0c;动态规划专栏以及递归&#xff0c;搜索与回溯算法专栏四部分。 通过本专栏的深入学习&#xff0c;你可以了解并掌握算法。 &#x1f493;博主csdn个人主页&#xff1a;小…

【线段树 有序映射】715. Range 模块

算法可以发掘本质&#xff0c;如&#xff1a; 一&#xff0c;若干师傅和徒弟互有好感&#xff0c;有好感的师徒可以结对学习。师傅和徒弟都只能参加一个对子。如何让对子最多。 二&#xff0c;有无限多1X2和2X1的骨牌&#xff0c;某个棋盘若干格子坏了&#xff0c;如何在没有坏…

谷歌pixel6/7pro等手机WiFi不能上网,显示网络连接受限

近期在项目中遇到一个机型出现的问题,先对项目代码进行排查,发现别的设备都能正常运行,就开始来排查机型的问题,特意写出来方便后续查看,也方便其它开发者来自查。 设备机型:Pixel 6a 设备安卓版本:13 该方法无需root,只需要电脑设备安装adb(即Android Debug Bridge…