当前位置: 首页 > 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;避免一次性构建完整数据结构带来的开销。统…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...