火龙信奥
  • 分享
  • 课程
  • 在线题库
  • CSES
    • GESP
    • CSP
  • 打卡
    • 代码对战
    • 快速对战
  • 题单
  • 知识课堂
  • 在线比赛
  • 团队
  • 荣誉墙
  • 商城
  • 登录 / 注册

数据结构模块讲义

作者: 作者的头像   huolong , 时间:2026-09-25 15:09:48 , 所有人可见, 阅读  30

数据结构模块讲义

本模块包含 单链表、双链表、栈、队列、单调栈、单调队列、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$ 的滑动窗口,窗口从左向右滑动,求每次滑动时窗口中的最大值。
  • 单调队列的妙处:队列里只存可能成为最大值的“潜力股”的下标,并且保证队列里的下标对应的数值是单调递减的。

队列状态维护过程

  1. 移出窗口外的人:如果队头的下标已经不在当前窗口范围 $[i - k + 1, i]$ 内了,队头滚蛋(hh++)。
  2. 清理比自己小的弱者:新来的数如果比队尾的数大,说明队尾老了又弱,直接从队尾挤出去(tt--)。
  3. 入队:新元素下标入队。此时队头永远是当前窗口的最大值。

单调队列模板 (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

关于火龙

  • 关于我们
  • 学员获奖
  • 预约试听
  • ACM课程
  • CSP课程
  • 学习指南

帮助中心

  • 用户协议
  • 打字练习 HOT
  • 在线画图
  • DevC++下载
  • CSP报名
  • GESP官网

推荐课程

  • C++零基础入门(可试看)
  • C++进阶提升
  • GESP考级辅导
  • GESP打卡
  • CSP-J/S打卡

公众号

火龙信奥公众号二维码

© 2017-2026 义乌市睿码科技有限公司版权所有 浙ICP备2021013995号

火龙信奥
请输入登录信息


请完成安全验证
验证码底图 滑块
向右拖动滑块完成验证
请输入用户名 / 绑定的手机号码



请输入注册信息(手机号验证码注册)





验证码5分钟有效,60秒内不可重复获取,每日最多3次

微信登录

微信登录二维码

正在生成二维码...

账号已过期,请续期。
去续期

绑定手机号

📱

为了更好地保护您的账号安全,享受完整的平台服务

请您尽快绑定手机号码