数据结构--双链表

news/2024/5/28 2:52:33/文章来源:https://blog.csdn.net/qq_42673622/article/details/133316244

今天我们来用数组来模拟双链表

为什么要数组模拟呢?
因为用数组模拟的双链表,运行速度更快,做算法题更加舒服

用数组模拟双链表的内容

1、同样也有首尾结点
2、相邻的两个节点是相互指向的
3、可以看成两个方向相反的单链表相互连接在一起

首先同样要初始化

1、现在用两个数组来代表左单链表和右单链表,即为l[N], r[N]
2、l[N]数组为指向右边的链表,r[N]为指向左边的链表
3、e[N]为当前结点的值
4、设r[0]=1,l[1]=0,因为是相互指向
5、同样用一个idx来储存当前结点用到了哪一点下面给出图和代码

在这里插入图片描述

int m;
int e[N],r[N],l[N],idx;void init()
{r[0]=1,l[1]=0;idx=2;
}

为什么idx要等于2呢,因为初始化左右结点因为各被用了,所以 idx为2,而且0代表头结点,1为尾节点

接下来就是功能的实现

1、任意插入一个数x
2、任意删除某一个结点

讲x插入到第k的右边

1、首先要确定某一个结点,e[idx]=x;
2、让idx的右边指向k结点的右边,r[idx]=r[k];
3、让idx的左边指向k,l[idx]=k
4、再让k结点的右边的点指向x,即为l[r[k]]=idx;
5、再让k结点的左边指向idx,r[k]=idx;
6、最后当前结点被用过了,所以idx要向后移动一位,即idx++;

在这里插入图片描述
而且第四步和第五步不能相互颠倒,如果相互颠倒,就会改变r[k]的值,就会出现错误
代码功能如下

//插入第k个数
void add(int k,int x)
{e[idx]=x;r[idx]=r[k];l[idx]=k;l[r[k]]=idx;r[k]=idx;idx++;
}

那怎么插入到k节点的左边呢?

就是相当于l[k]的右边插入一个数,所以把参数k换成l[k]就行,因为l[k]为k左边相邻的结点

2、删除某一个结点

和单链表相似,不过这次要左边和右边都要相互操作一遍

因为某一个结点都是相互指向的,用第k个结点举例

首先,用k结点的左边的结点等于k结点右边的结点,即为r[l[k]]=r[k];

然后再让k结点的右边的结点等于k结点左边的节点,即为l[r[k]]=l[k];

//删除第k个数
void remove(int k)
{r[l[k]]=r[k];l[r[k]]=l[k];
}

这样双链表的功能的就实现了

具体问题:

实现一个双链表,双链表初始为空,支持 5 种操作:

  1. 在最左侧插入一个数;
  2. 在最右侧插入一个数;
  3. 将第 k 个插入的数删除;
  4. 在第 k 个插入的数左侧插入一个数;
  5. 在第 k 个插入的数右侧插入一个数
  6. 现在要对该链表进行 M 次操作,进行完所有操作后,从左到右输出整个链表。

现在要对该链表进行 M 次操作,进行完所有操作后,从左到右输出整个链表。
注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数,则按照插入的前后顺序,这 n 个数依次为:第 1 个插入的数,第 2 个插入的数,…第 n 个插入的数。

Acwing 827

#include <iostream>
using namespace std;const int N = 100010;
int e[N], l[N], r[N], idx;void init() {r[0] = 1, l[1] = 0;idx = 2;
}// 在下标是k的点的右边插入x
void add(int k, int x) {e[idx] = x;l[idx] = k;r[idx] = r[k];l[r[k]] = idx;r[k] = idx;idx++;
}void remove(int k) {r[l[k]] = r[k];l[r[k]] = l[k];
}int main() {int n;cin >> n;init();while (n--) {string op;cin >> op;int k, x;if (op == "L") {cin >> x;add(0, x);} else if (op == "R") {cin >> x;add(l[1], x);} else if (op == "D") {cin >> k;remove(k + 1);} else if (op == "IL") {cin >> k >> x;add(l[k + 1], x);} else if (op == "IR") {cin >> k >> x;add(k + 1, x);}}int head = r[0];while (head != 1) {cout << e[head] << " ";head = r[head];}return 0;
}

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

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

相关文章

【项目】Http服务器

【项目】Http服务器 项目简介 背景&#xff1a; http协议被广泛使用&#xff0c;从移动端&#xff0c;pc端浏览器&#xff0c;http协议无疑是打开互联网应用窗口的重要协议&#xff0c;http在网络应用层中的地位不可撼动&#xff0c;是能准确区分前后台的重要协议。 描述&a…

Android Studio插件版本与Gradle 版本对应关系

关于作者&#xff1a;CSDN内容合伙人、技术专家&#xff0c; 从零开始做日活千万级APP。 专注于分享各领域原创系列文章 &#xff0c;擅长java后端、移动开发、商业变现、人工智能等&#xff0c;希望大家多多支持。 目录 一、导读二、概览三、Gradle各版本对应关系3.1 Gradle 版…

26663-2011 大型液压安全联轴器 课堂随笔

声明 本文是学习GB-T 26663-2011 大型液压安全联轴器. 而整理的学习笔记,分享出来希望更多人受益,如果存在侵权请及时联系我们 1 范围 本标准规定了大型液压安全联轴器的分类、技术要求、试验方法及检验规则等。 本标准适用于联接两同轴线的传动轴系&#xff0c;可起到限制…

【AntDesign】封装全局异常处理-全局拦截器

[toc] 场景 本文前端用的是阿里的Ant-Design框架&#xff0c;其他框架也有全局拦截器&#xff0c;思路是相同&#xff0c;具体实现自行百度下吧 因为每次都需要调接口&#xff0c;都需要单独处理异常情况&#xff08;code !0&#xff09;&#xff0c;因此前端需要对后端返回的…

问题记录 springboot 事务方法中使用this调用其它方法

原因: 因为代理对象中调用了原始对象的toString()方法,所以两个不同的对象打印出的引用是相同的

解决Linux服务器中docker访问报127.0.0.1:2375拒绝连接 (Connection refused)的问题

解决问题&#xff1a; org.apache.hc.client5.http.HttpHostConnectException: Connect to http://127.0.0.1:2375 [/127.0.0.1] failed: 拒绝连接 (Connection refused) 解决思路&#xff1a; 在Linux服务器中&#xff0c;Docker是远程访问的&#xff0c;因此需要开放2375端口…

Java 基于 SpringBoot 的在线学习平台

1 简介 基于SpringBoot的Java学习平台&#xff0c;通过这个系统能够满足学习信息的管理及学生和教师的学习管理功能。系统的主要功能包括首页&#xff0c;个人中心&#xff0c;学生管理&#xff0c;教师管理&#xff0c;课程信息管理&#xff0c;类型管理&#xff0c;作业信息…

时序分解 | Matlab实现SSA-VMD麻雀算法优化变分模态分解时间序列信号分解

时序分解 | Matlab实现SSA-VMD麻雀算法优化变分模态分解时间序列信号分解 目录 时序分解 | Matlab实现SSA-VMD麻雀算法优化变分模态分解时间序列信号分解效果一览基本介绍程序设计参考资料 效果一览 基本介绍 SSA-VMD麻雀搜索算法SSA优化VMD变分模态分解 可直接运行 分解效果好…

华为云云耀云服务器L实例评测 | 实例评测使用之体验评测:华为云云耀云服务器安全加固/防范黑客攻击

华为云云耀云服务器L实例评测 &#xff5c; 实例评测使用之体验评测&#xff1a;华为云云耀云服务器安全加固/防范黑客攻击 介绍华为云云耀云服务器 华为云云耀云服务器 &#xff08;目前已经全新升级为 华为云云耀云服务器L实例&#xff09; 华为云云耀云服务器是什么华为云云…

【项目】在线音乐播放器测试报告

目录 项目背景 项目功能 测试计划 功能测试 登录页面的测试 测试用例 测试结果 注册页面的测试 测试用例 测试结果 音乐列表页面的测试 测试用例 测试结果 出现的bug 搜索功能的bug 问题解决 删除功能的bug 问题解决 喜欢列表页面的测试 测试用例 测试结果…

stc8H驱动并控制三相无刷电机综合项目技术资料综合篇

stc8H驱动并控制三相无刷电机综合项目技术资料综合篇 🌿相关项目介绍《基于stc8H驱动三相无刷电机开源项目技术专题概要》 🔨停机状态,才能进入设置状态,可以设置调速模式,以及转动方向。 ✨所有的功能基本已经完成调试,目前所想到的功能基本已经都添加和实现。引脚利…

python进制转换

""" 基数:有几个数 0b 2进制: 0、1 基数是:2 0o 8进制: 0、1、2、3、4、5、6、7 基数是:8 0d 10进制: 0到9 基数是:10 0x 16进制: 0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F 基数是:16十进制转二进制: bin() 十进制转八进…

安卓玩机-----给app加注册码 app加弹窗 云注入弹窗

在对接很多工作室业务中有些客户需要在他们自带的有些app中加注册码或者验证码的需求。其实操作起来也很简单。很多反编译软件有自带的注入功能。例如注入弹窗。这个是需要对应的注册码来启动应用。而且是随机id。重新安装app后需要重新注册才可以继续使用&#xff0c;原则上可…

仿真数据检查器如何比较数据

可以定制仿真数据检查器比较过程&#xff0c;以多种方式满足您的需求。在比较各运行时&#xff0c;仿真数据检查器会执行以下操作&#xff1a; 根据对齐设置&#xff0c;对齐基线运行和比较项运行中的信号对组。 仿真数据检查器不会比较无法对齐的信号。 根据指定的同步方法同…

前端开发如何更好的避免样式冲突?级联层(CSS@layer)

本文主要讲述了CSS中的级联层&#xff08;CSSlayer&#xff09;&#xff0c;讨论了级联以及级联层的创建、嵌套、排序和浏览器支持情况。级联层可以用于避免样式冲突&#xff0c;提高代码可读性和可维护性。 一、什么是级联层(Cascade Layers)&#xff1f; 1.1 级联层的官方定…

网络子网划分练习

网络子网划分练习 1.背景&#xff1a; 在一个仓储企业网络拓朴结构如图1-所示&#xff0c;该企业占地500亩。有五层办公楼1栋&#xff0c;大型仓库10栋。每栋仓库内、外部配置视频监控16台&#xff0c;共计安装视频监控160台&#xff0c;Switch A、服务器、防火墙、管理机、Rou…

源码编译安装zstd

目录 1 下载源码https://github.com/facebook/zstd 2 解压 3 在解压后的目录里输入make 4 sudo make install 安装完毕 5 输入whereis zstd 检查安装结果 1 下载源码https://github.com/facebook/zstd 2 解压 3 在解压后的目录里输入make 4 sudo make install 安装完毕…

【2023保研】双非上岸东南网安

个人情况 学校&#xff1a;henu 专业&#xff1a;信息安全 排名&#xff1a;1/66 英语&#xff1a;六级500 竞赛&#xff1a;蓝桥杯PB国一&#xff0c;ISCC国一&#xff0c;密码数学挑战赛国三&#xff0c;还有其他一些省级水奖 论文&#xff1a;一篇EI在投&#xff08;三作通…

【Aurora 8B/10B IP(1)--初步了解】

Aurora 8B/10B IP(1)–初步了解 1 Aurora 8b/10b IP的基本状态: •通用数据通道吞吐量范围从480 Mb/s到84.48 Gb/s •支持多达16个连续粘合7GTX/GTH系列、UltraScale™ GTH或UltraScale+™ GTH收发器和4绑定GTP收发器 •Aurora 8B/10B协议规范v2.3顺从的 •资源成本低(请参…

python:bottle + eel 模仿 mdict 查英汉词典

Eel 是一个轻量的 Python 库&#xff0c;用于制作简单的类似于离线 HTML/JS GUI 应用程序&#xff0c;并具有对 Python 功能和库的完全访问权限。 Eel 托管一个本地 Web 服务器&#xff0c;允许您使用 Python 注释函数&#xff08;annotate functions&#xff09;&#xff0c;…