基础数据结构（一）

前言

本人写作习惯在提供 代码 之后 解释，所以阅读注释时若不理解可以先看看下面的 解释 部分

链表

单链表

介绍

  • 我们使用数组创建一个静态链表，相比结构体+指针的动态链表速度更快。
  • 链表中包含一串相互链接的节点，每个节点中中包含这个节点的值与这个节点所指向的下一个节点的下标。

几种操作

初始化

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

在头节点添加新的节点

1
2
3
4
5
6
void add_to_head(int x) {
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;
}

在第 k 个节点后添加新的节点

1
2
3
4
5
6
void add(int k, int x) {
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}

删除第 k 个节点后的节点

1
2
3
void remove(int k) {
    ne[k] = ne[ne[k]];
}

解释

  1. e[] 用于存储节点的值.
  2. ne[] 用于存储该节点指向的下一个节点的下标.
  3. head 用于存储头节点的下标.
  4. idx 用作指针，指向操作的元素.

双链表

介绍

  • 一个节点存在三个数据: e[] 表示该点的值，l[] 和 r[] 分别表示该点左边与右边的点的下标。

几种操作

初始化

1
2
3
4
5
void init() {
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}
  • 与上面不同，这里不定义 head，使用下标为 0 的点代替 head， 下标为 1 的点表示列表的最后一个空集点。

在第 k 个点的右边插入一个点

1
2
3
4
5
6
7
void add(int k, int x) {
    e[idx] = x;
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx;
}
  • 如果想在第 k 个点的左边插入一个点，无需再创建一个函数，直接使用 add(l[k], x)，表示在第 k 个点左边那个点的右边插入一个点，等同于在第 k 个点的左边插入。

删除第 k 个点

1
2
3
4
void remove(int k) {
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

数组模拟栈和队列

栈

  • 先进后出

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int N = 100010;

// stk[] 存数据，tt 表示队尾
int stk[N], tt;

// 插入
stk[++tt] = x;

// 弹出
tt--;

// 判断栈是否为空
if (tt > 0) not empty
else empty

// 栈顶
stk[tt];

队列

  • 先进先出
  • 从队尾插入，从队头弹出

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int N = 100010;

// q[] 存数据，hh 表示队头，tt 表示队尾
int q[N], hh, tt = -1;

// 插入
q[++tt] = x;

// 弹出
hh++;

// 判断队列是否为空
if (hh <= tt) not empty
else empty

// 取出队头元素
q[hh];

// 取出队尾元素
q[tt];

单调栈和单调队列

单调栈

介绍

  • 最常用的情况，输出每一个数前的第一个比它小的数。
  • 比起传统方法，单调栈可以大幅节省时间。
  • 如果 x 前面的数比它大，先删去那个数，直到找到小于 x 的数，输出它，再插入 x。
  • 这样保证了每一个数前的数都小于它，也就是整个栈是单调递增的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int n;
int stk[N], tt;

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        while (tt && stk[tt] >= x) tt--;
        if (tt) printf("%d ", stk[tt]);
        else printf("-1 ");
        stk[++tt] = x;
    }
    return 0;
}

单调队列

介绍

  • 常用题，求滑动窗口中的最大值和最小值，滑动窗口可用队列维护。
  • 相比传统遍历，这里只把符合条件的数保留在队列中，其余删去，和单调栈类似，最终的队列呈单调递增或递减。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>

using namespace std;

const int N = 1e6 + 10;
int n, k;
// q[] 用于存下标
int a[N], q[N];

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    // 最小值
    int hh = 0, tt = -1;
    for (int i = 0; i < n; i++) {
        // 判断队头是否弹出
        if (hh <= tt && i - k + 1 > q[hh]) hh++;
        // 删除窗口中比 a[i] 大的元素
        while (hh <= tt && a[q[tt]] >= a[i]) tt--;

        // 插入新元素到窗口中
        q[++tt] = i;
        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }
    puts("");

    // 最大值
    hh = 0, tt = -1;
    for (int i = 0; i < n; i++) {
        if (hh <= tt && i - k + 1 > q[hh]) hh++;
        while (hh <= tt && a[q[tt]] <= a[i]) tt--;

        q[++tt] = i;
        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }
    puts("");
    return 0;
}

疑问

为什么使用数组存储下标，而不直接利用 hh / tt 表示下标?

  • hh / tt 是动态变化的队列指针，与原数组下标无直接关联
  • 队列中存储的下标非连续（因弹出操作）
  • 直接使用 hh / tt 会导致：
    • 无法定位原数组元素（如输出时 a[hh] 无意义）
    • 无法判断窗口边界（窗口边界依赖原数组下标）
    • 无法处理值重复的情况（下标是唯一标识）

Trie 字符串

例题

维护一个字符串集合，支持两种操作：

  1. I x 向集合中插入一个字符串 x；
  2. Q x 询问一个字符串在集合中出现了多少次。
    共有 N 个操作，所有输入的字符串总长度不超过 105，字符串仅包含小写英文字母。

输入格式

第一行包含整数 N，表示操作数。

接下来 N 行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。

输出格式

对于每个询问指令 Q x，都要输出一个整数作为结果，表示 x 在集合中出现的次数。

每个结果占一行。

数据范围

1 ≤ N ≤ 2∗10^4

输入样例：

1
2
3
4
5
6
5
I abc
Q abc
Q ab
I ab
Q ab

输出样例：

1
2
3
1
0
1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
using namespace std;

const int N = 1e5 +10;
char str[N];
// son表示子节点，idx是每个节点的索引，cnt记录以该点结尾的单词个数
int son[N][26], cnt[N], idx;

int insert(char str[]) {
    // p表示父节点
    int p = 0;
    for (int i = 0; str[i]; i++) {
        // u表示当前节点，减去'a'可以将字母映射为数字0～25
        int u = str[i] - 'a';
        // 如果子节点不存在，创建子节点（赋予子节点编号idx）
        if(!son[p][u]) son[p][u] = ++idx;
        // 往下一层走
        p = son[p][u];
    }
    
    // 创建完成后，该点结尾的单词数量++
    cnt[p]++;
}

int query(char str[]) {
    int p = 0;
    for (int i = 0; str[i]; i++) {
        int u = str[i] - 'a';
        // 如果不存在子节点，说明该字符串不存在
        if(!son[p][u]) return 0;
        // 否则往下走
        p = son[p][u];
    }
    
    // 返回以该节点结尾的单词数量，也就可以得出出现了多少次该字符串
    return cnt[p];
}

int main() {
    int n;
    scanf("%d", &n);
    while (n--) {
        // scanf 使用 %s 读取字符串时，会存储字符 + 终止符 \0
        char op[2];
        scanf("%s%s", op, str);
        if (op[0] == 'I') insert(str);
        else printf("%d\n", query(str));
    }
    return 0;
}

解释

  • Trie字符串的实现逻辑是从数顶往下走，如果不存在就创建该点，存在则继续往下走。
    例如：abc 这个字符串，最开始 a 不存在， 创建 a，一直创建到 c。这时候添加下一个字符串 abd 的时候，a 和 b 都已经存在，只需在 b 的子节点创建一个 c。
  • 应当在每组字符串的最后一个字母打上标记，确认这里为一个完整字符串的结尾。

并查集

例题

一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。

现在要进行 m 个操作，操作共有两种：

M a b，将编号为 a 和 b 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
Q a b，询问编号为 a 和 b 的两个数是否在同一个集合中；

输入格式

第一行输入整数 n 和 m。

接下来 m 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。

输出格式

对于每个询问指令 Q a b，都要输出一个结果，如果 a 和 b 在同一集合内，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

1 ≤ n, m ≤105

输入样例：

1
2
3
4
5
6
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例：

1
2
3
Yes
No
Yes

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;

const int N = 1e5 + 10;
// p 数组指向该点的父节点的编号
int p[N];

// 寻找 x 的根节点，重要 ！！！
int find(int x) {
    // 如果不为根节点，则令 x 的父节点为父节点的父节点
    // 这样操作之后最终指向的就会是根节点
    if (p[x] != x) p[x] = find(p[x]);

    // 归的过程就是返回根节点的编号，这样该枝所有的数都指向根节点
    return p[x];
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    // 初始化每个节点的父节点的编号为自己的编号
    // 也就是初始时每一个节点都是自己的根节点
    // 换一句话说，只有根节点的父节点是自己
    for (int i = 0; i < n; i++) p[i] = i;
    
    char op[2];
    int a, b;
    while (m--) {
        scanf("%s%d%d", op, &a, &b);
        // 让编号为 a 的数的根节点的父节点为编号 b 的根节点，也就是把 a 接在 b 上
        if (op[0] == 'M') p[find(a)] = find(b);
        else {
            // 如果 a 和 b 的根节点相同， 则在同一个树上
            if (find(a) == find(b)) printf("Yes\n");
            else printf("No\n");
        }
    }
    
    return 0;
}

解释

  • 定义当 p[x] == x 时为根节点。
  • find 函数 “递” 与 “归” 的步骤解析：
    “递”：令每一个点的父节点的编号都为父节点的父节点，最后一步就是第二个点的父节点编号为根节点的父节点（也就是根节点本身）。
    “归”：每一次返回的值都是根节点的编号（第一次归是第二个节点的父节点指向根节点的父节点，第二次归是第三个点的父节点指向第二个点的父节点），最后所有点的父节点都指向根节点的父节点（也就是根节点）。

模拟堆

介绍

  • 堆是一种特殊的完全二叉树数据结构。
  • 特性：
    最大堆（大顶堆）：每个节点的值都大于或等于其子节点的值。
    最小堆（小顶堆）：每个节点的值都小于或等于其子节点的值。
  • 令编号为 u 的点的左子节点编号为 u * 2，右子节点编号为 u * 2 + 1。

例题

维护一个集合，初始时集合为空，支持如下几种操作：

  1. I x，插入一个数 x；
  2. PM，输出当前集合中的最小值；
  3. DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
  4. D k，删除第 k 个插入的数；
  5. C k x，修改第 k 个插入的数，将其变为 x；
    现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。

输入格式

第一行包含整数 N。

接下来 N 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。

输出格式

对于每个输出指令 PM，输出一个结果，表示当前集合中的最小值。

每个结果占一行。

数据范围

1 ≤ N ≤105
−10^9 ≤ x ≤ 10^9
数据保证合法。

输入样例：

1
2
3
4
5
6
7
8
9
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM

输出样例：

1
2
-10
6

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;
int n;
// h 即 heap，存储堆中数据
int h[N];
// ph 记录第 k 个创建的点的编号
// hp 记录该点指向的 ph 数组的下标
int ph[N], hp[N];
// heap_size 记录堆的大小，也就是最后一个点的编号
int heap_size, m;

// 交换函数不是简单的交换，要把映射的变量也交换
void heap_swap(int a, int b) {
    // 交换编号为 a 和 b 的堆指向的 ph 数组(hp[a]是其下标) 所指向的数。
    swap(ph[hp[a]], ph[hp[b]]);
    // 交换编号为 a 和 b 的堆指向的 ph 数组
    swap(hp[a], hp[b]);
    // 交换编号为 a 和 b 的堆中的数
    swap(h[a], h[b]);
}

void down(int u) {
    // t记录最小点的编号
    int t = u;

    // 如果左子节点存在且更小
    if (u * 2 <= heap_size && h[u * 2] < h[t]) t = u * 2;
    // 如果右子节点存在且更小
    if (u * 2 + 1 <= heap_size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    
    // 如果最小的数不是当前数
    if (u != t) {
        // 交换两点
        heap_swap(u, t);
        // 应满足越往上的点越小，如果换下去的数比它的子节点还大，就要再往下走
        down(t);
    }
}

void up(int u) {
    // 确保父节点存在 u / 2 > 0，如果父节点更大，则交换
    while (u / 2 && h[u / 2] > h[u]) {
        heap_swap(u / 2, u);
        // 原先编号为 u 的数被换上去了，这里要保证 u 时刻追踪这个数，直到 up 操作结束
        u /= 2;
    }
}

int main() {
    scanf("%d", &n);
        
    string op;
    while (n--) {
        cin >> op;
        if (op == "I") {
            int x;
            scanf("%d", &x);
            // m 表示第几个插入的数
            m++;
            // heap_size 记录堆的大小，也就是最后一个点的编号
            heap_size++;
            // 插入的时候总是操作最后一个数
            // 让最后一个数指向的 ph 数组的下标为 m，也就是记录了这个数是第几个插入的
            hp[heap_size] = m;
            // 记录第 m 个插入的数的编号为 heap_size
            ph[m] = heap_size;
            // 给该点赋值
            h[heap_size] = x;
            // 让改点往上走，找到自己的位置
            up(heap_size);
        } else if (op == "PM") {
            // 第一个点总是最小的点
            printf("%d\n", h[1]);
        } else if (op == "DM") {
            // 删除第一个点
            // 先将第一个点与最后一个点交换
            heap_swap(1, heap_size);
            // 堆的大小减1，也就是删除了最后一个点
            heap_size--;
            // 再把换上来的这个点 down 下去
            down(1);
        } else if (op == "D") {
            int k;
            scanf("%d", &k);
            // 第 k 个创建的点的编号为 ph[k] 的值
            k = ph[k];
            // 先将该点和最后一个点交换（同理删除第 1 个点）
            heap_swap(k, heap_size);
            // 再删除最后一个点
            heap_size--;
            // 最后把换上来的点 down 下去
            up(k); down(k);
        } else {
            // 最后一个操作：修改第 k 个插入的数，将其变为 x
            int k, x;
            scanf("%d%d", &k, &x);
            // 第 k 个创建的点的编号为 ph[k] 的值 
            k = ph[k];
            // 修改该点的值为 x
            h[k] = x;
            // 实际只会执行 down 或者 up，因为它不可能同时满足 down 的条件（比它的子节点大）又满足 up 的条件（比它的父节点小）
            up(k); down(k);
        }
    }
    
    return 0;
}
Algorithms
基础数据结构（一）
http://www.cactily.me/2025/08/15/基础数据结构（一）/
Author
Cactus
Posted on
August 15, 2025
Licensed under