$\color{green}{<–画图不易,点下这里赞一下吧}$
代码详解:
#include <iostream>
using namespace std;
const int N = 100010;
int e[N], l[N], r[N],index = 0;
void init()
{
//如下初始化导致第 a 个插入的元素的索引为: a + 1
l[1] = 0;
r[0] = 1;
index = 2;
}
// 在索引为 a 的右侧插入x,对应第 a - 1 个插入元素右侧插入 x
void insert(int a, int x)
{
e[index] = x;
l[index] = a;
r[index] = r[a];
l[r[a]] = index;
r[a] = index++;
}
//删除索引为 a 的元素,对应于删除第 a - 1 个插入元素。
void remove(int a)
{
r[l[a]] = r[a];
l[r[a]] = l[a];
}
int main()
{
init();
int m;
cin>>m;
while(m--)
{
string op;
cin >> op;
int k, x;
if(op == "L")
{
cin >> x;
insert(0, x);
}
else if(op == "R")
{
cin >> x;
insert(l[1], x);
}
else if (op == "D")
{
cin >> k;
remove(k + 1);//第 k 个插入元素对应的索引为 k + 1
}
else if (op == "IL")
{
cin >> k >> x;
insert(l[k + 1], x);// 第 k 个插入元素对应的索引为 k + 1, l[k + 1] 为链表中上一个位置对应的索引
}
else
{
cin >> k >> x;
insert(k + 1, x);//第 k 个插入元素对应的索引为 k + 1
}
}
for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
cout << endl;
return 0;
}
完结,撒花,求赞~~
为什么在最左边插入的a是0,最右边插入的a是l[1]啊?
同问,l[1]不是0吗
为什么是k+1,我怎么想都是k-1
一开始初始化用了两个结点表示头和尾,这两个点设置前后指针形成双链表,就相当于一个点就已经用了,假设k=3时,这个时候你要找的点是第三个,但是由于头结点已经用掉一个了,这个时候参数写k的话相当于是第二个点,所以要写k+1;
idx=2,是用了两个点吧(0、1)
https://www.acwing.com/file_system/file/content/whole/index/content/11769884/
你好,可以参考一下我的理解。//为什么要remove1(k+1)?
初始化时idx=2,indx表示下一个可以存储元素的位置索引。在e[]数组为空时,已经有头尾两个指针了,头指针在数组中的下标为0,尾指针在数组中下标为1,所以第一个插入的值,在数组中的下标为2,以此类推,第k个插入的值在数组e[]中的下标为k+1
请问这里用scanf和printf为什么会segmentation fault呢?好像是输入输出数据的时候出了一点问题?
看了单链表那篇再看双链表这边终于知道为什么是k+1了,第k个数这个概念我一直混了,以为是从左往右数,原来是第k个插入的数,然后第k个数插入的索引是k+1,感谢大佬
主要是结构体比较慢,如果是优化写法的话,和数组也差不多了
new节点的时候会很慢
对
为啥是l!=1呀
因为1代表着尾节点
结构体也可以用,但是写的要多一点,就是各种.,没数组方便。