出 版 说 明
信息时代早已显现其诱人魅力，当前几乎每个人随身都携有多个媒体、信息和通信设备，享受其带来的快乐和便利。
我国高等教育早已进入大众化教育时代，计算机技术发展很快，知识更新速度也在增长，社会对计算机专业学生的专业能力要求也在不断提高，这就使得我国目前的计算机教育面临严峻挑战。我们必须更新教育观念——弱化知识培养目的，强化对学生兴趣的培养，加强培养学生理论学习、快速学习的能力，强调培养学生的实践能力、动手能力、研究能力和创新能力。
教育观念的更新，必然伴随教材的更新。一流的计算机人才需要一流的名师指导，一流的名师需要精品教材的辅助，而精品教材也将有助于催生更多一流名师。名师们在长期的一线教学改革实践中，总结出了一整套面向学生的独特的教法、经验、教学内容等。本套丛书的目的就是推广他们的经验，并促使广大教育工作者更新教育观念。
在教育部相关教学指导委员会专家的帮助和指导下，在各大学计算机院系领导的协助下，清华大学出版社规划并出版了本系列教材，以满足计算机课程群建设和课程教学的需要，并将各重点大学的优势专业学科的教育优势充分发挥出来。
本系列教材行文注重趣味性，立足课程改革和教材创新，广纳全国高校计算机优秀一线专业名师参与，从中精选出佳作予以出版。
本系列教材具有以下特点。
1. 有的放矢
针对计算机专业学生并站在计算机课程群建设、技术市场需求、创新人才培养的高度，规划相关课程群内各门课程的教学关系，以达到教学内容互相衔接、补充、相互贯穿和相互促进的目的。各门课程功能定位明确，并去掉课程中相互重复的部分，使学生既能够掌握这些课程的实质部分，又能节约一些课时，为开设社会需求的新技术课程准备条件。
2. 内容趣味性强
按照教学需求组织教学材料，注重教学内容的趣味性，在培养学习观念、学习兴趣的同时，注重创新教育，加强“创新思维”“创新能力”的培养、训练；强调实践，案例选题注重实际和兴趣度，大部分课程各模块的内容分为基本、加深和拓宽内容3个层次。
3. 名师精品多
广罗名师参与，对于名师精品，予以重点扶持，教辅、教参、教案、PPT、实验大纲和实验指导等配套齐全，资源丰富。同一门课程，不同名师分出多个版本，方便选用。
4. 一线教师亲力
专家咨询指导，一线教师亲力；内容组织以教学需求为线索；注重理论知识学习，注重学习能力培养，强调案例分析，注重工程技术能力锻炼。
经济要发展，国力要增强，教育必须先行。教育要靠教师和教材，因此建立一支高水平的教材编写队伍是社会发展的关键，特希望有志于教材建设的教师能够加入到本团队。通过本系列教材的辐射，培养一批热心为读者奉献的编写教师团队。

清华大学出版社前言
本书内容丰富,包含了计算机科学与技术的许多重要方面,书中分析问题和解决问题的思路和方法新颖,技巧性强,对学生的计算机软件素质的培养作用明显。通过学习本书，读者可具备选用合适的数据结构与算法设计方法编写质量高、风格好的应用程序,评价算法优劣的能力。
本书采用C++作为描述语言对数据结构与算法的知识进行介绍,由于使用了模板程序设计技术,与传统采用面向过程的观点相比优势较大,使所设计的程序更容易实现代码重用,在提供通用性和灵活性的同时,又保证了学习效率。本书融入了面向对象程序设计的思想,读者通过学习可进一步提高面向对象程序设计的能力。
全书共分为11章。第1章是基础知识,介绍了基本概念及其术语,抽象数据类型的实现,讨论了算法的概念和算法分析的简单方法。为了便于学习，读者应具有一定的C++程序设计的基础。
第2章引入了线性表,详细讨论了线性表的顺序存储结构与链式存储结构。在讨论链式存储结构时,首先用传统方法实现线性表,然后在此基础之上,以链表结构保存当前位置和元素个数,这样可使学习者在难度增加不大的情况下体会改进算法效率的方法。
第3章介绍了栈和队列,讨论了栈和队列的顺序存储结构与链式存储结构,以及如何用栈实现表达式求值,通过学习能掌握各种栈和队列的实现与使用,为操作系统原理和编译原理等后续课程的学习打下良好的基础。此外，本章还讨论了优先队列,使队列应用更加广泛。
第4章介绍了串,详细讨论了串的存储结构与模式匹配算法,为开发串应用(如实现文本编辑)软件打下坚实的基础。
第5章介绍了数组和广义表,详细讨论了数组、特殊矩阵、稀疏矩阵和广义表的存储结构及实现方法,提出并实现了广义表的使用空间表存储结构。
第6章介绍了树,讨论了二叉树、线索二叉树、树、森林及其哈夫曼树的结构及其实现,并应用哈夫曼编码实现了压缩软件。
第7章介绍了图,实现了图的常用存储结构,并讨论了图的相关应用,实现了相应算法(如求最小生成树的Prim算法与Kruskal算法,求最短路径的Dijkstra算法与Floyd算法)。
第8章介绍了查找,讨论了静态表的查找、动态查找表与哈希表,还讨论了二叉排序树、平衡二叉树与B树,并实现了所有算法。
第9章介绍了排序,以简捷方式实现各种排序算法。
第10章介绍了文件,讨论了主存储器、辅助存储器以及各种常用文件结构,并对数据库中经常采用的VSAM文件进行了实例研究,对读者研究与学习数据库有一定的帮助。
第11章介绍了算法设计和分析技术,详细讨论了分治算法、贪婪算法、回溯法的使用方法和实现,对算法分析技术和可计算问题也进行了深入浅出的讨论。对读者的算法设计和分析的理论与实践都有极大的帮助。
对于初学者,数据结构与算法的代码实现是相当困难的,因此本书对所讨论的数据结构与算法都加以实现并进行了严格测试,提供了完整的测试程序,供读者学习参考。如果只会使用已有的数据结构编写简单的程序，不利于读者对数据结构与算法的深入理解与研究，也不利于面对新数据结构时算法处理能力的提高，因此本书配有习题，其中既包括了基本练习题,又包括了仿照书中数据结构构造新数据结构的题目以及改造已有算法的题目。
对于一部分学有余力的学习者，本书各章还提供了实例研究。这些实例包括对正文内容的补充(例如9.9节中的用堆实现优先队列)、离散数学中著名算法的实现(例如7.7节中的周游世界问题——哈密顿圈)以及应用所学知识解决实际问题(例如6.9节中的哈夫曼压缩算法)。读者通过对实例的研究学习,可提高实际应用数据结构与算法的能力,这当然会有一定的难度,但应比读者所想象的更易学习与掌握。
为了尽快提高读者的学习收获,本书各章还提供了深入学习导读,包含了本书作者实现相关数据结构与算法的最原始思想的资料来源以及进一步学习所需阅读的参考资料,可为教学提供极大的方便。
本书在内容组织上特别考虑了读者的可接受性;在算法实现时,重点考虑了程序的可读性,为实现更强的功能,一般采用启发的方式在习题、上机实验或课程设计中实现,这样容易激发读者的学习兴趣,使读者感到自己具有能发展或改进已有算法的能力,也会使读者感到自己已达到计算机高手的自信心。
下面，讨论一下在国外数据结构与算法教材中上机时喜欢采用的STL。实际上,STL是AT&T贝尔实验室和HP研究实验室的研究人员将模板程序设计和面向对象程序设计的原理结合起来,创造的一套研究数据结构与算法的一种统一的方法,现在已成为C++标准库的一部分。STL提供了实现数据结构的新途径。它将(数据)结构(即组织数据的存储结构)抽象为容器,将之分为3类: 序列容器、关联容器和适配器容器。通过使用模板和迭代器,STL库使得程序员能够将广泛的通用算法应用到各种容器类上。据本书作者研究与了解,STL库只覆盖了数据结构中的线性结构和树结构,并没有覆盖图部分,因此,对数据结构来讲,STL库并不完备。同时,如果读者上机编程都只使用STL库解决数据结构的相关算法,可能使读者在数据结构编程方面,只会使用STL库,而不能独自设计新数据结构。本书采用模板方法实现了书中所有数据结构的算法,应比STL库更完备;同时STL库中包含的源代码可读性差,不适合作为教学使用,本书的算法源程序首要强调可读性,使读者易于接受与模仿,并且读者可进行改进或修改算法实现。因此在某种意义上讲,本书提供的关于数据结构与算法实现的类模板与函数模板是一种GTL(general template library)或OSGTL(open source general template library),读者也可用本书提供的软件包(具体内容请参看附录C)来进行实际数据结构与算法方面的软件开发。当然,通过本书的学习,再返回来学习STL库的应用,将会事半功倍,读者只要找一本介绍STL的书籍或从网上找一些介绍使用STL库的文档,并用SLT库试着编程即可完全掌握SLT库的使用。
本书所有算法都同时在Visual C++ 6.0、Visual C++ 2017、DevC++ v5.11和CodeBlocks v16.01中通过测试。读者可根据实际情况选择适当的编译器,建议选择Visual C++ 6.0。
在教学过程中，可采取多种方式来使用本书讲授数据结构、数据结构与算法分析、数据结构与算法设计、数据结构与算法等课程,根据学生的背景知识以及课程的学时数来进行内容的取舍。为满足不同层次的教学需求,本书使用了分层的思想,分层方法如下: 没加星号“”及“”的部分是基本内容,适合所有读者学习;加星号“”的部分是适合计算机专业的读者深入学习的选学内容;加两个星号“”的部分适合于感兴趣的同学研究,尤其适合于那些有志于ACM竞赛的读者加以深入研究。
作者为本书提供了全面的教学支持，除了向专业教师提供教学资源外，普通读者也可在清华大学出版社官方网站下载如下教学参考内容: 
（1） 教学用PowerPoint幻灯片课件。
（2） C++编译环境等相关资源。
（3） 本书作者开发的包含所有本书所讲数据结构与算法的类模板与函数模板的软件包（包括软件包说明文档、软件代码及软件包测试程序）。
（4） 全书所有例题、数据结构相关的类模板及算法相关函数模板在Visual C++ 6.0、Visual C++ 2017、DevC++ v5.11和CodeBlocks v16.01开发环境中的测试程序。
（5） 多套数据结构与算法模拟试题、参考答案和相关测试程序，以供学生期末及其考研复习，也可供教师出考题时参考。
通过扫描二维码可观看全书所有例题、数据结构相关的类模板及算法相关函数模板的测试程序演示视频,其中第1个二维码对应于Visual C++ 6.0开发环境的测试程序演示视频,第2个二维码对应于Visual C++ 2017开发环境的测试程序演示视频,第3个二维码对应于DevC++ v5.11开发环境的测试程序演示视频,第4个二维码对应于CodeBlocks v16.01开发环境的测试程序演示视频。
在附录D中介绍了Visual C++ 6.0、Visual C++ 2017、DevC++ v5.11和CodeBlocks v16.01开发环境建立工程的步骤,可通过扫描二维码观看具体操作视频。
程艳红、袁平、陈良银、游倩、张银、文芝明等人对本书做了大量的工作,包括提供资料,调试算法,参与了部分内容的编写,在此特向他们表示感谢;作者还要感谢为本书提供直接或间接帮助的每一个朋友,他们热情的帮助和鼓励激发了作者写好本书的信心以及写作热情。
本书的出版要感谢清华大学出版社的编校人员。他们为本书的出版倾注了大量热情，也由于他们具有前瞻性的眼光，才让本书得以顺利出版。
尽管作者有良好而负责任的写作态度,并做了最大努力,但书中难免有不妥之处,敬请各位读者不吝赐教,以便作者学习提高。

作者2020年8月