数据结构简明教程(第2版)-微课版

国际著名计算机教育专家Weiss数据结构与算法Java描述经典教材新版，把算法分析与高效率的Java程序的开发有机地结合起来，深入分析每种算法。 本书是国外数据结构与算法分析方面的经典教材，使用卓越的Java编程语言作为实现工具，讨论数据结构（组织大量数据的方法）和算法分析（对算法运行时间的估计）。 随着计算机速度的不断增加和功能的日益强大，人们对有效编程和算法分析的要求也不断增长。本书将算法分析与*有效率的Java程序的开发有机结合起来，深入分析每种算法，并细致讲解精心构造程序的方法，内容全面，缜密严格。 第3版的主要更新如下： 第4章包含AVL树删除算法的实现。 第5章进行了全面修订和扩充，现在包含两种较新的算法——布谷鸟散列和跳房子散列。 第7章包含基数排序的相关内容，并给出了下界证明。 第12章增加了后缀树和后缀数组的相关材料，包括Karkkainen和Sanders的线性时间后缀数组构造算法。 更新书中的代码，使用了Java 7中的菱形运算符。 　　本书目标本书新的Java版论述数据结构——组织大量数据的方法，以及算法分析——算法运行时间的估计。随着计算机的速度越来越快，对于能够处理大量输入数据的程序的需求变得日益迫切。可是，由于在输入量很大的时候程序的低效率变得非常明显，因此这又要求对效率问题给予更仔细的关注。通过在实际编程之前对算法的分析，我们可以确定某个特定的解法是否可行。例如，查阅本书中一些特定的问题，可以看到我们如何通过巧妙的实现，将其处理大量数据的时间限制从几个世纪减至不到1秒。因此，我们在提出所有算法和数据结构时都会阐释其运行时间。在某些情况下，对于影响实现的运行时间的一些微小细节都需要认真探究。 　　一旦确定了解法，接着就要编写程序。随着计算机功能的日益强大，它们必须解决的问题也变得更加庞大和复杂，这就要求我们开发更加复杂的程序。本书的目的是同时教授学生良好的程序设计技巧和算法分析能力，使得他们能够以最高的效率开发出这种程序。 　　本书适用于高级数据结构（CS7）课程或是第一年研究生的算法分析课程。学生应该掌握一些中级编程知识，包括基于对象的程序设计和递归等内容，并具备一些离散数学的背景。 　　第3版中最显著的变化第3版订正了大量的错误，也修改了很多地方，以使内容更加清晰。此外还有以下修订： 　　●第4章包括了AVL树的删除算法——这也是读者经常需要的内容。 　　●第5章进行了大量修改和扩充，现在包含两种新算法：布谷鸟散列（cuckoohashing）和跳房子散列（hopscotchhashing）。此外还增加了一节讨论通用散列法。 　　●第7章现在包含了基数排序的内容，并且增加了一节讨论下界的证明。 　　●第8章用到Seidel和Sharir提出的新的并查集分析，并且证明了O(Mα(M,N))界，而不是前一版中比较弱的O(Mlog*N)界。 　　●第12章增加了后缀树和后缀数组的内容，包括Karkkainen和Sanders提出的构造后缀数组的线性时间算法（附带实现）。关于确定性跳跃表和AA树的章节被删除。 　　●通篇代码已做更新，使用了Java7的菱形运算符。 　　处理方法虽然本书的内容大部分都与语言无关，但是，程序设计还是需要使用某种特定的语言。正如书名所示，我们为本书选择了Java。 　　人们常常将Java和C++比较。Java具有许多优点，程序员常常把Java看成是一种比C++更安全、更具有可移植性并且更容易使用的语言。因此，这使得它成为讨论和实现基础数据结构的一种优秀的核心语言。Java的其他重要的方面，诸如线程和GUI（图形用户界面），虽然很重要，但是本书并不需要，因此也就不再讨论。 　　完整的Java和C++版数据结构均在互联网上提供。我们采用相似的编码约定以使得这两种语言之间的对等性更加明显。 　　内容概述第1章包含离散数学和递归的一些复习材料。我相信熟练掌握递归的唯一办法是反复不断地研读一些好的用法。因此，除第5章外，递归遍及本书每一章的例子之中。第1章还介绍了一些相关内容，作为对Java中“继承”的复习，包括对Java泛型的讨论。 　　第2章讨论算法分析，阐述渐近分析及其主要缺点，提供了许多例子，包括对对数级运行时间的深入分析。我们通过直观地把递归程序转变成迭代程序，对一些简单递归程序进行了分析。更复杂的分治程序也在此介绍，不过有些分析（求解递推关系）要推迟到第7章再进行详细讨论。 　　第3章介绍表、栈和队列。包括对CollectionsAPIArrayList类和LinkedList类的讨论，提供了CollectionsAPIArrayList类和LinkedList类的一个重要子集的若干实现。 　　.第4章讨论树，重点是查找树，包括外部查找树（B-树）。UNIX文件系统和表达式树是作为例子来介绍的。这一章还介绍了AVL树和伸展树。查找树实现细节的更仔细的处理可在第12章找到。树的另外一些内容（如文件压缩和博弈树）推迟到第10章讨论。外部介质上的数据结构作为若干章中的最后论题来考虑。对于CollectionsAPITreeSet类和TreeMap类的讨论，则通过一个重要的例子来展示三种单独的映射在求解同一个问题中的使用。 　　第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.pearsonhighered.com/cssupport对所有读者公开： 　　●例子程序的源代码此外，下述材料仅提供给经培生教师资源中心（Pearson’sInstructorResourceCenter，IRC）(www.pearsonhighered.com/irc)认可的教师。有意者请访问IRC或联系培生的校园代表以获得访问权限。关于本书教辅资源，用书教师可向培生教育出版集团北京代表处申请，电话：010-57355169/57355171，电子邮件：service.cn@pearson.com。——编辑注●部分练习的解答●来自本书的一些附图致谢在本书的准备过程中，我得到了许多人的帮助，有些已在本书的其他版本中列出，感谢大家。 　　一如既往地，培生的专家们的努力使得本书的写作过程更加轻松。我愿在此感谢我的编辑MichaelHirsch以及制作编辑PatBrown。我还要感谢AbinayaRajendran和她在IntegraSoftwareServices的同事，感谢他们使最后的散稿成书的出色工作。贤妻Jill所做的每一件事情都值得我特别感谢。 　　最后，我还想感谢发来E-mail并指出前面各版中错误和矛盾之处的广大读者。我的网页www.cis.fiu.edu/~weiss包含更新后的源代码（用Java和C++编写）、勘误表以及提交问题报告的链接。 　　M.A.W.佛罗里达州迈阿密市