双链表
一、算法描述
本篇文章讲述的数据结构是双链表，与上一篇文章一样是算法竞赛中常用的用数组模拟的双链表。
//用数组模拟的双链表定义如下：
int e[N], l[N], r[N], idx;
/*
e[i]表示节点i的值
l[i]表示节点i的左边一个节点
r[i]表示节点i的右边一个节点
idx表示当前用到了哪个节点
*/
- 跟单链表差不多。
- 多画图，多思考。
接下来介绍双链表的各种操作：
初始化操作：
void init()
{
r[0] = 1, l[1] = 0, idx = 2;
}
- 以 \(0\) 和 \(1\) 为两个界限，初始状态就是 \(0\) 的右边是 \(1\) ，\(1\) 的左边是 \(0\)。
- 要注意 \(idx\) 从 \(2\) 开始。
在第k个节点右边插入：
void add(int k, int x) //在第k个节点的右边插入一个新节点
{
e[idx] = x;
r[idx] = r[k], l[r[k]] = idx;
l[idx] = k, r[k] = idx ++ ;
}
- \(e[idx] = x\) 表示新节点的值为 \(x\)。
- \(r[idx] = r[k], l[r[k]] = idx;\) 表示新节点的下一个节点指向 \(k\) 节点的下一个节点 \(p\) ，然后 \(p\) 的前一个节点又指向新节点。
- \(l[idx] = k, r[k] = idx;\) 表示新节点的左节点为 \(k\) ，\(k\) 节点的右节点指向 新节点。
- \(idx ++ ;\) 表示当前节点已经被用了，待使用的节点是下一个。
- 如何在左边插入呢？显然只需要修改一下参数即可：
add(l[k], x)。 - 建议画图来理解。
删除第 \(k\) 个节点：
void remove(int k)
{
r[l[k]] = r[k];
l[r[k]] = l[k];
}
- 数组删除不需要管内存泄漏的问题。
- 假设用 \(p, k, q\) 来表示三个节点：
- \(r[l[k]] = r[k];\) 表示 \(p\) 的右边指向 \(k\) 的右边，即 \(q\)。
- \(l[r[k]] = l[k];\) 表示 \(q\) 的左边指向 \(k\) 的左边，即 \(p\)。
- 画图来理解。
如何遍历呢？
for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
for (int i = l[1]; i != 0; i = l[i]) cout << e[i] << ' ';
- 第一行是从左往右遍历，第二行是从右往左遍历。
- \(0\) 和 \(1\) 是两个界限，所以是从 \(r[0]\) 和 \(l[1]\) 开始，而不是从 \(0\) 和 \(1\) 开始。
链表的问题都需要读者多画图、多思考，也要多复习。
二、题目描述
实现一个双链表，双链表初始为空，支持 \(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 <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int e[N], l[N], r[N], idx;
void init()
{
l[1] = 0, r[0] = 1, idx = 2;
}
void add(int k, int x)
{
e[idx] = x;
r[idx] = r[k], l[r[k]] = idx;
l[idx] = k, r[k] = idx ++ ;
}
void remove(int k)
{
r[l[k]] = r[k];
l[r[k]] = l[k];
}
int main()
{
int m;
cin >> m;
init();
while (m -- )
{
char s[10];
cin >> s;
int k, x;
if (!strcmp(s, "L"))
{
cin >> x;
add(0, x);
}
else if (!strcmp(s, "R"))
{
cin >> x;
add(l[1], x);
}
else if (!strcmp(s, "D"))
{
cin >> k;
remove(k + 1);
}
else if (!strcmp(s, "IL"))
{
cin >> k >> x;
add(l[k + 1], x);
}
else
{
cin >> k >> x;
add(k + 1, x);
}
}
for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
return 0;
}
/*
本题目并非完全照抄以上函数，还是需要处理一些问题的。
例如：删除第k个数，idx是从2开始使用的，所以删除的时候应该是remove(k + 1);
还有其他问题，读者可自行思考。
*/