摘要

网罗算法和数据结构的关键知识点！
系统学习基础知识——适合初学者的入门书
有效运用在线评测——适合挑战者的参考书
全书练习均可借助在线评测系统（AIZU ONLINE JUDGE）
与竞赛相同的自动审查系统，有效检测Bug和算法效率
大量习题及往年真题，体验各类题型、总结答题技巧
与世界各地选手相互切磋、共同成长
入门、挑战、进阶，享受收集算法的乐趣！

挑战程序设计竞赛2 算法和数据结构 内容简介

本书分为准备篇、基础篇和应用篇三大部分，借助在线评测系统Aizu Online Judge以及大量例题，详细讲解了算法与复杂度、初等和高等排序、搜索、递归和分治法、动态规划法、二叉搜索树、堆、图、计算几何学、数论等与程序设计竞赛相关的算法和数据结构，既可以作为挑战程序设计竞赛的参考书，也可以用来引导初学者系统学习算法和数据结构的基础知识。本书适合所有程序设计人员、程序设计竞赛爱好者以及高校计算机专业师生阅读。

挑战程序设计竞赛2 算法和数据结构 目录

第1部分 [准备篇]攻克程序设计竞赛的学习方法

第1章 有效运用在线评测系统

1.1 攻克程序设计竞赛的学习方法

1.2 什么是在线评测

1.3 用户注册

1.4 浏览问题

1.5 解答问题

1.6 个人页面

1.7 如何运用本书

第2部分 [基础篇]为程序设计竞赛做准备的算法与数据结构

第2章 算法与复杂度

2.1 算法是什么

2.2 问题与算法示例

2.3 伪代码

2.4 算法的效率

2.5 入门问题

第3章 初等排序

3.1 挑战问题之前——排序

3.2 插入排序法

3.3 冒泡排序法

3.4 选择排序法

3.5 稳定排序

3.6 希尔排序法

第4章 数据结构

4.1 挑战问题之前——什么是数据结构

4.2 栈

4.3 队列

4.4 链表

4.5 标准库的数据结构

4.6 数据结构的应用——计算面积

第5章 搜索

5.1 挑战问题之前——搜索

5.2 线性搜索

5.3 二分搜索

5.4 散列法

5.5 借助标准库搜索

5.6 搜索的应用——计算最优解

第6章 递归和分治法

6.1 挑战问题之前——递归与分治

6.2 穷举搜索

6.3 科赫曲线

第7章 高等排序

7.1 归并排序

7.2 分割

7.3 快速排序

7.4 计数排序

7.5 利用标准库排序

7.6 逆序数

7.7 最小成本排序

第8章 树

8.1 挑战问题之前——树结构

8.2 有根树的表达

8.3 二叉树的表达

8.4 树的遍历

8.5 树遍历的应用——树的重建

第9章 二叉搜索树

9.1 挑战问题之前——二叉搜索树

9.2 二叉搜索树——插入

9.3 二叉搜索树——搜索

9.4 二叉搜索树——删除

9.5 通过标准库管理集合

第10章 堆

10.1 挑战问题之前——堆

10.2 完全二叉树

10.3 最大/最小堆

10.4 优先级队列

10.5 通过标准库实现优先级队列

第11章 动态规划法

11.1 挑战问题之前——动态规划法的概念

11.2 斐波那契数列

11.3 最长公共子序列

11.4 矩阵链乘法

第12章 图

12.1 挑战问题之前——图

12.2 图的表示

12.3 深度优先搜索

12.4 广度优先搜索

12.5 连通分量

第13章 加权图

13.1 挑战问题之前——加权图

13.2 最小生成树

13.3 单源最短路径

第3部分 [应用篇]程序设计竞赛的必备程序库

第14章 高等数据结构

14.1 互质的集合

14.2 范围搜索

14.3 其他问题

第15章 高等图算法

15.1 所有点对间最短路径

15.2 拓扑排序

15.3 关节点

15.4 树的直径

15.5 最小生成树

15.6 其他问题

第16章 计算几何学

16.1 几何对象的基本元素与表现

16.2 直线的正交/平行判定

16.3 投影

16.4 映象

16.5 距离

16.6 逆时针方向

16.7 判断线段相交

16.8 线段的交点

16.9 圆与直线的交点

16.10 圆与圆的交点

16.11 点的内包

16.12 凸包

16.13 线段相交问题

16.14 其他问题

第17章 动态规划法

17.1 硬币问题

17.2 背包问题

17.3 最长递增子序列

17.4 最大正方形

17.5 最大长方形

17.6 其他问题

第18章 数论

18.1 质数检验

182最大公约数

18.3 幂乘

18.4 其他问题

第19章 启发式搜索

19.1 八皇后问题

19.2 九宫格拼图

19.3 十六格拼图

附录

通过本书可以获得的技能

挑战以往的程序设计竞赛真题！

参考文献

挑战程序设计竞赛2 算法和数据结构 精彩文摘

在步骤1 中，将开头元素A0 视为已排序，所以我们取出A1 的3，将其插入已排序部分的恰当位置。首先把原先位于A[0] 的8 移动至A1，再把3 插入A[0]。这样一来，开头2 个元素就完成了排序。

在步骤2 中，我们要把A2 的1 插入恰当位置。这里首先将比1 大的A1 和A0顺次向后移一个位置，然后把1 插入A[0]。

在步骤3 中，我们要把A3 的5 插入恰当位置。这次将比5 大的A2 向后移一个位置，然后把5 插入A2。

之后同理，将已排序部分的其中一段向后移动，再把未排序部分的开头元素插入已排序部分的恰当位置。插入排序法的特点在于，只要0 到第i 号元素全部排入已排序部分，那么无论后面如何插入，这个0 到第i 号的元素都将永远保持排序完毕的状态。

实现插入排序法时需要的主要变量如图3.3 所示。