您的位置: 首页  >  文章  >  #软件构造 ADT与OOP的总结 （3） 抽象数据类型 (ADT)

#软件构造 ADT与OOP的总结 （3） 抽象数据类型 (ADT)

分类: 文章 • 2022-11-15 00:06:26

在软件构造课程的第三章
Abstract Data Type (ADT) and Object Oriented Programming (OOP）
中主要分为五个子章节

  1. 3-1 Data Type and Type Checking 数据类型与类型检验
  2. 3-2 DesigningSpecification 设计规约
  3. 3-3 Abstract Data Type (ADT) 抽象数据类型
  4. 3-4 Object-Oriented Programming (OOP)面向对象的编程
  5. 3-5 Equality in ADT and OOP ADT和OOP中的“等价性”

下面我们边分别对这五个子章节进行总结

3.3Abstract Data Type 抽象数据类型 (ADT)

3.3.1 为什么需要ADT？

通过抽象数据类型设计良好的抽象数据结构，通过封装来避免客户端获取数据的内部表示（即“表示泄露”），避免潜在 的bug——在client和implementer之间建立“防火墙”

3.3.2 ADT为什么叫ADT？

抽象数据类型 (ADT)全称Abstract Data Type，是软件工程中的一些普适原理原理的一个实例，它有很多含义：

  • 抽象：为高级的设计思想隐藏的底层的技术细节。
  • 模块化：将系统划分为组件或模块，每个组件或模块都可以与系统其余部分分开设计，实现，测试，推理和复用。
  • 封装：对模块进行封装，以使每个模块负责其自身的内部行为，并且使得系统其他模块中的错误不会破坏其本模块的完整性。
  • 信息隐藏： 隐藏系统其余部分的模块底层的技术实现细节，以便以后可以修改这些代码而无需更改系统其余部分。
  • 功能分离： 使功能成为单个模块的责任，而不是将其分散到多个模块中。

3.3.3 抽象数据类型 和 传统数据类型

首先知道什么是数据抽象：由一组操作所刻画的数据类型

  • 传统的类型定义：关注数据 的具体表示
  • 抽象类型：强调“作用于数据上的操作”，程序员和 client无需关心数据如何具体存储的，只需设计/使用操作即可
    ADT是由操作定义的，与其内部 如何实现无关！

3.3.4 ADT中的类型和运算

ADT的类型可以分为可变类型和不可变数据类型 ，可以用以下的准则进行区分

  • 可变类型的对象：提供了可改变其 内部数据的值的操作

  • 不变数据类型： 其操作不改变 内部值，而是构造新的对象

而ADT的运算
ADT的运算，表现为各种类型的方法：

3.3.4.1 构造器 creator

创建该类型的新对象

其可能实现为构造函数或静态函数，
构造器可以实现为构造方法，如new ArrayList（），也可以实现为静态方法，例如Arrays.asList()，List.of()

而构造器实现为静态方法的创建者通常称为工厂方法(factory method )

Java中各种**String.valueOf（Object Obj）**方法是实现为工厂方法的创建者的其他示例。 与 Object.toString（） 正好是相对的

3.3.4.2 生产器 Producers

生产者从该类型的旧对象创建新对象。
例如，String的 concat() 方法是一个生产器：它接受两个字符串，并产生一个表示它们的串联的新字符串。

3.3.4.3 观察器 Observers

观察者获取抽象类型的对象并返回不同类型的对象
例如，List的 size() 方法返回一个int

3.3.4.4 变值器 Mutators

仅有可变类型的对象拥有！
改变对象属性的方法
例如，List的 add（） 方法通过将元素添加到末尾来对列表进行修改

变值器通常返回 void
但是有时候变值器也可能返回非空类型
例如，Set.add（） 返回一个bool类型的数值，该布尔值指示是否实际更改了设置。
在Java的图形用户界面(GUI)工具包中， Component.add（） 返回对象本身，以便可以将多个add（）调用链接在一起。

3.3.4.5 一些方法的类型的例子

#软件构造 ADT与OOP的总结 （3） 抽象数据类型 (ADT)

3.3.4 一些ADT的例子

  • int是不可变类型，因此它没有任何 Mutator
  • 构造器：形如0，1，2，…的数字
  • 生产器：算术运算符+，-，*，/
  • 观察器：比较运算符==，！=，<，>
  • 变值器：无
  • String是Java的字符串类型,是不可变类型
  • 构造器：字符串构造器 String()
  • 生产器：concat , substring , toUpperCase
  • 观察器： length , charAt
  • 变值器：无
  • List是Java的列表类型，并且是可变的；同时List也是一个接口，这意味着其他类可以提供数据类型的实际实现，例如ArrayList和LinkedList。
  • 构造器： ArrayList and LinkedList 构造方法, Collections.singletonList
  • 生产器：Collections.unmodifiableList
  • 观察器：size , get
  • 变值器：add , remove , addAll , Collections.sort
3.3.5 保持不变性和避免表示泄漏

什么是表示独立性（RI）？
表示独立性是指client使用ADT时无需考虑其内部如何实 现，ADT内部表示的变化不应影响外部spec和客户端。
ADT的使用与其表示形式（用于实现它的实际数据结构或变量）无关，因此，表示形式的更改对抽象类型本身之外的代码没有影响。
例如，List提供的操作与列表是否表示为链接列表还是数组无关。

除非ADT的操作指明了具体的pre和post-condition，否则不能改变ADT的内部表示——spec规定了 client和implementer之间的契约。

  • 表示不变性RI：某个具体的“表示”是否是“合法的”
  • 也可将RI看作：所有表示值的一个子集，包含了所有合法的表示值
  • 也可将RI看作：一个条件，描述了什么是“合法”的表示值
    什么是保持不变性？
    好的ADT最重要的属性是它保持自己的不变量 ，由ADT 自身来负责其不变量，与client端的任何行为无关

为什么需要不变量？
保持程序的“正确性”，容易发现错误
不然可能会出现 表示泄露（representation exposure ）
不仅影响不变性，也影响了表示独立性：无法在不影响客户 端的情况下改变其内部表示 ，这样的表示泄露不仅威胁不变性，而且也威胁着表示独立性（RI），因此ADT有责任保证自己的invariants，并避免“表示泄露”，

最好的办法就是使 用immutable的类型，彻底避免表示泄露。

3.3.6 ADT的 Abstraction Function抽象函数

#软件构造 ADT与OOP的总结 （3） 抽象数据类型 (ADT)
R：ADT中底层实现构建的空间
A：抽象值构成的空间：client看到和使用的值
ADT开 发者关注表示空间R，client关注抽象空间A
因此
抽象函数便是R和A之间映射关系的函数，即如何去解 释R中的每一个值为A中的每一个值。
#软件构造 ADT与OOP的总结 （3） 抽象数据类型 (ADT)
AF与RI的关系：
选择某种特定的表示方式R，进而指定某个子集是“合 法”的(RI)，并为该子集中的每个值做出“解释”(AF)——即如何映射 到抽象空间中的值。
即使是同样的R、同样的RI，也 可能有不同的AF，即“解释不同”。

3.3.7 如何设计ADT和对于ADT的测试

设计ADT：

  1. 选择R和A；
  2. RI — 合法的表示值；
  3. 如何解释合法的表示值 —映射AF 做出具体的解释：每个rep value如何映射到abstract value

而且要把这种选择和解释明确写到代码当中

测试ADT：

  • 测试creators, producers, and mutators：调用observers来观察这些 operations的结果是否满足spec；
  • 测试observers：调用creators, producers, and mutators等方法产生或 改变对象，来看结果是否正确。
  • 风险：如果被依赖的其他方法有错误，可能导致被测试方法的测试结 果失效。

相关推荐