算法(4th ed)(80):基础——数据抽象 4.2

阅读数:23 2019 年 11 月 2 日 12:08

算法(4th ed)(80):基础——数据抽象 4.2

(抽象数据类型举例)

Java 语言内置了上千种抽象数据类型,我们也会为了辅助算法研究创建许多其他抽象数据类型。实际上,我们编写的每一个 Java 程序实现的都是某种数据类型(或是一个静态方法库)。为了控制复杂度,我们会明确地说明在本书中用到的所有抽象数据类型的 API(实际上并不多)。

在本节中,我们会举一些抽象数据类型的例子,以及它们的一些用例。在某些情况下,我们会节选一些含有数十个方法的 API 的一部分。我们将会用这些 API 展示一些实例以及在本书中会用到的一些方法,并用它们说明要使用一个抽象数据类型并不需要了解其实现细节。

作为参考,下页显示了我们在本书中将会用到或开发的所有数据类型。它们可以被分为以下几类。

  • java.lang.* 中的标准系统抽象数据类型,可以被任意 Java 程序调用。
  • Java 标准库中的抽象数据类型,如 java.swt、java.net 和 java.io,它们也可以被任意 Java 程序调用,但需要import 语句。
  • I/O 处理类抽象数据类型,和 StdIn 和 StdOut 类似,允许我们处理多个输入输出流。
  • 面向数据类抽象数据类型,它们的主要作用是通过封装数据的表示简化数据的组织和处理。稍后在本节中我们将介绍在计算几何和信息处理中的几个实际应用的例子,并会在以后将它们作为抽象数据类型用例的范例。
  • 集合类抽象数据类型,它们的主要用途是简化对同一类型的一组数据的操作。我们将会在 1.3 节中介绍基本的BagStackQueue 类,在第 2 章中介绍优先队列(PQ)及其相关的类,在第 3 章和第 5 章中分别介绍符号表(ST)和集合(SET)以及相关的类。
  • 面向操作的抽象数据类型,我们用它们分析各种算法,如 1.4 节和 1.5 节所述。
  • 图算法相关的抽象数据类型,它们包括一些用来封装各种图的表示的面向数据的抽象数据类型,和一些提供图的处理算法的面向操作的抽象数据类型。

这个列表中并没有包含我们将在练习中遇到的某些抽象数据类型,读者可以在本书的索引中找到它们。另外,如 1.2.4.1 节所述,我们常常通过描述性的前缀来区分各种抽象数据类型的多种实现。从整体上来说,我们使用的抽象数据类型说明组织并理解你所使用的数据结构是现代编程中的重要因素。

一般的应用程序可能只会使用这些抽象数据类型中的 5 ~ 10 个。在本书中,开发和组织抽象数据类型的主要目标是使程序员们在编写用例时能够轻易地利用它们的一小部分。

评论

发布