做网站违反广告法,电脑网站开发,个人网站开发 怎么赚钱吗,聊城哪儿做网站便宜实现一个双链表#xff0c;双链表初始为空#xff0c;支持 5 种操作#xff1a;
在最左侧插入一个数#xff1b; 在最右侧插入一个数#xff1b; 将第 k 个插入的数删除#xff1b; 在第 k 个插入的数左侧插入一个数#xff1b; 在第 k 个插入的数右侧插入一个数 现在要…实现一个双链表双链表初始为空支持 5 种操作
在最左侧插入一个数 在最右侧插入一个数 将第 k 个插入的数删除 在第 k 个插入的数左侧插入一个数 在第 k 个插入的数右侧插入一个数 现在要对该链表进行 M 次操作进行完所有操作后从左到右输出整个链表。
注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数则按照插入的时间顺序这 n 个数依次为第 1 个插入的数第 2 个插入的数…第 n 个插入的数。
输入格式 第一行包含整数 M 表示操作次数。
接下来 M 行每行包含一个操作命令操作命令可能为以下几种
L x表示在链表的最左端插入数 x 。 R x表示在链表的最右端插入数 x 。 D k表示将第 k 个插入的数删除。 IL k x表示在第 k 个插入的数左侧插入一个数。 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
#include iostreamusing namespace std;const int N 100010;
int head, idx;
int e[N], l[N], r[N];void init()//初始化为0是左端点1是右端点。
{r[0] 1, l[1] 0;idx 2;
}void add_(int k, int x)
{e[idx] x;r[idx] r[k];l[idx] k;l[r[k]] idx; //先调用r[k]再改r[k]r[k] idx;idx ;
}void remove_(int k)
{r[l[k]] r[k];l[r[k]] l[k];
}int main()
{int m;cinm;int k, x;init();while(m -- ){string op;cinop;if(op L){cinx;add_(0, x);}else if(op R){cinx;add_(l[1], x); //右端点左侧}else if(op D){cink;remove_(k 1);}else if(op IL){cinkx;add_(l[k 1], x);}else{cinkx;add_(k 1, x);}} for(int i r[0]; i ! 1; i r[i]) coute[i] ;return 0;
}
