数据结构-带头双向循环链表
前言:
链表有很多种,上一章结,我复盘了单链表,这一章节,主要针对双链表的知识点进行,整理复盘,如果将链表分类的话,有很多种,我就学习的方向考察的重点,主要针对这两种链表进行整理。
带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了。带头双向循环链表如下图所示。
目录
1. 带头双向链表的实现
1.1封装链表节点结构体
1.2建立新的节点
1.3初始化链表
1.4尾插函数
1.5尾删
1.6头插
1.7头删
1.8显示
1.9销毁
1.10查找
1.11插入
1.12擦除
1.13判空
1. 带头双向链表的实现
1.1封装链表节点结构体
typedef int LDataType;typedef struct ListNode
{LDataType data;//自身数据struct ListNode* prev;指向前一个节点指针struct ListNode* next;指向后一个节点指针}LTNode;
1.2建立新的节点
链表的增删查改都会有新的节点,所以我们可以封装一个建立节点的函数,具体代码如下:
LTNode* BuyNode(LDataType x)
{LTNode* temp = (LTNode*)malloc(sizeof(LTNode));if (temp == NULL){perror("malloc:fail");exit(-1);}temp->data = x;temp->next = NULL;temp->prev = NULL;return temp;
}
1.3初始化链表
因为是带头节点,初始化会改变节点指向,如果按照单链表的操作习惯,我们可能穿指针变量的地址,用二级指针接收,但是也没必要,我们可以让函数返回的类型,为指针,具体代码如下:
LTNode* ListInit()
{LTNode* phead = BuyNode(-1);phead->next = phead;phead->prev = phead;return phead;
}
1.4尾插函数
因为头结点的prev指向tail,tail的next节点指向head所以我们只要改变节点指向就可以完成尾插,如图所示:
具体代码如下:
void PushBack(LTNode* pa, LDataType x)
{assert(pa);LTNode* newnode = BuyNode(x);LTNode* tail = pa->prev;tail->next = newnode;newnode->prev = tail;pa->prev = newnode;newnode->next = pa;}
1.5尾删
删掉最后一个节点,并改变节点指向
具体代码如下:
void PopBack(LTNode* pa)
{assert(pa);LTNode* tail = pa->prev;LTNode* middle = tail->prev;middle->next = pa;pa->prev = middle;free(tail);tail = NULL;}
1.6头插
代码如下:
void PushFront(LTNode* pa, LDataType x)
{assert(pa);LTNode* newnode = BuyNode(x);LTNode* middle = pa->next;newnode->next = middle;middle->prev = newnode;pa->next = newnode;newnode->prev = pa;
}
1.7头删
代码如下
void PopFront(LTNode* pa)
{assert(pa);LTNode* middle = pa->next;LTNode* cur = middle->next;pa->next = cur;cur->prev = pa;free(middle);middle = NULL;
}
1.8显示
增删查改之后,需要显示在终端,所以要有打印显示函数
void ListPrint(LTNode* pa)
{LTNode* cur = pa->next;while (cur != pa) {printf("%d<=>", cur->data);cur = cur->next;}printf("NULL\n");
}
1.9销毁
在堆上创建的空间,使用完成后,要返还给操作系统。
void ListDestroy(LTNode* pa)
{LTNode* cur = pa->next;LTNode* prev = NULL;while (cur != pa){LTNode* prev = cur;cur = cur->next;free(prev);}free(pa);pa->next = pa->prev = NULL;
}
1.10查找
查找指定数值得节点,当查找到的时候返回该数值得地址,如果没有查找到则返回空指针。
LTNode* ListFind(LTNode* pa, LDataType x)
{assert(pa);LTNode* cur = pa->next;while (cur != pa){if (cur->data != x){cur = cur->next;}else{return cur;}}return NULL;}
1.11插入
在当前节点的前一个位置插入节点
void ListInsert(LTNode* pa, LTNode* pos, LDataType x)
{assert(pa);assert(pos);LTNode* newnode = BuyNode(x);LTNode* prev = pos->prev;newnode->next = pos;pos->prev = newnode;prev->next = newnode;newnode->prev = prev;}
1.12擦除
将当前节点去除掉。
void ListErase(LTNode* pa, LTNode* pos)
{assert(pos);LTNode* prev = pos->prev;LTNode* next = pos->next;prev->next = next;next->prev = prev;free(pos);pos = NULL;}
1.13判空
如果头节点的下个指向为自己这个表达式为真的话,则返回true 否则返回false。
bool LTEmpty(LTNode* pa)
{return pa->next == pa;
}
相关文章:
数据结构-带头双向循环链表
前言: 链表有很多种,上一章结,我复盘了单链表,这一章节,主要针对双链表的知识点进行,整理复盘,如果将链表分类的话,有很多种,我就学习的方向考察的重点,主要…...
3 问 6 步,极狐GitLab 帮助企业构建高效、安全、合规的 DevSecOps 文化
本文来源:about.gitlab.com 作者:Vanessa Wegner 译者:极狐(GitLab) 市场部内容团队 🔒 安全为何重要?此前,我们分享了: 1. 2023年DevOps发展趋势👉重磅!GitLab 提出五大…...
SPA(单页应用)知多少
单页面应用程序将所有的活动局限于一个Web页面中,在该Web页面初始化时加载相应的HTML、JavaScript 和 CSS。一旦页面加载完成,单页面应用不会因为用户的操作而进行页面的重新加载或跳转。取而代之的是利用 JavaScript 动态的变换HTML的内容,从…...
Selenium实战【远程控制】【JAVA爬虫】
简介 Selenium RemoteWebDriver是Selenium WebDriver的一个扩展,它可以将测试运行在远程机器上的浏览器中。 使用RemoteWebDriver,可以在本地机器上编写测试脚本,然后将测试请求发送到远程机器上的浏览器中执行。这使得测试可以在多个不同的机器上并行运行,从而加快测试的…...
图片动画化应用中的动作分解方法
作者 | FesianXu 前言 最近基于AI的换脸应用非常的火爆,同时也引起了新一轮的网络伦理大讨论。如果光从技术的角度看,对于视频中的人体动作信息,通常可以通过泰勒展开分解成零阶运动信息与一阶运动信息,如文献[1,2]中提到的&…...
我又和redis超时杠上了
背景 经过上次redis超时排查,并联系云服务商解决之后,redis超时的现象好了一阵子,但是最近又有超时现象报出,但与上次不同的是,这次超时的现象发生在业务高峰期,在简单看过服务器的各项指标以后࿰…...
一文带你吃透MySQL数据库!
文章目录1. 索引2. 事务3. 存储引擎4. 锁机制5. MySQL其他知识点文章字数大约1.27万字,阅读大概需要42分钟,建议收藏后慢慢阅读!!!1. 索引 为什么使用索引 通过创建唯一性索引,可以保证数据库表中每一行数据…...
[学习笔记] 2. 数据结构
数据结构视频地址:https://www.bilibili.com/video/BV1uA411N7c5 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。简单来说,数据结构就是设计数据以何种方式组织并存储在计算机中。 比如:列表、集合与字…...
[学习笔记] 3. 算法进阶
算法进阶视频地址:https://www.bilibili.com/video/BV1uA411N7c5 1. 贪心算法 贪心算法(又称贪婪算法),是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑 —— 所做…...
做自媒体真的能赚到钱吗?真的能赚到几十万吗?
自媒体在当今社会已经成为一个热门话题,越来越多的人开始尝试做自媒体,希望能够通过自媒体赚到钱。但是,做自媒体真的能赚到钱吗?能赚到几十万吗?下面我们来一一解答。 首先,做自媒体确实可以赚到钱。随着互…...
QT使用QListWidget显示多张图片
Qt系列文章目录 文章目录Qt系列文章目录前言一、QListWidget 和 QListView 的差异二、显示效果1.操作工作区界面1.主界面头文件2. 主界面实现界面2.左边图片目录展示界面1.图片目录头文件2.图片目录实现文件2.属性窗口区1.属性窗口头文件2.属性窗口实现文件3 源码下载前言 QLi…...
python 打印进度条
import time recv_size0 total_size1024while recv_size < total_size:time.sleep(0.1)recv_size1024#打印进度条percentrecv_size / total_sizeres int(50 * percent) * #print(\r[%-50s] %d%% % (res,int(100 * percent)),end) # end 打印以‘’结尾,打印% 需…...
【微小说】大学日记
感谢B站up主“看见晴晴了吗”的视频提供的灵感,链接:https://www.bilibili.com/video/BV1tA411m7Kc 整篇故事完全虚构,如有雷同纯属巧合。 2019年8月25日 星期天 晴 今天是我进入大学的第一天。早晨,我画了美美的妆,穿…...
ArrayList扩容机制解析
1.ArrayList的成员变量 首先我们先了解一下ArrayList的成员变量。 // 默认初始化大小 private static final int DEFAULT_CAPACITY 10;// 空数组(用于空实例) // 比如List<String> ls new ArrayList<>(0); private static final Object[…...
jsp-----web应用与开发
jsp基本语法 jsp页面的基本结构 定义变量 <%! %> 表达式:变量、常量、表达式 <% %>代码块、程序段【jsp程序代码即jsp脚本】 <% %>注释 隐藏注释 不会显示在客户的浏览器上,即jsp页面运行后页面上看不到注释内容。同时也不会出…...
洛谷 P1201 [USACO1.1]贪婪的送礼者Greedy Gift Givers
题目链接:P1201 [USACO1.1]贪婪的送礼者Greedy Gift Givers - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述 对于一群 n 个要互送礼物的朋友,GY 要确定每个人送出的钱比收到的多多少。在这一个问题中,每个人都准备了一些钱来送礼物…...
php设计模式-组合模式的运用
介绍 PHP的组合模式是一种设计模式,用于将对象组合成树形结构以表示“部分-整体”的层次结构。该模式允许客户端统一处理单个对象和组合对象,使得客户端在处理对象时不需要知道对象是否为单个对象还是组合对象。 在组合模式中,有两种类型的…...
一文教会你如何简单使用Fegin进行远程服务调用
文章目录1、fegin的基本介绍2、fegin的基本使用步骤3、项目中的实际运用4、测试前言在分布式微服务中,少不了会进行不同服务之间的相互调用,比如A服务要调用B服务中的接口,如何简单方便的实现呢?fegin可以来帮助。 1、fegin的基本…...
OpenAI——CLIPs(代码使用示例)
OpenAI——CLIPs(打通NLP与CV) Open AI在2021年1月份发布Contrastive Language-Image Pre-training(CLIP),基于对比文本-图像对对比学习的多模态模型,通过图像和它对应的文本描述对比学习,模型能够学习到文本-图像对的匹配关系。它开源、多模态、zero-s…...
什么样的人更适合创业?那类人创业更容易成功?
创业是一项充满风险和机遇的事业,成功的创业者需要具备一定的素质和能力。那么,什么样的人更适合创业?哪类人创业更容易成功呢?本文将为您介绍几个适合创业的人群和成功创业者的共同特点。 具有创新精神的人 创业需要不断创新&am…...
RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...
【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
