AcWing - 双链表(模拟)
发布日期:2021-07-01 00:21:57
浏览次数:4
分类:技术文章
本文共 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月26日 12时37分10秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
什么是Web 2.0?
2019-05-01
Junit执行及加载顺序分析(原创)
2019-05-01
ORACLE SQL性能优化系列(一)
2019-05-01
ORACLE SQL性能优化系列(二)
2019-05-01
处理正则表达式的java包:regexp
2019-05-01
正则表达式简介(微软)--4.正则表达式语法
2019-05-01
正则表达式简介(微软)--5.建立正则表达式
2019-05-01
正则表达式简介(微软)--6.优先权顺序
2019-05-01
算法-Hash+滑动窗口/按位编码-重复的DNA序列
2019-05-01
多用户与多租户的区别
2019-05-01
算法-滑动窗口-最小覆盖子串
2019-05-01
算法-图/DFS/BFS/并查集-岛屿数量
2019-05-01
算法-并查集
2019-05-01
常使用的Emacs命令
2019-05-01
现代UNIX系统有什么设计上的不足么
2019-05-01
linux 初学者常用命令!
2019-05-01
Spring源代码解析(四):Spring MVC
2019-05-01
Spring源代码解析(五):Spring AOP获取Proxy
2019-05-01
Spring源代码解析(六):Spring声明式事务处理
2019-05-01
8张图理解Java
2019-05-01