算法(4th ed)(90):基础——数据抽象 4.3.5

阅读数:13 2019 年 11 月 2 日 12:14

算法(4th ed)(90):基础——数据抽象 4.3.5

(抽象数据类型的实现:API、用例与实现)

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

  • 定义一份 API:API 的作用是将使用和实现分离,以实现模块化编程。我们制定一份 API 的目标有二:第一,我们希望用例的代码清晰而正确,事实上,在最终确定 API 之前就编写一些用例代码来确保所设计的数据类型操作正是用例所需要的是很好的主意;第二,我们希望能够实现这些操作,定义一些无法实现的操作是没有意义的。
  • 用一个 Java 类实现 API 的定义:首先我们选择适当的实例变量,然后再编写构造函数和实例方法。
  • 实现多个测试用例来验证前两步做出的设计决定。

表 1.2.11 一个简单计数器的抽象数据类型

APIpublic class Counter
             Counter(String id)创建一个名为 id 的计数器
       void  increment()将计数器的值加 1
        int  tally()计数器的值
     String  toString()对象的字符串表示
典型的用例
public class Flips
{
public static void main(String[] args)
{
int T = Integer.parseInt(args[0]);
Counter heads = new Counter("heads");
Counter tails = new Counter("tails");
for (int t = 0; t < T; t++)
if (StdRandom.bernoulli(0.5))
heads.increment();
else tails.increment();
StdOut.println(heads);
StdOut.println(tails);
int d = heads.tally() - tails.tally();
StdOut.println("delta: " + Math.abs(d));
}
}

数据类型的实现
public class Counter
{
private final String name;
private int count;
public Counter(String id)
{ name = id; }
public void increment()
{ count++; }
public int tally()
{ return count; }
public String toString()
{ return count + " " + name; }
}

使用方法
% java Flips 1000000
500172 heads
499828 tails
delta: 344

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

评论

发布