软件构造复习6--ADT抽象数据类型3.3

基本概念

抽象类型：强调“作用于数据上的操作”，无需关心数据具体如何存储，只需设计操作即可

分类

数据类型分类

1.可变的

提供可改变内部数据值的方法

2.不可变

操作不可改变内部值，而是构造新的对象 因此一些类型会提供两种形式

方法分类

1.构造器 creator

从无到有 t*->T 可实现为构造函数或静态函数

2.生产器 Producers

T+,t* ->T 从有到新 比如字符串拼接方法

3.观察器 Observer

T+,t*->void | t |T

4.变值器 Mutators

改变对象属性 add方法 不可变类型没有变值器，所有基本类型都是不可变类型

ADT实例

List

设计ADT

简洁一致的操作

同过简单操作的组合实现复杂操作

满足客户需求

能支持客户对数据的所有操作，且对client需要的难度低 judge: 每个属性是否都能被访问？

要么抽象，要么具体，不要混合

表示独立性

客户使用ADT时，无需考虑其内部如何实现，ADT内部的变化不应该影响外部spec和客户端

ADT的不变量

程序在任何时候总是true的性质 由ADT来负责，与客户端的行为无关 利用private final 关键字实现不变量 使用不可变类型保证ADT的不变性

防御式拷贝

在返回时，不返回对象，而是返回对象的拷贝

Rep

表示空间 R

表示值构成的空间 实现者看到和使用的值

抽象空间 A

client看到和使用的值

AF：R→A

R和A之间映射关系的函数，即如何将R的每个值解释为A中的每一个值 一定是满射 不一定是单射

RI：R→boolean Rep invariant

R中的值通过AF的映射能映射到A中则属于RI，否则不属于RI

Invariants of ADT

不变量，在任何时候都是true 不可变类型就是一个典型的不变量 由ADT负责，与client无关

为什么需要不变量

保持程序的正确性，容易发现错误

设计ADT

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

Benefit mutation

why need?

checkRep()

在所有可能改变rep的方法内都要检查

AF RI文档化

代码中用注释记录AF RI 精确记录RI：rep中的所有field何时有效 精确记录AF：如何解释每个R值

RI:针对Rep的每一个field以及多个fields之间的关系，进行条件限定，要精确 AF：给客户看到，是对每个rep值进行“数学运算”

如果spec中需要值，只能用A空间的值