1.抽象数据类型

抽象数据类型(ADT)

ADT是计算机领域被广泛接受的一种思想和方法，也是一种用于设计和实现程序模块的有效技术。

---

0.数据类型和数据构造

• 数据有很多类型(数据类型)，比如整型、浮点型...各种编程语言都有类型的概念，每种语言都提供一组内置数据类型，并为每个内置类型提供一批操作。
• 就python而言，数据类型有bool、int、str、float...以及组合类型list、tuple、set、dict等.类型bool包含两个值True和False，可用的操作包括and、or、not；类型int包含很多值，对它们可以做加减乘除等运算；其余类型相仿。
• 这时候程序需要处理有理数(数学上，有理数是一个整数a和一个正整数b的比，例如3/8，通则为a/b)，因而我们很容易想到用一个tuple表示一个有理数，约定其中的第0项表示分子，第1项表示分母。我们为有理数提供一个相加的操作，即3/5+7/10 = （3*10 + 7*5）/（5*10）

r1 = (3,5)
r2 = (7,10)

def rational_plus(r1,r2):
    num = r1[0]*r2[1] + r2[0]*r1[1]
    den = r1[1]*r2[1]
    return num,den

r3 = rational_plus(r1,r2)
print(r3)

"""
(65, 50)
"""

这样编程perfect吗？进一步考虑，有很多缺陷：(尽管我也不是很明白，反正就有不好)

• 在这里使用的不是特殊的'有理数'，而是普通的元组，因此不能将其它元组相互区分；
• 与有理数相关的操作并没有绑定于表示有理数的二元组；
• 在为有理数对象定义运算(函数)的时，需要直接按位置取其元素。若需要处理的对象包含十个乃至几十个元素，就会让人很头疼。
  造成这些缺陷的最重要的问题之一是数据的表示完全暴露，以及对象使用和操作实现对具体的依赖性。所以，我们需要把对象的使用与其具体实现隔离开，抽象数据类型的思想和支持这种思想的编程机制能帮忙解决这些问题
  (理解：数据的表示完全暴露——这里我们用一个tuple表示一个有理数；依赖性——有理数加法操作的实现是依赖于元组的索引的)

---

1.抽象数据类型的概念

数据元素的基本思想是把数据定义为抽象(忽略细节，概括具体事物的特征) 的对象集合，只为它们定义可用的合法操作，并不暴露其内部实现的具体细节，不论是其数据的表示细节还是操作的实现细节

简单来说，一个抽象数据类型定义了：一个数据对象、数据对象中各元素之间的关系、及对数据元素的操作. 一个数据类型的操作通常可分为三类：

• 构造操作：这类操作基于一些已知的信息，产生出这种类型的一个新对象
• 解析操作：这种操作从一个对象取得有用的信息，其结果反映了被操作对象的某方面特性，但结果并不是本类型的对象
• 变动操作：这类操作修改被操作对象的内部状态

构造操作+解析操作 = 不变数据类型(简称不变类型)
构造操作+解析操作+变动操作 = 可变数据类型(简称可变类型)
在python语言中，不变类型：str、tuple、frozenset；可变类型：list、set、dict

---

2.抽象数据类型的描述

抽象数据类型的描述，其形式体现了抽象数据类型的主要特点

有一个简单的有理数抽象数据类型，有下面描述：

有理数抽象数据类型

• ADT表明这是一个抽象数据类型的描述，Rational是被定义抽象类型的名字
• 主体提供了7个操作，第一个操作以Rational作为名字，表示它是一个最基本的构造操作，从其它类型的参数出发构造本类型的对象
• 随后几个运算也是构造操作，它们基于Rational类型的对象生成Rational类型的新对象
• 最后两个操作是解析操作，取得有理数对象的性质(成分)

那如何描述一个抽象数据类型呢？照猫画虎..

• 一个ADT描述由一个头部和按一定格式给出的一组操作描述构成
• ADT的头部给出类型名，最前面是表示抽象数据类型的关键字ADT
• 操作的形式描述给出操作的名字、参数的类型和参数名
• 各操作的实际功能用自然语言描述，是一种非形式的说明，帮助理解操作