抽象资料型别

数学模型的数据类型

抽象资料型别(英语:Abstract data type,缩写:ADT)是计算机科学中具有类似行为的特定类别的数据结构数学模型;或者具有类似语义的一种或多种程序设计语言数据类型。抽象数据类型是间接定义的,通过其上的可执行的操作以及这些操作的效果的数学约束(与可能的代价)。

例如,抽象的堆叠(stack)由3个操作定义:推入push,弹出pop(接受约束:每次弹出返回的是最新被推入且没有被弹出的数据,也就是后进先出),查看堆叠顶端数据peek。当分析使用堆叠演算法的效率,所有这3个操作用时相同,无论堆叠中包含多少项数据;并且对每项数据栈使用了常量大小的存储。

抽象数据类型(ADT)是纯粹理论实体,用于简化描述抽象算法,分类与评价数据结构,形式描述程序设计语言的类型系统。一个ADT可以用特定数据类型或数据结构实现,在许多程序设计语言中有许多种实现方式;或者用形式规范语言描述。ADT常实现为模块(module):模块的接口声明了对应于ADT操作的例程(procedure),有时用注释描述了约束。

范例

在程式语言(或函式库)和教科书中,常见的几个抽象资料型别如下:

介面和实作的分离

实现于程式时,抽象资料型别只显现出其介面,并将实作加以隐藏。使用者只需关心它的介面,而不是如何实作。未来更可以改变实作的方式。(其支援资讯隐藏原理,或保护程式免受变化的冲击。)

抽象资料型别的强处在于对使用者隐藏了实作细节,仅公开其介面。这表示抽象资料型别可以用各种方法来实作,只要遵循其介面,就不会影响到使用者。

在抽象资料型别和资料结构之间,有一个实作上的微妙差别。例如,列表的抽象资料型别可以阵列为基础、或者使用链表来实作。列表即是一种具良好运算(加入元素、移除元素等等)定义的抽象资料型别。链表是以指标为基础的资料结构,且可用来建立一个列表。链表常用于列表的抽象资料型别。

同样地,二元树搜寻法的抽象资料结构可以几个方式实作:二元树、AVL树、红黑树、阵列等等。且无须关心其实作,二元树搜寻法总是有相同的运算(插入、移除、寻找等等)。

从实作中分离出介面,并不表示使用者不该知道实作的方法,而是使用者不能依赖于实作细节。例如,一个抽象资料型别可以用脚本语言建立,或其它可以被反编译的语言(如 C语言)。即使使用者可发现实作的方法,只要所有客户端程式遵循该介面,且改变实作方式时不会产生影响,那就仍是抽象资料型别。

在物件导向的用语中,抽象资料型别相当于类别;抽象资料型别的实体就相当于物件。某些语言包含了用于宣告抽象资料型别的建构子。例如,C++ 和 Java 为此提供了类别建构子。

抽象资料结构

抽象资料结构即根据所要运算的资料以及其计算复杂性所定义的抽象储存区,而不关心具体的资料结构的实作。

就实作高效率的演算法而言,对资料结构的选择相当重要。抽象资料结构的选择,决定了高效率的演算法的设计,和估计其计算复杂性。

这个概念与程式语言理论中所使用的抽象资料型别非常接近,大致上抽象资料结构和抽象资料型别的名称,和具体的资料结构的名称一致。

内建抽象资料型别

一部分抽象资料型别在程式设计中相当普遍且实用,所以在某些程式语言中,成为原生型别、或加进标准函式库中。例如,Perl 的阵列可以用列表或双端伫列之类的抽象资料型别来实作,杂凑表也可以用 Map 或 Table 来做。C++ 标准函式库和 Java 函式库也提供了列表、堆叠、伫列、Map、优先权伫列和字串。

实际范例

作为抽象资料型别的有理数

有理数(可以 a/b 格式表示的数,且 a 和 b 都是整数)本来是不能在电脑中表示出来。不过可以合理的抽象资料型别来定义,如下。

构造:使用两个整数 a 与 b 建立实体,其中 a 为分子,b 为分母。

运算:加法、减法、乘法、除法、乘幕、比较、约分,转成实数(浮点数)。

要完成整个规格,就要根据资料来定义所有的运算。例如,当两个有理数 a/b 和 c/d 相乘时,相乘的结果就要定义为 ( a c ) / ( b d )。还有输入、输出、先决条件、后置条件,以及对抽象资料型别的各种假定。

堆叠

介面

堆叠的抽象资料型别介面,以 C 语法编写:

long stack_create(); /* 建立新的堆疊實體 */
void stack_push(long stack, void *item); /* 將一個項目堆入堆疊 */
void *stack_pop(long stack); /* 從堆疊頂部取得項目 */
void stack_delete(long stack); /* 刪除堆疊 */

用法

抽象资料型别可以如下方式使用:

long stack;
struct foo *f;

stack = stack_create(); /* 建立堆疊 */

stack_push(stack, f); /* 將 foo 結構加入堆疊 */

f = stack_pop(stack); /* 從堆疊取得頂部的結構 */

各种实作

上述堆叠的抽象资料型别,一开始可以使用阵列来实作,然后改用链表,而不会伤到任何使用者的代码。有多少方法可以实作抽象资料型别,取决于程式语言。例如,上述范例可使用 C 编写一个结构,以及随同的一组资料结构,可使用阵列或链表来存放记录;当建构子函式返回一个抽象句柄时,就对使用者隐藏了真实的实作过程。

参阅