程序设计中实用的数据结构

《程序设计中实用的数据结构》按照数据结构知识的分类，以线性表、树型问题和图型问题为基本构件，介绍了几十种存储方式和相应算法，同时深入浅出地分析和证明了每一种存储方式和算法的应用场合和效率，引导读者尽可能选择有利于提升算法效率的数据结构。

《程序设计中实用的数据结构》既可以作为大专院校计算机专业数据结构或算法类课程的教材，亦可以作为大学生和中学生程序设计竞赛活动的培训教程，还可以作为计算机软件研发的参考资料。

王建德 国务院特殊津贴专家、上海师范大学特聘教授、控江中学特级教师。他辅导学生在国际奥林匹克信息学竞赛（IOI）中获8金、4银、2铜，先后出版了《新编实用算法分析与程序设计》和《程序设计中常用的计算思维方式》等多本广受好评的图书，这些图书长期以来是国内各类程序设计竞赛的必备教程。吴永辉 博士，复旦大学计算机科学与工程系副教授，ACM-ICPC中国赛区指导委员会成员，复旦大学ACM程序设计竞赛队教练。自2001年起连续带队进入ACM-ICPC世界总决赛，并取得过世界第六名的佳绩。主要研究方向为数据库，在《计算机研究与发展》、《软件学报》以及重大学术会议上发表过多篇论文，参与翻译的著作有《数据通信与网络》和《数据通信、计算机网络与开放系统》。

上篇讨论线性表
第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.1SBT的性质
13.3.2旋转
13.3.3动态维护SBT的平衡特性
13.3.4SBT的基本操作
中篇小结
下篇讨论图型问题
第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.1BFS算法的基本概念
15.1.2BFS算法的应用
15.2深度优先遍历（DFS算法）
15.2.1DFS的基本概念
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.1Kruskal算法
18.4.2Prim算法
18.5最小生成树算法的应用实例
第19章加权图的单源最短路径问题
19.1基本概念
19.1.1单源算法是高效解决所有最短路径问题的基础
19.1.2负权回路影响单源最短路径的计算
19.1.3松弛技术是单源算法的核心
19.2求解单源最短路径问题的3种算法
19.2.1Dijkstra算法
19.2.2Bellman-Ford算法
19.2.3SPFA算法
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.2KM算法的基本思路
20.3.3KM算法的基本流程和应用实例
第21章最大流问题
21.1基本概念
21.2在可增广路径的基础上计算最大流
21.2.1可增广路径的基本概念
21.2.2基于最大流定理上的最大流算法
21.3按层次计算最大流的Dinic算法
21.3.1Dinic算法的基本思路
21.3.2Dinic算法的基本流程
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计算容量有上下界的网络的最小费用最小流
下篇小结