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

【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刷题之消失的数字&#xff08;C语言版&#xff09; 一、题目描述二、题目解析 一、题目描述 数组nums包含从0到n的所有整数&#xff0c;但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗&#xff1f; 注意&#xff1a;本题相对书上原题稍作…...

LeetCode654:最大二叉树

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

AI禁区徘徊监测识别摄像机

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

【学习】什么是信创适配性测试?信创适配性测试的重要性有哪些?

随着信息技术的快速发展和广泛应用&#xff0c;信息技术应用创新&#xff08;信创&#xff09;已成为推动我国产业升级和经济发展的重要力量。在信创领域&#xff0c;适配性测试至关重要&#xff0c;它不仅关系到信创产品的质量和性能&#xff0c;还直接影响到用户的使用体验和…...

linux 配置服务开机启动

一、Centos 中配置进程开启启动 1、使用 systemd 服务&#xff1a; &#xff08;1&#xff09;创建一个名为 myapp.service 的服务文件&#xff1a; [Unit] DescriptionMyApp #描述 After #描述服务类别 [Service] Typefork…...

React中State管理的4 个关键解决方案

在 React 应用开发中,状态(state)管理是非常重要的一部分。合理地管理状态可以确保组件的行为正确,提高应用的可维护性和性能。然而,在实际使用 React 的 state 时,开发者常常会遇到一些常见的问题和陷阱。 本文将从解决问题的角度,总结 React 中 state 管理的4个关键技巧: 使…...

Testng测试框架(6)--@Factory动态地创建测试类的实例

工厂允许您动态地创建测试。例如&#xff0c;假设您想创建一个测试方法&#xff0c;该方法将多次访问网站上的某个页面&#xff0c;并且您希望使用不同的值来调用它。 public class TestWebServer {Test(parameters { "number-of-times" })public void accessPage(…...

Kubernetes(K8s)运维实战:案例解析与代码实践

一、引言 随着容器技术的普及&#xff0c;Kubernetes&#xff08;K8s&#xff09;作为容器编排领域的领军者&#xff0c;已成为企业运维不可或缺的工具。K8s以其强大的自动化管理、可扩展性和高可用性等特点&#xff0c;为运维人员提供了便捷、高效的管理手段。本文将结合具体案…...

nginx反向代理配置详解

首先配置端口 server {listen 3080; server_name 172.20.109.27 localhost;}为了解决刷新后显示404的问题&#xff0c;增加配置如下&#xff1a; location / {root html;index index.html index.htm;try_files $uri $uri.html $uri/ mongrel;}location mongrel {# ip…...

【LeetCode】单调栈类题目详解

所有题目均来自于LeetCode&#xff0c;刷题代码使用的Python3版本 单调栈 通常针对一维数组的问题&#xff0c;如果需要寻找一个元素右边或者左边第一个比自己大或者小的元素的位置&#xff0c;就可以使用单调栈&#xff0c;时间复杂度为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一键重置还原

适用型号&#xff1a;GU605MI、GU605MY、GU605MZ、GU605MV、GU605MU 链接&#xff1a;https://pan.baidu.com/s/1YBmZZbTKpIu883jYCS9KfA?pwd9jd4 提取码&#xff1a;9jd4 华硕原厂Windows11系统带有ASUS RECOVERY恢复功能、自带所有驱动、出厂主题壁纸、系统属性联机支持…...

【OpenVINO™】使用 OpenVINO™ C# API 部署 YOLOv9 目标检测和实例分割模型(上篇)

YOLOv9模型是YOLO系列实时目标检测算法中的最新版本&#xff0c;代表着该系列在准确性、速度和效率方面的又一次重大飞跃。它通过引入先进的深度学习技术和创新的架构设计&#xff0c;如通用ELAN&#xff08;GELAN&#xff09;和可编程梯度信息&#xff08;PGI&#xff09;&…...

代码随想录——二分查找(一)

模版 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 }特点 查找条件可以在不与元素的两侧进行比较的情况下确定&#xff08;或使用它周围的特…...

【NLP】多标签分类【下】

文章目录 简介个人博客与相关链接1 实验数据与任务说明2 模型介绍2.1 TransformerTransformer能做什么&#xff1f; 2.2 Hugging FaceHugging Face的Transformers库社区支持和资源预训练模型的应用 2.3 T5模型&#xff08;Text-To-Text Transfer Transformer&#xff09;T5的核…...

HWOD:密码强度等级

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

期货学习笔记-MACD指标学习2

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

5G智慧港口简介(一)

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

订单中台架构:打造高效订单管理系统的关键

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

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

Golang——7、包与接口详解

包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...

【UE5 C++】通过文件对话框获取选择文件的路径

目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 &#xff0c;这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器&#xff0c;右键点击 .uproject 文件&#xff0c;选择 "Generate Visual Studio project files"&#xff0c;重…...

Matlab实现任意伪彩色图像可视化显示

Matlab实现任意伪彩色图像可视化显示 1、灰度原始图像2、RGB彩色原始图像 在科研研究中&#xff0c;如何展示好看的实验结果图像非常重要&#xff01;&#xff01;&#xff01; 1、灰度原始图像 灰度图像每个像素点只有一个数值&#xff0c;代表该点的​​亮度&#xff08;或…...