软件构造复习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

设计ADT

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