数据结构学习笔记——链式表示中的双链表及循环单/双链表

一、双链表

(一)双链表的定义

双链表是在单链表结点上增添了一个指针域prior,指针域prior指向当前结点的前驱结点,即此时链表的每个结点中都有两个指针域prior和next,从而可以很容易通过后继结点找到前驱结点,故访问前驱和后继结点的时间复杂度都为O(1)
在这里插入图片描述

(二)双链表的判空

一个带头结点L的双链表,若L->next==NULL时,则该双链表为空;一个不带头结点的双链表,若L==NULL时,则该双链表为空。

双链表判空条件
带头结点L->next==NULL
不带头结点L==NULL

(三)双链表的插入操作

  • 由于双链表可以很快地找到前驱结点,所以双链表的插入、删除操作的时间复杂度都为O(1)

双链表的插入操作可以概括为【先连后,后连前】,若在指针 *p 指向的结点之后插入结点 *q,首先,新结点q与原本 *p的指针域相连,即下一个结点,然后将结点q插入到结点p之后,再将其prior和next域相连,代码如下:

q->next=p->next;
p->next->prior=q;
q->prior=p;
p->next=q;

在这里插入图片描述

这里的代码插入不唯一,插入操作必须保证的是不能断链,即不能导致*p的后继结点的指针丢掉。

(四)双链表的删除操作

双链表的删除操作的代码如下:

p->next=q->next;
q->next->prior=p;
free(q);

在这里插入图片描述

二、循环单链表

(一)循环单链表的定义

循环单链表可以实现从任一个结点访问链表中的任何结点(遍历整个链表。
在这里插入图片描述

(二)循环单链表的判空

在带头结点L的循环单链表中,若L==head->next时,循环单链表为空;在不带头结点的循环单链表中,若L==NULL时,循环单链表为空。

循环单链表判空条件
带头结点L==head->next
不带头结点L==NULL

(三)循环单链表的查找

在一个带头结点的循环单链表中:
1、若只设置头指针L,则查找表头结点的时间复杂度为O(1),查找表尾结点需要依次遍历整个链表,即时间复杂度为O(n),而查找一个结点的前驱结点时的时间复杂度为O(n)。
2、若只设置尾指针R,这样的好处是可以使查找链表的开始结点和终端结点很方便,其查找时间都为O(1),而查找一个结点的前驱结点时的时间复杂度为O(n)。

(四)循环单链表的插入操作

循环单链表的插入操作与单链表类似,也是【先连后,再连前】,若在指针 *p 指向的结点后插入结点 *p ,步骤是:首先将q的指针域与p结点原本的指向下一个结点的指针域相连,即q->next=p->next,然后再将q结点与p结点相连,即p->next=q,如下:

q->next=p->next;	//先连后
p->next=q;		//再连前

在这里插入图片描述

(五)循环单链表的删除操作

循环单链表的删除操作也与单链表类似,删除的步骤可概括为【先定位,后断开释放】,将*q指针指向要删除的结点,p为其前驱结点,如下代码:

q=p->next;	//先定位,定位删除位置
p->next=q->next;	//断开q与p的连接,p与下一个结点连接
free(q);	//free()函数释放结点

在这里插入图片描述

三、循环双链表

(一)循环双链表的定义

循环双链表基于双链表,头结点L的prior域指向表尾结点,查找表头结点和表尾结点的时间复杂度均为O(1),查找一个结点的前驱结点时的时间复杂度也为O(1)。
在这里插入图片描述

(二)循环双链表的判空

一个带头结点L的循环双链表,若L->prior==L&&L->next==L时,则该双链表为空。(头结点的prior和next域都指向其本身时为空)

循环双链表判空条件
带头结点L->prior == L && L->next == L
不带头结点L==NULL

(三)循环双链表的插入操作

若要在指针 *p 指向的结点后插入结点 *p,其代码如下:

q->next=p->next;
p->next->prior=q;
q->prior=p;
p->next=q;

在这里插入图片描述

(四)循环双链表的删除操作

将*p指针指向要删除的结点,其代码如下:

p->next->prior=p->prior;
p->prior->next=p->next;
free(p);

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

视阅口译有何特点,哪里提供视阅口译翻译?

据了解,视阅口译是一种涉及视听和口头表达的翻译方式,它在跨文化交流等领域中起到了非常重要的作用。那么,视阅口译有何特点,哪里提供专业的视阅口译服务? 我们知道,视阅口译就是基于事先准备好的讲稿或文…

【HMS Core】机器学习服务热门问题合集

【关键词】 机器学习服务、文本识别、身份证识别 【问题描述1】 机器学习服务的文本识别能力,是否支持草书等? 【解决方案】 草书是不支持的,目前建议使用较为规范的字体测试。 【问题描述2】 机器学习服务是否支持训练模型?…

Docker 运行swagger-editor实现在线接口文档维护与调试

文章目录 一、序二, Docker部署准备1. 编辑docker-compose.yml2. 新增启动、停止脚本3. 样例 swagger.yaml 三, 启动swagger-editor1. 使用说明2. 完整代码备份 一、序 因工作需要,需要搭建python运行环境,项目中python基于flask…

spark

spark Spark可以将Hadoop集群中的应用在内存中的运行速度提升100倍,甚至能够将应用在磁盘上的运行速度提升10倍。除了Map和Reduce操作之外,Spark还支持SQL查询,流数据,机器学习和图表数据处理。开发者可以在一个数据管道用例中单独…

华锐技术何志东:证券核心交易系统分布式改造将迎来规模化落地阶段

近年来,数字化转型成为证券业发展的下一战略高地,根据 2021 年证券业协会专项调查结果显示,71% 的券商将数字化转型列为公司战略任务。 在落地数字化转型战略过程中,证券业核心交易系统面临着不少挑战。构建新一代分布式核心交易…

SpringMVC Day 06 : 转发视图

前言 在SpringMVC框架中,视图解析器可以将逻辑视图名称转换为实际的视图对象。除了直接渲染视图,你还可以通过SpringMVC提供的转发和重定向机制来跳转到另一个视图。在本篇博客中,我们将学习SpringMVC中的转发视图技术,以及如何使…

Android 10适配外部存储方案

Android Api 29 对文件和文件夹进行了重大更改。不允许使用外部存储,如下方法: Environment.getExternalStorageDirectory() /mnt/sdcard Environment.getExternalStoragePublicDirectory(“test”) /mnt/sdcard/test 只能使用内部存储 getExterna…

抖音小店怎么做?五步教你做好抖店,新手快来看!

我是电商珠珠 新手在做抖音小店的时候,往往在入驻完成之后,就不知道后续应该怎么操作了。 我将抖店的运营分为了五个步骤,可以供大家参考。 一、类目 开店之前选择好的类目,后续如果想要更改的话可以随时更改。 不过需要下架…

python函数的定义与调用

python定义函数和函数的使用 函数 函数是对程序逻辑进行结构化或过程化的一种编程方法,将整块代码巧妙地隔离成易于管理的小块。把重复代码放到函数中而不是进行大量的拷贝,这样既能节省空间,也有助于保持一致性;通常函数都是用…

metaRTC集成flutter ui demo编译指南

概要 Flutter是由Google开发的开源UI工具包,用于构建跨平台应用程序,支持linux/windows/mac/android/ios等操作系统。 metaRTC新增flutter demo,支持linux/windows/mac/android/ios操作系统,此demo在ubuntu桌面环境下测试成功。…

【文献分享】基于线特征的激光雷达和相机外参自动标定

论文题目:Line-based Automatic Extrinsic Calibration of LiDAR and Camera 中文题目:基于线特征的激光雷达和相机外参自动标定 作者:Xinyu Zhang, Shifan Zhu, Shichun Guo, Jun Li, and Huaping Liu 作者机构:清华大学汽车安…

SAML- 安全断言标记语言

一、概念 安全断言标记语言(SAML)是一种开放标准,用于在各方之间(特别是身份提供商和服务提供商之间)交换身份验证和授权数据。SAML 是一种基于XML的安全断言标记语言(服务提供商用来做出访问控制决策的语句…

Unity 多图片(带透明通道)合成

取个巧,利用Camera和Render Texture 多个2d图片组合成型 每个Square都单独设置一个层级 相机设置 RenderTexture设置,然后将RenderTexture放在一个RawImage上 以下是生成图片的代码 using UnityEngine.UI; using System.Collections; using System.…

【zTree】节点添加不同操作按钮,点击后生成弹窗

zTree api 文档:https://www.treejs.cn/v3/api.php 1. 初始化树的配置项 const initZtreeSetting () > {const setting {view: {addHoverDom: addHoverDom, // 显示用户自定义控件selectedMulti: false,// 是否允许同时选中多个节点,默认为truesh…

C++的拷贝构造函数

目录 拷贝构造函数一、为什么用拷贝构造二、拷贝构造函数1、概念2、特征1. 拷贝构造函数是构造函数的一个重载形式。2. 拷贝构造函数的参数3. 若未显式定义,编译器会生成默认的拷贝构造函数。4. 拷贝构造函数典型调用场景 拷贝构造函数 一、为什么用拷贝构造 日期…

C++设计模式_18_State 状态模式

State和Memento被归为“状态变化”模式。 文章目录 1. “状态变化”模式1.1 典型模式 2. 动机 (Motivation)3. 代码演示State 状态模式3.1 常规方式3.2 State 状态模式 4. 模式定义5. 结构( Structure )6. 要点总结7. 其他参考 1. “状态变化”模式 在组件构建过程中&#xf…

Redis——哨兵模式与Zookeeper选举的异同点

摘要 当我们使用主从复制出现的问题:手动故障转移:写能力和存储能力受限:主从复制 -master 宕机故障处理。 主从切换技术的方法是:当主服务器宕机后,需要手动把一台从服务器切换为主服务器,这就需要人工干…

军工工厂安全生产视频AI识别技术方案

一、需求分析 在国家政策、技术创新和企业发展需求转变等多个维度的共同驱动和协同下,特别是工业互联网作为“新基建”的提出,都在推动工业制造朝着数字化、网络化、智能化方向发展。军工装备制造行业承担着国民经济和国防建设的重要使命,构…

【uniapp】uview1.x使用upload上传图片

和2.x不同的是,要用 action 来配置后端上传图片的接口地址; 再来一些配置项的命名有所不同,一般1.x的命名用 -,2.x的命名使用小驼峰; 1.x 的上传会自带删除时的提示框,2.x 没有; 重要的几个配置…

银河集团香港优才计划95分获批案例展示!看看是如何申请的?

银河集团香港优才计划95分获批案例展示!看看是如何申请的? 今天来分享一则银河集团香港优才计划获批案例!客户本科学历非名校、从事业务支援及人力资源行业,优才打分95分,这个条件可能在很多人的印象里,会觉…