前言 背景 伴随着计算学科（Computing Discipline）近二十多年来的迅猛发展，相关专业方向不断细化和分化，相应地在计算机教育方面，人才培养的定位与目标呈现明显的多样化趋势，在知识结构与专业素养方面对人才的要求也在广度与深度上拓展到空前的水平。以最新版的计算学科教学大纲（ACM/IEEE Computing Curricula，以下简称CC大纲）为例，2001年制定的CC2001因只能覆盖狭义的计算机科学方向而更多地被称作CS2001。所幸的是，CC2001的意义不仅在于针对计算机科学方向的本科教学提出了详细的指导意见，更在于构建了一个开放的CC2001框架（CC2001 Model）。按照这一规划，首先应该顺应计算学科总体发展的大势，沿着计算机科学（CS）、计算机工程（CE）、信息系统（IS）、信息技术（IT）和软件工程（SE）以及更多潜在的新学科方向，以不同分卷的形式制定相应的教学大纲计划，同时以综述报告的形式做一概括统领；另外，不宜仍拘泥于十年的周期，而应更为频繁地调整和更新大纲，以及时反映计算领域研究的最新进展，满足应用领域对人才的现实需求。 饶有意味的是，无论从此后发表的综述报告还是各分卷报告都可看出，作为计算学科知识结构的核心与技术体系的基石，数据结构与算法的基础性地位不仅没有动摇，反而得到进一步的强化和突出，依然是计算学科研究开发人员的必备素养，以及相关应用领域专业技术人员的看家本领。以CC大纲的综述报告（Computing Curricula 2005 - The Overview Report）为例，在针对以上五个专业方向本科学位所归纳的共同要求中，数据结构与算法作为程序设计概念与技能的核心，紧接在数学基础之后列第二位。这方面的要求可进一步细分为五个层次：对数据结构与算法核心地位的充分理解与认同，从软件视角对处理器、存储器及显示器等硬件资源的透彻理解，通过编程以软件方式实现数据结构与算法的能力，基于恰当的数据结构与算法设计并实现大型结构化组件及其之间通讯接口的能力，运用软件工程的原理与技术确保软件鲁棒性、可靠性及其面向特定目标受众的针对性的能力。 自20世纪末起，我有幸参与和承担清华大学计算机系以及面向全校“数据结构”课程的教学工作，在学习和吸收前辈们丰富而宝贵教学经验的同时，通过悉心体会与点滴积累，逐步摸索和总结出一套较为完整的教学方法。做为数据结构与算法一线教学工作者中的一员，我与众多的同行一样，在为此类课程的重要性不断提升而欢欣鼓舞的同时，更因其对计算学科人才培养决定性作用的与日俱增而倍感责任重大。尽管多年来持续推进的教学改革已经取得巨大的进展，但面对新的学科发展形势和社会发展需求，为从根本上提高我国计算机理论及应用人才的培养质量，我们的教学理念、教学内容与教学方法仍然有待于进一步的突破。 与学校“高素质、高层次、多样化、创造性”人才培养总体目标相呼应，我所在的清华大学计算机系长期致力于培养“面向基础或应用基础的科学技术问题，具备知识创新、技术创新或集成创新能力的研究型人才”。沿着这个大方向，近年来我与同事们从讲授、研讨、作业、实践、考核和教材等方面入手，在系统归纳已有教学资源和成果的基础上，着力推进数据结构的课程建设与改革。其中，教材既为所授知识提供了物化的载体，也为传授过程指明了清晰的脉络，更为教师与学生之间的交流建立了统一的平台，其中重要性不言而喻。继2006年出版《数据结构与算法（Java语言描述）》之后，本教材的出版也是编者对自己数据结构与算法教学工作的又一次系统总结与深入探索。 原则 在读者群体的定位、体例结构的编排以及环节内容的取舍等方面，全书尽力贯彻了以下原则。 * 兼顾基础不同、目标不同的多样化读者群体 全书12章按四大部分组织，既相对独立亦彼此呼应，难度较大的章节以星号标注，教员与学生可视具体情况相应地灵活取舍。其中第1章绪论旨在尽快地将背景各异的读者引导至同一起点，为此将系统地引入计算与算法的一般性概念，确立时空复杂度的度量标准，并以递归为例介绍算法设计的一般模式；第2～7章为基础部分，涵盖序列、树、图、初级搜索树等基本数据结构及其算法的实现方法及性能分析，这也是多数读者在实际工作中最常涉及的内容，属于研读的重点；第8～10章为进阶部分，介绍高级搜索树、词典和优先级队列等高级数据结构，这部分内容对更加注重计算效率的读者将很有帮助；最后两章分别以串匹配和高级排序算法为例，着重介绍算法性能优化以及针对不同应用需求的调校方法与技巧，这部分内容可以帮助读者深入理解各类数据结构与算法在不同实际环境中适用性的微妙差异。 * 注重整体认识，着眼系统思维 全书体例参照现代数据结构普遍采用的分类规范进行编排，其间贯穿以具体而本质的线索，帮助读者在了解各种具体数据结构之后，通过概括与提升形成对数据结构家族的整体性认识。行文从多个侧面体现“转换-化简”的技巧，引导读者逐步形成和强化计算思维（computational thinking）的意识与习惯，从方法论的高度掌握利用计算机求解问题的一般性规律与方法。 比如从逻辑结构的角度，按照线性、半线性和非线性三个层次对数据结构进行分类，并以遍历算法为线索，点明不同层次之间相互转换的技巧。又如，通过介绍动态规划、减而治之、分而治之等算法策略，展示如何将人所擅长的概括化简思维方式与计算机强大的枚举迭代能力相结合，高效地求解实际应用问题。再如，从数据元素访问形式的角度，按照循秩访问（call-by-rank）、循位置访问（call-by-position）、循关键码访问（call-by-key）、循值访问（call-by-value）、循优先级访问（call-by-priority）等方式对不同的数据结构做了归类，并指明它们之间的联系与区别。 通过引入代数判定树模型以及对应的下界等概念，并讲解如何针对具体计算模型确定特定问题的复杂度下界，破除了部分读者对计算机计算能力的盲目迷信。按照CC大纲综述报告的归纳结论，这也是对计算学科所有专业本科毕业生共同要求中的第三点——不仅需要了解计算机技术可以做什么（possibilities）以及如何做，更需要了解不能做什么（limitations）以及为什么。 * 尊重认知规律，放眼拓展提升 在相关学科众多的专业基础课程中，数据结构与算法给学生留下的印象多是内容深、难度大，而如何让学生打消畏难情绪从而学有所乐、学有所获，则是摆在每位任课教师面前的课题。计算机教学有其独特的认知规律，整个过程大致可以分为记忆（remember）、理解（understand）、应用（apply）、分析（analyze）、评估（evaluate）和创造（create）等若干阶段，本书也按照这一脉络，在叙述方式上做了一些粗浅的尝试。 为加深记忆与理解，凡重要的知识点均配有插图。全书共计230余幅插图，借助视觉通道，从原理、过程、实例等角度使晦涩抽象的知识点得以具体化、形象化，也就是鲁迅先生“五到”读书法中的第一条“眼到”。 为加深对类似概念或系列概念的综合理解，完成认识上的提升，还普遍采用“对比”的手法。例如，优先级队列接口不同实现方式之间的性能对比、快速排序算法不同版本在适用范围上的对比，等等。又如，通过Dijkstra算法和Prim算法的横向对比，提炼和抽象出更具一般性的优先级搜索框架，并反过来基于这一认识实现统一的搜索算法模板。 为强化实践能力的培养，多从具体的应用问题入手，经逐步分析导出具体的解决方法。所列230余段代码，均根据讲述的侧重按模块划分，在力求简洁的同时也配有详实的备注解说。读者可以下载代码，边阅读边编译执行，真正做到“手到”和“心到”。几乎所有实现的数据结构均符合对应的抽象数据类型接口标准，在强化接口规范的同时，从习惯与方式上为读者日后的团队协作做铺垫与准备。 在分析与评估方面，介绍了算法复杂度的典型层次及分析技巧，包括常规的最坏情况和平均情况分析，以及分摊分析。针对递归算法，还着重介绍了递归跟踪法与递推方程法。另外从实用的角度，还引入了稳定性、就地性等更为精细的性能评估尺度，并结合部分算法做了相关的分析对比。 数据结构与算法这二者之间相辅相成的关系，也是本书着重体现的一条重要线索。为此，本书的体例与多数同类教材不尽相同。以排序算法为例，除最后一章外，大部分排序算法都作为对应数据结构的应用实例，分散编入相应的章节：其中起泡排序、归并排序、插入排序、选择排序等算法以排序器的形式归入序列部分；桶排序和基数排序归入散列部分；而堆排序则归入优先级队列部分。再如，图算法及其基本实现均前置到第6章，待到后续章节引入高级数据结构时再介绍其优化方法，如此前后呼应。行文讲述中也着力突出数据结构对高效算法的支撑作用，以及源自应用的算法问题对数据结构发展的反向推动作用，优先级队列之于Huffman编码算法、完全二叉堆之于就地堆排序、伸展树之于基于局部性原理的缓存算法、散列表之于数值空间与样本空间规模差异的弥合算法等，均属于这方面的实例。 与许多课程的规律一样，习题对于数据结构与算法而言也是强化和提升学习效果的必由之途，否则无异于“入宝山而空返”。当然，好的习题不应仅限于对讲授内容的重复与堆砌，而应更多地侧重于拓展与反思。本书的拓展型习题既包括对书中数据结构接口的扩充、算法性能的改进，也包括通过查阅文献资料补充相关的知识点。另外，一些难度极大或者难度不大但过程繁琐的内容，在这里也以习题的形式留待课后进一步探讨。在求知求真的过程中，质疑与批判是难能可贵的精神，反诘与反思更是创造创新的起点。从吸收到反思，在某种意义上也就是学习（learning）与反学习（unlearning）反复迭代、不断上升的过程。为此，部分习题的答案并非简单地重复正文的结论，甚至并不具有固定的答案，以给读者日后灵活的运用与创新留下足够的空间。 说明 书中凡重要的专业词汇均注有原文，插图中的标注也多以英文给出，因为编者认为这都是进一步探究以及与国际同行交流的基础。公式多采用接近代码的风格，而非严格的数学格式，以利于理解算法。 书中涉及的所有代码以及大量尚未在书中列出的辅助代码，均按Visual Studio工程形式分成50多组，并统一到名为DSACPP的解决方案之下，完整的代码包可从本书主页下载后直接编译执行。 为精简篇幅、突出重点，在一定程度上牺牲了软件规范性甚至计算效率，读者不必全盘效仿。比如，为尽量利用页面宽度和便于投影式播放，全文源代码统一采用Java风格编排，但代码的层次感却因此有所削弱，代码片段的切分也有过度之嫌。同样出于简化的考虑，代码中一些本可优化的细节也被忽略。以第11章的串匹配算法为例，总是直接调用计算成本较高的strlen()获取串长，在尚未对串结构做封装处理之前，这并非高效的做法。另外，对错误与意外的处理也采用了简化的处理方式。 限于编者的水平与经验，书中一定不乏纰漏与谬误之处，恳请读者及专家批评指正。 2011年夏末于清华园

• 暂无课件
• 样章下载
• 网络资源

扫描二维码
下载APP了解更多

版权图片链接