AcWing - 双链表(模拟)
发布日期:2021-07-01 00:21:57
浏览次数:3
分类:技术文章
本文共 2360 字,大约阅读时间需要 7 分钟。
题目链接:
时/空限制:1s / 64MB题目描述
实现一个双链表,双链表初始为空,支持5种操作:
(1) 在最左侧插入一个数;
(2) 在最右侧插入一个数;
(3) 将第k个插入的数删除;
(4) 在第k个插入的数左侧插入一个数;
(5) 在第k个插入的数右侧插入一个数
现在要对该链表进行M次操作,进行完所有操作后,从左到右输出整个链表。
注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数,则按照插入的时间顺序,这n个数依次为:第1个插入的数,第2个插入的数,…第n个插入的数。
输入格式
第一行包含整数M,表示操作次数。
接下来M行,每行包含一个操作命令,操作命令可能为以下几种:
(1) “L x”,表示在链表的最左端插入数x。
(2) “R x”,表示在链表的最右端插入数x。
(3) “D k”,表示将第k个插入的数删除。
(4) “IL k x”,表示在第k个插入的数左侧插入一个数。
(5) “IR k x”,表示在第k个插入的数右侧插入一个数。
输出格式
共一行,将整个链表从左到右输出。
数据范围
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
解题思路
题意:对双向链表有5种操作,求出n次操作后的双向链表。
思路:直接模拟,写的是数组型的,不过操作和指针的类似。Accepted Code:
/* * @Author: lzyws739307453 * @Language: C++ */#includeusing namespace std;const int MAXN = 100005;struct List { int data, prior, next; List() { prior = -1; next = -1; } List(int data, int prior, int next) : data(data), prior(prior), next(next) {}}list_[MAXN];int cnt = 0, head = 0, rear = 0;void Insert_L(int x) { list_[++cnt] = List(x, head, list_[head].next); list_[list_[head].next].prior = cnt; list_[head].next = cnt; if (!rear) rear = cnt;}void Insert_R(int x) { list_[++cnt] = List(x, rear, -1); list_[rear].next = cnt; rear = cnt;}void Delete(int k) { if (!(k != rear)) rear = list_[k].prior; else { list_[list_[k].prior].next = list_[k].next; list_[list_[k].next].prior = list_[k].prior; }}void Insert_IL(int k, int x) { list_[++cnt] = List(x, list_[k].prior, k); list_[list_[k].prior].next = cnt; list_[k].prior = cnt;}void Insert_IR(int k, int x) { list_[++cnt] = List(x, k, list_[k].next); list_[list_[k].next].prior = cnt; list_[k].next = cnt; if (!(rear != k)) rear = cnt;}int main() { char op; int n, k, x; scanf("%d", &n); while (n--) { scanf(" %c", &op); switch (op) { case 'L': scanf("%d", &x); Insert_L(x); break; case 'R': scanf("%d", &x); Insert_R(x); break; case 'D': scanf("%d", &k); Delete(k); break; default: scanf("%c%d%d", &op, &k, &x); if (op != 'R') Insert_IL(k, x); else Insert_IR(k, x); break; } } int p = list_[head].next; while (~p) { printf("%d ", list_[p].data); p = list_[p].next; } printf("\n"); return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/99958270 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2024年04月23日 03时46分27秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Err:11 https://developer.download.nvidia.cn/compute/cuda/repos/ubuntu2004/x86_64 Packages 404 No
2019-05-01
ubuntu opencv-python 安装很慢问题
2019-05-01
cudnn cuda-11.0
2019-05-01
MySQL5.7版本修改了my.ini配置文件后mysql服务无法启动问题
2019-05-01
【大数据开发】Java基础 -总结21-Hashmap和HashTable的区别
2019-05-01
Azkaban体系结构
2019-05-01
机器学习之重头戏-特征预处理
2019-05-01
synchronized底层实现及锁的升级、降级
2019-05-01
PermGen space-永久区内存溢出
2019-05-01
Maven继承和聚合
2019-05-01
nexus发布工程版本问题总结
2019-05-01
windows无法找到发送到桌面快捷方式
2019-05-01
redhat-vim文本编辑
2019-05-01
linux-文件挂载
2019-05-01
scala与java之间的集合类型转换
2019-05-01
Vue 3中令人激动的新功能:Fragment+Suspense+多v-model
2019-05-01
浅析Vuex及相关面试题答案
2019-05-01