数据结构概览

---

第一章：线性表 (Linear List)

线性表是 $n$ 个数据元素的有限序列。

1. 顺序表 (Array) vs 链表 (Linked List)

维度	顺序表 (Array)	链表 (Linked List)
物理结构	内存地址连续	内存地址离散，通过指针链接
随机访问	支持，$O(1)$	不支持，需遍历，$O(n)$
插入/删除	需移动大量元素，$O(n)$	修改指针即可，$O(1)$ (需知位置)
空间分配	静态分配易溢出，动态分配需扩容	动态分配，无溢出问题
存储密度	高 (1.0)	低 (需存指针域)

• 核心考点：
  • 顺序表地址计算：$Loc(a_i) = Loc(a_0) + i \times d$。
  • 链表头结点：引入头结点是为了统一空表和非空表的操作，以及第一个结点的插入删除操作。
  • 双链表：删除节点 $p$ 时，需同时修改 p->prior 和 p->next 相关的指针，防止断链。

---

第二章：栈与队列 (Stack & Queue)

1. 基础特性与复杂度

所有基本操作（进出栈、入出队、判空）的时间复杂度均为 $O(1)$。

结构	特性	典型应用
栈 (Stack)	后进先出 (LIFO)	递归、括号匹配、表达式求值、DFS
队列 (Queue)	先进先出 (FIFO)	缓冲区、层序遍历、BFS

2. 核心公式与考点

• 出栈序列计数 (卡特兰数)：$n$ 个元素进栈，合法出栈序列数为 $\frac{1}{n+1} C_{2n}^n$。
• 循环队列 (Circular Queue)：
  • 解决“假溢出”问题，牺牲一个单元区分空/满。
  • 队空：front == rear
  • 队满：(rear + 1) % MaxSize == front
  • 队列长度：(rear - front + MaxSize) % MaxSize

---

第三章：串 (String)

主要考察模式匹配算法（主串长 $n$，模式串长 $m$）。

算法	平均时间复杂度	最坏时间复杂度	空间复杂度	特点
暴力匹配 (BF)	$O(n+m)$	$O(n \times m)$	$O(1)$	简单，但回溯导致效率低
KMP算法	$O(n+m)$	$O(n+m)$	$O(m)$	主串指针不回溯，依赖 next 数组

• KMP核心：利用匹配失败后的信息（部分匹配表 next），将模式串向右滑动尽可能远的距离。

---

第四章：树与二叉树 (Tree)

1. 二叉树性质 (必考计算)

1. 节点数关系：$n_0 = n_2 + 1$ （叶子节点数 = 度为2节点数 + 1）。
2. 层级关系：第 $i$ 层至多 $2^{i-1}$ 个节点；深度 $k$ 至多 $2^k - 1$ 个节点。
3. 完全二叉树：
   • 编号为 $i$ 的节点：左孩子 $2i$，右孩子 $2i+1$，父节点 $\lfloor i/2 \rfloor$。
   • 具有 $n$ 个节点的完全二叉树深度为 $\lfloor \log_2 n \rfloor + 1$。

2. 操作复杂度

设树的节点数为 $n$，树的高度为 $h$。

操作	复杂度	备注
遍历 (前/中/后/层)	$O(n)$	必须访问每个节点一次
二叉搜索树 (BST) 查找	$O(h)$	最好 $O(\log n)$，最坏 $O(n)$ (退化成链表)
平衡二叉树 (AVL) 查找	$O(\log n)$	强制 $h \approx \log n$
堆 (Heap) 建立	$O(n)$	筛选法建堆是线性的
堆 (Heap) 插入/删除	$O(\log n)$	需要向上/向下调整

• AVL树性质：任意节点左右子树高度差绝对值 $\le 1$。
• 哈夫曼树 (Huffman)：带权路径长度 (WPL) 最小。只有度为0和2的节点，没有度为1的节点。

---

第五章：图 (Graph)

$V$ = 顶点数，$E$ = 边数。

1. 存储结构对比

存储方式	空间复杂度	适用场景	查边效率 (判两点相连)
邻接矩阵	$O(V^2)$	稠密图 ($E \approx V^2$)	$O(1)$
邻接表	$O(V+E)$	稀疏图 ($E \ll V^2$)	$O(Degree(V))$

2. 图算法复杂度

注意：算法的时间复杂度通常取决于存储结构。

算法	功能	邻接矩阵时间	邻接表时间	辅助空间
DFS	深度遍历	$O(V^2)$	$O(V+E)$	$O(V)$ (递归栈)
BFS	广度遍历	$O(V^2)$	$O(V+E)$	$O(V)$ (队列)
Prim	最小生成树	$O(V^2)$	$O(E \log V)$	$O(V)$
Kruskal	最小生成树	-	$O(E \log E)$	$O(V)$
Dijkstra	单源最短路	$O(V^2)$	$O(E \log V)$	$O(V)$
Floyd	多源最短路	$O(V^3)$	-	$O(V^2)$
拓扑排序	无环检测	$O(V^2)$	$O(V+E)$	$O(V)$

• 总结：稠密图用矩阵（Prim, Dijkstra），稀疏图用表（Kruskal, 优化版Dijkstra）。

---

第六章：查找 (Search)

1. 核心对比

查找方法	平均时间	最坏时间	空间	备注
顺序查找	$O(n)$	$O(n)$	$O(1)$	无序表唯一选择
二分查找	$O(\log n)$	$O(\log n)$	$O(1)$	仅限有序顺序表
分块查找	$O(\sqrt{n})$	$O(\sqrt{n})$	$O(\sqrt{n})$	块间有序，块内无序
哈希查找	$O(1)$	$O(n)$	$O(n)$	效率取决于散列函数和装填因子

2. B树与B+树 (多路查找树)

• 主要用于磁盘文件系统和数据库索引。
• 操作复杂度均为 $O(\log_m n)$ ($m$为阶数)，通过减少树高来减少磁盘I/O次数。
• B+树区别：数据全在叶子节点，叶子节点连成链表（适合范围查询）。

---

第七章：排序 (Sort) - 终极表格

$n$: 数据量, $d$: 位数, $k$: 范围。

类别	算法	平均时间	最坏时间	空间	稳定性	核心特点
插入类	直接插入	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	序列越有序越快 (最好 $O(n)$)
	希尔排序	$O(n^{1.3})$	$O(n^2)$	$O(1)$	不稳定	插入排序的改进版 (缩小增量)
交换类	冒泡排序	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	每一趟确定一个最值
	快速排序	$O(n \log n)$	$O(n^2)$	$O(\log n)$	不稳定	平均性能最快；有序时退化
选择类	简单选择	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定	比较次数恒定，与初始状态无关
	堆排序	$O(n \log n)$	$O(n \log n)$	$O(1)$	不稳定	适合Top K问题；空间最省的 $n \log n$ 排序
归并类	归并排序	$O(n \log n)$	$O(n \log n)$	$O(n)$	稳定	效率高且稳定，但费空间
其他	基数排序	$O(d(n+k))$	$O(d(n+k))$	$O(k)$	稳定	不基于比较，基于分配收集

记忆口诀

1. 不稳定：快、希、选、堆。
2. 时间 $O(n \log n)$：快、归、堆。
3. 最坏退化 $O(n^2)$：快、希、插、冒、选。
4. 空间 $O(1)$：插、希、冒、选、堆。

---

备考 避坑指南

1. 快排的最坏情况：当数组原本有序（或逆序）时，快排退化为冒泡排序，时间 $O(n^2)$，空间 $O(n)$（递归栈）。
2. Top K 问题选谁？：选堆排序。因为只需要维护一个大小为 K 的堆，不需要对所有数据全局排序。
3. 为什么数据库不用二叉平衡树而用B+树？：因为B+树层级更少，且节点大小利用率高，极大减少了机械硬盘的寻道时间（I/O）。
4. 哈希表的 $O(1)$ 是绝对的吗？：不是。发生哈希冲突时会退化，极端情况下（所有元素哈希值相同）退化为链表查询 $O(n)$。