数据结构——lesson3单链表介绍及实现

目录

 

1.什么是链表？

2.链表的分类

（1）无头单向非循环链表：

（2）带头双向循环链表：

3.单链表的实现

 （1）单链表的定义

（2）动态创建节点

（3）单链表打印

（4）单链表尾插

（5）单链表头插

（6）单链表尾删

（7）单链表头删

（8）单链表查找

（9）单链表在pos位置之后插入

(10)单链表在pos位置之前插入

（11）单链表删除pos位置的节点

（12）单链表销毁

 4.运行结果

5.结语 


4da1dfe51db24bf1b72fbdc29e0e7e93.jpeg

1.什么是链表？

链表是一种 物理存储结构上非连续、非顺序的存储结构，数据元素的 逻辑顺序是通过链表中的 指针链 接次序实现的 。
 
逻辑图如下：
a83f5df4179a4feca08f0f62d06a39f7.png

可以看出链表有两个变量，一个存放数据，另一个存放指向下一节点的指针；

此外链表还具有以下特征：

（1）链表在逻辑上连续，但在物理上不一定连续；

（2）链表的节点在现实中一般都是在堆上开辟出来的，所以使用结束后需要释放空间；

（3）从堆上申请的空间是按照一定策略分配的，所以物理空间可能连续也可能不连续。

 

2.链表的分类

链表按单向双向、无头带头、循环非循环可分为多种，这里我们介绍最常用的两种——无头单向非循环链表、带头双向循环链表。本篇文章将详细介绍无头单向非循环链表（简称单链表）的增删查改等的实现。

（1）无头单向非循环链表：

fafc7d2473954f09b3d06e85bfe83539.jpeg

 

结构简单，一般不会单独用来存数据。实际中更多是作为 其他数据结构的子结 构，如哈希桶、图的邻接表等等。另外这种结构在 笔试面试中出现很多。
 

（2）带头双向循环链表：

3a1b4f8edc084008881c1a27a3973991.jpeg 
结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。
 
 

3.单链表的实现

 （1）单链表的定义

typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;//存放数据
	struct SListNode* next;//存放下一个节点的指针
}SListNode;

结构体定义两个变量，一个是SLDataType类型的数据，另一个时结构体的指针用来存放下一节点指针；

（2）动态创建节点


//申请新的节点，返回指向节点的指针
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* buynode = (SListNode*)malloc(sizeof(SListNode));
	buynode->data = x;
	buynode->next = NULL;
	return buynode;
}

（3）单链表打印


// 单链表打印
void SListPrint(SListNode* plist)
{
	//assert(plist);//没有节点，指针为空，断言，为空也可打印空指针所以不需要断言
	SListNode* psl = plist;//用一个临时变量接收，如果不喜欢也可以不用
	while (psl)//利用while循环遍历单链表
	{
		printf("%d->", psl->data);//打印单链表指向的数据
		psl = psl->next;//继续循环
	}
	printf("%d->NULL\n");//最后一个不要漏了
}

（4）单链表尾插

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);//断言二级指针
	SListNode* buy = BuySListNode(x);
	assert(buy);//判断节点是否开辟成功
	SListNode* psl= *pplist;//创建一个新的变量
	if (psl == NULL)//如果是一个节点都没有的情况
	{
		*pplist = buy;//需要将头指针改变（原本头指针是NULL）所以需要节点指针的指针
		return;
	}
	while (psl->next)//如果已经有节点的情况
	{
		psl = psl->next;//通过next遍历链表找到最后的节点
	}
	psl->next = buy;//将最后节点的next改成buy节点的指针，所以需要节点的指针即可，不需要二级指针

}

pplist是指向链表第一个节点指针的指针，是二级指针，所以一定不为空，要用assert断言；

（5）单链表头插

// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* buy = BuySListNode(x);
	assert(buy);//判断节点是否开辟成功
	SListNode* psl = *pplist;
	if (*pplist == NULL)//如果一个节点都没有的情况
	{
		*pplist = buy;//需要将头指针改变（原本头指针是NULL）所以需要节点指针的指针
		return;
	}
	//有节点的情况
	buy->next = psl;//需要通过next连接新节点
	*pplist = buy;//通过节点的指针的指针改变节点的指针
}

 要注意有两种情况一直是没有一个节点的情况即*pplist = NULL，另一种是有节点的情况；

传二级指针的作用就是为了改变指针plist，所以需要指针的指针pplist；

（6）单链表尾删

// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
	assert(pplist);
	assert(*pplist);//删除节点要判断有没有节点
	SListNode* psl = *pplist;
	if (psl->next == NULL)//只有一个节点时
	{
		free(psl);//释放最后一个节点的空间
		*pplist = NULL;//尾指针置空
		return;
	}
	while (psl->next->next)//多个节点时找到倒数第二个节点
	{
		psl = psl->next;
	}
	free(psl->next);
	psl->next = NULL;//尾指针置空
}

单链表尾删同样要注意两种情况；使用free释放指针指向的空间；

（7）单链表头删

// 单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	assert(*pplist);//删除节点要判断有没有节点
	SListNode* psl = *pplist;
	if (psl->next == NULL)//只有一个节点时
	{
		free(psl);
		*pplist = NULL;
		return;
	}
	//多个节点时
	*pplist = psl->next;//将第二个节点的指针给头指针
	free(psl);//释放第一个节点的空间
}

（8）单链表查找

// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	assert(plist);//查找节点要判断有没有节点
	SListNode* psl = plist;
	while (psl)
	{
		if (psl->data == x)
		{
			return psl;//找到了返回psl
		}
		psl = psl->next;
	}
	return NULL;//没找到返回空指针
}

（9）单链表在pos位置之后插入

// 单链表在pos位置之后插入x

void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* buy = BuySListNode(x);
	assert(buy);//判断节点是否开辟成功
	//if (pos->next == NULL)
	//{
	//	pos->next = buy;//将最后节点的next改成buy节点的指针	
	//	return;
	//}
	buy->next = pos->next;//只有一个节点和多个节点一样
	pos->next = buy;
}

思考分析这两行代码可不可以调换一下顺序呢？

buy->next = pos->next;//只有一个节点和多个节点一样
pos->next = buy;

答案是不能，我们看到如果交换顺序，先将buy赋值给pos->next，那么pos->next的值将会被改变，而我们需要在buy->next中保存原来的pos->next，所以不能调换顺序；

如果你想要换也可以通过创建一个临时变量来存储pos->next的方式实现.例如：


SListNode* cur = pos->next;
pos->next = buy;
buy->next = cur;

(10)单链表在pos位置之前插入

// 在pos的前面插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{
	//assert(pphead);
	assert(pos);
	SListNode* buy = BuySListNode(x);
	assert(buy);//判断节点是否开辟成功
	SListNode* psl = *pphead;
	if (psl->next == NULL)//只有一个节点
	{
		buy->next = pos;
		*pphead = buy;
		return;

	}
	while (psl->next != pos)//多个节点
	{
		psl = psl->next;
	}
	buy->next = pos;
	psl->next = buy;
}

（11）单链表删除pos位置的节点

// 删除pos位置
void SLTErase(SListNode** pphead, SListNode* pos)
{
	assert(pos);
	SListNode* psl = *pphead;
	if (psl->next == NULL)//只有一个节点，类似于头删
	{
		free(pos);
		pos = NULL;
		*pphead = NULL;
		return;
	}
	while (psl->next != pos)//多个节点
	{
		psl = psl->next;
	}
	//此时psl->next = pos;
	psl->next = pos->next;将pos位置指向的下一个节点指针赋给psl->next
	free(pos);
	pos = NULL;

}

删除pos位置也要注意有两种情况；

（12）单链表销毁

void SLTDestroy(SListNode** pphead)
{
	assert(pphead);
	SListNode* psl = *pphead;
	SListNode* psll = *pphead;

	while (psl != NULL)
	{
		free(psll);
		psl = psl->next;
		psll = psl;
	}
	*pphead = NULL;
}

 4.运行结果

ee434ab5c2f04694b1021b41252e8c93.png

5.结语 

        以上就是今天学习的内容了，单链表的实现关键在于理解它的逻辑结构，包括两个变量，一个是指向数据，另一个则指向下一节点的指针，此外，单链表实现还涉及了二级指针的内容以及动态内存函数的内容，涉及的代码知识更为广泛，但是只要抓住了关键点就会发现每个函数的中心思想都是不变的，好了以上就是今天学习的内容啦，有什么问题欢迎大家在评论区指出或者私信我哦~

 

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

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

相关文章

【Gitea】配置 Push To Create

【Gitea】配置 Push To Create

引 在 Git 代码管理工具使用过程中，经常需要将一个文件夹作为仓库上传到一个未创建的代码仓库。如果 Git 服务端使用的是 Gitea，通常会推送失败。 PS D:\tmp\git-test> git remote add origin http://192.1.1.1:3000/root/git-test.git PS D:\tmp\g…
阅读更多...
VMware虚拟机安装CentOS7

VMware虚拟机安装CentOS7

对于系统开发来说，开发者时常会需要涉及到不同的操作系统，比如Windows系统、Mac系统、Linux系统、Chrome OS系统、UNIX操作系统等。由于在同一台计算机上安装多个系统会占据我们大量的存储空间，所以虚拟机概念应运而生。本篇将介绍如何下载安…
阅读更多...
SaaS系统介绍

SaaS系统介绍

本文系个人学习笔记，内容来源于资料整合及个人理解。 1. 概念介绍 SaaS系统英文全称为Software as a Service（软件即服务），通俗来讲就是提供固定功能的在线软件。从宏观上看，SaaS有三大特点： 1. 用户无需…
阅读更多...
如何在Linux系统中配置并优化硬盘的RAID

如何在Linux系统中配置并优化硬盘的RAID

在Linux系统中配置和优化硬盘的RAID技术可以帮助提高数据存储性能和安全性。RAID（Redundant Array of Independent Disks）技术通过将多个硬盘组合起来，以增加性能、容量或冗余度，提高数据的可靠性和可用性。本文将介绍如何在Linux…
阅读更多...
代码随想录算法训练营第15天—二叉树04 | ● *110.平衡二叉树 ● *257. 二叉树的所有路径 ● 404.左叶子之和

代码随想录算法训练营第15天—二叉树04 | ● *110.平衡二叉树 ● *257. 二叉树的所有路径 ● 404.左叶子之和

*110.平衡二叉树 题目链接/文章讲解/视频讲解：https://programmercarl.com/0110.%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91.html 考点 后序遍历二叉树高度计算 我的思路 错误地将平衡二叉树的定义等价为判断整体二叉树的最大深度和最小深度之差是否大于1 视…
阅读更多...
黑马程序员-瑞吉外卖-day8

黑马程序员-瑞吉外卖-day8

目录 菜品新增 菜品代码准备： 1.entity 2.mapper 3.service 4.sevice目录下的impl目录 5.controller 菜品口味代码准备： 1.entity 2.mapper 3.service 4.sevice目录下的impl目录 菜品新增 分析： 后台系统中可以管理菜品信息&…
阅读更多...
胆小勿入！AI创作恐怖电影宣传片《生化危机：重生》

胆小勿入！AI创作恐怖电影宣传片《生化危机：重生》

胆小勿入！AI创作恐怖电影宣传片《生化危机：重生》 "The city is falling, and the dead walk among us." "In the shadow of the apocalypse, the fight for survival begins." "The streets are silent, but the nightmare …
阅读更多...
若依项目改造

若依项目改造

ctrlalt l 格式化项目 alt f6 修改包和import包名 替换com.ruoyi 为 com.cj 替换若依版本为自己的版本 将ruoyi改成自己项目的英文名 修改中文名字 修改文件包名 修改有ruoyi的类名 ： 验证码生成器包名修改：
阅读更多...
蝶阀、球阀、阀门百科

蝶阀、球阀、阀门百科

一、D71X是蝶阀的型号其中D 就代表了蝶阀,7 代表是对夹式链接,1代表这个蝶阀是中线结构,x就是密封面材质为橡胶。结合起来D71X表示的就是手柄对夹中线蝶阀。 二、J41H-100C型号字母含义介绍 J41H-100C型号是德特森阀门常用的高压截止阀型号字母代表的意思是: J——代表阀门类…
阅读更多...
英文论文（sci）解读复现【NO.21】一种基于空间坐标的轻量级目标检测器无人机航空图像的自注意

英文论文（sci）解读复现【NO.21】一种基于空间坐标的轻量级目标检测器无人机航空图像的自注意

此前出了目标检测算法改进专栏，但是对于应用于什么场景，需要什么改进方法对应与自己的应用场景有效果，并且多少改进点能发什么水平的文章，为解决大家的困惑，此系列文章旨在给大家解读发表高水平学术期刊中的 SCI论文&a…
阅读更多...
内存基础知识

内存基础知识

内存作用：用来存放数据 int x10； xx1； 这会生成一个可执行文件（装入模块）然后存入内存地址中 绝对装入：-如果知道程序放到内存中哪个位置，编译程序将产生绝对地址的目标代码 可重定位装入&am…
阅读更多...
【MySQL】变量、流程控制

【MySQL】变量、流程控制

一、变量 在MySQL的存储过程与函数中，可以使用变量来存储查询或计算的中间结果数据，或者输出最终的结果数据。它可以分为用户自定义变量与系统变量 1、系统变量 1）系统变量分为全局变量（需要使用关键字global）和会话…
阅读更多...
Shell脚本条件语句

Shell脚本条件语句

1.条件测试 文件测试与整数测试 test命令 测试表达式是否成立，若成立返回0，不成立返回其他数值 格式1：test 条件表达式 格式2：[ 条件表达式 ] 测试 是否成功使用 $? 操作符： -d：测试是否为目…
阅读更多...
JavaWeb学习（1）数据库相关概念，mysql数据库管理系统，SQL语句

JavaWeb学习（1）数据库相关概念，mysql数据库管理系统，SQL语句

数据库相关概念 数据库： 存储数据的仓库，数据是有组织的进行存储 英文：DataBase 简称DB 数据库管理系统： 管理数据库的大型软件 英文：DataBase Management System,简称DBMS SQL 英文：Stry…
阅读更多...
Java_方法(重载方法签名等详解)

Java_方法(重载方法签名等详解)

在之前我们学习C语言时，当我们想要重复使用某段代码的功能时，我们会将这段代码定义为一个函数，而在java中我们把这段重复使用的代码叫做方法。 方法的定义 类体的内容分为变量的声明和方法的定义，方法的定义包括两部分&#xff1…
阅读更多...
鱼皮项目_可下载

鱼皮项目_可下载

​ 一、网址 Sign in GitLab 二、登录 以个人邮箱登录 c7 三、下载 四、打开下载文件，后缀zip ​
阅读更多...
MyBatis核心配置文件详解

MyBatis核心配置文件详解

MyBatis核心配置文件详解 一、Environments标签1.Environment标签详解（1）如何创建对应环境的 SqlSessionFactory对象 2.transactionManager标签详解3.dataSource标签详解（1）UNPOOLED（2）POOLED（3…
阅读更多...
MCU电源控制(PWR)与低功耗

MCU电源控制(PWR)与低功耗

目录 一、STM32 的内核和外设电源系统管理： 二、MCU电源监控： 三、三种低功耗模式： 1、睡眠模式： 2、停止模式： 3、待机模式： 一、STM32 的内核和外设电源系统管理： ① 电池备份区域&#…
阅读更多...
NumPy模块完结篇：深入探讨和高效利用【第85篇—NumPy模块】

NumPy模块完结篇：深入探讨和高效利用【第85篇—NumPy模块】

NumPy模块完结篇：深入探讨和高效利用 NumPy是Python中用于科学计算的核心库之一，提供了高性能的多维数组对象（numpy.ndarray）以及许多用于操作这些数组的函数。在前面的几篇博客中，我们介绍了NumPy的基础知识、数组操…
阅读更多...
【Linux】进程地址空间的理解

【Linux】进程地址空间的理解

进程地址空间的理解 一，什么是程序地址空间二，页表和虚拟地址空间三，为什么要有进程地址空间 一，什么是程序地址空间 在我们写程序时，都会有这样下面的内存结构，来存放变量和代码等数据。 一个进程要执行…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站