抽象数据类型

抽象数据类型（Abstract Data Type，ADT）是指一个数学模型以及定义在这个模型上的一组操作。抽象数据类型的定义仅仅取决于它的一组逻辑特性，而与它在计算机中的表示和实现无关。

抽象数据类型有两个重要特征：数据抽象和数据封装。

所谓数据抽象是指用ADT描述程序处理的实体时，强调的是其本质的特征，无论内部结构如何变化，只要本质特性不变，就不影响其外部使用。例如，在程序设计语言中经常使用的数据类型int，它就可以理解为是一个抽象数据类型，在不同的计算机或操作系统中，它的实现方式可能会有所不同，但它本质上的数学特性是保持不变的， int类型的数据指的是整数，可以进行加减乘除模等一些运算，int类型数据的这些数学特性保持不变，那么在编程者来看，它们都是相同的。因此数据抽象的意义在于数据类型的数学抽象特性。

而另一方面，所谓的数据封装是指用户在软件设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算，需要通过固有数据类型（高级编程语言中已实现的数据类型）来实现，它在定义时必须要给出名字及其能够进行的运算操作。一旦定义了一个抽象数据类型，程序设计中就可以像使用基本数据类型那样来使用它。例如，在统计学生信息时，经常会使用姓名、学号、成绩等信息，我们可以定义一个抽象数据类型“student”，它封装了姓名、学号、成绩三个不同类型的变量，这样我们操作student的变量就能很方便地知道这些信息了。C语言中的结构体以及C++语言中的类等都是这种形式。

抽象数据类型在定义时遵循一定的格式规范，一般抽象数据类型的定义格式如下所示：

ADT 抽象数据类型名
{
Data:
​    数据元素之间逻辑关系的定义；
 Operation:
   操作1；
   操作2；
   …
}

使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。

抽象数据类型的定义由一个值域（Data）和定义在该值域上的一组操作（Operation）组成，若按其值的不同特性，可将抽象数据类型细分为三类：

（1）原子类型

属于原子类型的变量，值是不可分解的。例如int、char等这些数据类型就无法再分解，属于原子类型的数据类型。一般较少定义这种抽象数据类型，因为固有数据类型基本都能满足程序设计。

（2）固定聚合类型

这种抽象数据类型，其值是由确定数目的成分按一定的结构组成。例如以上讲解的student抽象数据类型，由姓名、学号、成绩三个成分按照先后顺序组成。

（3）可变聚合类型

与固定聚合类型相比，构成可变聚合类型值的成分的数目不确定。例如，定义一个“字符序列”，其中序列长度是可变的，我们并不知道会有多少个字符来组成这个序列。

抽象数据类型可以更好地使程序设计模块化，在模块内部给出这些数据的表示及其操作的细节，在模块外部使用抽象的数据和抽象的操作。而且，所定义的数据类型的抽象层次越高，含有该抽象数据类型的软件模块的复用程度也就越高。