上篇 讨论线性表
第1章 数组
1.1 数组的基本概念
1.1.1 数组是一种顺序存储结构
1.1.2 数组是程序设计中使用频率最高的数据类型
1.2 优化数组的存储方式
1.2.1 规则矩阵的压缩存储
1.2.2 稀疏矩阵的压缩存储
1.2.3 矩阵的压缩存储
1.3 排序与顺序统计
1.3.1 排序的基本概念
1.3.2 计数排序与贪心策略
1.3.3 采用“二分”策略的排序方法
1.3.4 顺序统计的基本方法
第2章 链式存储结构
2.1 链表的基本概念
2.1.1 单链表
2.1.2 循环链表
2.1.3 双向链表
2.2 链表的基本运算
2.2.1 构建单链表
2.2.2 插入操作
2.2.3 删除操作
2.2.4 读取操作
2.3 链表的应用
第3章 两种存取方式特殊的线性表
3.1 “后进先出”的栈
3.1.1 栈的基本运算
3.1.2 栈的应用
3.2 “先进先出”的队列
3.2.1 队列的基本运算
3.2.2 队列的应用
第4章 散列技术
4.1 散列表
4.2 散列函数的设计
4.3 消除冲突的基本方法
4.3.1 使用开放寻址法消除冲突
4.3.2 使用分离链接法消除冲突
第5章 后缀数组
5.1 后缀数组的基本概念
5.2 采用倍增算法求解rank数组
5.3 利用rank数组计算最长公共前缀
5.3.1 计算最长公共前缀是一个典型的RMQ问题
5.3.2 计算最长公共前缀的基本方法
5.4 后缀数组的应用
5.4.1 利用后缀数组处理单个字符串
5.4.2 两个字符串的公共子串问题
5.4.3 多个字符串共享子串的问题
上篇小结
中篇 讨论树型问题
第6章 树的基本概念和遍历规则
6.1 树的递归定义
6.2 节点的分类
6.3 有关度的定义
6.4 树的深度（高度）
6.5 森林
6.6 有序树和无序树
6.7 树的表示方法
6.8 树的遍历规则
6.8.1 先根次序遍历树
6.8.2 后根次序遍历树
第7章 树的存储结构
7.1 采用数组存储入边信息
7.1.1 存储无权树的入边信息
7.1.2 存储加权树的入边信息
7.2 采用数组存储所有儿子的地址信息
7.2.1 采用整数存储儿子的数组下标
7.2.2 采用指针存储儿子的地址
7.3 采用邻接表存储出边信息
7.3.1 采用数组存储方式的邻接表
7.3.2 采用单链表存储方式的邻接表
7.4 无根树的一般存储方式
第8章 二叉树
8.1 二叉树的基本概念和存储结构
8.1.1 二叉树的基本概念
8.1.2 二叉树的存储结构
8.2 将普通有序树和森林转换成对应的二叉树
8.2.1 将普通有序树转换成对应的二叉树
8.2.2 将普通有序树组成的森林转换成对应的二叉树
8.3 二叉树的遍历
8.3.1 前序遍历
8.3.2 中序遍历
8.3.3 后序遍历
8.3.4 由两种遍历确定二叉树结构
第9章 并查集
9.1 并查集的基本概念
9.2 查找元素所在树的根节点并进行路径压缩
9.3 合并两个元素所在的集合
第10章 堆
10.1 二叉堆的概念
10.2 在插入或删除节点时维护堆性质
10.2.1 插入节点
10.2.2 删除最小值元素
10.3 建堆
10.4 堆排序
第11章 最优二叉树
11.1 最优二叉树的基本概念
11.2 构造最优二叉树
第12章 线段树
12.1 线段树的基本概念
12.1.1 用于区间运算的线段树
12.1.2 用于数据统计的线段树
12.1.3 线段树的数据结构
12.2 线段树的基本操作
12.2.1 建立线段树
12.2.2 在区间内插入线段或数据
12.2.3 删除区间内的线段或数据
12.2.4 计算区间内的线段或数据状态
12.3 线段树在静态统计问题上的应用
12.4 线段树在动态统计问题上的应用
第13章 二叉查找树
13.1 二叉排序树
13.1.1 二叉排序树的基本概念
13.1.2 二叉排序树的基本操作
13.2 静态二叉排序树
13.2.1 静态二叉排序树的特征
13.2.2 静态二叉排序树的构造方法
13.2.3 在静态二叉排序树上进行数据统计
13.3 子树大小平衡树（SBT）
13.3.1 SBT的性质
13.3.2 旋转
13.3.3 动态维护SBT的平衡特性
13.3.4 SBT的基本操作
中篇小结
下篇 讨论图型问题
第14章 图的基本概念及其存储结构
14.1 图的基本概念
14.2 图的简单分类
14.2.1 无向图和有向图
14.2.2 无权图和加权图
14.2.3 稀疏图和稠密图
14.2.4 完全图和补图
14.2.5 树和森林
14.2.6 图的生成树和生成森林
14.2.7 平面图
14.2.8 二分图
14.2.9 相交图和区间图
14.3 图的存储结构
14.3.1 存储节点间相邻关系的相邻矩阵
14.3.2 存储边信息的3种数据结构
第15章 图的遍历及其应用
15.1 广度优先遍历（BFS算法）
15.1.1 BFS算法的基本概念
15.1.2 BFS算法的应用
15.2 深度优先遍历（DFS算法）
15.2.1 DFS的基本概念
15.2.2 在DFS遍历过程中记录节点颜色变化的时间
15.2.3 根据节点颜色对边进行分类
15.2.4 分析DFS森林的结构
15.2.5 使用DFS算法进行拓扑排序
15.2.6 使用DFS算法计算欧拉回路
第16章 有向图的强连通分量和传递闭包
16.1 判定仙人掌图
16.2 计算强连通分量
16.3 传递闭包的应用
第17章 无向图的连通性分析
17.1 计算节点的low函数
17.2 计算连通图的割点和桥
17.2.1 计算连通图的割点
17.2.2 计算连通图的桥
17.3 计算双连通子图
17.4 分析连通图的连通程度
17.4.1 连通图的顶连通度
17.4.2 连通图的边连通度
第18章 最小生成树
18.1 基本概念
18.2 最小生成树的应用价值
18.3 最小生成树的计算策略
18.4 计算最小生成树的两种算法
18.4.1 Kruskal算法
18.4.2 Prim算法
18.5 最小生成树算法的应用实例
第19章 加权图的单源最短路径问题
19.1 基本概念
19.1.1 单源算法是高效解决所有最短路径问题的基础
19.1.2 负权回路影响单源最短路径的计算
19.1.3 松弛技术是单源算法的核心
19.2 求解单源最短路径问题的3 种算法
19.2.1 Dijkstra算法
19.2.2 Bellman-Ford算法
19.2.3 SPFA算法
19.3 单源最短路径算法的应用实例
第20章 二分图的匹配问题
20.1 基本概念
20.1.1 图的匹配概念
20.1.2 二分图的概念和判定方法
20.2 计算无权二分图的最大匹配
20.2.1 匈牙利算法的基本思路
20.2.2 匈牙利算法的基本流程
20.2.3 匈牙利算法的应用实例
20.3 计算带权二分图的最佳匹配
20.3.1 最佳匹配的概念
20.3.2 KM算法的基本思路
20.3.3 KM算法的基本流程和应用实例
第21章 最大流问题
21.1 基本概念
21.2 在可增广路径的基础上计算最大流
21.2.1 可增广路径的基本概念
21.2.2 基于最大流定理上的最大流算法
21.3 按层次计算最大流的Dinic算法
21.3.1 Dinic算法的基本思路
21.3.2 Dinic算法的基本流程
21.4 利用最大流最小割定理解题
21.4.1 割的概念
21.4.2 最小割的计算方法和应用实例
21.5 计算多源多汇网络的可行流
21.6 网络增加容量下界因素后的流量计算问题
21.6.1 求容量有上下界的网络的最大流
21.6.2 求容量有上下界的网络的最小流
21.7 网络增加费用因素后的流量计算问题
21.7.1 计算最小费用最大流
21.7.2 计算容量有上下界的网络的最小费用最小流
下篇小结
展开
