第3版前言

数据结构课程是计算机科学、计算机工程、软件工程和电子信息工程等专业的专业基础课，是在各类应用系统开发中提高系统可靠性、提高系统运行安全性和效率的关键技术之一。学好数据结构和算法，有利于后续的专业课程学习，包括操作系统、数据库系统、计算机体系结构、人工智能、信息安全和密码学、系统分析与设计等，这些课程都需要应用数据结构的知识，所以在国家研究生考试、软件水平考试、各高科技公司的面试中都少不了数据结构方面知识的考查。作者于1985年公派到日本东京的某大学当客座研究员，研究室的教授是刚从日立公司退下来的软件质量保证部的部长菅野先生，当时还兼任日本软件质量管理协会的干事长。第一次见面他就来了个突袭，出了两道题让我当场解答，一道是程序设计的题，一道是数据结构的题，记得是计算关键路径，我是在清华大学计算机系教数据结构课程的，当然这难不倒我，但这也说明了学习数据结构课程的重要性。

从2016年以来，作者受清华大学出版社委托，开始《数据结构算法解析》一书的写作。从收集题目到逐一做出解答，上机测试，花费了三年时间。该书包含了2000多道习题，几乎将所有课本上提到的因篇幅限制没有深入挖掘的内容（主要是算法实现）都给出了C语言代码，并做了调试。2020年开始了《数据结构（C++版）》的第3版升级工作，按照面向对象系统的要求，整理了书中所有算法，还扩充了部分章节的内容。

从2021年开始准备本书第3版的升级工作，第3版与第2版比较，各章节变化不大，但修改和增加了一些内容。举例说明如下:

第3章栈和队列中增加了双端队列的内容，还增加了与递归相关的算法设计技术，包括分治、减治、回溯、贪心法的例题讲解。

第5章树与二叉树增加了二叉树顺序表示相关操作的实现，以及树的双亲表示、子表表示操作的实现。

第6章树与二叉树的应用中修改了AVL树的插入与删除算法的实现，增加了中序线索二叉查找树的查找、插入与删除算法的实现，以及Huffman编码的译码和解码算法的实现。

第7章图中增加了求有向图的强连通分量算法的实现，求任意权值的单源最短路径Bellmanford算法的实现，以及修改了求关键路径算法的实现。

第8章查找中增加了最优二叉查找树的构建算法的实现，增加了数字查找树的插入与删除算法的实现，修改了B树的插入与删除算法的实现。

第9章内排序中增加了两路插入排序算法的实现，增加了三路快速排序算法的实现，修改了胜者树和锦标赛排序算法的实现，修改了LSD基数排序算法的实现，增加了3个时间复杂度小于O(nlog2n)的排序算法的实现，增加了用于选择的3个算法的实现。

第10章外排序中为方便学生上机模拟外排序，脱离了C的文件读写操作，全部采用数组模拟文件，自行设计了读写物理块和记录的函数，实现了多路平衡归并排序、置换选择排序、最佳归并树和使用最佳归并树实现多路归并排序等算法。

第3版与第2版相比，还做了如下改进:

(1) 对全书的算法全部重新测试和调试。实际上，对计算机程序做测试和调试是两个概念，测试是“查错”，调试是“改错”。以前的课本，涉及的例题和算法的实现都可能有逻辑错误，只拿少量数据做了确认，也就是说，用一些合理的运行数据，证明算法实现了或达到了预期的效果。但是很少检查它们在不合理的输入下是否能检错、通过出现的错误行为发现代码中可能存在的Bug。这次，作者对书中的所有算法都重新做了黑盒测试，在输入方面，选择了边界、典型和超出边界的数据作为测试用例，运行程序，看结果是否正确。不但要确认算法做了它应该做的事，还要检查它是否做了不该做的事，如果结果有误，查错并改正之。

（2） 针对全书的算法，都赋予了编号，如“程序230”。书中对每一个程序，都注明了它存放于哪个程序文件中，如“prg230.cpp”或“DataList.h”，在其他使用这个程序的主调程序中，使用了#include “prg230.cpp”指明被调用程序所在的文件。这样便于读者在组织自己的程序系统时找到书中算法的调用关系。

〖2〗〖2〗(3) 对各章的习题做了修改。除保留了简答题和算法题外，增加了单项选择题、判断题等题型的习题。新增习题多数取材于清华大学计算机系列教材，包括作者以前编写的辅助教材《数据结构（C语言描述）》《数据结构习题解析》《数据结构精讲与习题解答》《数据结构使用面向对象方法（C++语言）》《数据结构算法解析》等。这些习题覆盖了数据结构各章的知识点，从不同侧面训练如何运用数据结构的基本知识解决应用问题的能力。经过筛选，习题的难度都不大。如果读者有余力，可以参考《数据结构算法解析》一书，该书中有正式教材收录的习题及其解答，还有正式教材没有收录的习题及其解答。

本书有些例题综合运用了前面的知识，由于C没有提供C++常用的模板机制，求解例题相对复杂一点。例如，使用最佳归并树实现m路平衡归并排序时，由于加入了空归并段，导致某趟归并的归并路数少于m，程序要很好地通过最佳归并树控制各次归并的归并路数，并在用大根堆实现m路归并时每次选最小，用置换选择完成归并排序，等于把第10章前面的几个知识点都用上了，还遇上了数组超界、冲掉其他变量的计算结果等编程问题，需要读者下功夫钻研，这对掌握知识、提高技能很有帮助。本书第2版出版后，作者开始另一本辅助教材《数据结构精讲与习题详解》（第2版）的写作，接着又结合考研和求职的需要，开始了《数据结构算法解析》的写作，在此期间，对本书第2版的内容、知识体系编排和算法的有效性有了一些体会，又回过头来修改本书，所以本书实际上是第2版的修订本。

自从1978年美籍华人冀中田第一次在中国讲授数据结构课开始，很多老师对课程的内容和讲授方法做了大量的研究，也可以说是在做中学，总结出许多好的经验，使得课程的教学与当时相比进步了很多。作者在这门课程的教学中也积累了一些心得，希望与正在学习这门课程的同学们分享，这是作者修改这本教材的初衷。

由于数据结构课程学时的限制（多数学校为48～64学时），作为本科生的教材，包含的知识容量应有一定限度，可以选择部分章节进行教与学。若知识点太少，学生在未来的工作实践中可联想的思考空间狭窄，解决问题的能力受限；若知识点太多，必然沦为百科全书式的阅读，基础不牢靠，同样使得解决问题的能力受限。教材可以适当地覆盖，但教学可以根据教师的理解进行节选。通过教学实践证明，本书的第2版在内容上取材是恰当的，范围上取材的深度和广度也是恰当的，但联想不够，某些算法的实现上偏向使用伪代码描述，造成部分读者在学习上和实践上的困惑。本书第3版做了适当修改，各章增加了“想想看”，目的是增加一些互动环节。这些思考题触及的都是可联想的内容，或者是对理解正文有用的知识“点拨”。所谓“学问”就是有“学”还要有“问”。正面的“问”有助于理解“应该做什么”；反面的“问”有助于理解“不该做什么”。

因为作者的水平有限，可能在某些方面有考虑不周的地方，虽然作者对全部书稿通读并修改了两次，但书中难免还存在疏漏或错误，诚恳希望读者提出宝贵意见。

作者

2023年1月于清华大学