本书结构 本书共由7个部分组成。为学好后半部分的内容,第一部分和第二部分主要介绍了一些背景知识,其中包括程序设计竞赛中解决问题的方法、编写代码和调试中的注意事项、算法的正确性证明以及效率分析等。不要以为此部分是基础性的内容而可以忽视,如果不能很好地理解这些基础知识,那么之后更深的内容就只能学到皮毛。本书的其他部分都将围绕着算法设计技巧和数据结构等程序设计竞赛解决问题的技术进行介绍。在这些部分将讲解各个算法诞生的背景以及设计过程,也包括能够直接解答或变换形式解答的练习题。 本书中,练习题和解题部分所占比重较大。请各位阅读练习题时不要一带而过,要尽力去解答这些习题。只有这样才能与书中正确解法相比较,从而学到更多。 大家解题后最好把自己编写的代码跟书中代码进行比较。因为本书在确保效率的前提下,尽量精简了代码。各位可比较书中代码是否与自己编写的代码相似,实现算法的方法是否相同,进而可再思索一下是否有更好的实现方法。 必要的基础知识 本书面向计算机科学专业本科生。读者只要具备高中数学、计算机科学的入门级知识就足够了。所以,已经学过高中数学课程以及能够使用C++ 和STL就可以放心大胆地阅读本书。 给初学者的一点建议 本书涵盖多个主题,有些部分必然会先涉及尚未介绍的技巧或工具。 同样,本书不少示例也是利用后半部分要介绍的方法进行解答的。建议各位不要一味地按照章节顺序阅读,而是要先理解最重要、最基础的主题部分,等学到这些方法后再进行补充。建议初学者在深入学习之前,先阅读内容出现频率较高的几个章节。表1-1是推荐给初学者的课程表。 表1-1 初学者的课程表 章节序号 章节题目 2 解决问题概述 3 编码与调试 4 分析算法的时间复杂度 (续) 章节序号 章节题目 6 暴力解决法 7 分治法 8 动态规划法 18 线性数据结构 19 队列、栈以及双端队列 21 树的实现与遍历 22 二叉搜索树 23 优先级队列和堆 27 图的表示方式及定义 28 图的深度优先搜索 29 图的宽度优先搜索 30 最短路径问题