资 源 简 介
资料详情
本书的初稿完成于2009年冬季，随后在清华大学经过了三个学期共四个课堂的试用，根据各方的反馈意见做过调整补充之后，第1版于2011年夏季由清华大学出版社正式出版发行。此后，又在清华大学经过两个学期共三个课堂的教学实践，并汇总读者的反馈进一步修订完善之后，第 2版终于2012年夏季出版发行，也就是目前读者所看到的这个版本。
第2版继承并强化了此前版本的叙述风格，基本保留了总体的体例结构，同时在针对性、简洁性、实用性和拓展性等方面，也做了大量的修改、删节与扩充。与此前的版本相比较，主要的变化包括以下几个方面：
针对多种数据结构的算法实现及其性能分析，精简了行文叙述与代码实现，比如有序向量的查找、树和图的遍历、Huffman编码、平衡二叉搜索树的重平衡、二叉堆的调整等。
更换并补充了大量的实例和插图，比如向量、词典、关联数组、高级平衡二叉搜索树和优先级队列等数据结构，以及表达式求值、KMP、BM、平衡二叉搜索树的重平衡、字符串散列、快速排序、中位数及众数等算法的原理及过程等等，插图增至260多组。
重写了多个章节的总结部分，比如针对各类查找算法、串匹配算法，就其性能特点均做了统一的归纳与梳理，指明其中的关键因素以及不同的适用范围。
进一步规范和统一了几个基本概念的定义及其表述方式，使得各章节之间的相互引述更趋一致，比如栈混洗、真二叉树、完全二叉树、满树、闭散列策略等概念的定义，以及遍历序列、红黑树不同类型节点等概念的图解示意方式。
细化了针对一些关键知识点的讲解，比如第1章的渐进复杂度层次和伪复杂度、第8章中B树及kd-树的引入动机、第11章中BM算法好后缀策略中的GS［］表构造算法等。
添加了大量的习题，总量已超过280道。在帮助读者梳理主要知识点、加深对讲解内容理解的同时，还从以下方面为他们的进一步拓展，提供了必要的线索：插入排序算法性能与逆序对的关系、选择排序算法性能与循环节的关系、插值查找、指数查找、马鞍查找、CBA式排序算法平均性能的下界、栈混洗甄别、栈堆、队堆、算术表达式的组合搜索、键树、关联矩阵、Prim算法与Krusal算法的正确性、欧氏最小支撑树、并查集、计数排序、四叉树、八叉树、范围树、优先级搜索树、树堆、AVL树节点删除算法的平均性能、AVL树的合并与分裂、堆节点插入算法的平均性能、支持重复元素的二叉搜索树、双向平方试探、轴点构造算法版本C、希尔排序算法的正确性，等等。
提供了一批相关的参考文献，包括经典的教材专著20余册、拓展的学术论文30余篇。
修正了多处排版问题及若干实质错误。请此前版本的读者下载勘误表并做相应更正，同时感谢我的读者、学生和同行，他们的意见与建议是本教材不断完善的保证。
作为万物之灵的人，与动物的根本区别在于理性，而计算则是理性的一种重要而具体的表现形式。计算机是人类从事计算的工具，是抽象计算模型的具体物化。基于图灵模型的现代计算机，既是人类现代文明的标志与基础，更是人脑思维的拓展与延伸。
尽管计算机的性能日益提高，但这种能力在解决实际应用问题时能否真正得以发挥，决定性的关键因素仍在于人类自身。具体地，通过深入思考与分析获得对问题本质的透彻理解，按照长期积淀而成的框架与模式设计出合乎问题内在规律的算法，选用、改进或定制足以支撑算法高效实现的数据结构，并在真实的应用环境中充分测试、调校和改进，构成了应用计算机高效求解实际问题的典型流程与不二法门。任何一位有志于驾驭计算机的学生，都应该从这些方面入手，不断学习，反复练习，勤于总结。
本章将介绍与计算相关的基本概念，包括算法构成的基本要素、算法效率的衡量尺度、计算复杂度的分析方法与界定技巧、算法设计的基本框架与典型模式，这些也构成了全书所讨论的各类数据结构及相关算法的基础与出发点。
