本文共 3457 字,大约阅读时间需要 11 分钟。
本文内容,来说明一下抽象数据型(ADT)在软件构造中的重要作用。
1.抽象数据类型(Abstract Data Type,ADT)是将数据对象、数据对象之间的关系和数据对象的基本操作封装在一起的一种表达方式,它和工程中的应用是一致的。
在工程项目中,开始编程之前,首先列出程序需要完成的功能任务,先不用管具体怎么实现,实现细节在项目后期完成,一开始只是抽象出有哪些基本操作。把这些操作项封装为抽象数据类型,等待后面具体实现这些操作。而其他对象如果想调用这些操作,只需要按照规定好的参数接口调用,并不需要知道具体是怎么实现的,从而实现了数据封装和信息隐藏。
2.抽象数据类型可以用以下的三元组来表示:
ADT抽象数据类型名{
数据对象:<数据对象的定义> 数据关系:<数据关系的定义> 基本操作:<基本操作的定义> } ADT抽象数据类型名3. 例如,线性表的抽象数据类型的定义:
ADT List{
数据对象:D={ai|ai∈Elemset, i=1,2,…,n, n≥0} 数据关系:R={<ai−1,ai>|ai−1,ai∈D, i=2,…,n} 基本操作: InitList(&L) 操作结果:构造一个空的线性表 L DestroyList(&L) 初始条件:线性表已存在 操作结果:销毁线性表L ClearList(&L) 初始条件:线性表已存在 操作结果:置线性表L为空表 ListEmpty(L) 初始条件:线性表已存在 操作结果:若线性表L为空表,则返回TRUE,否则返回FALSE ListLenght(L) 初始条件:线性表已存在 操作结果:返回线性表L数据元素个数 GetElem(L, i, &e) 初始条件:线性表已存在(1≥i≥ListLenght(L)) 操作结果:用e返回线性表L中第i个数据元素的值 locatElem(L, e, comare()) 初始条件:线性表已存在,comare()是数据元素判定函数 操作结果:返回线性表L中第1个与e满足关系comare()的数据元素的位序 PriorElem(L, cur_e, &pre_e) 初始条件:线性表已存在 操作结果:若cur_e是线性表L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败,pre_e无定义 NextElem(L, cur_e, &next_e) 初始条件:线性表已存在 操作结果:若cur_e是线性表L的数据元素,且不是第最后一个,则用next_e返回它的后继,否则操作失败,next_e无定义 ListInsert(&L, i, e) 初始条件:线性表已存在(1≥i≥ListLenght(L)+1) 操作结果:在线性表L中第i个数据元素之前插入新元素e,L长度加1 ListDelete(&L, i, &e) 初始条件:线性表已存在(1≥i≥ListLenght(L)) 操作结果:删除线性表L中第i个数据元素,用e返回其值,L长度减1 ListTraverse(L, visit()) 初始条件:线性表已存在 操作结果:依次对线性表L的每个数据元素调用visit()函数,一旦visit()失败,则操作失败 }ADT List抽象数据类型是软件工程中一个普遍原则的实例,从它衍生出很多意思相近的名词。这里列出了几个能够表达其中思想的词:
在软件构造的过程中,我们会遇到各种各样的问题,当然对于问题测试大于编程 ,但是在设计方法和规格说明的时候,对于任务的抽象应用也很重要,这会是我们方便很多。
分类一个ADT(抽象数据型)的操作:
Creators:Creators能够通过一些必需的参数来构造一个新的对象,即从无到有。(构造器) Producers:Producers能从一个对象产生一个新对象(相同的对象)。例如String的concat()操作能够从两个String中合并产生新的String。(生产器) Observers:Observers通过观察一个抽象类型的对象来返回一个不同于观察对象的一个新对象。例如List的size()。(观察器) Mutators:用于改变对象属性的方法。例如List的add()。(变值器) 注:如果有Mutators方法的话,那么数据类型必然是可变类型的。可变类型的例子:
List: creators:ArrayList 和LinkedList的constructor,Collections.singletonList。 producer:Collections.unmodifiable.List observers:size,get mutators:add,remove,Collections.sort不可变类型的例子:
String: creators:String constructor。 producer:concat,substring,toUpperCase。 observers:length。 mutators:没有。因为是不可变数据类型设计好的ADT,靠“经验法则”,提供一组操作,设计行为规约spec。主要有以下几个要求:
1.设计简洁,一致的操作。 比起许多复杂的操作,不如结合有用的方法的简单的操作。每一个操纵都应该有明确的目的。并且有一致的行为而不是一大堆的特例。 2.要足以支持用户对数据所做的所有操作的需要,而且设计操作的难度要低。 3.一个好的抽象数据类型应该是表示独立的。这意味着它的使用和它的内部表示(实际的数据结构和实现)无关,所以内部表示的改变将对外部的代码没有影响。例如,List
就是表示独立的——它的使用与它是用数组还是连接链表实现无关。 如果一个操作完全在规格说明中定义了前置条件和后置条件,使用者就知道他应该依赖什么,而你也可以安全的对内部实现进行更改(遵循规格说明)。
抽象数据类型的主要作用是数据封装和信息隐藏,让实现与使用相分离。数据及其相关操作的结合称为数据封装。对象可以对其他对象隐藏某些操作细节,从而使这些操作不会受到其他对象的影响,这就是信息隐藏。
抽象数据类型独立于运算的具体实现,使用户程序只能通过抽象数据类型定义的某些操作来访问其中的数据,实现了信息隐藏。转载地址:http://mwxbi.baihongyu.com/