Java数据结构与算法分析：从理论到实践，优化程序效率的关键

本书的目标 本书的新 Java 版本讨论了数据结构（组织大量数据的方法）和算法分析（算法运行时间的估计）。随着计算机变得越来越快，对能够处理大量输入数据的程序的需求变得越来越迫切。然而，这需要更加仔细地关注效率问题，因为当输入很大时，程序的低效率变得明显。通过在实际编程之前分析算法，我们可以确定特定的解决方案是否可行。例如，查看本书中的一些具体问题，您可以看到我们如何通过巧妙的实现将处理大量数据的时间限制从几个世纪缩短到不到一秒。因此，我们说明了所有算法和数据结构的运行时间。在某些情况下，需要仔细探索影响实现运行时间的小细节。确定了解决方案后，下一步就是编写程序。随着计算机变得越来越强大，它们必须解决的问题变得越来越大、越来越复杂，这就要求我们开发更复杂的程序。本书的目的是教会学生良好的编程技能和算法分析技能，以便他们能够以最高的效率开发此类程序。本书适合研究生一年级的高级数据结构（CS7）课程或算法分析课程。学生应该具备一些中级编程知识，包括基于对象的编程和递归，以及一些离散数学背景。第三版最显着的变化 第三版纠正了大量错误，修改了很多地方，使内容更加清晰。

此外，还有以下修改： ●第4章包括AVL树的删除算法——这也是读者经常需要的内容。 ●第5章进行了重大修改和扩展，现在包括两种新算法：布谷鸟哈希和跳房子哈希。还添加了一个部分来讨论通用哈希。 ●第7章现在涵盖基数排序，并有一个附加部分讨论下界的证明。 ●第8章使用了Seidel和Sharir提出的新并查分析，并证明了O(Mα(M,N))界限，而不是前一版本中较弱的O(Mlog*N)界限。 ●第12章增加了后缀树和后缀数组的内容，包括Karkkainen和Sanders提出的构建后缀数组的线性时间算法（附实现）。关于确定性跳转表和 AA 树的章节已被删除。 ●整个代码已更新为使用Java 7的菱形运算符。 方法 尽管本书中的大部分内容与语言无关，但编程仍然需要使用特定的语言。正如标题所示，我们为本书选择了 Java。人们经常将Java和C进行比较。Java有很多优点，程序员通常认为Java是一种比C更安全、更可移植、更易于使用的语言。

因此，这使其成为讨论和实现基本数据结构的优秀核心语言。 Java 的其他重要方面，例如线程和 GUI（图形用户界面）虽然很重要，但在本书中并不需要，也不会讨论。完整的 Java 和 C 版本的数据结构可以在 Internet 上找到。我们采用类似的编码约定，使两种语言之间的等价性更加明显。内容概述 第 1 章包含一些有关离散数学和递归的复习材料。我相信精通递归的唯一方法是一遍又一遍地学习良好的用法。因此，除了第5章之外，本书每一章的例子中都出现了递归。第1章还介绍了一些相关内容，作为对Java中“继承”的回顾，包括对Java泛型的讨论。第 2 章讨论算法分析，解释渐近分析及其主要缺点，提供许多示例，包括对对数运行时间的深入分析。我们通过直观地将一些简单的递归程序转换为迭代程序来分析它们。这里还介绍了更复杂的分治过程，但一些分析（解决递归关系）推迟到第 7 章进行详细讨论。第 3 章介绍表、堆栈和队列。包括对 Collections API ArrayList 类和 LinkedList 类的讨论，并提供 Collections API ArrayList 类和 LinkedList 类的重要子集的多个实现。

第4章讨论树，重点关注搜索树，包括外部搜索树（B树）。以UNIX文件系统和表达式树为例进行介绍。本章还介绍了AVL树和扩展树。对搜索树实现细节的更仔细的处理可以在第 12 章中找到。树的其他方面（例如文件压缩和博弈树）被推迟到第 10 章。外部介质上的数据结构被认为是几个章节的最后主题。对于 Collections API TreeSet 类和 TreeMap 类的讨论，使用了一个重要的示例来演示如何使用三个单独的映射来解决同一问题。第5章讨论哈希表，包括分割链、线性和平方检测等经典算法，以及布谷鸟哈希和跳房子哈希等几种新算法。本章还讨论了通用哈希，并在本章末尾讨论了可扩散列。第 6 章是关于优先级队列的。这里还教授了二叉堆，并且还有关于优先级队列的一些理论上有趣的实现的附加材料。第 11 章讨论斐波那契堆，第 12 章讨论配对堆。第 7 章讨论排序。本章特别关注编程细节和分析。本章讨论并比较了所有重要的通用排序算法。另外还详细分析了四种排序算法，分别是插入排序、希尔排序、堆排序和快速排序。此版本中的新内容是基数排序和选择问题下界的证明。

外部排序将在本章末尾讨论。第8章讨论不相交集算法并证明其运行时间。分析部分是新的。这是一个简短而特殊的章节，如果您不讨论 Kruskal 算法，可以跳过。第9章讲授图论算法。图论算法很有趣，不仅因为它们在实践中频繁出现，还因为它们的运行时间很大程度上取决于数据结构的适当使用。几乎所有标准算法都与适用的数据结构、伪代码和运行时分析一起提供。为了正确理解这些问题，我们对复杂性理论进行了简要讨论，包括 NP 完备性和不可判定性。第 10 章通过考察一般问题解决技术来介绍算法设计。本章使用大量示例来增强理解。本章和后续章节中使用的伪代码使读者能够理解示例，而不会被实现细节所困扰。第11章涉及摊销分析，主要分析第4章、第6章和本章（斐波那契堆）中介绍的三种数据结构。第12章讨论搜索树算法、后缀树和数组、kd树和成对堆。与其他章节不同，本章给出了搜索树和配对堆的完整而仔细的实现。这些材料的安排是为了让教师可以将一些材料纳入其他章节的讨论中。例如，第 12 章中的自顶向下红黑树可以与 AVL 树（第 4 章中）一起讨论。第 1 章到第 9 章为大多数一学期的数据结构课程提供了足够的材料。

如果时间允许，也可以将第10章纳入其中。研究生算法分析课程可以使用第7章到第11章的内容。第11章分析的高级数据结构可以在前面的章节中轻松提及。第 9 章中关于 NP 完备性的讨论太简短，不适合这样的课程。此外，使用另一部有关 NP 完备性的著作作为本教科书的补充可能会更有益。练习每章末尾提供的练习与它们在文本中出现的顺序相对应。一些最后的练习是针对整章而不是针对特定部分。较困难的练习用一个星号标记，更具挑战性的练习用两个星号标记。参考文献 参考文献列于每章末尾。通常，这些参考文献要么具有历史意义，提供书中材料的原始来源，要么描述对书中所呈现结果的扩展和改进。一些文献提供了一些练习的解决方案。补充材料 以下补充材料向所有读者开放： ● 示例程序的源代码。此外，以下材料仅提供给经培生教师资源中心 (IRC) () 认可的教师。感兴趣的各方应访问 IRC 或联系 Pearson 校园代表以获得访问权限。 使用本书的教师可向培生教育出版集团北京代表处申请本书教辅资源，电话：010-5735 5169/5735 5171，邮箱：service.cn@pearson.com。

——编者注●部分习题解答●本书中的一些图致谢在本书的编写过程中，我得到了很多人的帮助，其中一些已经在本书的其他版本中列出。谢谢大家。与往常一样，培生的专家让写作过程变得更加容易。我要感谢我的编辑迈克尔·赫希（Michael Hirsch）和制作编辑帕特·布朗（Pat Brown）。我还要感谢 Integra Software Services 的 Abinaya Rajendran 和她的同事在将最终草稿编写成书方面所做的出色工作。我出色的妻子吉尔所做的一切值得特别感谢。最后，我还要感谢给我发邮件并指出前几版错误和矛盾的读者。我的页面 ~weiss 包含更新的源代码（用 Java 和 C 编写）、勘误表以及提交问题报告的链接。 MAW 佛罗里达州迈阿密