数学模型和数学建模 ADT(数学模型)详细资料大全

ADT(数学模型)详细资料大全  

抽象数据类型（Abstract Data Type，ADT）是计算机科学中具有类似行为的特定类别的数据结构的数学模型；或者具有类似语义的一种或多种程式设计语言的数据类型。抽象数据类型是间接定义的，通过其上的可执行的操作以及这些操作的效果的数学约束（与可能的代价）。

基本介绍

中文名：抽象数据类型外文名：Abstract Data Type简称：ADT领域：计算机科学 简介,示例,接口和实现的分离,抽象数据结构,内置抽象数据类型,实际示例,作为抽象数据类型的有理数,堆叠,用法,各种实现,参阅,

简介

抽象数据类型（AbstractDataType，ADT）是计算机科学中具有类似行为的特定类别的数据结构的数学模型；或者具有类似语义的一种或多种程式设计语言的数据类型。抽象数据类型是间接定义的，通过其上的可执行的操作以及这些操作的效果的数学约束（与可能的代价）。 例如，抽象的堆叠（stack）由3个操作定义：推入push，弹出pop（接受约束：每次弹出返回的是最新被推入且没有被弹出的数据，也就是后进先出），查看堆叠顶端数据peek。当分析使用堆叠算法的效率，所有这3个操作用时相同，无论堆叠中包含多少项数据；并且对每项数据栈使用了常量大小的存储。 抽象数据类型（ADT）是纯粹理论实体，用于简化描述抽象算法，分类与评价数据结构，形式描述程式设计语言的类型系统。一个ADT可以用特定数据类型或数据结构实现，在许多程式设计语言中有许多种实现方式；或者用形式规范语言描述。ADT常实现为模组（module）：模组的接口声明了对应于ADT操作的例程（procedure），有时用注释描述了约束。

示例

在程式语言（或库）和教科书中，常见的几个抽象数据类型如下： 关联数组 复数 容器 双端伫列 列表 Multimap 优先伫列 伫列 集合 堆叠 字元串 树

接口和实现的分离

实现于程式时，抽象数据类型只显现出其接口，并将实现加以隐藏。用户只需关心它的接口，而不是如何实现。未来更可以改变实现的方式。（其支持信息隐藏原理，或保护程式免受变化的冲击。） 抽象数据类型的强处在于对用户隐藏了实现细节，仅公开其接口。这表示抽象数据类型可以用各种方法来实现，只要遵循其接口，就不会影响到用户。 在抽象数据类型和数据结构之间，有一个实现上的微妙差别。例如，列表的抽象数据类型可以数组为基础、或者使用炼表来实现。列表即是一种具良好运算（加入元素、移除元素等等）定义的抽象数据类型。炼表是以指针为基础的数据结构，且可用来创建一个列表。炼表常用于列表的抽象数据类型。 同样地，二叉树搜寻法的抽象数据结构可以几个方式实现：二叉树、AVL树、红黑树、数组等等。且无须关心其实现，二叉树搜寻法总是有相同的运算（插入、移除、查找等等）。 从实现中分离出接口，并不表示用户不该知道实现的方法，而是用户不能依赖于实现细节。例如，一个抽象数据类型可以用脚本语言创建，或其它可以被反编译的语言（如C语言）。即使用户可发现实现的方法，只要所有客户端程式遵循该接口，且改变实现方式时不会产生影响，那就仍是抽象数据类型。 在面向对象的用语中，抽象数据类型相当于类别；抽象数据类型的实体就相当于对象。某些语言包含了用于宣告抽象数据类型的构造函式。例如，C++ 和 Java 为此提供了类的构造函式。

抽象数据结构

抽象数据结构即根据所要运算的数据以及其计算复杂性所定义的抽象存储区，而不关心具体的数据结构的实现。 就实现高效率的算法而言，对数据结构的选择相当重要。抽象数据结构的选择，决定了高效率的算法的设计，和估计其计算复杂性。 这个概念与程式语言理论中所使用的抽象数据类型非常接近，大致上抽象数据结构和抽象数据类型的名称，和具体的数据结构的名称一致。

内置抽象数据类型

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

实际示例

作为抽象数据类型的有理数

有理数（可以 a/b 格式表示的数，且 a 和 b 都是整数）本来是不能在电脑中表示出来。不过可以合理的抽象数据类型来定义，如下。 构造：使用两个整数 a 与 b 创建实体，其中 a 为分子，b 为分母。 运算：加法、减法、乘法、除法、乘幕、比较、约分，转成实数（浮点数）。 要完成整个规格，就要根据数据来定义所有的运算。例如，当两个有理数 a/b 和 c/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); f = stack_pop(stack); 

各种实现

上述堆叠的抽象数据类型，一开始可以使用数组来实现，然后改用炼表，而不会伤到任何用户的代码。有多少方法可以实现抽象数据类型，取决于程式语言。例如，上述示例可使用C 编写一个结构，以及随同的一组数据结构，可使用数组或炼表来存放记录；当构造函式函式返回一个抽象句柄时，就对用户隐藏了真实的实现过程。

参阅

抽象化