Loading......

目的/目标
    本书全面论述了数据结构和算法分析，即组织大量数据的方法和对算法运行时间的估计。随着计算机的速度越来越快，对于能够处理大量输入数据的程序的需求变得日益迫切。具有讽刺意味的是，由于在输入量很大时程序的效率明显降低，因此这又要求更加关注效率问题。通过在实际编程之前对算法进行分析，学生可以确定一个特定的解法是否可行。例如，在本书中学生可看到一些特定的问题，并了解精心的实现如何能够把处理大量数据的时间从16年减至不到1秒。因此，本书中论述的算法和数据结构均对其运行时间进行了分析。在某些情况下，还研究了影响实现运行时间的一些微小细节。
    一旦确定了解法，接着就要编写程序。随着计算机功能的日益强大，它们必须解决的问题也越来越大，越来越复杂，这就要求开发更加复杂的程序。本书的目的是在教会学生使用良好的程序设计技巧的同时让学生具备算法分析能力，使得他们能够开发这种具有最高效率的程序。
    本书适用于本科生的高级数据结构课程或是研究生的算法分析课程。使用本书的学生应该具有中等程度的程序设计方面的知识，包括指针、递归和面向对象程序设计，还要具有离散数学的某些知识。
方法
    虽然本书中的内容大部分都是与语言无关的，但是，程序设计还是需要使用某种特定的语言。正如书名指出的，我们为本书选择了C++。
    C++已经成为系统编程的主流语言。除了修正了许多C语言的语法方面的缺陷之外，C++还提供了直接结构（类和模板）来实现抽象数据类型的通用数据结构。
    撰写本书最困难的部分是确定C++在书中所占的比例。使用太多的C++的特性将使教材变得很晦涩，使用得太少又会和使用支持类的C语言撰写的教材区别不大。
    我们采用的方法是以基于对象的方法来阐述文中的内容。这样，本书中几乎没有用到继承性。我们采用类模板来描述通用数据结构。通常情况下尽量避免使用深奥的C++特性，而是使用标准C++中的vector和string类。通过采用C++的现代特性来取代在本书第1版中所用的次级特性简化了很多代码。本书前几版已经实现了类模板，方法是将类模板的接口与其实现分离开。毫无疑问，这是一种好方法，但是这种方法暴露出了编译的问题，读者事实上很难利用这些代码。本版中，在线的源代码将类模板作为一个单元来表示，而不再将接口和实现分离开。本书第1章对书中所用到的C++特性进行了介绍，并阐述了对类模板的处理方法。附录A描述了如何重写类模板，用于分离编译。
    以Java和C++两种语言描述的数据结构的完全版在因特网上可以得到。我们使用类似的编码习惯使得这两种语言间的相似性表现得更加明显。
第3版中的主要变化
    第3版中包含了大量的错误修正，并且书中的大部分章节都经过了修订以提高其可读性。另外，本版还有以下几方面的变化：
  ·书中的所有代码都做了更新以适应现代的C++特性。
  ·第3章进行了大量的修订，并且讨论了标准vector和list类的使用及其实现。标准vector类在其他数据结构的实现中被广泛使用。
  ·第4章修订后包含了关于set和map类的讨论，并通过一个扩展的例子介绍了它们在有效算法设计中的应用。在第9章中也包含了一个使用标准map类来实现最短路径算法的例子。
  ·第7章讨论了标准sort算法，其中包括一个关于实现重载的标准sort算法所涉及的技巧。
  ·书中提供的源代码都已经进行了简化，从而避免了与类模板的分离编译有关的复杂语法。修订后的代码可以使读者更专心于算法本身，而不是过多地关注C++。
内容概述
    第1章包含离散数学和递归的一些内容。我相信熟悉递归的唯一办法是反复不断地看一些好的用法。因此，除第5章外，递归遍布本书每一章的例子中。第1章还介绍了一些C++的内容，作为对C++基础知识的了解，包含在C++类设计中模板和重要结构的讨论。
    第2章讨论算法分析。这一章阐述了渐近分析和它的主要弱点。这里提供了许多例子，包括对对数运行时间的深入解释。通过直观地把一些简单递归程序转变成迭代程序，对它们进行分析。这一章还介绍了更复杂的分治程序，不过有些分析（求解递归关系）要推迟到第7章再详细地进行。
    第3章包括表、栈和队列。这一章较之以前的版本进行了大量的修订。现在包含了关于STL vector和list类的讨论，包括有关迭代的内容，并且提供了STL vector和list类的重要子集的实现。
    第4章讨论树，重点在查找树，包括外部查找树（B树）。UNIX文件系统和表达式树是作为例子介绍的。本章还介绍了AVL树和伸展树。查找树实现细节的更详细讨论可在第12章找到。树的另外一些内容，如文件压缩和博弈树，延迟到第10章讨论。外部介质上的数据结构作为几章中的最后论题来考虑。本版中新增的部分是对STL set和map类的讨论，包括一个讲解了如何使用三个分离的图来高效率地解决问题的例子。
    第5章相对较短，主要讨论散列表。这里进行了某些分析，本章末尾讨论了可扩展散列。
    第6章是关于优先队列的。这一章还讲解了二叉堆，还有一些附加内容，论述优先队列某些理论上很有趣的实现方法。斐波那契堆在第11章讨论，配对堆在第12章讨论。
    第7章是排序。它是关于编程细节和分析的非常特殊的一章，讨论并比较了所有重要的通用排序算法。对插入排序、希尔排序、堆排序以及快速排序这四种算法进行了详细的分析。这一章末尾还讨论了外部排序。
    第8章讨论不相交集算法并证明其运行时间。这一章短且特殊，如果不讨论Kruskal算法则这一章可跳过。
    第9章讲授图论算法。图论算法之所以重要，不仅因为它们在实践中频繁出现，而且因为它们的运行时间特别依赖于数据结构的恰当使用。实际上，所有标准算法都是和相应的数据结构、伪代码以及运行时间的分析一起介绍的。为把这些问题放在一个适当的环境下讨论中，书中提供了对复杂性理论（包括NP完全性和不可判定性）的简短讨论。
    第10章通过考查一般的问题求解技巧来介绍算法设计。这一章含有大量的实例。这里及后面各章使用了伪代码，使学生对一个示例算法的理解不受具体实现细节的困扰。
    第11章处理摊还分析。对第4章和第6章的三种数据结构以及本章介绍的斐波那契堆进行了分析。
    第12章讨论查找树算法、k-d树和配对堆。不同于其他各章，这一章给出了查找树和配对堆完全的仔细的实现。材料的安排使得教师可以把一些内容纳入到其他各章的讨论之中。例如，第12章中的自顶向下红黑树可以和（第4章的）AVL树一起讨论。
    第1章～第9章为大多数一学期的数据结构课程提供了足够的材料。如果时间允许，第10章也可以包括进来。研究生的算法分析课程可以使用第7章到第11章的内容。在第11章分析的高级数据结构可以很容易地在前面各章中查到。第9章中对NP完全性的讨论太过简短，以至于不能用于算法分析课程。可以使用论述NP完全性的其他书籍来补充本书的这部分不足。
习题
    每章末尾提供的习题与正文中讲授内容的顺序相匹配。最后的习题是把一章作为一个整体来处理而不是针对特定的一节来考虑的。较困难的习题标有一个星号，更难的习题标有两个星号。
参考文献
    参考文献位于每章的最后。一般说来，这些参考文献或者是历史性的，代表着书中材料的原始来源，或者阐述对书中给出的结果的扩展和改进。有些文献提供了一些习题的解法。
补充材料
    所有的读者都可以在www.aw.com/cssupport网站得到下面的补充材料：
  ·书中例子的程序代码。
    此外，以下材料可从Addison-Wesley的教师资源中心（www.aw.com/irc）获得，但是这部分内容仅针对有资质的教师。教师可以访问Addison-Wesley的教师资源中心或向当地的Addison- Wesley代表申请下面这些资料：
  ·书中部分习题的答案。
  ·书中的图。
致谢
    在本丛书几部著作的准备过程中，我得到许多人的帮助。有些人在本书的其他版本中提到过，谢谢他们每一位。
    同往常一样，Addison-Wesley的专家们使得本书的写作过程更加轻松。我愿意借此机会感谢本书的编辑Michael Hirsch和文字编辑Marilyn Lloyd。我还想感谢Paul Anagnostopoulos和他在Windfall Software的同事，感谢他们的出色工作使最后的书稿成书。特别感谢我的爱妻Jill，感谢她所做的一切。
    最后，我还想感谢广大的读者，他们发来电子邮件并指出前面各版中的一些错误和矛盾之处。我的网http://www.cis.fiu.edu/~weiss将包含更新的（C++的、C的以及Java的）源代码、勘误表以及指向提交问题报告的一个链接。

                                                    Mark Allen Weiss
                                            于佛罗里州达州迈阿密