数据结构与算法_郭炜_9787302696360_厦门外图集团有限公司

本书内容全面、细致、通俗易懂。涵盖线性表、栈和队列、树和二叉树、堆、哈夫曼树、并查集、AVL树、红黑树、B树和B+树、串、图、散列表等数据结构，以及枚举、二分、递归、分治、动态规划、贪心、深搜、广搜、最短路、最小生成树、拓扑排序、关键路径、内外排序等算法。对各类数据结构和算法，不但要掌握理论，还应熟练地编程实现。本书的最大特点是高标准的实践性。除了少数几个特别复杂的数据结构，95%的数据结构和算法都给出了完整可运行的代码，一共130多份，并且这些代码几乎都出现在具体的例题中。本书的例题和编程习题，都可以在北京大学在线程序评测平台OpenJudge上提交解题程序并自动评判对错。本书内容和习题按难度做了明确分级，因此不论是高等学校计算机专业还是非计算机专业的师生，都可以从中各取所需用于教学。本书既可以用作数据结构和算法入门教材，又可以作为考研、找工作面试的提高秘籍，还可以用于程序设计竞赛的基础培训。

前言
要成为的程序员，必须学习“数据结构与算法”课程。虽然同类课程或教材有些只是名为“数据结构”，没有提到“算法”，但实际上，数据结构和算法，没有必要也无法严格区分，两者是“你中有我、我中有你”的关系。或者，将数据结构算作算法的一个分支也未尝不可，如著名教材《算法导论》，其中就包含大量数据结构的内容。本书中涉及的问题，如果需要将数据以复杂的方式组织起来，就归类为数据结构；否则，就归类为算法。
大多数课程或教材，用C语言实现数据结构和算法。然而，相比C++语言，甚至Java和Python语言，用C语言实现数据结构和算法有明显的劣势。C语言没有对面向对象程序设计方法的支持，实现的数据结构无法做到“封装”和“隐藏”。不支持“封装”，导致代码缺乏局部性，难以理解，难以维护。不支持“隐藏”，导致无法防止数据结构从外部被不慎破坏，缺乏安全性。C语言不支持泛型程序设计，导致实现的数据结构和算法缺乏通用性或可重用性。例如，编写一个可以对任何数据类型的数组排序的函数、编写一个可以存放任何数据类型的二叉查找树数据结构是比较困难的，即便实现了，这样的函数和数据结构的使用方式也较为麻烦和不自然。C语言无可变长数组，这导致在实现图的邻接表、树等数据结构时不得不采用链表、儿子兄弟树等编程效率或运行效率不佳的方案。总之，“数据结构与算法”是理论结合实践的课程，对数据结构和算法的编程实现，不但应该正确，还应在工程上是优美的，即安全、简洁、好用、可重用，这用C语言很难做到。目前，程序设计方法的潮流是面向对象、泛型和函数式编程，C语言对这三大特性均无支持，故作者认为，当前的数据结构和算法教学，亟须改革，将用C语言描述数据结构和算法，转变为用支持面向对象、支持泛型和函数式编程的C++语言描述。
然而，系统掌握C++语言有较高的学习成本，即便对已经掌握C语言的编程者也是如此，这是阻碍C++语言在数据结构和算法教学中得以推广的主要原因。实际上，C++语言的大量特性，如异常处理、继承、多态等，是为了编写大型程序而设计的，数十行或一百多行代码即可实现的数据结构和算法不需要使用这些特性，因而用C++语言进行数据结构与算法教学，其实无须学员系统地掌握C++语言，只须学会C++语言中一小部分最核心的面向对象、泛型和函数式编程特性即可。为此，作者抽取了这部分核心特性，精心编写了“C++语言快速入门和温故知新”一章，依此章进行4个课时的教学，可使学过C语言的学生掌握C++语言的精髓，从而可以充分理解本书的所有程序，并用C++语言编写小型程序。本书完全适用于只学过C语言的读者，故虽然所有程序均用C++语言实现，却依然命名为《数据结构与算法(C/C++语言实现)》。
作者在北京大学讲授“数据结构与算法”和“数据结构与算法实习”课程多年,并曾担任北京大学ACM国际大学生程序设计竞赛队教练9年。作者讲授的这些课程，既有面向非计算机专业的，也有面向计算机专业的。本书即是对这些课程教学经验的归纳与整合。
本书数据结构部分包括线性表、栈、队列、二叉树、堆、哈夫曼树、树和森林、并查集、散列表、二叉查找树、AVL树、红黑树、B树、B+树、图、矩阵等内容。算法部分包括枚举、二分、递归、深度优先搜索、广度优先搜索、贪心、动态规划、内排序、外排序、最短路、最小生成树、拓扑排序、关键路径等内容。数据结构部分和算法部分交替讲述。本书内容覆盖计算机专业408考研大纲。
相比大部分同类教材，本书的知识覆盖面更广，尤其是算法部分。
阅读本书需要读者已经掌握C语言程序设计的基础知识。对于学过C语言程序设计的读者，本书非常适合作为第二门编程课的教材。
本书内容和习题按难度明确分级，不论是高校计算机专业还是非计算机专业的师生，都可以从中各取所需。不带“★”标记的是基本内容，适用于所有读者；计算机专业的读者应掌握带“★”标记的章节；标记为“★★”的内容，则适用于高水平院校计算机专业的教学；少数标记为“★★★”的例题和习题，难度与大学生程序设计竞赛的中等题相当。有些例题习题来自早年的程序设计竞赛，或在竞赛中本就是简单题，难度不高，因而没有“★★★”标记，甚至没有“★”标记。
作者考察了许多国内外流行的数据结构与算法教材，发现许多教材中多用伪代码，或不完整的代码来描述数据结构和算法，很少给出能直接运行的完整程序。不但需要实打实编程解决的例题很少，而且配套的习题，基本都是考查概念，或只要求描述解决问题的过程，几乎不会要求写出完整的、完全正确的程序。即便一些教材中有编程习题，读者也无法评判自己编写的解题程序是否完全正确无隐错。用这样的教材教学，虽然可以应付考研等笔试考试，但是难免有纸上谈兵之嫌。一旦碰到企业招聘要求现场写代码，或者考研复试要求上机写代码，往往力不从心。
相比大多数数据结构和算法教材，本书的最大特点就是高标准的实践性。除了少数几个特别复杂的数据结构，95%的数据结构和算法都给出了完整可运行的代码，并且这些代码大部分都出现在具体的例题中。
本书的例题和编程习题，都可以在北京大学在线程序评测平台OpenJudge上提交解题程序。平台广泛用于北京大学“计算概论”“程序设计实习”“数据结构与算法”等编程类课程的教学。要在OpenJudge上完成本书的编程习题，必须对相应的数据结构和算法知识的每个实现细节都清楚地掌握，且编写的程序不能有隐错，这样的要求,比自己写个程序随意测试一下没发现问题就算对了要高得多，更远非在纸上写写画画的笔试型习题可比。OpenJudge的具体使用方法见附录。
本书配套电子资料齐全，包括课程讲义以及130多个风格简洁优美的程序源码。
本书还另有Python语言版和Java语言版，均已经由清华大学出版社出版。
作者水平有限，书中难免存在一些不足及疏漏之处，恳请读者批评指正。读者可以通过guo_wei@pku.edu.cn与作者沟通、交流。
作者的女儿兼校友郭小美审阅并校对了全部书稿。一部分程序由她从作者编写的其他语言的程序改写为C++程序，特此感谢。

郭炜
于北京大学信息科学技术学院
2025年4月

你还可能感兴趣

我要评论