C语言:双链表

一、什么是双链表?

双链表,顾名思义,是一种每个节点都包含两个链接的链表:一个指向下一个节点,另一个指向前一个节点。这种结构使得双链表在遍历、插入和删除操作上都表现出色。与单链表相比,双链表不仅可以从头节点开始遍历,还可以从尾节点开始遍历,甚至从中间某个节点开始双向遍历。

二、双链表的特点

双向性:每个节点都包含两个指针,一个指向前一个节点,一个指向后一个节点。这使得双链表在遍历上更加灵活。
动态性:链表的大小可以根据需要动态地增加或减少,无需预先分配固定大小的内存空间。
三、实现双链表

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

三、实现的功能

LTNode* LTInit();// 初始化双链表
void LTDestroy(LTNode* phead);//销毁
void LTPrint(LTNode* phead);//打印
bool LTEmpty(LTNode* phead);//判断链表是否为空·void LTPushBack(LTNode* phead, LTDataType x);//尾插
void LTPopBack(LTNode* phead);//尾删void LTPushFront(LTNode* phead, LTDataType x);//头插
void LTPopFront(LTNode* phead);//头删
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);//指定删除
LTNode* LTFind(LTNode* phead, LTDataType x);//查找

 1.创建节点

// 创建新的双链表节点  
LTNode* LTBuyNode(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函数在堆上动态地分配内存空间,以存储LTNode结构体的大小。
检查malloc是否成功分配了内存。如果返回NULL,表示内存分配失败,此时调用perror函数打印错误消息,并使用exit(1)退出程序。
如果内存分配成功,将新节点的数据成员data设置为参数x的值。
初始化新节点的next和prev指针为NULL,表示这个新节点在创建时并不指向任何其他的节点。
返回指向新创建节点的指针。

2.初始化

LTNode* LTInit() {  LTNode* pheda = LTBuyNode(-1); // 使用-1作为哨兵位头节点的数据  pheda->next = pheda; // 指向自己,表示链表为空  pheda->prev = pheda;  return pheda;  
}

 3.双链表的尾插

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);// 创建一个新节点newnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;}

newnode->prev = phead->prev; 将新节点的prev指针设置为当前链表的尾节点。
newnode->next = phead; 将新节点的next指针设置为头节点。

phead->prev->next = newnode; 更新当前尾节点的next指针,使其指向新节点。
phead->prev = newnode; 更新头节点的prev指针,使其指向新节点

4.双链表的尾删

//尾删
void LTPopBack(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}

prev指针指向链表的最后一个节点

del->prev->next = phead; 和 phead->prev = del->prev; 这两行代码更新了链表的链接,将尾节点从链表中移除。

 5.双链表的头插

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode ->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}

newnode ->next = phead->next;将新节点的next指针指向当前链表的第一个节点

newnode->prev = phead;将新节点的prev指针指向链表的头节点

phead->next->prev = newnode;更新当前链表第一个节点的prev指针,使其指向新节点。

phead->next = newnode;:更新链表的头节点的next指针,使其指向新节点,这样新节点就成为了链表的第一个节点。

6.双链表的头删

void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;phead->next = del->next;phead->next->prev = phead;free(del);del = NULL;}

 LTNode* del = phead->next;:将待删除的节点的地址赋给del指针。
phead->next = del->next;:更新链表的头节点的next指针,使其跳过待删除的节点,直接指向下一个节点。
phead->next->prev = phead;:由于我们刚刚更新了phead->next,现在它指向的是原第一个节点的下一个节点。我们将这个新节点的prev指针更新为指向链表的头节点。

7.双链表的打印 

void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d ", pcur->data);pcur = pcur->next;}printf("\n");
}

8.在pos位置之后插入数据

void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);	newnode-> next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}

9.指定删除     

void LTErase(LTNode* pos)
{assert(pos);assert(pos != pos->next);pos->prev->next = pos->next;// 更新pos的前一个节点的next指针pos->next->prev = pos->prev;//更新pos的下一个节点的prev指针free(pos);pos = NULL;
}

 10.判空

bool LTEmpty(LTNode* phead)
{return phead->next == phead;
}

 11.销毁

//销毁
void LTDestroy(LTNode* phead)
{LTNode* cur = phead->next;while (cur != phead){LTNode* tmp = cur;cur = cur->next;free(tmp);}free(phead);
}

四、全部源码

LTNode* LTBuyNode(LTDataType x)
{LTNode* Node = (LTNode*)malloc(sizeof(LTNode));if (Node == NULL){perror("malloc fail!");exit(1);}Node->data = x;Node->next = NULL;  Node->prev = NULL;   return Node;
}
LTNode* LTInit() {LTNode* pheda = LTBuyNode(-1); // 使用-1作为哨兵头节点的数据  pheda->next = pheda; // 指向自己,表示链表为空  pheda->prev = pheda;  return pheda;
}//销毁
void LTDestroy(LTNode* phead)
{LTNode* cur = phead->next;while (cur != phead){LTNode* tmp = cur;cur = cur->next;free(tmp);}free(phead);
}
//打印
void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d ", pcur->data);pcur = pcur->next;}printf("\n");
}
//判断链表是否为空·
bool LTEmpty(LTNode* phead)
{return phead->next == phead;
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;}
//尾删
void LTPopBack(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode ->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;phead->next = del->next;phead->next->prev = phead;free(del);del = NULL;}
//查找LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur=cur->next;}return NULL;
}在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);	newnode-> next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}//指定删除
void LTErase(LTNode* pos)
{assert(pos);assert(pos != pos->next);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

五、结语 

让我们一起在编程的道路上不断前行,创造更加美好的未来!

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Rust 实战丨SSE(Server-Sent Events)

📌 SSE(Server-Sent Events)是一种允许服务器向客户端浏览器推送信息的技术。它是 HTML5 的一部分,专门用于建立一个单向的从服务器到客户端的通信连接。SSE的使用场景非常广泛,包括实时消息推送、实时通知更新等。 S…

C++中的priority_queue和deque以及适配器

C中的priority_queue和deque 一丶 priority_queue1.1 priority_queue的介绍1.2 priority_queue的使用1.3 priority_queue的模拟实现 二丶 deque2.1 deque的简单介绍2.2 deque的缺陷2.3 为什么要选择deque作为stack和queue的迭代器 三丶 容器适配器3.1 什么是适配器3.2 STL标准库…

Effective Java 2 遇到多个构造器参数时要考虑使用构建器

第2个经验法则:用遇到多个构造器参数时要考虑使用构建器(consider a builder when faced with many constructor parameters) 上一条讨论了静态工厂相对于构造器来说有五大优势。但静态工厂和构造器有个共同的局限性:它 们都不能很好地扩展到…

开源网关Apache APISIX启用JWT身份验证

说明: 本文APISIX的配置参考我之前写的《Ubuntu部署Apache APISIX》 创建最小API 首先,确保你已经安装了.NET 6 SDK。创建文件夹“MinimalApiDemo”,VS Code打开文件夹,打开终端 dotnet new web -o MinimalApiDemo cd Minimal…

【JMeter接口测试工具】第二节.JMeter基本功能介绍(上)【入门篇】

文章目录 前言一、获取所有学院信息接口执行二、线程组的介绍 2.1 并发和顺序执行 2.2 优先和最后执行线程组 2.3 线程组的设置细节三、HTTP请求的介绍四、查看结果树的配置使用总结 前言 一、获取所有学院信息接口执行 我们先针对一条简单的接口进行执行&#…

代码随想录刷题笔记-哈希表篇

文章目录 242 有效的字母异位词(easy)力扣地址题目描述题目实例解题思路代码实现 383 赎金信(easy)力扣地址题目描述题目实例解题思路代码实现 49 字母异位词分组(mid)力扣地址题目描述题目实例解题思路代码实现 438 找到字符串中所有字母异位词(mid)力扣地址题目描述题目实例解…

3038. 相同分数的最大操作数目 I(Rust模拟击败100%Rust用户)

题目 给你一个整数数组 nums ,如果 nums 至少 包含 2 个元素,你可以执行以下操作: 选择 nums 中的前两个元素并将它们删除。 一次操作的 分数 是被删除元素的和。 在确保 所有操作分数相同 的前提下,请你求出 最多 能进行多少次…

SpringBoot整合钉钉实现消息推送

前言 钉钉作为一款企业级通讯工具,具有广泛的应用场景,包括但不限于团队协作、任务提醒、工作汇报等。 通过Spring Boot应用程序整合钉钉实现消息推送,我们可以实现以下功能: 实时向指定用户或群组发送消息通知。自定义消息内容…

Python进阶-部署Flask项目(以TensorFlow图像识别项目WSGI方式启动为例)

本文详细介绍了如何通过WSGI方式部署一个基于TensorFlow图像识别的Flask项目。首先简要介绍了Flask框架的基本概念及其特点,其次详细阐述了Flask项目的部署流程,涵盖了服务器环境配置、Flask应用的创建与测试、WSGI服务器的安装与配置等内容。本文旨在帮…

【iOS】——Runtime学习

文章目录 一、Runtime介绍二、Runtime消息传递三、实例对象、类对象、元类对象四、isa_t结构体的具体实现五、cache_t的具体实现六、class_data_bits_t的具体实现七、Runtime消息转发动态方法解析备用接收者完整消息转发 一、Runtime介绍 iOS的Runtime,通常称为Obj…

使用汇编和proteus实现仿真数码管显示电路

proteus介绍: proteus是一个十分便捷的用于电路仿真的软件,可以用于实现电路的设计、仿真、调试等。并且可以在对应的代码编辑区域,使用代码实现电路功能的仿真。 汇编语言介绍: 百度百科介绍如下: 汇编语言是培养…

【通俗易懂的Python入门基础详细教程,可分享哦!!!】

Python,作为一种高级编程语言,自其诞生以来就以其独特的魅力吸引了无数开发者。以下是对学习Python的简要介绍: 一、Python的起源与发展 Python由荷兰计算机科学家吉多范罗苏姆于1990年代初设计,其设计初衷是作为ABC语言的替代品…

计算机网络复习题

期末题库复习1 一. 单选题(共32题,100分) 1. (单选题) 在脉冲起始时刻,有无跳变来表示“0”和“1”,且在脉冲中间时刻始终发生跳变的编码是( )。 A.非归零码 B.曼彻斯特编码 C.归零码 D.差…

Facebook革新:数字社交的下一个阶段

在数字化时代,社交网络已经成为人们生活中不可或缺的一部分。作为全球最大的社交网络平台之一,Facebook一直在不断创新,引领着数字社交的发展。然而,随着科技的不断进步和社交需求的变化,Facebook正在走向一个新的阶段…

k8s和deepflow部署与测试

Ubuntu-22-LTS部署k8s和deepflow 环境详情: Static hostname: k8smaster.example.net Icon name: computer-vm Chassis: vm Machine ID: 22349ac6f9ba406293d0541bcba7c05d Boot ID: 605a74a509724a88940bbbb69cde77f2 Virtualization: vmware Operating System: U…

STM32F103C8移植uCOSIII并以不同周期点亮两个LED灯(HAL库方式)【uCOS】【STM32开发板】【STM32CubeMX】

STM32F103C8移植uC/OSIII并以不同周期点亮两个LED灯(HAL库方式)【uC/OS】【STM32开发板】【STM32CubeMX】 实验说明 将嵌入式操作系统uC/OSIII移植到STM32F103C8上,构建两个任务,两个任务分别以1s和3s周期对LED进行点亮—熄灭的…

基于Python + Flask+ Mysq实现简易留言板

使用Python Flask Mysql实现简易留言板,包括网友编辑留言、修改留言,删除留言、分页显示四大功能。 写出留言板建设过程,包括开发使用工具、留言板模块设计、数据库设计、页面设计、关键技术。 留言板建设过程总结 一.开发使用…

一文学习yolov5 实例分割:从训练到部署

一文学习yolov5 实例分割:从训练到部署 1.模型介绍1.1 YOLOv5结构1.2 YOLOv5 推理时间 2.构建数据集2.1 使用labelme标注数据集2.2 生成coco格式label2.3 coco格式转yolo格式 3.训练3.1 整理数据集3.2 修改配置文件3.3 执行代码进行训练 4.使用OpenCV进行c部署参考文…

燃料电池汽车践行者

前言 见《氢燃料电池技术综述》 见《燃料电池工作原理详解》 见《燃料电池发电系统详解》 见《燃料电池电动汽车详解》 见《氢燃料电池汽车行业发展》 现代汽车(中国) 现代汽车集团,自1998年成立氢燃料电池研发小组以来深耕氢燃料电池技术&am…

Python爬虫入门与登录验证自动化思路

1、pytyon爬虫 1.1、爬虫简介 Python爬虫是使用Python编写的程序,可以自动访问网页并提取其中的信息。爬虫可以模拟浏览器的行为,自动点击链接、填写表单、进行登录等操作,从而获取网页中的数据。 使用Python编写爬虫的好处是,…