数据结构——单链表（Singly Linked List）

1.链表介绍

        链表是一种物理储存上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

        对于上图，每一个结点都是一个结构体，这个结构体内存储的成员是值和下一个结点的地址。所以plist存储的是第一个结点的地址（即plist为一个结构体指针），而后续每个节点都会存储对于自己下一个结点的地址。由于链表的结点是通过malloc一个个申请出来的，所以其存储空间是不连续的，也是由于这个原因我们才需要通过一个结构体指针来访问逻辑上的下一个结点。

2.链表的分类

        链表具有三个特征，根据这三个特征的排列组合得知链表有8种组合。

2.1 单向和双向

        

       单向链表的每个结点成员只有指向下一个结点的指针，而没有指向上一个结点的指针。双向链表则二者皆有，所以单向链表就像“过河的卒”，不可以回头访问自己的上一个结点，而双向链表则既可以访问自己的上一个结点，也可以访问自己的下一个结点。

2.2 带头和不带头

        带头链表和不带头链表的区别就在于带头链表有一个“头结点”。

总结下来，带头链表会有一些优势：

        ① 避免空指针的访问：因为头结点又名哨兵位，所以它起到一个放哨的作用。无论链表结构是否为空，都可以放心的访问链表，因为有头结点的存在，就算链表为空也不会访问到空指针，更加安全。

        ② 函数传参不需要传递二级指针：如果没有头结点，当我对链表增删查改操作时，由于手上拿的是链表的第一个结点，所以如果操作到链表第一个位置，可能会涉及到链表第一个结点指针的变化，而传一级指针的参数是不会使该操作生效的，所以需要二级指针。但是有了头结点后无论做什么操作，头结点一旦生成直至链表销毁都不会改变，所以不需要传递二级指针，更加方便。

2.3 循环和非循环

        非循环链表的尾结点由于是最后一个结点，其后没有结点，所以它的next指针是指向NULL的。循环链表的尾结点则是指回了链表的第一个结点，使得整体结构体现出循环的功能。

        

        尽管有八种链表的组合形式，但是我们常用的的只有两种形式的链表。即单向不带头不循环链表和双向带头循环链表。

3.单链表工程

对于一个单链表工程，我们一般模式需要分为三部分。

        SList.h 为头文件，其中包含库函数头文件的包含，顺序表结构体的定义与声明，接口函数的声明。

        SList.c 包含接口函数的定义。

        Test.c 是我们的测试源文件，从这里进入main函数。

 3.1 单链表的定义

        建立一个单链表需要多个结点共同构成，我们针对单链表一个结点进行定义，将其定义为一个结构体，包含数据和下一个结点的指针。

typedef int SLNDataType;

typedef struct SListNode
{
	SLNDataType val;
	struct SListNode* next;
}SLNode;

3.2 单链表的函数接口

        对一个单链表，我们需要一些函数来方便我们管理数据。因此我们所要实现的基本的函数接口需要包含增删查改等功能。

3.2.1 单链表结点插入

        单链表常用的插入数据方式有：头插，即在链表最前端插入数据结点；尾插，即在链表最后端插入数据结点；随机插入，即在指定的结点前或者后插入结点。

        单链表由于没有头结点，所以在插入时很有可能需要改变头结点，例如头插或链表为空时插入。所以在参数传递时我们不得不以二级指针的形式进行传参，这样可以在函数内部修改头结点，从而成功插入结点。

3.2.1.1 单链表创建结点

        因为在单链表的函数接口中有多个结点需要插入结点，需要频繁创建结点并以不同的方式插入，所以我们将创建节点的过程封装成一个函数，在需要创建结点时调用函数即可，避免代码冗余。

SLNode* CreateNode(SLNDataType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;
	return newnode;
}
3.2.1.2 单链表头插

        单链表头插时只需要将原来的第一个结点链接在新结点之后即可。

void SLTPushFront(SLNode** pphead, SLNDataType x)
{
	assert(pphead);

	SLNode* tmp = CreateNode(x);
	tmp->next = *pphead;
	*pphead = tmp;
}
3.2.1.3 单链表尾插

        单链表尾插需要先找到尾结点，但由于单链表的单向不循环的特性，我们只能从头遍历链表找到尾结点，才能将新结点链接在尾结点之后。

void SLTPushBack(SLNode** pphead, SLNDataType x)
{
	assert(pphead);

	if (*pphead == NULL)
	{
		*pphead = CreateNode(x);
	}
	else
	{
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = CreateNode(x);
	}
}
3.2.1.4 单链表在指定结点前插入

        在指定节点前插入需要这个结点前一个结点的指针指向新结点，所以我们就需要先遍历找到这个结点的前一个结点。

//在pos节点前插入
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);

	SLNode* tmp = CreateNode(x);
	if (pos == *pphead)
	{
		tmp->next = *pphead;
		*pphead = tmp;
	}
	else
	{
		SLNode* prev = *pphead;
		tmp->next = pos;
		while (prev->next != pos)
		{
			//if (prev->next == NULL)
			//{
			//	printf("插入节点有误\n");
			//	exit(-1);
			//}
			prev = prev->next;
		}
		prev->next = tmp;
	}
}
3.2.1.5 单链表在指定结点后插入

        在指定节点后插入就可以不用遍历链表，直接链接即可。

void SLTInsertAfter(SLNode** pphead, SLNode* pos, SLNDataType x)
{
	assert(pphead);
	assert(pos);

	SLNode* tmp = CreateNode(x);
	tmp->next = pos->next;
	pos->next = tmp;
}

3.2.2 单链表结点删除

        单链表常用的删除结点的方式有：头删，即删除在链表最前端的结点；尾删，即删除在链表最后端的结点；随机删除，即删除在指定的结点前或者后的结点。

3.2.2.1 单链表头删

        头删只需要将第一个结点释放掉，然后将原来指向链表第一个结点的变量赋值第二个结点即可。

void SLTPushFront(SLNode** pphead, SLNDataType x)
{
	assert(pphead);

	SLNode* tmp = CreateNode(x);
	tmp->next = *pphead;
	*pphead = tmp;
}
3.2.2.2 单链表尾删

        尾删需要遍历链表找到尾结点，然后将尾结点释放并将尾结点的前一个结点的next指针赋值为空指针。需要警惕只有一个结点的链表，需要将链表置为空。

void SLTPopBack(SLNode** pphead)
{
	assert(pphead);
	//0个节点
	assert(*pphead);
	//1个节点
	SLNode* prev = NULL;
	SLNode* tail = *pphead;
	if (tail->next == NULL)
	{
		free(tail);
		tail = NULL;
		*pphead = NULL;
	}
	else
	{
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}
}
3.2.2.3 单链表删除指定结点

        想要删除一个指定结点，需要找到其前一个结点，将前一个结点与后一个结点链接起来。

//删除pos节点
void SLTErase(SLNode** pphead, SLNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	
	if (pos == *pphead)
	{
		SLNode* tmp = *pphead;
		*pphead = (*pphead)->next;
		free(tmp);
		tmp = NULL;
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			/*if (prev->next == NULL)
			{
				printf("删除节点有误\n");
				exit(-1);
			}*/
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
3.2.2.4 单链表在指定结点后删除

        删除指定结点后一个结点，只需要将这个结点和它的下下个结点链接起来即可。

//在pos位置后删除
void SLTEraseAfter(SLNode** pphead, SLNode* pos)
{
	assert(pphead);
	assert(pos);
	assert(pos->next);

	SLNode* tmp = pos->next;
	pos->next = tmp->next;
	free(tmp);
	tmp = NULL;
}

3.2.3 单链表打印

        依次遍历所有结点即可，由于不需要改变链表的值，所以可以传递一个一级指针。

void SLTPrint(SLNode* phead)
{
	while (phead != NULL)
	{
		printf("%d->", phead->val);
		phead = phead->next;
	}
	printf("NULL\n");
}

3.2.4 单链表查找

        用于查找链表中指定值的结点，会返回该结点的地址。所以，只需要遍历链表并且比较即可。

SLNode* SLTFind(SLNode* phead, SLNDataType x)
{

	SLNode* tmp = phead;
	while (tmp != NULL)
	{
		if (tmp->val == x)
		{
			return tmp;
		}
		else
		{
			tmp = tmp->next;
		}
	}
	printf("未找到节点\n");
	return NULL;
}

3.2.5 单链表销毁

        销毁单链表只需要遍历链表，依次释放所有结点即可。

void SLTDestroy(SLNode** pphead)
{
	while (*pphead != NULL)
	{
		SLNode* tmp = *pphead;
		*pphead = (*pphead)->next;
		free(tmp);
		tmp = NULL;
	}
}

4.单链表总结反思

        无头单向不循环链表，这种链表虽然结构简单但是应用广泛。在最近的学习过程中，我发现不少与链表有关的题目多用单链表来设题，除此之外，一些更加复杂的结构也需要用单链表作为支撑，所以可以看出其重要性。

        除此之外，恰恰是因为其结构简单，所以对特殊情况的限制较少，这就需要我在写代码时充分考虑可能会发生的所有情况，以便做出合理控制。毫无疑问，单链表是很重要的，我感觉它就像“原汁原味”的链表，需要反复品尝，并且一切上层建筑都是源于这看似简单的结构。

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

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

相关文章

C语言—指针和数组

C语言—指针和数组

写在前 一个指针变量指向某个普通变量，则指针变量就等于普通变量。 指针变量存放的是地址，普通变量存放的是数据。 int * p; int i5,j; p &i;此程序，*pi5，在所有出现 *p 或 i 的位置，两者都可以互相替换。 通过…
阅读更多...
2023年亚太杯数学建模A题水果采摘机器人的图像识别功能（基于yolov5的苹果分割）

2023年亚太杯数学建模A题水果采摘机器人的图像识别功能（基于yolov5的苹果分割）

注：.题中附录并没有给出苹果的标签集，所以需要我们自己通过前4问得到训练的标签集，采用的是yolov5 7.0 版本，该版本带分割功能 一：关于数据集的制作： clc; close all; clear; %-----这个是生成yolov5 数据…
阅读更多...
2、git进阶操作

2、git进阶操作

2、git进阶操作 2.1.1 分支的创建 命令参数含义git branch (git checkout -b)<new_branch> <old_branch>表示创建分支-d <-D>删除分支 –d如果分支没有合并&#xff0c;git会提醒&#xff0c;-D强制删除-a -v查看分支-m重新命名分支commit id从指定的commi…
阅读更多...
【数据结构】树与二叉树（廿二）：树和森林的遍历——后根遍历(递归算法PostOrder、非递归算法NPO)

【数据结构】树与二叉树（廿二）：树和森林的遍历——后根遍历(递归算法PostOrder、非递归算法NPO)

文章目录 5.1 树的基本概念5.1.1 树的定义5.1.2 森林的定义5.1.3 树的术语 5.2 二叉树5.3 树5.3.1 树的存储结构1. 理论基础2. 典型实例3. Father链接结构4. 儿子链表链接结构5. 左儿子右兄弟链接结构 5.3.2 获取结点的算法5.3.3 树和森林的遍历1. 先根遍历&#xff08;递归、非…
阅读更多...
XG916Ⅱ轮式装载机后驱动桥设计机械设计CAD

XG916Ⅱ轮式装载机后驱动桥设计机械设计CAD

wx供重浩&#xff1a;创享日记 对话框发送&#xff1a;装载机 获取完整论文报告工程源文件 本次设计内容为XG916Ⅱ装载机后驱动桥设计&#xff0c;大致上分为主传动的设计&#xff0c;差速器的设计&#xff0c;半轴的设计&#xff0c;最终传动的设计四大部分。其中主传动锥齿轮…
阅读更多...
【从删库到跑路】MySQL数据库 — E-R图 | 关系模型

【从删库到跑路】MySQL数据库 — E-R图 | 关系模型

&#x1f38a;专栏【MySQL】 &#x1f354;喜欢的诗句&#xff1a;更喜岷山千里雪 三军过后尽开颜。 &#x1f386;音乐分享【如愿】 大一同学小吉&#xff0c;欢迎并且感谢大家指出我的问题&#x1f970; 文章目录 &#x1f339;简述什么是E-R图⭐核心概念 &#x1f339;E-R图…
阅读更多...
MTK联发科MT6762/MT6763/MT6765安卓核心板参数规格比较

MTK联发科MT6762/MT6763/MT6765安卓核心板参数规格比较

MT6762安卓核心板 MTK6762安卓核心板是一款工业级高性能、可运行 android9.0 操作系统的 4G智能模块。 CPU&#xff1a;4xCortex-A53 up to 2.0Ghz/4xCortex-A53 up to 1.5GhzGraphics&#xff1a;IMG GE8320 Up to 650MhzProcess&#xff1a;12nmMemory&#xff1a;1xLP3 9…
阅读更多...
Windows从源码构建tensorflow（离线编译）

Windows从源码构建tensorflow（离线编译）

由一开始的在线编译&#xff0c;到后面的离线编译&#xff0c;一路踩坑无数&#xff0c;历经整整6个半小时&#xff0c;终于编译成功&#xff01;在此记录一下参考过的文章&#xff0c;有时间整理一下踩坑记录。 一、环境配置 在tensorflow官网上有版本对应关系 win10 bazel …
阅读更多...
只考数据结构，计算机评级C+，成都信息工程大学考情分析

只考数据结构，计算机评级C+，成都信息工程大学考情分析

成都信息工程大学(C) 考研难度&#xff08;☆☆&#xff09; 内容&#xff1a;23考情概况&#xff08;拟录取和复试分析&#xff09;、院校概况、24专业目录、23复试详情、各专业考情分析、各科目考情分析。 正文1715字&#xff0c;预计阅读&#xff1a;3分钟 2023考情概况 …
阅读更多...
1、Docker概述与安装

1、Docker概述与安装

相关资源网站&#xff1a; ● docker官网&#xff1a;http://www.docker.com ● Docker Hub仓库官网: https://hub.docker.com/ 注意&#xff0c;如果只是想看Docker的安装&#xff0c;可以直接往下拉跳转到Docker架构与安装章节下的Docker具体安装步骤&#xff0c;一步步带你安…
阅读更多...
红黑树详解

红黑树详解

红黑树的概念与性质 前置知识 在学习红黑树之前&#xff0c;最好有二叉查找树和AVL树的基础&#xff0c;因为红黑树本质就是一种特殊的二叉查找树&#xff0c;而红黑树的操作中需要用到AVL树中旋转的相关知识。至于二叉查找树和AVL树&#xff0c;可以参考如下两篇博客&#xf…
阅读更多...
01、Tensorflow实现二元手写数字识别

01、Tensorflow实现二元手写数字识别

01、Tensorflow实现二元手写数字识别&#xff08;二分类问题&#xff09; 开始学习机器学习啦&#xff0c;已经把吴恩达的课全部刷完了&#xff0c;现在开始熟悉一下复现代码。对这个手写数字实部比较感兴趣&#xff0c;作为入门的素材非常合适。 基于Tensorflow 2.10.0 1、…
阅读更多...
C#，《小白学程序》第一课：初识程序，变量，数据与显示

C#，《小白学程序》第一课：初识程序，变量，数据与显示

曰&#xff1a;扫地僧练就绝世武功的目的是为了扫地更干净。 1 引言 编程只是一项技术&#xff0c;如包包子&#xff0c;不是什么高深的科学。 学习程序最不好的方法是先学习枯燥的语法。 学习程序主要是用代码解决问题。因此&#xff0c;我们抛开所有的语法与诸多废物&…
阅读更多...
【Tiny_CD】Tiny_CD变化检测网络详解（含python代码）

【Tiny_CD】Tiny_CD变化检测网络详解（含python代码）

题目：TinyCD: A (Not So) Deep Learning Model For Change Detection 论文：paper 代码：code 目录 🍟 🍟1.摘要 🍗🍗 2.贡献 🍖🍖 3.网络结构
阅读更多...
classifier-free-guidance 扩散模型引导生成

classifier-free-guidance 扩散模型引导生成

浅谈扩散模型的有分类器引导和无分类器引导 - 知乎这篇文章主要比较一下扩散模型的引导生成的三种做法的区别。它们分别是用显式分类器引导生成的做法&#xff0c;用隐式无分类器引导的做法和用CLIP计算跨模态间的损失来引导生成的做法。 Classifier-Guidance: Diffusion Mode……
阅读更多...
React + BraftEditor 实现富文本编辑

React + BraftEditor 实现富文本编辑

Braft Editor 是一个基于 React 和 Draft-js 开发的富文本编辑器&#xff0c;提供了丰富的基础功能&#xff0c;如基本文本格式化、列表、链接、图片上传、视频插入等&#xff0c;并且还支持扩展。 首先&#xff0c;确保你已经在项目中安装了 Braft Editor 和它的依赖项&#x…
阅读更多...
腾讯云发布新一代基于AMD处理器的星星海云服务器实例SA5

腾讯云发布新一代基于AMD处理器的星星海云服务器实例SA5

基础设施的硬实力&#xff0c;愈发成为云厂商的核心竞争力。 11月24日&#xff0c;腾讯云发布了全新一代星星海服务器。基于自研服务器的高密设计与硬件升级&#xff0c;对应云服务器SA5是全球首家搭载第四代AMD EPYC处理器&#xff08;Bergamo&#xff09;的公有云实例&#…
阅读更多...
【机器学习】平滑滤波

【机器学习】平滑滤波

平滑滤波技术 平滑滤波&#xff0c;顾名思义就是对信号进行处理使之整体显得更加平滑&#xff0c;降低噪声影响&#xff0c;提高信号质量&#xff0c;它常见于数字信号处理和图像处理&#xff0c;一般意义上的数字信号多体现于一维数据&#xff0c;图像信号多体现于二维数据。…
阅读更多...
大众博客系统测试报告【改】

大众博客系统测试报告【改】

一、项目背景 大众博客系统采用前后端分离的方法来实现&#xff0c;同时使用了数据库来存储相关的数据&#xff0c;同时将其部署到云服务器上。前端主要有四个页面构成&#xff1a;登录页、列表页、详情页以及编辑页&#xff0c;以上模拟实现了最简单的大众博客系统。其结合后端…
阅读更多...
DGL在异构图上的GraphConv模块

DGL在异构图上的GraphConv模块

回顾同构图GraphConv模块 首先回顾一下同构图中实现GraphConv的主要思路&#xff08;以GraphSAGE为例&#xff09;&#xff1a; 在初始化模块首先是获取源节点和目标节点的输入维度&#xff0c;同时获取输出的特征维度。根据SAGE论文提出的三种聚合操作&#xff0c;需要获取所…
阅读更多...
最新文章

Copyright @ 2022~2023