文章目录

• 1.抽象和定义类型
• 2.对操作和类型的分类
• 3.抽象数据类型的案列
• 4.设计一个抽象类
• 5.表示独立性
• 6.测试抽象数据类型
• 7.不变量
• 8.表示不变性和抽象函数
• 9.有益的突变
• 10.记录AF、RI和 代表暴露的安全性

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

ADT的特性：表示泄漏、抽象函数AF、表示不变量RI
基于数学的形式对ADT的这些核心特征进行描述并应用于设计中。

1.抽象和定义类型

编程语言本身带有一些数据类型，如：integers, booleans, strings, 等。用户可以使用他们作为输入和输出

用户也可以定义自己需要的数据类型并且使用他们。

传统的类型定义：关注数据的具体表示，例如：：创建一个整形字段来记录年月日

抽象类型： 抽象类型：强调“作用于数据上的操作”，程序员和
client无需关心数据如何具体存储的，只需设计/使用操作即可。例如：一个布尔值的操作有：与或非；我们不关心用什么值表示真假，只关心定义在类型上的操作。
例如：但我们谈论List类型时，我们不关心它是一个链表还是数组又或者是其它的表示list的特殊数据结构，我们关心的是定义在List上的一系列操作，如get（），size（）等

2.对操作和类型的分类

**可变数据类型：**提供了可改变其内部数据的值得操作
不可变数据类型：其操作不改变内部值，而是构造新的对象

对数据的操作有四类：
Creators：构造器，从无到有创建一个新的对象
Producers：生产器，从一个之前的对象生产一个新的对象
Observers：观察器，获取对象的属性
Mutators：变值器，改变对象属性

例子：

变值器常常没有返回，如果返回值为void，则必然意味着它改变了对象的某些内部状态，变值器也可能返回非空类型。

不可变的抽象数据类型没有变值器

3.抽象数据类型的案列

int 和 String

因为这个数据类型是不可变的，所以子字符串操作 不需要将字符复制到一个新的数组中。 它可以指向原始的MyString对象的字符数组 并记录新子字符串对象的开始和结束 代表。 为了实现这个优化，我们可以改变内部 这个类的表示为:

7.不变量

好的抽象数据类型最重要的属性是它保留了自己的不变量。

不变量是程序的一种属性，在程序运行时的每一个这阶段都保持为真

不可变性是一个关键的不变量:一旦创建，就是一个不可变对象
应该在整个生命周期中始终表示相同的值。 例如： 不变性

由ADT来负责其不变量，与client端的任何行为无关

为什么需要不变量：保持程序的“正确性”，容易发现错误

在具有不变性的地方，一旦某个方法所使用的，就要在使用后检查是否改变，总是要假设client有“恶意”破坏ADT的不变量-

public：class的外部也可以访问
private：只有类的内部可以访问

final：不可变的数据类型在创建后不会被冲洗赋值构造

除非迫不得已，否则不要把希望寄托于客户端上，ADT有责任保证自己的invariants，并避免“表示泄露”。

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

8.表示不变性和抽象函数

一般情况下ADT的表示比较简单，有些时候需要复杂表示
R:表示值的空间 (rep值)由实际实现的实体构成。
A抽象值构成的空间：client看到和使用的值

映射规则：
满射：每个抽象值都要代表值映射到他
未必单射：每个抽象值可以有多个代表制映射到他
未必双射：存在代表值没有映射，没有映射代表表示值不合法

抽象函数：R和A之间映射关系的函数，即如何去解释R中的每一个值为A中的每一个值。

选择某种特定的表示方式R，进而指定某个子集是“合法”的(RI)，并为该子集中的每个值做出“解释”(AF)——即如何映射到抽象空间中的值。

设计ADT：
(1) 选择R和A；
(2) RI — 合法的表示值；
(3) 如何解释合法的表示值 —映射AF

做出具体的解释：每个rep value如何映射到abstract value，而且要把这种选择和解释明确写到代码当中

表示不变量仅仅是一个数学概念，在每次操作之后检查表示不变量可以快速发现bug

在所有可能改变rep的方法内都要检查
Observer方法可以不用，但
建议也要检查，以防止你的“万一”

10.记录AF、RI和 代表暴露的安全性

要精确的记录RI：rep中的所有fields何为有效
要精确记录AF：如何解释每一个R值
要精确记录AF：如何解释每一个R值
给出理由，证明代码并未对外泄露其内部表示——自证清白

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览34598 人正在系统学习中