算法表达中的抽象机制（二）

todaytomo 2007-01-18

展开全文

抽象数据类型

与机器语言、汇编语言相比，高级语言的出现大大地简便了程序设计。但算法从非形式的自然语言表达到形式化的高级语言表达，仍然是一个复杂的过程，仍然要做很多繁杂琐碎的事情，因而仍然需要抽象。

对于一个明确的数学问题，设计它的算法，总是先选用该问题的一个数据模型。接着，弄清该问题所选用的数据模型在已知条件下的初始状态和要求的结果状态，以及隐含着的两个状态之间的关系。然后探索从数据模型的已知初始状态出发到达要求的结果状态所必需的运算步骤。把这些运算步骤记录下来，就是该问题的求解算法。

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

抽象数据类型是算法设计和程序设计中的重要概念。严格地说，它是算法的一个数据模型连同定义在该模型上、作为该算法构件的一组运算。这个概念明确地把数据模型与作用在该模型上的运算紧密地联系起来。事实正是如此。一方面，如前面指出过的，数据模型上的运算依赖于数据模型的具体表示，因为数据模型上的运算以数据模型中的数据变量作为运算对象，或作为运算结果，或二者兼而为之;另方面，有了数据模型的具体表示，有了数据模型上运算的具体实现，运算的效率随之确定。于是，就有这样的一个问题:如何选择数据模型的具体表示使该模型上的各种运算的效率都尽可能地高?很明显，对于不同的运算组，为使组中所有运算的效率都尽可能地高，其相应的数据模型具体表示的选择将是不同的。在这个意义下，数据模型的具体表示又反过来依赖于数据模型上定义的那些运算。特别是，当不同运算的效率互相制约时，还必须事先将所有的运算的相应使用频度排序，让所选择的数据模型的具体表示优先保证使用频度较高的运算有较高的效率。数据模型与定义在该模型上的运算之间存在着的这种密不可分的联系，是抽象数据类型的概念产生的背景和依据。

应该指出，抽象数据类型的概念并不是全新的概念。它实际上是我们熟悉的基本数据类型概念的引伸和发展。用过高级语言进行算法设计和程序设计的人都知道，基本数据类型已隐含着数据模型和定义在该模型上的运算的统一，只是当时还没有形成抽象数据类型的概念罢了。事实上，大家都清楚，基本数据类型中的逻辑类型就是逻辑值数据模型和或(∨)、与(∧)、非(┐)三种逻辑运算的统一体；整数类型就是整数值数据模型和加(+)、减(-)、乘(*)、除(div)四种运算的统一体；实型和字符型等也类同。每一种基本类型都连带着一组基本运算。只是由于这些基本数据类型中的数据模型的具体表示和基本运算的具体实现都很规范，都可以通过内置(built-in)而隐蔽起来，使人们看不到它们的封装。许多人已习惯于在算法与程序设计中用基本数据类型名和相关的运算名，而不问其究竟。所以没有意识到抽象数据类型的概念已经孕育在基本数据类型的概念之中。

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

在定义了抽象数据类型之后，算法底层的设计任务就可以明确为:

赋每一个抽象数据类型名予具体的构造数据类型，或者说，赋每一个抽象数据类型名予具体的数据结构;
赋每一个抽象数据类型上的每个运算名予具体的运算内容，或者说，赋予具体的过程或函数。

因此，落实下来，算法底层的设计就是数据结构的设计和过程与函数的设计。用高级语言表达，就是构造数据类型的定义和过程与函数的说明。

不言而喻，由于实际问题千奇百怪，数据模型千姿百态，问题求解的算法千变万化，抽象数据类型的设计和实现不可能像基本数据类型那样可以规范、内置、一劳永逸。它要求算法设计和程序设计人员因时因地制宜，自行筹划，目标是使抽象数据类型对外的整体效率尽可能地高。

下面用一个例子来说明，对于一个具体的问题，抽象数据类型是如何定义的。

考虑拓扑排序问题:已知一个集合S={a₁,a₂, ... ,a_m}，S上已规定了一个部分序<。要求给出S的一个线性序{a₁‘,a₂‘, ... ,a_m‘}，即S的一个重排，使得对于任意的1<=j<k<=m，不得有a_k‘<a_j‘。这里所谓S上的部分序<，是指S上的一种序关系，它对于S中的任意元素x,y和z，具有如下三个性质:

不得有x<x；(反自反性）
若x<y，则不得有y<x；（反对称性）
若x<y，,且y<z，则x<z；(传递性)。

其中x<y读作x先于y,或等价地读作x是y的前驱，或y是x是后继。

由于已知的S上的部分序<可以用一个有向图G来表示，而要求的S的线性序可以用一个队列Q来表示，所以问题的数据模型包括一类有向图和一类队列。我们将其分别取名为Digraph和Queue。其中G=G(V，E)是Digraph中的一个有向图，结点集V=S，有向边集E是由<决定的S的元素间的有向连线的全体;Q=S={a₁,a₂, ... ,a_m}是Queue中的一个队列。在G中，a_i和a_j之间有一条起于a_i止于a_j的有向连线的充分必要条件是a_i<a_j。具体地说，比如S={a₁，a₂, ... ,a₁₀}，而<如表1-3所示，则G(V,E)如图1-7，而Q={a₇，a₉，a₁，a₂，a₄，a₆，a₃，a₅，a₈，a₁₀}。这个Q只是问题的一个解。显然问题的解不唯一，容易举出Q‘={a₁，a₂，a₇,a₉，a₁₀，a₄，a₆，a₃，a₅，a₈}是另一个解。

a₁<a₂

a₂<a₄

a₄<a₆

a₂<a₁₀

a₄<a₈

a₆<a₃

a₁<a₃

a₃<a₅

a₅<a₈

a₇<a₅

a₇<a₉

a₉<a₄

a₉<a₁₀

表1-3 S={a₁,a_2,...,a₁₀}中的部分序

在数据模型Digraph和Queue的基础上，容易拟定出算法高层的宏观运算步骤，我们称之为算法的主干部分，并用非形式的自然语言表述如下：

1.φ->Q;

2.检测G。

(1)当G≠φ时;

①在G中出任意一个无前驱的结点，记为a；

②将a加到Q的末尾;

③在G中删去结点a以及以a为起点的所有有向边;

④转向2。

(2)当C=φ时，算法结束，问题的解在Q中。

用高级语言中的控制结构语句成分，替换上述主干算法中自然语言的控制转移术语，则主干算法可用自然语言和高级语言的混合语言改述如下:

φ->Q;
while G≠φ do
begin
a:=G中任意一个无前驱的顶点;
将a加到Q的末尾; 从G中删去结点a以及以a为起点的所有有向边;
end;

我们看到，其中那些还未能用高级语言表达的语句或语句成分，正是算法需要定义在数据模型Digraph和Queue上的运算。现分别将它们列出。

对于Digraph中的G:

检测G是否非空图;
在G中找任意一个无前驱的结点;
在G中删去一个无前驱的结点，以及以该结点为起点的所有有向边。

对于Queue中的Q:

初始化Q为空队列;
将一个结点加到Q的末尾。

如果还考虑到已知G的初始状态如何由输入形成和Q的结果状态的输出，那么，对于Digraph和Queue还需要补充定义若干有关的运算。为了简单，这里从略。

由于高级语言为抽象数据类型的定义提供了很好的环境和工具，再复杂的数据模型都可以通过构造数据类型来表达，再复杂的运算都可以借助过程或函数来描述。因此，上述由数据模型和数据模型上定义的运算综合起来的抽象数据类型很容易用高级语言来定义。

对于抽象数据类型mgraph，定义如下三个运算:

(l)function G_empty(G:Digraph):boolean;

{检测图G是否非空。如果G=φ，则函数返回true，否则返回false}

(2)function G_front(G:Digraph):nodetype；

{在有向图G中找一个无前驱的结点。nodetype是结点类型名，它有待用户定义，下同}

(3)Procedure delete_G_front(var G:Digraph;a:nodetype);

{在G中删去结点a以及以a为起点的所有有向边}

对抽象数据类型Queue，定义如下两个运算:

(l)Procedure init_Q(var Q:Queue); {初始化队列Q为空队列}

(2)Procedure add_Q_rear(a:nodetype;var Q:Queue) {将结点a加到队列Q的末尾}

这样，我们便定义了ADT Digraph和ADT Queue。

有了抽象数据类型Digraph和Queue的上述定义，拓扑排序问题的主干算法即可完全由高级语言表达成主程序。

Program topsort(input，ouput);
type
nodetype=…
Digraph=…
Queue=…
Function G_empty(G:Digraph):boolean;
...
Function G_front(G:Dlgraph):nodetype;
...
Procedure delete_G_front(var G:Digraph;a:nodetype);
...
Procedure init_Q(var Q:Queue);
...
Procedure add_Q_rear(a:nodetype;var Q:Queue);
...
var
a:nodetype;
G:Digraph;
Q:Queue;
begin
…       {输入并形成G的初始状态即拓扑排序前的状态}
init_Q(Q);
while not G_empty(G) do
begin
a:=G_front(G);
add_Q_rear(a，Q);
delete_G_front(G，a);
end;
…
{输出Q中的结果}
end;

为了简明，我们在其中略去了输入、拓扑排序前G的状态的形成和结果输出三个部分。至于构造数据类型nodetype，Digraph和Queue的表示，函数G_empty，G_front，过程delete_G_front，init_Q和add_Q_rear等的实现，则留待算法的底层设计去完成。需要指出的是，nodetype通常用记录表示，而Digraph和Queue都有多种表示方式。因而G_empty，G_front，delete_G_front，init_Q和add_Q_rear也有多种的实现方式。

但是，只要抽象数据类型Digraph和Queue的定义不变，不管上述构造数据类型的表示和过程与函数的实现如何改变，主程序的表达都不会改变;反过来，不管主程序在哪里调用抽象数据类型上的函数或过程，上述构造数据类型的表示和过程与函数的实现都不必改变。算法顶层的设计与底层的设计之间的这种独立性，显然得益于抽象数据类型的引人。而这种独立性给算法和程序设计带来了许多好处。

使用抽象数据类型带来的好处

使用抽象数据类型将给算法和程序设计带来很多好处，其中主要的有下面几条。

算法顶层的设计与底层的设计被隔开，使得在进行顶层设计时不必考虑它所用到的数据和运算分别如何表示和实现;反过来，在进行数据表示和运算实现等底层设计时，只要抽象数据类型定义清楚，也不必考虑它在什么场合被引用。这样做，算法和程序设计的复杂性降低了，条理性增强了。既有助于迅速开发出程序的原型，又有助于在开发过程中少出差错，保证编出的程序有较高的可靠性。
算法设计与数据结构设计隔开，允许数据结构自由选择，从中比较，可优化算法和提高程序运行的效率。
数据模型和该模型上的运算统一一在抽象数据类型中，反映了它们之间内在的互相依赖和互相制约的关系，便于空间和时间耗费的折衷，满足用户的要求。
由于顶层设计和底层设计被局部化，在设计中，如果出现差错，将是局部的，因而容易查我也容易纠正。在设计中常常要做的增、删、改也都是局部的，因而也都很容易进行。因此，可以肯定，用抽象数据类型表述的程序具有很好的可维护性。
编出来的程序自然地呈现模块化，而且，抽象的数据类型的表示和实现都可以封装起来，便于移植和重用。
为自顶向下逐步求精和模块化提供一种有效的途径和工具。
编出来的程序结构清晰，层次分明，便于程序正确性的证明和复杂性的分析。

数据结构、数据类型和抽象数据类型

数据结构、数据类型和抽象数据类型，这三个术语在字面上既不同又相近，反映出它们在含义上既有区别又有联系。

数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由哪些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，物理上的数据结构反映成分数据在计算机内的存储安排。数据结构是数据存在的形式。

数据是按照数据结构分类的，具有相同数据结构的数据属同一类。同一类数据的全体称为一个数据类型。在程序设计高级语言中，数据类型用来说明一个数据在数据分类中的归属。它是数据的一种属性。这个属性限定了该数据的变化范围。为了解题的需要，根据数据结构的种类，高级语言定义了一系列的数据类型。不同的高级语言所定义的数据类型不尽相同。Pascal语言所定义的数据类型的种类如图1-8所示。

其中，简单数据类型对应于简单的数据结构;构造数据类型对应于复杂的数据结构;在复杂的数据结构里，允许成分数据本身具有复杂的数据结构，因而，构造数据类型允许复合嵌套;指针类型对应于数据结构中成分数据之间的关系，表面上属简单数据类型，实际上都指向复杂的成分数据即构造数据类型中的数据，因此这里没有把它划入简单数据类型，也没有划入构造数据类型，而单独划出一类。

数据结构反映数据内部的构成方式，它常常用一个结构图来描述:数据中的每一项成分数据被看作一个结点，并用方框或圆圈表示，成分数据之间的关系用相应的结点之间带箭号的连线表示。如果成分数据本身又有它自身的结构，则结构出现嵌套。这里嵌套还允许是递归的嵌套。

由于指针数据的引入，使构造各种复杂的数据结构成为可能。按数据结构中的成分数据之间的关系，数据结构有线性与非线性之分。在非线性数据结构中又有层次与网状之分。由于数据类型是按照数据结构划分的，因此，一类数据结构对应着一种数据类型。数据类型按照该类型中的数据所呈现的结构也有线性与非线性之分，层次与网状之分。一个数据变量，在高级语言中的类型说明必须是读变量所具有的数据结构所对应的数据类型。

最常用的数据结构是数组结构和记录结构。数组结构的特点是：

成分数据的个数固定，它们之间的逻辑关系由成分数据的序号(或叫数组的下标)来体现。这些成分数据按照序号的先后顺序一个挨一个地排列起来。
每一个成分数据具有相同的结构(可以是简单结构，也可以是复杂结构)，因而属于同一个数据类型(相应地是简单数据类型或构造数据类型)。这种同一的数据类型称为基类型。
所有的成分数据被依序安排在一片连续的存储单元中。

概括起来，数组结构是一个线性的、均匀的、其成分数据可随机访问的结构。由于这种结构有这些良好的特性，所以最常被人们所采用。在高级语言中，与数组结构相对应的数据类型是数组类型，即数组结构的数据变量必须说明为array [i] of T₀，其中i是数组结构的下标类型，而T₀是数组结构的基类型。

记录结构是另一种常用的数据结构。它的特点是:

与数组结构一样，成分数据的个数固定。但成分数据之间没有自然序，它们处于平等地位。每一个成分数据被称为一个域并赋予域名。不同的域有不同的域名。
不同的域允许有不同的结构，因而允许属于不同的数据类型。
与数组结构一样，它们可以随机访问，但访问的途径靠的是域名。

在高级语言中记录结构对应的数据类型是记录类型。记录结构的数据的变量必须说明为记录类型。

抽象数据类型的含义在上一段已作了专门叙述。它可理解为数据类型的进一步抽象。即把数据类型和数据类型上的运算捆在一起，进行封装。引入抽象数据类型的目的是把数据类型的表示和数据类型上运算的实现与这些数据类型和运算在程序中的引用隔开，使它们相互独立。对于抽象数据类型的描述，除了必须描述它的数据结构外，还必须描述定义在它上面的运算(过程或函数)。抽象数据类型上定义的过程和函数以该抽象数据类型的数据所应具有的数据结构为基础。