【C语言】数据结构——带头双链表实例探究

💗个人主页💗
⭐个人专栏——数据结构学习⭐
💫点击关注🤩一起学习C语言💯💫

目录

  • 导读：
  • 1. 双链表结构特征
  • 2. 实现双向循环链表
    • 2.1 定义结构体
    • 2.2 创造节点
    • 2.3 双向链表初始化
    • 2.4 双向链表打印
    • 2.5 双向链表尾插
    • 2.6 双向链表尾删
    • 2.7 双向链表头插
    • 2.8 双向链表头删
    • 2.9 双向链表查找
    • 2.10 双向链表任意位置插入
    • 2.11 双向链表任意位置删除
    • 2.12 双链表销毁
    • 2.13 利用任插、任删完成头尾插入和头尾删除

导读：

我们在前面学习了单链表和顺序表。
今天我们来学习双向循环链表。
在经过前面的一系列学习，我们已经掌握很多知识，相信今天的内容也是很容易理解的。
关注博主或是订阅专栏，掌握第一消息。

1. 双链表结构特征

今天我们要学的是双向带头循环列表。
双向循环链表是一个链表的数据结构，每个节点包含两个指针，分别指向前一个节点和后一个节点。与普通的链表不同的是，双向循环链表的尾节点的后继节点指向头节点，头节点的前驱节点指向尾节点，形成一个闭环。
在这里插入图片描述
双向循环链表的特点是可以从任意一个节点开始遍历整个链表。

由于每个节点都可以直接访问前一个节点和后一个节点，所以在双向循环链表中插入和删除节点的操作更加方便和高效。
在插入和删除节点时，只需要修改相邻节点的指针即可，不需要像普通链表那样需要遍历找到前一个节点。

2. 实现双向循环链表

我们需要创建两个 C文件: study.c 和 SList.c，以及一个 头文件： SList.h。
头文件来声明函数，一个C文件来定义函数，另外一个C文件来用于主函数main（）进行测试。

2.1 定义结构体

typedef是类型定义的意思。typedef struct 是为了使用这个结构体方便。

若struct SeqList {}这样来定义结构体的话。在申请SeqList 的变量时，需要这样写，struct SList n;
若用typedef，可以这样写，typedef struct SList{}SL; 。在申请变量时就可以这样写，SL n;
区别就在于使用时，是否可以省去struct这个关键字。

定义两个指针next和prev，分别指向该节点的下一个节点和前一个节点，data记录该节点存放的值。

typedef int LTDataType;

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

2.2 创造节点

因为链表的插入都需要新创建一个节点，为了方便后续的使用以及避免代码的重复出现，我们直接定义函数，后续直接调用即可。

LTNode* CreateLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

malloc开辟一块空间，存入想要插入的值，前后指针闲置为空，后面调用后再去改变，返回该节点的指针。

2.3 双向链表初始化

先把哨兵位创建出来，前后指针都先指向自己，该节点不存储任何实际的数据，只是作为链表的起始点。

LTNode* LTInit()
{
	LTNode* phead = CreateLTNode(-1);

	phead->next = phead;
	phead->prev = phead;
	return phead;
}

2.4 双向链表打印

方便我们后面测试代码是否出错。

void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	printf("哨兵位<=>");
	while (cur != phead)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

2.5 双向链表尾插

首先，需要找到链表的尾节点（即头节点的前驱节点）。
然后将新节点插入到尾节点的后面，即新节点的前驱指向尾节点，新节点的后继指向头节点（即原先的尾节点的后继节点），头节点的前驱指向新节点，头节点的后继指向新节点。
最后，将新节点作为尾节点。

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* tail = phead->prev;//尾节点
	LTNode* newnode = CreateLTNode(x);//新建一个节点

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

我们用尾插插入1，2，3，4来进行测试。

void TestLT1()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);

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

在这里插入图片描述
最开始的时候链表只有一个哨兵位，它的前后指针都是指向自己，所以找尾节点找到的就是哨兵位。
在这里插入图片描述
第一个数据的插入：
在这里插入图片描述

第二个数据的插入：

在这里插入图片描述

2.6 双向链表尾删

要实现带头双向循环链表的尾删操作，可以按照以下步骤：

  1. 首先判断链表是否为空，如果为空，则直接返回。

  2. 如果链表不为空，找到链表中的最后一个节点的前一个节点，即尾节点的前一个节点。

  3. 将尾节点的前一个节点的next指针指向头节点，即将尾节点从链表中移除。

  4. 释放尾节点的内存空间。

  5. 更新链表的尾指针，即将尾指针指向尾节点的前一个节点。

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next);

	LTNode* tail = phead->prev;//最后一个节点
	LTNode* tailprev = tail->prev;//倒数第二个节点
	phead->prev = tailprev;
	tailprev->next = phead;
	free(tail);
	tail = NULL;
}

测试：

void TestLT1()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);

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

在这里插入图片描述

在这里插入图片描述

2.7 双向链表头插

头插法是指将新的节点插入链表的头部，而不是尾部。
在带头双向链表中，首先创建一个新的节点，并将其next指针指向原来的头节点，然后将原来的头节点的prev指针指向新的节点即可。

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = CreateLTNode(x);//增加新节点
	LTNode* next = phead->next;//记录原先的第一个节点
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = next;
	next->prev = newnode;
}

测试：

void TestLT2()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushFront(plist, 99);
	LTPushFront(plist, 88);
	LTPushFront(plist, 77);
	LTPushFront(plist, 66);
	LTPushFront(plist, 55);
	LTPrint(plist);
}
int main()
{
	TestLT2();
	return 0;
}

在这里插入图片描述
在这里插入图片描述

2.8 双向链表头删

带头双向链表的头删操作可以通过以下步骤实现：

  1. 如果链表为空，直接返回。
  2. 将头节点的下一个节点指针保存在一个临时变量中。
  3. 将头节点的下一个节点的前驱节点指针指向空。
  4. 将临时变量指向的节点的前驱节点指针指向空。
  5. 将头节点指向临时变量指向的节点。
  6. 释放临时变量指向的节点的内存空间。
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next);
	LTNode* del = phead->next;//第一个节点
	LTNode* next = del->next;//第二个节点
	phead->next = next;
	next->prev = phead;
	free(del);
	del = NULL;
}

测试：

void TestLT2()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushFront(plist, 99);
	LTPushFront(plist, 88);
	LTPushFront(plist, 77);
	LTPushFront(plist, 66);
	LTPushFront(plist, 55);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
}
int main()
{
	TestLT2();
	return 0;
}

在这里插入图片描述
在这里插入图片描述

2.9 双向链表查找

在带头双向链表中查找一个特定的元素可以按照以下步骤进行：

  1. 如果链表为空，则返回空指针或者空值，表示找不到目标元素。
  2. 通过指针访问链表的第一个节点，即头节点的下一个节点。
  3. 从第一个节点开始，依次遍历链表的每一个节点，直到找到目标元素或者遍历到链表的末尾。
    4 如果找到目标元素，返回该节点的指针或者该节点的值，表示找到了目标元素。
  4. 如果遍历到链表的末尾都没有找到目标元素，则返回空指针或者空值，表示找不到目标元素。
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

2.10 双向链表任意位置插入

我们利用查找函数，插入到找到的数前面。

  1. 判断链表里是否有这位数。
  2. 创建一个新节点。
  3. 改变pos位置前一个节点、pos节点和新节点的前后驱指针。
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = CreateLTNode(x);//增加新节点
	LTNode* cur = pos->prev;//pos前一个节点
	cur->next = newnode;
	newnode->prev = cur;
	pos->prev = newnode;
	newnode->next = pos;
}

测试：

//任意位置插入测试
void TestLT5()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	if (LTFind(plist, 2))
	{
		LTNode* pos = LTFind(plist, 2);
		LTInsert(pos, 999);
		LTPrint(plist);
	}
	else
	{
		printf("fail\n");
	}
}
int main()
{
	TestLT5();
	return 0;
}

在这里插入图片描述

2.11 双向链表任意位置删除

仍然是利用查找函数，删除find函数返回的节点。

  1. 判断是否存在这个数。
  2. 把该节点的前一个节点和后一个节点相关联。
  3. 释放该节点。
void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* before = pos->prev;//pos前一个节点
	LTNode* next = pos->next;//pos后一个节点
	before->next = next;
	next->prev = before;
	free(pos);
	pos = NULL;
}

测试：

//任意位置删除测试
void TestLT6()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushFront(plist, 99);
	LTPushFront(plist, 88);
	if (LTFind(plist, 2))
	{
		LTNode* pos = LTFind(plist, 2);
		LTErase(pos);
	}
	LTPrint(plist);
}
int main()
{
	TestLT6();
	return 0;
}

在这里插入图片描述

2.12 双链表销毁

动态内存开辟空间，使用完之后需要进行销毁。

void LTDestory(LTNode* phead)
{
	assert(phead);
	assert(phead->next);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

2.13 利用任插、任删完成头尾插入和头尾删除

因为我们是带头双向链表，所以我们利用哨兵位就可以轻松找到链表的头尾结点。
所有我们只需要把哨兵位的位置做为参数，就可以轻易完成。

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTInsert(phead, x);
}

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next);
	LTErase(phead->prev);
}

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTInsert(phead->next, x);

}

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next);
	LTErase(phead->next);
}

测试：

//任意位置插入删除（头尾增删调用）
void TestLT4()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPrint(plist);
	LTPushFront(plist, 99);
	LTPushFront(plist, 88);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);

	LTPopFront(plist);

	LTPrint(plist);
	LTDestory(plist);
}
int main()
{
	TestLT4();
	return 0;
}

在这里插入图片描述

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

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

相关文章

【Unity动画系统】Animator有限状态机参数详解

【Unity动画系统】Animator有限状态机参数详解

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;元宇宙-秩沅 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 秩沅 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a;Uni…
阅读更多...
攻防技术1-网络攻击（HCIP）

攻防技术1-网络攻击（HCIP）

目录 一、网络攻击方式分类 1、被动攻击&#xff1a; 2、主动攻击&#xff1a; 3、中间人攻击&#xff1a; 二、网络攻击报文类型分类&#xff1a; 1、流量型攻击 2、单包攻击 三、流量型攻击防范技术 1、DNS Request Flood攻击 攻击原理 DNS交互过程 2、TCP类报文…
阅读更多...
统信UOS及麒麟KYLINOS操作系统上设置GRUB密码

统信UOS及麒麟KYLINOS操作系统上设置GRUB密码

原文链接&#xff1a;给单用户模式上一层保险&#xff01;&#xff01;&#xff01; hello&#xff0c;大家好啊&#xff01;今天我要给大家介绍的是在统信UOS及麒麟KYLINOS操作系统上设置GRUB密码的方法。GRUB&#xff08;GRand Unified Bootloader&#xff09;是Linux系统中的…
阅读更多...
【Vue】使用Axios请求下载后端返回的文件流，并能够提示后端报错信息

【Vue】使用Axios请求下载后端返回的文件流，并能够提示后端报错信息

【需求】使用Axios请求下载后端返回的文件流&#xff0c;下载失败时提示信息不写死&#xff0c;按照后端返回的信息进行提示。 一、需求分析 看到这个需求的时候&#xff0c;有人可能会很疑惑&#xff0c;这不是直接就能获取到吗&#xff0c;直接message.error()弹框就完事了&…
阅读更多...
J1 - ResNet-50实战

J1 - ResNet-50实战

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 | 接辅导、项目定制 目录 环境步骤环境设置数据准备图像信息查看 模型设计模型训练模型效果展示 总结与心得体会 环境 系统: Linux语言: Python3.8.10深度学习…
阅读更多...
MySQL MVCC精讲

MySQL MVCC精讲

版本链 我们前面说过&#xff0c;对于使用InnoDB存储引擎的表来说&#xff0c;它的聚簇索引记录中都包含两个必要的隐藏列&#xff08;row_id并不是必要的&#xff0c;我们创建的表中有主键或者非NULL的UNIQUE键时都不会包含row_id列&#xff09;&#xff1a; trx_id&#xff…
阅读更多...
贪心算法Part01 455分发饼干

贪心算法Part01 455分发饼干

455分发饼干 376摆动序列 53 最大子数组和
阅读更多...
强大的音乐乐谱控件库

强大的音乐乐谱控件库

2023 Conmajia, 2018 Ajcek84 SN: 23C.1 本中文翻译已获原作者首肯。 简介 PSAM 控件库——波兰音乐文档系统——是用于显示、排版乐谱的强大 WinForm 库&#xff0c;包含用于绘制乐谱的名为 IncipitViewer 控件&#xff0c;乐谱内容可以从 MusicXml 文件读取&#xff0c;或者…
阅读更多...
网大为卸任腾讯CXO；Midjourney 1 月训练视频模型；2023年马斯克赚了7700亿

网大为卸任腾讯CXO；Midjourney 1 月训练视频模型；2023年马斯克赚了7700亿

投融资 • 2023 年大型科技公司在生成式 AI 初创企业上的投资远超风险投资集团• 恒信东方与无锡政府合作成立布局 MR/XR 技术及 3D 数字资产 AIGC 产业投资基金• 新公司法完善注册资本认缴登记制度• 网大为卸任腾讯CXO&#xff0c;曾促成南非MIH的投资• 宁波蔚孚科技完成数…
阅读更多...
Spring-6-事务管理

Spring-6-事务管理

事务是构建可靠企业级应用程序的最关键部分之一。 最常见的事务类型是数据库操作。 在典型的数据库更新操作中&#xff0c;首先数据库事务开始&#xff0c;然后数据被更新&#xff0c;最后提交或回滚事务(根据数据库操作的结果而定)。但是&#xff0c;在很多情况下&#xff0…
阅读更多...
手写Spring与基本原理--简易版

手写Spring与基本原理--简易版

文章目录 手写Spring与基本原理解析简介写一个简单的Bean加载容器定义一个抽象所有类的BeanDefinition定义一个工厂存储所有的类测试 实现Bean的注册定义和获取基于Cglib实现含构造函数的类实例化策略Bean对象注入属性和依赖Bean的功能Spring.xml解析和注册Bean对象实现应用上下…
阅读更多...
Y9000P + ubuntu22.04 配置Anaconda+pycharm +pytorch

Y9000P + ubuntu22.04 配置Anaconda+pycharm +pytorch

Anaconda3 的安装及使用方法安装 Anaconda3 Anaconda3 是 Anaconda 的具体版本 Anaconda3 中的 Python 解释器默认使用的是 Python3.x 版本&#xff0c;而不是 Python2.x 版本 Python2.x 版本中&#xff0c;字符串是以 ASCII 编码处理的&#xff0c;而在 Python3.x 版本中&am…
阅读更多...
软件测试/测试开发丨Python 虚拟环境及pip环境管理

软件测试/测试开发丨Python 虚拟环境及pip环境管理

venv 虚拟环境管理 venv 虚拟环境的优点 独立的 Python 环境&#xff0c;不会产生冲突有助于包的管理删除和卸载方便 venv 使用方法 创建虚拟环境 python3 -m venv test 激活虚拟环境 切换指定文件夹Windows&#xff1a;/Scripts/macOS&#xff1a;/bin/ 执行指令&#xff…
阅读更多...
【Git】Git的基本操作

【Git】Git的基本操作

前言 Git是当前最主流的版本管理器&#xff0c;它可以控制电脑上的所有格式的文件。 它对于开发人员&#xff0c;可以管理项目中的源代码文档。&#xff08;可以记录不同提交的修改细节&#xff0c;并且任意跳转版本&#xff09; 本篇博客基于最近对Git的学习&#xff0c;简单介…
阅读更多...
自制双色球/大乐透摇奖小程序代码

自制双色球/大乐透摇奖小程序代码

自制双色球/大乐透摇奖小程序 双色球/大乐透 双色球/大乐透等彩票摇奖深受大众彩迷的喜爱&#xff0c;但是每次摇奖的随机性总是有内部操作的空间&#xff0c;为了将降低可能存在的黑幕&#xff0c;本人自制了简单的双色球/大乐透摇奖小程序,可以供官方参考&#xff1a; def…
阅读更多...
华为服务器安装银河麒麟V10操作系统（IBMC安装）

华为服务器安装银河麒麟V10操作系统（IBMC安装）

iBMC是华为面向服务器全生命周期的服务器嵌入式管理系统。提供硬件状态监控、部署、节能、安全等系列管理工具&#xff0c;标准化接口构建服务器管理更加完善的生态系统。 服务器BMC IP&#xff1a;192.168.2.100 一、准备工作 1、确保本机和服务器BMC管理口在同一网络 2、银…
阅读更多...
前后端分离架构的特点以及优缺点

前后端分离架构的特点以及优缺点

文章目录 一、前后端不分离架构(传统单体结构)1.1 什么是前后端不分离1.2 工作原理1.3 前后端不分离的优缺点1.4 应用场景 二、前后端分离架构2.1 为什么要前后端分离2.2 什么是前后端分离2.3 工作原理2.4 前后端分离的优缺点 参考资料 一、前后端不分离架构(传统单体结构) 首…
阅读更多...
【Linux驱动】设备树简介 | 内核对设备树的处理

【Linux驱动】设备树简介 | 内核对设备树的处理

&#x1f431;作者&#xff1a;一只大喵咪1201 &#x1f431;专栏&#xff1a;《Linux驱动》 &#x1f525;格言&#xff1a;你只管努力&#xff0c;剩下的交给时间&#xff01; 目录 &#x1f9f2;设备树简介&#x1f3f9;设备树语法&#x1f3f9;常见节点和属性&#x1f3f9…
阅读更多...
基于CNN神经网络的手写字符识别实验报告

基于CNN神经网络的手写字符识别实验报告

作业要求 具体实验内容根据实际情况自拟&#xff0c;可以是传统的BP神经网络&#xff0c;Hopfield神经网络&#xff0c;也可以是深度学习相关内容。 数据集自选&#xff0c;可以是自建数据集&#xff0c;或MNIST&#xff0c;CIFAR10等公开数据集。 实验报告内容包括但不限于&am…
阅读更多...
基于metersphere和supper-jacoco 测试覆盖率落地实践

基于metersphere和supper-jacoco 测试覆盖率落地实践

一、背景及目标 背景 1、技术研发流程为测试 提供冒烟用例-开发根据用例自测-提测-开始测试&#xff0c;这一套流程&#xff0c;但是中间开发是否真实执行冒烟&#xff0c;测试并不知晓&#xff0c;而且测试提供冒烟用例是否符合标准也没法进行量化 2、公司产品属于saas产品&…
阅读更多...
最新文章

Copyright @ 2022~2023