一、绪论
– 数据结构三要素：逻辑结构、存储结构、运算
– 逻辑结构
– 线性：线性表、栈、队列、串
– 非线性：树、图、集合
– 存储结构
– 顺序存储：数组，随机访问，连续空间
– 链式存储：指针/引用，灵活，非连续
– 索引存储、散列存储
– 时间复杂度 & 空间复杂度
– 大O表示法：O(1)、O(log n)、O(n)、O(n log n)、O(n²)
– 常见复杂度排序：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
二、线性表
1. 顺序表（数组）
– 特点：逻辑相邻 = 物理相邻
– 操作：插入 O(n)、删除 O(n)、按位查找 O(1)
– 优缺点：支持随机访问，插入删除慢，扩容成本高
2. 链表
– 单链表
– 头结点作用：统一插入删除操作
– 按值查找 O(n)，插入删除 O(1)（已知位置）
– 双链表：前驱 + 后继，方便反向遍历
– 循环链表：尾指针指向头
– 静态链表：用数组模拟链表（无指针语言）
3. 对比
结构 访问 插入删除 空间
顺序表 O(1) O(n) 紧凑
链表 O(n) O(1) 指针额外开销
三、栈和队列
1. 栈（Stack）
– 特点：后进先出 LIFO
– 顺序栈 / 链栈
– 应用：函数调用、表达式求值、括号匹配、递归
2. 队列（Queue）
– 特点：先进先出 FIFO
– 循环队列（重点）：
"front == rear" 判空，
"(rear+1)%max == front" 判满
– 双端队列、优先队列（堆实现）
四、串（String）
– 存储：定长顺序、堆分配、块链
– 模式匹配
– BF算法：O(nm)，简单但慢
– KMP算法（重点）：O(n+m)，核心是 next 数组 / nextval 数组
五、树与二叉树
1. 二叉树
– 性质：
– 第 i 层最多 2ⁱ⁻¹ 个结点
– 深度为 k 的二叉树最多 2ᵏ − 1 个结点
– n₀ = n₂ + 1
– 存储：顺序（完全二叉树）、链式（二叉链表）
2. 遍历（必考）
– 先序 / 中序 / 后序（递归 + 非递归栈实现）
– 层次遍历（队列）
– 由中序 + 先序 / 后序可唯一确定二叉树
3. 特殊二叉树
– 满二叉树 / 完全二叉树
– 二叉排序树（BST）：左 < 根 < 右
– 平衡二叉树（AVL）：|左高 − 右高| ≤ 1，四种旋转
– 哈夫曼树：带权路径最短，哈夫曼编码（前缀编码，无歧义）
六、图
1. 存储结构
– 邻接矩阵：O(|V|²)，适合稠密图
– 邻接表：O(|V|+|E|)，适合稀疏图
– 十字链表（有向图）、邻接多重表（无向图）
2. 遍历
– DFS：栈 / 递归，时间 O(V+E)
– BFS：队列，求最短路径（无权图）
3. 最小生成树
– Prim：适合稠密图，O(V²)
– Kruskal：适合稀疏图，O(E log E)，并查集实现
4. 最短路径
– Dijkstra：单源最短路径，非负权，O(V²) / O(E + V log V)
– Floyd：多源最短路径，O(V³)
– Bellman-Ford：可处理负权边
5. 拓扑排序 & 关键路径
– AOV 网：拓扑排序（DFS / 入度表）
– AOE 网：关键路径（最早/最晚时间）
七、查找
1. 静态查找
– 顺序查找：O(n)
– 折半查找：O(log n)，要求有序
– 分块查找：块间有序，块内无序
2. 动态查找
– 二叉排序树：平均 O(log n)，最坏 O(n)
– AVL 树：严格平衡 O(log n)
– B 树 / B+ 树
– B 树：多路平衡查找树，数据库索引
– B+ 树：叶子结点链表，范围查询友好
3. 哈希表（Hash）
– 构造：直接定址、除留余数、平方取中等
– 冲突处理
– 开放定址：线性探测、二次探测
– 链地址法（最常用）
– 装填因子 α = 表中记录数 / 哈希表长度
八、排序（超级重点）
比较类排序
排序 平均 最坏 稳定 备注
冒泡 O(n²) O(n²) ✅ 相邻交换
选择 O(n²) O(n²) ❌ 交换次数少
插入 O(n²) O(n²) ✅ 基本有序时快
希尔 O(n¹·³) — ❌ 插入排序改进
快排 O(n log n) O(n²) ❌ pivot 选择关键
归并 O(n log n) O(n log n) ✅ 额外空间 O(n)
堆排 O(n log n) O(n log n) ❌ 建堆 O(n)
非比较类
– 计数排序、基数排序、桶排序：O(n + k)，稳定，适合特定场景
九、常见综合考点
– 递归 → 栈
– 栈 / 队列 / 树 / 图的相互转换
– 排序算法思想 + 手写代码 + 稳定性判断
– 时间空间复杂度对比
– 算法设计题：如用栈实现队列、用队列实现栈、LRU 缓存等
十、速记口诀
– 栈：后进先出
– 队列：先进先出
– 中序 + 先/后序 → 唯一二叉树
– 平衡二叉树：左旋右旋
– 最小生成树：Prim 稠密，Kruskal 稀疏
– 排序稳定性：冒插归基计桶稳，其余不稳
如果你告诉我用途（比如：期末复习 / 考研 / 面试 / 转码刷题），我可以帮你再缩成一份“极简必背版”或“易错点清单”，更适合冲刺。需要吗？
