网站首页的动态效果图怎么做,wordpress如何更换域名,安溪网页定制,沙坪坝最新消息今天双链表#xff08;数组模拟#xff09; 什么是双链表数组模拟双链表题目 什么是双链表
双链表不同于单链表的是 每一个节点不但存储了下一个节点的位置#xff0c;也存储了上一个节点的位置。
数组模拟双链表
所以如果用数组的话#xff0c;就需要创建三个数组。
题目 … 双链表数组模拟 什么是双链表数组模拟双链表题目 什么是双链表
双链表不同于单链表的是 每一个节点不但存储了下一个节点的位置也存储了上一个节点的位置。
数组模拟双链表
所以如果用数组的话就需要创建三个数组。
题目
实现一个双链表双链表初始为空支持 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 1e510;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个数就是下标就是k1.}else if (strcmp(op, IL) 0){scanf(%d%d, k, x);insert(l[k1], x); }else {scanf(%d%d, k, x);insert(k1, x);}}for (int i r[0]; i ! 1; i r[i]) printf(%d , e[i]);return 0;
} 完
