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

【(数据结构)— 双向链表的实现】

(数据结构)— 双向链表的实现

  • 一.双向链表的结构
  • 二. 双向链表的实现
    • 2.1 头文件 ——双向链表的创建及功能函数的定义
    • 2.2 源文件 ——双向链表的功能函数的实现
    • 2.3 源文件 ——双向链表功能的测试
    • 2.4 双向链表各项功能测试运行展示
      • 2.4.1 双向链表的初始化 ——(以调试窗口展示)
      • 2.4.2 双向链表的尾插 ——(以打印展示)
      • 2.4.3 双向链表的头插 ——(以打印展示)
      • 2.4.4 双向链表的尾删 ——(以打印展示)
      • 2.4.5 双向链表的头删 ——(以打印展示)
      • 2.4.6 双向链表的查找指定位置及在指定位置之后插入 ——(以打印展示)
      • 2.4.7 双向链表的查找指定位置及删除指定位置的数据 ——(以打印展示)
      • 2.4.8 双向链表的销毁 ——(以调试窗口展示)
  • 三.顺序表和双向链表的优缺点分析

一.双向链表的结构

在这里插入图片描述

注意:这里的“带头”跟前面我们说的“头节点”是两个概念,实际前面的在单链表阶段称呼不严
谨,但是为了同学们更好的理解就直接称为单链表的头节点。
带头链表里的头节点,实际为“哨兵位”,哨兵位节点不存储任何有效元素,只是站在这里“放哨
的”
“哨兵位”存在的意义:
遍历循环链表避免死循环。

二. 双向链表的实现

2.1 头文件 ——双向链表的创建及功能函数的定义

List.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int LTDatatype;
//链表的结构创建
typedef struct ListNode
{LTDatatype data;struct ListNode* next;struct ListNode* prev;
}LTNode;
//打印
void LTPrint(LTNode* phead);//双链表的初始化//销毁
//void LTInit(LTNode** pphead);
LTNode* LTInit();
//销毁
//void LTDestroy(LTNode** pphead);
void LTDestroy(LTNode* phead);
//头部/尾部/插入/删除
//尾插
void LTPushBack(LTNode* phead, LTDatatype x);
//头插
void LTPushFront(LTNode* phead, LTDatatype x);
//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);
//再pos位置之后插入/删除 
void LTInsrt(LTNode* pos, LTDatatype x);
void LTErase(LTNode* pos);
//查找pos
LTNode* LTFind(LTNode* phead, LTDatatype x);

2.2 源文件 ——双向链表的功能函数的实现

List.c
#include"List.h"//初始化
//二级指针初始化
//前提是我们需要传入一个头节点
//void LTInit(LTNode** pphead)
//{
//	*pphead = (LTNode*)malloc(sizeof(LTNode));
//	if (*pphead == NULL)
//	{
//		perror("malloc error");
//		return;
//	}
//	(*pphead)->data = -1;//哨兵位
//	(*pphead)->next = (*pphead)->prev = *pphead;
//	
//}
//一级指针初始化
//不需要传参,只需要返回一个地址即可
LTNode* LTInit()
{LTNode* phead = (LTNode*)malloc(sizeof(LTNode));if (phead == NULL){perror("malloc error");return;}phead->data = -1;phead->next = phead->prev = phead;return phead;
}
//链表的销毁
//参数是二级指针
//void LTDestroy(LTNode** pphead)
//{
//	assert(pphead && *pphead);
//	LTNode* cur = (*pphead)->next;
//	while(cur!=(*pphead))
//	{
//		LTNode* next = cur->next;
//		free(cur);
//		cur = next;
//	}
//	free(*pphead);
//	*pphead = NULL;
//}
//参数是一级指针
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);phead = NULL;
}void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){printf("%d->", cur->data);cur = cur->next;}printf("\n");}
LTNode* LTBuyNode(LTDatatype x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));node->data = x;node->next = node->prev = NULL;return node;
}
//尾插
void LTPushBack(LTNode* phead, LTDatatype x)
{LTNode* node = LTBuyNode(x);//先处理插入的节点的前驱和后继指针node->next = phead;node->prev = phead->prev;//然后考虑哨兵位的前驱和尾节点的后继指针phead->prev->next = node;phead->prev = node;}
//头插
void LTPushFront(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* node = LTBuyNode(x);//先处理插入节点的前驱和后继的指针node->next = phead->next;node->prev = phead;//然后处理phead,phead->nextphead->next->prev = node;phead->next = node;}
//尾删
void LTPopBack(LTNode* phead)
{assert(phead);//链表不能为空,链表中只有一个哨兵位节点assert(phead->next != phead);LTNode* del = phead->prev;//先处理 del->prevdel->prev->next = phead;//接着处理pheadphead->prev = del->prev;free(del);del = NULL;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;//先处理del->nextdel->next->prev = phead;//接着处理pheadphead->next = del->next;free(del);del = NULL;
}
//在pos位置之后插入
void LTInsrt(LTNode* pos, LTDatatype x)
{LTNode* node = LTBuyNode(x);//先处理node的前驱和后继node->next = pos->next;node->prev = pos;//接着处理pos->next,pos->next->prevpos->next = node;pos->next->prev = node;
}
//删除pos位置的数据
void LTErase(LTNode* pos)
{assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}
//查找pos
LTNode* LTFind(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

2.3 源文件 ——双向链表功能的测试

test.c
#include"List.h"void ListTest()
{/*LTNode* plist = NULL;LTInit(&plist);*///初始化LTNode* plist = LTInit();//尾插LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);//头插/*LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);*///尾删/*LTPopBack(plist);LTPopBack(plist);*///头删/*LTPopFront(plist);LTPopFront(plist);*/LTNode* find = LTFind(plist, 4);//在pos位置之后插入/*LTInsrt(find, 5);*///删除pos位置的数据LTErase(find);LTPrint(plist);//销毁链表//LTDestroy(&plist);//一级指针销毁需要手动将plist置空LTDestroy(plist);plist = NULL;}int main()
{ListTest();return 0;
}

2.4 双向链表各项功能测试运行展示

2.4.1 双向链表的初始化 ——(以调试窗口展示)

//初始化
LTNode* plist = LTInit();

在这里插入图片描述

2.4.2 双向链表的尾插 ——(以打印展示)

//尾插
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);

在这里插入图片描述

2.4.3 双向链表的头插 ——(以打印展示)

//头插
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);

在这里插入图片描述

2.4.4 双向链表的尾删 ——(以打印展示)

//尾删
LTPopBack(plist);
LTPopBack(plist);

在这里插入图片描述

2.4.5 双向链表的头删 ——(以打印展示)

//头删
LTPopFront(plist);
LTPopFront(plist);

在这里插入图片描述

2.4.6 双向链表的查找指定位置及在指定位置之后插入 ——(以打印展示)

//查找指定位置pos
LTNode* find = LTFind(plist, 4);
//在pos位置之后插入
LTInsrt(find, 5);

在这里插入图片描述

2.4.7 双向链表的查找指定位置及删除指定位置的数据 ——(以打印展示)

// //查找指定位置pos
LTNode* find = LTFind(plist, 4);
//删除pos位置的数据
LTErase(find);

在这里插入图片描述

2.4.8 双向链表的销毁 ——(以调试窗口展示)

//销毁链表
//LTDestroy(&plist);
//一级指针销毁需要手动将plist置空
LTDestroy(plist);
plist = NULL;

在这里插入图片描述

三.顺序表和双向链表的优缺点分析

在这里插入图片描述

相关文章:

【(数据结构)— 双向链表的实现】

&#xff08;数据结构&#xff09;— 双向链表的实现 一.双向链表的结构二. 双向链表的实现2.1 头文件 ——双向链表的创建及功能函数的定义2.2 源文件 ——双向链表的功能函数的实现2.3 源文件 ——双向链表功能的测试2.4 双向链表各项功能测试运行展示2.4.1 双向链表的初始化…...

酷克数据发布HD-SQL-LLaMA模型,开启数据分析“人人可及”新时代

随着行业数字化进入深水区&#xff0c;企业的关注点正在不断从“数字”价值转向“数智”价值。然而&#xff0c;传统数据分析的操作门槛与时间成本成为了掣肘数据价值释放的阻力。常规的数据分析流程复杂冗长&#xff0c;需要数据库管理员设计数据模型&#xff0c;数据工程师进…...

FL Studio21最新中文破解进阶高级完整版安装下载教程

目前水果软件最版本是FL Studio21&#xff0c;它让你的计算机就像是全功能的录音室&#xff0c;大混音盘&#xff0c;非常先进的制作工具&#xff0c;让你的音乐突破想象力的限制。喜欢音乐制作的小伙伴千万不要错过这个功能强大&#xff0c;安装便捷的音乐软件哦&#xff01;如…...

MDN--Web性能

CSS 动画与 JavaScript 动画 动画的实现可以有很多种方式&#xff0c;比如 CSS transition 和 animation 或者基于 JavaScript 的动画(使用 requestAnimationFrame()) CSS 过渡和动画 CSS transiton :创建当前样式与结束状态样式之间的动画。尽管一个元素处于过渡状态中&…...

Vue3.js:自定义组件 v-model

Vue3的自定义v-model和vue2稍有不同 文档 https://cn.vuejs.org/guide/components/v-model.html 目录 原生组件自定义组件CustomInput实现代码1CustomInput实现代码2 v-model 的参数 原生组件 <input v-model"searchText" />等价于 <input:value"s…...

AI虚拟主播开发实战(附源码)

人工智能 文章目录 人工智能前言 前言 https://blog.csdn.net/icemanyandy/article/details/124035967...

innoDB如何解决幻读

Mysql的事务隔离级别 Mysql 有四种事务隔离级别&#xff0c;这四种隔离级别代表当存在多个事务并发冲突时&#xff0c;可能出现的脏读、不可重复读、幻读的问题。其中 InnoDB 在 RR 的隔离级别下&#xff0c;解决了幻读的问题 事务隔离级别脏读不可重复读幻读未提交读&#xff…...

Git - 导出(archive)、忽略(gitignore)、隐藏(Stash)、合并冲突(merge)的解决方法

概述 本次集中总结了Git4个常规操作&#xff0c;导出(archive)、忽略(gitignore)、隐藏(Stash)、合并冲突(merge)的解决方法&#xff0c;希望帮助到正在辛苦寻找的你。 .gitignore忽略文件 之前开发和部署服务比较仓促&#xff0c;所以有很多图片文件一起加载到服务中&#…...

【Javascript】‘var‘ is used instead of ‘let‘ or ‘const‘

解决&#xff1a; 设置完之后,var 就不会再出现黄色波浪线警告...

金融统计学方法:神经网络

目录 1.神经网络 2.深度神经网络 3.案例分析 1.神经网络 神经网络是模仿人脑神经元工作原理而设计的一种算法模型。在一个基本的神经网络中&#xff0c;存在多个“神经元”或称为“节点”&#xff0c;这些节点被组织成多个层次。每个节点都接收前一层的输入&#xff0c;进行…...

任何人不知道这款超实用的配音软件,我都会伤心的OK?

看完一段精彩的视频&#xff0c;令人陶醉的原因之一就是配音&#xff0c;有的充满感情&#xff0c;有的字正腔圆&#xff0c;相信很多人都不知道这样的声音是怎么配出来的&#xff1f;今天&#xff0c;小编就来给大家分享一款超实用的配音软件&#xff0c;不仅操作简单&#xf…...

Linux查看日志文件的常用命令

1、查看文件最后1000行内容 tail -n 1000 filename 2、实时查看文件最后1000行内容&#xff0c;动态刷新 tailf -n 1000 filename tail -f -n 1000 filename 3、按照关键字搜索日志 cat filename | grep 关键字 4、按照关键字搜索并包含前(后)多少行 【&#xff08;A前B后C前…...

AcWing算法分享系列——二分图

这是AcWing算法分享系列的第一篇文章,我们先从图论的知识下手(因为我觉得图论的只是好理解些)。 这次我们主要讲的就是二分图,二分图这次我们主要讲的就是最基础的两个板块: 二分图的判定(染色法)二分图的完美匹配(匈牙利算法)我们这一篇文章先从二分图的概念开始入手…...

【Excel单元格类型的解析校验】Java使用POI解析excel数据

一、使用的maven依赖&#xff1a; <dependency><groupId>com.alibaba</groupId><artifactId>easyexcel</artifactId><version>2.1.7</version> </dependency> <dependency><groupId>org.apache.poi</groupId&…...

【运维知识高级篇】超详细的Jenkins教程5(pipeline流水线配置+分布式构建)

CI/CD是持续集成&#xff0c;持续部署&#xff0c;集成就是开发人员通过自动化编译&#xff0c;发布&#xff0c;测试的手段集成软件&#xff0c;在开发的测试环境上测试发现自己的错误&#xff1b;持续部署是自动化构建&#xff0c;部署&#xff0c;通常也是在测试环境上进行&…...

为什么要在电影院装监控?有什么作用?

近期小编在网上看到有很多人在讨论&#xff1a;电影院的摄像头有多高清&#xff1f;看电影时的小动作放映员都能看得一清二楚&#xff1f;答案是&#xff1a;是的。但大家也不必有心理负担&#xff0c;电影院的监控目的不是为了监控观众&#xff0c;更多的是为了保障观影者的权…...

攻防世界题目练习——Web引导模式(三)(持续更新)

题目目录 1. mfw2. Cat3.4.5. 1. mfw 进去看到网页和页面内容如下&#xff1a; 看到url的参数 ?pageabout &#xff0c;我以为是文件包含什么的&#xff0c;反复试了几次&#xff0c;想用 …/…/…/…/etc/passwd &#xff0c;但是发现.似乎被过滤了&#xff0c;实在不知道怎…...

Python制作PDF转Word工具(Tkinter+pdf2docx)

一、效果样式 二、核心点 1. 使用pdf2docx完成PDF转换Word 安装pdf2docx可能会报错&#xff0c;安装完成引入from pdf2docx import Converter运行也可能报错&#xff0c;可以根据报错提示看缺少那些库&#xff0c;先卸载pip uninstall xxx,使用pip install python-docx -i htt…...

有哪些手段可以优化 CSS, 提高性能

CSS优化是Web开发中提高性能和用户体验的关键部分。下面详细解释一些CSS优化的方法&#xff0c;以提高性能&#xff1a; 合并和压缩CSS文件: 合并文件&#xff1a;将多个CSS文件合并成一个&#xff0c;以减少HTTP请求次数。这可以通过构建工具&#xff08;如Webpack&#xff09…...

ARM可用的可信固件项目简介

安全之安全(security)博客目录导读 目录 一、TrustedFirmware-A (TF-A) 二、MCUboot 三、TrustedFirmware-M (TF-M) 四、TF-RMM 五、OP-TEE 六、Mbed TLS 七、Hafnium 八、Trusted Services 九、Open CI 可信固件为Armv8-A、Armv9-A和Armv8-M提供了安全软件的参考实现…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...