双向链表(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.rhkb.cn/news/382798.html

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

相关文章

MaxSite CMS v180 文件上传漏洞(CVE-2022-25411)

前言 CVE-2022-25411 是一个影响 Maxsite CMS v180 的远程代码执行漏洞。攻击者可以通过上传一个特制的 PHP 文件来利用这个漏洞,从而在受影响的系统上执行任意代码。 漏洞描述 该漏洞存在于 Maxsite CMS v180 的文件上传功能中。漏洞利用主要通过允许上传带有危…

Vue 3项目安装Element-Plus

Element Plus 是一个基于 Vue 3 的现代前端UI框架,它旨在提升开发体验,并为开发者提供高效、优雅的组件。如果你正在使用 Vue 3 进行项目开发,那么安装和集成 Element Plus 是一个不错的选择。在本文中,博主将详细介绍如何在 Vue …

【SASS/SCSS(三)】样式的复用与动态计算(@mixin和@function)

目录 一、mixin 1、定义复用的样式代码,接受传参,搭配include使用。 位置传参 关键词传参 ...语法糖接受传入的任意参数 2、在mixin中使用content,获取外部对mixin的追加内容 二、function 三、字符串——值得注意的点 很多时候&#…

智慧大棚数据库版

创建一个SMartBigHouse数据库 在数据库创建一个表用来存储数据 这边将id设为主键并将标识增量设为1 搭建Winfrom 搭建历史查询界面 串口数据,(这边是用的一个虚拟的串口工具,需要的话私) ModbusSerialMaster master;DataPointCollection wenduValues; //…

细说MCU用DMA控制ADC采样和串口传送的实现方法

目录 一、建立工程 1.相同的配置 2.配置ADC 3.配置DMA 二、代码修改 1.定义存储ADC采样结果的数组 2.启动ADC与定时器 3.编写主程序代码 4.重定义回调函数 5.查看结果 三、修改DMA模式 1. 修改DMA模式为Circular 2.查看结果 采用DMA(Direct Memory Access&#xf…

WSL2 Centos7 Docker服务启动失败怎么办?

wsl 安装的CentOS7镜像,安装了Docker之后,发现用systemctl start docker 无法将docker启动起来。 解决办法 1、编辑文件 vim /usr/lib/systemd/system/docker.service将13行注释掉,然后在下面新增14行的内容。然后保存退出。 2、再次验证 可以发现,我们已经可以正常通过s…

关于Mysql的面试题(实时更新中~)

一、主键约束与“not null unique”区别 1、作为Primary Key的域/域组不能为null,而Unique Key可以。 2、在一个表中只能有一个Primary Key,而多个Unique Key可以同时存在。unique not null 可以 将表的一列或多列定义为唯一性属性,而prima…

redis的集群模式

目录 1. 为什么使用redis集群 2. 主从模式 2.1修改配置文件 2.2 开启三台redis服务 2.3配置主从关系 3. 哨兵模式 3.1 监控功能 3.2 选举的机制 3.3 准备条件 4. 去中心化模式 4.1 准备三主三从 4.2 启动redis 4.3 分配槽以及主从关系 4.4 命令行的客户端 redis提供…

CAD框架介绍

1、适用范围:矢量编辑软件如 服装模板软件、CAD软件、绘图软件 2、支持PLT,DXF,PDF,GCode(服装裁割指令)等矢量文件导入 3、支持简易的自动手动排料 4、直线,曲线等编辑功能 5、分页输出绘图指令 6、良好的框架结构:绘图引擎…

d3d12.dll 文件缺失如何解决?五种修复丢失问题的方法

d3d12.dll 文件缺失如何解决?它为什么会不见呢?今天,我们将探讨 d3d12.dll 文件的重要性、原因以及丢失时的解决策略。本文将全面介绍 d3d12.dll 文件,并提供五种修复丢失问题的方法。 d3d12.dll文件是什么的详细介绍 d3d12.dll …

laravel为Model设置全局作用域

如果一个项目中存在这么一个sql条件在任何情况下或大多数情况都会被使用,同时很容易被开发者遗忘,那么就非常适用于今天要提到的这个功能,Eloquent\Model的全局作用域。 首先看一个示例,有个数据表,结构如下&#xff1…

深入浅出WebRTC—NACK

WebRTC 中的 NACK(Negative Acknowledgment)机制是实时通信中处理网络丢包的关键组件。网络丢包是常见的现象,尤其是在无线网络或不稳定连接中。NACK 机制旨在通过请求重传丢失的数据包来减少这种影响,从而保持通信的连续性和质量…

vue学习笔记(十一)——开发心得(axios的封装、promise细节、vue-router开发中的使用)

1. axios的网络请求的封装 1.1 为什么要封装api? 代码分层,便于以后的修改,无需触碰逻辑页面 目标: 网络请求,不散落在各个逻辑页面里,封装起来方便以后修改 1.2 封装api步骤 ① 在项目 src 下新建目录 utlis &am…

C++——初识模板

前言 模板是C中的重大板块,是使C真正超越C语言的工具,在C模板没有设计出来之前其实C是没有那么被行业和社会所认可的,本节我们将初步了解C中的模板(仅作大致讲解,具体的细枝末节将会再过几节讲解)&#xf…

Qt多语言功能实现

本文介绍Qt多语言功能实现。 应用程序多语言支持是常用功能,比如产品需要出口到不同语种的国家。采用Qt的多语言支持工具可以方便实现应用程序的多语言功能。本文以中英文语言切换为例,简要介绍Qt的多语言功能实现。 1.界面设计 界面设计需要考虑使用…

【数据分享】2013-2022年我国省市县三级的逐日SO2数据(excel\shp格式\免费获取)

空气质量数据是在我们日常研究中经常使用的数据!之前我们给大家分享了2000——2022年的省市县三级的逐日PM2.5数据和2013-2022年的省市县三级的逐日CO数据(均可查看之前的文章获悉详情)! 本次我们分享的是我国2013——2022年的省…

数据隐私保护与区块链技术的结合:新兴趋势分析

在当今数字化时代,数据隐私保护成为了一个备受关注的重要话题。随着个人数据的不断生成和流通,如何有效保护用户的隐私成为了技术创新的一个重要方向。区块链技术作为一种去中心化、安全性高且可追溯的技术手段,正在逐渐成为解决数据隐私保护…

golang 基础 泛型编程

(一) 示例1 package _caseimport "fmt"// 定义用户类型的结构体 type user struct {ID int64Name stringAge uint8 }// 定义地址类型的结构体 type address struct {ID intProvince stringCity string }// 集合转列表函数&#…

杰发科技Bootloader(2)—— 基于7840的Keil配置地址

序 在7840的sample代码里面有一个简单的Boot跳转APP的示例 PFlash地址从0开始 DFlash的地址从1000000开始 Boot解析 他的boot地址配置为0 Boot的代码主要是这几行,主要作用就是Flash的跳转 int main(void) {SystemClock_Config();InitDebug();printf("demo…

Leetcode 721.账户合并(hash+dfs)☆

思路: 最核心的地方在于如何合并?这里是通过具有相同的email进行账户的合并,这个相同的email类似于图中的共同节点将两个账户连接起来,所以将原来 账户名 -> 邮件1 邮件2.。。变成hash 邮件1 ->账户id1,账户id2…