- Part I Abstraction and User-Defined Types
- Part II Classifying Types and Operations
- Part III Abstract Data Type Examples
- Part IV Designing an Abstract Type
- Part V Representation Independence
文章的内容是我在复习这门课程时候看PPT时自己进行的翻译和一些总结，如果有错误或者出入希望大家能和我讨论！同时也希望给懒得翻译PPT而刷到这篇博客的你一些帮助！
Part I Abstraction and User-Defined Types
每一种编程语言都有他自己内置的变量类型，例如大家再熟悉不过的int、boolean、strings等等。当然用户可以根据自己的需要定义自己的数据类型。
数据抽象：
数据抽象是指由一组操作所刻画的数据类型，例如数字number就是一种能够进行加和乘的东西，而字符串string是一种可以进行连接和获得子串的东西。
- 传统的类型定义：
程序员在使用早先时候的编程语言的时候，定义变量时更关注于数据的具体表示。例如，他们会创建一个int整型变量来存储一天的年月日日期。 - 抽象类型：
抽象类型更加聚焦于操作。它的使用者无需担心它的数据实际上是怎么存储的，它的实现者也可以忽略编译器实际存储它的方式。所有所有需要关注的就是这个数据类型是怎么操作的。
需要记住，一个抽象树类型是由他所能进行的操作定义的。对于一种类型
为了更明了一点，举一个例子。当我们说到数据类型List的时候，我们说的既不是ArrayList亦或是LinkedList，我们说的只是List这一个数据类型和它能进行的操作，并不关注他具体是由链表实现还是由数组实现。
数据类型可以分为可变数据类型和不可变数据类型。可变型的对象提供了可改变其内部数据的值的方法，而不可变数据类型的对象，他的操作其操作不可改变内部值，而是构造新的对象并且更改引用。关于这一部分的详细内容可以看一看我的笔记四。
接下来介绍非常重要的几个概念：
- 构造器Creators：
构造器的功能是实现一个抽象数据类型从无到有的过程。一个构造器所使用的参数可以是一个对象，但是不可以是正在构造的这个对象。 - 生产器Producer：
生产器的功能是从一个旧的对象中派生出一个新的对象，实现从有到新的过程。举一个例子吧，对象数据类型String中的.concat()方法的功能是连接两个字符串，它产生了一个新的对象，它实际上就是一个Producer。 - 观察器Observers：
观察器的功能是观察对象的某些性质，表现出来的结果就是返回一个跟对象不同类型的值。例如List中的.size()方法，它的返回值是一个int。 - 变值器Mutators：
变值器是指那些能够改变对象属性的方法。List中的.add()方法就是一个例子，它在原本的对象尾部添加了一个新的元素，使它本身的发生了改变。
对下表中的符号进行一些说明：
- 每一个T是一个抽象数据类型本身
- 每一个t是一些其他的数据类型
- + 号意味着前面的符号出现一次或者更多次
- * 号意味着前面的符号没出现过或者更多次
- | 号就是逻辑操作符or
| OP | effect |
|---|---|
| Creators | t* → T |
| Producer | T+, t* → T |
| Observer | T+, t* → t |
| Mutator | T+, t* → void | t | T |
Creator的标签
对于Creator来说的话，他在实现的过程中可能被弄成构造函数或者静态函数，而实现静态方法的Creator通常被称为工厂方法。
Mutator的标签
Mutator通常都是void方法，也就是说它多数情况下都会返回void。那么如果它返回了void，那么一定意味着他改变了对象的某些内部状态。当然啦，Mutator返回值也可以是非空的类型。例如Mutator方法Set.add()返回值就是一个boolean类型，成功添加返回true，失败添加返回false。
这一部分举一些例子，让大家更好的熟悉一下抽象数据类型
首先我们来看一看一个不可变数据类型String中的方法：
| 方法 | 类型 |
|---|---|
| Creators | String constructors |
| Producers | .concat()，.substring()，.toUpperCase |
| Observers | .length，.charAt() |
| Mutators | NONE(It’s immutable) |
再来看一个可变数据类型List中的方法
| 方法 | 类型 |
|---|---|
| Creators | ArrayList and LinkedList constructors , Collections.singletonList |
| Producers | Collections.unmodifiableList |
| Observers | .size()，.get() |
| Mutators | .remove()，.addAll()，Collections.sort |
做一个小练习吧~
这里解释一下最后一个BufferedReader.readLine()。在课后也有同学提问为什么这个方法是Mutator。老师给出了解答：当调用这个.readLine()方法时，内部的指针指向的位置放生了改变，因此为Mutaor。
Part IV Designing an Abstract Type
设计一个ADT包括了选择好的操作以及要决定它们怎么运作。良好的ADT设计要考经验法则，提供一组操作，设计其行为规约Spec。
-
Rules of thumb 1 设计简洁、一致的操作
使用简单但是数量上多一些的小操作往往是更好的。通过简单操作的组合来实现更加复杂的操作，要远远比弄一个巨大巨复杂的方法好。而且操作应该是有着被精心设计过的目的，也就是说，方法的行为应该是内聚的，而不是包含一个非单一的全套动作。 -
Rules of thumb 2 要足以支持client对数据所做的所有操作需要，且用操作满足client需要的难度要低
也就是说操作集的规模应该是足够大的，可以满足客户端想要进行的所有计算和访问。这个经验规则的判断方法也很简单，检测一下对象每一个需要被访问到的属性是否都能被访问到就可以了。
举一个例子来说明吧。对于ADTList来说，如果我们没有.get()方法，我们就无从访问List中的值；如果没有.size()方法就需要使用比那里的方法来获取数组的长度，比较麻烦。 -
Rules of thumb 3 要么抽象、要么具体
面向具体应用的ADT不应该包含通用的方法，同样的，面向通用类型的ADT也不应该包含一些特化的方法。
这一部分的内容很重要，讲的是表示独立性的内容，在后面的学习中有很多使用
首先说一下表示独立性的概念：客户端在使用ADT的时候无需考虑其内部是如何实现的，ADT内部标识的变化不影响外部Spec和客户端。
这个概念很重要，它保证了通过前提条件和后置条件可以充分刻画了ADT的操作，Spec规定了客户端和实现这之间的契约，明确了客户端可以知道依赖哪些内容，实现者知道可以安全更改的内容。
持更QAQ
