本次课程的目的
▪ 抽象数据类型和表示独立性：使我们能够将如何在程序中使用数据结构与数据结构本身的特定形式区分开来。
抽象数据类型解决了一个特别危险的问题：客户对类型的内部表示进行假设。
–我们将了解为什么这是危险的，以及如何避免。
–我们还将讨论操作的分类，以及抽象数据类型的一些良好设计原则。

▪ 不变量、rep暴露、抽象函数（AF）和表示不变量（RI）
–通过抽象函数和表示不变量的概念，对类实现ADT意味着什么的更形式化的数学概念。
–这些数学概念在软件设计中非常实用。
–抽象函数将为我们提供一种在抽象数据类型上清晰定义相等操作的方法。
–rep不变量将使捕获由损坏的数据结构引起的错误变得更容易。

1抽象和用户定义类型
用户定义的类型
▪ 一种编程语言带有内置类型（如整数、布尔值、字符串等）和内置过程（如输入和输出）。
▪ 用户可以定义自己的数据类型和过程-用户定义的类型。

数据抽象
▪ 数据抽象：类型的特征是可以对其执行的操作。
–一个数字是可以加和乘的；
–一个字符串是可以连接并取的子字符串；
▪ 传统上，程序员用早期的编程语言定义自己的类型，例如：创建记录类型date，其中包含日期、月份和年份的整数字段。
▪ 抽象类型专注于操作——该类型的用户不必担心它的值实际上是如何存储的，程序员可以忽略编译器实际上是如何存储整数的。重要的是操作。

抽象数据类型Bool有以下操作：
–true:Bool
–false:Bool
–and:Bool×Bool→Bool
–or:Bool×Bool→Bool
–not:Bool→Bool
▪ Bool有很多可能的实现方式，并且仍然能够满足操作规范，例如：–作为一个位，1表示true，0表示false。–作为int值，其中5表示真，8表示假。
–作为对字符串对象的引用，其中“false”表示true，“true”表示false。
–当int值大于1时，质数表示真，复合数表示假。

操作本身（及其规范）完全定义了数据类型，从数据结构、内存存储或实现的细节中抽象出来。

抽象类型由其操作定义
▪ 记住——抽象数据类型是由其操作定义的。
–T类型的操作集及其规范完全描述了T的含义。
▪ 当我们讨论列表类型时，我们指的不是链表、数组或任何其他用于表示列表的特定数据结构。
▪ 相反，我们指的是一组不透明的对象（可能是具有列表类型的对象），它们满足List:get（）、size（）等所有操作的规范。

2分类类型和操作

可变和不可变类型
▪ 无论是内置的还是用户定义的Type，都可以分为可变的或不可变的。
–可变类型的对象可以更改：也就是说，它们提供的操作在执行时会导致同一对象上其他操作的结果产生不同的结果。
–日期是可变的，因为可以调用setMonth（）并使用getMonth（）操作观察更改。
–但是字符串是不可变的，因为它的操作创建了新的字符串对象，而不是更改现有的对象。
–有时类型将以两种形式提供，一种是可变的，另一种是不可变的。例如，StringBuilder是String的可变版本.

对抽象类型的操作进行分类
▪ 创建者创建该类型的新对象。
–创建者可以将对象作为参数，但不能将其作为正在构造的类型的对象。
▪ 生产者从该类型的旧对象创建新对象。
–例如，String的concat（）方法是一个生产者：它接受两个字符串并生成一个表示它们的连接的新字符串。
▪ Observerstake抽象类型的对象并返回不同类型的对象。
–例如，List的size（）方法返回一个int。
▪ 变换器更改对象。
–例如，List的add（）方法通过在末尾添加元素来改变列表。

▪ 创建者：t→t
▪ 生产者：T+，T→T
▪ 观察者：T+，T→T
▪ 改变者：T+，T→void| T | T
▪ 每个T都是抽象类型本身；
▪ 每个t都是另一种类型。
▪ +标记表示该类型可能在签名的该部分出现一次或多次。
▪ *标记表示它出现零次或多次。
▪ |表示或。

创造者
▪ creator要么像new ArrayList（）一样实现为构造函数，要么只是一个静态方法，像Arrays.as List（），List.of（）。
构造器：可能实现为构造函数或静态 函数
▪ 作为静态方法实现的创建者通常称为工厂方法
▪ Java中的各种String.valueOf（Object Obj）方法是作为工厂方法实现的创建者的其他示例。

▪ mutator通常由void返回类型发出信号。
–如果返回值为void，则必然意 味着它改变了对象的某些内部状态
▪ 但并不是所有的变异都返回无效。
–例如，Set.add（）返回一个布尔值，该布尔值指示集是否已实际更改。
–在Java的图形用户界面工具包中，Component.add（）返回对象本身，以便可以将多个add（）调用链接在一起。

3抽象数据类型示例
int和String
▪ int是不可变的，所以它没有mutator
–创建者：数字文本0，1，2，…
–生产者：算术运算符+，-，*，/
–观察者：比较运算符=！=，<，>
-mutator：无（不可变）
▪ String是Java的字符串类型。字符串是不可变的。
–创建者：字符串构造函数
–生产者：concat、substring、toUpperCase
–观察者：length、charAt
–mutators:none

列表
▪ List是Java的列表类型，并且是可变的。
▪ List也是一个接口，这意味着其他类提供数据类型的实际实现，例如ArrayList和LinkedList。
–创建者：ArrayList和LinkedList构造函数，Collections.singletonList
–生产者：Collections.unmodifiableList
–观察者：size，get
–mutators:add，remove，addAll，Collections.sort

4设计抽象类型
设计抽象类型
▪ 设计一个抽象类型需要选择好的操作并确定它们的行为方式。
▪ 经验法则1-最好有几个简单的操作，可以用强大的方式组合，而不是很多复杂的操作。
–每个操作都应该有一个明确的目的，并且应该有一个连贯的行为，而不是一大堆特殊情况。
–例如，我们可能不应该向List添加sum操作。它可以帮助处理整数列表的客户机，但是字符串列表呢？或者嵌套列表？所有这些特殊情况都会使sum成为一个难以理解和使用的操作

经验法则2▪ 操作集应该足够，因为必须有足够的操作来完成客户机可能要执行的计算类型。
–一个好的测试是检查是否可以提取该类型对象的每个属性。
–例如，如果没有get操作，我们将无法找出列表中的元素是什么。
——基本信息的获取不应过于困难。
–例如，对于List，大小方法并不是严格必要的，因为我们可以应用get on increasing index，直到出现故障，但这是低效和不方便的。

要么抽象、要么具体，不要混合 — 要么针对抽象设计，要么针对具体应用的设计
经验法则3
▪ 类型可以是泛型的：例如列表、集合或图形。
▪ 或者可能是特定领域的：街道图、员工数据库、电话簿等。 ▪ 但是它不应该混合通用和特定领域的特性。
–用于表示扑克牌序列的牌组类型不应具有接受任意对象（如整数或字符串）的泛型add方法。
–相反，将dealCards之类的特定于域的方法放入泛型类型列表是没有意义的。

5表示独立性
▪ 关键的一点，一个好的抽象数据类型应该是独立于表示的。
–抽象类型的使用独立于其表示（用于实现它的实际数据结构或数据字段），因此表示的更改对抽象类型本身之外的代码没有影响。
–例如，List提供的操作独立于List是表示为链表还是表示为数组。
▪ 除非ADT的操作完全由前置条件和后置条件指定，否则根本无法更改ADT的表示形式，这样客户就知道要依赖什么，并且知道可以安全地更改什么

MyString的一个简单表示
▪ 看看MyString的一个简单表示：只是一个字符数组，正好是字符串的长度，末尾没有多余的空间。
▪ 下面是如何将该内部表示声明为类中的实例变量： private String[]a；
▪ 有了这种表示方式的选择，这些操作将以一种简单的方式实现：

更好的performance
▪ 因为此数据类型是不可变的，所以子字符串操作实际上不必将字符复制到新数组中。
▪ 它可以只指向原始MyString对象的字符数组，并跟踪新子字符串对象表示的开始和结束。
▪ 要实现此优化，我们可以将此类的内部表示更改为：
private char[] a;
private int start;
private int end;

因为MyString的现有客户机只依赖于其公共方法的规范，而不依赖于其私有字段，所以我们可以在不检查和更改所有客户机代码的情况下进行此更改。

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

7不变量
ADT的不变量
▪ 一个好的抽象数据类型最重要的特性是它保留了自己的不变量。
▪ 不变量是程序的一个属性，对于程序的每一个可能的运行时状态，它始终为真。
–不变性是一个关键的不变量：一旦创建，一个不变性对象在其整个生命周期中都应该始终表示相同的值。
▪ 说ADT保留了它自己的不变量，ADT负责确保它自己的不变量保持不变。
–这并不依赖于客户的良好行为。
–正确性不依赖于其他模块。

为什么需要不变量？
▪ 当ADT保留自己的不变量时，对代码的推理就变得容易多了。
–如果您可以相信字符串永远不会改变，那么在调试使用字符串的代码时，或者在尝试为另一个使用字符串的ADT建立不变量时，可以排除这种可能性。
–与此相反，字符串类型保证只有当其客户机承诺不更改它时，它才是不可变的。然后，您必须检查代码中可能使用字符串的所有位置。
▪我们总数需要假设客户端将尝试销毁不变量

不变性作为一种不变量
▪ 我们如何保证这些Tweet对象是不可变的——
一旦创建了Tweet，它的作者、消息和日期就永远不会更改？

假设它是可变的…
▪ 对不变性的第一个威胁来自这样一个事实：客户机可以直接访问其字段。

▪ 以下Code的作用是什么？

▪ 这是表示公开的一个小例子，意味着类之外的代码可以直接修改表示。–这样的Rep曝光不仅威胁不变量，还威胁表示独立性。–我们不能在不影响所有直接访问这些字段的客户机的情况下更改Tweet的实现。

我们需要让他不可变
▪ private和public关键字指示哪些字段和方法只能在类内访问，哪些可以从类外访问。
▪ final关键字还有助于确保在构造对象之后不会重新分配此不可变类型的字段。

▪ 这段Code的作用是什么？

▪ retweetLater（）接收一条tweet，并应返回另一条带有相同消息（称为retweet）但在一小时后发送的tweet。▪ retweetLater（）方法可能是一个系统的一部分，该系统自动响应Twitter名人所说的有趣的事情。
▪ 这里有什么问题？
–getTimestamp调用返回对tweet t引用的同一日期对象的引用。t、 timestamp和d是同一可变对象的别名。–因此，当该日期对象被d.setHours（）变异时，这也会影响t中的日期，如快照图所示。

▪ Tweet的不变性不变量已经被破坏。
–问题是Tweet泄漏了对可变对象的引用，而可变对象的不变性依赖于该对象。
–我们公开了rep，这样Tweet就不能再保证它的对象是不变的。–完全合理的客户端代码创建了一个微妙的错误

怎么解决？—防御性拷贝
▪ 我们可以使用防御复制来修补这种rep暴露：复制可变对象以避免泄漏对rep的引用。
▪ 防御性复制是防御性编程的一种方法——假设客户机试图破坏不变量——实际上可能是真的（恶意黑客），但更可能是普通的错误——确保类不变量在任何输入下都能保持不变，以最小化易变性

复制和克隆（）
▪ 可变类型通常有一个复制构造函数，它允许您创建一个新实例来复制现有实例的值。
–在本例中，日期的复制构造函数使用时间戳值，从1970年1月1日起以毫秒为单位进行测量。
–另一个例子是，StringBuilder的复制构造函数接受一个字符串。
▪ 复制可变对象的另一种方法是clone（），某些类型（而不是所有类型）支持它。

▪ 这段代码的副作用是什么？

▪ Tweet的构造器保存了传入的引用，因此所有24个Tweet对象都在同一时间结束。

怎么解决？—仍然是防御性拷贝

▪ 一般来说，应该仔细检查所有ADT操作的参数类型和返回类型。
▪ 如果任何类型都是可变的，请确保实现不会返回对其表示的直接引用。
▪ 这样做会增加代表的曝光率。

把责任留给你的客户？
▪ 你可能会反对拷贝，这似乎是浪费。为什么要复制这些日期？为什么我们不能用这样一个精心编写的规范来解决这个问题呢？

–当没有任何其他合理的替代方案时（例如，可变对象太大而无法有效复制），有时会采用这种方法。
–但是，您对程序进行推理的能力和避免错误的能力的成本是巨大的。

使用不可变类型而不是可变类型
▪ 在没有令人信服的相反论据的情况下，对于抽象数据类型来说，保证其自身的不变量几乎总是值得的，而防止rep暴露对这一点至关重要。
▪ 更好的解决方案是选择不可变类型。如果我们使用了一个不可变的日期对象，比如java.time.ZonedDateTime，而不是可变的java.util.date，那么我们将在讨论了public和private之后结束本节。再也不可能暴露在公众面前了。

总结
▪ 不要将可变参数合并到对象中；制作防御副本
▪ 返回可变字段的防御副本…–返回新实例而不是修改它
▪ 或返回可变字段的不可修改视图
▪ 教训-使用不可变的组件，以消除防御性复制的需要

8代表不变量和抽象函数
▪ R： 表示值（rep值）的空间由实际实现实体的值组成。
–ADT将作为单个对象实现，但更常见的是需要一个小的对象网络，因此其值通常相当复杂。
▪ A： 抽象值的空间由类型设计为支持的值组成。
–它们是柏拉图式的实体，不存在于描述中，但它们是我们希望将抽象类型的元素视为该类型的客户机的方式。
–例如，无边界整数的抽象类型可能将数学整数作为其抽象值空间；例如，它可能被实现为原始（有边界）整数数组，这与该类型的用户无关。

▪ 抽象类型的实现者必须对表示值感兴趣，因为使用表示值空间实现抽象值空间是实现者的工作。
▪ 例如，假设我们选择使用字符串来表示一组字符： ▪ 然后表示空间R包含字符串，抽象空间A是字符的数学集合。

R与A之间的映射
▪ 每个抽象值都被一些rep值（surjective 满射）映射到。
–实现抽象类型的目的是支持对抽象值的操作。大概，我们需要能够创建和操作所有可能的抽象值，因此它们必须是可表示的。▪
一些抽象值被多个rep值（不是内射的）映射到。
–发生这种情况是因为表示不是严格编码。有多种方法可以将无序字符集表示为字符串。
▪ 并不是所有的rep值都被映射（不是双射的）。
–在本例中，字符串“abbc”未映射。在这种情况下，我们决定字符串不应包含重复项。这将允许我们在命中特定字符的第一个实例时终止remove方法，因为我们知道最多只能有一个。

抽象函数
▪ 一个抽象函数，它将rep值映射到它们表示的抽象值： AF:R→A▪ 图中的弧表示抽象函数。
–在函数的术语中，属性可以表示为：函数是满射的（也被调用），不一定是内射的（一对一），因此不一定是双射的，而且通常是部分的。

Rep不变量：另一个重要的ADT不变量
▪ 将rep值映射到布尔值的rep不变量：
RI:R→布尔值
▪ 对于代表值r，RI（r）是真的，前提是且仅当r由AF映射。
▪ 换句话说，RI告诉我们一个给定的rep值是否格式正确。
▪ 或者，您可以将RI看作一个集合：它是定义AF的rep值的子集。

▪ 表示不变性RI：某个具体的“表示”是否是“合法的”
▪ 也可将RI看作：所有表示值的一个子集，包含了所有合法的表示值
▪ 也可将RI看作：一个条件，描述了什么是“合法”的表示值

记录RI和AF
▪ rep不变量和抽象函数都应该记录在代码中，就在rep本身的声明旁边：

什么决定AF和RI？
▪ 抽象值空间本身并不决定AF或RI:–同一抽象类型可以有多个表示。
–一组字符可以等效地表示为字符串（如上所述）或位向量，每个可能的字符有一个位。
–显然，我们需要两个不同的抽象函数来映射这两个不同的代表值空间。
▪ 为rep定义一种类型，并因此选择rep值空间的值，并不确定哪些rep值将被视为合法，哪些是合法的，以及如何解释它们。

例如，如果我们允许字符串中存在重复项，但同时要求对字符进行排序，并以非递减顺序出现，那么将存在相同的rep值空间，但rep不变量不同。

▪ 即使对rep值空间使用相同的类型和相同的rep不变量RI，我们可能仍然会对rep进行不同的解释，使用不同的抽象函数AF…
-也许我们会将连续的字符对解释为子范围，这样字符串rep“acgg”就被解释为两个范围对，[a-c]和[g-g]，因此表示集合{a，b，c，g}。

下列哪个s值满足这个rep不变量？
–“abc”–“abcd”–“eeee”–“ad”–“adad”–“
▪ “AF（“acfg”）映射到以下哪一个？
–{a，b，c，d，e，f，g}–{a，b，c，f，g}–{a，c，f，g}
–其他一些抽象值
–没有抽象值，因为“acfg”不满足rep不变量
▪ 抽象函数映射到与它映射“tv”相同的抽象值的值是什么？–“ttv”–“ttuuvv”–“ttuv”–“tuv”

RI和AF对ADT设计的影响
▪ 关键点在于，设计抽象类型不仅意味着选择两个空间（规范的抽象值空间和实现的rep值空间），还意味着决定要使用哪些rep值以及如何解释它们。
抽象值
▪ 在代码中写下这些假设是非常重要的，这样未来的程序员（和未来的自己）就知道表示的实际含义了。–为什么？如果不同的实现者不同意rep的含义，会发生什么？

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

示例：有理数的ADT

本例的RI和AF
▪ RI要求分子/分母对为简化形式（即最低项），因此上面（2,4）和（18,12）这样的对应在RI之外绘制。

检查Rep不变量
▪ rep不变量不仅仅是一个简洁的数学概念。如果您的实现在运行时声明rep不变量，那么您可以及早捕获bug。
▪ 当然，您应该调用checkRep（）来在创建或变异rep（创建者、生产者和变异者）的每个操作结束时断言rep不变量。
▪ 观察者方法通常不需要调用checkRep（），但无论如何这样做都是很好的防御。——在每个方法中调用checkRep（），包括观察者，意味着您将更容易捕获由rep暴露引起的rep不变量冲突。

9有益的改变

▪ 回想一下，只有当类型的值在创建后从未更改时，类型才是不可变的。
▪ 随着我们对抽象空间A和rep空间R的新理解，我们可以完善这个定义：抽象值不应该改变。
▪ 但是，只要rep值继续映射到同一个抽象值，实现就可以自由地对其进行变异，这样客户机就看不到更改。
▪ 这种变化称为有益突变

有益突变的一个例子
▪ RatNum：这个rep有一个较弱的rep不变量，它不需要以最低的条件存储分子和分母

▪ 这个较弱的rep不变量允许一系列RatNum算术运算省略将结果减少到最低项。但是，当需要向人展示结果时，我们首先要简化它

▪ 注意，这个toString实现重新分配了私有字段分子和分母，并对表示进行了修改——即使它是不可变类型上的观察者方法！▪ 但是，关键的是，突变并没有改变抽象值。–将分子和分母除以相同的公因数，或将两者乘以-1，对抽象函数AF（分子，分母）=分子/分母的结果没有影响。
▪ 另一种思考方法是：AF是一个多对一函数，rep值已更改为另一个仍然映射到相同抽象值的函数。所以突变是无害的，或者说是有益的。

为什么需要有益的突变？
▪ 这种实现者自由通常允许性能改进，如：
– Caching：例如通过cache暂存某些频繁计算的结果
– Data structure rebalancing：例如对tree数据结构进行插入或删除节点之后
– Lazy computation：上例中在toString()的时候才进行约分计算

10记录AF、RI和Rep暴露的安全性

记录AF和RI
▪ 在类中记录抽象函数和rep不变量是一个很好的实践，在声明rep的私有字段的地方使用注释。
▪ 像“所有字段都有效”这样的泛型语句不足以成为RI，rep不变量的工作是精确解释字段值有效与否的原因。
▪ 对于AF来说，仅仅提供“表示一组字符”这样的通用解释是不够的，抽象函数的工作是精确定义具体字段值的解释方式。
–作为一个函数，如果我们使用文档化的AF并替换为实际（合法）字段值，我们应该获得它们所表示的单个抽象值的完整描述。

安全性证明
▪ 另一个文档是rep exposure安全性论证
▪ 这是一个注释，它检查rep的每个部分，查看处理该部分rep的代码（特别是有关参数和来自客户机的返回值的代码，因为这是rep公开发生的地方），并给出代码不公开rep的原因。

getFollowers（）对它返回的集合进行防御复制，所有其他参数和返回值都是不可变的字符串或void。
rep中的Set对象由不可修改的包装器设置为不可变的

摘要：ADT规范可能会谈论什么
▪ 抽象类型T的规范（由其操作规范组成）应该只讨论对客户可见的东西。
–这包括参数、返回值和由其操作引发的异常。
▪ 当规范需要引用类型T的值时，它应该将该值描述为抽象值，即抽象空间a中的数学值。

▪ 规范不应讨论代表性的细节或代表性空间的元素
▪ 它应该将rep本身（私有字段）视为对客户机不可见，就像方法体及其局部变量被视为不可见一样。ADT建设
▪ 这就是为什么我们将rep不变量和抽象函数编写为类主体内的普通注释，而不是类上方的Javadoc注释。该类型规范的一部分，它将影响rep独立性和信息隐藏。

如何建立不变量
▪ 不变量是一个对整个程序来说都是真的属性，如果是关于一个对象的不变量，它会减少到对象的整个生命周期。
▪ 为了保持不变，我们需要：–在对象的初始状态下使不变为真；–确保对对象的所有更改都保持不变为真。根据ADT操作的类型来转换此操作：
–创建者和生产者必须为新对象实例建立不变量；
–变异者和观察者必须保留不变量。
–在每个方法return之前使用checkRep（）检查不变量。

▪ rep暴露的风险使情况更加复杂。
▪ 如果rep被公开，那么对象可能会在程序中的任何地方被更改，而不仅仅是在ADT的操作中，并且我们不能保证在这些任意更改之后，不变量仍然保持不变。
▪ 所以证明不变量的完整规则
——如果一个抽象数据类型的不变量是由创建者和生产者建立的
——由变异者和观察者保存的
——不发生表示暴露，那么这个不变量对于抽象数据类型的所有实例都是正确的。

这里会导致rep暴露，因此客户机可能会无意中更改返回数组中的值，并因此破坏不变量，即使遵守了所有的规范。此方法创建一个新的三角形，但只更改腿，不重新计算它的新斜边。这不会保留新三角形的毕达哥拉斯不变量。

11个ADT不变量替换前置条件

ADT不变量替换前置条件
▪ 设计良好的抽象数据类型的一个巨大优势是，它封装并强制执行我们在前提条件中必须规定的属性。

ADT不变量替换前置条件
▪ 更安全的是避免出现错误，因为所需的条件（排序时不重复）可以在一个地方强制执行，即SortedSet类型，并且因为Java静态检查起作用，防止根本不满足此条件的值被使用，同时在编译时出错。
▪ 它更容易理解，因为它简单得多，SortedSet这个名字传达了程序员需要知道的东西。
▪ 它更易于更改，因为SortedSet的表示现在可以在不更改exclusiveOr或其任何客户端的情况下更改。

TweetList能够表示tweets具有不同时间戳的要求
UserName能够表示对有效用户名的约束。

摘要
▪ 抽象数据类型以其操作为特征。
▪ 操作可以分为创造者、生产者、观察者和变异者。
▪ ADT的规范是它的一组操作及其规范。
▪ 一个好的ADT是简单、连贯、充分和独立的。
▪ ADT通过为其每个操作生成测试来进行测试，但是在相同的测试中同时使用创建者、生产者、变异者和观察者。 3.3抽象数据类型（ADT）
▪ safe from bugs。一个好的ADT为一个数据类型提供了一个定义良好的契约，这样客户就知道从数据类型中期望得到什么，而实现者有定义良好的自由来改变。
▪ easy to understand。一个好的ADT将其实现隐藏在一组简单的操作后面，这样使用ADT的程序员只需要了解操作，而不需要了解实现的细节。
▪ready for change。表示独立性允许对抽象数据类型的实现进行更改，而不需要对其客户端进行更改。

▪ 不变量是在对象的生存期内，ADT对象实例始终为真的属性。
▪ 一个好的ADT保留它自己的不变量。不变量必须由创造者和生产者建立，并由观察者和变异者保存。
▪ rep不变量指定表示的合法值，并应在运行时使用checkRep（）进行检查。
▪ 抽象函数将具体表示映射到它所表示的抽象值。
▪ 表征暴露威胁着表征的独立性和不变量的保存。

▪ safe from bugs。一个好的ADT会保留它自己的不变量，这样这些不变量就不容易受到ADT客户机中的错误的影响，并且在ADT本身的实现中，可以更容易地隔离对不变量的冲突。显式声明rep不变量，并在运行时使用checkRep（）检查它，可以更早地捕获误解和错误，而不是继续使用损坏的数据结构。
▪ easy to understand。Rep不变量和抽象函数解释了数据类型表示的含义，以及它与抽象的关系。
▪ ready for change。抽象数据类型将抽象与具体表示分离开来，这使得无需更改客户机代码就可以更改表示。

重新学习数据结构，主要了解了一些关于数据结构的一些相关的概念；

数据结构是一种带结构的数据集合；它包括逻辑结构还有存储结构，然后学习了一下数据类型的表示以及实现，虽然在C语言基础中可以常常看到结构体，但是到今天才明白什么是用户建立自己的数据类型这句话，以下就是构建复数这样一个结构体的数据类型；

• 抽象数据类型是指一个数学模型以及定义在这个模型上的一组操作。
  抽象数据类型的定义仅仅取决于它的一组逻辑特性，而与它在计算机中的表示和实现无关。

• 数据类型一般指同一类数据的全体，用于高级语言中说明数据的分类，是一种属性，限制了该数据的变化范围和可进行的操作。

• 数据结构则是分为逻辑结构和物理结构，侧重数据以及数据之间的联系方式，表示数学模型极其操作到计算机上的应用。

总体就说 ADT 具体化 为数据结构 再可细化为数据类型。
下面介绍一个ADT的具体代码实现
（学习了复数的抽象数据类型实例）
头文件：

//complex.h头文件内容
#ifndef COMPLEX_H
#define COMPLEX_H
typedef struct 
{
	float Realpart;
	float Imagepart;
}complex;
//创建一个复数
complex Creat(float x, float y);
//获得复数的实部
float Getreal(complex c);
//获得数据的虚部
float Getimage(complex c);
//求两个复数的和sum
complex add(complex c1, complex c2);
//求两个复数的差difference
complex difference(complex c1, complex c2);
#endif

源代码：

#define _CRT_SECURE_NO_WARNINGS
#include"stdio.h"
#include"stdlib.h"
#include"complex.h"
void main(void)
{
	complex c1,c2,c3,c4;
	c1= Creat(1, 1);
	c2 = Creat(2, 2);
	Getreal(c1);
	Getimage(c2);
	c3=add(c1, c2);
	c4=difference(c1, c2);
	printf("c1=%f+(%f)i\n", c1.Realpart, c1.Imagepart);
	printf("c2=%f+(%f)i\n", c2.Realpart, c2.Imagepart);
	printf("c3=%f+(%f)i\n", c3.Realpart, c3.Imagepart);
	printf("c4=%f+(%f)i\n", c4.Realpart, c4.Imagepart);
	system("pause");
}
//创建一个复数
complex Creat(float x, float y)
{
	complex c;
	c.Realpart = x;
	c.Imagepart = y;
	return c;
}
//获得复数的实部
float Getreal(complex c)
{
	return c.Realpart;
}
//获得数据的虚部
float Getimage(complex c)
{
	return c.Imagepart;
}
//求两个复数的和sum
complex add(complex c1, complex c2)
{
	complex c;
	c.Realpart = c1.Realpart + c2.Realpart;
	c.Imagepart = c1.Imagepart + c2.Imagepart;
	return c;
}
//求两个复数的差difference
complex difference(complex c1, complex c2)
{
	complex c;
	c.Realpart = c1.Realpart - c2.Realpart;
	c.Imagepart = c1.Imagepart - c2.Imagepart;
	return c;
}

1. 抽象数据类型与表示独立性：能够分离程序中数据结构的形式和对其使用的方式。如何设计良好的抽象数据结构，通过封装来避免客户端获取数据的内部表示（表示泄露），避免潜在的bug–在client和implement之间建立“防火墙”.
2. ADT的特性：不变量、表示泄露、抽象函数AF、表示不变量RI。
3. 给出了一个类通过抽象函数和表示不变量来实现ADT意味着什么的更正式的数学概念。
4. 抽象函数将为我们提供一种在抽象数据类型上清晰定义等式的方法。
5. 基于数学的形式对ADT的核心特征进行描述并应用于设计中。

抽象和用户定义类型

除了编程语言所提供的基本数据类型和对象数据数据类型，程序员可以定义自己的数据类型。

1. 数据抽象

定义：由一组操作所刻画的数据类型。
-number是可以进行加和乘等操作的东西
-string是可以进行连接或者取子字符串的东西
传统上，程序员会提前定义自己的数据类型，比如创建一种记录日期的类型，具有年月日的整数段。传统的类型定义会更关注数据的具体表示
抽象类型关注于操作，强调“作用于数据上的操作”，程序员和用户无需关心数据如何存储。
注：抽象数据类型是由其操作定义的，与其内部实现无关。
类型T的操作和规约刻画了T的特性。当我们谈论列表类型时，我们的意思并不是链接列表、数组或者任何其他的数据结构代表一个列表，而是指的一组不透明的值，可能的对象可以有列表类型-满足所有操作的规格get(), size()等。

2. 分类类型和操作

1. 可变和不可变数据类型：无论内置的还是用户定义的类型，都可以分类为可变的或不可变的。
   （1） 可变类型的对象：提供了可改变其内部数据的值的操作
   （2） 不可变数据类型：其操作不可改变内部值，而是构造新的对象
   有时一个类型将以两种形式提供，一种可变，一种不可变，比如：StringBuilder是可变版本的String（两者不是相同的Java类型，也不可互换）
2. 对抽象类型的操作进行分类：
   （1） 构造器（从无到有）：创建该类型的新对象。
   构造器可以将对象作为参数，但是不能作为一个构建中的该类型的对象
   （2） 生产器（从有到新）：从该类型的旧对象创建新对象。比如String的conact方法就是一个生产器，它利用两个字符串生成一个表示其串联的新字符串。
   （3） 观察器：获取抽象类型的对象并返回不同的类型。比如List的size()方法就返回一个int型。
   （4） 变值器：改变对象属性的方法。比如List的add()方法，通过在尾部添加元素改变列表的属性。
   构造器：t*->T
   生产器：T+，t*->T
   观察器：T+，t*->T
   变值器：T+，t*->void | t | T
   其中每个T本身就是抽象数据类型，t为其他类型，+标记表示该类型可能在签名的该部分出现一次或多次，*标记表示它出现零次或多次，| 表示或。
3. 操作的签名：
   构造器可能实现为构造函数或静态函数，实现为静态方法的构造器通常称为工厂方法。
   变值器通常返回void，如果返回值为void，则必然意味着它改变了对象的某些内部状态。变值器也可能返回非空类型

3. 抽象数据类型实例

1. int：不可变，所以没有变值器
   –构造器:数字文字0，1，2，…
   –生产器:算术运算符+、-、*、/
   –观察器:比较运算符==，！= , < , >
   –变值器:无(它是不可变的)
2. String：String是Java的字符串类型，字符串是不可变的。
   –构造器:String类的构造函数
   –生产器:concat，substring，toUpperCase
   –观察器:length，chartAt
   -变值器：无
3. List：List是Java的列表类型，是可变的。
   列表也是一个接口，这意味着其他类提供数据类型的实际实现，如ArrayList和LinkedList。
   –构造器:ArrayList和LinkedList构造函数，Collections.singletonList
   –生产器:Collections.unmodifiableList
   –观察器:size，get
   –变值器:add , remove , addAll , Collections.sort
   

4. 设计抽象数据类型

良好ADT的设计：靠“经验法则”，提供一组操作，设计其行为规约 spec

1. 经验法则1：设计简洁、一致的操作
   –最好有一些简单的操作，可以以强大的方式进行组合，而不是大量复杂的操作，通过简单操作组和实现复杂的操作，操作的行为应该是内聚的
   –每个操作都应该有一个明确的目的，并且应该有一个连贯的行为，而不是一系列的特殊情况。
   –例如，我们可能不应该向列表中添加求和操作。它可能对使用整数列表的客户有所帮助，但是字符串列表呢？还是嵌套列表？所有这些特殊情况会使sum操作变得难以理解和使用。
2. 经验法则2：要足以支持用户对数据所做的所有操作需要,且用操作满足用户需要的难度要低
   操作集应该是足够的，因为必须有足够的操作来完成用户可能想要完成的计算。
   –一个好的测试是检查该类型的对象的每个属性都可以被提取。判断方法：对象每个需要被访问到的属性是否都能够被访问到
   例如，如果没有get操作，我们将无法找到列表的元素。没有get()操作就无法获取目录的内部数据
   –基本信息应该不难获得。
   例如，size方法对于List来说并不是严格必要的，因为我们可以在递增索引上应用get，直到失败，但这是低效和不方便的。用遍历方式获取List的size太复杂了，但是提供size()操作,会方便用户使用

5. 表示独立性

一个好的抽象数据类型应该是表示独立的。
表示独立性:客户端使用ADT时无需考虑其内部如何实
现，ADT内部表示的变化不应影响外部spec和客户端。
–抽象类型的使用独立于其表示(用于实现它的实际数据结构或数据字段)，因此表示的变化对抽象类型本身之外的代码没有影响。
–例如，“List”提供的操作与列表是以链表还是数组表示无关。
您将根本无法更改ADT的表示，除非其操作完全由前提条件和后置条件指定，以便客户知道依赖什么，并且您知道您可以安全地更改什么。通过前提条件和后置条件充分刻画了ADT的操作，spec规定了client和implementer之间的契约,明确了client知道可以依赖哪些内容，implementer（执行者）知道可以安全更改的内容。