【数据结构】双向带头循环链表（c语言）（附源码）

🌟🌟作者主页：ephemerals__

🌟🌟所属专栏：数据结构

目录

前言

1.双向带头循环链表的概念和结构定义

2.双向带头循环链表的实现

2.1 方法声明

2.2 方法实现

2.2.1 创建新节点

2.2.2 初始化

2.2.3 打印

2.2.4 判断链表是否为空

2.2.5 尾插

2.2.6 头插

2.2.7 尾删

2.2.8 头删

2.2.9 查找

2.2.10 指定位置之前插入

2.2.11 指定位置之后插入

2.2.12 删除指定位置节点

2.2.13 销毁链表

3.程序全部代码

总结

前言

        我们常用的链表有两种：

单向无头不循环链表：也就是我们所说的单链表，它的结构简单，一般是不会用于单独存放数据的。它常被用于实现哈希桶、图的邻接表等。

双向带头循环链表：通常称为双向链表，它的结构较为复杂，实际使用中用于单独存放数据。虽然它的结构比较复杂，但是它的方法执行效率要高于单链表。

接下来，就让我们学习并尝试实现双向带头循环链表。

1.双向带头循环链表的概念和结构定义

双向带头循环链表（双向链表）有三个关键点：

1.双向：不同于单链表，双向链表的节点的指针域附带有两个指针，分别指向其前驱节点和后继节点，这便于我们更灵活地访问链表元素。

2.带头：这里的“头”指的是“哨兵位”，也就是说在创建链表时先创建一个哨兵位的节点位于头部，此节点不存放任何有效数据，只是起到“放哨”的作用。

3.循环：也就是说链表尾部不指向空指针，而是指向头部的节点，形成一个“环”状结构。

而对于单链表，由于不具备这三个特性，所以在运行效率上要低于双向链表。那么我们来看看它的结构定义：

typedef int LTDataType;//双向链表的节点定义
typedef struct ListNode
{LTDataType data;//数据域struct ListNode* next;//指向前驱节点的指针struct ListNode* prev;//指向后继节点的指针
}LTNode;

2.双向带头循环链表的实现

        接下来，我们尝试实现它的一些功能。首先是方法的声明：

2.1 方法声明

//创建新节点
LTNode* LTBuyNode(LTDataType n);//初始化，创建哨兵
void LTInit(LTNode** pphead);//打印链表
void LTPrint(LTNode* phead);//判断链表是否为空
bool LTEmpty(LTNode* phead);//尾插
void LTPushBack(LTNode* phead,LTDataType n);//头插
void LTPushFront(LTNode* phead, LTDataType n);//尾删
void LTPopBack(LTNode* phead);//头删
void LTPopFront(LTNode* phead);//查找
LTNode* LTFind(LTNode* phead, LTDataType n);//指定位置之前插入
void LTInsert(LTNode* pos, LTDataType n);//指定位置之后插入
void LTInsertAfter(LTNode* pos, LTDataType n);//删除指定节点
void LTErase(LTNode* pos);//销毁链表
void LTDestroy(LTNode** pphead);

2.2 方法实现

2.2.1 创建新节点

        创建新节点的方式于单链表相似，但由于循环的特性，要暂时将其next指针和prev指针指向自己：

//创建新节点
LTNode* LTBuyNode(LTDataType n)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//动态申请内存if (newnode == NULL)//申请失败，退出程序{perror("malloc");exit(1);}newnode->data = n;newnode->next = newnode->prev = newnode;//让两个指针都指向自己return newnode;//返回该节点
}

2.2.2 初始化

        初始化时，我们需要创建一个哨兵节点，并且让头指针指向它。由于修改了头指针的值，所以要传入二级指针。

//初始化，创建哨兵
void LTInit(LTNode** pphead)
{assert(pphead);//避免传入空指针*pphead = LTBuyNode(-1);//创建哨兵节点，传无效数据
}

2.2.3 打印

        对于打印操作，我们从哨兵的next节点开始，按顺序向后遍历打印即可。这里需要注意一下循环的结束条件。

//打印链表
void LTPrint(LTNode* phead)
{LTNode* cur = phead->next;//从头节点的下一个节点开始遍历while (cur != phead)//由于链表为循环链表，一轮遍历之后还会走到头节点的位置，所以就以头节点为结束标志{printf("%d ", cur->data);//打印数据cur = cur->next;//向后遍历}printf("\n");
}

2.2.4 判断链表是否为空

        将判空操作单独封装为一个函数，便于其他方法使用。

//判断链表是否为空
bool LTEmpty(LTNode* phead)
{assert(phead);//防止传空指针return phead == phead->next;//后继节点为头节点本身，则说明链表为空，返回true，否则返回false
}

2.2.5 尾插

        与单链表不同，尾插的操作不需要遍历找到链表末尾，头节点的prev指针就是链表的尾节点。

代码如下：

//尾插
void LTPushBack(LTNode* phead, LTDataType n)
{assert(phead);LTNode* newnode = LTBuyNode(n);//创建新节点newnode->next = phead;//新节点的next指向头节点newnode->prev = phead->prev;//新节点的prev指向当前的尾节点phead->prev->next = newnode;//当前尾节点的next指向新节点phead->prev = newnode;//头节点的prev指向新节点
}

2.2.6 头插

        头插的操作过程与尾插十分相似，注意要在头节点的下个节点处插入。

代码如下：

//头插
void LTPushFront(LTNode* phead, LTDataType n)
{assert(phead);LTNode* newnode = LTBuyNode(n);newnode->next = phead->next;//新节点的next指向当前的第一个节点newnode->prev = phead;//新节点的prev指向头节点phead->next->prev = newnode;//当前第一个节点的prev指向新节点phead->next = newnode;//头节点的next指向新节点
}

2.2.7 尾删

        尾删操作时，注意针对的是头节点的prev节点。

代码如下：

//尾删
void LTPopBack(LTNode* phead)
{assert(phead && !LTEmpty(phead));//注意链表不能为空LTNode* del = phead->prev;//要删除的节点LTNode* prev = del->prev;//要删除节点的前驱节点prev->next = phead;//前驱节点的next指向头节点phead->prev = prev;//头节点的prev指向前驱节点free(del);//释放del的内存del = NULL;//及时制空
}

2.2.8 头删

        头删的操作与尾删相似，针对的是头节点的next节点。

代码如下：

//头删
void LTPopFront(LTNode* phead)
{assert(phead && !LTEmpty(phead));LTNode* del = phead->next;//要删除的节点LTNode* next = del->next;//要删除节点的后继节点next->prev = phead;//后继节点的prev指向头节点phead->next = next;//头节点的next指向后继节点free(del);del = NULL;
}

2.2.9 查找

        与单链表相同，查找操作也需要遍历链表，匹配成功则返回该节点；找不到则返回空指针。

//查找
LTNode* LTFind(LTNode* phead, LTDataType n)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == n){return cur;}cur = cur->next;}return NULL;
}

2.2.10 指定位置之前插入

        进行指定位置插入时，注意确定指定位置的前驱节点和后继节点。

//指定位置之前插入
void LTInsert(LTNode* pos, LTDataType n)
{assert(pos);LTNode* newnode = LTBuyNode(n);newnode->next = pos;//新节点的next指向posnewnode->prev = pos->prev;//新节点的prev指向pos的前一节点pos->prev->next = newnode;//pos的前节点的next指向newnodepos->prev = newnode;//pos的prev指向newnode
}

2.2.11 指定位置之后插入

//指定位置之后插入
void LTInsertAfter(LTNode* pos, LTDataType n)
{assert(pos);LTNode* newnode = LTBuyNode(n);newnode->next = pos->next;//新节点的next指向pos的后一节点newnode->prev = pos;//新节点的prev指向pospos->next->prev = newnode;//pos的后一节点的prev指向newnodepos->next = newnode;//pos的next指向newnode
}

2.2.12 删除指定位置节点

//删除指定节点
void LTErase(LTNode* pos)
{assert(pos);pos->next->prev = pos->prev;//pos的后继节点的prev指向pos的前驱节点pos->prev->next = pos->next;//pos的前驱节点的next指向pos的后继节点free(pos);pos = NULL;
}

2.2.13 销毁链表

        销毁链表时，我们需要遍历链表按照顺序删除全部节点，最后记得要删除头节点。

//销毁链表
void LTDestroy(LTNode** pphead)
{assert(pphead);if (*pphead == NULL)//链表已经被销毁的情况{return;}LTNode* cur = (*pphead)->next;//从第一个节点开始遍历while (cur != *pphead){LTNode* next = cur->next;//记录后继节点free(cur);//释放内存cur = next;//使cur指向记录的后继节点}cur = NULL;free(*pphead);//删除头节点*pphead = NULL;
}

3.程序全部代码

        程序全部代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int LTDataType;//双向链表的节点定义
typedef struct ListNode
{LTDataType data;//数据域struct ListNode* next;//指向前驱节点的指针struct ListNode* prev;//指向后继节点的指针
}LTNode;//创建新节点
LTNode* LTBuyNode(LTDataType n);//初始化，创建哨兵
void LTInit(LTNode** pphead);//打印链表
void LTPrint(LTNode* phead);//判断链表是否为空
bool LTEmpty(LTNode* phead);//尾插
void LTPushBack(LTNode* phead,LTDataType n);//头插
void LTPushFront(LTNode* phead, LTDataType n);//尾删
void LTPopBack(LTNode* phead);//头删
void LTPopFront(LTNode* phead);//查找
LTNode* LTFind(LTNode* phead, LTDataType n);//指定位置之前插入
void LTInsert(LTNode* pos, LTDataType n);//指定位置之后插入
void LTInsertAfter(LTNode* pos, LTDataType n);//删除指定节点
void LTErase(LTNode* pos);//销毁链表
void LTDestroy(LTNode** pphead);//创建新节点
LTNode* LTBuyNode(LTDataType n)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//动态申请内存if (newnode == NULL)//申请失败，退出程序{perror("malloc");exit(1);}newnode->data = n;newnode->next = newnode->prev = newnode;//让两个指针都指向自己return newnode;//返回该节点
}//初始化，创建哨兵
void LTInit(LTNode** pphead)
{assert(pphead);//避免传入空指针*pphead = LTBuyNode(-1);//创建哨兵节点，传无效数据
}//打印链表
void LTPrint(LTNode* phead)
{LTNode* cur = phead->next;//从头节点的下一个节点开始遍历while (cur != phead)//由于链表为循环链表，一轮遍历之后还会走到头节点的位置，所以就以头节点为结束标志{printf("%d ", cur->data);//打印数据cur = cur->next;//向后遍历}printf("\n");
}//判断链表是否为空
bool LTEmpty(LTNode* phead)
{assert(phead);//防止传空指针return phead == phead->next;//后继节点为头节点本身，则说明链表为空，返回true，否则返回false
}//尾插
void LTPushBack(LTNode* phead, LTDataType n)
{assert(phead);LTNode* newnode = LTBuyNode(n);//创建新节点newnode->next = phead;//新节点的next指向头节点newnode->prev = phead->prev;//新节点的prev指向当前的尾节点phead->prev->next = newnode;//当前尾节点的next指向新节点phead->prev = newnode;//头节点的prev指向新节点
}//头插
void LTPushFront(LTNode* phead, LTDataType n)
{assert(phead);LTNode* newnode = LTBuyNode(n);newnode->next = phead->next;//新节点的next指向当前的第一个节点newnode->prev = phead;//新节点的prev指向头节点phead->next->prev = newnode;//当前第一个节点的prev指向新节点phead->next = newnode;//头节点的next指向新节点
}//尾删
void LTPopBack(LTNode* phead)
{assert(phead && !LTEmpty(phead));//注意链表不能为空LTNode* del = phead->prev;//要删除的节点LTNode* prev = del->prev;//要删除节点的前驱节点prev->next = phead;//前驱节点的next指向头节点phead->prev = prev;//头节点的prev指向前驱节点free(del);//释放del的内存del = NULL;//及时制空
}//头删
void LTPopFront(LTNode* phead)
{assert(phead && !LTEmpty(phead));LTNode* del = phead->next;//要删除的节点LTNode* next = del->next;//要删除节点的后继节点next->prev = phead;//后继节点的prev指向头节点phead->next = next;//头节点的next指向后继节点free(del);del = NULL;
}//查找
LTNode* LTFind(LTNode* phead, LTDataType n)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == n){return cur;}cur = cur->next;}return NULL;
}//指定位置之前插入
void LTInsert(LTNode* pos, LTDataType n)
{assert(pos);LTNode* newnode = LTBuyNode(n);newnode->next = pos;//新节点的next指向posnewnode->prev = pos->prev;//新节点的prev指向pos的前一节点pos->prev->next = newnode;//pos的前节点的next指向newnodepos->prev = newnode;//pos的prev指向newnode
}//指定位置之后插入
void LTInsertAfter(LTNode* pos, LTDataType n)
{assert(pos);LTNode* newnode = LTBuyNode(n);newnode->next = pos->next;//新节点的next指向pos的后一节点newnode->prev = pos;//新节点的prev指向pospos->next->prev = newnode;//pos的后一节点的prev指向newnodepos->next = newnode;//pos的next指向newnode
}//删除指定节点
void LTErase(LTNode* pos)
{assert(pos);pos->next->prev = pos->prev;//pos的后继节点的prev指向pos的前驱节点pos->prev->next = pos->next;//pos的前驱节点的next指向pos的后继节点free(pos);pos = NULL;
}//销毁链表
void LTDestroy(LTNode** pphead)
{assert(pphead);if (*pphead == NULL)//链表已经被销毁的情况{return;}LTNode* cur = (*pphead)->next;//从第一个节点开始遍历while (cur != *pphead){LTNode* next = cur->next;//记录后继节点free(cur);//释放内存cur = next;//使cur指向记录的后继节点}cur = NULL;free(*pphead);//删除头节点*pphead = NULL;
}

总结

        今天我们学习了双向带头循环链表的概念以及功能实现。可以发现，与单链表不同，它的头插、尾插、头删、尾删等操作的时间复杂度都是O(1)，大大提升了运行效率。之后博主回合大家分享栈和队列的内容。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://xiahunao.cn/news/3269312.html

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

【基于yolo转onnx 量化测试】

【基于yolo转onnx 量化测试】

1、 训练模型转onnx 和量化 from ultralytics import YOLOmodel_path "yolov10/runs/train8/weights/best.pt" model YOLO(model_path) # 载入官方模型 # 导出模型 model.export(formatonnx,halfTrue)2、量化&#xff0c;减少了三分之一的存储空间从100M到30M …
阅读更多...
当镜像地址出错的时候下载selenium的处理办法

当镜像地址出错的时候下载selenium的处理办法

当镜像地址出错的时候下载selenium的处理办法 一、原因 显示出错&#xff1a; C:\Users\xiaodaidai>pip install selenium3.4.0 Looking in indexes: Simple Index WARNING: Retrying (Retry(total4, connectNone, readNone, redirectNone, statusNone)) after connection …
阅读更多...
学语言，看这里，如何快速掌握JavaScript？

学语言，看这里，如何快速掌握JavaScript？

本篇文章是基于会点c语言和会点python基础的&#xff0c;去更容易上手javascript 学习笔记分享✨&#x1f308;&#x1f44f;&#x1f44f;&#x1f451;&#x1f451; javascript目录 1.安装node.js&#xff1a;2.配置环境变量——创建NODE_HOME :3.变量与常量4.原生数据类型5…
阅读更多...
C++ —— STL简介

C++ —— STL简介

1. 什么是STL STL(standard template libaray-标准模板库)&#xff1a;是C标准库的重要组成部分&#xff0c;不仅是一个可复用的 组件库&#xff0c;而且是一个包罗数据结构与算法的软件框架 2.STL的版本 原始版本 Alexander Stepanov、Meng Lee 在惠普实验室完成的原始版本…
阅读更多...
Java之父官宣退休

Java之父官宣退休

今年不用说大家都知道环境真的很差很差&#xff0c;裁员降薪已经是家常便饭&#xff0c;在这种严峻环境下&#xff0c;我们只能提升自己内功来抗风险&#xff0c;下面分享一本java之父推荐的优秀书籍。 刚过完自己 69 岁生日的两个月后&#xff0c;Java 之父 James Gosling&…
阅读更多...
论文阅读：Deep_Generic_Dynamic_Object_Detection_Based_on_Dynamic_Grid_Maps

论文阅读：Deep_Generic_Dynamic_Object_Detection_Based_on_Dynamic_Grid_Maps

目录 概要 Motivation 整体框架流程 技术细节 小结 不足 论文地址&#xff1a;Deep Generic Dynamic Object Detection Based on Dynamic Grid Maps | IEEE Conference Publication | IEEE Xplore 概要 该文章提出了一种基于动态网格图&#xff08;Dynamic Grid Maps&a…
阅读更多...
Golang高效合并(拼接)多个gzip压缩文件

Golang高效合并(拼接)多个gzip压缩文件

有时我们可能会遇到需要把多个 gzip 文件合并成单个 gzip 文件的场景&#xff0c;最简单最容易的方式是把每个gzip文件都先解压&#xff0c;然后合并成一个文件后再次进行压缩&#xff0c;最终得到我们想要的结果&#xff0c;但这种先解压后压缩的方式显然效率不高&#xff0c;…
阅读更多...
监控Windows文件夹下面的文件(C#和C++实现)

监控Windows文件夹下面的文件(C#和C++实现)

最近在做虚拟打印机时&#xff0c;需要实时监控打印文件的到达&#xff0c;并移动文件到另外的位置。一开始我使用了线程&#xff0c;在线程里去检测新文件的到达。实际上Windows提供了一个文件监控接口函数ReadDIrectoryChangesW。这个函数可以对所有文件操作进行监控。 ReadD…
阅读更多...
1 深度学习网络DNN

1 深度学习网络DNN

代码来自B站up爆肝杰哥 测试版本 import torch import torchvisiondef print_hi(name):print(fHi, {name}) if __name__ __main__:print_hi(陀思妥耶夫斯基)print("HELLO pytorch {}".format(torch.__version__))print("torchvision.version:", torchvi…
阅读更多...
2024后端开发面试题总结

2024后端开发面试题总结

一、前言 上一篇离职贴发布之后仿佛登上了热门&#xff0c;就连曾经阿里的师兄都看到了我的分享&#xff0c;这波流量真是受宠若惊&#xff01; 回到正题&#xff0c;文章火之后&#xff0c;一些同学急切想要让我分享一下面试内容&#xff0c;回忆了几个晚上顺便总结一下&#…
阅读更多...
mybatis查询数据字段返回空值

mybatis查询数据字段返回空值

1.描述 数据苦衷实际存储字段全不为空 查询后brand_name/company_name为空 2.原因分析 带下划线的字段&#xff0c;都会返回空值&#xff0c;应该是字段映射出了问题 3.解决方案 在配置文件中添加下划线自动映射为驼峰 <configuration><settings><sett…
阅读更多...
【计算机网络】OSPF单区域实验

【计算机网络】OSPF单区域实验

一&#xff1a;实验目的 1&#xff1a;掌握在路由器上配置OSPF单区域。 2&#xff1a;学习OSPF协议的原理&#xff0c;及其网络拓扑结构改变后的变化。 二&#xff1a;实验仪器设备及软件 硬件&#xff1a;RCMS交换机、网线、内网网卡接口、Windows 2019操作系统的计算机等。…
阅读更多...
STM32+ESP8266-连接阿里云-物联网通用Android app（2）

STM32+ESP8266-连接阿里云-物联网通用Android app（2）

前言 接着上一篇的文章创建好了设备&#xff0c;云产品转发&#xff0c;让STM32连接上阿里云&#xff0c;发布和订阅了相关主题。本篇文章来编写一个Android app来进行控制STM32和接收传感器数据显示在屏幕上。基于Android studio。 演示视频 实现一个简单的app来控制stm32开…
阅读更多...
Django-3.3创建模型

Django-3.3创建模型

创建模型&#xff08;models&#xff09;的时候&#xff0c; 1&#xff1a;我们需要这个模型是哪个文件下面的模型&#xff08;models&#xff09;&#xff0c;我们需要在配置文件中吧应用安装上&#xff08;安装应用&#xff1a;INSTALLED_APPS&#xff09; 2&#xff1a;找对…
阅读更多...
【机器学习】不同操作系统下如何安装Jupyter Notebook和Anaconda

【机器学习】不同操作系统下如何安装Jupyter Notebook和Anaconda

引言 Jupyter Notebook 是一个非常流行的开源Web应用程序&#xff0c;允许你创建和共享包含代码、方程、可视化和解释性文本的文档 文章目录 引言一、如何安装Jupyter Notebook1.1 对于Windows用户1.2 对于macOS用户1.3 对于Linux用户&#xff1a; 二、如何安装Anaconda2.1 对于…
阅读更多...
《python程序语言设计》第6章13题 数列求和编写一个函数计算

《python程序语言设计》第6章13题 数列求和编写一个函数计算

正确代码 def sumNumber(integer_num):print(" i || m(i)")print("-"*30)a 0for i in range(1, integer_num 1):a i / (i 1)print("{:4d} || {:.4f}".format(i, a))sumNumber(20)结果如下
阅读更多...
使用 leanback 库 GridView 管理AnroidTV的焦点

使用 leanback 库 GridView 管理AnroidTV的焦点

一、前情提要 我当前需要开发一个TV应用&#xff0c;但是之前处理过的焦点问题的很少&#xff0c;现在空下来了&#xff0c;对过往的工作做一个总结分享。在手机APP开发中常用的 RecycleView 在 TV 中开发时&#xff0c;无法解决大量的焦点问题&#xff0c;所以使用leanback进…
阅读更多...
ElasticSearch核心之DSL查询语句实战

ElasticSearch核心之DSL查询语句实战

什么是DSL&#xff1f; Elasticsearch提供丰富且灵活的查询语言叫做DSL查询(Query DSL),它允许你构建更加复杂、强大的查询。 DSL(Domain Specific Language特定领域语言)以JSON请求体的形式出现。目前常用的框架查询方法什么的底层都是构建DSL语句实现的&#xff0c;所以你必…
阅读更多...
git 学习总结

git 学习总结

文章目录 一、 git 基础操作1、工作区2、暂存区3、本地仓库4、远程仓库 二、git 的本质三、分支git 命令总结 作者: baron 一、 git 基础操作 如图所示 git 总共有几个区域 工作区, 暂存区, 本地仓库, 远程仓库. 1、工作区 存放项目代码的地方&#xff0c;他有两种状态 Unm…
阅读更多...
2024新版 黑马程序员《C++零基础入门》笔记——第一章24 三元运算符

2024新版 黑马程序员《C++零基础入门》笔记——第一章24 三元运算符

1.三元运算符 2.代码实践 #include "iostream" using namespace std;int main() {// 表达式? v1 : v2;int num1, num2;cout << "请输入num1的值" << endl;cin >> num1;cout << "请输入num2的值" << endl;cin >…
阅读更多...
最新文章

Copyright @ 2022~2023