数据结构学习笔记——链式表示中的双链表及循环单/双链表
一、双链表
(一)双链表的定义
双链表是在单链表结点上增添了一个指针域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 …...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...
【Go语言基础【13】】函数、闭包、方法
文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数(函数作为参数、返回值) 三、匿名函数与闭包1. 匿名函数(Lambda函…...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...

【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

恶补电源:1.电桥
一、元器件的选择 搜索并选择电桥,再multisim中选择FWB,就有各种型号的电桥: 电桥是用来干嘛的呢? 它是一个由四个二极管搭成的“桥梁”形状的电路,用来把交流电(AC)变成直流电(DC)。…...

ui框架-文件列表展示
ui框架-文件列表展示 介绍 UI框架的文件列表展示组件,可以展示文件夹,支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项,适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...
二维FDTD算法仿真
二维FDTD算法仿真,并带完全匹配层,输入波形为高斯波、平面波 FDTD_二维/FDTD.zip , 6075 FDTD_二维/FDTD_31.m , 1029 FDTD_二维/FDTD_32.m , 2806 FDTD_二维/FDTD_33.m , 3782 FDTD_二维/FDTD_34.m , 4182 FDTD_二维/FDTD_35.m , 4793...

门静脉高压——表现
一、门静脉高压表现 00:01 1. 门静脉构成 00:13 组成结构:由肠系膜上静脉和脾静脉汇合构成,是肝脏血液供应的主要来源。淤血后果:门静脉淤血会同时导致脾静脉和肠系膜上静脉淤血,引发后续系列症状。 2. 脾大和脾功能亢进 00:46 …...