前辅文
第1章 绪论
1.1 问题引入：大型超市商品管理
1.2 问题求解
1.2.1 问题分析
1.2.2 存储实现与算法设计
1.3 数据结构定义
1.3.1 数据的逻辑结构
1.3.2 数据的存储结构
1.3.3 数据的操作实现
1.4 算法分析
1.4.1 算法的基本概念
1.4.2 时间复杂性的度量
1.4.3 空间复杂性的度量
1.4.4 常用的时间复杂度函数
1.4.5 渐近表示法的计算
1.5 算法优化
1.6 应用场景：数据挖掘
本章小结
本章习题
溯源与参考文献
第2章 线性表
2.1 问题引入：一元多项式
2.2 线性表的定义与结构
2.2.1 线性表的定义
2.2.2 线性表的结构
2.3 线性表的顺序存储实现
2.3.1 顺序表
2.3.2 顺序表的基本操作
2.4 线性表的链式存储实现
2.4.1 单链表
2.4.2 单链表的基本操作
2.4.3 双向链表
2.4.4 循环链表
*2.4.5 静态链表
*2.4.6 块状链表
2.5 线性表的应用
2.5.1 一元多项式的加法
2.5.2 大整数处理
☆2.6 拓展延伸
2.6.1 广义表
2.6.2 多维数组和特殊矩阵
*2.6.3 稀疏矩阵和舞蹈链
2.7 应用场景：内存管理
本章小结
本章习题
溯源与参考文献
第3章 栈与队列
3.1 问题引入：超市货架管理
3.2 栈的定义与结构
3.2.1 栈的定义
3.2.2 栈的顺序存储实现
3.2.3 栈的链式存储实现
3.2.4 栈的变种
3.3 队列的定义与结构
3.3.1 队列的定义
3.3.2 队列的顺序存储实现
3.3.3 队列的链式存储实现
3.3.4 队列的变种
3.4 栈与队列的应用
3.4.1 表达式求值
3.4.2 递归实现与系统运行栈
3.4.3 火车车厢重排
☆3.5 拓展延伸
3.5.1 单调栈
3.5.2 单调队列
3.6 应用场景：消息队列
本章小结
本章习题
溯源与参考文献
第4章 字符串
4.1 问题引入：模式匹配
4.2 字符串的定义与结构
4.3 字符串的存储实现
4.3.1 字符串的顺序存储实现
4.3.2 字符串的链式存储实现
4.4 字符串的模式匹配
4.4.1 朴素模式匹配算法
4.4.2 KMP算法
*4.4.3 BM算法
*4.4.4 KR算法
*4.4.5 Sunday算法
☆4.5 拓展延伸
4.5.1 正则表达式
4.5.2 带有通配符的字符串匹配
4.6 应用场景：基因测序
本章小结
本章习题
溯源与参考文献
第5章 树与二又树
5.1 问题引入：商品分类
5.2 树的定义与结构
5.3 二又树
5.3.1 二又树的定义
5.3.2 满二叉树、完全二又树、完美二叉树
5.3.3 二又树的基本性质
5.3.4 二又树的顺序存储实现
5.3.5 二又树的链式存储实现
5.4 二又树的遍历
5.4.1 遍历的基本概念
5.4.2 二又树遍历的递归算法
5.4.3 二又树遍历的非递归算法
5.4.4 二叉树的序列化与反序列化
5.5 Huffman树与Huffman编码
5.5.1 Huffman树
5.5.2 Huffman算法
5.5.3 Huffman编码
5.6 树与森林
5.6.1 树的存储结构
5.6.2 树、森林与二叉树的转换
5.6.3 树和森林的遍历
☆5.7 拓展延伸
5.7.1 Trie树
5.7.2 后缀树和后缀自动机
5.8 应用场景：决策树
本章小结
本章习题
溯源与参考文献
第6章 优先级队列
6.1 问题引入：带优先级的服务处理
6.2 优先级队列的定义
6.3 二叉堆
6.3.1 二叉堆的定义
6.3.2 二叉堆的操作
6.4 多叉堆
*6.5 可并堆
6.5.1 左堆
6.5.2 斜堆
6.5.3 二项堆
6.5.4 均摊分析
6.6 优先级队列应用：Huffman树的构建
*6.7 拓展延伸
6.7.1 双端优先级队列
6.7.2 对顶堆
6.8 应用场景：离散事件模拟
本章小结
本章习题
溯源与参考文献
第7章 图
7.1 问题引入：哥尼斯堡七桥问题
7.2 图的定义与结构
7.3 图的存储表示及实现
7.3.1 邻接矩阵和加权邻接矩阵
7.3.2 邻接表
*7.3.3 多重邻接表
*7.3.4 十字链表
7.3.5 图的基本操作实现
7.4 图的遍历
7.4.1 图的深度优先遍历
7.4.2 图的广度优先遍历
7.5 图的连通性
7.5.1 无向图的连通性
*7.5.2 六度空间理论的验证
7.5.3 有向图的连通性
7.6 图的应用：哥尼斯堡七桥问题求解
☆7.7 拓展延伸：双连通分量
7.8 应用场景：语义网络
本章小结
本章习题
溯源与参考文献
第8章 图应用
8.1 问题引入：魔方问题
8.2 最短路径
8.2.1 单源最短路径：Dijkstra算法
8.2.2 带负权值的单源最短路径：Bellman-Ford算法
8.2.3 所有顶点对之间的最短路径：Floyd-Warshall算法
8.3 最小生成树
8.3.1 Prim 算法
8.3.2 Kruskal算法
8.4 拓扑排序和关键路径
8.4.1 拓扑排序
8.4.2 关键路径
☆8.5 拓展延伸
8.5.1 二部图
8.5.2 网络流
8.6 应用场景：图计算
本章小结
本章习题
溯源与参考文献
*第9章 不相交集
9.1 问题引入：Kruskal算法的高效实现
9.2 等价关系、等价类和不相交集
9.3 不相交集的存储实现
9.4 不相交集的基本运算实现
9.4.1 按秩合并
9.4.2 路径压缩
☆9.4.3 时间复杂度分析
9.5 不相交集的应用：最近公共祖先问题
☆9.6 拓展延伸：扩展不相交集
9.7 应用场景：面向对象的编程语言
本章小结
本章习题
溯源与参考文献
第10章 内排序
10.1 问题引入：姓氏排序
10.2 排序的定义
10.3 插入排序
10.3.1 直接插入排序
10.3.2 折半插入排序
10.3.3 Shell排序
10.4 选择排序
10.4.1 简单选择排序
10.4.2 堆排序
10.5 交换排序
10.5.1 冒泡排序
10.5.2 快速排序
10.6 归并排序
10.6.1 二路归并
10.6.2 归并排序
*10.7 基于比较排序的时间复杂度分析
10.7.1 基于比较排序的时间复杂度下界
10.7.2 基于比较排序的平均情况时间复杂度
10.7.3 最少比较排序
10.8 基于分配的排序
10.8.1 计数排序
10.8.2 基数排序
*10.9 索引排序
☆10.10 拓展延伸
10.10.1 内省排序
10.10.2 Tim排序
10.11 应用场景：考试录取中的成绩排序
本章小结
本章习题
溯源与参考文献
第11章 查找
11.1 问题引入：手机通讯录
11.2 查找的定义
11.3 静态查找表
11.3.1 顺序查找
11.3.2 二分查找
11.3.3 索引查找
11.4 动态查找表
11.4.1 二叉查找树
11.4.2 AVL树
11.5 散列方法
11.5.1 基本概念
11.5.2 散列函数
11.5.3 散列冲突解决方法
11.5.4 散列查找算法及查找性能分析
11.6 查找的应用：手机通讯录的查找
☆11.7 拓展延伸：分布式散列表
11.8 应用场景：词频统计
本章小结
本章习题
溯源与参考文献
*第12章 高级查找
12.1 问题引入：网上购物
12.2 线段树
12.2.1 线段树的定义
12.2.2 线段树的存储实现
12.2.3 线段树的动态维护操作
12.2.4 树状数组
12.3 跳表
12.3.1 跳表的定义
12.3.2 跳表的基本操作
12.4 红黑树
12.4.1 红黑树的定义
12.4.2 红黑树的存储实现
12.4.3 红黑树基本操作实现及性能
*12.4.4 红黑树的变种：AA树
12.5 伸展树
12.5.1 伸展树的定义与调整方法
12.5.2 伸展树的性能分析
12.6 树堆
12.6.1 树堆的概念
12.6.2 树堆的基本操作
☆12.7 拓展延伸
12.7.1 KD树
12.7.2 四叉树
12.8 应用场景：虚拟内存管理
本章小结
本章习题
溯源与参考文献
第13章 外排序
13.1 问题引入：内存与外存
13.2 文件与文件流
13.2.1 文件组织
13.2.2 流文件
13.2.3 缓冲区和缓冲池
13.3 外排序处理过程
13.4 二路归并外排序
*13.5 多路归并外排序：选择树
13.5.1 胜者树
13.5.2 败者树
*13.6 最佳归并树
13.7 置换选择外排序
☆13.8 拓展延伸：并行归并和分布式归并
13.9 应用场景：数据库系统中的外排序
本章小结
本章习题
溯源与参考文献
第14章 索引
14.1 问题引入：索引和查找
14.2 索引的定义和基本概念
14.3 线性索引与静态索引
*14.4 倒排索引
14.4.1 基于属性的倒排
14.4.2 对正文文件的倒排
*14.5 动态索引
14.5.1 B树
14.5.2 B+树
14.5.3 B/B+树的性能分析
14.5.4 动态索引和静态索引性能的比较
*14.6 位索引
14.6.1 位图索引
14.6.2 签名文件
☆14.7 拓展延伸：多维的外存索引——R树
14.8 应用场景：搜索引擎中的索引
本章小结
本章习题
溯源与参考文献
*第15章 算法设计基础
15.1 分书问题与枚举法
15.1.1 分书问题
15.1.2 枚举法的设计思想
15.1.3 枚举法的优化方向
15.2 回溯法与分支限界法
15.2.1 问题的解空间与状态搜索
15.2.2 叵回溯法的设计思想
15.2.3 分支限界法的设计思想
15.3 分治法
15.3.1 分治法的设计思想
15.3.2 算法复杂度分析与主定理
15.4 动态规划
15.4.1 优化问题与最优子结构
15.4.2 应用案例分析
15.4.3 动态规划的设计思想
15.5 贪心法
15.5.1 贪心法的设计思想
15.5.2 应用案例分析
15.5.3 贪心法的正确性分析
15.6 经典算法的应用：背包问题
15.6.1 连续背包问题
15.6.2 离散背包问题
15.7 拓展延伸：启发式算法概述
15.8 应用场景：代码查重
本章小结
本章习题
溯源与参考文献
☆第16章 高级算法设计
16.1 近似算法
16.1.1 问题引入：无向图的顶点覆盖
16.1.2 近似算法的性能比
16.1.3 近似算法的设计思想与分析方法
16.2 启发式搜索算法
16.2.1 问题引入：八数码问题
16.2.2 A算法与A*算法
16.2.3 局部搜索算法
16.3 随机算法
16.3.1 问题引入：大素数测试
16.3.2 随机算法的设计思想
16.3.3 随机数的生成
16.4 拓展延伸：博弈搜索
16.5 应用场景：机器博弈
本章小结
本章习题
溯源与参考文献
术语对照表
参考文献
