前言FOREWORD



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

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