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

定　价：¥59.00

作　者：	王建德，吴永辉著
出版社：	人民邮电出版社
丛编项：
标　签：	计算机理论

购买这本书可以去

ISBN：	9787115268655	出版时间：	2012-01-01	包装：	平装
开本：	16开	页数：	369	字数：

内容简介

　　本书对近年来程序设计教育和竞赛培训活动中涌现的许多实用的数据结构设计方法进行了全面总结，通过深入的分析和生动的实例引导读者寻找问题中各对象之间的关系，确定数学模型所使用的逻辑结构；实现对各个对象的操作，即确定数据所采用的存储结构；将数据类型与定义在该类型上的运算融于一体，为面向对象的程序设计方法奠定基础。本书既是大学计算机专业数据结构课程和算法设计课程的优秀参考书，也是大中学生程序设计竞赛不可多得的培训教材。本书特色按照数据结构的知识体系，全书分为“线性表”、“树型问题”和“图型问题”三篇，介绍了几十种存储方式和相应的算法。介绍了许多实用的数据结构设计方法，同时引导读者尽可能采用“扬长避短”的选择原则和“取长补短”的结合方法，选择有利于提升算法效率的数据结构。对每个比较难懂的概念都举实例加以说明，对每个比较抽象的定理都有具体的应用例证帮助理解，对每个经典算法都有清晰的程序流程给予示范。此外，还大量运用图表，使得概念、定理和算法的由来变得具体、形象和直观。书中采用了一种结构清晰、移植性强且贴近自然语言表述的类程序设计语言。只要读者具备Pascal和C等任一种语言的基础，就可以比较轻松地读懂其语义。

作者简介

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

图书目录

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