数据结构模块讲义
本模块包含 单链表、双链表、栈、队列、单调栈、单调队列、KMP、Trie、并查集、堆、哈希表 共 11 个核心数据结构。
1. 单链表 (Single Linked List)
概念与生活比喻
- 数组:就像一排连体别墅,房间号(下标)是连续的。如果想在中间插入一个人,后面的人全得往后搬家,非常麻烦。
- 单链表:就像一串糖葫芦。每个山楂(节点)只管记住下一个山楂是谁。
- 结构:每个节点包含两部分:
val:存的数据。next:指向下一个节点的“指针”(传送门)。
在算法竞赛(如蓝桥杯、ACWing)中,为了追求极致的速度,我们通常不用高级语言自带的指针,而是用静态链表(用数组模拟指针)。
静态链表模板 (C++)
// head 表示头结点的下标
// e[i] 表示节点 i 的值
// ne[i] 表示节点 i 的 next 指针是多少
// idx 用来存储当前已经用到了哪个点
int head, e[N], ne[N], idx;
// 初始化
void init() {
head = -1;
idx = 0;
}
// 在头结点后面插入一个数 x
void add_to_head(int x) {
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
// 将 x 插到下标是 k 的点后面
void add(int k, int x) {
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
// 将下标是 k 的后面的点删掉
void remove(int k) {
ne[k] = ne[ne[k]];
}
2. 双链表 (Double Linked List)
概念
单链表只能单向往前走,如果想知道前面是谁还得从头再来。双链表的每个节点有两个指针:
* l[i]:指向上一个节点(Left)。
* r[i]:指向下一个节点(Right)。
它就像一列双向行驶的火车,每个车厢既知道前面是谁,也知道后面是谁,在中间插入和删除极其方便。
双链表模板 (C++)
int e[N], l[N], r[N], idx;
// 初始化(通常用 0 表示头,1 表示尾)
void init() {
r[0] = 1, l[1] = 0;
idx = 2; // 从 2 开始用
}
// 在节点 k 的右边插入一个数 x
void insert(int k, int x) {
e[idx] = x;
l[idx] = k;
r[idx] = r[k];
l[r[k]] = idx;
r[k] = idx;
idx++;
}
// 删除节点 k
void remove(int k) {
r[l[k]] = r[k];
l[r[k]] = l[k];
}
3. 栈 (Stack)
概念与生活比喻
栈就像一叠盘子,遵循先进后出 (FILO - First In Last Out) 的原则。 * 只能在栈顶(Top)操作。 * 刚洗好的盘子叠在最上面(压栈/Push)。 * 用盘子时只能从最上面拿走(弹栈/Pop)。
栈的实现模板 (C++)
int stk[N], tt = 0; // tt 是栈顶指针(top),初始为 0
// 向栈顶插入一个元素
stk[++tt] = x;
// 弹栈(删除栈顶)
tt--;
// 判断栈是否为空
if (tt == 0) { /* 空 */ }
// 查看栈顶元素
int top_element = stk[tt];
4. 队列 (Queue)
概念与生活比喻
队列就像去食堂排队打饭,遵循先进先出 (FIFO - First In Last Out 的反义词,即 First In First Out) 的原则。 * 两个人:队头(Front)负责出队,队尾(Back)负责入队。 * 先来的人排在前面先打饭,后来的人只能乖乖排在队尾。
队列的实现模板 (C++)
int q[N], hh = 0, tt = -1; // hh 是队头,tt 是队尾
// 向队尾插入一个元素
q[++tt] = x;
// 队头弹出一个元素
hh++;
// 判断队列是否为空
if (hh > tt) { /* 空 */ }
// 查看队头元素
int front_element = q[hh];
5. 单调栈 (Monotonic Stack)
概念与数学证明
- 什么是单调栈? 栈内元素保持单调递增或单调递减的栈。
- 经典问题:给定一个数组,求每个数左边离它最近、比它小的数是谁。如果找不到输出
-1。
暴力做法的时间复杂度分析
如果对每个数都往左遍历一遍,最坏情况下需要比较 $\frac{n(n-1)}{2}$ 次,时间复杂度为 $O(n^2)$。当 $n = 10^5$ 时,计算机会直接超时。
单调栈的优化原理
利用单调栈,我们可以把每个数最多进栈一次、出栈一次。
* 数学证明:假设数组长度为 $n$,每个元素在整个运行过程中最多被 push 进栈 1 次,最多被 pop 出栈 1 次。因此,while 循环内部的操作总执行次数不会超过 $2n$ 次。
* 总时间复杂度直接降为 $O(n)$。
单调栈模板 (C++)
// 求左边第一个比它小的数
int stk[N], tt = 0;
for (int i = 1; i <= n; i++) {
// 如果栈顶元素大于或等于当前数,说明栈顶这家伙太高了,留着没用,弹掉!
while (tt && stk[tt] >= x) tt--;
if (tt) cout << stk[tt] << " "; // 栈顶就是左边第一个比它小的数
else cout << -1 << " "; // 栈空说明没有
stk[++tt] = x; // 当前数入栈
}
6. 单调队列 (Monotonic Queue)
概念与生活比喻
- 场景:滑动窗口最大值。给你一个长度为 $n$ 的数组,和一个大小为 $k$ 的滑动窗口,窗口从左向右滑动,求每次滑动时窗口中的最大值。
- 单调队列的妙处:队列里只存可能成为最大值的“潜力股”的下标,并且保证队列里的下标对应的数值是单调递减的。
队列状态维护过程
- 移出窗口外的人:如果队头的下标已经不在当前窗口范围 $[i - k + 1, i]$ 内了,队头滚蛋(
hh++)。 - 清理比自己小的弱者:新来的数如果比队尾的数大,说明队尾老了又弱,直接从队尾挤出去(
tt--)。 - 入队:新元素下标入队。此时队头永远是当前窗口的最大值。
单调队列模板 (C++)
// q 存的是数组下标
int q[N], hh = 0, tt = -1;
for (int i = 0; i < n; i++) {
// 1. 判断滑出窗口的元素是否需要弹出
if (hh <= tt && q[hh] < i - k + 1) hh++;
// 2. 把队列后面比当前元素小的全部挤出去
while (hh <= tt && a[q[tt]] <= a[i]) tt--;
// 3. 当前元素下标入队
q[++tt] = i;
// 4. 输出窗口最大值(当窗口形成后)
if (i >= k - 1) cout << a[q[hh]] << " ";
}
7. KMP 字符串匹配算法 (Knuth-Morris-Pratt)
概念
- 任务:在文本串 $S$(长)中寻找模式串 $P$(短)第一次出现的位置。
- 核心灵魂:
next数组(也叫前缀函数 $\pi$):next[i]表示:模式串从头开始到第 $i$ 个字符结束的这个子串中,有多长的相同前缀和后缀(不包含字符串本身)。
数学公式与原理图解
假设 $P = \text{"ABA"} $:
* 子串 "A":最长公共前后缀长度为 $0$。
* 子串 "AB":最长公共前后缀长度为 $0$。
* 子串 "ABA":前缀是 "AB" 的话不对,前缀是 "A",后缀也是 "A",长度为 $1$。
当主串匹配失败时,主串指针 $i$ 绝不回退,而是利用 next 数组把模式串指针 $j$ 弹到一个安全的位置:
$$j = \text{next}[j]$$
KMP 核心代码模板 (C++)
// 求 next 数组的过程
for (int i = 2, j = 0; i <= m; i++) {
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j++;
ne[i] = j;
}
// 匹配过程
for (int i = 1, j = 0; i <= n; i++) {
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j++;
if (j == m) {
// 匹配成功!输出起始位置
printf("%d ", i - m);
j = ne[j]; // 继续找下一个匹配
}
}
8. Trie 树(字典树)
概念与图解
Trie 树是一棵专门用来高效存储和查找字符串集合的多叉树。
* 假设我们要存储四个单词:cat, cap, dog, dad。
* 它们有共同的前缀 ca 和 d。在 Trie 树中,公共前缀只存一次。
Root
/ \
c d
| |
a a
/ \ /
t p d
(end)(end)(end)
- 优点:查找一个字符串是否存在,时间复杂度仅仅取决于字符串的长度(例如找长度为 5 的词只需要走 5 步),和字典里总共有多少个词无关!
Trie 树模板 (C++)
// son[p][u] 存储编号为 p 的节点的第 u 个孩子的节点编号
// cnt[p] 记录以当前节点结尾的单词有多少个
int son[N][26], cnt[N], idx;
void insert(char *str) {
int p = 0;
for (int i = 0; str[i]; i++) {
int u = str[i] - 'a';
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]; // 返回这个单词出现了几次
}
9. 并查集 (Disjoint Set)
概念与生活比喻
并查集用来处理“帮派合并”与“查询亲戚”的问题。
* 基本操作:
1. find(x):寻找元素 $x$ 的门派老大(根节点是谁)。
2. union(x, y):把 $x$ 所在的门派和 $y$ 所在的门派合并。
* 核心黑科技:路径压缩:
每次找老大时,顺便把路上的所有小弟直接连到老大头上。这样下次再找老大时,一步到位,时间复杂度几乎为常数 $O(1)$。
并查集模板 (C++)
int p[N]; // 存每个人的父亲是谁
// 找老大 + 路径压缩
int find(int x) {
if (p[x] != x) p[x] = find(p[x]); // 递归找老大,并把路上的人直接挂到老大身上
return p[x];
}
// 初始化:每个人都是自己的老大
for (int i = 1; i <= n; i++) p[i] = i;
// 合并操作:让 y 的老大认 x 的老大当爹
p[find(x)] = find(y);
10. 堆 (Heap)
概念
堆是一棵完全二叉树,分为: * 小根堆:每一个父亲节点的值,都小于或等于它的左右孩子(树根最小)。 * 大根堆:每一个父亲节点的值,都大于或等于它的左右孩子(树根最大)。
核心操作
通常用一维数组模拟完全二叉树:
* 下标为 $x$ 的左孩子是 $2x$,右孩子是 $2x + 1$。
* down(u):如果某个节点变大了,把它“往下沉”到正确位置。
* up(u):如果某个节点变小了,把它“往上浮”到正确位置。
* 可以在 $O(1)$ 时间内拿到最值,在 $O(\log n)$ 时间内插入新元素或删除最值。
11. 哈希表 (Hash Table)
概念
- 问题:如果我们想用一个字符串(如
"xiaoming")作为数组下标来记录分数,普通的数组做不到(数组下标只能是整数)。 - 哈希函数:设计一个数学函数 $H(str)$,把一个大字符串或大整数,通过取模映射到一个较小的整数范围 $[0, N-1]$。
- 哈希冲突:两个不同的字符串通过公式算出来可能是一个数字。
- 解决方法:
- 拉链法:在发生冲突的数组位置挂一条单链表,把冲突的元素串起来。
- 开放寻址法:如果那个位置被占了,顺着往后面找空位。
哈希表示例(拉链法 C++)
int h[N], e[N], ne[N], idx;
void insert(int x) {
int k = (x % N + N) % N; // 防止负数取模
e[idx] = x;
ne[idx] = h[k];
h[k] = idx++;
}
bool find(int x) {
int k = (x % N + N) % N;
for (int i = h[k]; i != -1; i = ne[i]) {
if (e[i] == x) return true;
}
return false;
}
—— 本文来自火龙信奥(义乌睿码科技):义乌青少年信息学奥赛与编程教育平台,专注 CSP-J/S、NOIP、GESP 竞赛培训,线上线下融合教学,助力编程升学。网址:hlcoding.com