3.3抽象数据类型
课程目标
抽象数据类型与表示独立性： 如何设计良好的抽象数据结构，通过封装来避免客户端获取数据的内部表示（即“表示泄露”），避免潜在的bug—— 在client 和implementer之间建立“防火墙”。
ADT 的特性：不变量、表示泄漏、抽象函数AF 、表示不变量RI
基于数学的形式对ADT 的这些核心特征进行描述并应用于设计中。
大纲
1.抽象和用户定义的数据类型
2. ADT中的操作类
3.抽象数据类型的例子
4. ADT的设计原则
5.代表独立性（RI）
6.在Java中实现ADT概念
7.测试ADT
8.不变式
9.代表不变量和抽象函数
10.有利突变
11.记录重复暴露的AF，RI和安全性
12. ADT不变量取代先决条件
3.3.1.抽象和用户定义的数据类型
抽象数据类型：
-抽象化
-模块化
-封装
-信息隐藏
-关注点分离
用户定义数据类型
除了编程语言所提供的基本数据类型和对象数据类型，程序员可定义自己的数据类型
数据抽象
是由一组操作所刻画的数据类型
#传统的类型定义：关注数据的具体表示
抽象类型：强调“作用于数据上的操作”，程序员和client无需关心数据如何具体存储的，只需设计/使用操作即可。
抽象数据类型是由操作定义的，与其内部如何实现无关！
3.3.2分类类型和操作
可变和不可变数据类型
可变类型的对象：提供了可改变其内部数据的值的操作
不变数据类型： 其操作不改变内部值，而是构造新的对象
对抽象类型的操作进行分类
Creators--构造器：可能用构造函数或者静态函数实现
Producers--生产器
Observers--观察器
Mutators--变值器，改变对象属性的方法：经常返回void（如果返回值为void，则必然意味着它改变了对象的某些 内部状态）ps：变值器也可能返回非空类型
3.3.3抽象数据类型的例子
int型和字符串
int型是不可变的，所以它没有mutators（变值器）
string型是不可变的
3.3.4设计一个抽象数据类型
设计好的ADT ，靠“经验法则”，提供一组操作，设计其行为规约 spec
①设计简洁、一致的操作
②要足以支持客户端对数据所做的所有操作需要，且用操作满足客户端需要的难度要低
③要么抽象、要么具体，不要混合 --- 要么针对抽象设计，要么针对具体应用的设计
3.3.5表示独立性
表示独立性：客户端使用ADT 时无需考虑其内部如何实现，ADT 内部表示的变化不应影响外部spec 和客户端。
除非ADT 的操作指明了具体的pre-和post-condition（前置和后置条件） ，否则不能改变ADT 的内部表示——spec 规定了client 和implementer 之间 的契约。
3.3.6测试抽象数据类型
如何测试抽象数据类型
测试creators, producers, and mutators：调用observers来观察这些operations的结果是否满足spec；
测试observers：调用creators, producers, and mutators等方法产生或改变对象，来看结果是否正确。
3.3.7不变量
ADT中的不变量
保持自己的不变量
不变量任何时候总是true
由ADT来负责其不变量，与客户端的任何行为无关
为什么需要不变量：保持程序的“正确性”，容易发现错误
表示泄露, 不仅影响不变性，也影响了表示独立性：无法在不影响客户 端的情况下改变其内部表示
使它不可变可以使用private 和 final来修饰
当然不是全部的final都可以控制变量的不变，还要注意可变变量对不变性修饰的依赖（不可变变量的final
修 饰就只是不能改变其指向而已，但是还是可以改变内部的值，就像List）
一般来说，您应仔细检查所有ADT操作的参数类型和返回类型
当然也可以在规约spec里面写到不能对该返回值进行变值操作（当复制代价很高的时候就不得不那么做但是由此引发的潜在bug也将很多）
除非迫不得已，否则不要把希望寄托于客户端上，ADT有责任保证自 己的invariants，并避免表示泄露。
最好的办法就是使 用immutable的类型，彻底避免表示泄露
3.3.8.代表不变量和抽象函数
一般情况下ADT的表示比较简单，有些时候需要复杂表示
抽象值构成的空间：client看到和使用的值
ADT实 现者关注表示空间R，用户关注抽象空间A
R空间与A空间之前的关系有：
(surjective, 满射)
(not injective, 未必单射)
(not bijective, 未必双射)
抽象函数（Abstraction Function）：R和A之间映射关系的函数
Rep Invariant
表示不变性RI：某个具体的“表示”是否是“合法的”
也可将RI看作：所有表示值的一个子集，包含了所有合法的表示值
也可将RI看作：一个条件，描述了什么是“合法”的表示值
Documenting RI and AF（记录RI和AF）：
– 不同的内部表示，需要设计不同的AF和RI
选择某种特定的表示方式R，进而指定某个子集是“合 法”的(RI)，并为该子集中的每个值做出“解释”(AF)——即如何映射 到抽象空间中的值
即使是同样的R、同样的RI，也 可能有不同的AF，即“解释不同”。
设计ADT：(1) 选择R和A；
(2) RI --- 合法的表示值；
(3) 如何解释合法的表示值 ---映射AF 做出具体的解释：每个rep value如何映射到abstract
value
而且要把这种选择和解释明确写到代码当中
3.3.9.有利突变
对immutable的ADT来说，它在A空间的abstract value应是不变的。
但其内部表示的R空间中的取值则可以是变化的。
3.3.10.记录重复暴露的AF，RI和安全性
在代码中用注释形式记录AF和RI
表示泄漏的安全声明
给出理由，证明代码并未对外泄露其内部表示——自证清白
ADT的规约里只能使用client可见的内容来撰写，包括参数、返 回值、异常等。
如果规约里 需要提及“值”，只能使用A空间 中的“值”。
ADT的规约里也不应谈及任何内部表示 的细节，以及R空间中的任何值
ADT的内部表示(私有属性)对外部都应严格不可见
故在代码中以注释的形式写出AF和RI而不 能在Javadoc文档中，防止被外部看到而破坏表示独立性/信息隐藏
在对象的初始状态不变量为true，在对象发生变化时，不变量也要为true
构造器和生产器在创建对象时要确保不变量为true
变值器和观察器在执 行时必须保持不变性。
表示泄漏的风险：一旦泄露，ADT内部表示可能会在程序的任何位置 发生改变（而不是限制在ADT内部），从而无法确保ADT的不变量是 否能够始终保持为true。
3.3.11. ADT不变量取代先决条件
用不变量取代方法的Precondition