本书从面向对象的角度讲述了数据结构的基本理论。总的来说，数据结构就是处理批量数据的存储处理机。数据结构又称为集合(collection)，它可进行添加和删除数据项的操作，并且能够提供对集合中元素的访问。面向对象的编程方法将数据结构视为可对数据进行特定操作的对象。类声明定义了数据底层的存储结构和能高效执行操作的实现方法。 数据结构在计算机科学的各个领域中都扮演着非常重要的角色。在几乎所有重要的计算机应用程序的设计和实现中，它都是一个关键的要素。所以大多数学生在回顾数据结构的课程时，都认为这是他们将计算机科学作为一种学科来认识和了解的第一步。在数据结构的学习中会介绍大量的重要概念。 0.1 本书的编排 现代的观点将数据结构分为面向对象的编程原理和算法分析的概念。我们的学习主要是围绕定义集合类型的类别的接口来进行。这种接口把数据结构视为一种抽象数据类型(ADT)，它描述了集合如何存储元素并定义了关键的数据处理操作。集合类是一种聚合数据结构，它用特定的方法来实现存储和访问元素的接口。 本书对数据结构的学习按简单的接口和类的层次结构来进行。位于最高层的接口描述了与对集合中对象进行访问和更新操作有关的抽象结构。最底层含有的集合类使用不同的底层存储结构来保存元素和实现接口。接口和集合类的层次结构为数据结构创建了一个总的构造，我们将其称为集合架构(collections framework)。在本书中，我们模仿Java Collections Framework创建了一个简单的集合架构，该架构定义了使用有限的一组方法的接口，这些方法描述了集合类的基本功能。 Java Collections Framework是一个商业级软件系统，它提供了多种方法来帮助应用程序的编程人员。Java Framework中的集合类代码很大程度上依赖于抽象类和相当复杂的继承层次结构。书中的集合使用用于接口的相同名称和方法签名来模仿Java Collections Framework，此外还创建了具有相同名称和底层存储结构的集合类。不过，我们使用直观的实现来设计集合类。通过这种方式，学生能够阅读书中的代码并理解各种方法及其算法。学习本书所有内容后，读者会发现在职业生涯中很容易掌握更完整的Java Collection Framework。 图0-1示例了本书中集合架构的接口和集合类。类用阴影表示。List接口是按位置存储元素的数据结构模型，而Set接口是按值存储元素的数据结构模型，它不允许集合中存在重复值。Map接口是按键/值对存储元素的关联集合模型。映射中存储的键是不可重复的，并且提供了某种机制将键和值关联起来。在映射集合中，程序员通过键而不是索引来访问相应的值。Stack、Queue、PQueue是用于适配器集合的接口，上述接口将另外一个集合用作底层存储结构，不过只为这些结构提供受限的操作。图是由顶点和连接边组成的数据结构。网络就是图的一种模型。本书会讲述图及其经典的搜索和最优化算法。Graph接口中列出了这些操作以及作为具体数据结构的有向图。 图0-1 本书中介绍的接口与类 0.2 数据结构与算法 数据结构除了存储数据外，还具有处理数据的操作。这些操作的设计和实现涉及由完成任务所需的有限指令序列所组成的算法。学习数据结构必须对算法也有所了解，以便确保正确地处理数据。我们还必须考虑到大数据集带来的问题。数据结构的选择对访问和更新操作的效率影响非常大。假设要维护100 000张信用卡账户，类似数组的结构平均需要50 000次迭代才能定位某个元素，而用映射完成同样的任务只需要大约16次迭代。这两种结构都具有查找某个数据值的算法，但是两者的性能结果却大不相同。在讨论算法时，我们会使用简单、直观但却非常有效的方法来评估算法的执行时的时间性能，这种评估方式与所用的机器或编程语言无关。 数据结构需要优良的算法，反之亦然。在后面章节介绍图、数据压缩、密码术以及高级递归算法的时候，读者会看到这方面的示例。我们将重点讨论密切依赖于针对问题采用特定方式构造数据的算法和算法设计技术。通过这种方法，我们就能够使用在本书中讲述的数据结构特性。著名的计算机科学家Niklaus Wirth在其经典论文Algorithms + Data Structures = Programs一书中表明：对于计算机编程来说，算法和数据结构具有同样的重要性。在现代的面向对象编程中，数据结构对于算法设计和分析来说仍然至关重要。 0.3 Java与数据结构 本书中讨论的大多数素材都能够应用于任何编程语言。我们重点强调了与数据结构的设计和使用相关的概念。不过，读者还必须理解如何实现数据结构和编写应用程序。这要求读者采用特定的编程语言来编写代码，在本书中我们选择了Java语言。Java语言具有优良的、支持数据结构现代观点的面向对象设计构造。我们使用这种编程语言以一个层次架构来描绘数据结构。Java接口定义了数据结构(集合)的类别，而Java类则定义了单独的集合类型。 Java是可移植的，它允许程序不需重新编译就能够在任何平台上运行。这种特性具有许多实用的优点。学生可以先在Windows、Macintosh或UNIX系统中开发程序，然后再将代码移植到另一个系统中。大学里应该可以为实验室提供中央计算设备，这样学生就可以在自己的主系统上开始或完成所从事的项目。 Java是创建交互式图形用户界面(Graphical User Interface，GUI)程序的理想语言。大多数现代应用程序的形式是GUI程序。第3章使用Java Swing组件独立地介绍了GUI编程。本书的目标是促进读者对数据结构的理解，并且绝大部分示例、程序和练习都基于控制台，也就是使用键盘输入和屏幕输出。不过，GUI应用程序零散地遍布于全书以及练习当中。 Java语言具有许多有助于数据结构使用和实现的编程构造。这些构造包括： ● 自动装箱和自动拆箱，自动装箱提供从某个原始类型到其相关包装类型的自动转换，自动拆箱则提供从某个包装类型到其相关原始类型的自动转换。这允许我们将原始数字和字符数据作为对象存储在集合中。 ● 集合使用迭代器扫描数据。Java引入了使编译器能够维护迭代器的“增强的for”语句。这种语句使用变化形式的loop循环简化了初始化迭代器的需求以及使用迭代器方法访问集合元素。 ● Java提供了一个枚举工具，这个枚举工具允许程序定义其成员为命名常量的特殊类。编程人员能够使用enum类来增强程序的可读性。我们将在选定的应用程序和实现中示例说明这种特性。 ● Scanner对象为来自文件或键盘的文本数据输入提供一个简单的文本扫描器。这个扫描器将输入流中的文本分割为若干标记，并且使用多种方法将标记转换为一个串或一个原始类型值。 对于数据结构来说，Java语言中最重要的特性是泛型。泛型扩展了将类型参数与集合类实例、接口或方法相关联的语言。Java的编译器能够检查代码是否与指定类型一致；如果一致，那么代码是类型安全的。执行类型安全的代码不会导致某些运行时错误，这些运行时错误包括由于不正确的类型检查和类型处理所带来的代码质量和可靠性问题。 第5章详细阐述了Java泛型。我们首先阐明在Java语言中包含泛型的动机，随后讲述创建泛型类和方法时必须使用的机制。这些讨论的重点是读者必须了解的基础。本书的后面部分还将为更复杂的泛型开发相应的语法，并且始终重点讲述读者“需要知道”的基础知识。Java泛型的其他一些特征则超出了本书的讨论范围。 0.4 本书的功能部件 本书包含能够提高学生知识水平的功能部件以及促进深入理解数据结构的介绍主题。 ● UML：对象技术的发展促进了用于程序设计的各种表示法的出现。其中一个最重要的表示法是通用建模语言(Unified Modeling Language，UML)。UML使用图形规范来帮助完成对象和程序设计。通过使用UML图作为列出接口或集合类中方法的一种有效途径，使读者对UML有一定的了解。 ● 练习集：每一章都含有书面练习和编程练习。设计这些练习的目的是巩固对基本知识的理解，使学生能够设计与实现方法以及完成程序，促进对各种素材的创造性认识。每一章还含有编程项目，这些编程项目要求更高级的设计和编程以及开发更多算法。 设计模式：问题的面向对象解决方案经常使用软件重用的公共设计模式进行构造。我们选择介绍了一些设计模式，这些设计模式增强了读者对数据结构及其应用的理解，并且能够帮助构造类、方法以及对象的实现。 ● 注释：在研究各种主题的过程中，我们在文中插入了一些主要概念的注释。这些注释突出了重要的知识点，并且为学生提供了一种复习素材的简单有效方法。 0.5 适用范围 本书假定学生至少已学过一门编程课程。针对没有Java编程经验的学生，我们在附录A中提供了“Java入门”指南。“Java入门”采用文本样式编写，并且含有示例和完整的程序。这个指南为读者阅读和理解本书提供了必要的背景知识。学生应当掌握中学的大学预备课程中的数学知识。递归的示例以及算法运行时效率的讨论使用了高等代数课程中所讲述的数学知识。 0.6 教师需要注意的问题 本书可以用作两学期计算机科学授课内容的一部分，也可以作为一门为学习数据结构专门设计的课程。某些学校(如笔者的学校)开设了一门课程来阐述数据结构和介绍数据结构在算法中的应用。我们已经发现：本书中知识点的深度与多样性所达到的教学效果非常不错，并且能够在今后的算法设计与分析课程中为学生提供某些编程工具。本书的设计方式允许教师能够非常灵活、自由地组织和讲解各种知识点。 我们广泛使用示例、图表以及注释来包涵所有知识点。本书的前7个章节介绍了学习数据结构时要用到的各种概念和工具。 ● 第1~ 3章介绍了Java的对象技术特征，包括对象的使用、类的设计与实现、组合、继承、接口以及异常处理。这一部分通过许多示例和程序说明了使用Time24对象的数据结构。 ● 第4章讨论了如何使用独立于任何机器或编程语言的算法运行时间性能来描述算法的特征。我们直观地提出了效率度量Big-O，并且将其应用在全书范围内，以便有助于选择适用于特定程序应用的算法或数据结构。 ● 第5章较详细地讲述了Java泛型类与方法。泛型的使用贯穿全书，并且这一章节的知识点为学生提供了至关重要的背景知识。 ● 第6章和第7章介绍了递归及其在高效的归并排序与快速排序算法中的应用。对于学习二叉树来说，理解递归至关重要。 ● 第8~19章覆盖了初次接触数据结构的读者应当了解的主题。我们使用一种体系方式逐渐展开每种数据结构。这种方式认为学生需要从下列4个方面来理解每种数据结构：存储数据的方式，指定具体集合类的接口，在应用程序中使用这个类的能力，以及对类实现的理解。 • 动态数组、单链表和双链表以及二叉树是分别为ArrayList、LinkedList、TreeSet和TreeMap集合类提供底层存储结构的低级数据结构。我们首先介绍了这些数据结构，然后开发了定位、插入和删除元素的算法。 • 集合类型(接口)指定了用于集合类的大多数设计特性。一个类可以包含利用底层存储结构特征的额外方法。例如，ArrayList类定义了方法ensureCapacity()，该方法更新底层动态数组的大小。 • 我们为每种数据结构都提供了若干应用程序。某些应用程序简单地示例说明了如何使用集合类方法；另外一些应用程序则利用了独特的特征并示例说明了算法与数据结构之间的交互。 • 在讲述数据结构的课程中，学生必须理解每种集合类型的抽象设计和实现设计。他们应该掌握需要使用哪种数据结构以及如何使用这种数据结构。我们在介绍每种集合类的同一章节中开发了各种集合类的实现。读者可以根据自己的需求随时研究这些实现。对集合类实现的讨论独立于学生需要了解的其他方面的内容。 ● 第20~29章覆盖了数据结构高级课程与算法应用的主题。笔者建议：介绍集与映射的第19章既可以作为数据结构预备课程的内容，也可以作为数据结构高级课程的内容。在预备课程中，本章可以向学生介绍应用程序中所使用的重要集合类型以及作为键-值对的元素。在高级课程中，教师能够更详细地开发作为关联数组的映射并讨论区分元素键字段和值字段的迭代器访问方法。 数据结构预备课程介绍了简单的、具有节点和引用字段的二叉搜索树。数据结构高级课程将二叉搜索树的概念扩展到包含平衡树以及定义堆的基于数组的二叉树，此外，还将散列表开发为一种可供选择的搜索结构。第21、22和27章阐述了上述内容，并且使用它们创建用于有序与无序集、映射和优先队列的高效实现。 计算机科学专业的学生通常都需要参加算法设计与分析课程的学习。这门课程的重点是不同的算法设计策略，并且对算法效率进行更深入的数学分析。伪码被用于描述实现技术。针对实现算法的数据结构，通过示例说明这些数据结构的复杂与总是巧妙的用法，数据结构高级课程融会了算法设计与分析。因此，本书包含了数据与文件压缩(第23章)、图算法(第25章)、数论与密码术(第28章)以及杂类算法(第29章)等相关章节。这些章节都是独立的单元，教师可以选取某些主题进行教学。 教师指南 教师指南可供教师使用，它不仅提供了所有书面练习的答案以及大多数编程练习和编程项目的解决方案，而且提供了每章的测验模拟题。除此之外，我们还为练习中开发的程序和类给出了源文件。您可以通过Prentice Hall驻北京办事处的销售代理商购买教师指南。 0.7 补充内容 从如下所示的网址上可以得到本书的所有补充内容： http://www.tupwk.com.cn/downpage 软件补充内容 软件补充内容位于ftjavads目录中，这个目录由programs、packages和docs目录组成。Programs目录包含用于本书每个章节的若干独立子目录，这些子目录中存在用于本章中程序的源文件和数据文件。在某些情况下，读者还会发现指定章节所引用的图形程序和其他程序清单。Packages目录包含全书范围内所使用的软件，它的结构定义了ds子目录，该子目录又分支为对应于包graphics、time和util的目录。Util软件包包含了本书所介绍的接口、集合类和静态方法库。 软件API文档 文件docs包含对packages目录中软件的完整API说明，这为学生和教师提供了易于使用的、资料丰富的在线文档。Packages目录中的Java源文件清单包含文档注释。Javadoc工具使用这些注释来创建相应的HTML页面集。通过Web浏览器打开文件index.html，读者就可以使用API文档。 Web补充内容 笔者尽可能使本书自成一体。不过在某些情况下，我们引入了基本的功能与算法，并且基于Web补充内容进行更详细的讨论。这些补充内容通过简单地扩展本书的版面来提供额外的素材。 现代应用程序通常使用依赖于GUI窗体的交互式I/O，而GUI窗体具有组件和事件处理程序。第3章介绍了GUI应用程序设计，并且讨论了基本的组件集以及动作侦听器机制。 图形显示可以帮助读者理解各种算法，如Hanoi塔、八皇后问题等。本书还使用图形显示来示例说明二叉树以及用于二叉搜索树、AVL树、红-黑树和堆数组的插入与删除方法。软件补充内容包含基本的画图软件。Web补充内容“Graphics Package”给出了对画图系统的详细讨论，此外还提供了继承的一个优秀示例。 本书只简单描述了用于中缀表达式求解与红-黑树插入和删除方法的算法。对这些算法感兴趣的读者可以通过Web补充内容“Infix Expression Evaluation”和“RBTree Implementation”得到更详细的讨论以及Java实现的代码清单。 EZJava IDE EZJava是一个灵活的集成开发环境(Integrated Development Environment，IDE)，它允许在Windows、Linux、Solaris或Macintosh OS X系统下开发和运行Java程序。读者可以选择与当前系统匹配的版本。EZJava IDE允许非常简单地编译和运行一个主类以及位于相同目录中的任何支持类。对于更高级的软件开发来说，我们可以创建一个由相同软件包结构中多个源文件组成的项目。 EZJava拥有十分复杂的编程环境才具有的特性。虽然EZJava可以用来开发大型的软件系统，不过它是为了在学术课程作业中方便Java的使用而专门设计的。我们可以创建若干单独的程序，并且可以在项目环境之外运行这些程序。应用程序使用一个用于多个运行的命令按钮在自己的运行时窗口中执行命令。EZJava编译了Synchronous Java，Synchronous Java是一个具有并行编程工具的Java扩充，并行编程工具在操作系统课程中非常有用。 附录E讨论了如何获取和安装EZJava以及如何使用其主要功能创建和运行一个程序。这个软件所集成的帮助系统提供了更多的指南。 William Ford William Topp