1.2 数据抽象

数据类型指的是一组值和一组对这些值的操作的集合。目前，我们已经详细讨论过Java的原始数据类型：例如，原始数据类型int的取值范围是-231到231-1之间的整数，int的操作包括+、＊、-、/、%、＜和＞。原则上所有程序都只需要使用原始数据类型即可，但在更高层次的抽象上编写程序会更加方便。在本节中，我们将重点学习定义和使用数据类型，这个过程也被称为数据抽象（它是对1.1节所述的函数抽象风格的补充）。

Java编程的基础主要是使用class关键字构造被称为引用类型的数据类型。这种编程风格也称为面向对象编程，因为它的核心概念是对象，即保存了某个数据类型的值的实体。如果只有Java的原始数据类型，我们的程序会在很大程度上被限制在算术计算上，但有了引用类型，我们就能编写操作字符串、图像、声音以及Java的标准库中或者本书的网站上的数百种抽象类型的程序。比各种库中预定义的数据类型更重要的是Java编程中的数据类型的种类是无限的，因为你能够定义自己的数据类型来抽象任意对象。

抽象数据类型（ADT）是一种能够对使用者隐藏数据表示的数据类型。用Java类来实现抽象数据类型和用一组静态方法实现一个函数库并没有什么不同。抽象数据类型的主要不同之处在于它将数据和函数的实现关联，并将数据的表示方式隐藏起来。在使用抽象数据类型时，我们的注意力集中在API描述的操作上而不会去关心数据的表示；在实现抽象数据类型时，我们的注意力集中在数据本身并将实现对该数据的各种操作。

抽象数据类型之所以重要是因为在程序设计上它们支持封装。在本书中，我们将通过它们：

❏以适用于各种用途的API形式准确地定义问题；

❏用API的实现描述算法和数据结构。

我们研究同一个问题的不同算法的主要原因在于它们的性能特点不同。抽象数据类型正适合于对算法的这种研究，因为它确保我们可以随时将算法性能的知识应用于实践中：可以在不修改任何用例代码的情况下用一种算法替换另一种算法并改进所有用例的性能。

1.2.1 使用抽象数据类型

要使用一种数据类型并不一定非得知道它是如何实现的，所以我们首先来编写一个使用一种名为Counter（计数器）的简单数据类型的程序。它的值是一个名称和一个非负整数，它的操作有创建对象并初始化为0、当前值加1和获取当前值。这个抽象对象在许多场景中都会用到。例如，这样一个数据类型可以用于电子记票软件，它能够保证投票者所能进行的唯一操作就是将他选择的候选人的计数器加一。我们也可以在分析算法性能时使用Counter来记录基本操作的调用次数。要使用Counter对象，首先需要了解应该如何定义数据类型的操作，以及在Java语言中应该如何创建和使用某个数据类型的对象。这些机制在现代编程中都非常重要，我们在全书中都会用到它们，因此请仔细学习我们的第一个例子。

1.2.1.1 抽象数据类型的API

我们使用应用程序编程接口（API）来说明抽象数据类型的行为。它将列出所有构造函数和实例方法（即操作）并简要描述它们的功用，如表1.2.1中Counter的API所示。

尽管数据类型定义的基础是一组值的集合，但在API可见的仅是对它们的操作，而非它们的意义。因此，抽象数据类型的定义和静态方法库（请见1.1.6.3节）之间有许多共同之处：

❏两者的实现均为Java类；

❏实例方法可能接受0个或多个指定类型的参数，由括号表示并由逗号分隔；

❏它们可能会返回一个指定类型的值，也可能不会（用void表示）。

当然，它们也有三个显著的不同。

❏API中可能会出现若干个名称和类名相同且没有返回值的函数。这些特殊的函数被称为构造函数。在本例中，Counter对象有一个接受一个String参数的构造函数。

❏实例方法不需要static关键字。它们不是静态方法——它们的目的就是操作该数据类型中的值。

❏某些实例方法的存在是为了尊重Java的习惯——我们将此类方法称为继承的方法并在API中将它们显示为灰色。

和静态方法库的API一样，抽象数据类型的API也是和用例之间的一份契约，因此它是开发任何用例代码以及实现任意数据类型的起点。在本例中，这份API告诉我们可以通过构造函数Counter()、实例方法increment()和tally()，以及继承的toString()方法使用Counter类型的对象。

1.2.1.2 继承的方法

根据Java的约定，任意数据类型都能通过在API中包含特定的方法从Java的内在机制中获益。例如，Java中的所有数据类型都会继承toString()方法来返回用String表示的该类型的值。Java会在用+运算符将任意数据类型的值和String值连接时调用该方法。该方法的默认实现并不实用（它会返回用字符串表示的该数据类型值的内存地址），因此我们常常会提供实现来重载默认实现，并在此时在API中加上toString()方法。此类方法的例子还包括equals()、compareTo()和hashCode()（请见1.2.5.5节）。

1.2.1.3 用例代码

和基于静态方法的模块化编程一样，API允许我们在不知道实现细节的情况下编写调用它的代码（以及在不知道任何用例代码的情况下编写实现代码）。1.1.7节介绍的将程序组织为独立模块的机制可以应用于所有的Java类，因此它对基于抽象数据类型的模块化编程与对静态函数库一样有效。这样，只要抽象数据类型的源代码．java文件和我们的程序文件在同一个目录下，或是在标准Java库中，或是可以通过import语句访问，或是可以通过本书网站上介绍的classpath机制之一访问，该程序就能够使用这个抽象数据类型，模块化编程的所有优势就都能够继续发挥。通过将实现某种数据类型的全部代码封装在一个Java类中，我们可以将用例代码推向更高的抽象层次。在用例代码中，你需要声明变量、创建对象来保存数据类型的值并允许通过实例方法来操作它们。尽管你也会注意到它们的一些相似之处，但这种方式和原始数据类型的使用方式非常不同。

1.2.1.4 对象

一般来说，可以声明一个变量heads并将它通过以下代码和Counter类型的数据关联起来：

Counter heads；

但如何为它赋值或是对它进行操作呢？这个问题的答案涉及数据抽象中的一个基础概念：对象是能够承载数据类型的值的实体。所有对象都有三大重要特性：状态、标识和行为。对象的状态即数据类型中的值。对象的标识能够将一个对象区别于另一个对象。可以认为对象的标识就是它在内存中的位置。对象的行为就是数据类型的操作。数据类型的实现的唯一职责就是维护一个对象的身份，这样用例代码在使用数据类型时只需遵守描述对象行为的API即可，而无需关注对象状态的表示方法。对象的状态可以为用例代码提供信息，或是产生某种副作用，或是被数据类型的操作所改变。但数据类型的值的表示细节和用例代码是无关的。引用是访问对象的一种方式。Java使用术语引用类型以示和原始数据类型（变量和值相关联）的区别。不同的Java实现中引用的实现细节也各不相同，但可以认为引用就是内存地址，如图1.2.1所示（简洁起见，图中的内存地址为三位数）。

1.2.1.5 创建对象

每种数据类型中的值都存储于一个对象中。要创建（或实例化）一个对象，我们用关键字new并紧跟类名以及()（或在括号中指定一系列的参数，如果构造函数需要的话）来触发它的构造函数。构造函数没有返回值，因为它总是返回它的数据类型的对象的引用。每当用例调用了new()，系统都会：

❏为新的对象分配内存空间；

❏调用构造函数初始化对象中的值；

❏返回该对象的一个引用。

在用例代码中，我们一般都会在一条声明语句中创建一个对象并通过将它和一个变量关联来初始化该变量，和使用原始数据类型时一样。和原始数据类型不同的是，变量关联的是指向对象的引用而并非数据类型的值本身。我们可以用同一个类创建无数对象——每个对象都有自己的标识，且所存储的值和另一个相同类型的对象可以相同也可以不同。例如，以下代码创建了两个不同的Counter对象：

Counter heads = new Counter("heads");
Counter tails = new Counter("tails");

抽象数据类型向用例隐藏了值的表示细节。可以假定每个Counter对象中的值是一个String类型的名称和一个int计数器，但不能编写依赖于任何特定表示方法的代码（即使知道假定是否正确——也许计数器是一个long值呢）对象的创建过程如图1.2.2所示。

1.2.1.6 调用实例方法

实例方法的意义在于操作数据类型中的值，因此Java语言提供了一种特别的机制来触发实例方法，它突出了实例方法和对象之间的联系。具体来说，我们调用一个实例方法的方式是先写出对象的变量名，紧接着是一个句点，然后是实例方法的名称，之后是0个或多个在括号中并由逗号分隔的参数。实例方法可能会改变数据类型中的值，也可能只是访问数据类型中的值。实例方法拥有我们在1.1.6.3节讨论过的静态方法的所有性质——参数按值传递，方法名可以被重载，方法可以有返回值，它们也许还会产生一些副作用。但它们还有一个特别的性质：方法的每次触发都是和一个对象相关的。例如，以下代码调用了实例方法increment()来操作Counter对象heads（在这里该操作会将计数器的值加1）：

heads.increment();

而以下代码会调用实例方法tally()两次，第一次操作的是Counter对象heads，第二次是Counter对象tails（这里该操作会返回计数器的int值）：

heads.tally() - tails.tally();

以上示例的调用过程见图1.2.3。

正如这些例子所示，在用例中实例方法和静态方法的调用方式完全相同——可以通过语句（void方法）也可以通过表达式（有返回值的方法）。静态方法的主要作用是实现函数；非静态（实例）方法的主要作用是实现数据类型的操作。两者都可能出现在用例代码中，但很容易就可以区分它们，因为静态方法调用的开头是类名（按习惯为大写），而非静态方法调用的开头总是对象名（按习惯为小写）。表1.2.2总结了这些不同之处。

1.2.1.7 使用对象

通过声明语句可以将变量名赋给对象，在代码中，我们不仅可以用该变量创建对象和调用实例方法，也可以像使用整数、浮点数和其他原始数据类型的变量一样使用它。要开发某种给定数据类型的用例，我们需要：

❏声明该类型的变量，以用来引用对象；

❏使用关键字new触发能够创建该类型的对象的一个构造函数；

❏使用变量名在语句或表达式中调用实例方法。

例如，下面用例代码中的Flips类就使用了Counter类。它接受一个命令行参数T并模拟T次掷硬币（它还调用了StdRandom类）。除了这些直接用法外，我们可以和使用原始数据类型的变量一样使用和对象关联的变量：

❏赋值语句；

❏向方法传递对象或是从方法中返回对象；

❏创建并使用对象的数组。

接下来将逐个分析它们。你会发现，你需要从引用而非值的角度去考虑问题才能理解这些用法的行为。

1.2.1.8 赋值语句

使用引用类型的赋值语句将会创建该引用的一个副本。赋值语句不会创建新的对象，而只是创建另一个指向某个已经存在的对象的引用。这种情况被称为别名：两个变量同时指向同一个对象。别名的效果可能会出乎你的意料，因为对于原始数据类型的变量，情况不同，你必须理解其中的差异。如果x和y是原始数据类型的变量，那么赋值语句x = y会将y的值复制到x中。对于引用类型，复制的是引用（而非实际的值）。在Java中，别名是bug的常见原因，如下例所示（图1.2.4）：

Counter c1 = new Counter("ones");
c1.increment();
Counter c2 = c1;
c2.increment();
StdOut.println(c1);

对于一般的toString()实现，这段代码将会打印出"2 ones"。这可能并不是我们想要的，而且乍一看有些奇怪。这种问题经常出现在使用对象经验不足的人所编写的程序之中（可能就是你，所以请集中注意力！）。改变一个对象的状态将会影响到所有和该对象的别名有关的代码。我们习惯于认为两个不同的原始数据类型的变量是相互独立的，但这种感觉对于引用类型的变量并不适用。

1.2.1.9 将对象作为参数

可以将对象作为参数传递给方法，这一般都能简化用例代码。例如，当我们使用Counter对象作为参数时，本质上我们传递的是一个名称和一个计数器，但我们只需要指定一个变量。当我们调用一个需要参数的方法时，该动作在Java中的效果相当于每个参数值都出现在了一个赋值语句的右侧，而参数名则在该赋值语句的左侧。也就是说，Java将参数值的一个副本从调用端传递给了方法，这种方式称为按值传递（请见1.1.6.3节）。这种方式的一个重要后果是方法无法改变调用端变量的值。对于原始数据类型来说，这种策略正是我们所期望的（两个变量互相独立），但每当使用引用类型作为参数时我们创建的都是别名，所以就必须小心。换句话说，这种约定将会传递引用的值（复制引用），也就是传递对象的引用。例如，如果我们传递了一个指向Counter类型的对象的引用，那么方法虽然无法改变原始的引用（比如将它指向另一个Counter对象），但它能够改变该对象的值，比如通过该引用调用increment()方法。

1.2.1.10 将对象作为返回值

当然也能够将对象作为方法的返回值。方法可以将它的参数对象返回，如下面的例子所示，也可以创建一个对象并返回它的引用。这种能力非常重要，因为Java中的方法只能有一个返回值——有了对象我们的代码实际上就能返回多个值。

1.2.1.11 数组也是对象

在Java中，所有非原始数据类型的值都是对象。也就是说，数组也是对象。和字符串一样，Java语言对于数组的某些操作有特殊的支持：声明、初始化和索引。和其他对象一样，当我们将数组传递给一个方法或是将一个数组变量放在赋值语句的右侧时，我们都是在创建该数组引用的一个副本，而非数组的副本。对于一般情况，这种效果正合适，因为我们期望方法能够重新安排数组的条目并修改数组的内容，如java.util.Array.sort()或表1.1.10讨论的shuffle()方法。

1.2.1.12 对象的数组

我们已经看到，数组元素可以是任意类型的数据：我们实现的main()方法的args[]参数就是一个String对象的数组。创建一个对象的数组需要以下两个步骤：

❏使用方括号语法调用数组的构造函数创建数组；

❏对于每个数组元素调用它的构造函数创建相应的对象。

例如，下面这段代码模拟的是掷骰子。它使用了一个Counter对象的数组来记录每种可能的值的出现次数。在Java中，对象数组即是一个由对象的引用组成的数组，而非所有对象本身组成的数组。如果对象非常大，那么在移动它们时由于只需要操作引用而非对象本身，这就会大大提高效率；如果对象很小，每次获取信息时都需要通过引用反而会降低效率。

有了这些对象的知识，运用数据抽象的思想编写代码（定义和使用数据类型，将数据类型的值封装在对象中）的方式称为面向对象编程。刚才学习的基本概念是我们面向对象编程的起点，因此有必要对它们进行简单的总结。数据类型指的是一组值和一组对值的操作的集合。我们会将数据类型实现在独立的Java类模块中并编写它们的用例。对象是能够存储任意该数据类型的值的实体，或数据类型的实例。对象有三大关键性质：状态、标识和行为。一个数据类型的实现所支持的操作如下。

❏创建对象（创造它的标识）：使用new关键字触发构造函数并创建对象，初始化对象中的值并返回对它的引用。

❏操作对象中的值（控制对象的行为，可能会改变对象的状态）：使用和对象关联的变量调用实例方法来对对象中的值进行操作。

❏操作多个对象：创建对象的数组，像原始数据类型的值一样将它们传递给方法或是从方法中返回，只是变量关联的是对象的引用而非对象本身。

这些能力是这种灵活且应用广泛的现代编程方式的基础，也是我们在本书中对算法研究的基础。

1.2.2 抽象数据类型举例

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

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

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

❏ java.lang.＊中的标准系统抽象数据类型，可以被任意Java程序调用。

❏Java标准库中的抽象数据类型，如java.swt、java.net和java.io，它们也可以被任意Java程序调用，但需要import语句。

❏I/O处理类抽象数据类型，和StdIn和StdOut类似，允许我们处理多个输入输出流。

❏面向数据类抽象数据类型，它们的主要作用是通过封装数据的表示简化数据的组织和处理。稍后在本节中我们将介绍在计算几何和信息处理中的几个实际应用的例子，并会在以后将它们作为抽象数据类型用例的范例。

❏集合类抽象数据类型，它们的主要用途是简化对同一类型的一组数据的操作。我们将会在1.3节中介绍基本的Bag、Stack和Queue类，在第2章中介绍优先队列（PQ）及其相关的类，在第3章和第5章中分别介绍符号表（ST）和集合（SET）以及相关的类。

❏面向操作的抽象数据类型，我们用它们分析各种算法，如1.4节和1.5节所述。

❏图算法相关的抽象数据类型，它们包括一些用来封装各种图的表示的面向数据的抽象数据类型，和一些提供图的处理算法的面向操作的抽象数据类型。

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

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

1.2.2.1 几何对象

面向对象编程的一个典型例子是为几何对象设计数据类型。例如，表1.2.3至表1.2.5中的API为三种常见的几何对象定义了相应的抽象数据类型：Point2D（平面上的点）、Interval1D（直线上的间隔）、Interval2D（平面上的二维间隔，即和数轴对齐的长方形）。和以前一样，这些API都是自文档化的，它们的用例十分容易理解，列在了表1.2.5的后面。这段代码从命令行读取一个Interval2D的边界和一个整数T，在单位正方形内随机生成T个点并统计落在间隔之内的点数（用来估计该长方形的面积）。为了表现效果，用例还画出了间隔和落在间隔之外的所有点。这种计算方法是一个模型，它将计算几何图形的面积和体积的问题转化为了判定一个点是否落在该图形中（稍稍简单，但仍然不那么容易）。我们当然也能为其他几何对象定义API，比如线段、三角形、多边形、圆等，不过实现它们的相关操作可能十分有挑战性。本节末尾的练习会考察其中几个例子。

处理几何对象的程序在自然世界模型、科学计算、电子游戏、电影等许多应用的计算中有着广泛的应用。此类程序的研发已经发展成了计算几何学的这门影响深远的研究学科。在贯穿全书的众多例子中你会看到，我们在本书中学习的许多算法在这个领域都有应用。在这里我们要说明的是直接表示几何对象的抽象数据类型的定义并不困难且在用例中的应用也十分简洁。本书网站和本节末尾的若干练习都证明了这一点。

1.2.2.2 信息处理

无论是需要处理数百万信用卡交易的银行，还是需要处理数十亿点击的网络分析公司，或是需要处理数百万实验观察结果的科学研究小组，无数应用的核心都是组织和处理信息。抽象数据类型是组织信息的一种自然方式。虽然没有给出细节，表1.2.6中的两份API也展示了商业应用程序中的一种典型做法。这里的主要思想是定义和真实世界中的物体相对应的对象。一个日期就是一个日、月和年的集合，一笔交易就是一个客户、日期和金额的集合。这只是两个例子，我们也可以为客户、时间、地点、商品、服务和其他任何东西定义对象以保存相关的信息。每种数据类型都包含能够创建对象的构造函数和用于访问其中数据的方法。为了简化用例的代码，我们为每个类型都提供了两个构造函数，一个接受适当类型的数据，另一个则能够解析字符串中的数据（细节请见练习1.2.19）。和以前一样，用例并不需要知道数据的表示方法。用这种方式组织数据最常见的理由是将一个对象和它相关的数据变成一个整体：我们可以维护一个Transaction对象的数组，将Date值作为参数或是某个方法的返回值等。这些数据类型的重点在于封装数据，同时它们也可以确保用例的代码不依赖于数据的表示方法。我们不会深究这种组织信息的方式，需要注意的只是这种做法，以及实现继承的方法toString()、compareTo()、equals()和hashCode()可以使我们的算法处理任意类型的数据。我们会在1.2.5.4节中详细讨论继承的方法。例如，我们已经注意到，根据Java的习惯，在数据结构中包含一个toString()的实现可以帮助用例打印出由对象中的值组成的一个字符串。我们会在1.3节、2.5节、3.4节和3.5节中用Date类和Transaction类作为例子考察其他继承的方法所对应的习惯用法。1.3节给出了有关数据类型和Java语言的类型参数（泛型）机制的几个经典例子，它们都遵循了这些习惯用法。第2章和第3章也都利用了泛型和继承的方法来实现可以处理任意数据类型的高效排序和查找算法。

每当遇到逻辑上相关的不同类型的数据时，你都应该考虑像刚才的例子那样定义一个抽象数据类型。这么做能够帮助我们组织数据并在一般应用程序中极大地简化使用者的代码。它是我们在通向数据抽象之路上迈出的重要一步。

1.2.2.3 字符串

Java的String是一种重要而实用的抽象数据类型。一个String值是一串可以由索引访问的char值。String对象拥有许多实例方法，如表1.2.7所示。

String值和字符数组类似，但两者是不同的。数组能够通过Java语言的内置语法访问每个字符，String则为索引访问、字符串长度以及其他许多操作准备了实例方法。另一方面，Java语言为String的初始化和连接提供了特别的支持：我们可以直接使用字符串字面量而非构造函数来创建并初始化一个字符串，还可以直接使用+运算符代替concat()方法。我们不需要了解实现的细节，但是在第5章中你会看到，了解某些方法的性能特点在开发字符串处理算法时是非常重要的。为什么不直接使用字符数组代替String值？对于任何抽象数据类型，这个问题的答案都是一样的：为了使代码更加简洁清晰。有了String类型，我们可以写出清晰干净的用例代码而无需关心字符串的表示方式。先看一下右侧这段短小的列表，其中甚至含有一些需要我们在第5章才会学到的高级算法才能实现的强大操作。例如，split()方法的参数可以是正则表达式（请见5.4节）, “典型的字符串处理代码”（显示在下页）中split()的参数是"\\s+"，它表示“一个或多个制表符、空格、换行符或回车”。

1.2.2.4 再谈输入输出

1.1节中的StdIn、StdOut和StdDraw标准库的一个缺点是对于任意程序，我们只能接受一个输入文件、向一个文件输出或是产生一幅图像。有了面向对象编程，我们就能定义类似的机制来在一个程序中同时处理多个输入流、输出流和图像。具体来说，我们的标准库定义了数据类型In、Out和Draw，它们的API如表1.2.8至表1.2.10所示。当使用一个String类型的参数调用它们的构造函数时，In和Out会首先尝试在当前目录下查找指定的文件。如果找不到，它会假设该参数是一个网站的名称并尝试连接到那个网站（如果该网站不存在，它会抛出一个运行时异常）。无论哪种情况，指定的文件或网站都会成为被创建的输入或输出流对象的来源或目标，所有read＊()和print＊()方法都会指向那个文件或网站（如果你使用的是无参数的构造函数，对象将会使用标准的输入输出流）。这种机制使得单个程序能够处理多个文件和图像；你也能将这些对象赋给变量，将它们当做方法的参数、作为方法的返回值或是创建它们的数组，可以像操作任何类型的对象那样操作它们。下页所示的程序Cat就是一个In和Out的用例，它使用了多个输入流来将多个输入文件归并到同一个输出文件中。In和Out类也包括将仅含int、double或String类型值的文件读取为一个数组的静态方法（请见1.3.1.5节和练习1.2.15）。

1.2.3 抽象数据类型的实现

和静态方法库一样，我们也需要使用Java的类（class）实现抽象数据类型并将所有代码放入一个和类名相同并带有．java扩展名的文件中。文件的第一部分语句会定义表示数据类型的值的实例变量。它们之后是实现对数据类型的值的操作的构造函数和实例方法。实例方法可以是公共的（在API中说明）或是私有的（用于辅助计算，用例无法使用）。一个数据类型的定义中可能含有多个构造函数，而且也可能含有静态方法，特别是单元测试用例main()，它通常在调试和测试中很实用。作为第一个例子，我们来学习1.2.1.1节定义的Counter抽象数据类型的实现。它的完整实现（带有注释）如图1.2.5所示，在对它的各个部分的讨论中，我们还将该图作为参考。本书后面开发的每个抽象数据类型的实现都会含有和这个简单例子相同的元素。

1.2.3.1 实例变量

要定义数据类型的值（即每个对象的状态），我们需要声明实例变量，声明的方式和局部变量差不多。实例变量和你所熟悉的静态方法或是某个代码段中的局部变量最关键的区别在于：每一时刻每个局部变量只会有一个值，但每个实例变量则对应着无数值（数据类型的每个实例对象都会有一个）。这并不会产生二义性，因为我们在访问实例变量时都需要通过一个对象——我们访问的是这个对象的值。同样，每个实例变量的声明都需要一个可见性修饰符。在抽象数据类型的实现中，我们会使用private，也就是使用Java语言的机制来保证向使用者隐藏抽象数据类型中的数据表示，如下面的示例所示。如果该值在初始化之后不应该再被改变，我们也会使用final。Counter类型含有两个实例变量，一个String类型的值name和一个int类型的值count。如果我们使用public修饰这些实例变量（在Java中是允许的），那么根据定义，这种数据类型就不再是抽象的了，因此我们不会这么做。

1.2.3.2 构造函数

每个Java类都至少含有一个构造函数以创建一个对象的标识。构造函数类似于一个静态方法，但它能够直接访问实例变量且没有返回值。一般来说，构造函数的作用是初始化实例变量。每个构造函数都将创建一个对象并向调用者返回一个该对象的引用。构造函数的名称总是和类名相同。我们可以和重载方法一样重载这个名称并定义签名不同的多个构造函数。如果没有定义构造函数，类将会隐式定义一个默认情况下不接受任何参数的构造函数并将所有实例变量初始化为默认值。原始数字类型的实例变量默认值为0，布尔类型变量为false，引用类型变量为null。我们可以在声明语句中初始化这些实例变量并改变这些默认值。当用例使用关键字new时，Java会自动触发一个构造函数。重载构造函数一般用于将实例变量由默认值初始化为用例提供的值。例如，Counter类型有个接受一个参数的构造函数，它将实例变量name初始化为由参数给定的值（实例变量count仍将被初始化为默认值0）。构造函数解析如图1.2.6所示。

1.2.3.3 实例方法

实现数据类型的实例方法（即每个对象的行为）的代码和1.1节中实现静态方法（函数）的代码完全相同。每个实例方法都有一个返回值类型、一个签名（它指定了方法名、所有参数变量的类型和名称）和一个主体（它由一系列语句组成，包括一个返回语句来将一个返回类型的值传递给调用者）。当调用者触发了一个方法时，方法的参数（如果有）均会被初始化为调用者所提供的值，方法的语句会被执行，直到得到一个返回值并且将该值返回给调用者。它的效果就好像调用者代码中的函数调用被替换为了这个返回值。实例方法的所有这些行为都和静态方法相同，只有一点关键的不同：它们可以访问并操作实例变量。如何指定我们希望使用的对象的实例变量？只要稍加思考，就能够得到合理的答案：在一个实例方法中对变量的引用指的是调用该方法的对象中的值。当我们调用heads. increment()时，increment()方法中的代码访问的是heads中的实例变量。换句话说，面向对象编程为Java程序增加了另一种使用变量的重要方式。

❏通过触发一个实例方法来操作该对象的值。

这与调用静态方法仅仅是语法上的区别（请见答疑），但在许多情况下它颠覆了现代程序员对程序开发的思维方式。你会看到，这种方式与算法和数据结构的研究非常契合。实例方法解析如图1.2.7所示。

1.2.3.4 作用域

总的来说，我们在实现实例方法的Java代码中使用了三种变量：

❏参数变量；

❏局部变量；

❏实例变量。

前两者的用法和静态方法中一样：方法的签名定义了参数变量，在方法被调用时参数变量会被初始化为调用者提供的值；局部变量的声明和初始化都在方法的主体中。参数变量的作用域是整个方法；局部变量的作用域是当前代码段中它的定义之后的所有语句。实例变量则完全不同（如右侧示例所示）：它们为该类的对象保存了数据类型的值，它们的作用域是整个类（如果出现二义性，可以使用this前缀来区别实例变量）。理解实例方法中这三种变量的区别是理解面向对象编程的关键。

1.2.3.5 API、用例与实现

这些都是你要在Java中构造并使用抽象数据类型所需要理解的基本组件。我们将要学习的每个抽象数据类型的实现都会是一个含有若干私有实例变量、构造函数、实例方法和一个测试用例的Java类。要完全理解一个数据类型，我们需要它的API、典型的用例和它的实现。Counter类型的总结请见表1.2.11。为了强调用例和实现的分离，我们一般会将用例独立成为含有一个静态方法main()的类，并将数据类型定义中的main()方法预留为一个用于开发和最小单元测试的测试用例（至少调用每个实例方法一次）。我们开发的每种数据类型都会遵循相同的步骤。我们思考的不是应该采取什么行动来达成某个计算性的目的（如同我们第一次学习编程时那样），而是用例的需求。我们会按照下面三步走的方式用抽象数据类型满足它们。

❏定义一份API:API的作用是将使用和实现分离，以实现模块化编程。我们制定一份API的目标有二：第一，我们希望用例的代码清晰而正确，事实上，在最终确定API之前就编写一些用例代码来确保所设计的数据类型操作正是用例所需要的是很好的主意；第二，我们希望能够实现这些操作，定义一些无法实现的操作是没有意义的。

❏用一个Java类实现API的定义：首先我们选择适当的实例变量，然后再编写构造函数和实例方法。

❏实现多个测试用例来验证前两步做出的设计决定。

用例一般需要什么操作？数据类型的值应该是什么才能最好地支持这些操作？这些基本的判断是我们开发的每种实现的核心内容。

1.2.4 更多抽象数据类型的实现

和任何编程概念一样，理解抽象数据类型的威力和用法的最好办法就是仔细研究更多的例子和实现。本书中大量代码是通过抽象数据类型实现的，因此你的机会很多，但是一些更简单的例子能够帮助我们为研究抽象数据类型打好基础。

1.2.4.1 日期

表1.2.12是我们在表1.2.6中定义的Date抽象数据类型的两种实现。简单起见，我们省略了解析字符串的构造函数（请见练习1.2.19）和继承的方法equals()（请见1.2.5.8节）、compareTo()（请见2.1.1.4节）和hashCode()（请见练习3.4.22）。表1.2.12中左侧的简单实现将日、月和年设为实例变量，这样实例方法就可以直接返回适当的值；右侧的实现更加节省空间，仅使用了一个int变量来表示一个日期。它将d日、m月和y年的一个日期表示为一个混合进制的整数512y+32m+d。用例分辨这两种实现的区别的一种方法可能是打破我们对日期的隐式假设：第二种实现的正确性基于日的值在0到31之间，月的值在0到15之间，年的值为正（在实际应用中，两种实现都应该检查月份的值是否在1到12之间，日的值是否在1到31之间，以及例如2009年6月31日和2月29日这样的非法日期，尽管这么做要费些工夫）。这个例子的主要意思是说明我们在API中极少完整地指定对实现的要求（一般来说我们都会尽力而为，这里还可以做得更好）。用例要分辨出这两种实现的区别的另一种方法是性能：右侧的实现中保存数据类型的值所需的空间较少，代价是在向用例按照约定的格式提供这些值时花费的时间更多（需要进行一两次算术运算）。这种交换是很常见的：某些用例可能偏爱其中一种实现，而另一些用例可能更喜欢另一种，因此我们两者都要满足。事实上，本书中反复出现的一个主题就是我们需要理解各种实现对空间和时间的需求以及它们对各种用例的适用性。在实现中使用数据抽象的一个关键优势是我们可以将一种实现替换为另一种而无需改变用例的任何代码。

1.2.4.2 维护多个实现

同一份API的多个实现可能会产生维护和命名问题。在某些情况下，我们可能只是想将较老的实现替换为改进的实现。而在另一些情况下，我们可能需要维护两种实现，一种适用于某些用例，另一种适用于另一些用例。实际上，本书的一个主要目标就是深入讨论若干种基本抽象数据结构的实现并衡量它们的性能的不同。在本书中，我们经常会比较同一份API的两种不同实现在同一个用例中的性能表现。为此，我们通常采用一种非正式的命名约定。

❏通过前缀的描述性修饰符区别同一份API的不同实现。例如，我们可以将表1.2.12中的Date实现命名为BasicDate和SmallDate，我们可能还希望实现一种能够验证日期是否合法的SmartDate。

❏维护一个没有前缀的参考实现，它应该适合于大多数用例的需求。在这里，大多数用例应该直接会使用Date。

在一个庞大的系统中，这种解决方案并不理想，因为它可能会需要修改用例的代码。例如，如果需要开发一个新的实现ExtraSmallDate，那么我们只能修改用例的代码或是让它成为所有用例的参考实现。Java有许多高级语言特性来保证在无需修改用例代码的情况下维护多个实现，但我们很少会使用它们，因为即使Java专家使用起它们来也十分困难（有时甚至是有争议的），尤其是同我们极为需要的其他高级语言特性（泛型和迭代器）一起使用时。这些问题很重要（例如，忽略它们会导致千禧年著名的Y2K问题，因为许多程序使用的都是它们自己对日期的抽象实现，且并没有考虑到年份的头两位数字），但是深究它们会使我们大大偏离对算法的研究。

1.2.4.3 累加器

表1.2.13中的累加器API定义了一种能够为用例计算一组数据的实时平均值的抽象数据类型。例如，本书中经常会使用该数据类型来处理实验结果（请见1.4节）。它的实现很简单：它维护一个int类型的实例变量来记录已经处理过的数据值的数量，以及一个double类型的实例变量来记录所有数据值之和，将和除以数据数量即可得到平均值。请注意该实现并没有保存数据的值——它可以用于处理大规模的数据（甚至是在一个无法全部保存它们的设备上），而一个大型系统也可以大量使用累加器。这种性能特点很容易被忽视，所以也许应该在API中注明，因为一种存储所有数据值的实现可能会使调用它的应用程序用光所有内存。

1.2.4.4 可视化的累加器

表1.2.14所示的可视化累加器的实现继承了Accumulator类并展示了一种实用的副作用：它用StdDraw画出了所有数据（灰色）和实时的平均值（红色），见图1.2.8。完成这项任务最简单的办法是添加一个构造函数来指定需要绘出的点数和它们的最大值（用于调整图像的比例）。严格说来，VisualAccumulator并不是Accumulator的API的实现（它的构造函数的签名不同且产生了一种不同的副作用）。一般来说，我们会仔细而完整地设计API，并且一旦定型就不愿再对它做任何改动，因为这有可能会涉及修改无数用例（和实现）的代码。但添加一个构造函数来取得某些功能有时能够获得通过，因为它对用例的影响和改变类名所产生的变化相同。在本例中，如果已经开发了一个使用Accumulator的用例并大量调用了addDataValue()和mean()，只需改变用例的一行代码就能享受到VisualAccumulator的优势。

1.2.5 数据类型的设计

抽象数据类型是一种向用例隐藏内部表示的数据类型。这种思想强有力地影响了现代编程。我们遇到过的众多例子为我们研究抽象数据类型的高级特性和它们的Java实现打下了基础。简单看来，下面的许多话题和算法的学习关系不大，因此你可以跳过本节，在今后实现抽象数据类型中遇到特定问题时再回过头来参考它。我们的目的是将关于设计数据类型的重要知识集中起来以供参考，并为本书中的所有抽象数据类型的实现做铺垫。

1.2.5.1 封装

面向对象编程的特征之一就是使用数据类型的实现封装数据，以简化实现和隔离用例开发。封装实现了模块化编程，它允许我们：

❏独立开发用例和实现的代码；

❏切换至改进的实现而不会影响用例的代码；

❏支持尚未编写的程序（对于后续用例，API能够起到指南的作用）。

封装同时也隔离了数据类型的操作，这使我们可以：

❏限制潜在的错误；

❏在实现中添加一致性检查等调试工具；

❏确保用例代码更明晰。

一个封装的数据类型可以被任意用例使用，因此它扩展了Java语言。我们所提倡的编程风格是将大型程序分解为能够独立开发和调试的小型模块。这种方式将修改代码的影响限制在局部区域，改进了我们的软件质量。它也促进了代码复用，因为我们可以用某种数据类型的新实现代替老的实现来改进它的性能、准确度或是内存消耗。同样的思想也适用于许多其他领域。我们在使用系统库时常常从封装中受益。Java系统的新实现往往更新了多种数据类型或静态方法库的实现，但它们的API并没有变化。在算法和数据结构的学习中，我们总是希望开发出更好的算法，因为只需用抽象数据类型的改进实现替换老的实现即可在不改变任何用例代码的情况下改进所有用例的性能。模块化编程成功的关键在于保持模块之间的独立性。我们坚持将API作为用例和实现之间唯一的依赖点来做到这一点。并不需要知道一个数据类型是如何实现的才能使用它，实现数据类型时也应该假设使用者除了API什么也不知道。封装是获得所有这些优势的关键。

1.2.5.2 设计API

构建现代软件最重要也最有挑战的一项任务就是设计API。它需要经验、思考和反复的修改，但设计一份优秀的API所付出的所有时间都能从调试和代码复用所节省的时间中获得回报。为一个小程序给出一份API似乎有些多余，但你应该按照能够复用的方式编写每个程序。理想情况下，一份API应该能够清楚地说明所有可能的输入和副作用，然后我们应该先写出检查实现是否与API相符的程序。但不幸的是，计算机科学理论中一个叫做说明书问题（specification problem）的基础结论说明这个目标是不可能实现的。简单地说，这样一份说明书应该用一种类似于编程语言的形式语言编写。而从数学上可以证明，判定这样两个程序进行的计算是否相同是不可能的。因此，我们的API将是与抽象数据类型相关联的值以及一系列构造函数和实例方法的目的和副作用的自然语言描述。为了验证我们的设计，我们会在API附近的正文中给出一些用例代码。但是，这些宏观概述之中也隐藏着每一份API设计都可能落入的无数陷阱。

❏API可能会难以实现：实现的开发非常困难，甚至不可能。

❏API可能会难以使用：用例代码甚至比没有API时更复杂。

❏API的范围可能太窄：缺少用例所需的方法。

❏API的范围可能太宽：包含许多不会被任何用例调用的方法。这种缺陷可能是最常见的，并且也是最难以避免的。API的大小一般会随着时间而增长，因为向已有的API中添加新方法很简单，但在不破坏已有用例程序的前提下从中删除方法却很困难。

❏API可能会太粗略：无法提供有效的抽象。

❏API可能会太详细：抽象过于细致或是发散而无法使用。

❏API可能会过于依赖某种特定的数据表示：用例代码可能会因此无法从数据表示的细节中解脱出来。要避免这种缺陷也是很困难的，因为数据表示显然是抽象数据类型实现的核心。

这些考虑有时又被总结为另一句格言：只为用例提供它们所需要的，仅此而已。

1.2.5.3 算法与抽象数据类型

数据抽象天生适合算法研究，因为它能够为我们提供一个框架，在其中能够准确地说明一个算法的目的以及其他程序应该如何使用该算法。在本书中，算法一般都是某个抽象数据类型的一个实例方法的实现。例如，本章开头的白名单例子就很自然地被实现为一个抽象数据类型的用例。它进行了以下操作：

❏由一组给定的值构造了一个SET（集合）对象；

❏判定一个给定的值是否存在于该集合中。

这些操作封装在StaticSETofInts抽象数据类型中，和Whitelist用例一起显示在表1.2.15中。StaticSETofInts是更一般也更有用的符号表抽象数据类型的一种特殊情况，符号表抽象数据类型将是第3章的重点。在我们研究过的所有算法中，二分查找是较为适合用于实现这些抽象数据类型的一种。和1.1.10节中的BinarySearch实现比较起来，这里的实现所产生的用例代码更加清晰和高效。例如，StaticSETofInts强制要求数组在rank()方法被调用之前排序。有了抽象数据类型，我们可以将抽象数据类型的调用和实现区分开来，并确保任意遵守API的用例程序都能受益于二分查找算法（使用BinarySearch的程序在调用rank()之前必须能够将数组排序）。白名单应用是众多二分查找算法的用例之一。

每个Java程序都是一组静态方法和（或）一种数据类型的实现的集合。在本书中我们主要关注的是抽象数据类型的实现中的操作和向用例隐藏其中的数据表示，例如StaticSETofInts。正如这个例子所示，数据抽象使我们能够：

❏准确定义算法能为用例提供什么；

❏隔离算法的实现和用例的代码；

❏实现多层抽象，用已知算法实现其他算法。

无论是使用自然语言还是伪代码描述算法，这些都是我们所希望拥有的性质。使用Java的类机制来支持数据的抽象将使我们收获良多：我们编写的代码将能够测试算法并比较各种用例程序的性能。

1.2.5.4 接口继承

Java语言为定义对象之间的关系提供了支持，称为接口。程序员广泛使用这些机制，如果上过软件工程的课程那么你可以详细地研究一下它们。我们学习的第一种继承机制叫做子类型。它允许我们通过指定一个含有一组公共方法的接口为两个本来并没有关系的类建立一种联系，这两个类都必须实现这些方法。例如，如果不使用我们的非正式API，也可以为Date声明一个接口：

public interface Datable
{
    int month();
    int day();
    int year();
}

并在我们的实现中引用该接口：

public class Date implements Datable
{
    // 实现代码（和以前一样）
}

这样，Java编译器就会检查该实现是否和接口相符。为任意实现了month()、day()和year()的类添加implements Datable保证了所有用例都能用该类的对象调用这些方法。这种方式称为接口继承——实现类继承的是接口。接口继承使得我们的程序能够通过调用接口中的方法操作实现该接口的任意类型的对象（甚至是还未被创建的类型）。我们可以在更多非正式的API中使用接口继承，但为了避免代码依赖于和理解算法无关的高级语言特性以及额外的接口文件，我们并没有这么做。在某些情况下Java的习惯用法鼓励我们使用接口：我们用它们进行比较和迭代，如表1.2.16所示。我们会在接触那些概念时再详细研究它们。

1.2.5.5 实现继承

Java还支持另一种继承机制，被称为子类。这种非常强大的技术使程序员不需要重写整个类就能改变它的行为或者为它添加新的功能。它的主要思想是定义一个新类（子类，或称为派生类）来继承另一个类（父类，或称为基类）的所有实例方法和实例变量。子类包含的方法比父类更多。另外，子类可以重新定义或者重写父类的方法。子类继承被系统程序员广泛用于编写所谓可扩展的库——任何一个程序员（包括你）都能为另一个程序员（或者也许是一个系统程序员团队）创建的库添加方法。这种方法能够有效地重用潜在的十分庞大的库中的代码。例如，这种方法被广泛用于图形用户界面的开发，因此实现用户所需要的各种控件（下拉菜单，剪切——粘贴，文件访问等）的大量代码都能够被重用。子类继承的使用在系统程序员和应用程序员之间是有争议的（它和接口继承之间的优劣还没有定论）。在本书中我们会避免使用它，因为它会破坏封装。但这种机制是Java的一部分，因此它的残余是无法避免的：具体来说，每个类都是Java的Object类的子类。这种结构意味着每个类都含有getClass()、toString()、equals()、hashCode()（见表1.2.17）和另外几个我们不会在本书中用到的方法的实现。实际上，每个类都通过子类继承从Object类中继承了这些方法，因此任何用例都可以在任意对象中调用这些方法。我们通常会重载新类的toString()、equals()和hashCode()方法，因为Object类的默认实现一般无法提供所需的行为。接下来我们将讨论toString()和equals()，在3.4节中讨论hashCode()。

1.2.5.6 字符串表示的习惯

按照习惯，每个Java类型都会从Object继承toString()方法，因此任何用例都能够调用任意对象的toString()方法。当连接运算符的一个操作数是字符串时，Java会自动将另一个操作数也转换为字符串，这个约定是这种自动转换的基础。如果一个对象的数据类型没有实现toString()方法，那么转换会调用Obejct的默认实现。默认实现一般都没有多大实用价值，因为它只会返回一个含有该对象内存地址的字符串。因此我们通常会为我们的每个类实现并重写默认的toString()方法，如下面代码框的Date类中加粗的部分所示。由代码可以看到，toString()方法的实现通常很简单，只需隐式调用（通过+）每个实例变量的toString()方法即可。

1.2.5.7 封装类型

Java提供了一些内置的引用类型，称为封装类型。每种原始数据类型都有一个对应的封装类型：Boolean、Byte、Character、Double、Float、Integer、Long和Short分别对应着boolean、byte、char、double、float、int、long和short。这些类主要由类似于parseInt()这样的静态方法组成，但它们也含有继承得到的实例方法toString()、compareTo()、equals()和hashCode()。在需要的时候Java会自动将原始数据类型转换为封装类型，如1.3.1.1节所述。例如，当一个int值需要和一个String连接时，它的类型会被转换为Integer并触发toString()方法。

1.2.5.8 等价性

两个对象相等意味着什么？如果我们用相同类型的两个引用变量a和b进行等价性测试（a ==b），我们检测的是它们的标识是否相同，即引用是否相同。一般用例希望能够检查数据类型的值（对象的状态）是否相同或者实现某种针对该类型的规则。Java为我们开了个头，为Integer、Double和String等标准数据类型以及一些如File和URL的复杂数据类型提供了实现。在处理这些类型的数据时，可以直接使用内置的实现。例如，如果x和y均为String类型的值，那么当且仅当x和y的长度相同且每个位置的字符均相同时x.equals(y)的返回值为true。当我们在定义自己的数据类型时，比如Date或Transaction，需要重载equals()方法。Java约定equals()必须是一种等价性关系。它必须具有：

❏自反性，x.equals(x)为true；

❏对称性，当且仅当y.equals(x)为true时，x.equals(y)返回true；

❏传递性，如果x.equals(y)和y.equals(z)均为true, x.equals(z)也将为true。

另外，它必须接受一个Object为参数并满足以下性质：

❏一致性，当两个对象均未被修改时，反复调用x.equals(y)总是会返回相同的值；

❏非空性，x.equals(null)总是返回false。

这些定义都是自然合理的，但确保这些性质成立并遵守Java的约定，同时又避免在实现时做无用功却并不容易，如Date所示。它通过以下步骤做到了这一点。

❏如果该对象的引用和参数对象的引用相同，返回true。这项测试在成立时能够免去其他所有测试工作。

❏如果参数为空（null），根据约定返回false（还可以避免在下面的代码中使用空引用）。

❏如果两个对象的类不同，返回false。要得到一个对象的类，可以使用getClass()方法。请注意我们会使用==来判断Class类型的对象是否相等，因为同一种类型的所有对象的getClass()方法一定能够返回相同的引用。

❏将参数对象的类型从Object转换到Date（因为前一项测试已经通过，这种转换必然成功）。

❏如果任意实例变量的值不相同，返回false。对于其他类，等价性测试方法的定义可能不同。例如，我们只有在两个Counter对象的count变量相等时才会认为它们相等。

你可以使用上面的实现作为实现任意数据类型的equals()方法的模板。只要实现一次equals()方法，下一次就不会那么困难了。

1.2.5.9 内存管理

我们可以为一个引用变量赋予一个新的值，因此一段程序可能会产生一个无法被引用的对象。例如，请看图1.2.9中所示的三行赋值语句。在第三行赋值语句之后，不仅a和b会指向同一个Date对象（1/1/2011），而且不存在能够引用初始化变量a的那个Date对象的引用了。本来该对象的唯一引用就是变量a，但是该引用被赋值语句覆盖了，这样的对象被称为孤儿。对象在离开作用域之后也会变成孤儿。Java程序经常会创建大量对象（以及许多保存原始数据类型值的变量），但在某个时刻程序只会需要它们之中的一小部分。因此，编程语言和系统需要某种机制来在必要时为数据类型的值分配内存，而在不需要时释放它们的内存（对于一个对象来说，有时是在它变成孤儿之后）。内存管理对于原始数据类型更容易，因为内存分配所需要的所有信息在编译阶段就能够获取。Java（以及大多数其他系统）会在声明变量时为它们预留内存空间，并会在它们离开作用域后释放这些空间。对象的内存管理更加复杂：系统会在创建一个对象时为它分配内存，但是程序在执行时的动态性决定了一个对象何时才会变为孤儿，系统并不能准确地知道应该何时释放一个对象的内存。在许多语言中（例如C和C++），分配和释放内存是程序员的责任。众所周知，这种操作既繁琐又容易出错。Java最重要的一个特性就是自动内存管理。它通过记录孤儿对象并将它们的内存释放到内存池中将程序员从管理内存的责任中解放出来。这种回收内存的方式叫做垃圾回收。Java的一个特点就是它不允许修改引用的策略。这种策略使Java能够高效自动地回收垃圾。程序员们至今仍在争论，为获得无需为内存管理操心的方便而付出的使用自动垃圾回收的代价是否值得。

1.2.5.10 不可变性

不可变数据类型，例如Date，指的是该类型的对象中的值在创建之后就无法再被改变。与此相反，可变数据类型，例如Counter或Accumulator，能够操作并改变对象中的值。Java语言通过final修饰符来强制保证不可变性。当你将一个变量声明为final时，也就保证了只会对它赋值一次，可以用赋值语句，也可以用构造函数。试图改变final变量的值的代码将会产生一个编译时错误。在我们的代码中，我们用final修饰值不会改变的实例变量。这种策略就像文档一样，说明了这个变量的值不会再发生改变，它能够预防意外修改，也能使程序的调试更加简单。像Date这样实例变量均为原始数据类型且被final修饰的数据类型（按照约定，在不使用子类继承的代码中）是不可变的。数据类型是否可变是一个重要的设计决策，它取决于当前的应用场景。对于类似于Date的数据类型，抽象的目的是封装不变的值，以便将其和原始数据类型一样用于赋值语句、作为函数的参数或返回值（而不必担心它们的值会被改变）。程序员在使用Date时可能会写出操作两个Date类型的变量的代码d = d0，就像操作double或者int值一样。但如果Date类型是可变的且d的值在d = d0之后可以被改变，那么d0的值也会被改变（它们都是指向同一个对象的引用）！从另一方面来说，对于类似于Counter和Accumulator的数据类型，抽象的目的是封装变化中的值。作为用例程序员，你在使用Java数组（可变）和Java的String类型（不可变）时就已经遇到了这种区别。将一个String传递给一个方法时，你不会担心该方法会改变字符串中的字符顺序，但当你把一个数组传递给一个方法时，方法可以自由改变数组的内容。String对象是不可变的，因为我们一般都不希望String的值改变，而Java数组是可变的，因为我们一般的确希望改变数组中的值。但也存在我们希望使用可变字符串（这就是Java的StringBuilder类存在的目的）和不可变数组（这就是稍后讨论的Vector类存在的目的）的情况。一般来说，不可变的数据类型比可变的数据类型使用更容易，误用更困难，因为能够改变它们的值的方式要少得多。调试使用不可变类型的代码更简单，因为我们更容易确保用例代码中使用它们的变量的状态前后一致。在使用可变数据类型时，必须时刻关注它们的值会在何时何地发生变化。而不可变性的缺点在于我们需要为每个值创建一个新对象。这种开销一般是可以接受的，因为Java的垃圾回收器通常都为此进行了优化。不可变性的另一个缺点在于，final非常不幸地只能用来保证原始数据类型的实例变量的不可变性，而无法用于引用类型的变量。如果一个引用类型的实例变量含有修饰符final，该实例变量的值（某个对象的引用）就永远无法改变了——它将永远指向同一个对象，但对象的值本身仍然是可变的。例如，这段代码并没有实现一个不可变的数据类型：

public class Vector
{
    private final double[] coords;
    public Vector(double[] a)
    {  coords = a; }
    ..
}

用例程序可以通过给定的数组创建一个Vector对象，并在构造函数执行之后（绕过API）改变Vector中的元素的值：

double[] a = { 3.0, 4.0 };
Vector vector = new Vector(a);
a[0] = 0.0;  // 绕过了公有API

实例变量coords[]是private和final的，但Vector是可变的，因为用例拥有指向数据的一个引用。任何数据类型的设计都需要考虑到不可变性，而且数据类型是否是不可变的则应该在API中说明，这样使用者才能知道该对象中的值是无法改变的。在本书中，我们对不可变性的主要兴趣在于用它保证我们的算法的正确性。例如，如果一个二分查找算法所使用的数据的类型是可变的，那么算法的用例就可能破坏我们对二分查找中的数组已经有序的假设。可变数据与不可变数据的示例见表1.2.18。

表1.2.18 可变与不可变数据类型举例

1.2.5.11 契约式设计

在最后，我们将简要讨论Java语言中能够在程序运行时检验程序状态的一些机制。为此我们将使用两种Java的语言特性：

❏异常（Exception），一般用于处理不受我们控制的不可预见的错误；

❏断言（Assertion），验证我们在代码中做出的一些假设。

大量使用异常和断言是很好的编程实践。为了节约版面我们在本书中极少使用它们，但你在本书网站上的所有代码中都会找到它们。这些代码中的每个和异常条件以及断言恒等式有关的算法周围都有大量的注释。

1.2.5.12 异常与错误

异常和错误都是在程序运行中出现的破坏性事件。Java采取的行动称为抛出异常或是抛出错误。我们已经在学习Java的基本特性的过程中遇到过Java系统方法抛出的异常：StackOverflowError、ArithmeticException、ArrayIndexOutOfBoundsException、OutOfMemoryError和NullPointerException都是典型的例子。你也可以创建自己的异常，最简单的一种是RuntimeException，它会中断程序的执行并打印出一条出错信息：

throw new RuntimeException("Error message here.");

一种叫做快速出错的常规编程实践提倡，一旦出错就立刻抛出异常，使定位出错位置更容易（这和忽略错误并将异常推迟到以后处理的方式相反）。

1.2.5.13 断言

断言是一条需要在程序的某处确认为true的布尔表达式。如果表达式的值为false，程序将会终止并报告一条出错信息。我们使用断言来确定程序的正确性并记录我们的意图。例如，假设你计算得到一个值并可以将它作为索引访问一个数组。如果该值为负数，稍后它将会产生一条ArrayIndexOutOfBoundsException异常。但如果代码中有一句assert index ＞= 0;，你就能找到出错的位置。还可以选择性地加上一条详细的消息来辅助定位bug，例如：

assert index ＞= 0 : "Negative index in method X";

默认设置没有启用断言，可以在命令行下使用-enableassertions标志（简写为-ea）启用断言。断言的作用是调试：程序在正常操作中不应该依赖断言，因为它们可能会被禁用。系统编程课程会学习使用断言来保证代码永远不会被系统错误终止或是进入死循环。一种叫做契约式设计的编程模型采用的就是这种思想。数据类型的设计者需要说明前提条件（用例在调用某个方法前必须满足的条件）、后置条件（实现在方法返回时必须达到的要求）和副作用（方法可能对对象状态产生的任何其他变更）。在开发过程中，这些条件可以用断言进行测试。

1.2.5.14 小结

本节所讨论的语言机制说明实用数据类型的设计中所遇到的问题并不容易解决。专家们仍然在讨论支持某些我们已经学习过的设计理念的最佳方法。为什么Java不允许将函数作为参数？为什么Matlab会复制作为参数传递给函数的数组？正如本章前文所述，如果你总是抱怨编程语言的特性，那么你只能自己设计编程语言了。如果你不希望这样，最好的策略就是使用应用最广泛的编程语言。大多数系统都含有大量的库，在适当的时候你应该能用到它们，但通常你都能够通过构造易于移植到其他编程语言的抽象层来简化用例代码并进行自我保护。设计数据类型是你的主要目标，从而使大多数工作都能在抽象层次完成，且和手头的问题匹配。

表1.2.19总结了我们讨论过的各种Java类。

答疑

问 为什么要使用数据抽象？

答 它能够帮助我们编写可靠而正确的代码。例如，在2000年的美国总统竞选中，Al Gore在弗罗里达州的Volusia县的一个电子计票机上得到了-16022张选票——显然电子计票机软件中的选票计数器的封装不正确！

问 为什么要区别原始数据类型和引用类型？为什么不只用引用类型？

答 因为性能。Java提供了Integer、Double等和原始数据类型对应的引用类型，以供希望忽略这些类型的区别的程序员使用。原始数据类型更接近计算机硬件所支持的数据类型，因此使用它们的程序比使用引用类型的程序运行得更快。

问 数据类型必须是抽象的吗？

答 不。Java也支持public和protected来帮助用例直接访问实例变量。如正文所述，允许用例代码直接访问数据所带来的好处比不上对数据的特定表示方式的依赖所带来的坏处，因此我们代码中所有的实例变量都是私有的（private），有时也会使用私有实例方法在公有方法之间共享代码。

问 如果我在创建一个对象时忘记使用new关键字会发生什么？

答 对于Java，这种代码看起来就好像你希望调用一个静态方法，却得到一个对象类型的返回值。因为并没有定义这样一个方法，你得到的错误信息和引用一个未定义的符号是一样的。如果编译这段代码：

Counter c = Counter("test");

会得到这条错误信息：

cannot find symbol
symbol  : method Counter(String)

如果你提供给构造函数的参数数量不对，也会得到相同的出错信息。

问 如果我在创建一个对象数组时忘记使用new关键字会发生什么？

答 创建每个对象都需要使用new，所以要创建一个含有N个对象的数组，需要使用N+1次new关键字：创建数组需要一次，创建每个对象各需要一次。如果忘了创建数组：

Counter[] a;
a[0] = new Counter("test");

你得到的错误信息和尝试为一个未初始化的变量赋值是一样的：

variable a might not have been initialized
      a[0] = new Counter("test");
      ^

但如果在创建数组中的一个对象时忘了使用new，然后又尝试调用它的方法，会得到一个

NullPointerException：
Counter[] a = new Counter[2];
a[0].increment();

问 为什么不用StdOut.println(x.toString())来打印对象？

答 这条语句也可以，但Java能够自动调用任意对象的toString()方法来帮我们省去这些麻烦，因为println()接受的参数是一个Object对象。

问 指针是什么？

答 问得好。或许上面那个异常应该叫做NullReferenceException。和Java的引用一样，可以把指针看做机器地址。在许多编程语言中，指针是一种原始数据类型，程序员可以用各种方法操作它。但众所周知，指针的编程非常容易出错，因此需要精心设计指针类的操作以帮助程序员避免错误。Java将这种观点发挥到了极致（许多主流编程语言的设计者也赞同这种做法）。在Java中，创建引用的方法只有一种（new），且改变引用的方法也只有一种（赋值语句）。也就是说，程序员能对引用进行的操作只有创建和复制。在编程语言的行话里，Java的引用被称为安全指针，因为Java能够保证每个引用都会指向某种类型的对象（而且它能找出无用的对象并将其回收）。习惯于编写直接操作指针的程序员认为Java完全没有指针，但人们仍在为是否真的需要不安全的指针而争论。

问 我在哪里能够找到Java如何实现引用和进行垃圾收集的细节？

答 Java系统的实现各有不同。例如，实现引用的一种自然方式是使用指针（机器地址）；而另一种使用的则可能是句柄（指针的指针）。前者访问数据的速度更快，而后者则能够更好地实现垃圾回收。

问 导入（import）一个对象名意味着什么？

答 没什么，只是可以少打一些字。如果不想使用import语句，你也可以在代码中用java.util. Arrays代替所有的Arrays。

问 实现继承有什么问题？

答 子类继承阻碍模块化编程的原因有两点。第一，父类的任何改动都会影响它的所有子类。子类的开发不可能和父类无关。事实上，子类是完全依赖于父类的。这种问题被称为脆弱的基类问题。第二，子类代码可以访问所有实例变量，因此它们可能会扭曲父类代码的意图。例如，用于选票统计系统的Counter类的设计者可能会尽最大努力保证Counter每次只能将计数器加一（还记得Al Gore的问题吗）。但它的子类可以完全访问这个实例变量，因此可以将它改变为任意值。

问 怎样才能使一个类不可变？

答 要保证含有一个可变类型的实例变量的数据类型的不可变性，需要得到一个本地副本，这被称为保护性复制，但这也不一定能够达到目的。得到副本是一个方面，保证没有任何实例方法能够改变数据的值是另一方面。

问 什么是空（null）？

答 它是一个不指向任何对象的字面量。引用null调用一个方法是没有意义的，并且会产生NullPointerException。如果你得到了这条错误信息，请检查并确认构造函数是否正确地初始化了类的所有实例变量。

问 实现某种数据类型的类中能否存在静态方法？

答 当然可以。例如，我们实现的所有类中都含有一个main()方法。另外，对于涉及多个对象的操作，如果它们都不是触发该方法的合适对象，那么就应该考虑添加一个静态方法。例如，我们可以在Point类中定义如下静态方法：

public static double distance(Point a, Point b)
{
    return a.distTo(b);
}

这种方法常常能够简化用例代码。

问 除了参数变量、局部变量和实例变量外还有其他种类的变量吗？

答 如果你在类的声明中包含了关键字static（在其他类型之前），就创建了一种称为静态变量的完全不同的变量。和实例变量一样，类中的所有方法都可以访问静态变量，但静态变量却并不和任何具体的对象相关联。在较老的编程语言中，这种变量被称为全局变量，因为它们的作用域是全局的。在现代编程中，我们希望限制变量的作用域，因此很少使用这种变量。在使用它们时会非常小心。

问 什么是弃用（deprecated）的方法？

答 不再被支持但为了保持兼容性而留在API中的方法叫做弃用的方法。例如，Java曾经包含了一个Character.isSpace()的方法，程序员也使用这个方法编写了一些程序。当Java的设计者们后来希望支持Unicode空白字符时，他们无法既改变isSpace()的行为又不损害用例程序。因此他们添加了一个新方法Character.isWhiteSpace()并放弃了老的方法。随着时间的推移，这种方式显然会使API更复杂。有时候甚至整个类都会被弃用。例如，Java为了更好地支持国际化就将它的java. util.Date标记为弃用。

练习

1.2.1 编写一个Point2D的用例，从命令行接受一个整数N。在单位正方形中生成N个随机点，然后计算两点之间的最近距离。

1.2.2 编写一个Interval1D的用例，从命令行接受一个整数N。从标准输入中读取N个间隔（每个间隔由一对double值定义）并打印出所有相交的间隔对。

1.2.3 编写一个Interval2D的用例，从命令行接受参数N、min和max。生成N个随机的2D间隔，其宽和高均匀地分布在单位正方形中的min和max之间。用StdDraw画出它们并打印出相交的间隔对的数量以及有包含关系的间隔对数量。

1.2.4 以下这段代码会打印出什么？

String string1 = "hello";
String string2 = string1;
string1 = "world";
StdOut.println(string1);
StdOut.println(string2);

1.2.5 以下这段代码会打印出什么？

String s = "Hello World";
s.toUpperCase();
s.substring(6, 11);
StdOut.println(s);

答："Hello World"。String对象是不可变的——所有字符串方法都会返回一个新的String对象（但它们不会改变参数对象的值）。这段代码忽略了返回的对象并直接打印了原字符串。要打印出"WORLD"，请用s = s.toUpperCase()和s = s.substring(6, 11)。

1.2.6 如果字符串s中的字符循环移动任意位置之后能够得到另一个字符串t，那么s就被称为t的回环变位（circular rotation）。例如，ACTGACG就是TGACGAC的一个回环变位，反之亦然。判定这个条件在基因组序列的研究中是很重要的。编写一个程序检查两个给定的字符串s和t是否互为回环变位。提示：答案只需要一行用到indexOf()、length()和字符串连接的代码。

1.2.7 以下递归函数的返回值是什么？

public static String mystery(String s)
{
    int N = s.length();
    if (N ＜= 1) return s;
    String a = s.substring(0, N/2);
    String b = s.substring(N/2, N);
    return mystery(b) + mystery(a);
}

1.2.8 设a[]和b[]均为长数百万的整形数组。以下代码的作用是什么？有效吗？

int[] t = a; a = b; b = t;

答：这段代码会将它们交换。它的效率不可能再高了，因为它复制的是引用而不需要复制数百万个元素。

1.2.9 修改BinarySearch（请见1.1.10.1节中的二分查找代码），使用Counter统计在有查找中被检查的键的总数并在查找全部结束后打印该值。提示：在main()中创建一个Counter对象并将它作为参数传递给rank()。

1.2.10 编写一个类VisualCounter，支持加一和减一操作。它的构造函数接受两个参数N和max，其中N指定了操作的最大次数，max指定了计数器的最大绝对值。作为副作用，用图像显示每次计数器变化后的值。

1.2.11 根据Date的API实现一个SmartDate类型，在日期非法时抛出一个异常。

1.2.12 为SmartDate添加一个方法dayOfTheWeek()，为日期中每周的日返回Monday、Tuesday、Wednesday、Thursday、Friday、Saturday或Sunday中的适当值。你可以假定时间是21世纪。

1.2.13 用我们对Date的实现（请见表1.2.12）作为模板实现Transaction类型。

1.2.14 用我们对Date中的equals()方法的实现（请见1.2.5.8节中的Date类代码框）作为模板，实现Transaction中的equals()方法。

提高题

1.2.15 文件输入。基于String的split()方法实现In中的静态方法readInts()。

解答：

public static int[] readInts(String name)
{
    In in = new In(name);
    String input = in.readAll();
    String[] words = input.split("\\s+");
    int[] ints = new int[words.length];
    for(int i = 0; i ＜ word.length; i++)
      ints[i] = Integer.parseInt(words[i]);
    return ints;
}

我们会在1.3节中学习另一个不同的实现（请见1.3.1.5节）。

1.2.16 有理数。为有理数实现一个不可变数据类型Rational，支持加减乘除操作。

无需测试溢出（请见练习1.2.17），只需使用两个long型实例变量表示分子和分母来控制溢出的可能性。使用欧几里得算法来保证分子和分母没有公因子。编写一个测试用例检测你实现的所有方法。

1.2.17 有理数实现的健壮性。在Rational（请见练习1.2.16）的开发中使用断言来防止溢出。

1.2.18 累加器的方差。以下代码为Accumulator类添加了var()和stddev()方法，它们计算了addDataValue()方法的参数的方差和标准差，验证这段代码。

public class Accumulator
{
    private double m;
    private double s;
    private int N;
    public void addDataValue(double x)
    {
      N++;
      s = s + 1.0 ＊ (N-1) / N ＊ (x - m) ＊ (x - m);
      m = m + (x - m) / N;
    }
    public double mean()
    {  return m;  }
    public double var()
    {  return s/(N -1);  }
    public double stddev()
    {  return Math.sqrt(this.var());  }
}

与直接对所有数据的平方求和的方法相比较，这种实现能够更好地避免四舍五入产生的误差。

1.2.19 字符串解析。为你在练习1.2.13中实现的Date和Transaction类型编写能够解析字符串数据的构造函数。它接受一个String参数指定的初始值，格式如表1.2.20所示：

部分解答：

public Date(String date)
{
    String[] fields = date.split("/");
    month = Integer.parseInt(fields[0]);
    day   = Integer.parseInt(fields[1]);
    year  = Integer.parseInt(fields[2]);
}