数据结构与算法分析_(美) 马克·艾伦·维斯著_9787302710202

本书是数据结构和算法分析的经典教材，使用C++作为具体的实现语言。内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、搜索树算法、后缀数组、后缀树、kd树、配对堆，以及算法分析、摊还分析、算法设计技术等。本书把算法分析与数据结构有机结合起来，深入分析每种算法，内容全面、推导缜密，并细致讲解精心构造程序的方法。本书概念清楚，逻辑性强，内容新颖，适合作为高等学校计算机及相关专业的教材或参考书，也适合计算机工程技术人员参考。

前言

目的/目标

本书是《数据结构与算法分析: C++语言描述》的第4版，讨论了数据结构——大量数据的组织方法，以及算法分析——估算算法的运行时间。随着计算机的运行速度越来越快，对能够处理大量数据的程序需求变得更加迫切。由于输入量很大时，低效程序的问题更为突出，因此需要更加关注效率。在编码之前对算法进行分析，学生可以判断特定的解决方案是否可行。在本书中，学生通过具体问题可以看到精心的实现能够将大量数据的处理时间从几个世纪减至少于1s。因此，如果没有运行时间的约束，就不会提出算法和数据结构。在某些情况下，对于影响运行时间的微小细节都需要进行细致的探究。

一旦确定了解决方案，接下来就是编写程序。随着计算机的功能越来越强大，要求解决的问题也变得庞大和复杂，需要开发更加复杂的程序。本书的目标是教授学生良好的程序设计技能和算法分析能力，使他们能够编写高效的程序。

本书适用于高年级本科生的“数据结构”课程或研究生第一学年的“算法分析”课程，学生应该具有中级编程能力，包括指针、递归及面向对象程序设计等，此外还应该具有离散数学的基础。

处理方法

虽然本书的大部分内容与语言无关，但编程需要使用特定的语言，本书选择C++语言。

C++已成为主流的系统编程语言，除了修复了C语言的语法缺陷，还提供了类和模板以实现抽象数据类型的泛型数据结构。

编写本书最困难的部分是确定C++所占的篇幅。使用过多的C++特性将使本书难以理解，使用太少又会使得读者感觉本书只是支持类的C语言版本教材。

本书采取的方法是基于对象的处理方式，几乎没有使用继承。本书使用类模板描述泛型数据结构，避免使用深奥的C++特性，但使用了vector类和string类(如今属于C++标准的一部分)。本书以前的版本以接口与实现分离的方式创建类模板，虽然这是有争议的首选方法，但编译器问题使得读者很难使用代码。因此，本书的在线代码将类模板作为单个文件，没有将接口与实现分离。第1章综述了本书用到的C++特性，描述了类模板的处理方法。附录A介绍了如何使用分离式编译重写类模板。

本书提供使用C++和Java实现数据结构的完整版在线代码，类似的编码约定使得这两种语言的结构对比更加明显。

第4版的重要变化

本书修正了一些错误，修订了部分内容，提高了表述的清晰度。此外:

 第4章增加了AVL树删除算法的实现，这是很多读者提出的要求。

 第5章进行了大幅修订和扩充，包括两种较新的算法——杜鹃散列和跳房子散列，增加了通用散列，简要讨论了C++11引入的unordered_set和unordered_map类模板。

 第6章基本没有变化，只是在二叉堆的实现中使用了C++11的移动操作。

 第7章增加了关于下界的证明，以及基数排序。排序代码使用了C++11的移动操作。

 第8章增加了Seidel和Sharir对union/find算法的性能分析，并证明了O(Mα(M, N))界，替换了以前版本的较弱时间界O(MlogN)。

 第12章增加了后缀数组和后缀树，包括Karkkainen和Sanders提出的构建后缀数组的线性时间算法（及其实现），删除了确定性跳跃表和AA树。

 本书代码均使用C++11进行了更新。值得注意的是，这意味着使用了C++11的新特性，包括auto关键字、基于范围的循环、移动构造函数和移动赋值，以及统一初始化。

内容提要

第1章复习离散数学和递归。我相信熟悉递归的唯一方法是反复研读好的用法。因此，除了第5章，递归遍及每一章的示例。此外，本章回顾C++基本语法，包括C++的类模板和一些重要结构。

第2章是算法分析，首先阐释了渐近分析及主要缺点。然后提供了许多示例，深入探讨了对数运行时间。接着将简单的递归程序转换为迭代程序，并进行直观地分析。最后介绍了更复杂的分治程序，但是求解递归关系式将在第7章详细讨论。

第3章包括表、栈和队列，讨论了STL中的容器vector和list，涉及迭代器，并提供了vector和list的重要子集的代码实现。

第4章讨论树，重点是搜索树，包括外部搜索树（B树）。树的应用介绍UNIX文件系统和表达式树。然后讨论了AVL树和伸展树，搜索树的实现细节将在第12章讨论。树的其他应用，如文件压缩和博弈树，将在第10章介绍。最后考虑外部介质的数据结构，包括STL中的容器set和map，作为重要的例子，说明如何使用3个单独的map高效解决一个问题。

第5章讨论散列，包括分离链接法、线性探测法与平方探测法等经典算法，以及较新的算法，即杜鹃散列和跳房子散列。最后讨论了通用散列和可扩散列。

第6章讨论优先队列（堆），包括二叉堆，以及优先队列在理论上的一些有趣的实现。Fibonacci堆将在第11章讨论，配对堆将在第12章讨论。

第7章涉及排序，在编码细节和算法分析方面非常具体，涵盖并比较了所有重要的通用排序算法，详细分析了5种算法: 插入排序、希尔排序、堆排序、归并排序和快速排序。本章新增了基于比较的下界证明和基数排序。最后讨论了外部排序。

第8章讨论不相交集算法，并给出了运行时间的证明。如果不讨论Kruskal算法，可以跳过本章。

第9章讲授图论算法。图论算法非常有趣，不但在实践中经常出现，而且运行时间取决于数据结构的恰当使用，因此，几乎所有标准算法都是和相应的数据结构、伪代码及运行时间分析一起介绍。为了将这些问题放在适当的使用背景下，本章对复杂性理论（包括NP完全性和不可判定性）进行了简要的讨论。

第10章通过考查一些常见问题的求解方法来讨论算法设计技术。本章通过大量示例强化算法设计技术。本章及后面的章节使用伪代码描述算法，使得学生理解示例算法而不被实现细节困扰。

第11章涉及摊还分析，对第3章和第6章的3种数据结构及本章介绍的Fibonacci堆进行摊还分析。

第12章讨论搜索树、后缀数组和后缀树、kd树和配对堆。与其他章不同，本章对搜索树和配对堆提供了完整和仔细的实现，这样的结构使得教师可以将一些内容整合到其他章的讨论中。例如，可以一起讲授第12章的自顶向下红黑树和第4章的AVL树。

第1章～第9章为大多数一学期的“数据结构”课程提供了足够的内容，如果时间允许，可以学习第10章。研究生的“算法分析”课程可以使用第7章～第11章，第11章中高级数据结构的分析可以整合到前面的章节中。第9章对NP完全性的讨论过于简短，不足以在“算法分析”课程中使用，可以参阅其他NP完全性著作以扩充本书。

练习

每章末尾都提供了练习，并且与正文的呈现顺序相匹配，通常涉及当前章的整体内容，而不是针对某个特定的部分。较难的练习用一个星号标记，更具挑战性的练习用两个星号标记。

参考文献

每章末尾都提供了参考文献，有些参考文献是历史文献，代表书中相关内容的原始来源，有些参考文献是对正文的扩展或改进，还有些参考文献提供了练习的解决方案。

补充材料

读者可以扫描下方二维码获取下列补充材料:

 示例程序的源代码

 勘误表

 练习的解答

 本书的部分图示

致谢

本书在编写过程中得到了许多人的帮助，在本书的其他版本中列出了一些人，感谢你们。