MIT抽象数据类型笔记
抽象数据类型可以帮助我们将数据结构的使用和数据结构的具体实现分开，它是java编程时重要的工具。
为什么要使用抽象数据类型
抽象数据类型的主要作用是数据封装和信息隐藏，让实现与使用相分离。数据及其相关操作的结合称为数据封装。对象可以对其他对象隐藏某些操作细节，从而使这些操作不会受到其他对象的影响，这就是信息隐藏。
抽象数据类型独立于运算的具体实现，使用户程序只能通过抽象数据类型定义的某些操作来访问其中的数据，实现了信息隐藏。
抽象数据类型相比较数据结构要具体一些，我们光有了数据结构还不够，因为数据是各种各样的，对于不同数据，我们能采取的方法也不一样，比如说学生数据可以增减，成绩数据可以进行算数运算，但是为什么说抽象呢，也就说他并不是具体整型还是字符型这种基本类型，而是我们根据我们要解决的实际问题，对应现实世界所描述的一种和现实世界中的实体对应的数据类型，而且这种抽象的数据类型还包括能够对于他实行的操作，比如说我们定义一种数据类型叫“学生”，具体的数据我可以定义一中类似表的结构存储，而且还要定义一些操作，比如说添加学生，删除学生，这两部分就共同组成了“学生”这个抽象的数据类型。
抽象数据类型
：**抽象数据类型（Abstract Data Type，ADT）**是计算机科学中具有类似行为的特定类别的数据结构的数学模型；或者具有类似语义的一种或多种程序设计语言的数据类型。
- 抽象： 忽略底层的细节而在高层思考
- 模块化：将系统分为一个模块，每个模块可以单独的进行设计、实现、测试、推倒，并且在剩下的开发中进行复用。
- 封装：在模块的外部建立起一道“围墙”，使它只对自己内部的行为负责，并且系统别处的bug不会影响到它内部的正确性。
- 信息隐藏：将模块的实现细节隐藏，使未来更改模块内部时不必改变外部代码。
- 功能分离：一个模块仅仅负责一个特性/功能，而不是将一个特性运用在很多模块上或一个模块拥有很多特性。
抽象类型的操作符
- 创建者creator：创建一个该类型的新对象。一个创建者可能会接受一个对象作为参数，但是这个对象的类型不能是它创建对象对应的类型。
- 生产者producer：通过接受同类型的对象创建新的对象。例如， String类里面的 concat 方法就是一个生产者，它接受两个字符串然后据此产生一个新的字符串。
- 观察者observer：接受一个同类型的对象然后返回一个不同类型的对象/值。例如List的 size 方法，它返回一个 int。
- 改造者mutator：改变对象的内容，例如 List的 add 方法，它会在列表中添加一个元素。
可以将这种区别用映射来表示：
- creator : t* → T
- producer : T+, t* → T
- observer : T+, t* → t
- mutator : T+, t* → void | t | T
一般来说，构造者通常都是用构造函数实现的，例如 new ArrayList() 。但是有的构造体是静态方法（类方法）实现的，例如String.valueOf ，这样的静态方法也被称为工厂方法。
抽象类型由操作构成本身
对于类型T来说，它的操作集合和规格说明完全定义和构造了它的特性。例如，当我们谈到List类型时，我们并没有特指一个数组或者链接链表，而是一系列模糊的值——哪些对象可以是List类型——满足该类型的规格说明和操作规定，例如 get(), size(), 等等。
如何设计一个抽象类型
要求
- 应设计少量，简单，可组合成复杂功能的操作（而非复杂操作）
- 说明每一个操作的目的
- 应充分考虑用户需求
- 只设定于一个特定领域
表示独立
特别地，一个好的抽象数据类型应该是表示独立的。这意味着它的使用和它的内部表示（实际的数据结构和实现）无关，所以内部表示的改变将对外部的代码没有影响。例如，List就是表示独立的——它的使用与它是用数组还是连接链表实现无关。
如果一个操作完全在规格说明中定义了前置条件和后置条件，使用者就知道他应该依赖什么，而你也可以安全的对内部实现进行更改（遵循规格说明）。
抽象数据类型的表示
抽象数据类型可以使用一个三元组来表示：
ADT = (D, S, P)
其中D 是数据对象，S 是D 上的关系集，P 是加在D 上的一组操作。
在定义抽象数据类型时，我们使用以下格式：
ADT 抽象数据类型名{
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<基本操作的定义>
}