双链表(数组模拟)
双链表(数组模拟)
- 什么是双链表
- 数组模拟双链表
- 题目
什么是双链表
双链表不同于单链表的是 每一个节点不但存储了下一个节点的位置,也存储了上一个节点的位置。
数组模拟双链表
所以如果用数组的话,就需要创建三个数组。
题目
实现一个双链表,双链表初始为空,支持 5 5 5 种操作:
- 在最左侧插入一个数;
- 在最右侧插入一个数;
- 将第 k k k 个插入的数删除;
- 在第 k k k 个插入的数左侧插入一个数;
- 在第 k k k 个插入的数右侧插入一个数
现在要对该链表进行 M M M 次操作,进行完所有操作后,从左到右输出整个链表。
注意:题目中第 k k k 个插入的数并不是指当前链表的第 k k k 个数。例如操作过程中一共插入了 n n n 个数,则按照插入的时间顺序,这 n n n 个数依次为:第 1 1 1 个插入的数,第 2 2 2 个插入的数,…第 n n n 个插入的数。
输入格式
第一行包含整数 M M M,表示操作次数。
接下来 M M M 行,每行包含一个操作命令,操作命令可能为以下几种:
L x,表示在链表的最左端插入数 x x x。R x,表示在链表的最右端插入数 x x x。D k,表示将第 k k k 个插入的数删除。IL k x,表示在第 k k k 个插入的数左侧插入一个数。IR k x,表示在第 k k k 个插入的数右侧插入一个数。
输出格式
共一行,将整个链表从左到右输出。
数据范围
1 ≤ M ≤ 100000 1 \le M \le 100000 1≤M≤100000
所有操作保证合法。
输入样例:
10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2
输出样例:
8 7 7 3 2 9

其中 数组 e 用于存储 元素的值,数组 l 存储上一个节点的位置(下标),数组 r 存储下一个节点的位置。
idx 是 下一次即将要用到的 点。
对于双链表来说,虽然题目中有5中操作,但是只需要写两个函数就可以了。(不包含初始化函数)
初始化函数:

在用数组模拟双链表时,我们可以规定数组的前两个点分别指向 链表的头和尾,由于刚开始没有节点。
所以让他们互相指向对方,由于前面用了两个点,所以直接 让 idx = 2.
在 k 位置 后插入 一个新节点 的函数:

模拟代码过程:

e[ idx ] = x;

l[ idx ] = k;

r[ idx ] = r[ k ];

l[ r [ k ] ] = idx;

r[ k ] = idx;

最后自增 idx。
删除 下标为 k 的 数 的函数:

r[ l[ k ] ] = r [ k ];

l [ r [ k ] ] = l [ k ];

本题目当中的五种操作都可以转换该两种函数。

输入m,然后循环输入m次,记得写初始化函数。

因为用scanf读取字符会读取空格或换行符,而%s不会读取这些符号,所以会方便很多
题目的五个操作:

0下标是一个没有存值(数组e里面没有值,数组 l 有值)的头坐标,所以在下标0的右面插入一个值相当于在整个链表左边插入一个值。

1下标记录着链表最右边的位置,l [ 1 ] 则代表链表中最右边的点的位置,所以在 l [ 1 ] 后面插入相当于在链表的 最右边插入一个值。

这里唯一注意的点就是 传的实参是 k + 1,而不是k ,因为已经用过两个点了。所以插入的第一个数的下标就是从2开始的,以此类推。


如果我们想要在 k 位置的左边插入一个节点,那么相当于在 k 的左边节点的右侧插入一个节点。

那么在右侧就直接调用函数即可。
最后输出整个链表即可

完整代码如下:
#include <iostream>
#include <cstring>
using namespace std;const int N = 1e5+10;int e[N], l[N], r[N];
int idx;void init()
{r[0] = 1;l[1] = 0;idx = 2;
}//在 k 下标后插入一个数
void insert(int k, int x)
{e[idx] = x;l[idx] = k;r[idx] = r[k];l[r[k]] = idx;r[k] = idx;idx++;
}//删除下标为 k 的节点
void remove(int k)
{r[l[k]] = r[k];l[r[k]] = l[k];
}int main()
{init();int m;scanf("%d", &m);while (m--){char op[5];int k, x;scanf("%s", op);if (op[0] == 'L')//链表最左端插入一个数{scanf("%d", &x);insert(0, x);}else if (op[0] == 'R')//链表最右端插入一个数{scanf("%d", &x);insert(l[1], x);}else if (op[0] == 'D')//将插入的第K个数删除{scanf("%d", &k);remove(k + 1);//数组刚开始会用掉两个点,//那么插入的第一个数下标就为2,所以插入的第k个数就是下标就是k+1.}else if (strcmp(op, "IL") == 0){scanf("%d%d", &k, &x);insert(l[k+1], x); }else {scanf("%d%d", &k, &x);insert(k+1, x);}}for (int i = r[0]; i != 1; i = r[i]) printf("%d ", e[i]);return 0;
}
完
相关文章:
双链表(数组模拟)
双链表(数组模拟) 什么是双链表数组模拟双链表题目 什么是双链表 双链表不同于单链表的是 每一个节点不但存储了下一个节点的位置,也存储了上一个节点的位置。 数组模拟双链表 所以如果用数组的话,就需要创建三个数组。 题目 …...
ChatGPT 5.0:一年半后的展望与看法
在人工智能领域,每一次技术的飞跃都预示着未来生活与工作方式的深刻变革。随着OpenAI在人工智能领域的不断探索与突破,ChatGPT系列模型已成为全球关注的焦点。当谈及ChatGPT 5.0在未来一年半后可能发布的前景时,我们不禁充满期待,…...
城市地下综合管廊物联网远程监控
城市地下综合管廊物联网远程监控 城市地下综合管廊,作为现代都市基础设施的重要组成部分,其物联网远程监控系统的构建是实现智慧城市建设的关键环节。这一系统集成了先进的信息技术、传感器技术、通信技术和数据处理技术,旨在对埋设于地下的…...
VS 附加进程调试
背景: 此方式适合VS、代码和待调试的exe在同一台机器上。 一、还原代码到和正在跑的exe同版本 此操作可以保证能够调试生产环境的exe 二、设置符号路径 1.调试->选项 三、附加进程 方式1: 打开VS,调试->附加到进程,出…...
核函数的深入理解
核函数 (Kernel Function)是一种在高维特征空间中隐式计算内积的方法,它允许在原始低维空间中通过一个简单的函数来实现高维空间中的内积计算,而无需显式地计算高维特征向量。 核函数 的基本思想是通过一个映射函数 ϕ \phi ϕ …...
使用Ckman部署ClickHouse集群介绍
使用Ckman部署ClickHouse集群介绍 1. Ckman简介 ClickHouse Manager是一个为ClickHouse数据库量身定制的管理工具,它是由擎创科技数据库团队主导研发的一款用来管理和监控ClickHouse集群的可视化运维工具。目前该工具已在github上开源,开源地址为&…...
「前端工具」postman接口测试工具详解
Postman 是一款流行的 API 开发工具,用于构建和测试 RESTful API。以下是 Postman 的一些关键特性和使用方法的详解: 1. 界面和基本操作 工作区:Postman 的主界面,用于显示集合、环境和全局变量。请求构建器:用于输入请求的 URL、HTTP 方法、请求头、请求体等。响应区:显…...
生成requirements.txt
pip install pipreqs pipreqs ./ --encodingutf-8 --force python导出requirements.txt的几种方法总结...
ubuntu ceph部署
ubuntu ceph部署 参考文档:http://docs.ceph.org.cn/start/ 节点配置 1个mon节点,3个osd节点 安装前准备 安装ceph-deploy 添加 release key wget -q -O- https://download.ceph.com/keys/release.asc | sudo apt-key add -添加Ceph软件包源&…...
2024.7.8
2024.7.8 【追逐影子的人,自己就是影子 —— 荷马】 Monday 六月初三 讲的根本听不懂好吧! 目前只写了三道题(但是黑色 确实是没见过这么抽象的数据结构 Gregor and the Two Painters Number of Components Equal LCM Subsets 这个lcm确实…...
Spring 外部jar包Bean自动装配
Spring 外部jar包Bean自动装配 背景介绍 公共代码模块被作为jar包引入业务项目,前者定义的bean即使添加了Component注解由于不会被扫描到也就无法被Spring管理。此处通过Spring SPI机制来完成 使用 spring.factories 在外部 jar 包中创建 spring.factories 文件&a…...
2通道音频ADC解码芯片ES7243L、ES7243E、ES7243,用于低成本实现模拟麦克风转换为IIS数字话筒
前言: 音频解码芯片某创参考价格: ES7243L 500:¥1.36 / 个 ES7243E 500:¥1.66 / 个 ES7243 500: ¥1.91 / 个 其中ES7243L工作电压为1.8V,与其他两款的3.3V工作电压不同&…...
uniapp跨域问题解决
找到menifest文件,在文件的最后添加如下代码: // h5 解决跨域问题"h5":{"devServer": {"proxy": {"/adminapi": {"target": "https://www.demo.com", // 目标访问网址"changeOrigin…...
[C++][ProtoBuf][Proto3语法][一]详细讲解
目录 1.字段规则2.消息类型的定义与使用1.定义2.使用 3.enum类型1.语法2.定义时注意3.代码 1.字段规则 消息的字段可以⽤下⾯⼏种规则来修饰: singular:消息中可以包含该字段零次或⼀次(不超过⼀次) proto3语法中,字段默认使⽤该规则 repeat…...
千古雄文《渔樵问对》原文、译文、解析
邵雍《渔樵问对》:开悟奇文,揭示世界的终极意义 【邵雍《渔樵问对》:开悟奇文,揭示世界的终极意义】 邵雍(1011年1月21日-1077年7月27日,宋真宗大中祥符四年十二月二十五日戌时生至神宗熙宁十…...
uniapp 开发备忘录-防坑指南
uniapp 开发备忘录-防坑指南 npm run dev:mp-weixin 编译微信小程序报错: [plugin:uni:mp-using-component] Expected ‘,’ or ‘}’ after property value in JSON at position 解决方案:升级uniapp 到最新 alpha 版。(2024年7月13日&am…...
Simple_ReAct_Agent
参考自https://www.deeplearning.ai/short-courses/ai-agents-in-langgraph,以下为代码的实现。 Basic ReAct Agent(manual action) import openai import re import httpx import os from dotenv import load_dotenv, find_dotenvOPENAI_API_KEY os.getenv(OPEN…...
window wsl安装ubuntu
文章目录 wsl安装ubuntu什么是wsl安装wsl检查运行 WSL 2 的要求将 WSL 2 设置为默认版本查看并安装linux WSL2的使用如何查看linux文件wsl如何使用代理:方法1:方法2:通过 DNS 隧道来配置 WSL 的网络 如何将 WSL 接入局域网并与宿主机同网段使用VScode连接…...
postmessage()在同一域名下,传递消息给另一个页面
这里是同域名下,getmessage.html(发送信息)传递消息给index.html(收到信息,并回传收到信息) index.html页面 <!DOCTYPE html> <html><head><meta http-equiv"content-type"…...
初始redis:在Ubuntu上安装redis
1.先切换到root用户 使用su命令切换到root 2.使用apt命令来搜索redis相关的软件包 命令:apt search redis 3.下载redis 命令: apt install redis 在Ubuntu 20.04中 ,下载的redis版本是redis5 4.查看redis状态 命令: netst…...
超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...
新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
Rapidio门铃消息FIFO溢出机制
关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系,以下是深入解析: 门铃FIFO溢出的本质 在RapidIO系统中,门铃消息FIFO是硬件控制器内部的缓冲区,用于临时存储接收到的门铃消息(Doorbell Message)。…...
VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
R语言速释制剂QBD解决方案之三
本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...
AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...
Ubuntu系统复制(U盘-电脑硬盘)
所需环境 电脑自带硬盘:1块 (1T) U盘1:Ubuntu系统引导盘(用于“U盘2”复制到“电脑自带硬盘”) U盘2:Ubuntu系统盘(1T,用于被复制) !!!建议“电脑…...
32单片机——基本定时器
STM32F103有众多的定时器,其中包括2个基本定时器(TIM6和TIM7)、4个通用定时器(TIM2~TIM5)、2个高级控制定时器(TIM1和TIM8),这些定时器彼此完全独立,不共享任何资源 1、定…...
