【数据结构|C语言版】双向链表
- 前言
- 1. 初步认识双向链表
- 1.1 定义
- 1.2 结构
- 1.3 储存
- 2. 双向链表的方法(接口函数)
- 2.1 动态申请空间
- 2.2 创建哨兵位
- 2.3 查找指定数据
- 2.4 指定位置插入
- 2.5 指定位置删除
- 2.6 头部插入
- 2.7 头部删除
- 2.8 尾部插入
- 2.9 尾部删除
- 2.10 计算链表大小
- 2.11 销毁链表
- 3. 双向链表的代码实现
- 结语
↓
上期回顾: 【数据结构|C语言版】顺序表应用
个人主页:C_GUIQU
专栏:【数据结构(C语言版)学习】
↑
前言
各位小伙伴大家好!上期小编给大家讲解了数据结构中的顺序表应用,接下来讲讲数据结构中的双向链表!
1. 初步认识双向链表
1.1 定义
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。
1.2 结构
1.3 储存
//双链表节点结构体
typedef struct DoubleLinkNode
{char data;struct DoubleLinkNode* prior;struct DoubleLinkNode* next;
} Node,*NodePtr;
2. 双向链表的方法(接口函数)
2.1 动态申请空间
【本质】动态开辟一块sizeof(ListNode)大小的空间进行存储
// 动态申请一个结点
ListNode *BuyListNode(LTDateType x) {ListNode *node = (ListNode *) malloc(sizeof(ListNode));node->data = x;node->prev = NULL;node->next = NULL;return node;
}
2.2 创建哨兵位
// 创建返回链表的哨兵位
ListNode *ListInit() {ListNode *pHead = BuyListNode(-1);pHead->prev = pHead;pHead->next = pHead;return pHead;
}
2.3 查找指定数据
// 双向链表查找
ListNode *ListFind(ListNode *pHead, LTDateType x) {assert(pHead);ListNode *curr = pHead->next;while (curr != pHead) {if (curr->data == x) {return curr;}curr = curr->next;}return NULL;
}
2.4 指定位置插入
// 双向链表在pos位置插入x
void ListInsert(ListNode *pos, LTDateType x) {assert(pos);ListNode *newNode = BuyListNode(x);ListNode *prev = pos->prev;newNode->prev = prev;newNode->next = pos;prev->next = newNode;pos->prev = newNode;
}
2.5 指定位置删除
// 双向链表在pos位置删除
void ListErase(ListNode *pos) {assert(pos);assert(pos != pos->next);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);
}
2.6 头部插入
// 双向链表头插
void ListPushFront(ListNode *pHead, LTDateType x) {ListInsert(pHead->next, x);
}
2.7 头部删除
// 双向链表头删
void ListPopFront(ListNode *pHead) {ListErase(pHead->next);
}
2.8 尾部插入
// 双向链表尾插
void ListPushBack(ListNode *pHead, LTDateType x) {ListInsert(pHead, x);
}
2.9 尾部删除
// 双向链表尾删
void ListPopBack(ListNode *pHead) {ListErase(pHead->prev);
}
2.10 计算链表大小
// 计算大小
int ListSize(ListNode *pHead) {ListNode *curr = pHead->next;int size = 0;while (curr != pHead) {size++;curr = curr->next;}return size;
}
2.11 销毁链表
// 销毁(手动置空)
void ListDestory(ListNode *pHead) {ListNode *curr = pHead->next;while (curr != pHead) {ListNode *next = curr->next;free(curr);curr = next;}free(pHead);
}
3. 双向链表的代码实现
#include <stdio.h>
#include <stdlib.h>
int Linklength;//双链表节点结构体
typedef struct DoubleLinkNode
{char data;struct DoubleLinkNode* prior;struct DoubleLinkNode* next;
} Node,*NodePtr;//初始化
NodePtr initLinkList()
{NodePtr LinkHeader = (NodePtr)malloc(sizeof(Node));LinkHeader->data = '\0';LinkHeader->next = NULL;LinkHeader->prior = NULL;Linklength = 0;return LinkHeader;
}//寻找尾节点
NodePtr tailNodeSearch(NodePtr LinkHeader)
{NodePtr p = LinkHeader;while(p->next){p = p->next;}return p;
}//正向打印
void printListByHead(NodePtr LinkHeader)
{NodePtr p = LinkHeader->next;while (p){printf("%c",p->data);p = p->next;}printf("\n");
}//反向打印
void printListByTail(NodePtr LinkHeader)
{NodePtr tail = tailNodeSearch(LinkHeader);NodePtr p = tail;while (p){printf("%c",p->data);p = p->prior;}printf("\n");
}//在某位置插入
void ListInsert(NodePtr LinkHeader, int InsertPosition, char InsertChar)
{if(InsertPosition < 0 || InsertPosition > Linklength){printf("The position %d out of range of linked list!\n",InsertPosition);return ;}NodePtr p,q,r,tail;p = LinkHeader;for(int i = 0; i < InsertPosition; ++i){p = p->next;if(!p){printf("The position %d out of range of linked list!\n",InsertPosition);return ;}}q = (NodePtr)malloc(sizeof(Node));q->data = InsertChar;r = p->next;q->prior = p;q->next = r;p->next = q;if(r){r->prior = q;}Linklength++;
}//删除第一个数据域为x的节点
void ListDeleteByData(NodePtr LinkHeader, char DeleteChar)
{NodePtr p,q,r;p = LinkHeader;while(p->next && p->next->data != DeleteChar){p = p->next;}if(!(p->next)){printf("The char '%c' does't exist.\n",DeleteChar);return ;}q = p->next;r = q->next;p->next = r;if(r){r->prior = p;}free(q);Linklength--;
}//删除第Position个节点
void ListDeleteByPosition(NodePtr LinkHeader, int Position)
{NodePtr p,q,r,tail;int j = 0;tail = tailNodeSearch(LinkHeader);p = LinkHeader;while(p->next && j < Position){p = p->next;++j;}if(!(p->next) || j > Position){printf("Can't delete it!\n");return ;}q = p->next;r = q->next;p->next = r;if(r){r->prior = p;}free(q);Linklength--;
}//链表节点的读取(打印链表中第position个数据元素的值)
void GetElement(NodePtr LinkHeader, int position)
{NodePtr p,q,r;if(position <= Linklength/2){p = LinkHeader->next;int j = 0;while(p && j < position){p = p->next;++j;}if(!p || j > position){printf("Can't get it !\n");return ;}printf("The element at its %d-th position is %c\n",position,p->data);}else{p = tailNodeSearch(LinkHeader);int j = 0;while(p->prior && j < Linklength-position-1){p = p->prior;++j;}if(!p || j > Linklength-position-1){printf("Can't get it !\n");return ;}printf("The element at its %d-th position is %c\n",position,p->data);}
}//测试
void insertDeleteTest()
{printf("---------------Initialize bidirectional linked list--------------\n");NodePtr tempList = initLinkList();printListByHead(tempList);printListByTail(tempList);printf("---------------Inserts a node at the specified location--------------\n");ListInsert(tempList,0,'H');ListInsert(tempList,1,'e');ListInsert(tempList,2,'l');ListInsert(tempList,3,'l');ListInsert(tempList,4,'o');printListByHead(tempList);printListByTail(tempList);printf("---------------Gets the node data field at the specified location--------------\n");GetElement(tempList,0);GetElement(tempList,4);GetElement(tempList,5);printf("---------------Delete the first node whose data field is X--------------\n");ListDeleteByData(tempList,'e');printListByHead(tempList);printListByTail(tempList);printf("---------------Delete the position node--------------\n");ListDeleteByPosition(tempList,3);printListByHead(tempList);printListByTail(tempList);
}int main()
{insertDeleteTest();
}
结语
以上就是小编对双向链表的讲解。
如果觉得小编讲的还可以,还请一键三连。互三必回!
持续更新中~!
相关文章:

【数据结构|C语言版】双向链表
前言1. 初步认识双向链表1.1 定义1.2 结构1.3 储存 2. 双向链表的方法(接口函数)2.1 动态申请空间2.2 创建哨兵位2.3 查找指定数据2.4 指定位置插入2.5 指定位置删除2.6 头部插入2.7 头部删除2.8 尾部插入2.9 尾部删除2.10 计算链表大小2.11 销毁链表 3.…...

适用于 Windows 的 10 个顶级 PDF 编辑器 [免费和付费]
曾经打开PDF文件,感觉自己被困在数字迷宫中吗?无法编辑的文本、无法调整大小的图像以及签署感觉像是一件苦差事的文档?好吧,不用再担心了!本指南解开了在 Windows 上掌握 PDF 的秘密,其中包含 10 款适用于 …...
久菜盒子|留学|推荐信|活动类|改性伽马-三氧化二铝催化剂上甲醇制备二甲醚的研究项目
尊敬的录取委员会: 我是华东理工大学化工学院的刘殿华。非常荣幸在此推荐我校优秀学生 XXX 进入贵校学习。 我认识 XXX是在一年前,当时,我正计划做一个有关改性伽马-三氧化二铝催化剂上甲醇制备二甲醚的研究项目。XXX 找到了我,表示希望能够加…...

Java项目如何使用EasyExcel插件对Excel数据进行导入导出
文章目录 一、EasyExcel的示例导入依赖创建实体类数据导入和导出 二、EasyExcel的作用三、EasyExcel的注解 EasyExcel是一个阿里巴巴开源的excel处理框架,它以使用简单、节省内存著称。在解析Excel时,EasyExcel没有将文件数据一次性全部加载到内存中&…...
python标准库常用方法集合
前段时间准备第十五届蓝桥杯python a组,因为赛中不允许导包,因此对py中的标准库进行了笔记和总结,即不导包即可使用的常用方法。包含了内置函数、math、random、datetime、os、sys、re、queue、collections、itertools库的常用方法࿰…...

智谱AI通用大模型:官方开放API开发基础
目录 一、模型介绍 1.1主要模型 1.2 计费单价 二、前置条件 2.1 申请API Key 三、基于SDK开发 3.1 Maven引入SDK 3.2 代码实现 3.3 运行代码 一、模型介绍 GLM-4是智谱AI发布的新一代基座大模型,整体性能相比GLM3提升60%,支持128K上下文&#x…...
单片机家电产品--OC门电路
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 单片机家电产品–OC门电路 前言 记录学习单片机家电产品内容 已转载记录为主 一、知识点 1OC门电路和OD门电路的区别 OC门电路和OD门电路的区别 OC门:三极管…...

gcc常用命令指南(更新中...)
笔记为gcc常用命令指南(自用),用到啥方法就具体研究一下,更新进去... 编译过程的分布执行 64位系统生成32位汇编代码 gcc -m32 test.c -o test -m32用于生成32位汇编语言...

【深度学习】【机器学习】用神经网络进行入侵检测,NSL-KDD数据集,基于机器学习(深度学习)判断网络入侵,网络攻击,流量异常【3】
之前用NSL-KDD数据集做入侵检测的项目是: 【1】https://qq742971636.blog.csdn.net/article/details/137082925 【2】https://qq742971636.blog.csdn.net/article/details/137170933 有人问我是不是可以改代码,我说可以。 训练 我将NSL_KDD_Final_1.i…...

两步解决 Flutter Your project requires a newer version of the Kotlin Gradle plugin
在开发Flutter项目的时候,遇到这个问题Flutter Your project requires a newer version of the Kotlin Gradle plugin 解决方案分两步: 1、在android/build.gradle里配置最新版本的kotlin 根据提示的kotlin官方网站搜到了Kotlin的最新版本是1.9.23,如下图所示: 同时在Ko…...
ArcGIS加载的各类地图怎么去除服务署名水印
昨天介绍的: 一套图源搞定!清新规划底图、影像图、境界、海洋、地形阴影图、导航图-CSDN博客文章浏览阅读373次,点赞7次,收藏11次。一体化集成在一起的各类型图源,比如包括影像、清新的出图底图、地形、地图阴影、道路…...
AttributeError: module ‘cv2.face’ has no attribute ‘LBPHFaceRecognizer_create’
问题描述: 报错如下: recognizer cv2.face.LBPHFaceRecognizer_create() AttributeError: module ‘cv2.face’ has no attribute ‘LBPHFaceRecognizer_create’ 解决方案: 把opencv-python卸载了,然后安装ope…...

配置路由器实现互通
1.实验环境 实验用具包括两台路由器(或交换机),一根双绞线缆,一台PC,一条Console 线缆。 2.需求描述 如图6.14 所示,将两台路由器的F0/0 接口相连,通过一台PC 连接设备的 Console 端口并配置P地址(192.1…...
Google Guava第五讲:本地缓存实战及踩坑
本地缓存实战及踩坑 本文是Google Guava第五讲,先介绍为什么使用本地缓存;然后结合实际业务,讲解如何使用本地缓存、清理本地缓存,以及使用过程中踩过的坑。 文章目录 本地缓存实战及踩坑1、缓存系统概述2、缓存架构演变2.1、无缓存架构2.2、引入分布式缓存问题1:为什么选…...

一个文生视频MoneyPrinterTurbo项目解析
最近抖音剪映发布了图文生成视频功能,同时百家号也有这个功能,这个可以看做是一个开源的实现,一起看看它的原理吧~ 一句话提示词 大模型生成文案 百家号生成视频效果 MoneyPrinterTurbo生成视频效果 天空为什么是蓝色的? 天空之所以呈现蓝色,是因为大气中的分子和小粒子会…...

智能商品计划系统如何提升鞋服零售品牌的竞争力
国内鞋服零售企业经过多年的发展,已经形成了众多知名品牌,然而近年来一些企业频频受到库存问题的困扰,这一问题不仅影响了品牌商自身,也给长期合作的经销商带来了困扰。订货会制度在初期曾经有效地解决了盲目生产的问题࿰…...

OpenHarmony开发案例:【分布式遥控器】
1.概述 目前家庭电视机主要通过其自带的遥控器进行操控,实现的功能较为单一。例如,当我们要在TV端搜索节目时,电视机在遥控器的操控下往往只能完成一些字母或数字的输入,而无法输入其他复杂的内容。分布式遥控器将手机的输入能力…...

如何将Oracle 中的部分不兼容对象迁移到 OceanBase
本文总结分析了 Oracle 迁移至 OceanBase 时,在出现三种不兼容对象的情况时的处理策略以及迁移前的预检方式,通过提前发现并处理这些问题,可以有效规避迁移过程中的报错风险。 作者:余振兴,爱可生 DBA 团队成员&#x…...

Python也可以合并和拆分PDF,批量高效!
PDF是最方便的文档格式,可以在任何设备原样且无损的打开,但因为PDF不可编辑,所以很难去拆分合并。 知乎上也有人问,如何对PDF进行合并和拆分? 看很多回答推荐了各种PDF编辑器或者网站,确实方法比较多。 …...
python笔记(14)迭代器和生成器
迭代器的优势 延迟计算:迭代器按需提供数据,无需一次性加载整个数据集到内存中,特别适合处理大规模或无限数据流。资源效率:减少内存占用,尤其在处理大量数据时,避免一次性构建完整数据结构带来的开销。统…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...

C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...

基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...

el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...
在Ubuntu24上采用Wine打开SourceInsight
1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...
现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?
现有的 Redis 分布式锁库(如 Redisson)相比于开发者自己基于 Redis 命令(如 SETNX, EXPIRE, DEL)手动实现分布式锁,提供了巨大的便利性和健壮性。主要体现在以下几个方面: 原子性保证 (Atomicity)ÿ…...