为什么需要 Trie？

你有没有想过，手机输入法怎么根据你敲的前几个字母，快速提示出所有可能的单词？搜索引擎又是如何瞬间补全搜索词的？这些功能背后常常有一种叫 Trie（字典树 / 前缀树） 的数据结构。

Trie 把每个单词拆成字符，按字符顺序建成一棵多叉树。从根节点出发，沿着字符路径走，就能判断一个字符串是否存在，或者是否存在以某段字符开头的单词。

和普通查找相比，Trie 的最大优势是：查找时间只和单词长度有关，和字典里有多少单词关系不大。

并查集解决什么问题

假设班上有若干同学，他们之间有一些“朋友关系”。朋友的朋友也是朋友，所以这些人会形成一个一个的小圈子。现在的问题是：

• 给定两个人，他们是不是同一个圈子的？
• 如果让两个人成为朋友，会不会把两个原本不相干的圈子合并成一个？

这种“判断元素是否属于同一集合”以及“合并两个集合”的问题，就是并查集（Union-Find，也叫 Disjoint Set Union，DSU）的专长。

经典应用场景包括：

普通队列按进入顺序出队。优先队列则总是先取优先级最高的元素。二叉堆是实现优先队列的经典结构。

堆不是内存中的“堆区”

这里的 heap 是一种树形数据结构，与 malloc 使用的动态存储区域只是英文同名，概念完全不同。

完全二叉树可以放进数组

最大堆满足：

• 形状是完全二叉树；
• 每个父节点值都不小于孩子。

数组通过整数下标 O(1) 访问，但现实中的键往往是姓名、字符串或其他离散值。哈希表通过哈希函数把键映射到桶下标，在平均情况下实现接近 O(1) 的插入、查找和删除。

哈希函数

哈希函数把任意长度的键转换为整数哈希值：

#include <stddef.h>
#include <stdint.h>

uint64_t hash_string(const char *text) {
    uint64_t hash = UINT64_C(14695981039346656037);
    while (*text != '\0') {
        hash ^= (unsigned char)*text++;
        hash *= UINT64_C(1099511628211);
    }
    return hash;
}

前面已经具体实现了二叉树、二叉搜索树、堆和哈希表。现在进入更一般的关系结构：图。图不要求只有一个根，也不要求每个节点只有固定数量的孩子。

图由什么组成

图由顶点和边组成：

A ---- B
|      |
C ---- D

链表让每个节点指向下一个节点。二叉树让每个节点最多指向两个子节点，于是数据可以形成分支层次。

节点定义

#include <stdlib.h>

typedef struct TreeNode {
    int value;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode *tree_node_create(int value) {
    TreeNode *node = malloc(sizeof(*node));
    if (node == NULL) return NULL;

    node->value = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

二叉搜索树在普通二叉树上增加顺序不变量。对每个节点：

左子树中的值 < 当前值 < 右子树中的值

固定数组访问快、内存连续，但容量在创建后难以改变。动态数组在连续存储的基础上增加自动扩容，是 std::vector 等容器背后的核心思想。

数据结构

#include <stddef.h>

typedef struct {
    int *data;
    size_t size;
    size_t capacity;
} IntVector;

为什么需要链表？

之前我们用数组存一组整数，写起来很直接，但数组有个天生的“倔强”：它的大小在定义时就固定了。如果事先不知道要存多少数据，就得拍脑袋猜一个最大值；要么浪费内存，要么数据塞不下。而且如果要在数组中间插入或删除一个元素，往往要把后面的元素整体搬家，时间开销较大。

链表就是为了解决这些问题而生的：它不必连续占用内存，插入删除时也不需要搬动大量元素，只要改几个指针的指向即可。代价是，它无法像数组那样随机访问第 i 个元素，查找时需要从头节点一步步走。

学习目标

读完本文后，你将能够：

什么是栈？

刷盘子时，最后放上去的盘子会最先被拿走；编辑文档时，最后一步操作最先被撤销。这种“后进先出”（Last In First Out，简称 LIFO）的规则，就是栈的核心思想。

栈是一种只允许在一端进行插入和删除操作的线性表。这一端叫栈顶（top），另一端叫栈底（bottom）。你可以把栈想象成一个只有顶部开口的筒子，东西只能从顶部放进去，也只能从顶部拿出来。

学习目标

读完本文后，你将能够：