数据结构——lesson4带头双向循环链表实现

2024-02-29 21:04
文章标签 实现 链表 数据结构 双向 循环 带头 lesson4

本文主要是介绍数据结构——lesson4带头双向循环链表实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言✨✨

💥个人主页：大耳朵土土垚-CSDN博客

💥 所属专栏：数据结构学习笔记​​​​​​

💥双链表与单链表的区分：单链表介绍与实现

💥对于malloc函数有疑问的:动态内存函数介绍

   感谢大家的观看与支持🌹🌹🌹 

   有问题可以写在评论区或者私信我哦~

 

目录

前言✨✨

一、💥💥什么是带头双向循环链表？

二、🥳🥳带头双向循环链表的实现 

1 .搭建链表基础

2.从内存中开辟一个节点

3. 创建返回链表的头结点

4.双向链表销毁

5.双向链表打印 

6.双向链表尾插 

7.双向链表尾删

8.双向链表头插 

9.双向链表头删 

10.双向链表查找

11.双向链表在pos的前面进行插入 

12.双向链表删除pos位置的节点 

三、💫💫拓展

四、🎉🎉结言 

一、💥💥什么是带头双向循环链表？

 

带头双向循环链表（Doubly Circular Linked List with a Head）是一种链表数据结构，它具有以下特点：

1.头节点：带头双向循环链表包含一个头节点，它位于链表的起始位置，并且不存储实际数据。头节点的前驱指针指向尾节点，头节点的后继指针指向第一个实际数据节点。

2.循环连接：尾节点的后继指针指向头节点，而头节点的前驱指针指向尾节点，将链表形成一个循环连接的闭环。这样可以使链表在遍历时可以无限循环，方便实现循环操作。

3.双向连接：每个节点都有一个前驱指针和一个后继指针，使得节点可以向前和向后遍历。前驱指针指向前一个节点，后继指针指向后一个节点。

        总结:带头双向循环链表可以支持在链表的任意位置进行插入和删除操作，并且可以实现正向和反向的循环遍历。通过循环连接的特性，链表可以在连续的循环中遍历所有节点，使得链表的操作更加灵活和高效。

如下图所示：

 

 

结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。 

二、🥳🥳带头双向循环链表的实现 

1 .搭建链表基础

带头双向循环链表需要三个变量，两个存放指向前后节点的指针，另一个存放数据

// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;//存放数据struct ListNode* next;//指向下一个节点struct ListNode* prev;//指向上一个节点
}ListNode;

2.从内存中开辟一个节点

使用malloc函数开辟节点

//从内存中开辟一个节点
ListNode* BuyNode(LTDataType x)
{ListNode* buynode = (ListNode*)malloc(sizeof(struct ListNode));if (buynode == NULL)//开辟失败{perror("malloc fail");}buynode->data = x;buynode->next = NULL;buynode->prev = NULL;}

 

3. 创建返回链表的头结点
 

开始时头节点两个指针都指向自己

//创建返回链表的头结点.
ListNode* ListCreate()
{ListNode* head = BuyNode(-1);//这里将头节点数据设为-1，任意数都可以head->next = head;head->prev = head;return head;
}

 

4.双向链表销毁

 malloc开辟空间后要使用free销毁内存空间，防止内存泄漏

// 双向链表销毁
void ListDestory(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->next;//头节点最后销毁while (cur != pHead)//循环一遍{ListNode* next = cur->next;//保存下一个节点，防止丢失free(cur);//销毁节点cur = next;}free(pHead);//销毁头节点
}

5.双向链表打印 

 

//双向链表打印
void ListPrint(ListNode* pHead)
{assert(pHead);if (pHead->next == pHead)//没有节点的情况，也可以不考虑{printf("pHead<=>pHead");return;}//有节点的情况printf("pHead<=>");//先打印pHeadListNode* cur = pHead->next;while (cur != pHead){printf("%d<=>", cur->data);cur = cur->next;}printf("pHead");//因为最后也是指向pHead
}

 

没有节点情况打印如下： 

6.双向链表尾插 

 

// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);//找尾节点,保存原来的尾//尾节点就是pHead->prevListNode* tail = pHead->prev;//开辟新节点ListNode* newnode = BuyNode(x);//尾插pHead->prev = newnode;newnode->next = pHead;newnode->prev = tail;tail->next = newnode;}

 

结果如下：

 

7.双向链表尾删

// 双向链表尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);//没有节点不能尾删，头节点pHead不算if (pHead->next == pHead){printf("没有添加节点\n");return;}//找尾节点，以及尾节点的前一个节点ListNode* tail = pHead->prev;ListNode* tailprev = tail->prev;//尾删tailprev->next = pHead;pHead->prev = tailprev;free(tail);//释放内存空间
}

 结果如下：

8.双向链表头插 

// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);//找头以外的第一个节点ListNode* headnext = pHead->next;//创建新节点ListNode* newnode = BuyNode(x);//头插pHead->next = newnode;newnode->next = headnext;newnode->prev = pHead;headnext->prev = newnode;
}

 

结果如下：

9.双向链表头删 

 

// 双向链表头删
void ListPopFront(ListNode* pHead)
{assert(pHead);//判断有没有节点，头节点pHead除外if (pHead->next == pHead){printf("没有添加节点\n");return;}//有节点//找头节点以及头节点的下一个节点ListNode* head = pHead->next;ListNode* headnext = head->next;//头删pHead->next = headnext;headnext->prev = pHead;free(head);//释放内存空间
}

 

 结果如下：

 

10.双向链表查找

// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{assert(pHead);//判断有无节点if (pHead->next == pHead){printf("没有添加节点\n");return;}ListNode* cur = pHead->next;//遍历查找while (cur){if (cur->data == x){return cur;//找到返回地址}cur = cur->next;}
}

结果如下：

11.双向链表在pos的前面进行插入 

在pos位置前面插入原理和头插尾插相似

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);//找到pos前一个节点ListNode* posprev = pos->prev;//创建新节点ListNode* newnode = BuyNode(x);//在pos前插入posprev->next = newnode;newnode->next = pos;newnode->prev = posprev;pos->prev = newnode;}

结果如下：

 

12.双向链表删除pos位置的节点 

在pos位置删除原理和头删尾删相似

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);//找到pos前一个节点ListNode* posprev = pos->prev;//找打pos后一个节点ListNode* posnext = pos->next;//删除pos位置节点posprev->next = posnext;posnext->prev = posprev;free(pos);//释放内存空间}

结果如下：

三、💫💫拓展

思考：在pos之前插入与头插尾插是否有关？

           在pos位置删除与头删尾删是否相似？

 

我们发现pos位置前插入函数代码似乎可以复用在头插尾插；

pos位置删除函数代码似乎可以复用在头删尾删；

下面我们一起来实现

1.尾插头插 

//尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);//找尾节点,保存原来的尾//尾节点就是pHead->prev//ListNode* tail = pHead->prev;开辟新节点//ListNode* newnode = BuyNode(x);尾插//pHead->prev = newnode;//newnode->next = pHead;//newnode->prev = tail;//tail->next = newnode;ListInsert(pHead, x);}//头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);//找头以外的第一个节点//ListNode* headnext = pHead->next;创建新节点//ListNode* newnode = BuyNode(x);头插//pHead->next = newnode;//newnode->next = headnext;//newnode->prev = pHead;//headnext->prev = newnode;ListInsert(pHead->next, x);}

2.尾删，头删

 

// 双向链表尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);//没有节点不能尾删，头节点pHead不算if (pHead->next == pHead){printf("没有添加节点\n");return;}找尾节点，以及尾节点的前一个节点//ListNode* tail = pHead->prev;//ListNode* tailprev = tail->prev;尾删//tailprev->next = pHead;//pHead->prev = tailprev;//free(tail);//释放内存空间ListErase(pHead->prev);
}// 双向链表头删
void ListPopFront(ListNode* pHead)
{assert(pHead);//判断有没有节点，头节点pHead除外if (pHead->next == pHead){printf("没有添加节点\n");return;}有节点找头节点以及头节点的下一个节点//ListNode* head = pHead->next;//ListNode* headnext = head->next;头删//pHead->next = headnext;//headnext->prev = pHead;//free(head);//释放内存空间ListErase(pHead->next);
}

 

 运行结果依然不受影响：

 

四、🎉🎉结言 

        我们通过上面的学习发现，相似的代码的重复利用可以大大减少我们写代码的时间与精力，提高我们工作学习的效率；双向链表尽管结构较单链表复杂，但其实现却比单链表简单得多，相信大家对此都深有体会，此外数据结构的题目我们可以通过画图来很好的获得思路与接替步骤，以上就是带头双向循环链表的相关知识啦~完结撒花~🎉🎉🌹🌹🌹

这篇关于数据结构——lesson4带头双向循环链表实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/760078。

相关文章

Vue项目的甘特图组件之dhtmlx-gantt使用教程和实现效果展示(推荐)

Vue项目的甘特图组件之dhtmlx-gantt使用教程和实现效果展示(推荐)

《Vue项目的甘特图组件之dhtmlx-gantt使用教程和实现效果展示(推荐)》文章介绍了如何使用dhtmlx-gantt组件来实现公司的甘特图需求,并提供了一个简单的Vue组件示例,文章还分享了一... 目录一、首先 npm 安装插件二、创建一个vue组件三、业务页面内 引用自定义组件：四、dhtmlx
阅读更多...
Vue ElementUI中Upload组件批量上传的实现代码

Vue ElementUI中Upload组件批量上传的实现代码

《VueElementUI中Upload组件批量上传的实现代码》ElementUI中Upload组件批量上传通过获取upload组件的DOM、文件、上传地址和数据,封装uploadFiles方法,使... ElementUI中Upload组件如何批量上传首先就是upload组件 <el-upl
阅读更多...
Docker部署Jenkins持续集成(CI)工具的实现

Docker部署Jenkins持续集成(CI)工具的实现

《Docker部署Jenkins持续集成(CI)工具的实现》Jenkins是一个流行的开源自动化工具,广泛应用于持续集成（CI）和持续交付（CD）的环境中,本文介绍了使用Docker部署Jenkins... 目录前言一、准备工作二、设置变量和目录结构三、配置 docker 权限和网络四、启动 Jenkins
阅读更多...
Python3脚本实现Excel与TXT的智能转换

Python3脚本实现Excel与TXT的智能转换

《Python3脚本实现Excel与TXT的智能转换》在数据处理的日常工作中,我们经常需要将Excel中的结构化数据转换为其他格式,本文将使用Python3实现Excel与TXT的智能转换,需要的可以... 目录场景应用：为什么需要这种转换技术解析：代码实现详解核心代码展示改进点说明实战演练：从Excel到
阅读更多...
如何使用CSS3实现波浪式图片墙

如何使用CSS3实现波浪式图片墙

《如何使用CSS3实现波浪式图片墙》：本文主要介绍了如何使用CSS3的transform属性和动画技巧实现波浪式图片墙，通过设置图片的垂直偏移量，并使用动画使其周期性地改变位置，可以创建出动态且具有波浪效果的图片墙，同时，还强调了响应式设计的重要性，以确保图片墙在不同设备上都能良好显示，详细内容请阅读本文，希望能对你有所帮助...
阅读更多...
C# string转unicode字符的实现

C# string转unicode字符的实现

《C#string转unicode字符的实现》本文主要介绍了C#string转unicode字符的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随... 目录1. 获取字符串中每个字符的 Unicode 值示例代码：输出：2. 将 Unicode 值格式化
阅读更多...
python安装whl包并解决依赖关系的实现

python安装whl包并解决依赖关系的实现

《python安装whl包并解决依赖关系的实现》本文主要介绍了python安装whl包并解决依赖关系的实现,文中通过图文示例介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录一、什么是whl文件？二、我们为什么需要使用whl文件来安装python库？三、我们应该去哪儿下
阅读更多...
Python脚本实现图片文件批量命名

Python脚本实现图片文件批量命名

《Python脚本实现图片文件批量命名》这篇文章主要为大家详细介绍了一个用python第三方库pillow写的批量处理图片命名的脚本,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录前言源码批量处理图片尺寸脚本源码GUI界面源码打包成.exe可执行文件前言本文介绍一个用python第三方库pi
阅读更多...
Java中将异步调用转为同步的五种实现方法

Java中将异步调用转为同步的五种实现方法

《Java中将异步调用转为同步的五种实现方法》本文介绍了将异步调用转为同步阻塞模式的五种方法：wait/notify、ReentrantLock+Condition、Future、CountDownL... 目录异步与同步的核心区别方法一：使用wait/notify + synchronized代码示例关键
阅读更多...
Nginx实现动态封禁IP的步骤指南

Nginx实现动态封禁IP的步骤指南

《Nginx实现动态封禁IP的步骤指南》在日常的生产环境中,网站可能会遭遇恶意请求、DDoS攻击或其他有害的访问行为,为了应对这些情况,动态封禁IP是一项十分重要的安全策略,本篇博客将介绍如何通过NG... 目录1、简述2、实现方式3、使用 fail2ban 动态封禁3.1 安装 fail2ban3.2 配
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2