前言


目前，程序设计课程在中学已经较为普及，在许多大学更是理科生的必修课。社会上的编程培训班也十分流行。许多没有经过系统的计算机专业学习的学生，经过培训后掌握一两门语言，学会一些前端或后端应用的开发技能，虽然理论基础薄弱，也能求得一份程序员的职位。
然而，要成为一个优秀的程序员，有一门课是没有捷径可以绕过去的，那就是“数据结构”。优秀的公司是不会放心将重要的任务交给不懂数据结构和算法的程序员的，因为那些程序员没有效率的观念，一不小心就可能写出肆意挥霍计算资源的程序，让公司付出真金白银的代价。例如，低效的后端导致公司需要购买更多的服务器才能提供服务，甚至导致系统在访问量高时崩溃。如果有程序员信誓旦旦地说他的工作不需要用到数据结构和算法，那多半是因为他的水平不足以使他接触到需要数据结构和算法的任务。
总之，计算机专业的学习者需要掌握好数据结构与算法自不必说，非计算机专业的人士，不论是打算转行，还是已经转行做了程序员，都应该学好这门课。即便不做程序员，如果经常需要用编程来解决工作中的问题，学习这门课也是大有裨益的。因此，北京大学将“数据结构与算法”设置为所有理科生的必修课。
作者在北京大学讲授“数据结构与算法”“数据结构与算法实习”课程多年,并曾担任北京大学ACM国际大学生程序设计竞赛队教练9年。作者讲授的这些课程，既有面向高校非计算机专业的，也有面向计算机专业的。本书即是对这些课程教学经验的归纳与整合。
同类课程或教材，有些名为“数据结构”，有些名为 “数据结构与算法”，它们在内容上和本书并无很大区别。实际上，数据结构和算法，没有必要也无法严格区分，两者是你中有我、我中有你的关系。或者，将数据结构算作算法的一个分支也未尝不可，如著名教材《算法导论》中就包含大量数据结构的内容。
本书内容包括线性表、栈、队列、二叉树、堆、哈夫曼树、树和森林、并查集、散列表、二叉查找树、AVL树、红黑树、B\|树、B+树、图、最短路、最小生成树、拓扑排序、关键路径、内排序、外排序等。
阅读本书需要读者已经掌握Java语言程序设计的基础知识。对于学过Java程序设计的读者，本书非常适合作为第二门编程课的教材。
本书内容和习题按难度明确分级，不论是高校计算机专业还是非计算机专业的师生，都可以从中各取所需。不带★标记的是基本内容，适用于所有读者；计算机专业的读者应掌握带★标记的章节和习题；标记为★★的内容，则适用于高水平院校计算机专业的教学。
“数据结构与算法”是理论和实践必须紧密结合的课程。对各类数据结构和算法，不但要掌握其理论，还应该能够熟练地编程实现。作者考察许多国内外流行的数据结构和算法教材，发现许多教材多用伪代码或不完整的代码来描述数据结构和算法，很少给出能直接运行的完整程序。不但需要实打实编程解决的例题很少，而且配套的习题基本都是考查概念，或者只要求描述解决问题的过程，几乎不会要求写出完整的、完全正确的程序。即便一些教材中有编程习题，读者也无法评判自己编写的解题程序是否完全正确、无隐错(“隐错”英文俗称“bug”，指不容易发现的错误)。用这样的教材教学，虽然可以应付考研等笔试考试，但是难免有纸上谈兵之嫌。一旦碰到企业招聘要求现场写代码，或者考研复试要求上机写代码，往往会力不从心。
相比大多数数据结构和算法教材，本书的最大特点就是高标准的实践性。除了少数几个特别复杂的数据结构，95%的数据结构和算法都给出了完整可运行的代码，并且这些代码大部分都出现在具体的例题中。本书的代码要求JDK的版本至少是8。
本书的例题和编程习题，都可以在北京大学在线程序评测平台OpenJudge上提交解题程序。该平台包含两万多道编程题，程序提交后会自动评判对错。平台广泛用于北京大学“计算概论”“程序设计实习”“数据结构与算法”等编程类课程的教学。在这个平台上做题，必须极其严谨，应对众多不同测试数据，程序输出结果均必须一个字符都不能错，否则就不能通过。要完成本书的编程习题，必须对相应的数据结构和算法知识的每个实现细节都清楚地掌握，且编写的程序不能有隐错，这样的要求,比自己写个程序随意测试一下没发现问题就算对了要高得多，更远非在纸上写写画画的笔试型习题可比。
本书强调实践性还体现在倡导以下思想：一个数据结构的代码实现，不但要正确，还应健壮、易用和通用性强。健壮性要求数据结构的设计应有封装和隐藏功能，对外提供方便的接口，隐藏内部实现细节，并且提供的接口要防止数据结构从外部被不慎破坏。易用性要求数据结构支持一些通用的操作，比如用for循环即可遍历数据结构中的所有数据。通用性指的是数据结构应实现为模板的形式，可在数据结构中存储和处理不同类型的数据。为了达到上述目的，本书中数据结构的实现代码，用到了一些比较高级的Java语言特性，如内部类、匿名类、Lambda表达式和函数式接口、泛型等。因此，本书内容还包含一章“Java语言巩固与提高”，讲述Java语言的高级特性。
本书与时俱进，对一些数据结构的传统实现方法提出了革新。传统的数据结构教材往往用C语言描述或继承了用C语言描述时的写法。C语言没有可变长数组，因而对一些用可变长数组即可方便、高效实现的数据结构，传统教材却往往使用链表或其他不够直观的替代方法进行实现。例如，用链表实现图的邻接表和基数排序中的桶，用儿子\|兄弟表示法实现树结构。实际上，不论在程序设计竞赛还是在开发实践中，用支持可变长数组的语言如C++/Java/Python等实现上述数据结构时，使用可变长数组不但编程简单，而且由于CPU高速缓存机制的作用，程序运行效率也往往明显高于使用链表的做法。故本书在上述场合，介绍了传统C语言实现方法的同时，更强调在源代码中使用可变长数组的实现方法。
本书配套电子资料齐全，包括课程讲义以及100多个精心编写、风格简洁优美的程序源码。
作者水平有限，书中难免存在一些不足和疏漏之处，恳请读者批评指正。读者可以通过guo_wei@pku.edu.cn与作者沟通、交流。
感谢我的女儿兼校友郭小美审阅校对全部书稿，纠正了许多错误。

郭炜
2024年6月于北京大学信息科学技术学院