数据结构---＞单链表

文章目录

  • 链表
    • 链表的分类
  • 单链表
    • 单链表的存储结构
    • 单链表主要实现的接口函数
    • 单链表尾插
    • 动态申请新节点
    • 单链表头插
    • 单链表的尾删
    • 单链表的头删
    • 在指定位置之前插入
      • 单链表查找
      • 插入
    • 在指定位置之后插
    • 删除指定位置元素
    • 删除指定位置之后的元素
    • 顺序输出链表
    • 销毁单链表
  • 顺序表和单链表的区别
  • 关于指针传参

链表

链表是一种物理结构(储存结构)上不一定连续，不一定是顺序的存储结构，数据元素是通过链表中的指针链接次序实现的

链表的分类

image.png
链表有很多种类 两两匹配就一共有八种 这里主要介绍一下单链表(单向不带头不循环)

单链表

单链表的存储结构

图示：

image.png
链表中的结点一般都是在堆上申请的，从堆上申请的空间，按照一定的规则申请的，两次申请的空间也能相同也可能不相同。用一个指针就能找到下一个结点的空间地址了，从而形成线性关系

typedef int ElemType;
typedef struct SListNode
{
	ElemType data;
	struct SListNode* next;
}SLTNode;

typedef SLTNode* LinkList;//定义链表

定义一个数据域和指针域。数据域用来存放数据，指针域的指针指向下一个结点的空间地址

单链表主要实现的接口函数

//创建新结点
SLTNode* NewSLTNode(ElemType x);
//尾插
void SLTPushBack(SLTNode** phead, ElemType x);
//头插
void SLTPushFront(SLTNode** phead, ElemType x);
//尾删
void SLTPopBack(SLTNode** phead);
//头删
void SLTPopFront(SLTNode** phead);
//单链表查找
SLTNode* SLTNodeFind(SLTNode* phead, ElemType x);
//在pos之前插入
void SLTInsert(SLTNode** phead, SLTNode* pos, ElemType x);
//在pos之后插入
void SLTInsertAfter(SLTNode* pos, ElemType x);
//删除pos位置
void SLTErase(SLTNode** phead, SLTNode* pos);
//删除pos位置后得
void SLTEraseAfter(SLTNode* pos);
//打印
void SLTNodePrintf(SLTNode* ps);

单链表尾插

单链表插入主要分为两种情况

  • 没有结点，单链表是空的情况

image.png

  • 有一个以上的结点

image.png

注意:
这里需要一个头指针(pehad 指向第一个结点的指针)来维护这个链表。否则将无法寻找到这个链表

void SLTPushBack(SLTNode** phead, ElemType x)
{
	//申请结点
	SLTNode* newnode = NewSLTNode(x);
	//空链表
	if (*phead == NULL)
	{
		*phead = newnode;
	}
	//有一个以上的结点
	else
	{
		SLTNode* tail = *phead;
		//遍历找最后一个结点
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		//连接新结点
		tail->next = newnode;
	}
}

链表结点的类型是struct SListNode* (结构体指针)类型，插入一个新元素，需要改变头指针的指向，所以实参需要传其地址，形参需要一个结构体指针的指针才可接受这个地址即二级指针
每次进行插入操作时都要申请结点，封装成函数，方便复用

动态申请新节点

SLTNode* NewSLTNode(ElemType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if(newnode == NULL)
	{
		perror("malloc fail");
		eixt(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

单链表头插

头插可以只看作一种情况
空和非空的处理结果都一样

图解：
image.png
代码实现：

void SLTPushFront(SLTNode** phead, ElemType x)
{
	//申请结点
	SLTNode* newnode = NewSLTNode(x);
	//空和非空链表都可处理
	newnode->next = *phead;
	*phead = newnode;
}

单链表的尾删

尾删要注意三种情况，分别是

  • 空链表
    错误处理
  • 只有一个结点
    直接释放该结点即可

image.png

  • 有两个结点以上的链表
    先找到最后一个结点，记录最后一个结点的前一个 然后释放最后一个结点，再将最后一个的前一个指针域置为NULL
    image.png

代码实现：

void SLTPopBack(SLTNode** phead)
{
	//空链表
	assert(*phead);
	//只有一个结点
	if ((*phead)->next == NULL)
	{
		free(*phead);
		*phead = NULL;
	}
	//有两个结点以上的链表
	else
	{
		SLTNode* tail = *phead;
		SLTNode* tailprev = NULL;//记录最后一个的前一个
		while (tail->next != NULL)
		{
			tailprev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		tailprev->next = NULL;
	}
}

单链表的头删

头删时要注意两种情况分别是

  • 空链表
    错误处理
  • 有一个或多个结点
    先将头指针移动到第二个结点(只有一个结点第二个结点即为NULL也符合逻辑)的位置，在释放该结点
    image.png

image.png
代码实现：

void SLTPopFront(SLTNode** phead)
{
	//空
	assert(*phead);
	//一个和多个结点处理逻辑一样
	SLTNode* newhead = (*phead)->next;
	free(*phead);
	*phead = newhead;
}

在指定位置之前插入

位置由自己指定
比如链表元素 1 2 3 4 在2的位置之前插入6 链表变为1 6 2 3 4
插入之前首先要找到该元素结点的位置

单链表查找

SLTNode* SLTNodeFind(SLTNode* phead, ElemType x)
{
	assert(phead);
	SLTNode* pos = phead;
	while (pos)
	{
		if (pos->data == x)
		{
			return pos;
		}
		pos = pos->next;
	}
	//没有该元素
	return NULL;
}

然后根据查找到元素的结点位置进行插入

插入

在指定位置插入时要考虑以下情况

  • 空链表
    不需要做处理 因为空链表找不到指定的位置
  • 指定位置不存在
    错误处理
  • 指定的位置是第一个结点
    复用头插即可
  • 其他情况下插入
    申请新节点 找到pos的前一个结点 将新结点连接接起来
    image.png
void SLTInsert(SLTNode** phead, SLTNode* pos, ElemType x)
{
	assert(*phead);
	assert(pos);
	
	if (pos == *phead)
	{
		SLTPushFront(phead, x);
	}
	else
	{
		//申请结点
		SLTNode* newnode = NewSLTNode(x);
		//找pos的前一个
		SLTNode* cur = *phead;
		SLTNode* posprev = NULL;
		while (cur != pos)
		{
			posprev = cur;
			cur = cur->next;
		}
		posprev->next = newnode;
		newnode->next = pos;
	}
}

在指定位置之后插

比如链表元素 1 2 3 4 在2的位置之后插入6 链表变为1 2 6 3 4
和指定位置之前插入一样，首先要找到该元素结点的位置在进行插入
在指定位置后插入要考虑以下情况

  • 空链表
    不需要做处理 因为空链表找不到指定的位置
  • 指定位置不存在
    错误处理
  • 其他情况下插入

image.png
这里不用考虑插入的位置是最后一个结点的位置，这样首先要遍历链表进行判断，在复用尾插，代价太大。

代码实现：

void SLTInsertAfter( SLTNode* pos, ElemType x)
{
	assert(pos);
	//申请新结点
	SLTNode* newnode = NewSLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

删除指定位置元素

删除指定位置和插入指定位置一样，需要先查找到该元素结点的位置
比如链表元素 1 2 3 4 删除2的位置链表变为 1 3 4
删除pos位置要考虑以下情况

  • 空链表
    不需要做处理 因为空链表找不到指定的位置
  • 指定位置不存在
    错误处理
  • 指定位置是第一个结点
    复用头删
  • 其他情况下删除指定位置

image.png
代码实现：

void SLTErase(SLTNode** phead, SLTNode* pos)
{
       //空链表
	assert(*phead);
	// 指定位置不存在
	assert(pos); 
	//复用头删
	if (pos == *phead)
	{
		SLTPopFront(phead);
	}
	else
	{
		//找pos前一个
		SLTNode* cur = *phead;
		SLTNode* prevpos = NULL;
		while (cur != pos)
		{
			prevpos = cur;
			cur = cur->next;
		}
		prevpos->next = pos->next;
		free(pos);
	}
}

删除指定位置之后的元素

比如链表元素 1 2 3 4 删除2之后位置 链表变为 1 2 4
删除指定位置之后的元素分别要考虑以下情况

  • 空链表
    不需要做处理 因为空链表找不到指定的位置
  • 指定位置不存在
    错误处理
  • 是否是尾结点
    错误处理
  • 其他情况下删除指定位置之后

image.png
代码实现：

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLTNode* posnesxt = pos->next;
	pos->next = posnesxt->next;
	free(posnesxt);
	posnesxt = NULL;
}

顺序输出链表

void SLTNodePrintf(SLTNode* phead)
{
	SLTNode* tail = phead;
	while (tail != NULL)
	{
		printf("%d " , tail->data);
		tail = tail->next;
	}
	printf("\n");
}

销毁单链表

void SLTNodeDestory(SLTNode** phead)
{
	assert(*phead);
	SLTNode* cur = *phead;
	SLTNode* curnext = NULL;
	while (cur != NULL)
	{
		curnext = cur->next;
		free(cur);
		cur = curnext;
	}
}

顺序表和单链表的区别

不同点顺序表链表
存储空间上物理上一定连续逻辑上连续，物理上不一定连续
随机访问O(1)O(n)
任意位置插入或删除可能需要挪动数据，效率太低O(n)只需要修改指针指向即可
插入元素动态顺序表，空间不够时需要扩容没有容量概念，用多少申请多少
应用场景元素高效存储+频繁访问频繁在任意位置插入和删除

关于指针传参

当你传递一个参数给函数的时候，这个参数会不会在函数内被改动决定了函数参数形式

  • 如果需要改动，则需要传指向这个参数的指针
    比如单链表的头插，尾插、头删等，都需要改变头指针的指向位置，也就是这个参数需要被改动，那么传这个参数的指针
  • 如果不用被改动，可以直接传递这个参数
    比如单链表中的查找和打印，直接传参数就可以了，查找和打印，不用修改里面的内容

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

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

相关文章

随手写了个博客多平台发布脚本：Python自动发布文章到Wordpress

随手写了个博客多平台发布脚本：Python自动发布文章到Wordpress

​ 引言 作为一名技术博主，提高博客发布效率是我们始终追求的目标。在这篇文章中，我将分享一个基于Python的脚本，能够实现博客多平台发布，具体来说，是自动发布文章到WordPress。通过这个简单而高效的脚本&#xff0c…
阅读更多...
Android 单元测试初体验(二)-断言

Android 单元测试初体验(二)-断言

[TOC](Android 单元测试初体验(二)-断言) 前言 当初在学校学安卓的时候，老师敢教学进度，翻到单元测试这一章节的时候提了两句，没有把单元测试当重点讲，只是说我们工作中几乎不会用到，果真在之前的几年工作当中我真的没…
阅读更多...
人工智能与供应链行业融合：预测算法的通用化与实战化

人工智能与供应链行业融合：预测算法的通用化与实战化

前言 「作者主页」：雪碧有白泡泡 「个人网站」：雪碧的个人网站 让我们一起深入探索人工智能与供应链的融合，以及预测算法在实际应用中的价值！🔍🚀 文章目录 前言供应链预测算法的基本流程统计学习模型与机…
阅读更多...
Gitea和Jenkins安装

Gitea和Jenkins安装

Gitea Gitea：https://dl.gitea.com/gitea/1.21.0/ Jenkins：https://www.jenkins.io/download/ 数据库配置 可以参考官方文档-https://docs.gitea.cn/1.20/installation/database-prep，这里以MySQL作为讲解 MySQL 在数据库实例上&#xf…
阅读更多...
LeetCode-面试题08.01 三步问题 C/C++实现 超详细思路及过程[E]

LeetCode-面试题08.01 三步问题 C/C++实现 超详细思路及过程[E]

🎈归属专栏：深夜咖啡配算法 🚗个人主页：Jammingpro 🐟记录一句：摆了一个周末了，不能摆了，努力起来！！ 文章目录 LeetCode-面试题08.01 三步问题🚗题…
阅读更多...
SpringBoot : ch08 自动配置原理

SpringBoot : ch08 自动配置原理

前言 在现代的Java开发中，Spring Boot已经成为了一个备受欢迎的框架。它以其简化开发流程、提高效率和强大的功能而闻名，使得开发人员能够更加专注于业务逻辑的实现而不必过多地关注配置问题。 然而，你是否曾经好奇过Spring Boot是如何做到…
阅读更多...
C++11线程以及线程同步

C++11线程以及线程同步

C11中提供的线程类std::thread,基于此类创建一个新的线程相对简单，只需要提供线程函数和线程对象即可 一.命名空间 this_thread C11 添加一个关于线程的命名空间std::this_pthread ,此命名空间中提供四个公共的成员函数； 1.1 get_id() 调用命名空间s…
阅读更多...
识别验证码

识别验证码

背景 需求是要爬取某网站的数据, 已有账号密码, 但这个网站需要登录, 登录需要输入验证码 验证码样式如下 调研了Tesseract框架, 识别效果不佳. 后来使用ddddocr, 能正确识别. https://github.com/sml2h3/ddddocr 代码如下 def ocr():response requests.get(http://xxx/get…
阅读更多...
【JavaScript】封装自己的JavaScript公共工具函数，并上传到npm中 进行下载

【JavaScript】封装自己的JavaScript公共工具函数，并上传到npm中 进行下载

js公共方法封装方式都有哪些 全局函数 function greet(name) {console.log("Hello, " name "!"); }greet("Alice"); // 调用全局函数对象字面量 var utils {add: function(a, b) {return a b;},subtract: function(a, b) {return a - b;}…
阅读更多...
使用opencv实现图片相似度检测

使用opencv实现图片相似度检测

1.为什么学这个,我对图像处理非常感兴趣,我联想到海尔的指纹识别门锁是如何进行检测的,我在想不应该呀,单片机性能这么差,应该是使用了训练后的数据去检测图片的,如果我要实现草莓检测,知道它是不是草莓,我觉得单纯使用图片处理是不够的,我考虑过使用指纹模块来接触草莓从而实现…
阅读更多...
芯片制程中温度的几种表示方法

芯片制程中温度的几种表示方法

在众多影响芯片制程的因素中，温度控制被视为一项至关重要的技术。温度是比较一种物质相对于另一种物质是冷还是热的衡量标准，它会影响到芯片的性能、可靠性以及最终产量。在不同的制程步骤中，温度扮演着各种各样的角色。但是在评价制程温度高…
阅读更多...
振弦式轴力计和振弦采集仪组成的安全监测解决方案

振弦式轴力计和振弦采集仪组成的安全监测解决方案

振弦式轴力计和振弦采集仪组成的安全监测解决方案 振弦式轴力计和振弦采集仪是一种常用的结构安全监测工具，可以用于评估建筑物、桥梁、隧道或其他结构的结构健康状态和安全性能。这种监测方案较为先进、精确，并且能够监测长期的结构反应，因此…
阅读更多...
Git指定分支或文件回退到指定版本

Git指定分支或文件回退到指定版本

文章目录 一、分支回滚1.1、使用 git reset 命令1.2、使用 git revert 命令1.3、使用 git checkout 命令 二、文件回滚2.1、回滚未提交文件2.2、回滚已提交文件2.2.1、首先查看文件的历史版本2.2.2、找到你想要还原的版本2.2.3、将文件还原到你想要还原的版本2.2.4、提交代码 三…
阅读更多...
便利高效双赢：无人机油气管道巡检全面升级

便利高效双赢：无人机油气管道巡检全面升级

我国庞大的油气管道网络，包括原油、成品和天然气管道，因为地理区域广泛、建设年代久远、安全事故频发等现实因素，对管道的安全巡护与管理提出了更高的需求。在这一背景下，传统的人工巡护方式显然已经难以满足对高、精、准的要求。…
阅读更多...
s_v_web_id或fp协议过签名，dy滑块

s_v_web_id或fp协议过签名，dy滑块

某音s_web_id或fp协议过签名 ‘h5_sdk_version’, ‘2.36.0’ "search_impr":{"entity_id":"1135137973613200"},"link_item_list":null,"user_permissions":null,"offline_info_list":null,"is_cf":…
阅读更多...
计算机组成原理-页式存储器

计算机组成原理-页式存储器

文章目录 页式存储虚拟地址vs实地址页表：逻辑页->主存块号地址交换过程地址交换过程（增加TLB）总结 页式存储 把程序分散式地放到主存的不同块的地方 虚拟地址vs实地址 操作系统将逻辑地址映射到主存块中的物理地址，对应的物…
阅读更多...
新疆大学与优艾智合机器人成立联合创新实验室

新疆大学与优艾智合机器人成立联合创新实验室

11月22日至24日，第五届中国工业互联网大赛新疆赛站决赛在新疆维吾尔自治区昌吉回族自治州昌吉市举行。在大赛中崭露头角的优秀解决方案，将为绿色工厂、绿色园区、绿色供应链等建设提供新的动能，促进工业绿色发展。 作为大赛的成果延伸&#…
阅读更多...
unity UGUI中获取点击位置处的URL链接

unity UGUI中获取点击位置处的URL链接

需求是&#xff0c;我们在一个text组件中像写网页那样写入链接&#xff0c;然后点击这个链接&#xff0c;就能访问配置的网页啥的。比如&#xff1a; <a href"hello">链接文本</a></summary> 最终的效果如下&#xff1a; 图中&#xff0c;image区…
阅读更多...
智能优化算法应用：基于蜻蜓算法无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用：基于蜻蜓算法无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于蜻蜓算法无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于蜻蜓算法无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.蜻蜓算法4.实验参数设定5.算法结果6.参考文献7.MATLAB…
阅读更多...
Docker Compose；docker-compose；docker compose

Docker Compose；docker-compose；docker compose

(一) Docker Compose | 菜鸟教程 --> --> --> -->
阅读更多...
最新文章

Copyright @ 2022~2023