算法笔记:AcWing - 数据结构

算法笔记:AcWing - 数据结构

Ginkgo True love prevails.

数组模拟和 STL 两种写法都建议掌握:数组模拟更贴近竞赛底层实现,速度快、可控性高;STL 写法更简洁,日常刷题和工程代码更高效。这篇按”场景驱动”的思路整理,帮你快速定位该用什么。


一、链表:什么时候不用 vector

核心问题

vector 虽然方便,但中间插入/删除需要移动后面所有元素,复杂度 。链表的优势在于:知道位置后,插入删除都是 。

但要注意:链表查找第 k 个元素是 ,这点不如 vector 的 随机访问。


数组模拟单链表(竞赛常用)

为什么用数组模拟而不是指针?

  • 避免动态内存分配的开销
  • 内存连续,缓存友好
  • 不会内存泄漏
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
const int N = 100010;
int head, e[N], ne[N], idx;

void init() {
head = -1; // -1 表示空
idx = 0;
}

// 头插法
void add_to_head(int x) {
e[idx] = x;
ne[idx] = head;
head = idx++;
}

// 在下标为 k 的节点后插入
void add(int k, int x) {
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx++;
}

// 删除下标为 k 的节点后面的节点
void remove(int k) {
ne[k] = ne[ne[k]];
}

遍历方式:

1
2
3
for (int i = head; i != -1; i = ne[i]) {
cout << e[i] << ' ';
}

数组模拟双链表

场景:需要在任意位置前后都能快速插入/删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int N = 100010;
int e[N], l[N], r[N], idx;

void init() {
// 0 是左端点,1 是右端点,实际数据从下标 2 开始
r[0] = 1; l[1] = 0;
idx = 2;
}

// 在 k 右侧插入 x
void add(int k, int x) {
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;
r[k] = idx++;
}

// 删除 k 节点
void remove(int k) {
r[l[k]] = r[k];
l[r[k]] = l[k];
}

小技巧:要在 k 左侧插入,等价于在 l[k] 右侧插入,调用 add(l[k], x) 即可。


邻接表:存图的标配

场景:存图,尤其是稀疏图(边数远小于 )。

核心思想:每个点的所有出边连成一条链。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const int N = 100010, M = 200010;  // M 是边数,无向图要开 2 倍
int h[N], e[M], ne[M], idx;

void add(int a, int b) { // 加一条 a->b 的边
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}

// 遍历 u 的所有出边
for (int i = h[u]; i != -1; i = ne[i]) {
int v = e[i];
// 处理边 u->v
}

带权图:加一个 w[M] 数组存边权即可。

链式前向星:用数组模拟链表来存图

这部分很容易和“数组模拟链表”串起来理解:

  • head[u] 存点 u 的第一条边下标
  • Edge.next 把同一起点的边串成一条“下标链表”
  • 遍历时从 head[u] 出发,沿 next 一直走到 -1

所以从实现角度看,链式前向星本质上就是“数组模拟链表 + 图的邻接表”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int N = 100010, M = 200010;
struct Edge {
int to, w, next;
} edge[M];

int head[N], idx;

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

void add(int u, int v, int w) {
edge[idx] = {v, w, head[u]};
head[u] = idx++;
}

// 遍历以 u 为起点的所有边
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
int w = edge[i].w;
// 处理边 u -> v (权重 w)
}

二、栈与队列:受限的线性表

栈(LIFO:后进先出)

典型场景:

  • 表达式求值
  • 括号匹配
  • DFS 递归的迭代实现
  • 单调栈(见下文)
1
2
3
4
5
6
7
8
9
10
11
// 数组模拟
int stk[N], tt = 0;
stk[++tt] = x; // 入栈
tt--; // 出栈
int top = stk[tt]; // 栈顶

// STL
stack<int> stk;
stk.push(x);
stk.pop();
stk.top();

队列(FIFO:先进先出)

典型场景:

  • BFS
  • 层次遍历
  • 滑动窗口(用单调队列优化)
1
2
3
4
5
6
7
8
9
10
11
12
// 数组模拟
int q[N], hh = 0, tt = -1;
q[++tt] = x; // 入队
hh++; // 出队
int front = q[hh], back = q[tt];

// STL
queue<int> q;
q.push(x);
q.pop();
q.front();
q.back();

三、单调队列与单调栈:优化的艺术

单调队列 —— 滑动窗口最值

问题:有一个长度为 n 的数组,和一个大小为 k 的滑动窗口,求每个窗口位置的最小值/最大值。

朴素做法:每个窗口遍历 k 个元素,复杂度 。

单调队列优化:维护一个”可能成为答案的候选下标”的队列,复杂度降到 。

核心直觉:

  • 如果一个数比后面的数大(求最小值时),它永远不可能成为答案,可以扔掉
  • 队头超出窗口范围时,要弹出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 滑动窗口最小值
deque<int> q; // 存下标
for (int i = 0; i < n; i++) {
// 1. 队头超出窗口
if (!q.empty() && q.front() < i - k + 1)
q.pop_front();

// 2. 维护单调性(最小值用单调递增)
while (!q.empty() && a[q.back()] >= a[i])
q.pop_back();

// 3. 入队
q.push_back(i);

// 4. 输出答案(窗口形成后)
if (i >= k - 1)
cout << a[q.front()] << ' ';
}

为什么队头就是答案:队头是窗口内最小的元素的下标,而且是最靠左的(如果有多个相同最小值)。


单调栈 —— 找”第一个比它大/小”的数

典型问题:

  • 每个数左边第一个比它小的数
  • 柱状图中最大矩形
  • 接雨水

核心直觉:维护一个单调栈,当前元素入栈前,把”挡路”的元素都弹掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 找每个数左边第一个比它小的数
stack<int> st; // 存下标
for (int i = 0; i < n; i++) {
while (!st.empty() && a[st.top()] >= a[i])
st.pop();

if (st.empty())
cout << -1 << ' '; // 左边没有比它小的
else
cout << a[st.top()] << ' ';

st.push(i);
}

变式:找右边第一个比它大的数,从右往左遍历即可。


四、KMP:字符串匹配的高效算法

问题背景

给定主串 S 和模式串 P,找 P 在 S 中出现的所有位置。

暴力做法:每个位置尝试匹配,失配后主串回退,复杂度 。

KMP 的核心:失配时,主串不回退,只移动模式串。移动多少位由模式串自身的结构决定。


next 数组(或称 ne 数组)

ne[i] 的含义:模式串前 i 个字符中,最长相等前后缀的长度。

举个例子,p = "abab":

  • ne[1] = 0(”a”,没有真前后缀)
  • ne[2] = 0(”ab”,前后缀不相等)
  • ne[3] = 1(”aba”,前后缀都是”a”)
  • ne[4] = 2(”abab”,前后缀都是”ab”)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 求 next 数组(1 下标)
for (int i = 2, j = 0; i <= n; i++) {
while (j && p[i] != p[j + 1])
j = ne[j];
if (p[i] == p[j + 1])
j++;
ne[i] = j;
}

// KMP 匹配
for (int i = 1, j = 0; i <= m; i++) {
while (j && s[i] != p[j + 1])
j = ne[j];
if (s[i] == p[j + 1])
j++;
if (j == n) {
// 匹配成功,起点是 i - n + 1
j = ne[j]; // 继续找下一个匹配
}
}

时间复杂度:,主串和模式串各遍历一遍。


五、Trie 树:字符串的专属数据结构

核心思想

把字符串拆成字符,按字符建一棵多叉树。从根到某个节点的路径就是一个字符串。

优势:

  • 前缀查询极快
  • 统计某个字符串出现次数
  • 找异或最大值(01 Trie)

基础模板:统计字符串出现次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const int N = 100010;
int son[N][26], cnt[N], idx = 0;
// son[p][u]: 节点 p 沿字符 u 的儿子编号
// cnt[p]: 以节点 p 结尾的单词数量

void insert(const string& str) {
int p = 0; // 从根节点开始
for (char ch : str) {
int u = ch - 'a';
if (!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
cnt[p]++; // 标记结尾
}

int query(const string& str) {
int p = 0;
for (char ch : str) {
int u = ch - 'a';
if (!son[p][u]) return 0; // 不存在
p = son[p][u];
}
return cnt[p];
}

01 Trie:求最大异或对

问题:给定 n 个数,找两个数使它们的异或值最大。

核心直觉:异或值想最大,高位尽量变成 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
int son[N * 31][2], idx = 0;

void insert(int x) {
int p = 0;
for (int i = 30; i >= 0; i--) { // 从高位到低位
int c = (x >> i) & 1;
if (!son[p][c]) son[p][c] = ++idx;
p = son[p][c];
}
}

int query(int x) {
int p = 0, res = 0;
for (int i = 30; i >= 0; i--) {
int c = (x >> i) & 1;
int rev = 1 - c; // 希望走的相反位
if (son[p][rev]) {
res |= (1 << i); // 这一位能变成 1
p = son[p][rev];
} else {
p = son[p][c]; // 只能走相同位
}
}
return res;
}

用法:边插入边查询,每次用当前数查询已插入的数中的最大异或值。


六、并查集:处理集合合并与查询

核心问题

  • 合并两个集合
  • 查询两个元素是否在同一集合

典型场景:

  • 图的连通性
  • 最小生成树(Kruskal)
  • 亲戚关系传递

基础模板:路径压缩 + 按大小合并

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
struct DSU {
vector<int> fa, sz;

DSU(int n) {
fa.resize(n + 1);
sz.assign(n + 1, 1);
iota(fa.begin(), fa.end(), 0); // fa[i] = i
}

int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]); // 路径压缩
}

void unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (sz[x] < sz[y]) swap(x, y); // 小树挂大树
fa[y] = x;
sz[x] += sz[y];
}

bool same(int x, int y) {
return find(x) == find(y);
}
};

为什么按大小合并:避免树退化成链,保证 find 的复杂度接近 (实际上是反阿克曼函数)。


扩展:维护到根的距离

场景:不仅要判断连通性,还要知道点与点之间的关系(如”食物链”题中的捕食关系)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct DSUWithDist {
vector<int> fa, dist;
// dist[x]: x 到 fa[x] 的距离(或关系值)

DSUWithDist(int n) {
fa.resize(n + 1);
dist.assign(n + 1, 0);
iota(fa.begin(), fa.end(), 0);
}

int find(int x) {
if (fa[x] == x) return x;
int p = fa[x];
fa[x] = find(fa[x]); // 路径压缩
dist[x] += dist[p]; // 同步更新距离
return fa[x];
}
};

七、堆:动态维护最值

核心能力

  1. 插入一个数
  2. 查询最值
  3. 删除最值

STL 的局限:priority_queue 不支持删除任意元素或修改任意元素。需要这些功能时要手写堆。


手写堆模板(支持任意位置操作)

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
const int N = 100010;
int h[N], hp[N], ph[N], sz = 0;
// h[i]: 堆中位置 i 的值
// hp[i]: 堆位置 i 对应的插入编号
// ph[k]: 第 k 个插入的元素在堆中的位置

void heap_swap(int a, int b) {
swap(ph[hp[a]], ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}

void down(int u) {
int t = u;
if (u * 2 <= sz && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= sz && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t) {
heap_swap(u, t);
down(t);
}
}

void up(int u) {
while (u / 2 && h[u / 2] > h[u]) {
heap_swap(u / 2, u);
u /= 2;
}
}

// 插入
h[++sz] = x;
up(sz);

// 删除堆顶
heap_swap(1, sz);
sz--;
down(1);

// 删除第 k 个插入的元素
int pos = ph[k];
heap_swap(pos, sz);
sz--;
down(pos);
up(pos);

// 修改第 k 个插入的元素
h[ph[k]] = x;
down(ph[k]);
up(ph[k]);

建堆

直接从 n/2 开始向前 down,因为叶子节点不用调整。

1
2
for (int i = n / 2; i >= 1; i--)
down(i);

八、哈希表:O(1) 的查找

核心问题

  • 哈希函数怎么设计
  • 冲突怎么处理

拉链法

思路:每个桶挂一条链表,冲突的元素串起来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int MOD = 10000019;  // 取个大质数
const int N = 200000 + 10;
int h[MOD], e[N], ne[N], idx;

void init() {
memset(h, -1, sizeof h);
idx = 0;
}

void insert(int x) {
int k = (x % MOD + MOD) % MOD; // 处理负数
e[idx] = x;
ne[idx] = h[k];
h[k] = idx++;
}

bool find(int x) {
int k = (x % MOD + MOD) % MOD;
for (int i = h[k]; i != -1; i = ne[i])
if (e[i] == x) return true;
return false;
}

开放寻址法

思路:只开一个数组,冲突就往后找空位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int MOD = 200003;
const int NULL_VAL = 0x3f3f3f3f;
int h[MOD];

void init() {
memset(h, 0x3f, sizeof h);
}

int find_pos(int x) {
int k = (x % MOD + MOD) % MOD;
while (h[k] != NULL_VAL && h[k] != x) {
k++;
if (k == MOD) k = 0; // 循环
}
return k;
}

对比:

  • 拉链法:稳定,装载因子可以>1
  • 开放寻址:常数小,但装载因子高了性能下降快

九、字符串哈希:快速判断子串相等

核心思想

把字符串看成 P 进制数,计算前缀哈希。判断两段子串是否相等,只需比较哈希值。

经验取值:

  • P = 131 或 13331
  • Q = 2^64(用 unsigned long long 自然溢出)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
using ULL = unsigned long long;
const int N = 100010;
char str[N];
ULL h[N], p[N]; // h: 前缀哈希,p: P 的幂次

// 计算子串 [l, r] 的哈希(1 下标)
ULL get(int l, int r) {
return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
scanf("%s", str + 1);
int n = strlen(str + 1);

p[0] = 1;
for (int i = 1; i <= n; i++) {
p[i] = p[i - 1] * 131;
h[i] = h[i - 1] * 131 + str[i];
}

// 判断 [l1, r1] 和 [l2, r2] 是否相等
if (get(l1, r1) == get(l2, r2))
puts("相等");
}

和 KMP 的对比:

  • 字符串哈希:适合”子串相等判断”,写法灵活
  • KMP:适合”模式匹配 + 前后缀分析”,更体系化

十、STL 速记

vector

1
2
3
4
v.size(), v.empty(), v.clear()
v.push_back(x), v.pop_back()
v.erase(v.begin() + k)
sort(v.begin(), v.end())

string

1
2
3
s.size(), s.length(), s.c_str()
s.substr(pos, len)
s += "abc"

set / map

1
2
3
4
s.insert(x), s.erase(x)
s.lower_bound(x) // >= x 的第一个
s.upper_bound(x) // > x 的第一个
mp[key] = value

priority_queue

1
2
priority_queue<int> max_heap;  // 大根堆
priority_queue<int, vector<int>, greater<int>> min_heap; // 小根堆

常用算法

1
2
3
4
5
6
lower_bound(a.begin(), a.end(), x)
upper_bound(a.begin(), a.end(), x)
binary_search(a.begin(), a.end(), x)
unique(a.begin(), a.end())
next_permutation(a.begin(), a.end())
__gcd(a, b)

小结:什么时候用什么

需求 推荐数据结构
随机访问 + 尾部操作 vector
中间插入/删除 链表
后进先出 栈
先进先出 队列
滑动窗口最值 单调队列
找第一个比它大/小 单调栈
字符串前缀查询 Trie
集合合并查询 并查集
动态最值 堆
O(1) 查找 哈希表
子串相等判断 字符串哈希

理解每种结构的核心优势和代价,比死记模板重要得多。

  • Title: 算法笔记:AcWing - 数据结构
  • Author: Ginkgo
  • Created at : 2026-04-09 20:00:00
  • Updated at : 2026-04-26 21:33:40
  • Link: https://g1nkgo7.github.io/2026/04/09/算法笔记-AcWing-数据结构/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments