链表的极致——带头双向循环链表

​

文章目录

  • 双向带头循环链表简介：
    • 双向：
    • 带头：
      • 特点：
      • 链表带头节点的好处：
    • 循环：
      • 特点：
      • 循环的好处：
  • 双向带头循环链表的接口函数实现
    • 准备工作：
  • 初始化链表（头结点）
  • 尾插
    • 参数设计
    • 图解
  • 打印链表
    • 图解
  • 头插
    • 图解
  • 尾删
    • 图解
  • 头删
    • 图解
  • 查找
  • 随机插入
    • 图解
  • 随机删除
    • 图解
  • 销毁链表
    • 图解
  • 全部代码
    • SList.h
    • SList.c

双向带头循环链表简介：

双向带头循环链表是链表结构最复杂，但使用最方便的链表。
在这里插入图片描述

[图中phead表示链表的头节点（哨兵）;

d1，d2等表示链表存储的数据；

d1，d2等左侧的方框存储是指向该节点的上一个节点的指针（prev），右侧方框存储指向该节点的下一个的指针（next）]

双向：

双向带头循环链表的每一个节点的指针域都有俩个指针，一个指针（prev）指向该节点的前一个节点，一个指针（next）指向它的后一个节点。
解决了单链表只能向后访问，不能向前访问的问题

带头：

特点：

  1. 双向带头循环链表的头节点（哨兵）位于第一个存储数据的链表的前一个结点

  2. 双向带头循环链表有一个头节点（哨兵），该节点无论链表是否为空它都存在

  3. 头节点（哨兵）的数据域一般不存储数据或者存储链表的信息（有几个节点等）

  4. 双向带头循环链表的头节点（哨兵）指针域的也有两个指针，且指向前一个节点的指针（prev）指向链表的最后一个节点，指向下一个节点的指针（next）指向链表的第一个节点

链表带头节点的好处：

  1. 由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个节点上的操作就和在表的其它位置上操作一致,无须对链表的第一个节点进行进行特殊处理。 不会再改变链表phead指向的位置，也就不用再函数传参时有时传phead，有时传*phead，让链表的接口函数的参数类型也统一了。
  2. 无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表的处理也就统一了，不需要再分情况。

循环：

特点：

  1. 双向带头循环链表的最后一个节点的指向下一个节点的指针（next）指向头节点（哨兵）
  2. 头节点（哨兵）的指向上一个节点的指针（prev）指向链表的最后一个节点
  3. 当链表为空时，只有头节点（哨兵），此时头节点（哨兵）的prev指向它自己，它的next也指向它自己

循环的好处：

  1. 尾插时不用遍历找链表的最后一个节点（尾节点），因为指向双向带头循环链表的最后一个的节点的指针被存放在头节点（哨兵）的prev中。
  2. 在进行删除操作后，能保证链表不断开
  3. 从链表中任意结点出发都能遍历整个链表。
  4. 可以实现循环遍历，即在遍历到链表末尾后能够自动回到链表头部进行下一轮遍历。

双向带头循环链表的接口函数实现

准备工作：

创建一个头文件（SList.h）两个源文件（SList.c和test.c）

  • SList.h:用于包含库函数的头文件，链表节点结构体声明，接口函数的声明等【另外两个源文件要包含SList.h这个头文件，才能使用其中的声明】
  • SList.h：用于实现单链表的接口函数
  • test.c:存放main函数，用于链表的测试

在这里插入图片描述

上图包含了以下3个操作

1.库函数的头文件的包含：

stdio.h:输入/输出等函数
stdlib.h:动态内存申请
assert.h:报错函数assert
2.给链表节点的数据域的数据类型重命名
为什么要重命名呢？
这是为了以后如果改变了LTNoed结构体中数据存储的类型时，
不用到处改函数参数等地方的数据类型，只要改typedef后的int 为对应要改成的数据类型就可以。

3.链表节点结构体定义和重命名

初始化链表（头结点）

在这里插入图片描述
参数设计：
无需参数，将返回值赋值给一个指针，这个指针就成为链表的phead。

尾插

在这里插入图片描述

参数设计

LTNode*phead:
上面说了因为头指针（phead）不会改变，所以传一级指针phead即可

LTDaType x：
要插入的数据

图解

在这里插入图片描述
链表为空的时候也不需要像单链表那样特殊考虑，这也是双向带头循环链表的好处

打印链表

在这里插入图片描述

图解

在这里插入图片描述

头插

在这里插入图片描述

图解

在这里插入图片描述

尾删

在这里插入图片描述

图解

在这里插入图片描述

头删

在这里插入图片描述

图解

在这里插入图片描述

查找

在这里插入图片描述

随机插入

在这里插入图片描述
随机插入的pos要配合查找函数的返回值使用·

图解

在这里插入图片描述

随机删除

在这里插入图片描述

图解

在这里插入图片描述

销毁链表

在这里插入图片描述

图解

在这里插入图片描述

全部代码

SList.h

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int LTDateType;

typedef struct LTNode
{
	LTDateType data;
	struct LTNode* next;
	struct LTNode* prev;
}LTNode;

//初始化链表
LTNode* ListInit(void);
//打印链表
void ListPrint(LTNode* phead);
//尾插
void ListPushBack(LTNode* phead, LTDateType x);
//头插
void ListPushFront(LTNode* phead, LTDateType x);
//尾删
void ListPopBack(LTNode* phead);
//头删
void ListPopFront(LTNode* phead);
//查找x,找到了返回指向x的结构指针，找不到返回NULL
LTNode* ListFind(LTNode* phead, LTDateType x);
//在pos之前插入数据
void ListInsert(LTNode* phead, LTNode* pos, LTDateType x);
//删除pos指向的节点
void ListEase(LTNode* phead, LTNode* pos);
//销毁链表
void ListDestory(LTNode* phead);

SList.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"

LTNode* ListInit()
{
	//哨兵位头节点
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));//为头结点申请空间

	phead->data = 0;//不存储链表数据（链表的长度等）时也可不初始化

	phead->next = phead;//链表为空时头结点的next指向自己
	phead->prev = phead;//链表为空时头结点的prev也指向自己

	return phead;//返回被一个节点（phead）接收
}

void ListPushBack(LTNode* phead, LTDateType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//为新节点申请空间
	if (newnode == NULL)//如果为新节点申请空间失败
	{
		printf("malloc失败");
		exit(-1);//结束程序，-1表示程序非正常结束
	}
	LTNode* tail = phead->prev;//tail指向链表的最后一个节点

	tail->next = newnode;//让新节点成为原尾节点的下一个节点

	newnode->prev = tail;//让原尾节点成为新节点的上一个节点

	phead->prev = newnode;//更新头结点中存储的尾节点

	newnode->next = phead;//让新节点的下一个节点为头结点（phead）

	newnode->data = x;//存储数据
}

void ListPrint(LTNode* phead)
{
	LTNode* cur = phead->next;//将链表的第一个节点赋值给cur

	while (cur != phead)//因为双向带头循环链表没有指向NULL的指针了，而且链表的尾节点的next指向头结点（phead）
		                //所以遍历链表结束的条件为cur==phead
	{
		printf("%d  ", cur->data);//打印节点数据域的数据
		cur = cur->next;//让cur指向下一个节点
	}
}

//头插
void ListPushFront(LTNode* phead, LTDateType x)
{
	LTNode* cur = phead->next;//让cur指向链表的第一个节点
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//为新节点申请空间

	if (newnode == NULL)//如果为新节点申请空间失败
	{
		printf("malloc失败");
		exit(-1);//结束程序，-1表示程序非正常结束
	}
	phead->next = newnode;//让头结点的下一个节点为新节点

	newnode->next = cur;//让新节点的下一个节点为原链表的第一个节点

	newnode->prev = phead;//让新节点的上一个节点为头结点

	newnode->data = x;

	cur->prev = newnode;//让原链表的第一个节点的上一个节点为新节点
}
//尾删
void ListPopBack(LTNode* phead)
{
	assert(phead->next != phead);//链表为空时不能再删除

	LTNode* tail = phead->prev;//让tail指向尾节点

	tail->prev->next = phead;//让尾节点（tail）的前一个节点的next指向头结点，

	phead->prev = tail->prev;//让删除之前的尾节点的前一个节点成为新的尾节点

	free(tail);//释放删除之前的尾节点
}
//头删
void ListPopFront(LTNode* phead)
{
	assert(phead->next != phead);//链表为空时不能再删除

	LTNode* cur = phead->next;//让cur指向链表的第一个节点

	phead->next = cur->next;//让头节点的下一个节点为原链表第一个节点的下一个节点（原链表的第二个节点）

	cur->next->prev = phead;//让原链表的第二个节点的前一个节点为头结点

	free(cur);//释放原链表第一个节点
}
//查找x,找到了返回指向x的结构指针，找不到返回NULL
LTNode* ListFind(LTNode* phead, LTDateType x)
{
	LTNode* cur = phead->next;//让cur指向链表的第一个节点

	while (cur != phead)//因为双向带头循环链表没有指向NULL的指针了，而且链表的尾节点的next指向头结点（phead）
		                //所以遍历链表结束的条件为cur==phead
	{
		if (cur->data == x)
		{
			return cur;//找到了就直接返回
		}
		else
		{
			cur = cur->next;//让cur指向下一个节点
		}
	}
	return NULL;//找不到就返回NULL
}

//在pos之前插入数据
void ListInsert(LTNode** phead, LTNode* pos, LTDateType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)//如果为新节点申请空间失败
	{
		printf("malloc失败");
		exit(-1);//结束程序，-1表示程序非正常结束
	}
	newnode->data = x;//存放数据

	newnode->next = pos;//让新节点的下一个节点为pos指向的节点

	newnode->prev = pos->prev;//让新节点的上一个节点为pos指向节点的前一个节点

	pos->prev->next = newnode;//pos指向节点的上一个节点的下一个节点为新节点

	pos->prev = newnode;//让新节点成为pos指向节点的上一个节点
}

//删除pos指向的节点
void ListEase(LTNode* phead, LTNode* pos)
{
	assert(pos != phead);//链表为空时再不能删除

	pos->prev->next = pos->next;//让pos指向节点的前一个节点的next指向pos指向节点的下一个节点

	pos->next->prev = pos->prev;//让pos指向节点的下一个节点的prev指向pos指向节点的上一个节点

	free(pos);//释放pos指向节点
}

//销毁链表
void ListDestory(LTNode* phead)
{
	LTNode* cur = phead->next;//让cur指向链表的第一个节点

	LTNode* tmp = phead->next;

	while (cur != phead)
	{
		tmp = cur->next;//tmp指向cur的下一个节点，防止cur被释放了，找不到下一个节点了
		free(cur);
		cur = tmp;//让cur指向下一个节点
	}
	phead->prev = phead;//链表的所有节点都被释放后，头节点的prev要指向自己，让链表下一次使用时不会出错

	phead->next = phead;//链表的所有节点都被释放后，头节点的next也要指向自己
}

以上就是所有内容了，如果对你有帮助的话，可以点个赞支持一下！

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

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

相关文章

在flutter中添加video_player【视频播放插件】

在flutter中添加video_player【视频播放插件】

添加插件依赖 dependencies:video_player: ^2.8.3插件的用途 在Flutter框架中&#xff0c;video_player 插件是一个专门用于播放视频的插件。它允许开发者在Flutter应用中嵌入视频播放器&#xff0c;并提供了一系列功能来控制和定制视频播放体验。这个插件对于需要在应用中展…
阅读更多...
HarmonyOS 应用开发之创建自定义组件

HarmonyOS 应用开发之创建自定义组件

在ArkUI中&#xff0c;UI显示的内容均为组件&#xff0c;由框架直接提供的称为系统组件&#xff0c;由开发者定义的称为自定义组件。在进行 UI 界面开发时&#xff0c;通常不是简单的将系统组件进行组合使用&#xff0c;而是需要考虑代码可复用性、业务逻辑与UI分离&#xff0c…
阅读更多...
练习 17 Web [极客大挑战 2019]PHP

练习 17 Web [极客大挑战 2019]PHP

常见的网站源码备份文件名和后缀&#xff0c;反序列化攻击 unserialize()&#xff1a;wakeup绕过&#xff0c;private类以及属性序列化后的%00修改 开靶机 提到”备份“ 那看看有没有backup.php啥的 如果网站存在备份文件&#xff0c;常见的备份文件后缀名有&#xff1a;“.gi…
阅读更多...
系统IO函数接口

系统IO函数接口

目录 前言 一. man手册 1.1 man手册如何查询 1.2 man手册基础 二.系统IO函数接口 三.open打开文件夹 3.1 例1 open打开文件 3.2 open打开文件代码 3.3 例2 创建文件 四.write写文件 4.1 write写文件 五. read读文件 5.1 read读文件与偏移 5.2 偏移细节 5.3 read读文件代码 六.复…
阅读更多...
vscode 重命名很慢或失败 vscode renames are slow

vscode 重命名很慢或失败 vscode renames are slow

网上问题&#xff0c; 插件问题&#xff08;我遇见的排除&#xff0c;不是&#xff09;被其他程序占用问题&#xff0c;&#xff08;我这边是这个&#xff09; 解决方案&#xff1a; 打开【资源管理器】&#xff0c;使用火绒 或其他软件&#xff0c;查看文件夹 or 文件 被哪个…
阅读更多...
集合的学习

集合的学习

为什么要有集合&#xff1a;集合会自动扩容 集合不能存基本数据类型&#xff08;基本数据类型是存放真实的值&#xff0c;而引用数据类型是存放一个地址&#xff0c;这个地址存放在栈区&#xff0c;地址所指向的内容存放在堆区&#xff09; 数组和集合的对比&#xff1a; 集…
阅读更多...
Python 简单使用 RabbitMQ

Python 简单使用 RabbitMQ

一、安装 pip install pika 二、推送消息到队列中 执行pythone方法 import pika import time# 用户名和密码 user_info pika.PlainCredentials(admin,admin)# 连接服务器上的rabbitMQ服务 connection pika.BlockingConnection(pika.ConnectionParameters(127.0.0.1, 5672,…
阅读更多...
python核心篇之网络通信

python核心篇之网络通信

一. 发送请求 1. 发送get请求 2. 发送post请求 3. json数据与python数据的对应关系
阅读更多...
隐私计算实训营第七讲-隐语SCQL的架构详细拆解

隐私计算实训营第七讲-隐语SCQL的架构详细拆解

隐私计算实训营第七讲-隐语SCQL的架构详细拆解 文章目录 隐私计算实训营第七讲-隐语SCQL的架构详细拆解1.SCQL Overview1.1 多方数据分析场景1.2 多方数据分析技术路线1.2.1 TEE SQL方案1.2.2 MPC SQL方案 1.3 Secure Collaborative Query Language(SCQL)1.3.1 SCQL 系统组件1.…
阅读更多...
css3之2D转换transform

css3之2D转换transform

2D转换transform 一.移动&#xff08;translate)(中间用&#xff0c;隔开&#xff09;二.旋转&#xff08;rotate)&#xff08;有单位deg)1.概念2.注意点3.转换中心点&#xff08;transform-origin)&#xff08;中间用空格&#xff09;4.一些例子(css三角和旋转&#xff09; 三…
阅读更多...
SVM简介 详细推导 核函数 线性可分 非线性可分

SVM简介 详细推导 核函数 线性可分 非线性可分

注意&#xff1a;由于该文章由jupyter nbconvert导出&#xff0c;若单独执行代码可能出现变量找不到或者没有导入库的情况&#xff0c;正确的做法是将所有的代码片段按顺序放到一个.py文件里面或者按顺序放入一个.ipynb文件的多个代码块中。 SVM(Support Vector Machine) Vap…
阅读更多...
第十五届蓝桥杯模拟考试I_物联网设计

第十五届蓝桥杯模拟考试I_物联网设计

反思&#xff1a; 本次模拟让我惊醒&#xff0c;写这个作品如同搭积木&#xff0c;在拼接的时候都要仔细检查这个积木是否出bug,确保没有问题再将其拼接到之前搭好的大模块之中&#xff0c;因为就是这样的题目我在处理过程中就遇到了BUG&#xff0c;原因竟出在输入模式要上拉&…
阅读更多...
鸿蒙OS元服务开发：【（Stage模型）设置应用主窗口】

鸿蒙OS元服务开发：【（Stage模型）设置应用主窗口】

一、设置应用主窗口说明 在Stage模型下&#xff0c;应用主窗口由UIAbility创建并维护生命周期。在UIAbility的onWindowStageCreate回调中&#xff0c;通过WindowStage获取应用主窗口&#xff0c;即可对其进行属性设置等操作。还可以在应用配置文件中设置应用主窗口的属性&…
阅读更多...
MegaSeg Pro for Mac v6.3.1 注册激活版 音视频DJ混音工具

MegaSeg Pro for Mac v6.3.1 注册激活版 音视频DJ混音工具

MegaSeg Pro for Mac是一款专业的DJ和广播自动化软件&#xff0c;旨在为音乐专业人士提供强大的音乐播放和演播功能。这款软件具有多种功能&#xff0c;包括强大的音乐库管理&#xff0c;支持导入和组织大量音乐文件&#xff0c;可以轻松管理你的音乐收藏。它支持广泛的音频格式…
阅读更多...
idea快速找到maven中冲突的依赖,解决依赖冲突

idea快速找到maven中冲突的依赖,解决依赖冲突

红色实线&#xff1a;冲突&#xff0c;红色虚线&#xff1a;依赖于同一个包的多版本 选择包&#xff0c;右键Excluede&#xff0c;排除 问题原因: 一个项目中需要jar包A和jar包B,而jar包A和jar包B都需要依赖jar包C,但A需要1.2.16版本的C,B需要1.2.17版本的C,这时候就可能会产…
阅读更多...
vs2022断点找bug出错（打上100个断点）

vs2022断点找bug出错（打上100个断点）

初步分析&#xff1a;故障出自-具体功能模块 进一步分析&#xff1a;故障出自-该功能代码流程 进一步分析&#xff1a;从该功能起点-终点&#xff0c;一路打100个断点
阅读更多...
电商技术揭秘五：电商平台的个性化营销与数据分析

电商技术揭秘五：电商平台的个性化营销与数据分析

文章目录 引言1. 个性化营销的概念与价值1.1 个性化营销的定义1.1.1 个性化营销的基本概念1.1.2 个性化营销在电商领域的重要性 1.2 个性化营销的核心价值1.2.1 提升用户体验1.2.2 增加转化率和客户忠诚度1.2.3 优化营销资源配置 2. 用户画像与行为分析2.1 用户画像的构建2.1.1…
阅读更多...
【Linux】在生产环境中，Linux系统排查常用命令

【Linux】在生产环境中，Linux系统排查常用命令

问题排查 文章目录 问题排查top命令CPU&#xff1a;vmstatprocscpu内存&#xff1a;free硬盘&#xff1a;df硬盘IO&#xff1a;iostat网络IO&#xff1a;ifstat 生产环境服务器变慢&#xff0c;诊断思路和性能评估 top命令 查看整机系统新能 使用top命令的话&#xff0c;重点…
阅读更多...
如何处理Flutter应用在iOS平台上的兼容性问题

如何处理Flutter应用在iOS平台上的兼容性问题

本文探讨了使用Flutter开发的iOS应用能否上架&#xff0c;以及上架的具体流程。苹果提供了App Store作为正式上架渠道&#xff0c;同时也有TestFlight供开发者进行内测。合规并通过审核后&#xff0c;Flutter应用可以顺利上架。但上架过程可能存在一些挑战&#xff0c;因此可能…
阅读更多...
使用TCP协议就一定零丢包了吗？

使用TCP协议就一定零丢包了吗？

简述数据包发送流程 为了简化模型&#xff0c;我们把中间的服务器给省略掉&#xff0c;假设这是个端到端的通信。且为了保证消息的可靠性&#xff0c;它们之间用的是TCP协议进行通信。 为了发送数据包&#xff0c;两端首先会通过三次握手&#xff0c;建立TCP连接。 一个数据包&…
阅读更多...
最新文章

Copyright @ 2022~2023