当前位置: 首页 > news >正文

数据结构-带头双向循环链表

前言:

链表有很多种,上一章结,我复盘了单链表,这一章节,主要针对双链表的知识点进行,整理复盘,如果将链表分类的话,有很多种,我就学习的方向考察的重点,主要针对这两种链表进行整理。

带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了。带头双向循环链表如下图所示。 

 


目录

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;
}

相关文章:

数据结构-带头双向循环链表

前言&#xff1a; 链表有很多种&#xff0c;上一章结&#xff0c;我复盘了单链表&#xff0c;这一章节&#xff0c;主要针对双链表的知识点进行&#xff0c;整理复盘&#xff0c;如果将链表分类的话&#xff0c;有很多种&#xff0c;我就学习的方向考察的重点&#xff0c;主要…...

3 问 6 步,极狐GitLab 帮助企业构建高效、安全、合规的 DevSecOps 文化

本文来源&#xff1a;about.gitlab.com 作者&#xff1a;Vanessa Wegner 译者&#xff1a;极狐(GitLab) 市场部内容团队 &#x1f512; 安全为何重要&#xff1f;此前&#xff0c;我们分享了&#xff1a; 1. 2023年DevOps发展趋势&#x1f449;重磅&#xff01;GitLab 提出五大…...

SPA(单页应用)知多少

单页面应用程序将所有的活动局限于一个Web页面中&#xff0c;在该Web页面初始化时加载相应的HTML、JavaScript 和 CSS。一旦页面加载完成&#xff0c;单页面应用不会因为用户的操作而进行页面的重新加载或跳转。取而代之的是利用 JavaScript 动态的变换HTML的内容&#xff0c;从…...

Selenium实战【远程控制】【JAVA爬虫】

简介 Selenium RemoteWebDriver是Selenium WebDriver的一个扩展,它可以将测试运行在远程机器上的浏览器中。 使用RemoteWebDriver,可以在本地机器上编写测试脚本,然后将测试请求发送到远程机器上的浏览器中执行。这使得测试可以在多个不同的机器上并行运行,从而加快测试的…...

图片动画化应用中的动作分解方法

作者 | FesianXu 前言 最近基于AI的换脸应用非常的火爆&#xff0c;同时也引起了新一轮的网络伦理大讨论。如果光从技术的角度看&#xff0c;对于视频中的人体动作信息&#xff0c;通常可以通过泰勒展开分解成零阶运动信息与一阶运动信息&#xff0c;如文献[1,2]中提到的&…...

我又和redis超时杠上了

背景 经过上次redis超时排查&#xff0c;并联系云服务商解决之后&#xff0c;redis超时的现象好了一阵子&#xff0c;但是最近又有超时现象报出&#xff0c;但与上次不同的是&#xff0c;这次超时的现象发生在业务高峰期&#xff0c;在简单看过服务器的各项指标以后&#xff0…...

一文带你吃透MySQL数据库!

文章目录1. 索引2. 事务3. 存储引擎4. 锁机制5. MySQL其他知识点文章字数大约1.27万字&#xff0c;阅读大概需要42分钟&#xff0c;建议收藏后慢慢阅读&#xff01;&#xff01;&#xff01;1. 索引 为什么使用索引 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据…...

[学习笔记] 2. 数据结构

数据结构视频地址&#xff1a;https://www.bilibili.com/video/BV1uA411N7c5 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。简单来说&#xff0c;数据结构就是设计数据以何种方式组织并存储在计算机中。 比如:列表、集合与字…...

[学习笔记] 3. 算法进阶

算法进阶视频地址&#xff1a;https://www.bilibili.com/video/BV1uA411N7c5 1. 贪心算法 贪心算法&#xff08;又称贪婪算法&#xff09;&#xff0c;是指在对问题求解时&#xff0c;总是做出在当前看来是最好的选择。也就是说&#xff0c;不从整体最优上加以考虑 —— 所做…...

做自媒体真的能赚到钱吗?真的能赚到几十万吗?

自媒体在当今社会已经成为一个热门话题&#xff0c;越来越多的人开始尝试做自媒体&#xff0c;希望能够通过自媒体赚到钱。但是&#xff0c;做自媒体真的能赚到钱吗&#xff1f;能赚到几十万吗&#xff1f;下面我们来一一解答。 首先&#xff0c;做自媒体确实可以赚到钱。随着互…...

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 打印以‘’结尾&#xff0c;打印% 需…...

【微小说】大学日记

感谢B站up主“看见晴晴了吗”的视频提供的灵感&#xff0c;链接&#xff1a;https://www.bilibili.com/video/BV1tA411m7Kc 整篇故事完全虚构&#xff0c;如有雷同纯属巧合。 2019年8月25日 星期天 晴 今天是我进入大学的第一天。早晨&#xff0c;我画了美美的妆&#xff0c;穿…...

ArrayList扩容机制解析

1.ArrayList的成员变量 首先我们先了解一下ArrayList的成员变量。 // 默认初始化大小 private static final int DEFAULT_CAPACITY 10;// 空数组&#xff08;用于空实例&#xff09; // 比如List<String> ls new ArrayList<>(0); private static final Object[…...

jsp-----web应用与开发

jsp基本语法 jsp页面的基本结构 定义变量 <%! %> 表达式&#xff1a;变量、常量、表达式 <% %>代码块、程序段【jsp程序代码即jsp脚本】 <% %>注释 隐藏注释 不会显示在客户的浏览器上&#xff0c;即jsp页面运行后页面上看不到注释内容。同时也不会出…...

洛谷 P1201 [USACO1.1]贪婪的送礼者Greedy Gift Givers

题目链接&#xff1a;P1201 [USACO1.1]贪婪的送礼者Greedy Gift Givers - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述 对于一群 n 个要互送礼物的朋友&#xff0c;GY 要确定每个人送出的钱比收到的多多少。在这一个问题中&#xff0c;每个人都准备了一些钱来送礼物…...

php设计模式-组合模式的运用

介绍 PHP的组合模式是一种设计模式&#xff0c;用于将对象组合成树形结构以表示“部分-整体”的层次结构。该模式允许客户端统一处理单个对象和组合对象&#xff0c;使得客户端在处理对象时不需要知道对象是否为单个对象还是组合对象。 在组合模式中&#xff0c;有两种类型的…...

一文教会你如何简单使用Fegin进行远程服务调用

文章目录1、fegin的基本介绍2、fegin的基本使用步骤3、项目中的实际运用4、测试前言在分布式微服务中&#xff0c;少不了会进行不同服务之间的相互调用&#xff0c;比如A服务要调用B服务中的接口&#xff0c;如何简单方便的实现呢&#xff1f;fegin可以来帮助。 1、fegin的基本…...

OpenAI——CLIPs(代码使用示例)

OpenAI——CLIPs(打通NLP与CV) Open AI在2021年1月份发布Contrastive Language-Image Pre-training(CLIP),基于对比文本-图像对对比学习的多模态模型&#xff0c;通过图像和它对应的文本描述对比学习&#xff0c;模型能够学习到文本-图像对的匹配关系。它开源、多模态、zero-s…...

什么样的人更适合创业?那类人创业更容易成功?

创业是一项充满风险和机遇的事业&#xff0c;成功的创业者需要具备一定的素质和能力。那么&#xff0c;什么样的人更适合创业&#xff1f;哪类人创业更容易成功呢&#xff1f;本文将为您介绍几个适合创业的人群和成功创业者的共同特点。 具有创新精神的人 创业需要不断创新&am…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...