数据结构与算法之ACM Fellow-算法 1.2 数据抽象

数据结构与算法之ACM Fellow-算法 1.2 数据抽象

数据类型 指的是一组值和一组对这些值的操作的集合。目前，我们已经详细讨论过 Java 的 原始 数据类型：例如，原始数据类型 int 的取值范围是 ![-2^ /740932/image00851.gif) 到 ![2^-1/740932/image00852.gif) 之间的整数， int 的操作包括+、*、-、/、%、< 和 >。原则上所有程序都只需要使用原始数据类型即可，但在更高层次的抽象上编写程序会更加方便。在本节中，我们将重点学习定义和使用 数据类型，这个过程也被称为数据抽象（它是对 1.1 节所述的 函数抽象 风格的补充）。
Java 编程的基础主要是使用 class 关键字构造被称为 引用类型 的数据类型。这种编程风格也称为 面向对象编程，因为它的核心概念是 对象，即保存了某个数据类型的值的实体。如果只有 Java 的原始数据类型，我们的程序会在很大程度上被限制在算术计算上，但有了引用类型，我们就能编写操作字符串、图像、声音以及 Java 的标准库中或者本书的网站上的数百种抽象类型的程序。比各种库中预定义的数据类型更重要的是 Java 编程中的数据类型的种类是无限的，因为 你能够定义自己的数据类型来抽象任意对象。
抽象数据类型（ADT）是一种能够对使用者隐藏数据表示的数据类型。用 Java 类来实现抽象数据类型和用一组静态方法实现一个函数库并没有什么不同。抽象数据类型的主要不同之处在于它将 数据 和函数的实现关联，并将数据的表示方式隐藏起来。在 使用 抽象数据类型时，我们的注意力集中在 API 描述的 操作 上而不会去关心数据的表示；在 实现 抽象数据类型时，我们的注意力集中在 数据 本身并将实现对该数据的各种操作。
抽象数据类型之所以重要是因为在程序设计上它们支持封装。在本书中，我们将通过它们：

• 以适用于各种用途的 API 形式准确地定义问题；
  
• 用 API 的实现描述算法和数据结构。
  

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

附赠网盘下载地址

我用夸克网盘分享了「2025年AcWing在线课程VIP系列」，点击链接即可保存。
链接：https://pan.quark.cn/s/239188bc72b7
更多资源进+夸克网盘资源群 https://pan.quark.cn/g/4d94f2ef63
群满+新夸克共享群：https://link3.cc/cowcowit

要使用 一种数据类型并不一定非得知道它是如何实现的，所以我们首先来编写一个使用一种名为 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 中将它们显示为灰色。
  

表 1.2.1　计数器的 API
public class Counter``             Counter(String id)创建一个名为 id 的计数器      void   increment()将计数器的值加 1       int   tally()该对象创建之后计数器被加 1 的次数    String   toString()对象的字符串表示
和静态方法库的 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 类型的数据关联起来：

1. Counter heads;

复制代码

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

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

• 为新的对象分配内存空间；
  
• 调用构造函数初始化对象中的值；
  
• 返回该对象的一个引用。
  

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

1. Counter heads = new Counter("heads");
2. Counter tails = new Counter("tails");

复制代码

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

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

1. heads.increment();

复制代码

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

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

复制代码

以上示例的调用过程见图 1.2.3。
![/740932/image00855.gif)
图 1.2.3　触发实例方法的各种方式
正如这些例子所示，在用例中实例方法和静态方法的调用方式完全相同——可以通过语句（ void 方法）也可以通过表达式（有返回值的方法）。静态方法的主要作用是实现函数；非静态（实例）方法的主要作用是实现数据类型的操作。两者都可能出现在用例代码中，但很容易就可以区分它们，因为静态方法调用的开头是类名（按习惯为大写），而非静态方法调用的开头总是 对象 名（按习惯为小写）。表 1.2.2 总结了这些不同之处。
表 1.2.2　实例方法与静态方法
实例方法
静态方法
举例
heads.increment()
Math.sqrt(2.0)
调用方式
对象名
类名
参量
对象的引用和方法的参数
方法的参数
主要作用
访问或改变对象的值
计算返回值
1.2.1.7　使用对象

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

• 声明该类型的变量，以用来引用对象；
  
• 使用关键字 new 触发能够创建该类型的对象的一个构造函数；
  
• 使用变量名在语句或表达式中调用实例方法。
  

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

• 赋值语句；
  
• 向方法传递对象或是从方法中返回对象；
  
• 创建并使用对象的数组。
  

1. public class Flips
2. {
3.    public static void main(String[] args)
4.    {
5.       int T = Integer.parseInt(args[0]);
6.       Counter heads = new Counter("heads");
7.       Counter tails = new Counter("tails");
8.       for (int t = 0; t < T; t++)
9.          if (StdRandom.bernoulli(0.5))
10.               heads.increment();
11.          else tails.increment();
12.       StdOut.println(heads);
13.       StdOut.println(tails);
14.       int d = heads.tally() - tails.tally();
15.       StdOut.println("delta: " + Math.abs(d));
16.    }
17. }

复制代码

Counter 类的用例，模拟 T 次掷硬币

1. % java Flips 10
2. 5 heads
3. 5 tails
4. delta: 0
6. % java Flips 10
7. 8 heads
8. 2 tails
9. delta: 6
11. % java Flips 1000000
12. 499710 heads
13. 500290 tails
14. delta: 580

复制代码

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

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

1. Counter c1 = new Counter("ones");
2. c1.increment();
3. Counter c2 = c1;
4. c2.increment();
5. StdOut.println(c1);

复制代码

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

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

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

1. % java FlipsMax 1000000
2. 500281 tails wins

复制代码

1. public class FlipsMax
2. {
3.    public static Counter max(Counter x, Counter y)
4.    {
5.       if (x.tally() > y.tally()) return x;
6.       else return y;
7.    }
9.    public static void main(String[] args)
10.    {
11.       int T = Integer.parseInt(args[0]);
12.       Counter heads = new Counter("heads");
13.       Counter tails = new Counter("tails");
14.       for (int t = 0; t < T; t++)
15.       　　if (StdRandom.bernoulli(0.5))
16.         　　　　heads.increment();
17.         　else tails.increment();
19.     　if (heads.tally() == tails.tally())
20. 　　　　　　StdOut.println("Tie");
21.     　else StdOut.println(max(heads, tails) + " wins");
22. 　　}
23. }

复制代码

一个接受对象作为参数并将对象作为返回值的静态方法的例子
1.2.1.11　数组也是对象

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

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

• 使用方括号语法调用数组的构造函数创建数组；
  
• 对于每个数组元素调用它的构造函数创建相应的对象。
  

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

1. public class Rolls
2. {
3.    public static void main(String[] args)
4.    {
5.       int T = Integer.parseInt(args[0]);
6.       int SIDES = 6;
7.       Counter[] rolls = new Counter[SIDES+1];
8.       for (int i = 1; i <= SIDES; i++)
9.          rolls[i] = new Counter(i + "'s");
11.       for (int t = 0; t < T; t++)
12.       {
13.          int result = StdRandom.uniform(1, SIDES+1);
14.          rolls[result].increment();
15.       }
16.       for (int i = 1; i <= SIDES; i++)
17.          StdOut.println(rolls[i]);
18.    }
19. }

复制代码

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

本文由博客一文多发平台 OpenWrite 发布！

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！