算法基础课题解合集

链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

链表的实现过程

本题中要用到三种链表操作：

1. 插入 $x$ 到头结点后

我们只需要让 $hh$ 指针指向新结点的位置，而新节点指向原来 $hh$ 指向的结点。

2. 插入到第 $k$ 个插入的指针的后面

同上，不过是把 $hh$ 指针改成了 $k$ 。

3. 删除第 $k$ 个结点后面的结点

我们只要把 $k$ 的后继改成 $k$ 的后继的后继即可。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int hh, e[N], ne[N], idx;
void addh(int x) {
    e[idx] = x;
    ne[idx] = hh;
    hh = idx ++;
}
void add(int k, int x) {
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx ++;
}
void remove(int k) {
    ne[k] = ne[ne[k]];
}
int main() {
    cin >> n;
    hh = -1;
    while (n --) {
        char c;
        int x, k;
        cin >> c;
        if (c == 'H') {
            cin >> x;
            addh(x);
        } else if (c == 'D') {
            cin >> k;
            if (k == 0) hh = ne[hh];
            else remove(k - 1);
        } else {
            cin >> k >> x;
            add(k - 1, x);
        }
    }
    for (int i = hh; i != -1; i = ne[i])
        cout << e[i] << " ";
    return 0;
}

好啦，这篇题解到这里就结束啦！感谢观看！！！

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$