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

文章目录

    • 一.头结点
    • 二.双链表
      • 1·双链表的概念与结构
      • 2.与单链表相比
    • 三.循环链表
      • 1.关于循环链表
      • 2.循环链表的优点
    • 四.带头双向循环链表
      • 1.带头双向循环链表
      • 2.结构图
      • 3.实现
    • 五.代码一览

一.头结点

在链表中设置头结点的作用是什么

标识链表:头结点是链表的特殊节点,它的存在能够明确标识出这是一个链表。在链表中,头结点通常不包含任何数据,它的主要作用是作为链表的入口,使得链表的操作更加方便。
简化操作:头结点的存在可以简化链表的操作。例如,当我们需要遍历整个链表时,只需要从头结点开始即可,无需关心链表的起始位置。同时,头结点的存在也使得在链表末尾插入或删除节点等操作更加方便。
提高效率:头结点的存在可以提高链表操作的效率。由于头结点是链表的第一个节点,因此在遍历链表时,我们无需担心指针的移动方向问题。同时,由于头结点在链表中的特殊位置,当需要访问链表的第一个元素时,可以通过直接访问头结点来获取,无需遍历整个链表。

在这里插入图片描述

二.双链表

1·双链表的概念与结构

概念：双链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针双向链接次序实现的。

结构图：
在这里插入图片描述

2.与单链表相比

双向性:双链表支持在每个节点上存储前驱节点和后继节点的指针,使得在任何节点上都可以方便地找到其前驱节点和后继节点。而单链表只能通过遍历整个链表来查找特定节点的下一个节点或上一个节点,效率较低。
插入和删除操作更高效:由于双链表支持双向链接,因此在插入和删除操作中,双链表只需要重新调整相关的指针即可,而不需要像单链表那样需要遍历整个链表。这使得双链表的插入和删除操作更高效。

三.循环链表

1.关于循环链表

循环链表是一种特殊的链表，其中最后一个节点指向第一个节点，即起始节点。起始节点充当列表开头的参考点。

（1）遍历时，可以从任何节点开始并以任何方向向前或向后遍历列表，直到到达开始的同一节点。
（2）循环链表没有开始也没有结束。
（3）在循环链表中，最后一个节点地址部分保存第一个节点的地址，从而形成一个循环链状结构。

（4）.结构图：
在这里插入图片描述

2.循环链表的优点

（1）内存利用率是循环链表的共同优势之一
与线性数据结构不同，循环链表可以让人有效地使用内存，因为链表的大小动态增加或减少，因此不会浪费内存。此外，无需预先分配内存。
（2）实施
由于能够利用内存和易于数据操作，像堆栈和队列这样的线性数据结构通常可以使用链表轻松实现。
（3）易于数据操作
可以有效地处理循环链表的插入和删除，而无需重新构造链表。插入或删除元素后无需移动元素，只需更新下一个指针中存在的地址。

四.带头双向循环链表

1.带头双向循环链表

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

2.结构图

在这里插入图片描述

3.实现

思路：
（1）利用结构体存储数据和指针（结构体能够存储不同类型的数据）
（2）通过malloc函数进行扩容
（3）通过多条件实现
（4）我们实现初始化、打印、扩容、尾插、头插等函数
框架：
结构体的创建、一些定义等
List.h

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int LTDataType;

typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}ListNode;

Test.c

void Test() {
	ListNode* plist = ListInit()初始化，头结点不存储数据;
	}
int main() {
	Test();
	return 0;
}

函数实现：
（1）扩容函数：
返回值：一个结构体指针
参数：传来的数据
通过malloc函数实现扩容，并将扩容后的指针置空和存储传来的数据
代码：

ListNode* BuyListNode(LTDataType x) {//扩容
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));//扩容
	newnode->data = x;//存储数据
	newnode->next = NULL;//指针置空
	newnode->prev = NULL;
	return newnode;//返回指针
}

（2）初始化函数
我们开始要初始化一个头结点（不存储数据）
返回：一个指针（我们的头结点）
代码：

ListNode* ListInit() {//初始化
	ListNode* phead = BuyListNode(0);//第一个数据不打印
	phead->next = phead;//只有一个头结点，因为是双向循环链表，自己连接自己
	phead->prev = phead;
	return phead;
}

如图：
在这里插入图片描述
打印函数
代码：

void ListPrint(ListNode* phead) {
	assert(phead);//判断是否为空
	//初始条件
	ListNode* cat = phead->next;//打印出头结点next指向的结构体开始
	//结束条件
	while (cat!= phead)//当打印完一次后就会遇上同结点，此时结束打印
	{
		printf("%d ", cat->data);
		//迭代条件
		cat = cat->next;
	}
	printf("\n");
}

（3）尾插函数
我们要将一个数据尾插进去
第一步：找到这个链表的结尾处，我们可以通过头结点找到
第二步：我们重新将结尾处结构体的next指向尾插进来的结构体，再将尾插进来的结构体的prev指向结尾处的结构体，再再将尾插进来的结构体的next指向头结点，再再再将头结点的perv指向尾插进来的结构体
插前：
在这里插入图片描述
插后：
在这里插入图片描述
代码：

void ListPushBack(ListNode* phead, LTDataType x) {//尾插
	assert(phead);//判断是否为空
	ListNode* newnode = BuyListNode(x);//扩容
	ListNode* cat = phead->prev;//找到尾结点并保存
	//重新连接
	cat->next = newnode;
	newnode->prev = cat;
	phead->prev = newnode;
	newnode->next = phead;
}

检查：
尾插 1 、2 、3

ListNode* plist = ListInit();
ListPushBack(plist, 1);
ListPushBack(plist, 2);
ListPushBack(plist, 3);

运行结果：
在这里插入图片描述
（4）头插函数
我们要将一个数据尾插进去
第一步：通过头结点找到第一个存储数据的点
第二步：我们重新将第一存储数据的结点处结构体的prev指向头插进来的结构体，再将头插进来的结构体的next指向第一个存储数据的结构体，再再将头插进来的结构体的prtv指向头结点，再再再将头结点的next指向头插进来的结构体

插前：
在这里插入图片描述
插后：
在这里插入图片描述
代码：

void ListPushFront(ListNode* phead, LTDataType x) {//头插
	assert(phead);
	ListNode* newnode = BuyListNode(x);
	ListNode* cat = phead->next;//找到头结点并保存
	//重新连接
	cat->prev = newnode;
	newnode->next = cat;
	phead->next = newnode;
	newnode->prev = phead;
}

检查：

头插 0
ListNode* plist = ListInit();
ListPushBack(plist, 1);
ListPushBack(plist, 2);
ListPushBack(plist, 3);
ListPushFront(plist, 0);

运行结果：
在这里插入图片描述
（5）头删函数
我们想要删除第一个数据
第一步：通过头结点找到第一个存储数据的结点，再通过第一个存储数据的结点来找到第二个存储数据的结点
第二步：将第一个存储数据的结点释放掉，然后再将第二个存储数据的结点的prev指向头结点，再再头结点的next指向第二个存储数据的结点
删前：
在这里插入图片描述
删后：
在这里插入图片描述

代码：

void ListPopFront(ListNode* phead) {//头删
	assert(phead);
	assert(phead->next != phead);//
	ListNode* cat = phead->next->next;
	//通过第一个存储结点找到第二个存储的结点并保存
	free(phead->next);//释放掉
	phead->next = NULL;//并置空
	//重新连接
	cat->prev = phead;
	phead->next = cat;
	
}

检查：
头删一个数据

ListNode* plist = ListInit();
ListPushBack(plist, 1);
ListPushBack(plist, 2);
ListPushBack(plist, 3);
ListPushFront(plist, 0);
ListPopFront(plist);

运行结果：

在这里插入图片描述
（6）尾删函数
我们将最后一个结点删除
第一步：通过头结点来找到最后一个结点，再通过最后一个结点来找到倒数第二个结点
第二步：将最后一个结点释放掉，再将倒数第二个结点的next指向头结点，再再将头结点的prev指向倒数第二个结点
删前：
在这里插入图片描述
删后：
在这里插入图片描述
检查
尾删一个数据

ListNode* plist = ListInit();
ListPushBack(plist, 1);
ListPushBack(plist, 2);
ListPushBack(plist, 3);
ListPushFront(plist, 0);
ListPopFront(plist);
ListPopBack(plist);
ListPrint(plist);

运行结果：
在这里插入图片描述

五.代码一览

List.h：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int LTDataType;

typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}ListNode;

ListNode* ListInit();//初始化
void ListDestory(ListNode* phead);//清空
void ListPrint(ListNode* phead);//打印

void ListPushBack(ListNode* phead, LTDataType x);//尾插
void ListPushFront(ListNode* phead, LTDataType x);//头插
void ListPopFront(ListNode* phead);//头删
void ListPopBack(ListNode* phead);//尾删

List.c：

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"

ListNode* BuyListNode(LTDataType x) {//扩容
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

ListNode* ListInit() {//初始化
	ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

void ListPrint(ListNode* phead) {
	assert(phead);
	//初始条件
	ListNode* cat = phead->next;
	//结束条件
	while (cat!= phead)
	{
		printf("%d ", cat->data);
		//迭代条件
		cat = cat->next;
	}
	printf("\n");
}
void ListPushBack(ListNode* phead, LTDataType x) {//尾插
	assert(phead);
	ListNode* newnode = BuyListNode(x);
	ListNode* cat = phead->prev;
	cat->next = newnode;
	newnode->prev = cat;
	phead->prev = newnode;
	newnode->next = phead;
}
void ListPushFront(ListNode* phead, LTDataType x) {//头插
	assert(phead);
	ListNode* newnode = BuyListNode(x);
	ListNode* cat = phead->next;
	cat->prev = newnode;
	newnode->next = cat;
	phead->next = newnode;
	newnode->prev = phead;
}
void ListPopFront(ListNode* phead) {//头删
	assert(phead);
	assert(phead->next != phead);
	ListNode* cat = phead->next->next;
	free(phead->next);
	phead->next = NULL;
	cat->prev = phead;
	phead->next = cat;
	
}
void ListPopBack(ListNode* phead) {//尾删
	assert(phead);
	assert(phead->prev != phead);
	ListNode* cat = phead->prev->prev;
	free(phead->prev);
	phead->prev = NULL;
	cat->next = phead;
	phead->prev = cat;
}

Test.c

void Test() {
	ListNode* plist = ListInit();
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushFront(plist, 0);
	ListPopFront(plist);
	ListPopBack(plist);
	ListPrint(plist);
	}

	int main() {
	Test();
	return 0;
}

以上就是全部代码了
还有一些查改等接口函数没实现，感兴趣的可以去试试

以上就是我的分享了，如果有什么错误，欢迎在评论区留言。
最后，谢谢大家的观看！

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

JS初步了解this

JS初步了解this

什么是环境对象&#xff1f; 环境对象&#xff1a;指的是函数内部特殊的变量this&#xff0c;它代表着当前函数运行时所处的环境 作用&#xff1a;弄清楚this的指向&#xff0c;可以让我们代码更简洁 在普通函数中&#xff1a; // 每个函数里面都有this 普通函数的this指向wind…
阅读更多...
rcssci包横空出世，限制性立方样条全自动切点靓图

rcssci包横空出世，限制性立方样条全自动切点靓图

z致敬前辈:R语言统计与绘图 仅以本篇2800字真文一并纪念工作11年来潦倒的收入、间歇的鸡血、憋屈的倔强、幽暗的过往和心中的远方。 1 缘起 Restricted cubic splines (RCS)近年来火遍各类SCI期刊&#xff0c;初次接触的小伙伴们可以去搜索笔者前期的2篇RCS文章补充一下基础知…
阅读更多...
6.5 Windows驱动开发：内核枚举PspCidTable句柄表

6.5 Windows驱动开发：内核枚举PspCidTable句柄表

在 Windows 操作系统内核中&#xff0c;PspCidTable 通常是与进程&#xff08;Process&#xff09;管理相关的数据结构之一。它与进程的标识和管理有关&#xff0c;每个进程都有一个唯一的标识符&#xff0c;称为进程 ID&#xff08;PID&#xff09;。与之相关的是客户端 ID&am…
阅读更多...
（C语言）求出1,2,5三个数不同个数组合为100的组合个数

（C语言）求出1,2,5三个数不同个数组合为100的组合个数

#include<stdio.h> int main() {int count;for(int i 0;i < 100;i )for(int j 0;j < 50;j )for(int k 0;k < 20;k ){if(i j*2 k*5 100){count;printf("100可以拆分为%d个1元&#xff0c;%d个2元&#xff0c;%d个5元\n",i,j,k);} }printf("…
阅读更多...
2023年度端侧transformer类分类力作SwiftFormer模型解读

2023年度端侧transformer类分类力作SwiftFormer模型解读

写在前面&#xff1a;本篇直接结合代码来理解网络的笔记 paper: Swiftformer-paper code: https://github.com/Amshaker/SwiftFormer 文章目录 网络结构精析零、整体一、patch embed二、stage 网络结构精析 零、整体 可以看到结构中&#xff0c;整体就是&#xff1a; stem -&…
阅读更多...
洗地机哪个牌子好用？洗地机希亦、石头、添可、西屋谁的清洁力更强？

洗地机哪个牌子好用？洗地机希亦、石头、添可、西屋谁的清洁力更强？

洗地机的出现极大地改善了清洁过程&#xff0c;提高了效率&#xff0c;减少了人力投入。但随着市场上洗地机的种类和功能不断增加&#xff0c;人们可能会感到困惑&#xff0c;不知道如何选择适合自己需求的机器。为了帮助消费者更好地了解洗地机的选择&#xff0c;今天我将带大…
阅读更多...
从Intel Cyclone10GX TransceiverPHY 高速收发器认识ATX PLL、FPLL、CMU PLL等PLL

从Intel Cyclone10GX TransceiverPHY 高速收发器认识ATX PLL、FPLL、CMU PLL等PLL

文章目录 前言一、pandas是什么&#xff1f;二、使用步骤 1.引入库2.读入数据总结 前言 在使用Intel Cyclone10GX TransceiverPHY的过程中发现这个IP还是比较复杂的&#xff0c;特别是时钟系统&#xff0c;提到了多种PLL:ATX PLL、FPLL、CMU PLL&#xff0c;这里进行一下扩展学…
阅读更多...
vue3项目打包发布到apache服务器的流程

vue3项目打包发布到apache服务器的流程

vue3项目打包发布到apache服务器的流程&#xff08;不包含开机自启动apache&#xff09; 1. 下载部署apache服务器 打开apache官网https://www.apachelounge.com/download/ 下载windows的apache版本。 2. 在本地的E盘新建一个文件http&#xff0c;把下载好的apache解压放进…
阅读更多...
时间选择器

时间选择器

<el-form-item label"时间范围"><!-- <el-date-picker size"small"v-model"createTime"type"daterange"range-separator"至"start-placeholder"请输入起始创建时间"end-placeholder"请输入终止创…
阅读更多...
【C语言：自定义类型（结构体、位段、共用体、枚举）】

【C语言：自定义类型（结构体、位段、共用体、枚举）】

文章目录 1.结构体1.1什么是结构体1.2结构体类型声明1.3结构体变量的定义和初始化1.4结构体的访问 2.结构体对齐2.1如何对齐2.2为什么存在内存对齐&#xff1f; 3.结构体实现位段3.1什么是位段3.2位段的内存分配3.3位段的跨平台问题3.4位段的应用3.5位段使用注意事项 4.联合体4…
阅读更多...
vmware ubuntu22 访问github

vmware ubuntu22 访问github

1.虚拟机选NAT模式。 2.firefox找到下图setting。 3.选第四个&#xff0c;填主机ip和局域网代理的端口号。 4. 此时你应该能访问github了。
阅读更多...
外包测试8个月，技术退步有点明显···

外包测试8个月，技术退步有点明显···

有一说一&#xff0c;外包没有给很高的薪资&#xff0c;是真不能干呀&#xff01; 先说一下自己的情况&#xff0c;本科生&#xff0c;年初通过校招进入深圳某软件公司&#xff0c;干了接近半年的功能测试&#xff0c;直到最近遇到了瓶颈&#xff0c;感觉自己不能够在这样下去了…
阅读更多...
TrustZone之虚拟地址空间

TrustZone之虚拟地址空间

在本系列中的内存管理指南介绍了多个虚拟地址空间或translation regimes的概念。例如&#xff0c;有一个用于EL0/1的translation regime&#xff0c;还有一个用于EL2的独立translation regime&#xff0c;如下所示&#xff1a; 还有专门的翻译方案用于安全状态和非安全状态。例…
阅读更多...
麒麟系统图形化应用自启

麒麟系统图形化应用自启

1.图形化自启动 XDG_Autostart 规范定义了一种通过将其放置在特定中来在桌面环境启动和 可移动介质安装中自动启动普通桌面配置的方法。 ⚫ 用户级别$XDG_CONFIG_HOME/autostart (默认为~/.config/autostart) ⚫ 系统级别$XDG_CONFIG_DIRS/autostart (默认为 /etc/xdg/autost…
阅读更多...
12.1 二叉树简单题

12.1 二叉树简单题

101. 对称二叉树 给你一个二叉树的根节点 root &#xff0c; 检查它是否轴对称。 示例 1&#xff1a; 输入&#xff1a;root [1,2,2,3,4,4,3] 输出&#xff1a;true 思路&#xff1a;对称二叉树 有一个特点是以 中左右顺序遍历左子树的结果会等于 中右左顺序遍历右子树的结果…
阅读更多...
检测判断IP合法性API接口

检测判断IP合法性API接口

检测判断IP合法性API接口 一、检测判断IP合法性API接口二、使用步骤1、接口2、请求参数3、请求参数示例4、接口 返回示例 三、 如何获取appKey和uid1、申请appKey:2、获取appKey和uid 四、重要说明 一、检测判断IP合法性API接口 一款免费的帮助你检测判断IP合法性API接口 二、…
阅读更多...
shiny的图片如何插入，为什么会裂开？

shiny的图片如何插入，为什么会裂开？

因为你没有把资源放在内部&#xff1a; Shiny学习(二) ||构建用户界面 - 简书d 当然也有例外比如&#xff1a; shiny-如何在 Shinydashboard R 中 dashboard 标题的中心显示图像&#xff1f; - 糯米PHP
阅读更多...
河北科技大学2024招生简章

河北科技大学2024招生简章

河北科技大学2024招生简章 计算机专业目录 计算机专业参考书目 408计算机学科专业基础 无指定参考书&#xff0c;考试内容参考教育部公布的《全国硕士研究生招生考试计算机学科专业基础考试大纲》 计算机控制技术 《微型计算机控制技术》&#xff0c;赖寿宏&#xff0c;机械…
阅读更多...
DDD落地：京东的微服务生产项目，DDD如何落地？

DDD落地：京东的微服务生产项目，DDD如何落地？

尼恩说在前面 在40岁老架构师 尼恩的读者交流群(50)中&#xff0c;最近有小伙伴拿到了一线互联网企业如阿里、滴滴、极兔、有赞、希音、百度、网易、美团的面试资格&#xff0c;遇到很多很重要的面试题&#xff1a; 谈谈你的DDD落地经验&#xff1f; 谈谈你对DDD的理解&#x…
阅读更多...
Web漏洞分析-SQL注入XXE注入（中下）

Web漏洞分析-SQL注入XXE注入（中下）

随着互联网的不断普及和Web应用的广泛应用&#xff0c;网络安全问题愈发引起广泛关注。在网络安全领域中&#xff0c;SQL注入和XXE注入是两个备受关注的话题&#xff0c;也是导致许多安全漏洞的主要原因之一。本博客将深入研究这两种常见的Web漏洞&#xff0c;带您探寻背后的原…
阅读更多...
最新文章

Copyright @ 2022~2023