本书以数据结构基础和算法设计方法为知识单元，系统地介绍了数据结构与算法的基本知识及应用，简明扼要地阐释了计算机算法的设计与分析方法。本书的主要内容包括线性表、树、图等基础数据结构，同时也包括一些实用性较强的算法及高级数据结构，如并查集、伸展树等。以经典问题算法为例，书中分类介绍了算法设计方法以及查找与排序算法等。编者结合ACM国际大学生程序设计竞赛的需求，对各章节知识的灵活应用进行了详细的分析，用丰富的实例帮助读者由浅入深、快速地掌握算法设计的技巧，提升算法设计能力。本书的算法全部采用C语言描述，且在DevC++中测试通过，习题安排上注重能力培养和实战训练的需求。 本书注重理论与实践相结合，内容深入浅出，可以作为高等院校计算机相关专业的教材或参考书，同时也可供ACM竞赛的兴趣爱好者和有关工程技术人员参考。

前言 本书以教育部计算机专业数据结构课程大纲为基础，结合作者对该课程教学近30年的体会，以及指导一个省属普通高校学生队参加ACM国际大学生程序设计竞赛的经验来组织和安排教材内容。 本书的主要内容包括基础的算法分析(大O阶)方法，线性结构中的顺序结构与链式结构，栈与队列的应用，串的KMP模式匹配算法； 树、二叉树的常见遍历算法，线索二叉树、哈夫曼树； 图的深度优先、广度优先遍历算法，最小生成树、最短路径、拓扑排序、关键路径算法； 常用的查找和排序算法，散列表技术等。同时，从数据结构课程知识实际应用的角度，用相对比较多的篇幅，以经典算法应用为例重点介绍了常用的一些算法设计方法，例如分治法、贪心法、回溯与分支限界法、动态规划法等。 对于普通高等院校的学生来说，虽然大都能认识到数据结构课程的重要性，并有意要学好它，但事与愿违的事比比皆是。事实上有许多学生都会觉得数据结构比较抽象，上课时似乎听明白了，但实践算法时却总觉得无从下手，从而产生数据结构课程很难、枯燥乏味等不正确的观点和想法。其实数据结构中的很多算法都是人类智慧的结晶，通过它去感受计算机编程的魅力是一种非常愉悦的精神感受，这也正是许多ACMer对此乐不思蜀、欲罢不能的原因。 现如今各种数据结构教材、各类获奖教材、十一五、十二五规划教材可以说是层出不穷，但真正适合一个课程初学者自学和独立实践的教材并不多。为此，在本教材编写中，作者尽量摒弃传统数据结构教材“重理论思想而轻代码实现”的做法，关注一个初学数据结构和算法的自学者的感受，在题例中尽量给出完整的算法分析和代码实现。 作者是数据结构与算法课程浙江省省级精品课程负责人，也是教育部微软精品课程负责人，在执掌浙江师范大学ACM竞赛队教练期间，曾将一个几乎是零起点的学校ACM竞赛队，逐年提升竞技水平，在短短4年的时间里，实现了亚洲赛金奖的突破，并顺利取得了参加全球总决赛的资格。期望通过本教材的编写，对长期在这条战线上默默耕耘着的普通高等院校的教练们和ACM竞赛的爱好者们能有所启迪、有所帮助。 本书的题例和习题均以编程为主。作者认为理解概念还是相对容易的，理解算法思想并付诸于实践以解决实际问题才是本课程学习的真正目的。为增加课程学习的趣味性，提升学习者的实际编程能力或竞赛实战能力，本书的大多数题例来自北京大学和浙江大学的在线测试系统，同时也以这两个测试系统为主选择了课后练习实践题，以下是可供学习者练习的若干在线测试系统地址： 在线测试系统简称网址 北京大学在线评测系统POJhttp://poj.org/ 浙江大学在线评测系统ZOJhttp://acm.zju.edu.cn/onlinejudge/ UVA在线评测系统 UVA http://uva.onlinejudge.org/ http://livearchive.onlinejudge.org/ 续表 在线测试系统简称网址 Ural在线评测系统Uralhttp://acm.timus.ru/ SGU在线评测系统SGUhttp://acm.sgu.ru/ 上述各在线测试系统中均提供了丰富的测试练习题目，一个普通的学习者应该从中选择一些合适的题目进行练习。虽然说编程能力是听不会、看不会，而是靠练会的，但一个人的精力毕竟是有限的，尤其是一个普通高校而又在中学阶段没有经过任何信息学竞赛训练的学习者来说，题海战术显然是不合适，这就要求读者在研读本书时，在具备熟练的代码能力的基础上，还要善于分析总结、善于分类归纳，善于对题目做拓展、变化，真正做到举一反三、触类旁通，以求收到事半功倍的学习效果。作为课程授课的老师，引导学生多做角色换位思考训练，讲解问题点到为止，留出足够的空间给学习者自己去思考、去求解未尝不是一种好的训练方法。 学习数据结构与算法的另外一个目的是要学会分析判断最优化方法，竞赛中出现的题目往往不止一种求解方法，所以学习者首先应该学会分析某问题可以有多少种不同的求解方法，同时针对给定的问题和条件迅速判别出最优的求解方法。当然，此事说起来容易，做起来难，更何况算法和代码的优化是一个高智慧的体力活。限于作者自身的水平和能力，书中给出的算法并不一定能保证是最优的，也不一定能绝对保证是最合适的，从某种程度上说算法优化是无止境的，今天认为是最好的算法，也许明天就不是最好的了。限于篇幅，作者在介绍题例的时候一般也不对多种解法做分析，而是按照常规的理解来求解。关于算法设计的奥秘与乐趣读者可以从绪论中的求最大子序列和问题的求解中慢慢品味。 本书成稿周期颇长，从首次与清华大学出版社签约至今已有整整6年时间，期间也曾几次想放弃过，但每每想起许多挚友十多年来一直为之而默默地奋斗着，又总觉得自己应该来抛砖引玉，本书就是在这样的多次纠结中完稿的。 本书适合想从事编程工作的各类技术人员，以及就读于与计算机编程相关的各类大、中专相关专业的学生，以及工作后需要补学或温习数据结构和算法的各类读者。 本书诸多题例的代码来自众多ACMer的博客，而并非选自我的队员的代码，基本的想法也是为了使算法思想和代码实现更具代表性，当然，作者也对一些代码做了适当的修改。正如前面所述，由于成书周期过长，在代码引用中未一一列出各位ACMer的博客地址，还请见谅！限于作者的水平，书中的错误也恳请读者批评指正，有兴趣的读者请发送邮件到[email protected]。 感谢清华大学出版社的多位朋友为本书的出版所做的努力，同时也感谢我的研究生王超男、钟丽丽、盛贤良，曾经的ACM弟子陈聪、诸一行等为本书的出版所做出的贡献。 《数据结构与算法》被列为浙江省重点建设教材。 作者 于杭州下沙高教园区 2014年7月

版权图片链接