“车裂”链表---双向带头循环链表

这篇具有很好参考价值的文章主要介绍了“车裂”链表---双向带头循环链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

“车裂”链表---双向带头循环链表,数据结构与算法,链表,数据结构

目录

前言:

1.先看结构:

2.创建节点

3.初始化链表

4.打印链表

5.判空

6.尾插​

7.头插​

8.尾删​

9.头删

10.查找与修改

修改:

11.插入---在pos之前插入

12.删除---删除pos

13.销毁

总结:


前言:

继上一章的单链表,再介绍一个更加方便的链表---双向带头循环链表:

带头即哨兵位的头节点,双向即前后节点间建立了联系,循环即尾节点可以回到头节点即循环。

1.先看结构:

“车裂”链表---双向带头循环链表,数据结构与算法,链表,数据结构

由图中可以看出,每个节点被分为了三部分,比单链表多了一个什么呢?肯定也是指针啦,如果中间部分存储数据,那我们就让前后部分分别称为prev指针和next指针吧:

“车裂”链表---双向带头循环链表,数据结构与算法,链表,数据结构

2.创建节点

与单链表不同的是,这次我们等下再说遍历,原因下面再讲:

“车裂”链表---双向带头循环链表,数据结构与算法,链表,数据结构

一样需要注意要返回新的节点就要动态开辟出来,因为节点是一个局部的指针,开辟出来就让它放在堆区了,就可以直接返回了(后面c++有了传引用返回与new会更方便

3.初始化链表

“车裂”链表---双向带头循环链表,数据结构与算法,链表,数据结构“车裂”链表---双向带头循环链表,数据结构与算法,链表,数据结构

1.首先,由于不像单链表一样,最后指向NULL,我们就要初始化链表,我们只需要创建一个头节点,让它的头尾指针都指向它自己即可。

2.这里哨兵位的数据可以是链表的长度,是链表的长度的话再添加数据的时候就要phead->data++一下,但是如果存储的是char类型的数据,就会面临着如果超过128就会溢出的风险,所以这里使用的是一个无效的数据。

3.记得最后返回哨兵位的头节点。

4.打印链表

“车裂”链表---双向带头循环链表,数据结构与算法,链表,数据结构

1.断言phead是因为后面要解引用(这里说明一下,循环链表没有使用二级指针是因为二级指针在这里显的有些麻烦,有两个指针,并且前后节点和头尾节点都有了联系,不需要再用二级找指向再修改了,直接有了一个或者头都能找到其他的),并且从意义上说phead是空,那哨兵位就干没了。

2.注意循环条件cur与单链表不同了,直到走到与头节点相同才算遍历了一遍。

5.判空

“车裂”链表---双向带头循环链表,数据结构与算法,链表,数据结构

由于后面要删除数据,而只有哨兵位是不能删的,所以认为只有哨兵位是空的。

6.尾插

“车裂”链表---双向带头循环链表,数据结构与算法,链表,数据结构

1.先找到尾节点,尾节点是什么呢?这就用到了循环链表的特性了,单链表此时还需遍历一遍链表,而循环链表的头节点即哨兵位的prev不就是尾节点吗?

2.接下来就让尾节点的next指向newnode,让newnode的prev指向为节点,再建立尾节点与头节点的关系即可,前后顺序其实可以改变(前提是要定义了尾指针tail,避免头节点的prev产生改变而找不到尾节点了,其实只要保证链表不会断的原则怎么写都行)。

3.只有一个哨兵位这样写能不能行呢?带进去,答案是可以,这就是双向循环链表的好处,不用考虑只有一节点的情况了,因为头节点转了一圈还是指向自己,再加一个新节点找尾节点不还是头节点吗?新节点再建立与头节点的联系不还是与它建立联系吗?说着可能有点绕,建议代入一下即可体会到,下面的函数都是如此。

7.头插

“车裂”链表---双向带头循环链表,数据结构与算法,链表,数据结构

1.这里同样有很多写法,还是只要保证链表不断即可。

2.这里就要先找头(这里可不是哨兵位了,头节点是哨兵位的下一个,头插也是在哨兵位的下一个插入)start,再建立哨兵位,新节点,start的关系即可。

3.这里可以发现,只有哨兵位,这样写也是可以插入的。

8.尾删

“车裂”链表---双向带头循环链表,数据结构与算法,链表,数据结构

1.只有头节点不能删,所以断言链表不是空。

2.也可以再记录一个尾指针的前一个指针。

3.注意要记录尾节点,不让phead的prev改变指向后就找不到尾节点了,释放的时候就找不到了。

9.头删

“车裂”链表---双向带头循环链表,数据结构与算法,链表,数据结构

“车裂”链表---双向带头循环链表,数据结构与算法,链表,数据结构

与尾删要注意的内容一样。

10.查找与修改

“车裂”链表---双向带头循环链表,数据结构与算法,链表,数据结构

1.这里不用断言空链表,就算只有哨兵位,也是可以找,找不到直接返回NULL嘛。

修改:

“车裂”链表---双向带头循环链表,数据结构与算法,链表,数据结构

11.插入---在pos之前插入

“车裂”链表---双向带头循环链表,数据结构与算法,链表,数据结构

“车裂”链表---双向带头循环链表,数据结构与算法,链表,数据结构

1.在pos位置插入不就是在pos之前插入然后往后挪到数据嘛(但是链表就不用挪到数据了)。

12.删除---删除pos

“车裂”链表---双向带头循环链表,数据结构与算法,链表,数据结构

“车裂”链表---双向带头循环链表,数据结构与算法,链表,数据结构

1.也可以定义pos的前后节点,那样更清晰。

13.销毁

“车裂”链表---双向带头循环链表,数据结构与算法,链表,数据结构

1.注意最后要释放哨兵位,并再外面置空。

“车裂”链表---双向带头循环链表,数据结构与算法,链表,数据结构文章来源地址https://www.toymoban.com/news/detail-827054.html

总结:

双向带头循环链表只要注意好不让链表断的前提,再加上单链表的基础,基本3遍之内结合图就可以转换成代码,当然有很多写法,还是那句话,数据结构是很灵活的,本人在很长时间没复习且第一次复习链表的前提下大概1遍都能写成,相信仔细阅读后都能有所收获!

到了这里,关于“车裂”链表---双向带头循环链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构:链表基础OJ练习+带头双向循环链表的实现

    目录 一.leetcode剑指 Offer II 027. 回文链表 1.问题描述 2.问题分析与求解 (1) 快慢指针法定位链表的中间节点 (2) 将链表后半部分进行反转 附:递归法反转链表 (3) 双指针法判断链表是否回文 二.带头双向循环链表的实现 1.头文件 2.节点内存申请接口和链表初始化接口 3.链表的打

    2024年02月02日
    浏览(51)
  • 链接未来:深入理解链表数据结构(二.c语言实现带头双向循环链表)

    上篇文章简述讲解了链表的基本概念并且实现了无头单向不循环链表:链接未来:深入理解链表数据结构(一.c语言实现无头单向非循环链表)-CSDN博客 那今天接着给大家带来带头双向循环链表的实现 : 头文件DoubleList.h:用来基础准备(常量定义,typedef),链表表的基本框架

    2024年01月16日
    浏览(61)
  • 数据结构课程设计题目——链表综合算法设计、带头双向循环链表、插入、显示、删除、修改、排序

      课程设计题目1–链表综合算法设计   一、设计内容   已知简单的人事信息系统中职工记录包含职工编号(no)、职工姓名(name)、部门名称(depname)、职称(title)和工资数(salary)等信息(可以增加其他信息),设计并完成一个简单的人事信息管理系统,要求完成但不

    2024年02月08日
    浏览(64)
  • 带头双向循环链表--数据结构

    😶‍🌫️😶‍🌫️😶‍🌫️😶‍🌫️Take your time ! 😶‍🌫️😶‍🌫️😶‍🌫️😶‍🌫️ 💥个人主页:🔥🔥🔥大魔王🔥🔥🔥 💥所属专栏:🔥魔王的修炼之路–数据结构🔥 如果你觉得这篇文章对你有帮助,请在文章结尾处留下你的 点赞 👍和 关注 💖,支持一

    2024年02月01日
    浏览(55)
  • 数据结构---带头双向循环链表

    什么是双向带头循环链表? 上面简单的一个非空 带头循环双向链表逻辑图 如何定义一个双向链表? 根据图和代码可以看双向链表就是单链表的每个结点中,在设置一个指向前驱节点的指针 简单认识之后,对他进行初始化(申请一个头节点,让前驱和后驱指针都指向自己) 代码

    2024年02月07日
    浏览(69)
  • 数据结构——带头双向循环链表

    在创建带头双向循环链表的节点中比之前单链表节点的创建多了一个struct ListNode* prev;结构体指针,目的在与存储前一个节点的地址,便于将整个链表连在一起。 动态申请内存结点,函数返回的是一个指针类型,用malloc开辟一个LTNode大小的空间,并用node指向这个空间,再判断

    2024年02月09日
    浏览(43)
  • 【数据结构】带头双向循环链表

      🧑‍🎓 个人主页:简 料   🏆 所属专栏:C++   🏆 个人社区:越努力越幸运社区   🏆 简       介: 简料简料,简单有料~在校大学生一枚,专注C/C++/GO的干货分享,立志成为您的好帮手 ~ C/C++学习路线 (点击解锁) ❤️ C语言阶段(已结束) ❤️ 数据结构与算法(ing) ❤

    2024年01月16日
    浏览(79)
  • 数据结构-带头双向循环链表

    前言: 链表有很多种,上一章结,我复盘了单链表,这一章节,主要针对双链表的知识点进行,整理复盘,如果将链表分类的话,有很多种,我就学习的方向考察的重点,主要针对这两种链表进行整理。 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用

    2023年04月09日
    浏览(50)
  • 【数据结构】实现带头双向循环链表

    之前我们已经学习了单链表,有了单链表的基础,现在开始学习带头双向循环链表~ 结构最复杂 ,一般用在单独存储数据。 实际中使用的链表数据结构,都是带头双向循环链表 。另外这个结构虽然结构复杂,但是使用代码实现以后会发现 结构会带来很多优势 ,实现反而简单

    2024年02月10日
    浏览(46)
  • 数据结构_带头双向循环链表

    相较于之前的顺序表和单向链表,双向链表的逻辑结构稍微复杂一些,但是在实现各种接口的时候是很简单的。因为不用找尾,写起来会舒服一点。(也可能是因为最近一直在写这个的原因) 在实现接口的时候,除了没有找尾,其他的操作和单向链表是差不多的,这里就不多

    2024年04月14日
    浏览(63)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包