【数据结构初级（2）】单链表的基本操作和实现

文章目录

  • Ⅰ 概念及结构
    • 1. 单链表的概念
    • 2. 单链表的结构
  • Ⅱ 基本操作实现
    • 1. 定义单链表结点
    • 2. 创建新结点
    • 3. 单链表打印
    • 4. 单链表尾插
    • 5. 单链表头插
    • 6. 单链表尾删
    • 7. 单链表头删
    • 8. 单链表查找
    • 9. 在指定 pos 位置前插入结点
    • 10. 删除指定 pos 位置的结点
    • 11. 单链表销毁

本章实现的是不带头结点的单链表。

Ⅰ 概念及结构

1. 单链表的概念

  • 链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
  • 单链表的每个结点仅仅要存储该结点本身应该存储的数据，还要存储下一个与自己同类型结点的地址。

在这里插入图片描述

2. 单链表的结构

1. 物理结构

每个单链表结点都有一个指针域，用来存储下一个结点的地址。

在这里插入图片描述

2. 逻辑结构

为了方便理解和学习，使用箭头来表示每个结点的指针域所存储的是哪个结点的地址。

在这里插入图片描述

Ⅱ 基本操作实现

1. 定义单链表结点

  • 每个结点都应该包含数据域和指针域两部分内容。
  • 数据域的数据类型应该使用 typedef 来定义，防止以后更改数据域的数据类型。
typedef int SLTDataType;	//每个单链表结点数据域的数据类型

typedef struct SListNode	//定义一个单链表结点
{
	SLTDataType data;		//单链表的数据域
	struct SListNode* next;	//单链表的指针域，用于存放下一个同类型结点的地址
}SLNode;					//单恋表的结点类型

2. 创建新结点

  • 开辟一个结点空间，将传过来的数据 x 放到结点的数据域，然后将该结点的指针域置 NULL。
SLNode* BuySListNode(SLTDataType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));	//开辟一个新结点空间

	if (NULL == newnode)	//如果开辟该结点失败
	{
		perror("malloc");
		exit(-1);
	}

	newnode->data = x;		//参数给新结点的数据域
	newnode->next = NULL;	//将新结点的指针域置空

	return newnode;			//返回开辟的新结点的地址
}

3. 单链表打印

1. 遍历链表

因为不能动指向首结点的指针，防止找不到首结点，所以此类操作都是利用额外的指针来实现的。

  • 使用一个指针 cur (current) 指向当前结点，如果 cur 不为空，则说明链表还没走到头。打印 cur 所指向的结点的数据域，然后让 cur 指针指向下一个结点。
  • 在打印的时候会有两种情况。
  1. 单链表为空：此时 cur 直接就指向 NULL，什么也不会打印。

在这里插入图片描述

  1. 单链表非空：打印 cur 指向结点的数据域的类容，然后将 cur 指向指向下一个结点，直到 cur 走到链表末尾后为止。

在这里插入图片描述

2. 代码实现

 //单链表打印
void SListPrint(SLNode* plist)
{
	SLNode* cur = plist;			//指向单链表的首结点

	while (cur != NULL)				//单链表还没走到尾
	{
		printf("%d->", cur->data);	//打印当前结点数据域的值
		cur = cur->next;			//继续指向下一个结点
	}
	printf("NULL\n");
}

3. 函数调用

SListPrint(plist);

4. 单链表尾插

1. 插入链表

将数据依次插入到单链表的尾部。
在进行单链表尾插时有两种情况：

  1. 单链表为空：直接创建一个新结点然后插入到单链表即可。

在这里插入图片描述

  1. 单链表非空：使用一个 tail 指针用来寻找单链表的尾部，要将新结点插入到 tail->next 为 NULL 的位置。

在这里插入图片描述

2. 代码实现

//传过来的是个指针变量的地址，需要使用二级指针 pplist 来接收
void SListPushBack(SLNode** pplist, SLTDataType x)
{
	assert(pplist);

	SLNode* newnode = BuySListNode(x);	//创建一个新的结点

	if (NULL == *pplist)				//单链表当前为空
	{
		*pplist= newnode;				//直接将新结点插入链表
	}
	else								//单链表非空
	{
		SLNode* tail = *pplist;			//tail 用于寻找单链表的尾结点

		while (tail->next != NULL)		//没有找到尾结点
		{
			tail = tail->next;			//指向下一个结点
		}
		tail->next = newnode;			//将新结点插入到尾结点之后，成为新的尾结点
	}
}

3. 函数调用

在这里插入图片描述

5. 单链表头插

1. 插入链表

  • 不管链表中有多少个结点，所有的数据都插入到链表的都一个位置。

在这里插入图片描述

2. 代码实现

//要改变链表内容，实参要传指针变量的地址，形参用二级指针接收
void SListPushFront(SLNode** pplist, SLTDataType x)
{
	assert(pplist);						//传过来的不能是 NULL 指针

	SLNode* newnode = BuySListNode(x);	//创建新结点
	newnode->next = *pplist;			//将首结点地址交给新结点指针域
	*pplist= newnode;					//让新结点成为新的首结点
}

3. 调用函数

在这里插入图片描述

6. 单链表尾删

  • 每次将单链表尾部的的一个结点删除掉。

1. 实现方法

  1. 链表中只一个结点：直接释放链表指针指向的那个结点。

在这里插入图片描述

  1. 链表中有多个结点：使用一个 tail 指针寻找尾结点的前一个结点，如果 tail 所指向结点的下个结点的指针域为空，则说明 tail->next 指向的结点为尾结点，直接释放即可。

在这里插入图片描述

2. 实现代码

void SListPopBack(SLNode** pplist)
{
	assert(pplist);							//pplist 指向的 plist 不是 NULL
	assert(*pplist);						//plist 指向的链表不为空

	if (NULL == (*pplist)->next)			//1.一个结点
	{
		free(*pplist);						//释放链表中唯一的一个结点
		*pplist= NULL;
	}
	else									//2.多个结点
	{
		SLNode* tail = *pplist;				//使用 tail 找尾结点

		while (tail->next->next != NULL)	//当前结点的下下个结点不为空
		{
			tail = tail->next;				//tail 指向链表下一个结点
		}

		free(tail->next);					//释放 tail->next 指向的尾结点
		tail->next = NULL;					//将 tail->next 的值置空
	}
}

3. 函数调用

在这里插入图片描述

7. 单链表头删

  • 每次删除都只删除单链表的首结点。

1. 实现方法

  1. 链表有多个结点：先用一个临时指针变量保存首结点的地址，再让链表指针指向第二个结点，最后释放首结点。

在这里插入图片描述

  1. 链表只一个结点：步骤和上面相同，只不过只有一个结点时，链表指针在第二步会指向 NULL 而已。

2. 实现代码

void SListPopFront(SLNode** pplist)
{
	assert(pplist);				//传过来的不是 NULL
	assert(*pplist);			//链表不为空

	SLNode* tmp = *pplist;		//先保存链表首结点
	*pplist= (*pplist)->next;	//让链表指针指向第二个结点
	free(tmp);					//释放首结点
}

3. 函数调用

在这里插入图片描述

8. 单链表查找

  • 在单链表中查找数据域的值等于形参 x 的结点，并返回该结点的地址。
  • 如果链表中不存在 x 则返回 NULL。

实现代码

SLNode* SListFind(SLNode* plist, SLTDataType x)
{
	assert(plist);				//链表不为空

	SLNode* cur = plist;		//cur 用来访问当前结点

	while (cur != NULL)			//cur 没有走到链表末尾
	{
		if (cur->data == x)		//当前结点数据域的值等于形参 x
		{
			return cur;			//返回当前结点的地址
		}
		else					
		{
			cur = cur->next;	//继续往后找数据域等于 x 的结点
		}
	}

	return cur;					//链表中没有 x，返回 NULL
}

调用函数

在这里插入图片描述

9. 在指定 pos 位置前插入结点

1. 实现方法

  • 定义一个 cur (current) 指针指向当前结点，如果当前结点的下一个结点的地址等于 pos 的地址，则将 pos 指向的结点插入到新结点后，再将新结点插入到 cur 结点后。

在这里插入图片描述

2. 实现代码

void SLTInsert(SLNode** pplist, SLNode* pos, SLTDataType x)
{
	assert(pplist);						//传过来的不能是空指针
	assert((*pplist) && (pos));			//要么同时不为空
	assert(!(*pplist) && !(pos));		//要么同时为空

	SLNode* newnode = BuySListNode(x);	//创建新结点

	if (*pplist == pos)					//链表只有一个结点 - 头插
	{
		SListPopFront(pplist,x)			//新结点作首结点
	}
	else								//找 pos 位置的前一个
	{
		SLNode* cur = *pplist;			//cur 是 pos 位置的前一个结点

		while (cur->next != pos)		//当前结点的下个结点不是 pos 
		{
			cur = cur->next;			//cur 向后寻找 pos 结点
		}

		newnode->next = pos;		//让新结点指针域指向 pos 结点
		cur->next = newnode;			//当前结点的指针域指向新结点
	}
}

调用函数

在这里插入图片描述

10. 删除指定 pos 位置的结点

1. 实现思路

  1. 在删除 pos 位置的结点前，先用一个前趋指针 pre 保存 pos 结点的前一个结点。
  2. 让 pre 指向 pos 的下一个结点。
  3. 销毁 pos 指向的结点。

在这里插入图片描述

2. 实现代码

void SLTErase(SLNode** pplist, SLNode* pos)
{
	assert(pplist);
	assert((*pplist) && (pos));		//两个指针同时不为空

	SLNode* pre = NULL;				//当前位置的前一个结点
	SLNode* cur = *pplist;			//用来寻找 pos 结点

	while (cur != NULL)
	{
		if (cur != pos)			
		{
			pre = cur;
			cur = cur->next;
		}
		else						//cur 找到了 pos 指向的结点
		{
			pre->next = cur->next;	//pos 的前一个结点指向 pos 的后一个结点
			free(cur);				//删除 pos 指向的结点
			cur = NULL;
		}
	}
}

11. 单链表销毁

  • 持续对单链表连续执行头删。

实现代码

void SLTDestroy(SLNode** pplist)
{
	assert(pplist);					//链表指针不能为空
	
	SLNode* cur = *pplist;
	
	while (cur)						//链表不为空则执行头删
	{
		SLNode* next = cur->next;	//保存当前结点的下一个结点
		free(cur);					//释放当前结点
		cur = next;					//对下一个结点执行以上操作
	}
	
	*pplist = NULL;					//无论链表原来为不为空最后都执行这步
}

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

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

相关文章

计算机二级公共基础

计算机二级公共基础

知识点 1.树 树的最大层次（最长路径的长度）称为树的深度 二叉树的后件最多不超过两个 满二叉树：除最后一层每一层的所有节点都有两个子节点。（满二叉树一定是完全二叉树） 完全二叉树：所有节点均达到最大数…
阅读更多...
vue3怎么获取el-form的元素节点

vue3怎么获取el-form的元素节点

在元素中使用ref设置名称 在ts中通过从element-plus引入formInstance,设置formRef同名名称字段来获取el-form节点
阅读更多...
疏散及应急照明灯在地下建筑中的运用探析

疏散及应急照明灯在地下建筑中的运用探析

安科瑞 华楠 摘要：新型疏散及应急照明灯在地下建筑中的有效应用，可以有效的促使地下建筑提升自身的安全性能，尤其是在发生火灾时，改变传统的应急疏散的局限性，充分发挥出自身的新型特殊功能，为人们提供更为…
阅读更多...
ElementUI-tree拖拽功能与节点自定义

ElementUI-tree拖拽功能与节点自定义

前言 在管理端会遇到多分类时，要求有层次展示出来，并且每个分类有额外的操作。例如：添加分类、编辑分类、删除、拖到分类等。 下面将会记录这样的一个需求实习过程。 了解需求 分类展示按层级展示分类根据特定的参数展示可以操作的按钮&a…
阅读更多...
基于SpringBoot+Vue的婚恋相亲交友系统

基于SpringBoot+Vue的婚恋相亲交友系统

基于SpringBootVue的婚恋相亲交友系统~ 开发语言：Java数据库：MySQL技术：SpringBootMyBatisVue工具：IDEA/Ecilpse、Navicat、Maven 系统展示 主页 管理员界面 摘要 基于SpringBootVue的婚恋相亲交友系统是一个现代化的、高效的交…
阅读更多...
使用bitmap实现可回收自增id

使用bitmap实现可回收自增id

需求描述 设计一个方法，每次调用返回一个自增id，同时需要满足以下要求。 可更新id的状态为已使用，已使用的id下次调用时不再返回可修改某个id的状态为未使用，下次调用时设为未使用状态的id可重新被返回 思路 思路一&#xff1…
阅读更多...
全志T507-H技术帖 | 去掉IO扩展芯片后保留扩展引脚功能的实现方法

全志T507-H技术帖 | 去掉IO扩展芯片后保留扩展引脚功能的实现方法

飞凌嵌入式推出的OKT507-C作为一款广受欢迎的开发板拥有丰富的功能接口，而实际上OKT507-C开发板的CPU引脚资源是比较紧缺的，那么它究竟是如何提供如此丰富的接口资源的呢？答案就是IO扩展芯片——TCA6424A。 这是一个24 位 I2C 和系统管理总线…
阅读更多...
第三方商城对接项目（202311）

第三方商城对接项目（202311）

文章目录 1. 项目背景和目标2. 项目成果3. 项目经验总结4. 展望和建议 1. 项目背景和目标 竞标成功接口对接第三方商城，商品，订单，售后尽快完成对接 2. 项目成果 完成整个项目功能流程对接新业务功能移交项目等业务部门使用 3. 项目经验总…
阅读更多...
MySQL中表的增删查改（进阶），超详细！

MySQL中表的增删查改（进阶），超详细！

目录 一、数据库的约束 1、约束类型 2、NULL约束 3、UNIQUE：唯一约束 4、DEFAULT：默认值约束 5、PRIMARY KEY：主键约束（主键只能定义一个，NOT NULL 和 UNIQUE 的结合） 6、FOREIGN KEY：外键约…
阅读更多...
C++之List容器

C++之List容器

1.list容器简介 list是序列容器，允许在序列中的任何位置执行固定O(1)时间复杂度的插入和删除操作，并在两个方向进行迭代。list容器是一个双向循环链表。 list容器与vector容器区别： ①list中空间是随机的，通过指针域保存下一个成员…
阅读更多...
【C++】类和对象的关系，对象的存储方式以及对象内存的计算

【C++】类和对象的关系，对象的存储方式以及对象内存的计算

💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃个人主页 ：阿然成长日记 …
阅读更多...
Window10安装Docker

Window10安装Docker

文章目录 Window10安装Docker前提条件Hyper -VWSL 2.0 安装包下载执行安装包更新 Window10安装Docker 前提条件 Hyper -V 如何启用 WSL 2.0 安装包下载 官网地址 下载后： 执行安装包 wsl --update等得有点久 重新打开 拉取一个helloworld镜像 说明已经…
阅读更多...
【CocosCreator】利用遮罩Mask实现单边开门效果

【CocosCreator】利用遮罩Mask实现单边开门效果

如果对前端八股文感兴趣，可以留意公重号：码农补给站，总有你要的干货。 实现思路 首先新建一个新的遮罩节点（全部采用默认属性），将其大小设为门的大小，然后将其摆放到门所在的位置，如…
阅读更多...
MATLAB_5MW风电永磁直驱发电机-1200V直流并网MATLAB仿真模型

MATLAB_5MW风电永磁直驱发电机-1200V直流并网MATLAB仿真模型

仿真软件：matlab2016b 风机传动模块、PMSG模块、蓄电池模块、超级电容模块、无穷大电源、蓄电池控制、风机控制、逆变器控制等模块。 逆变器输出电压： 混合储能系统SOC： 威♥关注“电击小子程高兴的MATLAB小屋”获取更多精彩资料&#xff0…
阅读更多...
单调栈【2023年最新】

单调栈【2023年最新】

做题的时候看到了单调栈，但是不知道是个什么玩意，记录一下吧。 单调栈含义 单调栈是一种特殊的数据结构，用于解决一些与单调性相关的问题。它的基本含义是在栈的基础上，维护一个单调递增或单调递减的栈。 在单调递增栈中&#…
阅读更多...
SpringCloud-Gateway无法使用Feign服务(2021.X版本)

SpringCloud-Gateway无法使用Feign服务(2021.X版本)

Spring Cloud Gateway 2021.x版本，无法使用Feign调用其他服务接口。 问题原因： 在官网的 issue 里面找到了相关的问题。 How to call another micro-service on GatewayFilterFactory ? Issue #1090 spring-cloud/spring-cloud-gateway GitHubHel…
阅读更多...
QT QSplitter

QT QSplitter

分裂器QSplitter类提供了一个分裂器部件。和QBoxLayout类似，可以完成布局管理器的功能,但是包含在它里面的部件,默认是可以随着分裂器的大小变化而变化的。 比如一个按钮放在布局管理器中,它的垂直方向默认是不会被拉伸的,但是放到分裂器中就可以被拉伸。还有一点不…
阅读更多...
OV5640的参数与配置方法

OV5640的参数与配置方法

分辨率和速率（FPS） 寄存器配置 I/O 板的驱动能力和方向控制 system clock control OV5640 PLL 允许输入时钟频率范围为 6~27 MHz，最大 VCO 频率为 800 MHz。 MipiClk 用于 MIPI，SysClk 用于图像信号处理 (ISP) 模块的内部时钟。 …
阅读更多...
TensorFlow（1）：深度学习的介绍

TensorFlow（1）：深度学习的介绍

1 深度学习与机器学习的区别 学习目标：知道深度学习与机器学习的区别 区别：深度学习没有特征提取 1.1 特征提取方面 机器学习的特征工程步骤是要靠手动完成的，而且需要大量领域专业知识深度学习通常由多个层组成，它们通常将更简…
阅读更多...
Redis系列之实现分布式自增主键

Redis系列之实现分布式自增主键

软件环境 JDK 1.8 SpringBoot 2.2.1 Maven 3.2 Mysql 8.0.26 redis 6.2.14 Mybatis Plus 3.4.3.4 开发工具 IntelliJ IDEA smartGit 一、实现原理 使用Redis来实现分布式的主键自增主要是依赖于Redis的INCR命令，调用INCR命令的对应key，其数值…
阅读更多...
最新文章

Copyright @ 2022~2023