004——双向链表和循环链表

目录

双向链表

双向链表的初始化(与单链表类似)

增:

Ⅰ)头插法

Ⅱ)尾插法

Ⅲ)中间插入

整体代码示例:

 循环链表

循环单链表

​编辑 循环双链表


双向链表

不同于单链表,双向链表不仅可以往后指向,还可以往前指向,则双向链表是在单链表的基础上,每个结点增加一个指针域,这个指针域保存上一个结点的地址

pre指针域

(保存前一个结点的地址)

  数据域

    data

next指针域

(保存后一个结点的地址)

//双向链表的结构体
typedef struct Node {struct Node* pre;int data;struct Node* next;
}Node,*LinkList;

 由003——单链表可知,单链表分为带头结点的不带头结点的,双向链表也是同理(上图的是带头结点的)

双向链表的初始化
(与单链表类似)

LinkList InitLinkList() {Node* p = (Node*)malloc(sizeof(Node));//申请头结点if (p == NULL) {printf("空间分配失败\n");}else {//p->data	脏数据,不用管p->pre=p->next = NULL;//注意:该语句的执行方向是从右往左/*p->pre = NULL;p->next = NULL;*/}return p;
}
int main() {LinkList L = InitLinkList();
}

增:

双向链表中增加一个结点(数据)

Ⅰ)头插法

固定在头结点和首元结点之间插入一个结点(头结点之后)如下图的例子

为了方便分析,我们为示意图进行编号 

注意,在这里对数据进行处理时,我们不能使得这个线(单向的,无论是正向还是负向)断掉,比如像下面这种情况,就是错误

正确的顺序应该是先处理③和④,然后再处理①和②(顺序并不唯一)

 (下面代码并不完整)

//头插法:
LinkList HeadInsert(LinkList L, int k) {//先申请一个新的结点用来保存数据kNode* s = (Node*)malloc(sizeof(Node));if (s == NULL) {printf("空间分配失败/n");}else {s->data = k;//将数据传给新申请的结点ss->pre = L;//3s->next = L->next;//4L->next= s;//1s->next->pre = s;//2}return L;
}

或者可以写成3421(还有其他写法)

        s->pre = L;
        s->next = L->next;
        L->next->pre = s;
        L->next = s;

此时还要考虑L为空的情况,因为这个时候的②是不存在的

所以在我们更改②这条线之前,需要进行一个判断

//头插法:
LinkList HeadInsert(LinkList L, int k) {//先申请一个新的结点用来保存数据kNode* s = (Node*)malloc(sizeof(Node));if (s == NULL) {printf("空间分配失败/n");}else {s->data = k;//将数据传给新申请的结点ss->pre = L;//3s->next=L->next;//4L->next = s;//1if (s->next != NULL) {s->next->pre = s;//2}}return L;
}

Ⅱ)尾插法

从头结点开始遍历找到尾结点,在尾结点的后面插入新的结点(需要多维护一个pre)

//尾插法
LinkList RearInsert(LinkList L, int k) {Node* p = L;	//指针指p向头结点while (p->next != NULL) {p = p->next;}//循环结束后指针p指向最后一个结点//先申请一个新的结点用来保存数据kNode* s = (Node*)malloc(sizeof(Node));if (s == NULL) {printf("空间分配失败\n");return L;}else {s->data = k;//将数据传给新申请的结点ss->next = p->next;s->pre = p;p->next = s;}return L;
}

Ⅲ)中间插入


//中间插入
//首先需要一个查找函数,并且返回该结点的地址
Node* find(LinkList L, int k) {Node* p = L->next;while (p != NULL && p->data != k) {//出现NULL->data!=k会报错,所以这两项的顺序不可以颠倒p = p->next;}return p;//要么为空,要么保存所要数据
}
//中间插入的函数
Node* MidInsert(LinkList L, int x, int k) {//在元素x后面插入数据kNode* p = find(L, x);if (p == NULL) {printf("数据%d不存在,无法找到插入位置,插入失败\n", x);return L;}Node* s = (Node*)malloc(sizeof(Node));if (s == NULL) {printf("空间分配失败,插入失败\n");return L;}else {s->data = k;s->next = p->next;p->next = s;if (s->next != NULL) {s->next->pre = s;}}return L;
}

删除如下面图示

修改后的结果

 

//删除
LinkList Delete(LinkList L, int k) {if (L->next == NULL) {printf("空链表,删除失败\n");return L;}//找到k所在的结点pNode* p = find(L, k);if (p == NULL) {printf("数据%d不存在,删除失败\n");return L;}//删除p->pre->next = p->next;if (p->next != NULL) {p->next->pre = p->pre;}//防止p成为空指针free(p);p = NULL;return L;}

修改代码与单链表是相同的

//修改
LinkList Replace(LinkList L, int x, int k) {Node* p = find(L, x);if (p == NULL) {printf("数据%d不存在,无法找到修改位置,修改失败\n", x);return L;}else {p->data = k;}return L;
}

查找代码与单链表是相同的

Node* find(LinkList L, int k) {Node* p = L->next;while (p != NULL && p->data != k) {//出现NULL->data!=k会报错,所以这两项的顺序不可以颠倒p = p->next;}return p;//要么为空,要么保存所要数据
}

整体代码示例:

#include<stdio.h>
#include<stdlib.h>
//双向链表的结构体
typedef struct Node {struct Node* pre;int data;struct Node* next;
}Node,*LinkList;LinkList InitLinkList() {Node* p = (Node*)malloc(sizeof(Node));//申请头结点if (p == NULL) {printf("空间分配失败\n");}else {//p->data	脏数据,不用管p->pre=p->next = NULL;//注意:该语句的执行方向是从右往左/*p->pre = NULL;p->next = NULL;*/}return p;
}//头插法:
LinkList HeadInsert(LinkList L, int k) {//先申请一个新的结点用来保存数据kNode* s = (Node*)malloc(sizeof(Node));if (s == NULL) {printf("空间分配失败/n");}else {s->data = k;//将数据传给新申请的结点ss->pre = L;//3s->next=L->next;//4L->next = s;//1if (s->next != NULL) {s->next->pre = s;//2}}return L;
}//尾插法
LinkList RearInsert(LinkList L, int k) {Node* p = L;	//指针指p向头结点while (p->next != NULL) {p = p->next;}//循环结束后指针p指向最后一个结点//先申请一个新的结点用来保存数据kNode* s = (Node*)malloc(sizeof(Node));if (s == NULL) {printf("空间分配失败\n");return L;}else {s->data = k;//将数据传给新申请的结点ss->pre = p;//3s->next = p->next;//4p->next = s;//1if (s->next != NULL) {s->next->pre = s;//2}}return L;
}//中间插入
//首先需要一个查找函数,并且返回该结点的地址
Node* find(LinkList L, int k) {Node* p = L->next;while (p != NULL && p->data != k) {//出现NULL->data!=k会报错,所以这两项的顺序不可以颠倒p = p->next;}return p;//要么为空,要么保存所要数据
}
//中间插入的函数
Node* MidInsert(LinkList L, int x, int k) {//在元素x后面插入数据kNode* p = find(L, x);if (p == NULL) {printf("数据%d不存在,无法找到插入位置,插入失败\n", x);return L;}Node* s = (Node*)malloc(sizeof(Node));if (s == NULL) {printf("空间分配失败,插入失败\n");return L;}else {s->data = k;s->next = p->next;p->next = s;if (s->next != NULL) {s->next->pre = s;}}return L;
}//修改
LinkList Replace(LinkList L, int x, int k) {Node* p = find(L, x);if (p == NULL) {printf("数据%d不存在,无法找到修改位置,修改失败\n", x);return L;}else {p->data = k;}return L;
}//删除
LinkList Delete(LinkList L, int k) {if (L->next == NULL) {printf("空链表,删除失败\n");return L;}//找到k所在的结点pNode* p = find(L, k);if (p == NULL) {printf("数据%d不存在,删除失败\n");return L;}//删除p->pre->next = p->next;if (p->next != NULL) {p->next->pre = p->pre;}//防止p成为空指针free(p);p = NULL;return L;}void show(LinkList L) {Node* p = L->next;while (p != NULL){printf("%d\t", p->data);p = p->next;}
}int main() {LinkList L = InitLinkList();L = HeadInsert(L, 10);L = HeadInsert(L, 22);L = HeadInsert(L, 16);L = HeadInsert(L, 45);L = RearInsert(L, 77);L = MidInsert(L, 77,99);L = Delete(L, 10);show(L);return 0;}

运行结果

 循环链表

循环单链表

循环链表只需要让最后一个结点的指针域指向头结点

 那么循环链表和单链表几乎没有太大差异,只是在为空的一些位置改成头结点

#include<stdio.h>
#include<stdlib.h>
typedef struct Node {int data;		//该节点的数据struct Node* next;		
}Node,*LinkList;//初始化一个带头结点的空的循环链表
LinkList InitLinkList() {Node* s = (Node*)malloc(sizeof(Node));//申请头结点if (s == NULL) {printf("空间分配失败\n");}else {//s->data	脏数据,不用管s->next = s;//改变。。。。。。。。。。。。}return s;
}//头插法:
LinkList HeadInsert(LinkList L, int k) {//先申请一个新的结点用来保存数据kNode* s = (Node*)malloc(sizeof(Node));if (s == NULL) {printf("空间分配失败/n");}else {s->data = k;//将数据传给新申请的结点ss->next = L->next;L->next = s;}return L;
}//尾插法
LinkList RearInsert(LinkList L, int k) {Node* p = L;	//指针指p向头结点while (p->next != L) {//改变。。。。。。。。。。。。p = p->next;}//循环结束后指针p指向最后一个结点//先申请一个新的结点用来保存数据kNode* s = (Node*)malloc(sizeof(Node));if (s == NULL) {printf("空间分配失败\n");return L;}else {s->data = k;//将数据传给新申请的结点ss->next = p->next;//改变。。。。。。。。。。。。p->next = s;}return L;
}//中间插入
//首先需要一个查找函数,并且返回该结点的地址
Node* find(LinkList L, int k) {Node* p = L->next;while (p!=L && p->data != k) {//改变。。。。。。。。。。。。
//出现NULL->data!=k会报错,所以这两项的顺序不可以颠倒p = p->next;}return p;//要么为空,要么保存所要数据
}
//中间插入的函数
Node* MidInsert(LinkList L, int x, int k) {//在元素x后面插入数据kNode* p = find(L, x);if (p == L) {//改变。。。。。。。。。。。。printf("数据%d不存在,无法找到插入位置,插入失败\n",x);return L;}Node* s = (Node*)malloc(sizeof(Node));if (s == NULL) {printf("空间分配失败,插入失败\n");return L;}else {s->data = k;s->next = p->next;p->next = s;}return L;
}//修改
LinkList Replace(LinkList L, int x, int k) {Node* p = find(L, x);if (p == L) {//改变。。。。。。。。。。。。printf("数据%d不存在,无法找到修改位置,修改失败\n", x);return L;}else {p->data = k;}return L;
}//删除
LinkList Delete(LinkList L, int k) {if (L->next == L) {//改变。。。。。。。。。。。。printf("数据%d不存在,删除失败\n", k);return L;}//找到k所在的结点p和上一个结点Node* pre = L;Node* p = L->next;while (p!=L&&p->data!=k)//改变。。。。。。。。。。。。{pre = p;p = p->next;}if (p == L) {//改变。。。。。。。。。。。。printf("数据%d不存在,删除失败\n", k);return L;}pre->next = p->next;free(p);p = NULL;//防止p成为野指针return L;
}void show(LinkList L) {Node* p = L->next;while (p!= L)//改变。。。。。。。。。。。。{printf("%d\t", p->data);p = p->next;}
}
int main() {LinkList L = NULL;L = InitLinkList();L=HeadInsert(L,10);L = HeadInsert(L, 8);L = RearInsert(L, 15);L = MidInsert(L, 5, 55);L=Replace(L, 8, 88);L = Delete(L, 8);show(L);return 0;
}

运行结果:

 循环双链表

循环双链表与之同理


#include<stdio.h>
#include<stdlib.h>
//双向链表的结构体
typedef struct Node {struct Node* pre;int data;struct Node* next;
}Node, * LinkList;LinkList InitLinkList() {Node* p = (Node*)malloc(sizeof(Node));//申请头结点if (p == NULL) {printf("空间分配失败\n");}else {//p->data	脏数据,不用管//	p->next=p->pre=p;p->next = p;p->pre = p;}return p;
}//头插法:
LinkList HeadInsert(LinkList L, int k) {//先申请一个新的结点用来保存数据kNode* s = (Node*)malloc(sizeof(Node));if (s == NULL) {printf("空间分配失败/n");}else {s->data = k;//将数据传给新申请的结点ss->pre = L;//3s->next = L->next;//4L->next = s;//1s->next->pre = s;//2}return L;
}//尾插法
LinkList RearInsert(LinkList L, int k) {Node* s = (Node*)malloc(sizeof(Node));if (s == NULL){printf("空间分配失败\n");return L;}s->data = k;//找尾节点Node* p = L;while (p->next != L){p = p->next;}s->next = p->next;s->pre = p;p->next = s;s->next->pre = s;return L;
}//中间插入
//首先需要一个查找函数,并且返回该结点的地址
Node* find(LinkList L, int k) {//查找数据k所在的节点,并且返回该节点的地址 Node* p = L->next;while (p != L && p->data != k){p = p->next;}return p;
}
//中间插入的函数
Node* MidInsert(LinkList L, int x, int k) {//数据x后插入数据k Node* s = (Node*)malloc(sizeof(Node));if (s == NULL){printf("空间分配失败\n");return L;}s->data = k;//找x所在节点 Node* p = find(L, x);if (p == L){printf("数据%d不存在,插入失败\n", x);return L;}s->pre = p;//3s->next = p->next;//4p->next = s;//1s->next->pre = s;//2return L;}//修改
LinkList Replace(LinkList L, int x, int k) {Node* p = find(L, x);if (p == L) {printf("数据%d不存在,无法找到修改位置,修改失败\n", x);return L;}else {p->data = k;}return L;
}//删除
LinkList Delete(LinkList L, int k) {if (L->next == L){printf("空链表,删除失败\n");return L;}//找k所在的节点pNode* p = find(L, k);if (p == L){printf("数据%d不存在,删除失败\n", k);return L;}//删除:p->pre->next = p->next;p->next->pre = p->pre;free(p);p = NULL;return L;
}void show(LinkList L) {Node* p = L->next;while (p != L){printf("%d\t", p->data);p = p->next;}
}int main() {LinkList L = InitLinkList();L = HeadInsert(L, 10);L = HeadInsert(L, 22);L = HeadInsert(L, 16);L = HeadInsert(L, 45);L = RearInsert(L, 77);L = MidInsert(L, 77, 99);L = Delete(L, 10);show(L);return 0;}

 运行结果:

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/421074.html

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

相关文章

2024年录屏神器大盘点,轻松捕捉屏幕精彩

现在讲解一些操作越来越便捷了&#xff0c;我 一般都是用录屏工具来边录制操作边讲解&#xff0c;这样可以更方便对方了解操作步骤。这次我就分享几款免费录屏工具一起来试试吧。 1.福晰录屏软件 链接&#xff1a;www.foxitsoftware.cn/REC/ 对于初次尝试录屏的新手来说&…

每天五分钟玩转深度学习框架PyTorch:获取神经网络模型的参数

本文重点 当我们定义好神经网络之后,这个网络是由多个网络层构成的,每层都有参数,我们如何才能获取到这些参数呢?我们将再下面介绍几个方法来获取神经网络的模型参数,此文我们是为了学习第6步(优化器)。 获取所有参数Parameters from torch import nn net=nn.Sequent…

Java | Leetcode Java题解之第397题整数替换

题目&#xff1a; 题解&#xff1a; class Solution {public int integerReplacement(int n) {int ans 0;while (n ! 1) {if (n % 2 0) {ans;n / 2;} else if (n % 4 1) {ans 2;n / 2;} else {if (n 3) {ans 2;n 1;} else {ans 2;n n / 2 1;}}}return ans;} }

UE5引擎工具链知识点

当我们提到“引擎工具链的开发”时&#xff0c;通常指的是为游戏开发或其他类型的软件开发创建一系列工具和技术栈的过程。这包括但不限于游戏引擎本身&#xff08;如Unity或Unreal Engine&#xff09;&#xff0c;以及围绕这些引擎构建的各种工具和服务&#xff0c;比如用于构…

CTFHub技能树-Git泄漏-Index

目录 一、Git索引&#xff08;Index&#xff09;的基本概念 二、解题过程 主旨&#xff1a;使用git泄漏恢复源代码 方法一&#xff1a;使用GitHack手动恢复 方法二&#xff1a;直接使用Git_Extract获取网站源代码拿去flag 当前大量开发人员使用git进行版本控制&#xff0c…

新书宣传:《量子安全:信息保护新纪元》

《量子安全&#xff1a;信息保护新纪元》 前言本书的看点本书的目录结语 前言 你好&#xff01; 这是我第一次发布类广告的博文&#xff0c;目的也很单纯&#xff0c;希望以作者的身份介绍一下自己出版的图书——《量子安全&#xff1a;信息保护新纪元》。此书于2024年7月出版…

【鸿蒙】HarmonyOS NEXT星河入门到实战1-开发环境准备

目录 一、达成目标 二、鸿蒙开发环境准备 2.1 开发者工作下载 2.2 解压安装 2.3 运行配置安装node.js和SDK 2.4 开始创建第一个项目 2.5 预览 2.5.1 预览遇到的问题&#xff08;报错&#xff09; 2.5.2 修改内容查看预览 三、备用下载地址&#xff08;如果下载是4.X版…

会声会影2024发布了没有? 会声会影2024更新哪些内容?

嘿&#xff0c;亲爱的的朋友们&#xff0c;今天我要跟大家安利一款让我彻底沉迷、不能自拔的神器 —— 会声会影2024&#xff01;如果你还在为视频编辑头疼&#xff0c;那么准备好迎接你的救星吧&#xff01; 会声会影2024是一款功能全面的视频编辑软件&#xff0c;它不仅能帮你…

基于Logistic-Map混沌序列的数字信息加解密算法matlab仿真,支持对文字,灰度图,彩色图,语音进行加解密

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 5.完整程序 1.程序功能描述 基于Logistic-Map混沌序列的数字信息加解密算法matlab仿真,系统包含GUI操作界面&#xff0c;系统支持对文字,灰度图,彩色图,语音进行加解密。 2.测试软件版本以及…

人工智能在C/C++中的应用

随着技术的飞速发展&#xff0c;人工智能&#xff08;AI&#xff09;已经成为我们日常生活中不可或缺的一部分。从智能手机的语音助手到自动驾驶汽车&#xff0c;AI的应用无处不在。在众多编程语言中&#xff0c;C和C因其高性能和灵活性&#xff0c;成为实现复杂AI算法的理想选…

分类预测|基于雪消融优化BP神经网络的数据分类预测Matlab程序SAO-BP 多特征输入多类别输出 含基础程序

分类预测|基于雪消融优化BP神经网络的数据分类预测Matlab程序SAO-BP 多特征输入多类别输出 含基础程序 文章目录 一、基本原理二、实验结果三、核心代码四、代码获取五、总结 一、基本原理 SAO-BP模型结合了雪消融优化算法&#xff08;SAO&#xff09;和BP神经网络。以下是详细…

Linux中使用node xxx.js启动进程后终端关闭进程会自动关闭的解决方案

原标题&#xff1a;在Linux中想要运行一个node程序&#xff0c;但随着终端关闭&#xff0c;其node进程会自动关闭的解决方案&#xff1a; 使用nohup 运行命令&#xff0c;其中的app.js是你要运行的js output.log是运行日志 nohup node app.js > output.log 2>&1 &…

一. rpc基本学习

1. 什么是rpc&#xff0c;为什么有了http还要rpc 我们常说的http&#xff0c;应该是说的http1&#xff0c;http只是应用层的一个协议 Rpc是一种调用方式&#xff0c;全称叫远程过程调用&#xff0c;对应本地调用&#xff0c;rpc是一种调用方式&#xff0c;不是一种协议 更具体…

Marin说PCB之在CST软件中如何搭建两端子电容器--02

上回书到说到李相赫同学在导入一颗新的两端子电容器物料的时候&#xff0c;发现其阻抗频率特性曲线太反常了&#xff1a; 和之前的Murata家的GRT033D70E105ME18这个物料放在一起比对一下&#xff1a; 上编文章中有一句话我不知道诸位道友们是否还有印象啊&#xff1f; Murata家…

断点回归模型

断点回归&#xff08;Regression Discontinuity Design, RDD&#xff09;是一种准实验设计方法&#xff0c;用于评估政策或其他干预措施的效果。这种方法利用了一个清晰的阈值或“断点”&#xff0c;在这个阈值上&#xff0c;处理状态&#xff08;例如是否接受某种干预&#xf…

2-2 opencv实战进阶系列 多边形识别

目录 一、不说废话&#xff0c;先上现象 二、前言 三、思路讲解 step1&#xff1a;用阈值编辑器对图像进行处理。 step2&#xff1a;应用阈值进行二值化 step3&#xff1a;轮廓查找 step4&#xff1a; 显示文字 四、完整代码贴出 五、现象展示 六、结语 一、不说废话&…

【FastAPI】离线使用Swagger UI 或 国内网络如何快速加载Swagger UI

在FastAPI中&#xff0c;默认情况下&#xff0c;当应用启动时&#xff0c;Swagger UI 会通过在线加载 Swagger UI 的静态资源。这意味着如果应用运行在没有互联网连接的环境中&#xff0c;默认的 Swagger 文档页面将无法加载。 为了在离线环境中使用 Swagger UI&#xff0c;你…

计算机毕业设计 智能推荐旅游平台 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

&#x1f34a;作者&#xff1a;计算机编程-吉哥 &#x1f34a;简介&#xff1a;专业从事JavaWeb程序开发&#xff0c;微信小程序开发&#xff0c;定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事&#xff0c;生活就是快乐的。 &#x1f34a;心愿&#xff1a;点…

生成树详细配置(STP、RSTP、MSTP)

目录 一. 实验内容 STP配置实验 RSTP配置实验 MSTP配置实验 二. 1 ) STP配置实验 实验拓扑 ​编辑 实验配置 实验结果 2 ) RSTP配置实验 实验拓扑 实验配置 实验结果 3 ) MSTP配置实验 实验拓扑 实验配置 ​编辑 实验结果 三 实验总结 一. 实验内容 1) …

(详细整理!!!!)Tensorflow与Keras、Python版本对应关系!!!

小伙伴们大家好&#xff0c;不知道大家有没有被tensorflow框架困扰过 今天我就给大家整理一下tensorflow和keras、python版本的对应关系 大家这些都可以在官网找到&#xff0c;下面我把官网的连接给大家放在这里&#xff1a;在 Windows 环境中从源代码构建 | TensorFlow (g…