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

前言：前面我们实现了顺序表和单链表，这次来实现一个结构更复杂的链表-----带头双向循环链表。不要被它的名字吓到哦，只是结构复杂而已，它的结构更有利于代码的实现。

1 双向循环链表的介绍

有了单链表的基础，要实现这个双向循环带头链表其实并不难。下面我们先来了解一下什么是双向循环带头链表。

在这里插入图片描述

这就是双向循环带头链表的结构图，可以很清晰的看到，这个链表需要两个指针，一个指向后继结点，一个指向前驱节点，其次还需要一个头结点。只是这个头结点并不需要存储有效数据。

2 双向循环链表的实现

2.1 双向循环带头链表的定义

//存储的数据类型
typedef int LDataType;
//链表的定义
typedef struct ListNode
{LDataType val;struct ListNode* next;//指向后继节点struct ListNode* prev;//指向前驱节点
}LTNode;

2.2 双向循环带头链表的接口

//初始化双向循环带头链表‘
LTNode* ListInit();//打印
void ListPrint(plist);//尾插
void ListPushBack(LTNode* phead, LDataType x);//尾删
void ListPopBack(LTNode* phead);//头插
void ListPushFront(LTNode* phead, LDataType x);//头删
void ListPopFront(LTNode* phead);//查找
LTNode* ListFind(LTNode* phead, LDataType x);//pos位置之前插入
void ListInsert(LTNode* pos, LDataType x);//删除pos位置
void ListErase(LTNode* pos);//销毁链表
void ListDestroy(LTNode* phead);

2.2.1 初始化链表

//初始化双向循环带头链表
LTNode* ListInit()
{//哨兵位头结点LTNode* phead = (LTNode*)malloc(sizeof(LTNode));if (phead == NULL){printf("malloc fail\n");exit(-1);}phead->next = phead;phead->prev = phead;return phead;
}

在这里插入图片描述

2.2.2 创建新节点

//创建新节点
LTNode* BuyListNode(LDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->val = x;newnode->prev=newnode->next=NULL;return newnode;
}

2.2.3 链表尾插

//尾插
void ListPushBack(LTNode* phead, LDataType x)
{assert(phead);LTNode* tail = phead->prev;/*LTNode* newnode = (LTNode*)malloc(sizeof(LDataType));if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->val = x;*/LTNode* newnode = BuyListNode(x);newnode->next = phead;phead->prev = newnode;newnode->prev = tail;tail->next = newnode;
}

在这里插入图片描述

通过phead->prev就可以找到链表的尾节点，增加的节点newnode->prev
应该链接链表尾节点，链表的尾节点链接newnode,newnode->next应
该链接链表的头结点，链表的头结点的prev保存newnode的地址，使
newnode成为链表新的尾节点。

2.2.4 链表头插

//头插
void ListPushFront(LTNode* phead, LDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* pheadNext = phead->next;phead->next = newnode;newnode->prev = phead;pheadNext->prev = newnode;newnode->next = pheadNext;
}

在这里插入图片描述

先创建一个指针指向头结点的后继结点，再让newnode->next保存该
节点的地址，该节点的prev保存newnode的地址，phead->next保存
newnode的地址，newnode->prev保存头结点的地址。

2.2.5 链表尾删

//尾删
void ListPopBack(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;tailPrev->next = phead;phead->prev = tailPrev;free(tail);
}

在这里插入图片描述

通过phead->prev找到链表尾节点，再通过尾节点的prev找到尾节点
的前驱节点，让该前驱节点的next指向phead,phead->prev指向该前
驱节点，最后释放尾节点。

2.2.6 链表头删

//头删
void ListPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* head = phead->next;LTNode* next = head->next;next->prev = phead;phead->next = next;free(head);
}

在这里插入图片描述

首先通过phead->next找到链表头结点的后继结点，再通过该后继结点找到下一个节点，使该节点的prev保存头结点的地址，头结点的next保存该节点的地址，最后释放该后继结点。

2.2.7 链表的查找

//查找
LTNode* ListFind(LTNode* phead, LDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->val == x){return cur;}else{cur = cur->next;}}return NULL;
}

从头结点的后继结点开始遍历查找，找到了就返回该节点的地址，找不到返回NULL（当再一次遍历到头结点时，说明未找到）。

2.2.8 从pos位置之前插入

//pos位置之前插入
void ListInsert(LTNode* pos, LDataType x)
{assert(pos != NULL);LTNode* newnode = BuyListNode(x);LTNode* posPrev = pos->prev;posPrev->next = newnode;newnode->prev = posPrev;newnode->next = pos;pos->prev = newnode;
}

在这里插入图片描述

首先找到pos位置的前驱节点，再让newnode->prev指向该前驱节
点，该前驱节点的next指向newnode,pos->prev指newnode,
newnode->next指向pos。

2.2.9 删除pos位置

//删除pos位置
void ListErase(LTNode* pos)
{assert(pos != NULL);LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;posPrev->next = posNext;posNext->prev = posPrev;free(pos);
}

在这里插入图片描述

找到pos位置的前驱节点和后继结点，让该前驱节点的next指向该后
继结点，该后继结点的prev指向该前驱节点。

2.2.10 链表的打印

//打印
void ListPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){printf("%d ", cur->val);cur = cur->next;}printf("\n");
}

从头结点的后继结点开始遍历链表，当节点不是头结点时就打印该节点的值。

2.2.11 销毁链表

//销毁链表
void ListDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* tmp = cur;cur = cur->next;free(tmp);tmp = NULL;}cur = NULL;phead = NULL;
}

从头结点的后继结点开始销毁，先记录该后继结点的下一个节点，再销毁该后继结点。重复上述操作，直到再一次回到头结点的位置，此时销毁该头结点。

3 完整代码的实现

List.h文件

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LDataType;typedef struct ListNode
{LDataType val;struct ListNode* next;struct ListNode* prev;
}LTNode;//初始化双向循环带头链表‘
LTNode* ListInit();//打印
void ListPrint(plist);//尾插
void ListPushBack(LTNode* phead, LDataType x);//尾删
void ListPopBack(LTNode* phead);//头插
void ListPushFront(LTNode* phead, LDataType x);//头删
void ListPopFront(LTNode* phead);//查找
LTNode* ListFind(LTNode* phead, LDataType x);//pos位置之前插入
void ListInsert(LTNode* pos, LDataType x);//删除pos位置
void ListErase(LTNode* pos);//销毁链表
void ListDestroy(LTNode* phead);

List.c文件

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"//初始化双向循环带头链表
LTNode* ListInit()
{//哨兵位头结点LTNode* phead = (LTNode*)malloc(sizeof(LTNode));if (phead == NULL){printf("malloc fail\n");exit(-1);}phead->next = phead;phead->prev = phead;return phead;
}//打印
void ListPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){printf("%d ", cur->val);cur = cur->next;}printf("\n");
}//销毁链表
void ListDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* tmp = cur;cur = cur->next;free(tmp);tmp = NULL;}cur = NULL;phead = NULL;
}//创建新节点
LTNode* BuyListNode(LDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->val = x;//newnode->prev = newnode->next = NULL;return newnode;
}//尾插
void ListPushBack(LTNode* phead, LDataType x)
{assert(phead);LTNode* tail = phead->prev;/*LTNode* newnode = (LTNode*)malloc(sizeof(LDataType));if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->val = x;*/LTNode* newnode = BuyListNode(x);newnode->next = phead;phead->prev = newnode;newnode->prev = tail;tail->next = newnode;
}//尾删
void ListPopBack(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;//free(tail);tailPrev->next = phead;phead->prev = tailPrev;free(tail);
}//头插
void ListPushFront(LTNode* phead, LDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* pheadNext = phead->next;phead->next = newnode;newnode->prev = phead;pheadNext->prev = newnode;newnode->next = pheadNext;
}//头删
void ListPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* head = phead->next;LTNode* next = head->next;next->prev = phead;phead->next = next;free(head);
}//查找
LTNode* ListFind(LTNode* phead, LDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->val == x){return cur;}else{cur = cur->next;}}return NULL;
}//pos位置之前插入
void ListInsert(LTNode* pos, LDataType x)
{assert(pos != NULL);LTNode* newnode = BuyListNode(x);LTNode* posPrev = pos->prev;posPrev->next = newnode;newnode->prev = posPrev;newnode->next = pos;pos->prev = newnode;
}//删除pos位置
void ListErase(LTNode* pos)
{assert(pos != NULL);LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;posPrev->next = posNext;posNext->prev = posPrev;free(pos);
}

test.c文件

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"void ListTest1()
{LTNode* plist = ListInit();ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPushBack(plist, 5);ListPrint(plist);ListPopBack(plist);ListPopBack(plist);ListPrint(plist);ListPushFront(plist, 6);ListPushFront(plist, 7);ListPushFront(plist, 8);ListPushFront(plist, 9);ListPushFront(plist, 10);ListPrint(plist);ListPopFront(plist);ListPopFront(plist);ListPopFront(plist);ListPrint(plist);LTNode* pos = ListFind(plist, 2);if (NULL != pos){printf("找到了\n");}else{printf("找不到\n");}ListInsert(pos, 10);ListPrint(plist);pos = ListFind(plist, 1);ListErase(pos);ListPrint(plist);ListDestroy(plist);plist = NULL;//ListPrint(plist);}
int main()
{ListTest1();return 0;
}

4 顺序表与链表的对比

在这里插入图片描述

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

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

相关文章

10个最常用的Python包，程序员必备！

10个最常用的Python包，程序员必备！

世界上有超过200,000个Python程序包&#xff08;这只是基于官方的Python程序包索引PyPI托管的程序包&#xff09;。 这就引出了一个问题&#xff1a;拥有这么多的软件包&#xff0c;每个Python程序员都需要学习哪些软件包是最重要的&#xff1f; 为了帮助回答这个问题&#x…
阅读更多...
线上问题的排查-java死锁问题如何排查

线上问题的排查-java死锁问题如何排查

这里写目录标题 1.java死锁如何排查2.具体步骤1.1识别死锁现象1.2收集线程转储1.3分析线程转储1.4代码审查1.5重现问题1.6使用调试工具1.7.优化和验证 3. 解决方案总结 1.java死锁如何排查 在Java应用程序中&#xff0c;死锁是一个经典的并发问题&#xff0c;它会导致线程永久阻…
阅读更多...
shodan（4-5）

shodan（4-5）

以下笔记学习来自B站泷羽Sec&#xff1a; B站泷羽Sec 1. 查看自己的出口IP 可以知晓自己是哪个IP连接的公网 shodan myip2. 指定标题搜索 http.title:内容搜索被挂黑页的网页&#xff1a;获得标题中含有hacked by的IP shodan search --limit 10 --fields ip_str,port htt…
阅读更多...
三种风格截然不同的实验室工控界面

三种风格截然不同的实验室工控界面

三种风格截然不同的实验室工控界面各具特色。一种可能是简洁现代风&#xff0c;以简洁的线条、纯净的色彩和直观的图标&#xff0c;呈现出高效与专业。 另一种或许是科技未来风&#xff0c;运用炫酷的光影效果和立体感十足的设计&#xff0c;展现实验室的前沿科技感。 还有一…
阅读更多...
Redis如何保证数据不丢失（可靠性）

Redis如何保证数据不丢失（可靠性）

本文主要以学习为主&#xff0c;详细参考&#xff1a;微信公众平台 Redis 保证数据不丢失的主要手段有两个&#xff1a; 持久化 多机部署 我们分别来看它们两的具体实现细节。 1.Redis 持久化 持久化是指将数据从内存中存储到持久化存储介质中&#xff08;如硬盘&#xf…
阅读更多...
STM32F405RGT6单片机原理图、PCB免费分享

STM32F405RGT6单片机原理图、PCB免费分享

大学时机创比赛时画的板子&#xff0c;比到一半因为疫情回家&#xff0c;无后续&#xff0c;&#xff0c;&#xff0c;已打板验证过&#xff0c;使用stm32f405rgt6做主控 下载文件资源如下 原理图文件 pcb文件 外壳模型文件 stm32f405例程 功能 以下功能全部验证通过 4路…
阅读更多...
“穿梭于容器之间：C++ STL迭代器的艺术之旅”

“穿梭于容器之间：C++ STL迭代器的艺术之旅”

引言&#xff1a; 迭代器&#xff08;Iterator&#xff09;是C STL&#xff08;标准模板库&#xff09;中非常重要的一部分&#xff0c;它提供了一种统一的方式来遍历容器中的元素。无论容器是数组、链表、树还是其他数据结构&#xff0c;迭代器都能够以一致的方式访问这些数据…
阅读更多...
jmeter常用配置元件介绍总结之用linux服务器压测

jmeter常用配置元件介绍总结之用linux服务器压测

系列文章目录 安装jmeter jmeter常用配置元件介绍总结之用linux服务器压测 1.编写测试脚本2.执行测试脚本 1.编写测试脚本 在linux服务器上进行压测&#xff0c;由于是没有界面的&#xff0c;因此我们可以先在界面上把压测脚本写好&#xff1a; 如图&#xff1a;我这里简单的写…
阅读更多...
Ubuntu 的 ROS 操作系统安装与测试

Ubuntu 的 ROS 操作系统安装与测试

引言 机器人操作系统&#xff08;ROS, Robot Operating System&#xff09;是一个用于开发机器人应用的开源框架&#xff0c;它提供了一系列功能丰富的库和工具&#xff0c;能够帮助开发者构建和控制机器人。 当前&#xff0c;ROS1的最新版本为Noetic Ninjemys&#xff0c;专为…
阅读更多...
计算机组成原理——编码与纠错（汉明编码）

计算机组成原理——编码与纠错（汉明编码）

校验码放在2^x次方的位置——即1&#xff0c;2&#xff0c;4——将检测位按序排列p3p2p1 汉明编码从左到右数某个位置位1&#xff08;位数&#xff09;&#xff0c;就表示第几组 奇偶校验 例题 纠错过程 汉明编码的最小距离是3
阅读更多...
fabric操作canvas绘图(1)共32节

fabric操作canvas绘图(1)共32节

对于前端而言&#xff0c;离不开canvas就像鱼离不开水&#xff0c;前端canvas神器fabric你值得拥有&#xff01;接下来我们就来一步步揭开她的面纱。 一、fabric的理解 用原生的canvas来实现&#xff0c;代码量会比较大&#xff0c;而且还要处理很多细节&#xff0c;而Fabric…
阅读更多...
C++ 内存分布及 new , delete 分配问题( ~~~ 面试重要 ~~~)

C++ 内存分布及 new , delete 分配问题( ~~~ 面试重要 ~~~)

文章目录 前言一、内存分布二、new 、delete 分配问题总结 前言 本篇文章笔者将会对 C 中的内存问题简单的讲解 , 同时对 new , delete 的面试题进行重点讲解. 一、内存分布 ● C语言和C 分布情况是一样的, 如下 : ● 栈 ○ 栈 的管理是由编译器自动管理 , 不需要我们人为做…
阅读更多...
数据结构-哈夫曼树

数据结构-哈夫曼树

一.什么是哈夫曼树 不同搜索树的效率是不一样的,根据不同的频率构造效率比较好或者最好的搜索树就是哈夫曼树 二.哈夫曼树的定义 将带权路径的长度降低最低 每个叶子节点到根节点的距离乘权值&#xff0c;再全都加起来就得到了WPL值 第一颗二叉树:从上到下计算 5x14x23x32x41…
阅读更多...
双11精选网络安全书单：打造数字世界的钢铁长城！

双11精选网络安全书单：打造数字世界的钢铁长城！

&#x1f91f; 基于入门网络安全/黑客打造的&#xff1a;&#x1f449;黑客&网络安全入门&进阶学习资源包 &#x1f31f;双11火热来袭&#xff0c;网络安全书单推荐&#x1f680; 随着数字化浪潮的汹涌澎湃&#xff0c;网络安全已经成为了每个从业者不可回避的重要议…
阅读更多...
WebGUI之Gradio：Gradio 5的简介、安装和使用方法、案例应用之详细攻略

WebGUI之Gradio：Gradio 5的简介、安装和使用方法、案例应用之详细攻略

WebGUI之Gradio&#xff1a;Gradio 5的简介、安装和使用方法、案例应用之详细攻略 目录 Gradio 5的简介 1、Gradio的适用场景 2、Gradio 5 的主要改进包括&#xff1a; Gradio 5的安装和使用方法 1、安装和使用方法 2、使用方法 2.1、文本内容 (1)、简单的输入/输出组件…
阅读更多...
初始Python篇（5）—— 集合

初始Python篇（5）—— 集合

找往期文章包括但不限于本期文章中不懂的知识点&#xff1a; 个人主页&#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 所属专栏&#xff1a; Python 目录 集合 相关概念 集合的创建与删除 集合的操作符 集合的相关操作方法 集合的遍历 集合生成式 列表、元组、字典、集合的…
阅读更多...
探索Python的Shell力量：Plumbum库揭秘

探索Python的Shell力量：Plumbum库揭秘

文章目录 探索Python的Shell力量&#xff1a;Plumbum库揭秘第一部分&#xff1a;背景介绍第二部分&#xff1a;Plumbum是什么&#xff1f;第三部分&#xff1a;如何安装Plumbum&#xff1f;2. 创建管道3. 重定向4. 工作目录操作5. 前台和后台执行 第五部分&#xff1a;场景应用…
阅读更多...
大模型时代，算法岗到底哪个最有前景？什么样的算法工程师更吃香？

大模型时代，算法岗到底哪个最有前景？什么样的算法工程师更吃香？

毫无疑问&#xff0c;全栈型的算法工程师将更为抢手&#xff0c;如果你精通大模型从训练到应用的整个流程&#xff0c;你走到哪里都不怕。 但往往人的精力有限&#xff0c;如果从数据、预训练、微调、对齐、推理、应用几个方面来看的话&#xff0c;个人觉得 “预训练>数据&…
阅读更多...
Linux系统之sleep命令的基本使用

Linux系统之sleep命令的基本使用

Linux系统之sleep命令的基本使用 一、sleep命令介绍二、sleep的使用帮助2.1 查看帮助信息2.2 基本语法 三、sleep命令的基本使用3.1 指定暂停时间长度3.2 结合多个时间单位 四、在脚本中应用五、注意事项 一、sleep命令介绍 sleep命令是一个在Unix和类Unix操作系统中常见的命令…
阅读更多...
《Java核心技术 卷I》Swing处理2D图形

《Java核心技术 卷I》Swing处理2D图形

处理2D图形 Java1.0开始&#xff0c;Graphics类就包含绘制直线、矩形和椭圆等方法&#xff0c;但是绘制图形的操作能力有限&#xff0c;我们将使用Java2D的图形库。想绘制需要获得Graphics2D类的一个对象&#xff0c;是Graphics的子类。paintCompoent方法接收一个2D类对象&…
阅读更多...
最新文章

Copyright @ 2022~2023