当前位置: 首页 > news >正文

【数据结构|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. 双向链表的方法&#xff08;接口函数&#xff09;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文件&#xff0c;感觉自己被困在数字迷宫中吗&#xff1f;无法编辑的文本、无法调整大小的图像以及签署感觉像是一件苦差事的文档&#xff1f;好吧&#xff0c;不用再担心了&#xff01;本指南解开了在 Windows 上掌握 PDF 的秘密&#xff0c;其中包含 10 款适用于 …...

久菜盒子|留学|推荐信|活动类|改性伽马-三氧化二铝催化剂上甲醇制备二甲醚的研究项目

尊敬的录取委员会: 我是华东理工大学化工学院的刘殿华。非常荣幸在此推荐我校优秀学生 XXX 进入贵校学习。 我认识 XXX是在一年前&#xff0c;当时&#xff0c;我正计划做一个有关改性伽马-三氧化二铝催化剂上甲醇制备二甲醚的研究项目。XXX 找到了我&#xff0c;表示希望能够加…...

Java项目如何使用EasyExcel插件对Excel数据进行导入导出

文章目录 一、EasyExcel的示例导入依赖创建实体类数据导入和导出 二、EasyExcel的作用三、EasyExcel的注解 EasyExcel是一个阿里巴巴开源的excel处理框架&#xff0c;它以使用简单、节省内存著称。在解析Excel时&#xff0c;EasyExcel没有将文件数据一次性全部加载到内存中&…...

python标准库常用方法集合

前段时间准备第十五届蓝桥杯python a组&#xff0c;因为赛中不允许导包&#xff0c;因此对py中的标准库进行了笔记和总结&#xff0c;即不导包即可使用的常用方法。包含了内置函数、math、random、datetime、os、sys、re、queue、collections、itertools库的常用方法&#xff0…...

智谱AI通用大模型:官方开放API开发基础

目录 一、模型介绍 1.1主要模型 1.2 计费单价 二、前置条件 2.1 申请API Key 三、基于SDK开发 3.1 Maven引入SDK 3.2 代码实现 3.3 运行代码 一、模型介绍 GLM-4是智谱AI发布的新一代基座大模型&#xff0c;整体性能相比GLM3提升60%&#xff0c;支持128K上下文&#x…...

单片机家电产品--OC门电路

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 单片机家电产品–OC门电路 前言 记录学习单片机家电产品内容 已转载记录为主 一、知识点 1OC门电路和OD门电路的区别 OC门电路和OD门电路的区别 OC门&#xff1a;三极管…...

gcc常用命令指南(更新中...)

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

【深度学习】【机器学习】用神经网络进行入侵检测,NSL-KDD数据集,基于机器学习(深度学习)判断网络入侵,网络攻击,流量异常【3】

之前用NSL-KDD数据集做入侵检测的项目是&#xff1a; 【1】https://qq742971636.blog.csdn.net/article/details/137082925 【2】https://qq742971636.blog.csdn.net/article/details/137170933 有人问我是不是可以改代码&#xff0c;我说可以。 训练 我将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加载的各类地图怎么去除服务署名水印

昨天介绍的&#xff1a; 一套图源搞定&#xff01;清新规划底图、影像图、境界、海洋、地形阴影图、导航图-CSDN博客文章浏览阅读373次&#xff0c;点赞7次&#xff0c;收藏11次。一体化集成在一起的各类型图源&#xff0c;比如包括影像、清新的出图底图、地形、地图阴影、道路…...

AttributeError: module ‘cv2.face’ has no attribute ‘LBPHFaceRecognizer_create’

问题描述&#xff1a; 报错如下&#xff1a; recognizer cv2.face.LBPHFaceRecognizer_create() AttributeError: module ‘cv2.face’ has no attribute ‘LBPHFaceRecognizer_create’ 解决方案&#xff1a; 把opencv-python卸载了&#xff0c;然后安装ope…...

配置路由器实现互通

1.实验环境 实验用具包括两台路由器(或交换机)&#xff0c;一根双绞线缆&#xff0c;一台PC&#xff0c;一条Console 线缆。 2.需求描述 如图6.14 所示&#xff0c;将两台路由器的F0/0 接口相连&#xff0c;通过一台PC 连接设备的 Console 端口并配置P地址&#xff08;192.1…...

Google Guava第五讲:本地缓存实战及踩坑

本地缓存实战及踩坑 本文是Google Guava第五讲,先介绍为什么使用本地缓存;然后结合实际业务,讲解如何使用本地缓存、清理本地缓存,以及使用过程中踩过的坑。 文章目录 本地缓存实战及踩坑1、缓存系统概述2、缓存架构演变2.1、无缓存架构2.2、引入分布式缓存问题1:为什么选…...

一个文生视频MoneyPrinterTurbo项目解析

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

智能商品计划系统如何提升鞋服零售品牌的竞争力

国内鞋服零售企业经过多年的发展&#xff0c;已经形成了众多知名品牌&#xff0c;然而近年来一些企业频频受到库存问题的困扰&#xff0c;这一问题不仅影响了品牌商自身&#xff0c;也给长期合作的经销商带来了困扰。订货会制度在初期曾经有效地解决了盲目生产的问题&#xff0…...

OpenHarmony开发案例:【分布式遥控器】

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

如何将Oracle 中的部分不兼容对象迁移到 OceanBase

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

Python也可以合并和拆分PDF,批量高效!

PDF是最方便的文档格式&#xff0c;可以在任何设备原样且无损的打开&#xff0c;但因为PDF不可编辑&#xff0c;所以很难去拆分合并。 知乎上也有人问&#xff0c;如何对PDF进行合并和拆分&#xff1f; 看很多回答推荐了各种PDF编辑器或者网站&#xff0c;确实方法比较多。 …...

python笔记(14)迭代器和生成器

迭代器的优势 延迟计算&#xff1a;迭代器按需提供数据&#xff0c;无需一次性加载整个数据集到内存中&#xff0c;特别适合处理大规模或无限数据流。资源效率&#xff1a;减少内存占用&#xff0c;尤其在处理大量数据时&#xff0c;避免一次性构建完整数据结构带来的开销。统…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

C++_核心编程_多态案例二-制作饮品

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

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 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 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

在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 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...