软件构造第三章 第三节 抽象数据型

一、ADT及其四种类型

1.1 ADT的基本概念

1. 抽象数据类型（Abstract Data Type，ADT）是是指一个数学模型以及定义在该模型上的一组操作；即包括数据数据元素，数据关系以及相关的操作。
2. ADT具有以下几个能表达抽象思想的词：
   • 抽象化：用更简单、更高级的思想省略或隐藏低级细节。
   • 模块化： 将系统划分为组件或模块，每个组件可以设计，实施，测试，推理和重用，与系统其余部分分开使用。
   • 封装：围绕模块构建墙，以便模块负责自身的内部行为，并且系统其他部分的错误不会损坏其完整性。
   • 信息隐藏： 从系统其余部分隐藏模块实现的细节，以便稍后可以更改这些细节，而无需更改系统的其他部分。
   • 关注点分离： 一个功能只是单个模块的责任，而不跨越多个模块。

1.2 ADT的四种类型

• 前置定义：mutable and immutable types
  • 可变类型的对象：提供了可改变其内部数据的值的操作。Date
  • 不变数据类型： 其操作不改变内部值，而是构造新的对象。String

1. Creators（构造器）：
   • 创建某个类型的新对象，⼀个创建者可能会接受⼀个对象作为参数，但是这个对象的类型不能是它创建对象对应的类型。可能实现为构造函数或静态函数。（通常称为工厂方法）
   • t* -> T
   • 例：Integer.valueOf( )
2. Producers（生产器）：
   • 通过接受同类型的对象创建新的对象。
   • T+ , t* -> T
   • 例：String.concat( )
3. Observers（观察器）：
   • 获取抽象类型的对象然后返回一个不同类型的对象/值。
   • T+ , t* -> t
   • 例：List.size( ) ；
4. Mutators（变值器）：
   • 改变对象属性的方法 ，
   • 变值器通常返回void，若为void，则必然意味着它改变了对象的某些内部状态；当然，也可能返回非空类型
   • T+ , t* -> t || T || void
   • 例：List.add( )
     • 解释：T是ADT本身；t是其他类型；+ 表示这个类型可能出现一次或多次；* 表示可能出现0次或多次。

1.3 示例：

图1-1 immutable类型示例
图1-2 mutable类型示例
图1-3 方法类型

二、设计与测试ADT

2.1 设计ADT

  设计好的ADT，靠“经验法则”，提供一组操作，设计其行为规约 spec

• 原则 1：设计简洁、一致的操作。
  • 最好有一些简单的操作，它们可以以强大的方式组合，而不是很多复杂的操作。
  • 每个操作应该有明确的目的，并且应该有一致的行为而不是一连串的特殊情况。
• 原则 2：要足以支持用户对数据所做的所有操作需要，且用操作满足用户需要的难度要低。
  • 提供get()操作以获得list内部数据
  • 提供size()操作获取list的长度
• 原则 3：要么抽象、要么具体，不要混合 —— 要么针对抽象设计，要么针对具体应用的设计。

2.2 测试ADT

1. 测试creators, producers, and mutators：调用observers来观察这些 operations 的结果是否满足spec；
2. 测试observers： 调用creators, producers, and mutators等方法产生或改变对象，来看结果是否正确。

三、表示独立性

  表示独立性：client使用ADT时无需考虑其内部如何实现，ADT内部表示的变化不应影响外部spec和客户端。
  除非ADT的操作指明了具体的前置条件/后置条件，否则不能改变ADT的内部表示——spec规定了 client和implementer之间的契约。

四、不变量（Invariants）与表示泄露

  一个好的抽象数据类型的最重要的属性是它保持不变量。一旦一个不变类型的对象被创建，它总是代表一个不变的值。当一个ADT能够确保它内部的不变量恒定不变（不受使用者/外部影响），我们就说这个ADT保护/保留自己的不变量。
  在private和public关键字表明哪些字段和方法可访问时，只在类内部还是可以从类外部访问。所述final关键字还保证该变量的索引不会被更改，对于不可变的类型来说，就是确保了变量的值不可变。
  可以通过使用防御性拷贝来修补这种风险：制作可变对象的副本以避免泄漏对代表的引用。
  可变类型通常具有一个专门用来复制的构造函数，它允许创建一个复制现有实例值的新实例。在这种情况下，Date的复制构造函数就接受了一个timestamp值，然后产生一个新的对象。
  复制可变对象的另一种方法是clone()，某些类型但不是全部类型支持该方法。然而clone()在Java中的工作方式存在问题，具体在以后分析。
  通常来说，要特别注意ADT操作中的参数和返回值。如果它们之中有可变类型的对象，确保你的代码没有直接使⽤索引或者直接返回索引。

五、抽象函数AF与表示不变量RI

5.1 AF与RI

图5-1 表示域与抽象域

1. 在研究抽象类型的时候，先思考一下两个值域之间的关系：
   • 表示域（rep values）里面包含的是值具体的实现实体。一般情况下ADT的表示比较简单，有些时候需要复杂表示。
   • 抽象域（A）里面包含的则是类型设计时支持使用的值。这些值是由表示域“抽象/想象”出来的，也是使用者关注的。
2. ADT实现者关注表示空间R，用户关注抽象空间A 。
3. R->A的映射特点：
   • 每一个抽象值都是由表示值映射而来 ，即满射：每个抽象值被映射到一些rep值
   • 一些抽象值是被多个表示值映射而来的，即未必单射：一些抽象值被映射到多个rep值
   • 不是所有的表示值都能映射到抽象域中，即未必双射：并非所有的rep值都被映射。

4. 抽象函数（AF）：R和A之间映射关系的函数
     AF : R → A
5. 表示不变量（RI）：将rep值映射到布尔值
     RI : R → boolean　　
   • 对于表示值r，当且仅当r被AF映射到了A，RI(r)为真。
   • 表示不变性RI：某个具体的“表示”是否是“合法的”
   • 也可将RI看作：所有表示值的一个子集，包含了所有合法的表示值
   • 也可将RI看作：一个条件，描述了什么是“合法”的表示值
   • 在下图中，绿色表示的就是RI(r)为真的部分，AF只在这个子集上有定义。
   • AF与RI都不会展示给用户。 图5-2 AF与RI
     

5.2 用注释写AF和RI

1. 在抽象类型（私有的）表示声明后写上对于抽象函数和表示不变量的注解，这是一个好的实践要求。我们在上面的例子中也是这么做的。
2. 在描述抽象函数和表示不变量的时候，注意要清晰明确：
   • 对于RI（表示不变量），仅仅宽泛的说什么区域是合法的并不够，你还应该说明是什么使得它合法/不合法。
   • 对于AF（抽象函数）来说，仅仅宽泛的说抽象域表示了什么并不够。抽象函数的作用是规定合法的表示值会如何被解释到抽象域。作为一个函数，我们应该清晰的知道从一个输入到一个输入是怎么对应的。
3. 本门课程还要求你将表示暴露的安全性注释出来。这种注释应该说明表示的每一部分，它们为什么不会发生表示暴露，特别是处理的表示的参数输入和返回部分（这也是表示暴露发生的位置）。
4. 下面是一个Tweet类的例子，它将表示不变量和抽象函数以及表示暴露的安全性注释了出来：

图5-3 Tweet示例
  注意到我们并没有对 timestamp 的表示不变量进行要求（除了之前说过的默认 timestamp!=null）。但是我们依然需要对timestamp 的表示暴露的安全性进行说明，因为整个类型的不变性依赖于所有的成员变量的不变性。