数据结构演示教程：按 8 类结构建立全景图

目标：用截图中的分类方式讲清数据结构，而不是把 Heap、Skip List、Bloom Filter、LRU Cache 放错章节。

开场 Hook（0:00 - 0:20）

旁白

数据结构不是一串名字，而是一张分类地图。 今天按 8 类来整理：基础存储结构、线性 ADT、树结构、Hash 结构、图、集合维护、概率 / 高级索引、组合型工程结构。 先把位置放对，再谈复杂度和使用场景。

第一章 · 分类总览（0:20 - 1:10）

Screen

展示分类表。

Narration

这张图的关键是边界：数组和链表是基础存储；栈、队列、双端队列是线性 ADT；Heap 属于树；Hash 结构只放 HashMap 和 HashSet；Bloom Filter 和 Skip List 是概率 / 高级索引；LRU Cache 是组合结构。

第二章 · 基础存储结构（1:10 - 2:20）

Demo 2.1 · Array 数组

Command

arr = [10, 20, 30, 40, 50]
print(arr[2])
arr.insert(2, 99)
print(arr)

Output

30
[10, 20, 99, 30, 40, 50]

Narration

数组像编号固定的快递柜，知道下标就能 O(1) 直接取。中间插入时，后面的元素要整体后移，所以是 O(n)。

Demo 2.2 · Linked List 链表

Diagram

单链表:
HEAD -> [A|next] -> [B|next] -> [C|null]

双链表:
NULL <- [prev|A|next] <-> [prev|B|next] <-> [prev|C|next] -> NULL

Narration

链表不要求连续内存。单链表只知道下一个节点；双链表知道前后节点，所以 LRU 这类需要频繁移动节点的结构会用双链表。

第三章 · 线性 ADT（2:20 - 3:20）

Demo 3.1 · Stack 栈

Command

stack = [1, 2, 3]
stack.append(4)
print(stack.pop())

Output

4

Narration

栈是后进先出，像一摞盘子。撤销操作、函数调用栈、括号匹配都用它。

Demo 3.2 · Queue 队列

Diagram

出队 <- [A][B][C][D][E] <- 入队
        队首            队尾

A 最先进入，所以 A 最先从队首出去。

Command

from collections import deque

queue = deque(["A", "B", "C"])
queue.append("D")       # 队尾入队
print(queue.popleft())  # 队首出队
print(list(queue))

Output

A
['B', 'C', 'D']

Narration

这里箭头必须画对：队尾入队，队首出队。旧图写成左边入队、右边出队，会把 FIFO 的方向讲反。

Demo 3.3 · Deque 双端队列

Command

from collections import deque

dq = deque([1, 2, 3])
dq.appendleft(0)
dq.append(4)
print(list(dq))
print(dq.popleft(), dq.pop())

Output

[0, 1, 2, 3, 4]
0 4

Narration

双端队列两端都能进出，滑动窗口、回文检查、单调队列都常用它。

第四章 · 树结构（3:20 - 5:50）

Binary Tree / BST / AVL / Red-Black Tree

Diagram

Binary Tree:              BST:
      [root]                  [50]
      /    \                 /    \
   [L]    [R]             [30]    [70]
                            \       \
                            [40]    [80]

Narration

Binary Tree 是基础层级模型。BST 加入左小右大的有序规则。AVL 和 Red-Black Tree 是平衡 BST，避免顺序插入后退化成链表。

Heap 堆

Diagram

MIN HEAP
          [1]        <- 堆顶最小
        /     \
      [3]     [5]
     /  \    /  \
   [7] [9] [8] [12]

Narration

Heap 要放在树结构里。它通常是完全二叉树，用来快速拿最大值或最小值，不是 Hash 结构。

Trie 字典树

Diagram

root
 |- c - a |- t  (cat)
 |       |- r  (car)
 |- d - o |- g  (dog)
         |- or (door)

Narration

Trie 是前缀树，适合搜索补全、敏感词匹配、IP 路由最长前缀匹配。

Segment Tree / Fenwick Tree

Narration

Segment Tree 和 Fenwick Tree 也归在树结构。它们都服务于区间或前缀统计：线段树更通用，树状数组更轻量。

第五章 · Hash 结构（5:50 - 6:40）

Demo 5.1 · HashMap / HashSet

Command

profile = {"name": "Ada", "city": "Shanghai"}
print(profile["name"])

seen = set(["A", "B", "A"])
print(seen)
print("A" in seen)

Output

Ada
{'A', 'B'}
True

Narration

HashMap 存 key-value，HashSet 只存 key。它们才是 Hash 结构这一类的主体。Bloom Filter 虽然用哈希函数，但分类上放到概率 / 高级索引更准确。

第六章 · 图（6:40 - 7:30）

邻接矩阵 vs 邻接表

Diagram

邻接矩阵:
    0 1 2 3
0 [0 1 0 1]
1 [1 0 1 1]
2 [0 1 0 0]
3 [1 1 0 0]

邻接表:
0: [1, 3]
1: [0, 2, 3]
2: [1]
3: [0, 1]

Narration

邻接矩阵判断边是 O(1)，适合稠密图。邻接表只存实际存在的边，空间 O(V+E)，适合稀疏图和 BFS/DFS。

第七章 · 集合维护（7:30 - 8:10）

Demo 7.1 · Union-Find

Command

parent = list(range(5))

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

def union(a, b):
    parent[find(a)] = find(b)

union(1, 2)
union(2, 3)
print(find(1) == find(3))
print(find(1) == find(4))

Output

True
False

Narration

Union-Find 是集合维护结构，只回答两个元素是否属于同一个集合。连通块、最小生成树、账号合并都常用它。

第八章 · 概率 / 高级索引（8:10 - 9:10）

Bloom Filter

Narration

Bloom Filter 用多个哈希函数写入位数组。它能用很小空间判断“可能存在”或“一定不存在”，允许误判存在，但不会误判不存在。

add("hello"):
h1 -> bit[1] = 1
h2 -> bit[4] = 1
h3 -> bit[7] = 1

query("world"):
只要任意一位是 0 -> 一定不存在

Skip List

Narration

Skip List 是有序链表加多层索引，不是线性 ADT。它用高层索引跳过大段节点，查找、插入、删除期望 O(log n)。

L3: HEAD ----------------> [50] ------> NULL
L2: HEAD --------> [30] -> [50] ------> NULL
L1: HEAD -> [10] -> [30] -> [50] -> [70] -> NULL
L0: HEAD -> [10] -> [20] -> [30] -> [40] -> [50] -> [60] -> [70]

第九章 · 组合型工程结构（9:10 - 9:50）

LRU Cache

Diagram

LRU Cache = HashMap + Doubly Linked List

HashMap:
  key -> linked-list node

Doubly Linked List:
  HEAD <-> [recent] <-> [older] <-> TAIL

Narration

LRU Cache 不应该直接放到 Hash 结构里。它依赖 HashMap 做 O(1) 定位，也依赖双向链表做 O(1) 顺序维护，是组合型工程结构。

课程总结（9:50 - 10:00）

旁白

今天的重点是把分类放对：Heap 属于树结构；Bloom Filter 和 Skip List 属于概率 / 高级索引；LRU Cache 属于组合型工程结构；Hash 结构只放 HashMap 和 HashSet。 分类对了，后面讲复杂度、讲实现、讲工程组合才不会乱。

录制作业清单

• 分类与参考图一致。
• Queue 图为“队首出队、队尾入队”。
• 不再出现旧数量口径。
• 不再把 Heap 放进 Hash 结构。
• 不再把 Skip List 放进线性 ADT。
• 不再把 LRU Cache 当成单一 Hash 结构。