内容简介

吴永辉，博士，复旦大学计算机科学与工程系副教授，ACM-ICPC中国赛区指导委员会（ACM-ICPC Council China）成员，复旦大学ACM程序设计竞赛队教练。作者自2001年起连续带队进入ACM-ICPC世界总决赛，并取得过世界第6名的佳绩。他的主要研究方向为数据库，在《计算机研究与发展》、《软件学报》以及重大学术会议上发表过多篇论文，参与翻译出版了《数据通信与网络》和《数据通信、计算机网络与开放系统》。

王建德，著名的信息学奥林匹克竞赛金牌教练，国务院特殊津贴专家，中学特级教师。他所辅导的学生在国际奥林匹克信息学竞赛（IOI）中获7金、3银、2铜的优异成绩，先后出版了24本关于程序设计和算法的学术专著，其中《实用算法的分析与程序设计》广受好评，长期以来是国内各类程序设计竞赛的必备教程。

作品目录

前言
第一篇 基本能力的编程实验
第1章 简单计算的编程实验 2
1.1 改进程序书写风格的实验范例 2
1.2 正确处理多组测试数据的实验范例 4
1.3 提高实数精度的实验范例 7
1.4 使用二分法提高计算时效的实验范例 8
1.5 相关题库 13
第2章 简单模拟的编程实验 23
2.1 直叙式模拟的实验范例 23
2.2 筛选法模拟的实验范例 26
2.3 构造法模拟的实验范例 28
2.4 相关题库 30
第3章 简单递归的编程实验 36
3.1 计算递归函数的实验范例 36
3.2 用递归算法求问题解的实验范例 37
3.3 求解递归数据的实验范例 40
3.4 相关题库 42
本篇小结 46
第二篇 线性数据结构的编程实验
第4章 应用直接存取类线性表编程 48
4.1 数组应用一：日期计算的实验
范例 48
4.2 数组应用二：高精度运算的实验范例 54
4.3 数组应用三：多项式表示与处理的实验范例 60
4.4 数组应用四：数值矩阵运算的实验范例 65
4.5 字符串处理一：串的存储结构的实验范例 70
4.6 字符串处理二：串模式匹配的实验范例 71
4.7 相关题库 77
第5章 应用顺序存取类线性表编程 112
5.1 顺序表应用的实验范例 112
5.2 栈应用的实验范例 118
5.3 队列应用的实验范例 124
5.4 相关题库 134
第6章 应用广义索引类线性表编程 141
6.1 使用词典解题的实验范例 141
6.2 使用散列表与散列方法解题的实验范例 148
6.3 相关题库 154
第7章 应用线性表排序编程 160
7.1 利用STL中自带的排序功能编程的实验范例 160
7.2 应用排序算法编程的实验范例 166
7.3 相关题库 169
本篇小结 190
第三篇 层次类非线性表的编程实验
第8章 采用树结构的非线性表编程 192
8.1 用树的遍历求解层次性问题的实验范例 192
8.2 用树结构支持并查集的实验范例 201
8.3 用树状数组统计子树权和的实验范例 207
8.4 相关题库 211
第9章 应用二叉树的基本概念编程 231
9.1 普通有序树转化为二叉树的实验范例 231
9.2 计算二叉树路径的实验范例 234
9.3 通过遍历确定二叉树结构的实验范例 237
9.4 相关题库 239
第10章 应用经典二叉树编程 243
10.1 二叉搜索树的实验范例 243
10.2 二叉堆的实验范例 248
10.3 哈夫曼树的实验范例 259
10.4 相关题库 262
本篇小结 275
第四篇 群聚类非线性表的编程实验
第11章 应用图的遍历算法编程 278
11.1 BFS算法的实验范例 278
11.2 DFS算法的实验范例 282
11.3 拓扑排序的实验范例 285
11.4 计算无向图的连通性的实验范例 291
11.5 相关题库 299
第12章 应用最小生成树算法编程 327
12.1 Kruskal算法的实验范例 327
12.2 Prim算法的实验范例 330
12.3 相关题库 333
第13章 应用最佳路径算法编程 341
13.1 Warshall算法和Floyed-Warshall算法的实验范例 341
13.2 Dijkstra算法的实验范例 347
13.3 Bellman-Ford算法的实验范例 351
13.4 SPFA算法的实验范例 356
13.5 相关题库 360
第14章 应用特殊图的经典算法编程 368
14.1 二分图匹配的实验范例 368
14.2 计算网络最大流的实验范例 371
14.3 相关题库 385
本篇小结 396
· · · · · ·

作者简介

吴永辉，博士，复旦大学计算机科学与工程系副教授，ACM-ICPC中国赛区指导委员会（ACM-ICPC Council China）成员，复旦大学ACM程序设计竞赛队教练。作者自2001年起连续带队进入ACM-ICPC世界总决赛，并取得过世界第6名的佳绩。他的主要研究方向为数据库，在《计算机研究与发展》、《软件学报》以及重大学术会议上发表过多篇论文，参与翻译出版了《数据通信与网络》和《数据通信、计算机网络与开放系统》。

王建德，著名的信息学奥林匹克竞赛金牌教练，国务院特殊津贴专家，中学特级教师。他所辅导的学生在国际奥林匹克信息学竞赛（IOI）中获7金、3银、2铜的优异成绩，先后出版了24本关于程序设计和算法的学术专著，其中《实用算法的分析与程序设计》广受好评，长期以来是国内各类程序设计竞赛的必备教程。

精彩摘录

需要说明的是，本书是在复旦大学ACM集训队长期活动的基础上积累而成的。阿拉法特·居来提、姚哲云、张昊等同学精心编写了所有程序，每道程序都通过了严格的测试验证，其中一些程序经多次修改，精益求精。由于时间和水平所限，书中肯定夹杂了不少缺点和错误，表述不当和笔误更是在所难免，热忱欢迎学术界同仁和读者赐正。

——引自第3页

cnt=n的表示数为anw

——引自第6页