抽象数据类型

抽象数据类型ADT

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

实现于程序时，抽象数据类型只显现出其接口，并将实现加以隐藏。用户只需关心它的接口，而不是如何实现。未来更可以改变实现的方式。（其支持信息隐藏原理，或保护程序免受变化的冲击。）

       用具体的例子来讲就好比每一个抽象数据类型就是乐高里面的一块积木，而抽象数据类型的接口就好比每一块积木上面的小圆点，通过其来实现相互连接，最后形成一个乐高作品，即我们的最终的程序。抽象数据结构即根据所要运算的数据以及其计算复杂性所定义的抽象存储区，而不关心具体的数据结构的实现。就如同我们不关心每个积木的内部构造，我们就关注他是什么样式，是块状还是条状、是绿色还是蓝色，有几个接口等等。

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

抽象数据类型的强处在于对用户隐藏了实现细节，仅公开其接口。这表示抽象数据类型可以用各种方法来实现，只要遵循其接口，就不会影响到用户。如果两个积木各有8个圆点，8个对8个拼接在一起便十分牢固，但只用其中一个就会变得十分容易三家。

在抽象数据类型和数据结构之间，有一个实现上的微妙差别。例如，列表的抽象数据类型可以数组为基础、或者使用链表来实现。列表即是一种具良好运算（加入元素、移除元素等等）定义的抽象数据类型。链表是以指针为基础的数据结构，且可用来创建一个列表。链表常用于列表的抽象数据类型。

同样地，二叉树搜索法的抽象数据结构可以几个方式实现：二叉树、AVL树、红黑树、数组等等。且无须关心其实现，二叉树搜索法总是有相同的运算（插入、移除、查找等等）。

从实现中分离出接口，并不表示用户不该知道实现的方法，而是用户不能依赖于实现细节。例如，一个抽象数据类型可以用脚本语言创建，或其它可以被反编译的语言（如C语言）。即使用户可发现实现的方法，只要所有客户端程序遵循该接口，且改变实现方式时不会产生影响，那就仍是抽象数据类型。

在面向对象的用语中，抽象数据类型相当于类别；抽象数据类型的实体就相当于对象。某些语言包含了用于宣告抽象数据类型的构造函数。例如，C++ 和 Java 为此提供了类的构造函数。