|
|
抽象数据类型
(abstract data type 简称adt)
是指一个数学模型以及定义在此数学模型上的一组操作。
抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。
抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类型。
抽象数据类型的描述包括给出抽象数据类型的名称、数据的集合、数据之间的关系和操作的集合等方面的描述。抽象数据类型的设计者根据这些描述给出操作的具体实现，抽象数据类型的使用者依据这些描述使用抽象数据类型。
抽象数据类型描述的一般形式如下：
adt 抽象数据类型名称 {
数据对象：
……
数据关系：
……
操作集合：
操作名1：
……
……
操作名n：
}adt抽象数据类型名称
抽象数据类型定义（adt）
作用：抽象数据类型可以使我们更容易描述现实世界。例：用线性表描述学生成绩表，用树或图描述遗传关系。
定义：一个数学模型以及定义在该模型上的一组操作。
关键：使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。
例：线性表这样的抽象数据类型，其数学模型是：数据元素的集合，该集合内的元素有这样的关系：除第一个和最后一个外，每个元素有唯一的前趋和唯一的后继。可以有这样一些操作：插入一个元素、删除一个元素等。 |
|
抽象数据类型
abstract data type
ChouxiQng shUjU leixing
抽象数据类型(abstract data勺pe)与表示
无关的数据类型。数据类型由一个对象集合(值集)
和在该集合上定义的若干合法运算所组成的运算集
合组成。抽象数据类型用数学方法定义对象集合和
运算集合，仅通过运算的性质刻画数据对象，而独立
于计算机中可能的表示方法。其目的在于隐蔽运算
实现细节和内部数据结构，同时向用户提供该数据
类型的完整信息。
抽象数据类型的概念是逐步形成的。60年代
末到70年代，人们将用户自定义的类型称作抽象数
据类型。传统的算法语言没有用户自定义类型的设
施。到60年代末，为了实现算法细节和数据内部结
构的隐蔽，SIMIJLA67语言中引人了类，随后出现
了模块概念。模块可分成模块式和模块体，模块式
定义外部可见的运算接口，模块体对外不可见，其中
可定义私有的数据结构和运算。通过接口和实现的
分离，模块提供了用户自定义类型的手段，达到数据
抽象、信息隐蔽的目的。在这个意义下，模块所定义
的数据类型称作抽象数据类型。实际上，模块提供
了一种抽象数据类型实现的手段。这种手段在
入玉月ula-2，八da等语言中得到进一步的完善和发展。
用户自定义数据类型的另一优点是设计与实现相分
离，可将模块式看作设计规约，而模块体是相应的实
现。这种分离推动了软件规约的研究，也进一步推
动了抽象数据类型的研究。
当用一个数据类型去模拟一类客观对象时，可
先给出该类型的性质和功能的描述，然后用已有的
语言设施和数据类型实现所需的功能，并证明实现
的正确性。仅通过模块式描述数据类型的型构是不
够的，还必须用抽象的方法完整地描述对象的性态
和功能。这就是用抽象数据类型表示功能规约。这
时，抽象数据类型完全独立于具体表示，反映出纯抽
象的性质。抽象数据类型的规约方法主要有二:其
一是代数方法;其二是模型方法。代数方法基于G.
Birkhoff，J .D.LipSOn等的异调代数理论，经5.21115，
J.A.Guttag等人的发展，其理论基础日趋完善，并逐
步应用于软件工程实践，成为有代表性的抽象数据
类型规约方法。模型方法基于C.A.R.HOare的前
后断言方法，它通过已定义的(抽象)数据类型来给
出所要定义的新类型的抽象模型。
采用代数方法，抽象数据类型的规约由两部分
组成，一是语法部分，二是公理部分。语法部分给出
了抽象数据类型的名及其上运算的定义域和值域，
公理部分则通过给出一组刻画各运算之间相互关系
的方程来定义各运算的含义。从语义的角度，代数
规约的语义是一类代数。在语法正确的基础上，语
义正确性是指相应代数满足规约中公理部分的所有
公理。通常，具语义正确性的语义模型代数有多个 |
|
- : abstract data type
|
|
|