数据结构Java语言描述：数据类型与抽象数据类型

抽象数据类型是描述数据结构的一种理论工具，在介绍抽象数据类型之前，首先介绍一下数据类型的基本概念。

数据类型（Data Type）是指一组性质相同的数据元素的集合，以及加在这个集合上的一组操作。例如Java语言中包含数值型、字符串、布尔型等许多不同的数据类型。以Java语言中的int型为例，int型数据元素的集合是［-2 147 483 648，2 147 483 647］间的整数，定义在int型数据上的操作有加、减、乘、除四则运算，还有模运算等。

定义数据类型的一个作用是，隐藏计算机硬件及其特性和差别，使硬件对于用户而言是透明的，即用户可以不关心数据类型是怎么实现的，但可以使用它；定义数据类型的另一个作用是，用户能够使用数据类型定义的操作，方便实现问题的求解。例如，用户可以使用Java语言定义int型的加法操作来完成两个整数的加法运算，而不用关心两个整数的加法在计算机中到底是如何实现的。这样不但加快了用户解决问题的速度，而且也使得用户可以在更高的层面上考虑问题。

与机器语言和汇编语言相比，高级语言的出现大大简化了程序设计。但是要将解答问题的步骤从非形式化的自然语言表达转换为形式化的高级语言表达，仍然是一个复杂的过程，需要做很多繁杂琐碎的事情，因而仍然需要抽象。对于一个明确的问题，要解答这个问题，总是先选用该问题的一个数据模型，接着弄清该问题所选用的数据模型在已知条件下的初始状态和要求的结果状态，以及隐含着的两个状态之间的关系。最后，探索从数据模型的已知初始状态出发，到达要求的结果状态所必需的运算步骤。

在探索运算步骤时，首先应该考虑顶层的运算步骤，然后考虑底层的运算步骤。所谓顶层的运算步骤，是指定义在数据模型上的运算步骤，也叫宏观运算步骤，它们组成解答问题步骤的主干部分。其中，涉及的数据是数据模型中的一个变量，暂时不关心它的数据结构；涉及的运算是以数据模型中的数据变量作为运算对象，或作为运算结果，或二者兼而为之，简称为定义在数据模型上的运算。由于暂时不关心变量的数据结构，所以这些运算都带有抽象性质，不含运算的细节。所谓底层的运算步骤，是指顶层抽象运算的具体实现，它们依赖于数据模型的结构，依赖于数据模型结构的具体表示。因此，底层的运算步骤包括两部分：一是数据模型的具体表示；二是定义在该数据模型上运算的具体实现。可以把这两部分理解为微观运算。所以，底层运算是顶层运算的细化，底层运算为顶层运算服务。为了将顶层算法与底层算法隔开，使二者在设计时不会互相牵制、互相影响，必须对二者的接口进行一次抽象。让底层只通过这个接口为顶层服务，顶层也只通过这个接口调用底层的运算，这个接口就是抽象数据类型。

抽象数据类型（Abstract Data Type，ADT）由一种数据模型和在该数据模型上的一组操作组成。抽象数据类型包括定义和实现两个方面，其中定义是独立于实现的。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部的实现无关，即无论它的内部结构如何变化，只要它的逻辑特性不变，都不会影响到它的使用。抽象数据类型内部的变化（抽象数据类型实现的变化）只是可能会对外部在使用它解决问题时的效率产生影响，因此，一个重要任务就是如何简单、高效地实现抽象数据类型。很明显，对于不同的运算组，为使组中所有运算的效率都尽可能地高，其相应的数据模型具体表示的选择将是不同的。从这个意义上说，数据模型的具体表示又依赖于数据模型上定义的那些运算。特别是当不同运算的效率互相制约时，必须事先将所有运算的相应使用频度进行排序，让所选择的数据模型的具体表示优先使用。一般来说，频度较高的运算有较高的效率。

由此可见，抽象数据类型的概念并不是全新的概念。抽象数据类型和数据类型在实质上是同一个概念，只不过抽象数据类型是对数据类型的进一步抽象，它不仅包括各种不同的计算机处理器中已经实现的数据类型，还包括为解决更为复杂的问题而由用户自定义的数据类型。例如高级语言都有的“整数”类型就是一种抽象数据类型，只不过高级语言中的整型已经实现了，并且实现的细节可能不同而已。人们没有意识到抽象数据类型的概念已经孕育在基本数据类型的概念之中，是因为人们已经习惯于在程序设计中使用基本数据类型和相关的运算，而没有做进一步深究而已。(www.xing528.com)

抽象数据类型一方面可以使使用它的用户只关心它的逻辑特性，而不需要了解它的实现方式；另一方面，可以使人们更容易描述现实世界，可以站在更高的层面上来考虑问题。例如，可以使用树来描述行政区划，使用图来描述通信网络。

根据抽象数据类型的概念对抽象数据类型进行定义，就是约定抽象数据类型的名称，同时约定在该类型上定义的一组运算的各个运算的名称，并明确各个运算分别有多少个参数、这些参数的含义和顺序，以及运算的功能。一旦定义清楚，人们在使用抽象数据类型时，就可以像引用基本数据类型那样简便，同时抽象数据类型的实现就有了设计的依据和目标。抽象数据类型的使用和实现都与抽象数据类型的定义有关，这样就使得使用与实现没有直接的联系。因此，只要严格按照定义，抽象数据类型的使用和实现就可以互相独立、互不影响，从而实现对它们的隔离，达到抽象的目的。

因此，抽象数据类型可以使用一个三元组来表示：

ADT=(D,S,P)

其中，D是数据对象；S是D上的关系集；P是加在D上的一组操作。当定义抽象数据类型时，可以使用以下格式：

其中，数据对象和数据关系的定义用伪码来描述，基本操作的定义格式为：