双向链表(C语言版)

1. 双向链表的结构

注意:这里的“带头”跟单链表的“头结点”是两个概念,实际上在单链表阶段称呼不太严谨,但是为了更好地理解就直接称为单链表的头结点。带头链表里的头结点,实际为“哨兵位”,哨兵位结点不存储任何有效元素,只是站在这里“放哨的”。

哨兵位”存在的意义:

遍历循环链表避免死循环。

2. 双向链表的实现

2.1 双向链表结构体

typedef int LTDataType;
// 定义双向链表节点的结构
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;

2.2 申请结点

// 申请节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail!");exit(1);}node->data = x;node->next = node->prev = node;return node;
}

2.3 初始化

// 初始化
void LTInit(LTNode** pphead)
{// 给链表创建一个哨兵位*pphead = LTBuyNode(-1);
}

2.4 链表的销毁

// 销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}// 此时pcur指向phead,而phead还没有被销毁free(phead);phead = NULL;
}

2.5 链表的打印

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

2.6 链表的尾插

// 尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newNode = LTBuyNode(x);// 旧的尾结点就是phead->prev// 先让新的尾结点的前指针指向旧的尾结点newNode->prev = phead->prev;newNode->next = phead;	// 再让新的尾结点的下一级指针指向头结点(哨兵位)// 旧的尾结点下一级指针指向新的尾结点phead->prev->next = newNode;phead->prev = newNode;	// 再让头结点(哨兵位)的下一级指针指向新的尾结点
}

2.7 链表的头插

// 头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newNode = LTBuyNode(x);// 要改变的结点:phead newNode phead->nextnewNode->next = phead->next;	// 先让新的尾结点的下一级指针指向头结点的下一级指针的结点newNode->prev = phead;	// 让新的尾结点的前指针指向头结点//phead->next->prev = newNode;	// 指向头结点的下一级指针的结点的下一级指针指向新的结点//phead->next = newNode;	// 头结点的下一级指针指向新的结点// 这样也是可行的phead->next = newNode;	// 头结点的下一级指针指向新的结点newNode->next->prev = newNode;	// 指向头结点的下一级指针的结点的下一级指针指向新的结点}

2.8 链表的尾删

// 尾删
void LTPopBack(LTNode* phead)
{// 链表必须有效且链表不能为空(只有一个哨兵位)assert(phead && phead->next != phead);LTNode* del = phead->prev;// 影响的指针:phead del->prev deldel->prev->next = phead;phead->prev = del->prev;// 删除del节点free(del);del = NULL;
}

2.9 链表的头删

// 头删
void LTPopFront(LTNode* phead)
{// 链表必须有效且链表不能为空(只有一个哨兵位)assert(phead && phead->next != phead);LTNode* del = phead->next;// 影响的指针:phead del del->nextphead->next = del->next;del->next->prev = phead;// 删除del节点free(del);del = NULL;
}

2.10 链表查找数据

// 查找数据
LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}// 没有找到return NULL;
}

2.11 在pos位置之后插入数据

// 在 pos 位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newNode = LTBuyNode(x);// 影响的指针:pos newNode pos->nextnewNode->next = pos->next;newNode->prev = pos;pos->next->prev = newNode;pos->next = newNode;
}

2.12 删除pos结点

// 删除 pos节点
void LTErase(LTNode* pos)
{// pos理论上来说不能为phead,但是没有参数phead,无法增加校验assert(pos);// 影响的指针:pos->prev pos pos->nextpos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

运维锅总浅析网络攻击与防范

本文介绍常见的网络攻击手法及防御措施,并进一步介绍如何进行安全教育和培训、攻击溯源。希望对您提高网络安全防范意识有所帮助! 一、常见的网络攻击手法 网络攻击手法多种多样,以下是一些常见的网络攻击手法及其基本原理: 1.…

vue 两个页面切换, 再回到当前页,还是离开前的数据

1、要保证页面的name 和 建路由的大小写一致 2、页面不用生命周期--activated 调接口刷新

嵌入式系统上通过crontab表达式实现基于绝对时间的秒级定时任务

摘要 在嵌入式系统开发中,定时任务是确保系统按预定计划正确执行功能的关键。通过结合 crontab 表达式和 C 语言,可以设计出精准且灵活的定时任务系统。本博客详细描述了如何在嵌入式开发中,使用 crontab 表达式来实现基于绝对时间的定时任务…

农业农村大数据底座:实现智慧农业的关键功能

随着信息技术的快速发展,农业领域也在逐步实现数字化转型。农业农村大数据底座作为支持智慧农业发展的重要基础设施,承载了多种关键功能,为农业生产、管理和决策提供了前所未有的支持和可能性。 ### 1. 数据采集与监测 农业农村大数据底座首…

鸿蒙OpenHarmony Native API【NativeWindow】

NativeWindow Overview Description: 提供NativeWindow功能,主要用来和egl对接 syscap SystemCapability.Graphic.Graphic2D.NativeWindow Since: 8 Version: 1.0 Summary Files File NameDescription[external_window.h]定义获取和使用NativeWindow的相…

百度网盘批量转存程序

百度网盘批量转存程序,基于 Python 3.10 Tkinter 构建,主要用于批量转存网络上分享的资源到自己的百度网盘。此外还带有批量分享和批量检测链接有效性的功能。 程序主界面: 下载地址:https://pan.quark.cn/s/c739ee25b238

【算法专题】链表算法题

1. 链表常用操作 相信大家在学习数据结构的过程中已经接触过许多链表相关的题目了,在正式开始刷题之前,我想让大家先回顾一下过去处理链表相关问题时的一些常见操作。 首先肯定就是创建新节点了,如果使用C语言编写代码,我…

Mac m1安装 MongoDB 7.0.12

一、下载MongoDB MongoDB 社区版官网下载 二、安装配置MongoDB 1.解压下载的压缩包文件,文件夹重命名为mongodb; 2.将重命名为mongodb的文件夹,放在/usr/local 目录下 3.在/usr/local/mongodb 目录下,新建data 和 log这两个文件夹&#…

基于VUE的软件项目开发管理系统/项目管理系统/软件开发过程管理系统的设计与实现

摘 要 在Internet高速发展的今天,我们生活的各个领域都涉及到计算机的应用,其中包括软件项目开发管理系统的网络应用,在外国软件项目开发管理系统已经是很普遍的方式,不过国内的软件项目开发管理可能还处于起步阶段。软件项目开发…

手把手教你打造自己的AI聊天机器人程序(讯飞星火API)

案例背景 最近发现科大的讯飞星火大模型可以申请API试用了,我一直想用chatgpt的API,一是因为收费买不起,二是因为网络不方便..... 现在有了科大讯飞这个国内免费的,当然要试试。 目前讯飞星火可以申请试用他们的模型API&#x…

python: math模块

在Python中,math模块是一个内置的标准库模块,它提供了对浮点数的数学运算支持。这个模块包含了一系列函数和常量,用于执行各种数学计算,比如幂运算、对数计算、三角函数计算、指数计算等。 以下是math模块的一些主要特性和功能&a…

【JavaEE】Spring Boot 自动装配原理(源码分析)

一. 前言 我们在写Spring Boot的程序代码的时候, 可以注入很多我们没有定义过的Bean.例如: Autowired private ApplicationContext applicationContext; Autowired public DataSourceTransactionManager transactionManager; Autowired public AutowireCapableBeanFactory …

【LeetCode】翻转二叉树

目录 一、题目二、解法完整代码 一、题目 给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。 示例 1: 输入:root [4,2,7,1,3,6,9] 输出:[4,7,2,9,6,3,1] 示例 2: 输入:root…

一个C++模板工厂的编译问题的解决。针对第三方库的构造函数以及追加了的对象构造函数。牵扯到重载、特化等

一窥模板的替换和匹配方式:偏特化的参数比泛化版本的还要多:判断是不是std::pair<,>。_stdpair模板参数太多-CSDN博客 简介 在一个项目里,调用了第三封的库,这个库里面有个类用的很多,而且其构…

Java语言程序设计基础篇_编程练习题**15.18(使用鼠标来移动一个矩形)

**15.18(使用鼠标来移动一个矩形) 请编写一个程序显示一个矩形。可以使用鼠标单击矩形内部并且拖动(即按住鼠标移动)矩形到鼠标的位置。鼠标点成为矩形的中央习题思路: 新建一个面板Pane(),新建一个Rectangle() 为Rectangle注册…

Cxx Primer-chap7

类的基本思想是数据抽象和封装,前者强调interface和implement分离,后者在此基础上,强调访问控制符(存疑)。同时类的实现者和使用者考虑的角度不同,前者考虑实现效率,后者仅需关注功能即可&#…

猫头虎分享已解决Bug || JSON Parsing Errors: json: cannot unmarshal

猫头虎分享已解决Bug 🐯 || JSON Parsing Errors: json: cannot unmarshal 摘要 在后端开发过程中,处理JSON数据时经常会遇到解析错误,尤其是json: cannot unmarshal错误。这类问题往往由于JSON数据格式与Go语言结构体不匹配引起。今天&…

vue字段判断是否可以鼠标悬浮或者点击跳转

通过字段判断是否可以鼠标悬浮展示颜色 是否点击 <span :class"[converBond.stkindustry ! null ? hoverSpan:,]"click"converBond.stkindustry ! null ?goToIndustry(converBond.stkindustryname,converBond.stkindustry):false">{{converBon…

尚品汇-sku存入Redis缓存(二十三)

目录&#xff1a; &#xff08;1&#xff09;分布式锁改造获取sku信息 &#xff08;2&#xff09;使用Redisson 分布式锁 AOP实现缓存 &#xff08;3&#xff09;定义缓存aop注解 &#xff08;1&#xff09;分布式锁改造获取sku信息 前面学习了本地锁的弊端&#xff0c;…

怎么使用github上传XXX内所有文件

要将 目录中的所有文件上传到 GitHub&#xff0c;你可以按照以下步骤进行&#xff1a; 创建一个新的 GitHub 仓库 登录到你的 GitHub 账户。 点击右上角的加号&#xff08;&#xff09;&#xff0c;选择 “New repository”。 输入仓库名称&#xff08;例如&#xff1a;202407…