数据结构学习笔记——链式表示中的双链表及循环单/双链表
一、双链表
(一)双链表的定义
双链表是在单链表结点上增添了一个指针域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);
相关文章:

数据结构学习笔记——链式表示中的双链表及循环单/双链表
一、双链表 (一)双链表的定义 双链表是在单链表结点上增添了一个指针域prior,指针域prior指向当前结点的前驱结点,即此时链表的每个结点中都有两个指针域prior和next,从而可以很容易通过后继结点找到前驱结点&#x…...

DC电源模块去除输出电源中的高频噪声及杂波
BOSHIDA DC电源模块去除输出电源中的高频噪声及杂波 DC电源模块是电路中常用的部件,用于提供电子元器件的工作电源。然而,在使用DC电源模块的过程中,往往会出现一些问题,比如输出电源中产生的高频噪声和杂波。这些问题不仅会影响…...

【驱动开发】注册字符设备使用gpio设备树节点控制led三盏灯的亮灭
注册字符设备使用gpio设备树节点控制led三盏灯的亮灭 设备树: 头文件: #ifndef __HEAD_H__ #define __HEAD_H__ typedef struct {unsigned int MODER;unsigned int OTYPER;unsigned int OSPEEDR;unsigned int PUPDR;unsigned int IDR;unsigned int OD…...

面向制造企业的持续发展,2023数字化工单管理系统创新篇章-亿发
面向制造企业的持续发展,2023数字化工单管理系统开创新篇章-亿发 随着制造业的持续发展,运维工单管理日益成为关键环节,它设计客户管理、设备维护、服务商合作等多个业务领域,对运营效率和服务质量有着重要影响。然而,…...
mysql 元数据锁 MDL读锁与MDL写锁
事务一开启事务 begin; select * from tablename;--相当于加了MDL读锁 此时事务2执行alter table tablename add ... --会发生修改阻塞 commit; --提交事务 释放MDL读锁 此时事务二修改成功 如果事务一执行做dml操作,操作期间将加MDL写锁...

批量预处理哨兵2影像
批量预处理哨兵2影像 最近下载70多景哨兵2影像,平均每个影像在cmd中处理时间都需要半个小时。算下来我一景一景手动处理需要37个小时左右,每天在电脑前待8个小时也要4天多,很浪费时间。如果能够批处理,不需要我手动做的话&#x…...

Unity地面交互效果——2、动态法线贴图实现轨迹效果
Unity引擎动态法线贴图制作球滚动轨迹 大家好,我是阿赵。 之前说了一个使用局部UV采样来实现轨迹的方法。这一篇在之前的基础上,使用法线贴图进行凹凸轨迹的绘制。 一、实现的目标 先来回顾一下,上一篇最终我们已经绘制了一个轨迹的贴图…...

视频剪辑达人教您:如何运用嵌套合并技巧制作固定片尾
在视频剪辑的过程中,嵌套合并技巧是一种非常实用的技术,可以帮助您将多个素材叠加在一起,制作出更加丰富多彩的视频。本文将由视频剪辑达人为您详细介绍如何运用云炫AI智剪嵌套合并技巧制作固定片尾,让您的视频剪辑水平更上一层楼…...

【腾讯云 TDSQL-C Serverless 产品体验】TDSQL-C MySQL Serverless最佳实践
一、引言: 随着云计算技术的不断发展,越来越多的企业开始选择将自己的数据库部署在云上,以更好了的支持企业数字化转型以及业务创新,在这个过程中,很多客户会遇到这样一个问题,业务会存在高峰期和低谷期&a…...

SQLyog连接数据库报plugin caching_sha2_password could not be loaded......解决方案
问题描述 问题分析 因为MySQL新版默认使用caching_sha2_password作为身份验证的插件,而旧版本使用的是mysql_native_password。当出现plugin caching_sha2_password could not be loaded报错,我们更换为旧版本 如何解决 先使用cmd命令登录MySQL&a…...
linux应急排查
常用命令 查看登录用户和活动 whoami:显示当前登录用户的用户名。 w:显示当前登录到系统上的用户列表和他们正在执行的命令。 last:显示最近登录到系统的用户列表、登录时间和来源IP地址。 ps aux:列出当前正在运行的所有进程&…...
Apache POI及easyExcel读取及写入excel文件
目录 1.excel 2.使用场景 3.Apache POI 4.easyExcel 5.总结 1.excel excel分为两版,03版和07版。 03版的后缀为xls,最大有65536行。 07版的后缀为xlsx,最大行数没有限制。 2.使用场景 将用户信息导出到excel表格中。 将excel中的数…...
为什么写作
1记录生活,表达自己的想法和情感,提高沟通能力。 2年轻的时候就有写作的意愿,一直未动笔。 3想突破自己看看自己能写到什么程度。锻炼自己更好组织思路,提高逻辑思维能力。 4给自己的生活增添一些爱好,更好地理解和…...

python基于VGG19实现图像风格迁移
目录 1、原理 2、代码实现 1、原理 图像风格迁移是一种将一张图片的内容与另一张图片的风格进行合成的技术。 风格(style)是指图像中不同空间尺度的纹理、颜色和视觉图案,内容(content)是指图像的高级宏观结构。 实…...

BoredHackerBlog: Cloud AV RT日记
目录 信息搜集 WEB漏洞攻击 拿shell 信息搜集 首先ifconfig查看自己IP, netdiscover查看同网段下主机 第三个应该是目标靶机。用nmap查看靶机开放端口: 开放22和8080,看看8080开的啥服务 WEB漏洞攻击 看到让我们输入邀请码。有输入框的第…...

数据结构之“初窥门径”
目录 前言: 一,数据结构起源 二,基本概念和术语 2.1数据 2.2数据元素 2.3数据项 2.4数据对象 2.5数据结构 三,逻辑结构与物理结构 3.1逻辑结构 3.1.1集合结构 3.1.2线性结构 3.1.3树形结构 3.1.4图形结构 3.2物理结…...

css:transform实现平移、旋转、缩放、倾斜元素
目录 文档语法示例旋转元素 transform-rotate旋转过渡旋转动画 参考文章 文档 https://developer.mozilla.org/zh-CN/docs/Web/CSS/transform 语法 /* Keyword values */ transform: none;/* Function values */ transform: matrix(1, 2, 3, 4, 5, 6); transform: translate…...
如何理解AutoGPT
AutoGPT和GPT-4都是OpenAI公司的产品。AutoGPT是一个实验性开源应用程序,展示了GPT-4语言模型的能力。GPT-4是OpenAI研发的人工智能语言模型。 AutoGPT在GitHub主页上有151k星(151k星代表了151,000个用户点赞了该项目),AutoGPT获…...

【网络知识必知必会】聊聊网络层IP协议
文章目录 前言IP 协议格式总结 前言 在之前的博文中, 我们聊过了传输层中的两个重点协议 TCP 和 UDP, 本文我们再来聊聊网络层中的一个协议IP, 简单认识一下 IP 协议格式. IP 协议与 TCP 协议的复杂度也不妨多让, 不过我们在这里只是简单的聊一聊 IP 协议的报文格式就行, 毕竟…...
66. 加一
给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一。 最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外,这个整数不会以零开头。 示例 1: 输入: digits …...

React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...

tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...

计算机基础知识解析:从应用到架构的全面拆解
目录 前言 1、 计算机的应用领域:无处不在的数字助手 2、 计算机的进化史:从算盘到量子计算 3、计算机的分类:不止 “台式机和笔记本” 4、计算机的组件:硬件与软件的协同 4.1 硬件:五大核心部件 4.2 软件&#…...
云原生周刊:k0s 成为 CNCF 沙箱项目
开源项目推荐 HAMi HAMi(原名 k8s‑vGPU‑scheduler)是一款 CNCF Sandbox 级别的开源 K8s 中间件,通过虚拟化 GPU/NPU 等异构设备并支持内存、计算核心时间片隔离及共享调度,为容器提供统一接口,实现细粒度资源配额…...
【安全篇】金刚不坏之身:整合 Spring Security + JWT 实现无状态认证与授权
摘要 本文是《Spring Boot 实战派》系列的第四篇。我们将直面所有 Web 应用都无法回避的核心问题:安全。文章将详细阐述认证(Authentication) 与授权(Authorization的核心概念,对比传统 Session-Cookie 与现代 JWT(JS…...

Spring AOP代理对象生成原理
代理对象生成的关键类是【AnnotationAwareAspectJAutoProxyCreator】,这个类继承了【BeanPostProcessor】是一个后置处理器 在bean对象生命周期中初始化时执行【org.springframework.beans.factory.config.BeanPostProcessor#postProcessAfterInitialization】方法时…...