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

94.【C语言】数据结构之双向链表的初始化,尾插,打印和尾删

目录

1.双向链表

2.结构体的定义

3.示意图

3.代码示例

1.双向链表的尾插

示意图

代码

main.c

List.h

List.c

详细分析代码的执行过程

双向链表的初始化

2.双向链表的打印

代码

3.双向链表的尾删


1.双向链表

以一种典型的双向链表为例:带头双向循环链表(带头:哨兵位的节点)

2.结构体的定义

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

3.示意图

head为带哨兵位的头节点,无有效数值,只储存第一个有效节点的地址,负责找到第一个节点

特点:

1.prev指向前一个节点,next指向下一个节点

2.末尾的next指向哨兵位的头

3.哨兵位的头的prev指向末尾(不用像单向链表那样循环找尾节点)

3.代码示例

List.h

#pragma once
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
typedef int LTDataType;typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;void LTInit();
void LTDestory();
void LTPushBack(LTNode* phead,LTDataType x);
void LTPopBack(LTNode* phead);

用结构体定义节点,节点有三部分构成:next指针,prev指针和数据,符合双向节点的定义

 

注:prev为previous的缩写

1.双向链表的尾插

示意图

非空链表

空链表

和之前的无头的单向链表有所不同,这里的带哨兵位的头节点

未尾插之前,head->prev指向head->next,head->next指向head->prev(这样可以实现双向循环)

千万不要被箭头的指向所误导!!!!

不是head->prev=head->next;head->next=head->prev;

箭头指向的是head节点
head->prev=head;head->next=head;

尾插之后

实现过程和非空链表一样

*无论对于空链表还是非空链表,尾插都只需要4步,即修改四个指针*

tail指向尾节点

代码

main.c
#include "List.h"
void TestList()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);
}int main()
{TestList();return 0;
}
List.h
#include <assert.h>
typedef int LTDataType;typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;LTNode* LTInit();
LTNode* BuyListNode(LTDataType x);
void LTPushBack(LTNode* phead, LTDataType x);
List.c
#include "List.h"
LTNode* LTInit()
{LTNode* phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;
}LTNode* BuyListNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc");return NULL;}node->next = NULL;node->prev = NULL;node->data = x;return node;
}void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}

详细分析代码的执行过程

进入main函数-->调用TestList函数-->调用LTInit函数-->调用BuyListNode函数

在BuyListNode函数中,先为新的节点开辟空间,之后node指向新节点,如果node为NULL,则开辟失败返回NULL,如果开辟成功继续向下执行①prev和next置NULL ②写入节点的data值

返回node指针,BuyListNode函数结束

双向链表的初始化

在LTInit函数中,phead得到node的值

已知phead存储的值为00 c0 a0 98,求phead->next = phead;和phead->prev = phead;执行完后按小端序计算0x00c0a098~0x00c0a09f处的数据

解:

按照结构体成员变量定义的先后顺序

phead->prev存储在0x00C0A098~0x00C0A09B处,phead->next存储在0x00C0A09C~0x00C0A09F处

因此答案为98 a0 c0 00 98 a0 c0 00

返回phead后,LTInit函数结束

在TestList函数中,plist得到phead的值

调用LTPushBack函数

在LTPushBack函数中,phead得到plist的值(这里没有传二级指针,修改结构体成员变量的值只需要一级指针),断言phead,确保phead不为NULL

调用BuyListNode,返回新节点的地址给newnode

只有带哨兵位的头结点时,LTNode* tail = phead->prev;等价为LTNode* tail = phead;

LTPushBack函数结束

剩下的分析思想一样,略去

2.双向链表的打印

让cur指针指向head节点的下一个节点,循环打印,当cur直到head时,停止打印

代码

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

3.双向链表的尾删

尾删要单独判断是否只有带哨兵位的头节点

写一个LTEmpty函数

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

直接将phead->next == phead结果的真假返回,比if判断要简洁

void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//注意感叹号LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;//定义指向tail的前一个节点的指针tailPrev->next = phead;phead->prev = tailPrev;free(tail);tail = NULL;
}

 

相关文章:

94.【C语言】数据结构之双向链表的初始化,尾插,打印和尾删

目录 1.双向链表 2.结构体的定义 3.示意图 3.代码示例 1.双向链表的尾插 示意图 代码 main.c List.h List.c 详细分析代码的执行过程 双向链表的初始化 2.双向链表的打印 代码 3.双向链表的尾删 1.双向链表 以一种典型的双向链表为例:带头双向循环链表(带头:带…...

learn-F12 Performance(性能)前端性能分析(LCP,CLS,INP)

1.前言 在浏览器开发者工具&#xff08;F12&#xff09;中&#xff0c;本地指标&#xff08;Local Metrics&#xff09;包括LCP&#xff08; Largest Contentful Paint&#xff09;、CLS&#xff08; Cumulative Layout Shift&#xff09;和INP&#xff08; Interaction to Nex…...

XCZU47DR-2FSVE1156

XCZU47DR-2FSVE1156 芯片概述 XCZU47DR-2FSVE1156 是一款由 Xilinx 公司生产的 Zynq UltraScale™ RFSoC 芯片。该芯片集成了多种高性能组件&#xff0c;包括四核 ARM Cortex-A53 MPCore™ 和双核 ARM Cortex™-R5&#xff0c;提供了强大的计算能力和灵活性。它还具备丰富的连…...

物联网低功耗广域网LoRa开发(一):LoRa物联网行业解决方案

一、LoRa的优势以及与其他无线通信技术对比 &#xff08;一&#xff09;LoRa的优势 1、164dB链路预算 、距离>15km 2、快速、灵活的基础设施易组网且投资成本较少 3、LoRa节点模块仅用于通讯电池寿命长达10年 4、免牌照的频段 网关/路由器建设和运营 、节点/终端成本低…...

【LeetCode】【算法】23. 合并K个升序链表

LeetCode 23. 合并K个升序链表 题目描述 给你一个链表数组&#xff0c;每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中&#xff0c;返回合并后的链表。 思路 思路&#xff1a;用小根堆解&#xff0c;很强 创建一个小根堆&#xff0c;排序规则为小根堆排序…...

python3的基本数据类型:Dictionary(字典)的创建

一. 简介 本文开始简单学习一下 python3中的一种基本数据类型&#xff1a;Dictionary&#xff08;字典&#xff09;。 字典&#xff08;dictionary&#xff09;是Python中另一个非常有用的内置数据类型。 二. python3的基本数据类型&#xff1a;Dictionary&#xff08;字典&…...

【C++】string模拟实现

各位读者老爷好&#xff0c;俺最近在学习string的一些知识。为了更好的了解string的结构&#xff0c;俺模拟实现了一个丐版string&#xff0c;有兴趣的老爷不妨垂阅&#xff01;&#xff01;&#xff01; 目录 1.string类的定义 2.模拟实现成员函数接口 2.1.constructor&am…...

Springboot 使用EasyExcel导出含图片并设置样式的Excel文件

Springboot 使用EasyExcel导出含图片并设置样式的Excel文件 Excel导出系列目录&#xff1a;★★★★尤其注意&#xff1a;引入依赖创建导出模板类逻辑处理controllerservice 导出效果总结 Excel导出系列目录&#xff1a; 【Springboot 使用EasyExcel导出Excel文件】 【Springb…...

技术分享:《越南语翻译通》App高效学习越南语的智能助手,是怎么实现高精度语音识别翻译功能的呢?

在数字化时代&#xff0c;语言学习和跨文化交流变得日益重要。对于那些计划前往越南工作、旅游或学习的人来说&#xff0c;掌握越南语无疑是一个巨大的优势。然而&#xff0c;对于非越南语母语者来说&#xff0c;语言障碍可能会成为一大难题。幸运的是&#xff0c;《越南语翻译…...

工业互联网实验实训解决方案核心优势

工业互联网实验实训解决方案旨在通过模拟真实的工业环境&#xff0c;提供给学生或从业人员一个实践学习的平台&#xff0c;它结合了理论教学与实际操作&#xff0c;旨在培养具备工业互联网相关技能的专业人才。 工业互联网实验室必备的软件工具包括&#xff1a; 仿…...

Ceph client 写入osd 数据的两种方式librbd 和kernel rbd

在Ceph存储系统中&#xff0c;客户端&#xff08;Ceph client&#xff09;写入OSD&#xff08;Object Storage Daemon&#xff09;数据确实可以通过两种主要方式&#xff1a;librbd和kernel rbd。这两种方式各有特点和适用场景&#xff0c;下面将分别进行详细介绍。 librbd方式…...

相机光学(四十二)——sony的HDR技术

1.概述 索尼的HDR技术包括以下几种,这些技术共同构成了索尼在HDR领域的技术矩阵&#xff0c;旨在提供更宽广的动态范围、更丰富的色彩表现以及更真实的光影效果: Multi-frame HDR&#xff08;多帧异曝光HDR&#xff09;&#xff1a;这是一种通过不同曝光时间图像的多帧合成来实…...

文件上传漏洞--理论

什么是文件上传漏洞&#xff1f; Web应用允许用户上传文件&#xff0c;但是没有对上传的文件进行严格的过滤和检测&#xff0c;导致网站执行了文件中包含的恶意代码。 漏洞的基本利用方式是&#xff1a; 成功上传包含恶意代码的文件&#xff0c;并在服务端成功执行该文件。 …...

快速入门Selenium自动化测试

一、背景与意义 Selenium是常用的Web自动化测试工具&#xff0c;前端开发工程师可以在完成每项开发任务之后&#xff0c;使用Selenuim做一下回归测试&#xff0c;以避免被提BUG太多导致后面做项目总结时太难看。测试工程师学习Selenium时需要掌握很多API接口&#xff0c;例如页…...

C++指针使用指南

指针 适合指针的情况 动态内存管理 C 语言中&#xff0c;malloc、calloc 和 free 等函数用于动态分配和释放内存&#xff0c;这些函数返回的都是指针类型。通过指针&#xff0c;可以动态创建和管理内存区域&#xff0c;尤其在需要动态数组或复杂数据结构&#xff08;如链表、…...

一文学会,利用LLaMA 3.2打造能“识图断字”的个人AI助理

人工智能最直接也是最普及的应用之一肯定是聊天机器人&#xff0c;或者叫个人 AI 助理。尽管聊天机器人以各种形式存在了30年&#xff0c;但在过去两年中&#xff0c;这些个人AI助理才真正成为热门应用。它们已经从前沿技术范畴落地到生活的各个方面、社交场合和商业场景中。 虽…...

idea的mapper.xml文件里写sql语句出现Tag name expected错误提示

原因如下&#xff1a; xml文件的某些特殊字符是自动转义的, xml解析器会忽视CDATA中的内容 解决方法&#xff1a; 使用下面的表达式表示对应符号。 小于(<)&#xff1a;<大于(>)&#xff1a;>和号(&)&#xff1a;&amp;单引号()&#xff1a;&apos;双引…...

EasyExcel 使用多线程按顺序导出数据

通过多线程读取数据&#xff0c;使用EasyExcel按顺序导出数据 导出时如果要保证顺序需要使用单线程&#xff0c;但是查询时可以用多线程&#xff0c;因为多线程查询后返回数据不是按照顺序排列的&#xff0c;所以我的思路是再循环时给每个线程打标识&#xff0c;通过标识来排序…...

数据驱动的投资分析:民锋科技的量化模型探索

在全球金融市场中&#xff0c;数据驱动的投资分析正在变革传统投资方式。民锋科技通过精密的量化模型和智能算法&#xff0c;为投资者提供更加科学的市场预测和投资分析工具&#xff0c;以帮助他们更好地理解市场波动、优化投资组合&#xff0c;实现风险管理。 #### 一、数据驱…...

cesium 设置相机视角 flyTo 参数destination,orientation

效果 // 监听相机的改变 用来设置相机飞行到哪里window.viewer.camera.changed.addEventListener(function () {// 当相机改变时&#xff0c;获取相机的参数let camera window.viewer.camera;// 获取当前摄像机的位置&#xff08;经纬度&#xff09;let cameraPosition wind…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...