【C 数据结构】双向链表
文章目录
- 【 1. 基本原理 】
- 【 2. 双向链表的 创建 】
- 实例 - 输出双向链表
- 【 3. 双向链表 添加节点 】
- 【 4. 双向链表 删除节点 】
- 【 5. 双向链表查找节点 】
- 【 7. 双向链表更改节点 】
- 【 8. 实例 - 双向链表的 增删查改 】
【 1. 基本原理 】
- 表中各节点中都只包含一个指针(游标),且都统一指向直接后继节点,通常称这类链表为 单向链表(或单链表)。
- 背景
如果算法中需要大量地找某指定结点的前趋结点,使用单链表无疑是灾难性的,因为单链表更适合 “从前往后” 找,而 “从后往前” 找并不是它的强项。为了能够高效率解决类似的问题,引入双向链表(简称双链表)。 - 从名字上理解 双向链表,即链表是 “双向” 的,(双向指的是各节点之间的逻辑关系是双向的) 每个节点存在前后两个指针,分别指向前驱节点和后继节点,但通常头指针只设置一个,除非实际情况需要。
- 双向链表中各节点包含以下 3 部分信息:
- 前指针域:用于指向当前节点的直接前驱节点;
- 数据域:用于存储数据元素。
- 后指针域:用于指向当前节点的直接后继节点;
- 双链表的节点结构用 C 语言实现为:
typedef struct line
{struct line * prior; //指向直接前趋int data;struct line * next; //指向直接后继
}line;
【 2. 双向链表的 创建 】
- 同单链表相比,双链表仅是各节点多了一个用于指向直接前驱的指针域。因此,我们可以在单链表的基础轻松实现对双链表的创建。
- 需要注意的是,与单链表不同,双链表创建过程中,每创建一个新节点,都要与其前驱节点建立两次联系,分别是:
- 将新节点的 prior 指针指向直接前驱节点;
- 将直接前驱节点的 next 指针指向新节点;
- 创建双向链表的 C 语言实现代码:
line* initLine(line * head)
{head=(line*)malloc(sizeof(line));//创建链表第一个结点(首元结点)head->prior=NULL;head->next=NULL;head->data=1;line * list=head;for (int i=2; i<=3; i++) {//创建并初始化一个新结点line * body=(line*)malloc(sizeof(line));body->prior=NULL;body->next=NULL;body->data=i;list->next=body;//直接前趋结点的next指针指向新结点body->prior=list;//新结点指向直接前趋结点list=list->next;}return head;
}
实例 - 输出双向链表
#include <stdio.h>
#include <stdlib.h>//双向链表结构体
typedef struct line
{struct line* prior;int data;struct line* next;
}line;//双链表的创建函数
line* initLine(line* head)
{//创建一个首元节点,链表的头指针为headhead = (line*)malloc(sizeof(line));//对节点进行初始化head->prior = NULL;head->next = NULL;head->data = 1;//声明一个指向首元节点的指针,方便后期向链表中添加新创建的节点line* list = head;for (int i = 2; i <= 5; i++){//创建新的节点并初始化line* body = (line*)malloc(sizeof(line));body->prior = NULL;body->next = NULL;body->data = i;//新节点与链表最后一个节点建立关系list->next = body;body->prior = list;//list永远指向链表中最后一个节点list = list->next;}//返回新创建的链表return head;
}//输出双链表的函数
void display(line* head)
{line* temp = head;while (temp){//如果该节点无后继节点,说明此节点是链表的最后一个节点if (temp->next == NULL)printf("%d\n", temp->data);elseprintf("%d <-> ", temp->data);temp = temp->next;}
}int main()
{//创建一个头指针line* head = NULL;//调用链表创建函数head = initLine(head);//输出创建好的链表display(head);//显示双链表的优点printf("链表中第 4 个节点的直接前驱是:%d", head->next->next->next->prior->data);return 0;
}
【 3. 双向链表 添加节点 】
- 添加至表头
将新数据元素添加到表头,只需要将该元素与表头元素建立双层逻辑关系即可。换句话说,假设新元素节点为 temp,表头节点为 head,则需要做以下 2 步操作即可:- 新节点与头节点连接:temp->next=head; head->prior=temp;
- head指向新节点:将 head 移至 temp,重新指向新的表头;
例如,将新元素 7 添加至双链表的表头,则实现过程如图 2 所示:
- 添加至表的中间位置
同单链表添加数据类似,双向链表中间位置添加数据需要经过以下 2 个步骤,如下图所示:- 新节点先与其直接后继节点建立双层逻辑关系;
- 新节点的直接前驱节点与之建立双层逻辑关系;
- 添加至表尾
与添加到表头是一个道理,更简单,实现过程如下:- 找到双链表中最后一个节点;
- 让新节点与最后一个节点进行双层逻辑关系;
- C 语言实现
line * insertLine(line * head,int data,int add)
{//新建数据域为data的结点line * temp=(line*)malloc(sizeof(line));temp->data=data;temp->prior=NULL;temp->next=NULL;//插入到链表头,要特殊考虑if (add==1) {temp->next=head;head->prior=temp;head=temp;}else{line * body=head;//找到要插入位置的前一个结点bodyfor (int i=1; i<add-1; i++) {body=body->next;}//判断条件为真,说明插入位置为链表尾if (body->next==NULL) {body->next=temp;temp->prior=body;}else{body->next->prior=temp;//新节点后1个节点的前向指针指向新节点temp->next=body->next;//新节点的后向指针指向后一个节点body->next=temp;//新节点前1个节点的后向指针指向新节点temp->prior=body;//新节点的前向指针指向前一个节点}}return head;
}
【 4. 双向链表 删除节点 】
-双链表删除结点时,只需遍历链表找到要删除的结点,然后将该节点从表中摘除即可。
- 删除元素 2 的操作过程,如下图所示:
- 双向链表删除节点的 C 语言实现代码如下:
//删除结点的函数,data为要删除结点的数据域的值
line * delLine(line * head,int data)
{line * temp=head;//遍历链表while (temp) {//判断当前结点中数据域和data是否相等,若相等,摘除该结点if (temp->data==data) {temp->prior->next=temp->next;temp->next->prior=temp->prior;free(temp);return head;}temp=temp->next;}printf("链表中无该数据元素");return head;
}
【 5. 双向链表查找节点 】
- 通常,双向链表同单链表一样,都仅有一个头指针。因此,双链表查找指定元素 的实现同单链表类似,都是 从表头依次遍历表中元素。
- C 语言实现代码为:
//head为原双链表,elem表示被查找元素
int selectElem(line * head,int elem)
{
//新建一个指针t,初始化为头指针 headline * t=head;int i=1;while (t) {if (t->data==elem) {return i;}i++;t=t->next;}//程序执行至此处,表示查找失败return -1;
}
【 7. 双向链表更改节点 】
- 更改双链表中指定结点数据域的操作是在查找的基础上完成的。实现过程是:通过遍历找到存储有该数据元素的结点,直接更改其数据域即可。
- 实现此操作的 C 语言实现代码如下:
//更新函数,其中,add 表示更改结点在双链表中的位置,newElem 为新数据的值
line *amendElem(line * p,int add,int newElem)
{line * temp=p;//遍历到被删除结点for (int i=1; i<add; i++) {temp=temp->next;}temp->data=newElem;return p;
}
【 8. 实例 - 双向链表的 增删查改 】
#include <stdio.h>
#include <stdlib.h>
//双向链表结构体
typedef struct line
{struct line* prior;int data;struct line* next;
}line;
//双链表的创建
line* initLine(line* head);
//双链表插入元素,add表示插入位置
line* insertLine(line* head, int data, int add);
//双链表删除指定元素
line* delLine(line* head, int data);
//双链表中查找指定元素
int selectElem(line* head, int elem);
//双链表中更改指定位置节点中存储的数据,add表示更改位置
line* amendElem(line* p, int add, int newElem);
//输出双链表的实现函数
void display(line* head);int main()
{line* head = NULL;//创建双链表head = initLine(head);display(head);//在表中第 3 的位置插入元素 7head = insertLine(head, 7, 3);display(head);//表中删除元素 2head = delLine(head, 2);display(head);printf("元素 3 的位置是:%d\n", selectElem(head, 3));//表中第 3 个节点中的数据改为存储 6head = amendElem(head, 3, 6);display(head);return 0;
}line* initLine(line* head)
{head = (line*)malloc(sizeof(line));head->prior = NULL;head->next = NULL;head->data = 1;line* list = head;for (int i = 2; i <= 5; i++) {line* body = (line*)malloc(sizeof(line));body->prior = NULL;body->next = NULL;body->data = i;list->next = body;body->prior = list;list = list->next;}return head;
}
line* insertLine(line* head, int data, int add)
{//新建数据域为data的结点line* temp = (line*)malloc(sizeof(line));temp->data = data;temp->prior = NULL;temp->next = NULL;//插入到链表头,要特殊考虑if (add == 1) {temp->next = head;head->prior = temp;head = temp;}else {line* body = head;//找到要插入位置的前一个结点for (int i = 1; i < add - 1; i++) {body = body->next;}//判断条件为真,说明插入位置为链表尾if (body->next == NULL) {body->next = temp;temp->prior = body;}else {body->next->prior = temp;temp->next = body->next;body->next = temp;temp->prior = body;}}return head;
}
line* delLine(line* head, int data)
{line* temp = head;//遍历链表while (temp) {//判断当前结点中数据域和data是否相等,若相等,摘除该结点if (temp->data == data) {temp->prior->next = temp->next;temp->next->prior = temp->prior;free(temp);return head;}temp = temp->next;}printf("链表中无该数据元素");return head;
}
//head为原双链表,elem表示被查找元素
int selectElem(line* head, int elem)
{//新建一个指针t,初始化为头指针 headline* t = head;int i = 1;while (t) {if (t->data == elem) {return i;}i++;t = t->next;}//程序执行至此处,表示查找失败return -1;
}
//更新函数,其中,add 表示更改结点在双链表中的位置,newElem 为新数据的值
line* amendElem(line* p, int add, int newElem)
{line* temp = p;//遍历到被删除结点for (int i = 1; i < add; i++) {temp = temp->next;}temp->data = newElem;return p;
}
//输出链表的功能函数
void display(line* head)
{line* temp = head;while (temp) {if (temp->next == NULL) {printf("%d\n", temp->data);}else {printf("%d->", temp->data);}temp = temp->next;}
}
相关文章:

【C 数据结构】双向链表
文章目录 【 1. 基本原理 】【 2. 双向链表的 创建 】实例 - 输出双向链表 【 3. 双向链表 添加节点 】【 4. 双向链表 删除节点 】【 5. 双向链表查找节点 】【 7. 双向链表更改节点 】【 8. 实例 - 双向链表的 增删查改 】 【 1. 基本原理 】 表中各节点中都只包含一个指针&…...

Leetcode刷题之消失的数字(C语言版)
Leetcode刷题之消失的数字(C语言版) 一、题目描述二、题目解析 一、题目描述 数组nums包含从0到n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗? 注意:本题相对书上原题稍作…...

LeetCode654:最大二叉树
题目描述 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建: 创建一个根节点,其值为 nums 中的最大值。 递归地在最大值 左边 的 子数组前缀上 构建左子树。 递归地在最大值 右边 的 子数组后缀上 构建右子树。 返回 nums 构建的 …...

AI禁区徘徊监测识别摄像机
AI禁区徘徊监测识别摄像机是一种基于人工智能技术的智能监控设备,用于监测禁止进入或逗留的区域。这种摄像机通过高清摄像头实时捕捉场景图像,利用AI算法对人员徘徊行为进行识别和监测,有助于提高安全防范水平,减少潜在的安全风险…...

【学习】什么是信创适配性测试?信创适配性测试的重要性有哪些?
随着信息技术的快速发展和广泛应用,信息技术应用创新(信创)已成为推动我国产业升级和经济发展的重要力量。在信创领域,适配性测试至关重要,它不仅关系到信创产品的质量和性能,还直接影响到用户的使用体验和…...
linux 配置服务开机启动
一、Centos 中配置进程开启启动 1、使用 systemd 服务: (1)创建一个名为 myapp.service 的服务文件: [Unit] DescriptionMyApp #描述 After #描述服务类别 [Service] Typefork…...
React中State管理的4 个关键解决方案
在 React 应用开发中,状态(state)管理是非常重要的一部分。合理地管理状态可以确保组件的行为正确,提高应用的可维护性和性能。然而,在实际使用 React 的 state 时,开发者常常会遇到一些常见的问题和陷阱。 本文将从解决问题的角度,总结 React 中 state 管理的4个关键技巧: 使…...

Testng测试框架(6)--@Factory动态地创建测试类的实例
工厂允许您动态地创建测试。例如,假设您想创建一个测试方法,该方法将多次访问网站上的某个页面,并且您希望使用不同的值来调用它。 public class TestWebServer {Test(parameters { "number-of-times" })public void accessPage(…...
Kubernetes(K8s)运维实战:案例解析与代码实践
一、引言 随着容器技术的普及,Kubernetes(K8s)作为容器编排领域的领军者,已成为企业运维不可或缺的工具。K8s以其强大的自动化管理、可扩展性和高可用性等特点,为运维人员提供了便捷、高效的管理手段。本文将结合具体案…...
nginx反向代理配置详解
首先配置端口 server {listen 3080; server_name 172.20.109.27 localhost;}为了解决刷新后显示404的问题,增加配置如下: location / {root html;index index.html index.htm;try_files $uri $uri.html $uri/ mongrel;}location mongrel {# ip…...

【LeetCode】单调栈类题目详解
所有题目均来自于LeetCode,刷题代码使用的Python3版本 单调栈 通常针对一维数组的问题,如果需要寻找一个元素右边或者左边第一个比自己大或者小的元素的位置,就可以使用单调栈,时间复杂度为O(n) 单调栈的本质是空间换时间&#…...

Python上解决TypeError: not all arguments converted during string formatting错误
目录 背景尝试1: pymysql模块的escape_string方法尝试2: 修改pandas.read_excel引擎尝试3: 回退xlrd版本总结 背景 在Linux上部署的时候, 使用pandas模块读取Excel, 然后pymysql模块入库, 结果发生了错误 Traceback (most recent call last):File "/usr/local/lib64/pyth…...

ASUS华硕ROG幻16Air笔记本电脑GU605M原装出厂Win11系统工厂包下载,带有ASUSRecovery一键重置还原
适用型号:GU605MI、GU605MY、GU605MZ、GU605MV、GU605MU 链接:https://pan.baidu.com/s/1YBmZZbTKpIu883jYCS9KfA?pwd9jd4 提取码:9jd4 华硕原厂Windows11系统带有ASUS RECOVERY恢复功能、自带所有驱动、出厂主题壁纸、系统属性联机支持…...

【OpenVINO™】使用 OpenVINO™ C# API 部署 YOLOv9 目标检测和实例分割模型(上篇)
YOLOv9模型是YOLO系列实时目标检测算法中的最新版本,代表着该系列在准确性、速度和效率方面的又一次重大飞跃。它通过引入先进的深度学习技术和创新的架构设计,如通用ELAN(GELAN)和可编程梯度信息(PGI)&…...

代码随想录——二分查找(一)
模版 func BinarySearch(nums *int,target int){l,r:0,len(nums)-1for l<r{mid:l(r-l)/2if nums[mid]target{return mid}else if nums[mid]<target{lmid1}else{rmid-1}}return -1 }特点 查找条件可以在不与元素的两侧进行比较的情况下确定(或使用它周围的特…...

【NLP】多标签分类【下】
文章目录 简介个人博客与相关链接1 实验数据与任务说明2 模型介绍2.1 TransformerTransformer能做什么? 2.2 Hugging FaceHugging Face的Transformers库社区支持和资源预训练模型的应用 2.3 T5模型(Text-To-Text Transfer Transformer)T5的核…...

HWOD:密码强度等级
一、知识点 回车键的ASCII码是10 如果使用EOF,有些用例不通过 二、题目 1、描述 密码按如下规则进行计分,并根据不同的得分为密码进行安全等级划分。 一、密码长度: 5 分: 小于等于4 个字符 10 分: 5 到7 字符 25 分: 大于等于8 个字符 二、字母: 0…...

期货学习笔记-MACD指标学习2
MACD底背离把握买入多单的技巧 底背离的概念及特征 底背离指的是MACD指标与价格低点之间的对比关系,这里需要明白的是MACD指标的涨跌动能和价格形态衰竭形态之间的关系,如果市场价格创新低而出现衰竭形态同时也有底背离形态的出现,此时下跌…...

5G智慧港口简介(一)
引言 港口作为交通运输的枢纽,在促进国际贸易和地区发展中起着举足轻重的作用,全球贸易中约 90% 的贸易由海运业承载,作业效率对于港口至关重要。在“工业 4.0”、“互联网 +”大发展的时代背景下,港口也在进行数字化、全自动的转型升级。随着全球 5G 技术浪潮的到来,华为…...

订单中台架构:打造高效订单管理系统的关键
在现代商业环境下,订单管理对于企业来说是至关重要的一环。然而,随着业务规模的扩大和多渠道销售的普及,传统的订单管理方式往往面临着诸多挑战,如订单流程复杂、信息孤岛、数据不一致等问题。为了应对这些挑战并抓住订单管理的机…...

业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...
Java入门学习详细版(一)
大家好,Java 学习是一个系统学习的过程,核心原则就是“理论 实践 坚持”,并且需循序渐进,不可过于着急,本篇文章推出的这份详细入门学习资料将带大家从零基础开始,逐步掌握 Java 的核心概念和编程技能。 …...

Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)
一、OpenBCI_GUI 项目概述 (一)项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台,其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言,首次接触 OpenBCI 设备时,往…...
深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向
在人工智能技术呈指数级发展的当下,大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性,吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型,成为释放其巨大潜力的关键所在&…...

算法打卡第18天
从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。 示例 1: 输入:inorder [9,3,15,20,7…...

篇章二 论坛系统——系统设计
目录 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 1. 数据库设计 1.1 数据库名: forum db 1.2 表的设计 1.3 编写SQL 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 通过需求分析获得概念类并结合业务实现过程中的技术需要&#x…...