📄 chapter2.htm
字号:
<html><!-- #BeginTemplate "/Templates/article_template.dwt" -->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="keywords" content="algorithm, data structure, contest, programming, 算法, 数据结构, 程序设计, 竞赛">
<meta name="description" content="discussing the algorithm and data structure of computer programming, as well as all kinds of programming contest.">
<meta name="description" content="讨论程序设计的算法与数据结构，各类程序设计竞赛试题解析和参赛经验介绍。">
<!-- #BeginEditable "doctitle" -->
<title>算法表达中的抽象机制——抽象数据类型</title>
<!-- #EndEditable -->
<script id="header" language="JavaScript" src="../../lib/header.js"></script>
<!-- #BeginEditable "javascript" -->
<script language="JavaScript">
previous = "chapter1.htm";
next = "chapter3.htm";
contents="index.htm";
topic="算法表达中的抽象机制";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content">
<!-- #BeginEditable "MainContent" -->
<h2>抽象数据类型</h2>
<p>与机器语言、汇编语言相比，高级语言的出现大大地简便了程序设计。但算法从非形式的自然语言表达到形式化的高级语言表达，仍然是一个复杂的过程，仍然要做很多繁杂琐碎的事情，因而仍然需要抽象。</p>
<p><em>对于一个明确的数学问题，设计它的算法，总是先选用该问题的一个数据模型。接着，弄清该问题所选用的数据模型在已知条件下的初始状态和要求的结果状态，以及隐含着的两个状态之间的关系。然后探索从数据模型的已知初始状态出发到达要求的结果状态所必需的运算步骤。把这些运算步骤记录下来，就是该问题的求解算法。</em></p>
<p>按照自顶向下逐步求精的原则，我们在探索运算步骤时，首先应该考虑算法顶层的运算步骤，然后再考虑底层的运算步骤。所谓顶层的运算步骤是指定义在数据模型级上的运算步骤，或叫宏观运算。它们组成算法的主干部分。表达这部分算法的程序就是主程序。其中涉及的数据是数据模型中的一个变量，暂时不关心它的数据结构;涉及的运算以数据模型中的数据变量作为运算对象，或作为运算结果，或二者兼而为之，简称为定义在数据模型上的运算。由于暂时不关心变量的数据结构，这些运算都带有抽象性质，不含运算的细节。所谓底层的运算步骤是指顶层抽象的运算的具体实现。它们依赖于数据模型的结构，依赖于数据模型结构的具体表示。因此，底层的运算步骤包括两部分:一是数据模型的具体表示;二是定义在该数据模型上的运算的具体实现。我们可以把它们理解为微观运算。于是，底层运算是顶层运算的细化;底层运算为顶层运算服务。为了将顶层算法与底层算法隔开，使二者在设计时不会互相牵制、互相影响，必须对二者的接口进行一次抽象。让底层只通过这个接口为顶层服务，顶层也只通过这个接口调用底层的运算。这个接口就是<dfn>抽象数据类型</dfn>。其英文术语是<dfn><a name="ADT"></a>Abstract Data Types</dfn>，简记<ACRONYM title="Abstract Data Types">ADT</ACRONYM>。</p>
<p>抽象数据类型是算法设计和程序设计中的重要概念。严格地说，它是算法的一个数据模型连同定义在该模型上、作为该算法构件的一组运算。这个概念明确地把数据模型与作用在该模型上的运算紧密地联系起来。事实正是如此。一方面，如前面指出过的，数据模型上的运算依赖于数据模型的具体表示，因为数据模型上的运算以数据模型中的数据变量作为运算对象，或作为运算结果，或二者兼而为之;另方面，有了数据模型的具体表示，有了数据模型上运算的具体实现，运算的效率随之确定。于是，就有这样的一个问题:如何选择数据模型的具体表示使该模型上的各种运算的效率都尽可能地高?很明显，对于不同的运算组，为使组中所有运算的效率都尽可能地高，其相应的数据模型具体表示的选择将是不同的。在这个意义下，数据模型的具体表示又反过来依赖于数据模型上定义的那些运算。特别是，当不同运算的效率互相制约时，还必须事先将所有的运算的相应使用频度排序，让所选择的数据模型的具体表示优先保证使用频度较高的运算有较高的效率。数据模型与定义在该模型上的运算之间存在着的这种密不可分的联系，是抽象数据类型的概念产生的背景和依据。</p>
<p>应该指出，抽象数据类型的概念并不是全新的概念。它实际上是我们熟悉的基本数据类型概念的引伸和发展。用过高级语言进行算法设计和程序设计的人都知道，基本数据类型已隐含着数据模型和定义在该模型上的运算的统一，只是当时还没有形成抽象数据类型的概念罢了。事实上，大家都清楚，基本数据类型中的逻辑类型就是逻辑值数据模型和或(∨)、与(∧)、非(┐)三种逻辑运算的统一体；整数类型就是整数值数据模型和加(+)、减(-)、乘(*)、除(div)四种运算的统一体；实型和字符型等也类同。每一种基本类型都连带着一组基本运算。只是由于这些基本数据类型中的数据模型的具体表示和基本运算的具体实现都很规范，都可以通过内置(built-in)而隐蔽起来，使人们看不到它们的封装。许多人已习惯于在算法与程序设计中用基本数据类型名和相关的运算名，而不问其究竟。所以没有意识到抽象数据类型的概念已经孕育在基本数据类型的概念之中。</p>
<p>回到定义算法的顶层和底层的接口，即定义抽象数据类型。根据抽象数据类型的概念，对抽象数据类型进行定义就是约定抽象数据类型的名字，同时，约定在该类型上定义的一组运算的各个运算的名字，明确各个运算分别要有多少个参数，这些参数的含义和顺序，以及运算的功能。一旦定义清楚，算法的顶层就可以像引用基本数据类型那样，十分简便地引用抽象数据类型;同时，算法的底层就有了设计的依据和目标。顶层和底层都与抽象数据类型的定义打交道。顶层运算和底层运算没有直接的联系。因此，只要严格按照定义办，顶层算法的设计和底层算法的设计就可以互相独立，互不影响，实现对它们的隔离，达到抽象的目的。</p>
<p>在定义了抽象数据类型之后，算法底层的设计任务就可以明确为:</p>
<ol>
<li>赋每一个抽象数据类型名予具体的构造数据类型，或者说，赋每一个抽象数据类型名予具体的数据结构;</li>
<li>赋每一个抽象数据类型上的每个运算名予具体的运算内容，或者说，赋予具体的过程或函数。</li>
</ol>
<p>因此，落实下来，算法底层的设计就是数据结构的设计和过程与函数的设计。用高级语言表达，就是构造数据类型的定义和过程与函数的说明。</p>
<p>不言而喻，由于实际问题千奇百怪，数据模型千姿百态，问题求解的算法千变万化，抽象数据类型的设计和实现不可能像基本数据类型那样可以规范、内置、一劳永逸。它要求算法设计和程序设计人员因时因地制宜，自行筹划，目标是使抽象数据类型对外的整体效率尽可能地高。</p>
<p>下面用一个例子来说明，对于一个具体的问题，抽象数据类型是如何定义的。</p>
<p>考虑<a href="../../algorithm/index.html?commonalg/graph/connectivity/topo_sort.htm" target="_top">拓扑排序</a>问题:已知一个集合S={a<sub>1</sub>,a<sub>2</sub>,
... ,a<sub>m</sub>}，S上已规定了一个部分序<。要求给出S的一个线性序{a<sub>1</sub>',a<sub>2</sub>',
... ,a<sub>m</sub>'}，即S的一个重排，使得对于任意的1<=j<k<=m，不得有a<sub>k</sub>'<a<sub>j</sub>'。这里所谓S上的部分序<，是指S上的一种序关系，它对于S中的任意元素x,y和z，具有如下三个性质:</p>
<ol>
<li>不得有x<x；(反自反性）</li>
<li>若x<y，则不得有y<x；（反对称性）</li>
<li>若x<y，,且y<z，则x<z；(传递性)。</li>
</ol>
<p>其中x<y读作x先于y,或等价地读作x是y的前驱，或y是x是后继。</p>
<p>由于已知的S上的部分序<可以用一个有向图G来表示，而要求的S的线性序可以用一个队列Q来表示，所以问题的数据模型包括一类有向图和一类队列。我们将其分别取名为Digraph和Queue。其中G=G(V，E)是Digraph中的一个有向图，结点集V=S，有向边集E是由<决定的S的元素间的有向连线的全体;Q=S={a<sub>1</sub>,a<sub>2</sub>,
... ,a<sub>m</sub>}是Queue中的一个队列。在G中，a<sub>i</sub>和a<sub>j</sub>之间有一条起于a<sub>i</sub>止于a<sub>j</sub>的有向连线的充分必要条件是a<sub>i</sub><a<sub>j</sub>。具体地说，比如S={a<sub>1</sub>，a<sub>2</sub>,
... ,a<sub>10</sub>}，而<如表1-3所示，则G(V,E)如图1-7，而Q={a<sub>7</sub>，a<sub>9</sub>，a<sub>1</sub>，a<sub>2</sub>，a<sub>4</sub>，a<sub>6</sub>，a<sub>3</sub>，a<sub>5</sub>，a<sub>8</sub>，a<sub>10</sub>}。这个Q只是问题的一个解。显然问题的解不唯一，容易举出Q'={a<sub>1</sub>，a<sub>2</sub>，a<sub>7</sub>,a<sub>9</sub>，a<sub>10</sub>，a<sub>4</sub>，a<sub>6</sub>，a<sub>3</sub>，a<sub>5</sub>，a<sub>8</sub>}是另一个解。</p>
<p class="noindent" align="center"><img src="images/img2.gif" " width="395" height="285"></p>
<table width="95" border="1" align="center" bordercolorlight="#000000" bordercolordark="#000000" cellspacing="0">
<tr>
<td width="85">
<div align="center"> <font size="2">a<sub>1</sub><a<sub>2</sub></font>
</div>
</td>
</tr>
<tr>
<td width="85">
<div align="center"> <font size="2">a<sub>2</sub><a<sub>4</sub></font>
</div>
</td>
</tr>
<tr>
<td width="85">
<div align="center"> <font size="2">a<sub>4</sub><a<sub>6</sub></font>
</div>
</td>
</tr>
<tr>
<td width="85">
<div align="center"> <font size="2">a<sub>2</sub><a<sub>10</sub></font>
</div>
</td>
</tr>
<tr>
<td width="85">
<div align="center"> <font size="2">a<sub>4</sub><a<sub>8</sub></font>
</div>
</td>
</tr>
<tr>
<td width="85">
<div align="center"> <font size="2">a<sub>6</sub><a<sub>3</sub></font>
</div>
</td>
</tr>
<tr>
<td width="85">
<div align="center"> <font size="2">a<sub>1</sub><a<sub>3</sub></font>
</div>
</td>
</tr>
<tr>
<td width="85">
<div align="center"> <font size="2">a<sub>3</sub><a<sub>5</sub></font>
</div>
</td>
</tr>
<tr>
<td width="85">
<div align="center"> <font size="2">a<sub>5</sub><a<sub>8</sub></font>
</div>
</td>
</tr>
<tr>
<td width="85">
<div align="center"> <font size="2">a<sub>7</sub><a<sub>5</sub></font>
</div>
</td>
</tr>
<tr>
<td width="85">
<div align="center"> <font size="2">a<sub>7</sub><a<sub>9</sub></font>
</div>
</td>
</tr>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -