双链表
作者:
ICE_TEA
,
2022-11-18 19:46:39
,
所有人可见
,
阅读 171
// e[]表示节点的值,l[]表示节点的左指针,r[]表示节点的右指针,idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;
// 初始化
void init()
{
//0是左端点,1是右端点
r[0] = 1, l[1] = 0;
idx = 2;
}
// 在节点a的右边插入一个数x
void insert(int a, int x)
{
e[idx] = x;
l[idx] = a, r[idx] = r[a];
l[r[a]] = idx, r[a] = idx ++ ;
}
// 删除节点a
void remove(int a)
{
l[r[a]] = l[a];
r[l[a]] = r[a];
}
/////////////////////////////////////////////////////////////////////////
//cin.sync()标准未定义,不一定是清空缓存区
#include<iostream>
#include<string>
using namespace std;
const int N = 111111;
int l[N], r[N], e[N], idx;
void init()
{
r[0] = 1;
l[1] = 0;
idx = 2;
}
void dlt(int k)
{
r[l[k]] = r[k];
l[r[k]] = l[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++;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
init();
int n;
cin >> n;
string s;
//getchar();
for (int i = 0; i < n; i++)
{
//getline(cin, s);
cin >> s;
if (s == "L")
{
int x;
cin >> x;
insert(0, x);
}
if (s == "R")
{
int x;
cin >> x;
insert(l[1], x);
}
if (s == "D")
{
int k;
cin >> k;
dlt(k+1);
}
if (s == "IL")
{
int k, x;
cin >> k >> x;
insert(l[k+1], x);
}
if (s == "IR")
{
int k, x;
cin >> k >> x;
insert(k+1, x);
}
//cin.sync();
}
int t = r[0];
while (t-1)
{
cout << e[t] << ' ';
t = r[t];
}
return 0;
}