Abstract Data Type
抽象数据类型的定义(Abstract Data Type,ADT)
抽象数据类型( ADT,Abstract Data Type)是指一个数学模型以及定义在此数学模型上的一组操作。它通常是对数据的某种抽象,定义了数据的取值范围及其结构形式,以及对数据操作的集合。(抽象出来得到的数据 + 对数据的操作)
ADT的特性:
表示泄漏(representation exposure),抽象函数(Abstract function),表示不变量(representation invariants)。
特征如下:
1.数据抽象:用ADT描述程序处理的实体时,强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口(即外界使用它的方法)。
2.数据封装:将实体的外部特性和其内部实现细节分离,并且对外部用户 隐藏其内部实现细节,它包含两层含义:①将数据和其行为结合在一起,形成一个不可分割的独立单位;②信息隐藏,即尽可能隐藏数据内部细节,只留有限的对外接口形成一个边界,与外部发生联系。封装的原则使得软件错误能够局部化,大大降低排错的难度,便于软件的维护。
3.继承性:数据封装使得一个类型可以拥有一般类型的数据和行为,即对一般类型的继承。若特殊类型从多个一般类型中继承相关的数据和行为,则为多继承。
4.多态性:指在一般类型中定义的数据或行为被特殊类型继承后,具有不同的数据类型或呈现出不同的行为。例如,“苹果”是“水果”的子类,它可以有“水果”的一般“吃”法,但其本身还可以有别的多种“吃法”。
ADT的表示方法:
抽象数据类型是一个数学模型以及定义在其上的一组操作组成,因此,抽象数据类型一般通过数据对象、数据关系以及基本操作来定义,即抽象数据类型三要素是(D,R,P)。
表示形式具体如下:
ADT抽象数据类型名{
数据对象:<数据对象的定义>
数据关系:<数据关系的定义>
基本操作:<基本操作的定义>
}
设计ADT
设计好的ADT,靠“经验法则”,提供一组操作,设计其行为规约 spec。
基本规则:
1.设计简洁、一致的操作,操作的目标要清晰明确,简洁不复杂。
2.要足以支持client对数据所做的所有操作需要,且用操作满足client需要的难度要低,要便于client使用。
ADT的特性的细节
1.规约(Specification)
规约简单来说就是一份合同,一份契约:它规定了ADT的实现者需要按照规约进行实现,而客户则像使用说明书一样来使用规约,spec给实现者以及客户端两方都提供了要求。Spec给“供需双方”都确定了责任,在调用的时候双方都要遵守。
规约的意义:防止实现者和客户端之间产生误解。不同开发者想法不同,使用规约来对大家的做法进行统一。客户端无需阅读调用函数的代码,只需理解spec即可。
行为等价性:ADT之间是否可以相互替换?我们应该站在客户端的角度来进行观察,如果两个不同的ADT的实现所需要的输入以及产生的输出影响都是一样的,那我们就可以说他们具有行为等价性。那么简单的判定方式什么呢:利用规约来判定行为是否等价(一定要注意:规约中不应当包括局部变量,私有字段以及ADT的实现细节)
前置条件:对客户端的约束,在使用方法时必须满足的条件。后置条件:对开发者的约束,方法结束时必须满足的条件。契约:如果前置条件满足了,后置条件必须满足。
Java中通常来讲有两类规约:
(1).静态类型声明是一种规约,可据此进行静态类型检查static checking
(2).方法前的注释也是一种规约,但需人工判定其是否满足。@param @return @throws。
2.表示独立性(Representation Independence)
client使用ADT时无需考虑其内部如何实现,ADT内部表示的变化不应影响外部spec和客户端。spec规定了client和implementer之间的契约。我的理解就是RI就是用户和程序员之间的一种默契,二者独立开来互不影响。程序员以一种内部细节不可访问的方式去满足用户的要求,用户也不需要去关注其内部实现,用户只需通过specification去了解该程序如何使用及其注意事项。
3.表示不变性(Representation Invariant)
某个具体的“表示”是否是“合法的”。也可将RI看作:所有表示值的一个子集,包含了所有合法的表示值;也可将RI看作:一个条件,描述了什么是“合法”的表示值
4.抽象函数(Abstract Function)
Rep space和Abstract space之间映射关系的函数(满射、未必单射、未必双射),即如何去解释R中的每一个值为A中的每一个值。ADT开 发者关注表示空间R,client关注抽象空间A。
5.设计流程
(1) 选择R和A:
(2) RI --- 合法的表示值:要精确的记录RI:rep中的所有fields何为有效,针对Rep的每一个field以及多个fields之间的关系,进行条件限定,要精确。
(3) 如何解释合法的表示值 ---映射AF:要精确记录AF:如何解释每一个R值,给出client看到的A值是什么,是对每一个Rep值的“数学运算”。
(4)表示泄漏安全说明)rep exposure safety:给出理由,证明代码并未对外泄露其内部表示。