初阶数据结构(四)带头双向链表
💓博主csdn个人主页:小小unicorn
⏩专栏分类:数据结构
🚚代码仓库:小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识
带头双向链表
- 链表的相关介绍
- 初始化链表
- 销毁链表
- 打印双向链表
- 查找元素
- 增加节点
- 头插
- 尾插
- 在指定位置插入
- 删除节点
- 头删
- 尾删
- 在指定位置删除
- 链表判空
- 获取链表元素
链表的相关介绍
在之前链表的学习中,我们知道:
链表的结构一共有八种:带头单向循环链表、带头单向非循环链表、带头双向循环链表、带头双向非循环链表、无头单向循环链表、无头单向非循环链表、无头双向循环链表、无头双向非循环链表。
然而在这八种结构中,我们只挑两种来进行刨析,即无头单向非循环链表和带头双向循环链表。
不带头单向非循环链表:结构简单,一般不会用来存储数据。实际上更多是作为其他数据结构的子结构,如哈希桶、图的链接表等等。此外,这种结构在笔试面试中出现很多。
带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外,这个结构虽然复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了。
初始化链表
首先,我们还是需要先定义一个结点类型,与单向链表相比,双向链表的结点类型中需要多出一个前驱指针,用于指向前面一个结点,实现双向。
typedef int LTDataType;//存储的数据类型typedef struct ListNode
{LTDataType data;//数据域struct ListNode* prev;//前驱指针struct ListNode* next;//后继指针
}ListNode;
然后我们需要一个初始化函数,对双向链表进行初始化,在初始化的过程中,需要申请一个头结点,头结点的前驱和后继指针都指向自己,使得链表一开始便满足循环。
//创建一个新结点
ListNode* BuyListNode(LTDataType x)
{ListNode* node = (ListNode*)malloc(sizeof(ListNode));if (node == NULL){printf("malloc fail\n");exit(-1);}node->data = x;//新结点赋值node->prev = NULL;node->next = NULL;return node;//返回新结点
}//初始化链表
ListNode* ListInit()
{ListNode* phead = BuyListNode(-1);//申请一个头结点,头结点不存储有效数据//起始时只有头结点,让它的前驱和后继都指向自己phead->prev = phead;phead->next = phead;return phead;//返回头结点
}
销毁链表
销毁链表,从头结点的后一个结点处开始向后遍历并释放结点,直到遍历到头结点时,停止遍历并将头结点也释放掉。
//销毁链表
void ListDestroy(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;//从头结点后一个结点开始释放空间ListNode* next = cur->next;//记录cur的后一个结点位置while (cur != phead){free(cur);cur = next;next = next->next;}free(phead);//释放头结点
}
打印双向链表
打印双向链表时也是从头结点的后一个结点处开始向后遍历并打印,直到遍历到头结点处时便停止遍历和打印(头结点数据不打印)。
//打印双向链表
void ListPrint(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;//从头结点的后一个结点开始打印while (cur != phead)//当cur指针指向头结点时,说明链表以打印完毕{printf("%d ", cur->data);cur = cur->next;}printf("\n");
}
查找元素
给定一个值,在链表中寻找与该值相同的结点,若找到了,则返回结点地址;若没有找到,则返回空指针(NULL)。
//查找元素
ListNode* ListFind(ListNode* phead, LTDataType x)
{assert(phead);ListNode* cur = phead->next;//从头结点的后一个结点开始查找while (cur != phead)//当cur指向头结点时,说明链表已遍历完毕{if (cur->data == x){return cur;//返回目标结点的地址}cur = cur->next;}return NULL;//没有找到目标结点
}
增加节点
头插
头插,即申请一个新结点,将新结点插入在头结点和头结点的后一个结点之间即可。
//头插
void ListPushFront(ListNode* phead, LTDataType x)
{assert(phead);ListNode* newnode = BuyListNode(x);//申请一个结点,数据域赋值为xListNode* front = phead->next;//记录头结点的后一个结点位置//建立新结点与头结点之间的双向关系phead->next = newnode;newnode->prev = phead;//建立新结点与front结点之间的双向关系newnode->next = front;front->prev = newnode;
}
尾插
尾插,申请一个新结点,将新结点插入到头结点和头结点的前一个结点之间即可。因为链表是循环的,头结点的前驱指针直接指向最后一个结点,所以我们不必遍历链表找尾。
//尾插
void ListPushBack(ListNode* phead, LTDataType x)
{assert(phead);ListNode* newnode = BuyListNode(x);//申请一个结点,数据域赋值为xListNode* tail = phead->prev;//记录头结点的前一个结点的位置//建立新结点与头结点之间的双向关系newnode->next = phead;phead->prev = newnode;//建立新结点与tail结点之间的双向关系tail->next = newnode;newnode->prev = tail;
}
在指定位置插入
在直到位置插入结点,准确来说,是在指定位置之前插入一个结点。我们只需申请一个新结点插入到指定位置结点和其前一个结点之间即可。
//在指定位置插入结点
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* before = pos->prev;//记录pos指向结点的前一个结点ListNode* newnode = BuyListNode(x);//申请一个结点,数据域赋值为x//建立新结点与before结点之间的双向关系before->next = newnode;newnode->prev = before;//建立新结点与pos指向结点之间的双向关系newnode->next = pos;pos->prev = newnode;
}
删除节点
头删
头删,即释放头结点的后一个结点,并建立头结点与被删除结点的后一个结点之间的双向关系即可。
//头删
void ListPopFront(ListNode* phead)
{assert(phead);assert(phead->next != phead);ListNode* front = phead->next;//记录头结点的后一个结点ListNode* newfront = front->next;//记录front结点的后一个结点//建立头结点与newfront结点之间的双向关系phead->next = newfront;newfront->prev = phead;free(front);//释放front结点
}
尾删
尾删,即释放最后一个结点,并建立头结点和被删除结点的前一个结点之间的双向关系即可。
//尾删
void ListPopBack(ListNode* phead)
{assert(phead);assert(phead->next != phead);ListNode* tail = phead->prev;//记录头结点的前一个结点ListNode* newtail = tail->prev;//记录tail结点的前一个结点//建立头结点与newtail结点之间的双向关系newtail->next = phead;phead->prev = newtail;free(tail);//释放tail结点
}
在指定位置删除
删除指定位置结点,释放掉目标结点后,建立该结点前一个结点和后一个结点之间的双向关系即可。
//删除指定位置结点
void ListErase(ListNode* pos)
{assert(pos);ListNode* before = pos->prev;//记录pos指向结点的前一个结点ListNode* after = pos->next;//记录pos指向结点的后一个结点//建立before结点与after结点之间的双向关系before->next = after;after->prev = before;free(pos);//释放pos指向的结点
}
链表判空
链表判空,即判断头结点的前驱或是后驱指向的是否是自己即可。
//链表判空
bool ListEmpty(ListNode* phead)
{assert(phead);return phead->next == phead;//当链表中只有头结点时为空
}
获取链表元素
获取链表中的元素个数,即遍历一遍链表,统计结点的个数(头结点不计入)并返回即可。
//获取链表中的元素个数
int ListSize(ListNode* phead)
{assert(phead);int count = 0;//记录元素个数ListNode* cur = phead->next;//从头结点的后一个结点开始遍历while (cur != phead)//当cur指向头结点时,遍历完毕,头结点不计入总元素个数{count++;cur = cur->next;}return count;//返回元素个数
}
相关文章:

初阶数据结构(四)带头双向链表
💓博主csdn个人主页:小小unicorn ⏩专栏分类:数据结构 🚚代码仓库:小小unicorn的代码仓库🚚 🌹🌹🌹关注我带你学习编程知识 带头双向链表 链表的相关介绍初始化链表销毁链…...

2022年9月及10月
9月 1.Halcon12的HObject和Hobject halcon12 可以用HObject,也可以用Hobject,用法都一样 包括HalconCpp.h 如果附加目录中: C:\Program Files\MVTec\HALCON-12.0\include\halconcpp\ 在前面,则用 HalconCpp::HObject 如果附加目录…...
Vmware安装
title: “Vmware安装” createTime: 2021-11-22T09:53:2908:00 updateTime: 2021-11-22T09:53:2908:00 draft: false author: “name” tags: [“VMware”,“安装”,“linux”] categories: [“install”] description: “测试的” linux安装VMware Workstation16 1.安装包 …...
RSA算法
算法简介 RSA是一种非对称加密方式。发送者把明文通过公钥加密后发送出去,接受者把密文通过私钥解密得到明文。 算法过程 生成公钥和私钥 选取两个质数p和q,np*q。n的长度就是密钥长度。φ(n)(p-1)*(q-1)φ(n)为n的欧拉函数。找到1-φ(n)间与φ(n)互质的…...

计算机竞赛 深度学习手势识别 - yolo python opencv cnn 机器视觉
文章目录 0 前言1 课题背景2 卷积神经网络2.1卷积层2.2 池化层2.3 激活函数2.4 全连接层2.5 使用tensorflow中keras模块实现卷积神经网络 3 YOLOV53.1 网络架构图3.2 输入端3.3 基准网络3.4 Neck网络3.5 Head输出层 4 数据集准备4.1 数据标注简介4.2 数据保存 5 模型训练5.1 修…...
Spring的Ordered
Ordered Java中的Ordered接口是Spring框架中的一个接口,用于表示对象的顺序。它定义了一个方法getOrder(),用于获取对象的顺序值,值越小的对象越先被处理。 Ordered接口是Spring框架中的一个接口,用于定义组件的加载顺序。当一个…...

前端两年半,CSDN创作一周年
文章目录 一、机缘巧合1.1、起因1.2、万事开头难1.3、 何以坚持? 二、收获三、日常四、憧憬 五、总结 一、机缘巧合 1.1、起因 最开始接触CSDN,还是因为同专业的同学,将计算机实验课的实验题,记录总结并发在了专业群里。后来正式…...

定时任务管理平台青龙 QingLong
一、关于 QingLong 1.1 QingLong 介绍 青龙面板是支持 Python3、JavaScript、Shell、Typescript 多语言的定时任务管理平台,支持在线管理脚本和日志等。其功能丰富,能够满足大部分需求场景,值得一试。 主要功能 支持多种脚本语言…...

java多线程相关介绍
1. 线程的创建和启动 在 Java 中创建线程有两种方式。一种是继承 Thread 类并重写其中的 run() 方法,另一种是实现 Runnable 接口并重写其中的 run() 方法。创建完线程对象后,调用 start() 方法可以启动线程。 2. 线程的状态 Java 的线程在不同阶段会处于…...

css复合选择器
交集选择器 紧紧挨着 <template><div><p class"btn">Click me</p><button class"btn" ref"myButton" click"handleClick">Click me</button></div> </template> <style> but…...

USART串口协议
通信接口 •通信的目的:将一个设备的数据传送到另一个设备,扩展硬件系统 • 通信协议:制定通信的规则,通信双方按照协议规则进行数据收发 全双工:指通信双方能够同时进行双向通信,一般来说,全双…...

picoctf_2018_shellcode
picoctf_2018_shellcode Arch: i386-32-little RELRO: Partial RELRO Stack: No canary found NX: NX disabled PIE: No PIE (0x8048000) RWX: Has RWX segments32位,啥都没开 这个看着挺大的,直接来个ROPchain,…...

Apache Derby的使用
Apache Derby是关系型数据库,可以嵌入式方式运行,也可以独立运行,当使用嵌入式方式运行时常用于单元测试,本篇我们就使用单元测试来探索Apache Derby的使用 一、使用IDEA创建Maven项目 打开IDEA创建Maven项目,这里我…...
leetcode 图相关的题
图 图相关知识有leetcode207课程表1(有环判断)以及210 课程表2(拓扑排序). 链表遍历 def dfs(n):print(n)dfs(n)二叉树遍历 def dfs(n):print(n)dfs(n.left)dfs(n.right)多叉树遍历 dfs(root) def dfs(n):for node in n.nodes:dfs(node)图遍历 visited [False] * n_node…...

程序员们,我们能工作到65岁吗?
软件开发人员的职业生涯可以持续多久?这是大多数认真考虑成为专业程序员的人不禁想知道的事情。 在谈论这样一个要求很高的职业时,这是一个非常自然的问题。没有人愿意花费数年时间学习一项技能,这些技能将在几年内不再相关,或者当…...
【洛谷 P1996】约瑟夫问题 题解(队列+模拟+循环)
约瑟夫问题 题目描述 n n n 个人围成一圈,从第一个人开始报数,数到 m m m 的人出列,再由下一个人重新从 1 1 1 开始报数,数到 m m m 的人再出圈,依次类推,直到所有的人都出圈,请输出依次出圈人的编号。…...

字符串函数与内存函数讲解
文章目录 前言一、字符串函数1.求字符串长度strlen 2.长度不受限制的字符串函数(1)strcpy(2)strcat(3)strcmp 3.长度受限制的字符串函数(1)strncpy(2)strncat(3)strncmp 4.字符串查找(1)strstr(2)strtok 5.错误信息报告(1)strerror(2)perror 二、内存函数1.memcpy2.memmove3.me…...

c语言系统编程之多进程
程序与进程的区别? 程序是静态的未运行的二进制文件,存储在磁盘中 进程是已经运行的二进制文件,存储在内存中 进程的内存划分图有哪几部分? 堆(存储malloc和calloc出来的空间)、栈(局部变量…...
前端还是后端:探讨Web开发的两大街区
前端还是后端:探讨Web开发的两大街区 一、引言二、两者的对比分析技能要求和专业知识职责和工作内容项目类型和应用领域就业前景和市场需求 三、技能转换和跨领域工作四、全栈开发结语 一、引言 Web开发领域涉及到前端开发和后端开发这两个不同而又互为补充的领域。…...

JavaScript中如何确定this的值?如何指定this的值?
🎀JavaScript中的this 在绝大多数情况下,函数的调用方法决定了this的值(运行时绑定)。this不能在执行期间被赋值,并且在每次函数呗调用时this的值也可能会不同。 🍿如何确定this的值: 在非严格…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
云计算——弹性云计算器(ECS)
弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...

2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...

ios苹果系统,js 滑动屏幕、锚定无效
现象:window.addEventListener监听touch无效,划不动屏幕,但是代码逻辑都有执行到。 scrollIntoView也无效。 原因:这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作,从而会影响…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...