数据结构与算法¶

本章建立数据结构与算法的全局框架，帮助后续学习排序、树、堆、并查集和图论。

数据结构与算法简介¶

数据结构回答“数据怎么存”，算法回答“数据怎么处理”。同一个问题可以因为数据结构不同而产生完全不同的效率。

例如：

用数组查找元素通常需要线性扫描。
用哈希表查找元素平均接近常数时间。
用二分搜索树可以维护有序集合。
用图可以表示网络、地图、依赖关系和状态转移。

算法基础与分析方法¶

分析算法时常关注：

时间复杂度：输入规模增长时运行时间如何增长。
空间复杂度：额外内存使用如何增长。
最坏、平均、最好情况：不同输入分布下的表现。
稳定性：排序后相等元素的相对顺序是否保持。
原地性：是否只使用少量额外空间。

常见符号：

符号	含义
`O(f(n))`	上界，常用于描述最坏增长趋势
`Omega(f(n))`	下界
`Theta(f(n))`	紧确界，上下界同阶

线性数据结构¶

线性结构中的元素按一条逻辑顺序排列。

结构	特点	常见操作
数组	连续存储，按下标访问快	访问、遍历、排序
链表	节点通过指针连接	插入、删除、遍历
栈	后进先出	括号匹配、调用栈、DFS
队列	先进先出	BFS、任务调度
双端队列	两端都可进出	滑动窗口、单调队列

选择线性结构时，要先明确主要操作是随机访问、频繁插入删除，还是按顺序消费。

哈希表¶

哈希表通过哈希函数把键映射到桶位置，平均情况下查找、插入和删除接近 O(1)。

核心问题：

哈希函数是否分布均匀。
冲突如何处理，常见方式有链地址法和开放寻址法。
负载因子过高时是否扩容。
键是否可变，哈希值是否稳定。

哈希表适合去重、计数、缓存和快速映射，但不保留天然有序性。

树形结构¶

树是层级结构。常见概念包括根节点、父节点、子节点、叶子节点、高度和深度。

常见树：

二叉树：每个节点最多两个子节点。
二分搜索树：左子树小于节点，右子树大于节点。
堆：满足堆序性质，常用于优先队列。
平衡树：控制树高，避免退化为链表。
Trie：按字符路径组织字符串集合。

树结构常用于有序集合、优先队列、索引、表达式解析和层级数据。

图论结构¶

图由顶点和边组成，可表示任意对象之间的关系。

图的分类：

无向图与有向图。
无权图与带权图。
稀疏图与稠密图。
连通图与非连通图。

常见存储：邻接矩阵和邻接表。稀疏图通常使用邻接表，稠密图或需要快速判断边存在时可使用邻接矩阵。

分治算法¶

分治把问题拆成多个规模更小的子问题，分别解决后再合并结果。

典型步骤：

分解原问题。
递归解决子问题。
合并子问题答案。

归并排序、快速排序、二分搜索和最近点对都体现了分治思想。

贪心算法¶

贪心算法每一步选择当前看起来最优的方案，希望最终得到全局最优。

适用前提通常包括：

最优子结构。
贪心选择性质。

常见场景：区间调度、最小生成树、霍夫曼编码、部分最短路径算法。贪心的难点不在实现，而在证明局部最优能推出全局最优。

动态规划¶

动态规划适合有重叠子问题和最优子结构的问题。

常见建模步骤：

定义状态。
写出状态转移。
确定初始条件。
确定计算顺序。
优化空间或转移。

示例：背包问题、最长公共子序列、编辑距离、区间 DP、树形 DP。

高级树结构¶

高级树结构用于保证更稳定的复杂度或支持复杂查询。

结构	常见用途
AVL 树	严格平衡的有序集合
红黑树	工程中常见平衡搜索树
线段树	区间查询和区间修改
树状数组	前缀和与单点更新
Trie	字符串前缀检索

高级图算法¶

高级图算法覆盖路径、连通性、匹配和网络流等问题。

常见主题：

Dijkstra、Bellman-Ford、Floyd 最短路径。
Kruskal、Prim 最小生成树。
Tarjan 强连通分量和割点桥。
拓扑排序。
二分图匹配。
最大流与最小割。

图论题的关键是先把现实问题抽象为顶点和边，再选择合适的图模型。