内容介绍
《挑战程序设计竞赛2:算法和数据结构》分成提前准备篇、基本篇和运用篇三绝大多数,依靠免费在线测评系统软件Aizu Online Judge及其很多练习题,详尽解读了算法与算法复杂度、初等和高等学校排列、检索、递归和分治法、动态规划法、二叉搜索树、堆、图、测算几何学、数论等与程序设计竞赛有关的算法和数据结构,既能够做为挑战程序设计竞赛的教材,还可以用于正确引导新手系统软件学习培训算法和数据结构的基本知识。这书合适全部程序设计工作人员、程序设计竞赛发烧友及其高等院校软件工程专业老师学生阅读文章。
目录
- 第1部分 [准备篇]攻克程序设计竞赛的学习方法 1
- 第1章 有效运用在线评测系统 3
- 1.1 攻克程序设计竞赛的学习方法 3
- 1.2 什么是在线评测 7
- 1.3 用户注册 9
- 1.4 浏览问题 10
- 1.5 解答问题 12
- 1.6 个人页面 18
- 1.7 如何运用本书 19
- 第2部分 [基础篇]为程序设计竞赛做准备的算法与数据结构 21
- 第2章 算法与复杂度 23
- 2.1 算法是什么 23
- 2.2 问题与算法示例 23
- 2.3 伪代码 25
- 2.4 算法的效率 26
- 2.5 入门问题 28
- 第3章 初等排序 33
- 3.1 挑战问题之前——排序 33
- 3.2 插入排序法 35
- 3.3 冒泡排序法 40
- 3.4 选择排序法 44
- 3.5 稳定排序 48
- 3.6 希尔排序法 52
- 第4章 数据结构 57
- 4.1 挑战问题之前——什么是数据结构 57
- 4.2 栈 59
- 4.3 队列 64
- 4.4 链表 70
- 4.5 标准库的数据结构 77
- 4.6 数据结构的应用——计算面积 86
- 第5章 搜索 89
- 5.1 挑战问题之前——搜索 89
- 5.2 线性搜索 91
- 5.3 二分搜索 94
- 5.4 散列法 98
- 5.5 借助标准库搜索 102
- 5.6 搜索的应用——计算最优解 106
- 第6章 递归和分治法 109
- 6.1 挑战问题之前——递归与分治 109
- 6.2 穷举搜索 111
- 6.3 科赫曲线 114
- 第7章 高等排序 119
- 7.1 归并排序 120
- 7.2 分割 125
- 7.3 快速排序 129
- 7.4 计数排序 133
- 7.5 利用标准库排序 137
- 7.6 逆序数 139
- 7.7 最小成本排序 143
- 第8章 树 147
- 8.1 挑战问题之前——树结构 148
- 8.2 有根树的表达 150
- 8.3 二叉树的表达 154
- 8.4 树的遍历 159
- 8.5 树遍历的应用——树的重建 163
- 第9章 二叉搜索树 167
- 9.1 挑战问题之前——二叉搜索树 168
- 9.2 二叉搜索树——插入 169
- 9.3 二叉搜索树——搜索 174
- 9.4 二叉搜索树——删除 177
- 9.5 通过标准库管理集合 182
- 第10章 堆 189
- 10.1 挑战问题之前——堆 190
- 10.2 完全二叉树 191
- 10.3 最大/最小堆 193
- 10.4 优先级队列 197
- 10.5 通过标准库实现优先级队列 201
- 第11章 动态规划法 203
- 11.1 挑战问题之前——动态规划法的概念 203
- 11.2 斐波那契数列 204
- 11.3 最长公共子序列 208
- 11.4 矩阵链乘法 211
- 第12章 图 217
- 12.1 挑战问题之前——图 218
- 12.2 图的表示 221
- 12.3 深度优先搜索 224
- 12.4 广度优先搜索 232
- 12.5 连通分量 237
- 第13章 加权图 241
- 13.1 挑战问题之前——加权图 242
- 13.2 最小生成树 244
- 13.3 单源最短路径 249
- 第3部分 [应用篇]程序设计竞赛的必备程序库 261
- 第14章 高等数据结构 263
- 14.1 互质的集合 264
- 14.2 范围搜索 269
- 14.3 其他问题 278
- 第15章 高等图算法 279
- 15.1 所有点对间最短路径 280
- 15.2 拓扑排序 284
- 15.3 关节点 290
- 15.4 树的直径 295
- 15.5 最小生成树 299
- 15.6 其他问题 303
- 第16章 计算几何学 305
- 16.1 几何对象的基本元素与表现 306
- 16.2 直线的正交/平行判定 312
- 16.3 投影 314
- 16.4 映象 316
- 16.5 距离 317
- 16.6 逆时针方向 321
- 16.7 判断线段相交 324
- 16.8 线段的交点 326
- 16.9 圆与直线的交点 328
- 16.10 圆与圆的交点 331
- 16.11 点的内包 333
- 16.12 凸包 335
- 16.13 线段相交问题 339
- 16.14 其他问题 343
- 第17章 动态规划法 345
- 17.1 硬币问题 346
- 17.2 背包问题 349
- 17.3 最长递增子序列 353
- 17.4 最大正方形 357
- 17.5 最大长方形 360
- 17.6 其他问题 364
- 第18章 数论 367
- 18.1 质数检验 368
- 18.2 最大公约数 372
- 18.3 幂乘 376
- 18.4 其他问题 378
- 第19章 启发式搜索 381
- 19.1 八皇后问题 382
- 19.2 九宫格拼图 386
- 19.3 十六格拼图 391
- 附录 399
- 通过本书可以获得的技能 400
- 挑战以往的程序设计竞赛真题! 402
- 参考文献 404