[数据结构与算法]AcWing 826. 单链表

题目描述

分析：

之前学习单链表的时候都是使用的动态链表，第一次接触到静态链表。静态链表需要开两个数组 $e[]$和 $ne[]$ 存储所有结点的数据域和指针域的值。静态链表使用起来相对“死板”，是很看重是第几次插入这样的顺序信息，比如先插入两个结点再删除两个结点，那么第三次插入某结点时，这个“第三次”对于操作起重要的作用，比如要 idx 配合找出存储位置，还要根据这个第三次找到第二次插入的结点的指针指向并对其修改。动态链表中没有那么地麻烦，你插入两个再删除两个，第三个插入我只需要一个 new，再将头指针指向我当前 new 出来的地址即可，用起来灵活多了。

OK。既然动态链表那么好，我们不妨先看一下动态链表的插入和删除操作，以及会给出一个关键的思想。请务必理解并记住，这是解静态链表题目的关键。

这个思想就是：如果要在第 $k$ 个位置插入/删除结点，只需要操作第 $k?1$ 个位置的结点的指针指向即可。

好了，说了那么多动态链表的事情，我们回到本题目中，看看静态链表中的插入和删除操作。

静态链表删除后不对数组进行清空，因此涉及多次插入删除操作后数组存储情况就会很乱，不易理解，我们不妨设现在情况如下：

插入：

I k x，表示在第 $k$ 个插入的数后面插入一个数 $x$（此操作中 k 均大于 0）。
OKOK，这 $k$ 我一看着就头疼。来具体化一点，I 1 x：表示在第 $1$ 个插入的数后面插入一个数 $x$，也就是在第 $2$ 个位置插入一个数，根据上面的总结我们只需要修改第 $1$ 个位置的结点的指针指向。那第 $1$ 个位置的结点的指针信息存在哪里呢？答：存在 $ne[0]$。这就是下面代码中 $k?1$ 的原因。

if (s == 'I'){
	int k, x;
	cin >> k >> x;
	add(k - 1, x);
}

即 I k x ---> add(k - 1, x)。

删除：

删除和插入对于参数的分析是相同的，但有一个边界分题，一会我们再说。
D k，表示删除第 $k$ 个插入的数后面的数。同样地我们来具体化一点，D 1：表示删除第 $1$ 个插入的数后面的数，也就是删除在第 $2$ 个位置的数。根据上面的总结我们只需要修改第 $1$ 个位置的结点的指针指向。那第 $1$ 个位置的结点的指针信息存在哪里呢？答：存在 $ne[0]$。这就是下面代码中 $k?1$ 的原因。

	if (s == 'D') {
		int k;
		cin >> k;
		if (k == 0) head = ne[head];
			else remove(k - 1);
	}

即D k ---> remove(k - 1)。

这里有一个问题：假设我们想删除第 $0$ 个插入的数后面的数，将会输入 D 0 也就是第 1 个位置(头结点)的结点，岂不是要查询 $ne[?1]$，这显然是无法做到的。因此我们要进行特判，当输入D 0 时，我们需要执行 head = ne[head]，即将头指针更新为“头指针指向的结点的指针指向”。有点绕？希望你能参照上面存储信息图进行理解。

我们上面举的例子都是纯插入没有删除的，可是在算法题目中，插入和删除操作都是混合出现的，又因为静态链表中删除结点后不对 $e$ 数组的相应位置进行清空，因此原数组就会很乱。$idx$ 在这里起了大作用，假设我们的单链表插入了两个结点又删除了两个结点，这时链表为空，我们再次插入时应该在哪插入呢？显然不是下标 $0$，不然后序的插入/删除操作都乱了，根据之前的 $idx$，应该在下标为 $2$ 处继续插入，并将头指针指向此，从这里开始建立一段新的链表。

无论是在插入头结点还是删除头结点，都要定义特殊的操作，比如插入头结点为我们定义的函数 tohead，删除头结点为 head = ne[head]。

代码(C++)

// 插入/删除头结点是要定义不同的操作，比如 tohead 和 head = ne[head]。

#include <iostream>

using namespace std;

const int N = 100010;
// idx的作用是指向当前可用的位置
/* 举个例子，当前单链表插入两个结点后又删除掉，
    再次插入时结点应该存储在哪？我想这时 idx = 2，
    即下标为 2 的位置是可用的，可以让head 指向这里，再创建一个单链表
*/
int e[N], ne[N], head, idx;

void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入结点
void tohead(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx; // 头指针指向新插入结点的位置
    idx ++;
}

void add(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx ++;
}

// 需要特判，保证一定是删除的非头指针指向的
void remove(int k)
{
    // 若要在
    ne[k] = ne[ne[k]];
}
int main()
{
    int n;
    cin >> n;
    init();
    for (int i = 0; i < n; i ++)
    {
        char s;
        cin >> s;
        if (s == 'H') {
            int x;
            cin >> x;
            tohead(x);
        }
        if (s == 'D') {
            int k;
            cin >> k;
            // 当删除位置为第 0 个插入的数的后一个数，即头结点
            // 将头指针更新为“头指针指向的结点的指针指向”
            if (k == 0) head = ne[head];
            else remove(k - 1);
        }
        if (s == 'I') {
            int k, x;
            cin >> k >> x;
            // 在第 k 个数后面插入一个结点
            // 只需要修改第 k - 1个结点的指针指向，其存储在 ne[k - 1]
            add(k - 1, x);
        }
    }
    
    // i 根据当前结点的指针域指向下一个结点
    for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
}