数据结构

b · 发表于 2004-5-29 04:02:38

<H1>
<H1>数据结构 DATA STRUCTURE</H1>
<TABLE width="100%" border=0>

<TR>
<TD vAlign=top width="17%"><IMG src="http://algorithm.myrice.com/images/netwrkprotcl.gif"></TD>
<TD width="83%">
<

>数据结构是信息的组织方式。对于相同的算法，用不同的数据结构表示其中的抽象数据类型会造成不同的执行效率。这就有必要研究各种抽象数据类型用不同的数据结构表示的效率差异，以及其适用场合。 
<

>在这里您可以了解到：
<UL>
<LI><a href="http://algorithm.myrice.com/datastructure/defination.html" target="_blank" >数据结构定义</A>
<LI><a href="http://algorithm.myrice.com/datastructure/ADT/index.htm" target="_blank" >算法表达中抽象机制</A>
<LI><a href="http://algorithm.myrice.com/datastructure/basic/index.html" target="_blank" >常用抽象数据类型 </A>
<LI><a href="http://algorithm.myrice.com/datastructure/ADVANCED/index.html" target="_blank" >高级抽象数据类型 </A></LI></UL></TD></TR></TABLE></H1>

b · 发表于 2004-5-29 04:06:42

<H2>何谓数据结构</H2>
<

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

>数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。 
<H2>数据结构主要研究什么？</H2>
<

>数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。
<H2>什么是数据结构？什么是逻辑结构和物理结构？</H2>
<DFN>数据</DFN>是指由有限的符号（比如，"0"和"1"，具有其自己的结构、操作、和相应的语义）组成的元素的集合。<DFN>结构</DFN>是元素之间的关系的集合。通常来说，一个<DFN>数据结构DS</DFN> 可以表示为一个二元组：
DS=(D,S), //i.e., data-structure=(data-part,logic-structure-part)
这里D是数据元素的集合（或者是“结点”，可能还含有“数据项”或“数据域”），S是定义在D（或其他集合）上的关系的集合，S = { R | R : D×D×...}，称之为元素的<DFN>逻辑结构</DFN>。
逻辑结构有四种基本类型：集合结构、线性结构、树状结构和网络结构。<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter1.htm" target="_blank" >表</A>和<a href="http://algorithm.myrice.com/datastructure/basic/tree/chapter1.htm" target="_blank" >树</A>是最常用的两种高效数据结构，许多高效的算法可以用这两种数据结构来设计实现。<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter1.htm" target="_blank" >表</A>是线性结构的（全序关系），<a href="http://algorithm.myrice.com/datastructure/basic/tree/chapter1.htm" target="_blank" >树</A>(偏序或层次关系)和<a href="http://algorithm.myrice.com/datastructure/basic/graph/chapter1.htm" target="_blank" >图</A>（局部有序(weak/local orders)）是非线性结构。
数据结构的物理结构是指逻辑结构的存储镜像(image)。数据结构 DS 的物理结构 P 对应于从 DS 的数据元素到存储区M（维护着逻辑结构S）的一个映射：
P

D,S) --> M
存储器模型：一个存储器 M 是一系列固定大小的存储单元，每个单元 U 有一个唯一的地址 A(U)，该地址被连续地编码。每个单元 U 有一个唯一的后继单元 U'=succ(U)。
P 的四种基本映射模型：顺序（sequential）、链接（linked）、索引（indexed）和散列（hashing）映射。
因此，我们至少可以得到4×4种可能的物理数据结构：
<TABLE cellSpacing=0 cellPadding=0 width=284 border=1>

<TR>
<TD width=93> 
<DIV align=center>sequential</DIV></TD>
<TD align=right width=102>
<DIV align=center>(sets)</DIV></TD></TR>
<TR>
<TD width=93> 
<DIV align=center>linked</DIV></TD>
<TD align=right width=102>
<DIV align=center>lists</DIV></TD></TR>
<TR>
<TD width=93> 
<DIV align=center>indexed</DIV></TD>
<TD align=right width=102>
<DIV align=center>trees</DIV></TD></TR>
<TR>
<TD width=93> 
<DIV align=center>hash</DIV></TD>
<TD align=right width=102>
<DIV align=center>graphs</DIV></TD></TR></TABLE>
（并不是所有的可能组合都合理）
数据结构DS上的操作：所有的定义在DS上的操作在改变数据元素（节点）或节点的域时必须保持DS的逻辑和物理结构。
DS上的基本操作：任何其他对DS的高级操作都可以用这些基本操作来实现。最好将DS和他的所有基本操作看作一个整体——称之为<DFN>模块</DFN>。我们可以进一步将该模块抽象为数据类型（其中DS的存储结构被表示为私有成员，基本操作被表示为公共方法），称之为<ACRONYM title="Abstract Data Type">ADT</ACRONYM>。作为ADT，堆栈和队列都是一种特殊的表，他们拥有表的操作的子集。
对于DATs的高级操作可以被设计为（不封装的）算法，利用基本操作对DS进行处理。
好的和坏的DS：如果一个DS可以通过某种“线性规则”被转化为线性的DS（例如线性表），则称它为好的DS。好的DS通常对应于好的（高效的）算法。这是由计算机的计算能力决定的，因为计算机本质上只能存取逻辑连续的内存单元，因此如何没有线性化的结构逻辑上是不可计算的。比如对一个图进行操作，要访问图的所有结点，则必须按照某种顺序来依次访问所有节点（要形成一个偏序），必须通过某种方式将图固有的非线性结构转化为线性结构才能对图进行操作。
<a href="http://algorithm.myrice.com/datastructure/basic/tree/chapter1.htm" target="_blank" >树</A>是好的DS——它有非常简单而高效的线性化规则，因此可以利用树设计出许多非常高效的算法。树的实现和使用都很简单，但可以解决大量特殊的复杂问题，因此树是实际编程中最重要和最有用的一种数据结构。树的结构本质上有递归的性质——每一个叶节点可以被一棵子树所替代，反之亦然。实际上，每一种递归的结构都可以被转化为（或等价于）树形结构。

b · 发表于 2004-5-29 04:07:31

<H2>计算机中数据的描述方式</H2><

>我们知道，数据可以用不同的形式进行描述或存储在计算机存储器中。最常见的数据描述方法有：公式化描述、链接描述、间接寻址和模拟指针。<UL><LI>公式化描述借助数学公式来确定元素表中的每个元素分别存储在何处，也就通过公式计算元素的存储器地址。最简单的情形就是把所有元素依次连续存储在一片连续的存储空间中，这就是通常所说的连续线性表，即数组。复杂一点的情形是利用复杂的函数关系根据元素的某些特征来计算元素在内存中的位置，这种技术称为散列技术(Hash，经常音译为哈希技术)。 <LI>在链接描述中，元素表中的每个元素可以存储在存储器的不同区域中，每个元素都包含一个指向下一个元素的指针。这就是通常所说的<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter3_2.htm" target="_blank" >链表</A>。这种描述方法的好处是，知道了第一个元素的位置，就可以依次找到第n个元素的位置，而且在其中插入元素非常方便，缺点是查找某个元素要遍历所有在该元素之前的元素，实际应用中经常和公式化描述结合起来使用。 <LI>在间接寻址方式中，元素表中的每个元素也可以存储在存储器的不同区域中，不同的是，此时必须保存一张表，该表的第i项指向元素表中的第i个元素，所以这张表是一个用来存储元素地址的表。指针数组（元素为指针的数组）就是这种描述法的应用。这种描述方法是公式化描述和链接描述的一种折衷方案，同时具有两种描述方法的优点，但是需要额外的内存开销。 <LI>模拟指针非常类似于链接描述，区别在于它用整数代替了指针，整数所扮演的角色与指针所扮演的角色完全相同。模拟指针的描述方式是链接描述和公式化描述的结合，元素被存储在不同的区域中，每个元素包含一个指示下一个元素位置的整数，可以通过某种公式由该整数计算出下一个元素的存储器地址。<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter3_3.htm" target="_blank" >线性表的游标实现</A>就是模拟指针描述法.</LI></UL>

b · 发表于 2004-5-29 04:07:45

<H1>算法表达中的抽象机制</H1><

>傅清祥王晓东
<CITE>算法与数据结构</CITE> , 电子工业出版社,1998<

>摘要<

>本文介绍了算法表达中的抽象机制，引入了抽象数据类型ADT的概念，提供一种相应的自顶向下逐步求精、模块化的程序设计方法，即运用抽象数据类型来描述程序的方法。目录<UL><LI><a href="http://algorithm.myrice.com/datastructure/ADT/introduction.htm" target="_blank" >简介</A> <LI><a href="http://algorithm.myrice.com/datastructure/ADT/chapter1.htm" target="_blank" >从机器语言到高级语言的抽象</A> <LI><a href="http://algorithm.myrice.com/datastructure/ADT/chapter2.htm" target="_blank" >抽象数据类型</A> <LI><a href="http://algorithm.myrice.com/datastructure/ADT/chapter3.htm" target="_blank" >使用抽象数据类型带来的好处</A> <LI><a href="http://algorithm.myrice.com/datastructure/ADT/chapter4.htm" target="_blank" >数据结构、数据类型和抽象数据类型</A> </LI></UL>

b · 发表于 2004-5-29 04:08:09

<H2>简介</H2><

>要用计算机解决一个稍为复杂的实际问题，大体都要经历如下的步骤。<OL><LI>将实际问题数学化，即把实际问题抽象为一个带有一般性的数学问题。这一步要引入一些数学概念，精确地阐述数学问题，弄清问题的已知条件、所要求的结果、以及在已知条件和所要求的结果之间存在着的隐式或显式的联系。 <LI>对于确定的数学问题，设计其求解的方法，即所谓的算法设计。这一步要建立问题的求解模型，即确定问题的数据模型并在此模型上定义一组运算，然后借助于对这组运算的调用和控制，从已知数据出发导向所要求的结果，形成算法并用自然语言来表述。这种语言还不是程序设计语言，不能被计算机所接受。 <LI>用计算机上的一种程序设计语言来表达已设计好的算法。换句话说，将非形式自然语言表达的算法转变为一种程序设计语言表达的算法。这一步叫程序设计或程序编制。 <LI>在计算机上编辑、调试和测试编制好的程序，直到输出所要求的结果。 </LI></OL><

>在这里，我们只关心第3步，而且把注意力集中在算法程序表达的抽象机制上，目的是引人一个重要的概念--抽象数据类型，同时为大型程序设计提供一种相应的自顶向下逐步求精、模块化的具体方法，即运用抽象数据类型来描述程序的方法。

b · 发表于 2004-5-29 04:08:27

<H2>从机器语言到高级语言的抽象</H2>
<

>我们知道，算法被定义为一个运算序列。这个运算序列中的所有运算定义在一类特定的数据模型上，并以解决一类特定问题为目标。这个运算序列应该具备下列四个特征。
<OL>
<LI>有限性，即序列的项数有限，且每一运算项都可在有限的时间内完成;
<LI>确定性，即序列的每一项运算都有明确的定义，无二义性;
<LI>可以没有输入运算项，但一定要有输出运算项;
<LI>可行性，即对于任意给定的合法的输入都能得到相应的正确的输出。 </LI></OL>
<

>这些特征可以用来判别一个确定的运算序列是否称得上是一个算法。
<

>但是，我们现在的问题不是要判别一个确定的运算序列是否称得上是一个算法，而是要对一个己经称得上是算法的运算序列，回顾我们曾经如何用程序设计语言去表达它。
算法的程序表达，归根到底是算法要素的程序表达，因为一旦算法的每一项要素都用程序清楚地表达，整个算法的程序表达也就不成问题。
作为运算序列的算法，有三个要素。
<OL>
<LI>作为运算序列中各种运算的运算对象和运算结果的数据;
<LI>运算序列中的各种运算;
<LI>运算序列中的控制转移。 </LI></OL>
这三种要素依序分别简称为<DFN>数据</DFN>、<DFN>运算</DFN>和<DFN>控制</DFN>。
由于算法层出不穷，变化万千，其中的运算所作用的对象数据和所得到的结果数据名目繁多，不胜枚举。最简单最基本的有布尔值数据、字符数据、整数和实数数据等;稍复杂的有向量、矩阵、记录等数据;更复杂的有集合、树和图，还有声音、图形、图像等数据。
同样由于算法层出不穷，变化万千，其中运算的种类五花八门、多姿多彩。最基本最初等的有赋值运算、算术运算、逻辑运算和关系运算等;稍复杂的有算术表达式和逻辑表达式等;更复杂的有函数值计算、向量运算、矩阵运算、集合运算，以及表、栈、队列、树和图上的运算等:此外，还可能有以上列举的运算的复合和嵌套。
关于控制转移，相对单纯。在串行计算中，它只有顺序、分支、循环、递归和无条件转移等几种。
我们来回顾一下，自从计算机问世以来，算法的上述三要素的程序表达，经历过一个怎样的过程。
最早的程序设计语言是机器语言，即具体的计算机上的一个指令集。当时，要在计算机上运行的所有算法都必须直接用机器语言来表达，计算机才能接受。算法的运算序列包括运算对象和运算结果都必须转换为指令序列。其中的每一条指令都以编码(指令码和地址码)的形式出现。与算法语言表达的算法，相差十万八千里。对于没受过程序设计专门训练的人来说，一份程序恰似一份"天书"，让人看了不知所云，可读性极差。
用机器语言表达算法的运算、数据和控制十分繁杂琐碎，因为机器语言所提供的指令太初等、原始。机器语言只接受算术运算、按位逻辑运算和数的大小比较运算等。对于稍复杂的运算，都必须一一分解，直到到达最初等的运算才能用相应的指令替代之。机器语言能直接表达的数据只有最原始的位、字节、和字三种。算法中即使是最简单的数据如布尔值、字符、整数、和实数，也必须一一地映射到位、字节和字中，还得一一分配它们的存储单元。对于算法中有结构的数据的表达则要麻烦得多。机器语言所提供的控制转移指令也只有无条件转移、条件转移、进入子程序和从子程序返回等最基本的几种。用它们来构造循环、形成分支、调用函数和过程得事先做许多的准备，还得靠许多的技巧。
直接用机器语言表达算法有许多缺点。
<OL>
<LI>大量繁杂琐碎的细节牵制着程序员，使他们不可能有更多的时间和精力去从事创造性的劳动，执行对他们来说更为重要的任务。如确保程序的正确性、高效性。
<LI>程序员既要驾驭程序设计的全局又要深入每一个局部直到实现的细节，即使智力超群的程序员也常常会顾此失彼，屡出差错，因而所编出的程序可靠性差，且开发周期长。
<LI>由于用机器语言进行程序设计的思维和表达方式与人们的习惯大相径庭，只有经过较长时间职业训练的程序员才能胜任，使得程序设计曲高和寡。
<LI>因为它的书面形式全是"密"码，所以可读性差，不便于交流与合作。
<LI>因为它严重地依赖于具体的计算机，所以可移植性差，重用性差。 </LI></OL>
这些弊端造成当时的计算机应用未能迅速得到推广。
克服上述缺点的出路在于程序设计语言的抽象，让它尽可能地接近于算法语言。
为此，人们首先注意到的是可读性和可移植性，因为它们相对地容易通过抽象而得到改善。于是，很快就出现汇编语言。这种语言对机器语言的抽象，首先表现在将机器语言的每一条指令符号化:指令码代之以记忆符号，地址码代之以符号地址，使得其含义显现在符号上而不再隐藏在编码中，可让人望"文"生义。其次表现在这种语言摆脱了具体计算机的限制，可在不同指令集的计算机上运行，只要该计算机配上汇编语言的一个汇编程序。这无疑是机器语言朝算法语言靠拢迈出的一步。但是，它离算法语言还太远，以致程序员还不能从分解算法的数据、运算和控制到汇编才能直接表达的指令等繁杂琐碎的事务中解脱出来。
到了50年代中期，出现程序设计的高级语言如Fortran，Algol60，以及后来的PL/l，Pascal等，算法的程序表达才产生一次大的飞跃。
诚然，算法最终要表达为具体计算机上的机器语言才能在该计算机上运行，得到所需要的结果。但汇编语言的实践启发人们，表达成机器语言不必一步到位，可以分两步走或者可以筑桥过河。即先表达成一种中介语言，然后转成机器语言。汇编语言作为一种中介语言，并没有获得很大成功，原因是它离算法语言还太远。这便指引人们去设计一种尽量接近算法语言的规范语言，即所谓的高级语言，让程序员可以用它方便地表达算法，然后借助于规范的高级语言到规范的机器语言的"翻译"，最终将算法表达为机器语言。而且，由于高级语言和机器语言都具有规范性，这里的"翻译"完全可以机械化地由计算机来完成，就像汇编语言被翻译成机器语言一样，只要计算机配上一个编译程序。
上述两步，前一步由程序员去完成，后一步可以由编译程序去完成。在规定清楚它们各自该做什么之后，这两步是完全独立的。它们各自该如何做互不相干。前一步要做的只是用高级语言正确地表达给定的算法，产生一个高级语言程序;后一步要做的只是将第一步得到的高级语言程序翻译成机器语言程序。至于程序员如何用高级语言表达算法和编译程序如何将高级语言表达的算法翻译成机器语言表达的算法，显然毫不相干。
处理从算法语言最终表达成机器语言这一复杂过程的上述思想方法就是一种抽象。汇编语言和高级语言的出现都是这种抽象的范例。
与汇编语言相比，高级语言的巨大成功在于它在数据、运算和控制三方面的表达中引入许多接近算法语言的概念和工具，大大地提高抽象地表达算法的能力。
在运算方面，高级语言如Pascal，除允许原封不动地运用算法语言的四则运算、逻辑运算、关系运算、算术表达式、逻辑表达式外，还引入强有力的函数与过程的工具，并让用户自定义。这一工具的重要性不仅在于它精简了重复的程序文本段，而且在于它反映出程序的两级抽象。在函数与过程调用级，人们只关心它能做什么，不必关心它如何做。只是到函数与过程的定义时，人们才给出如何做的细节。用过高级语言的读者都知道，一旦函数与过程的名称、参数和功能被规定清楚，那么，在程序中调用它们便与在程序的头部说明它们完全分开。你可以修改甚至更换函数体与过程体，而不影响它们的被调用。如果把函数与过程名看成是运算名，把参数看成是运算的对象或运算的结果，那么，函数与过程的调用和初等运算的引用没有两样。利用函数和过程以及它们的复合或嵌套可以很自然地表达算法语言中任何复杂的运算。
在数据方面，高级语言如Pascal引人了数据类型的概念，即把所有的数据加以分类。每一个数据(包括表达式)或每一个数据变量都属于其中确定的一类。称这一类数据为一个数据类型。因此，数据类型是数据或数据变量类属的说明，它指示该数据或数据变量可能取的值的全体。对于无结构的数据，高级语言如Pascal，除提供标准的基本数据类型--布尔型、字符型、整型和实型外，还提供用户可自定义的枚举类型、子界类型和指针类型。这些类型(除指针外)，其使用方式都顺应人们在算法语言中使用的习惯。对于有结构的数据，高级语言如Pascal，提供了数组、记录、有限制的集合和文件等四种标准的结构数据类型。其中，数组是科学计算中的向量、矩阵的抽象;记录是商业和管理中的记录的抽象;有限制的集合是数学中足够小的集合的势集的抽象;文件是诸如磁盘等外存储数据的抽象。人们可以利用所提供的基本数据类型(包括标准的和自定义的)，按数组、记录、有限制的集合和文件的构造规则构造有结构的数据。此外，还允许用户利用标准的结构数据类型，通过复合或嵌套构造更复杂更高层的结构数据。这使得高级语言中的数据类型呈明显的分层，如图1-6所示。
<IMG src="http://algorithm.myrice.com/datastructure/ADT/images/img1.jpg">
高级语言中数据类型的分层是没有穷尽的，因而用它们可以表达算法语言中任何复杂层次的数据。
在控制方面，高级语言如Pascal，提供了表达算法控制转移的六种方式。
(1)缺省的顺序控制";"。
(2)条件(分支)控制:"if表达式(为真)then S1 else S2;" 。
(3)选择(情况)控制:
<BLOCKQUOTE>
"Case 表达式 of
<BLOCKQUOTE>
值1: S1
值2: S2
...
值n: Sn</BLOCKQUOTE>
end"</BLOCKQUOTE>
(4)循环控制:
<BLOCKQUOTE>
"while 表达式(为真) do S;" 或
"repeat S until 表达式(为真);" 或
"for变量名:=初值 to/downto 终值do S;"</BLOCKQUOTE>
(5)函数和过程的调用，包括递归函数和递归过程的调用。
(6)无条件转移goto。
　
这六种表达方式不仅覆盖了算法语言中所有控制表达的要求，而且不再像机器语言或汇编语言那样原始、那样繁琐、那样隐晦，而是如上面所看到的，与自然语言的表达相差无几。
程序设计语言从机器语言到高级语言的抽象，带来的主要好处是：
<OL>
<LI>高级语言接近算法语言，易学、易掌握，一般工程技术人员只要几周时间的培训就可以胜任程序员的工作；
<LI>高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；
<LI>高级语言远离机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可移植性好，重用率高；
<LI>由于把繁杂琐碎的事务交给了编译程序去做，所以自动化程度高，开发周期短，且程序员得到解脱，可以集中时间和精力去从事对于他们来说更为重要的创造性劳动，以提高程序的质量。 </LI></OL>

b · 发表于 2004-5-29 04:09:07

<H2>抽象数据类型</H2><

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

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

>按照自顶向下逐步求精的原则，我们在探索运算步骤时，首先应该考虑算法顶层的运算步骤，然后再考虑底层的运算步骤。所谓顶层的运算步骤是指定义在数据模型级上的运算步骤，或叫宏观运算。它们组成算法的主干部分。表达这部分算法的程序就是主程序。其中涉及的数据是数据模型中的一个变量，暂时不关心它的数据结构;涉及的运算以数据模型中的数据变量作为运算对象，或作为运算结果，或二者兼而为之，简称为定义在数据模型上的运算。由于暂时不关心变量的数据结构，这些运算都带有抽象性质，不含运算的细节。所谓底层的运算步骤是指顶层抽象的运算的具体实现。它们依赖于数据模型的结构，依赖于数据模型结构的具体表示。因此，底层的运算步骤包括两部分:一是数据模型的具体表示;二是定义在该数据模型上的运算的具体实现。我们可以把它们理解为微观运算。于是，底层运算是顶层运算的细化;底层运算为顶层运算服务。为了将顶层算法与底层算法隔开，使二者在设计时不会互相牵制、互相影响，必须对二者的接口进行一次抽象。让底层只通过这个接口为顶层服务，顶层也只通过这个接口调用底层的运算。这个接口就是<DFN>抽象数据类型</DFN>。其英文术语是<DFN>Abstract Data Types</DFN>，简记<ACRONYM title="Abstract Data Types">ADT</ACRONYM>。抽象数据类型是算法设计和程序设计中的重要概念。严格地说，它是算法的一个数据模型连同定义在该模型上、作为该算法构件的一组运算。这个概念明确地把数据模型与作用在该模型上的运算紧密地联系起来。事实正是如此。一方面，如前面指出过的，数据模型上的运算依赖于数据模型的具体表示，因为数据模型上的运算以数据模型中的数据变量作为运算对象，或作为运算结果，或二者兼而为之;另方面，有了数据模型的具体表示，有了数据模型上运算的具体实现，运算的效率随之确定。于是，就有这样的一个问题:如何选择数据模型的具体表示使该模型上的各种运算的效率都尽可能地高?很明显，对于不同的运算组，为使组中所有运算的效率都尽可能地高，其相应的数据模型具体表示的选择将是不同的。在这个意义下，数据模型的具体表示又反过来依赖于数据模型上定义的那些运算。特别是，当不同运算的效率互相制约时，还必须事先将所有的运算的相应使用频度排序，让所选择的数据模型的具体表示优先保证使用频度较高的运算有较高的效率。数据模型与定义在该模型上的运算之间存在着的这种密不可分的联系，是抽象数据类型的概念产生的背景和依据。应该指出，抽象数据类型的概念并不是全新的概念。它实际上是我们熟悉的基本数据类型概念的引伸和发展。用过高级语言进行算法设计和程序设计的人都知道，基本数据类型已隐含着数据模型和定义在该模型上的运算的统一，只是当时还没有形成抽象数据类型的概念罢了。事实上，大家都清楚，基本数据类型中的逻辑类型就是逻辑值数据模型和或(∨)、与(∧)、非(┐)三种逻辑运算的统一体；整数类型就是整数值数据模型和加(+)、减(-)、乘(*)、除(div)四种运算的统一体；实型和字符型等也类同。每一种基本类型都连带着一组基本运算。只是由于这些基本数据类型中的数据模型的具体表示和基本运算的具体实现都很规范，都可以通过内置(built-in)而隐蔽起来，使人们看不到它们的封装。许多人已习惯于在算法与程序设计中用基本数据类型名和相关的运算名，而不问其究竟。所以没有意识到抽象数据类型的概念已经孕育在基本数据类型的概念之中。回到定义算法的顶层和底层的接口，即定义抽象数据类型。根据抽象数据类型的概念，对抽象数据类型进行定义就是约定抽象数据类型的名字，同时，约定在该类型上定义的一组运算的各个运算的名字，明确各个运算分别要有多少个参数，这些参数的含义和顺序，以及运算的功能。一旦定义清楚，算法的顶层就可以像引用基本数据类型那样，十分简便地引用抽象数据类型;同时，算法的底层就有了设计的依据和目标。顶层和底层都与抽象数据类型的定义打交道。顶层运算和底层运算没有直接的联系。因此，只要严格按照定义办，顶层算法的设计和底层算法的设计就可以互相独立，互不影响，实现对它们的隔离，达到抽象的目的。在定义了抽象数据类型之后，算法底层的设计任务就可以明确为:<OL><LI>赋每一个抽象数据类型名予具体的构造数据类型，或者说，赋每一个抽象数据类型名予具体的数据结构; <LI>赋每一个抽象数据类型上的每个运算名予具体的运算内容，或者说，赋予具体的过程或函数。 </LI></OL>因此，落实下来，算法底层的设计就是数据结构的设计和过程与函数的设计。用高级语言表达，就是构造数据类型的定义和过程与函数的说明。不言而喻，由于实际问题千奇百怪，数据模型千姿百态，问题求解的算法千变万化，抽象数据类型的设计和实现不可能像基本数据类型那样可以规范、内置、一劳永逸。它要求算法设计和程序设计人员因时因地制宜，自行筹划，目标是使抽象数据类型对外的整体效率尽可能地高。下面用一个例子来说明，对于一个具体的问题，抽象数据类型是如何定义的。考虑<a href="http://algorithm.myrice.com/algorithm/index.html?commonalg/graph/connectivity/topo_sort.htm" target="_blank" >拓扑排序</A>问题:已知一个集合S={a1,a2, ... ,am}，S上已规定了一个部分序<。要求给出S的一个线性序{a1',a2', ... ,am'}，即S的一个重排，使得对于任意的1<=j<k<=m，不得有ak'<aj'。这里所谓S上的部分序<，是指S上的一种序关系，它对于S中的任意元素x,y和z，具有如下三个性质:<OL><LI>不得有x<x；(反自反性） <LI>若x<y，则不得有y<x；（反对称性） <LI>若x<y，,且y<z，则x<z；(传递性)。 </LI></OL>其中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={a1,a2, ... ,am}是Queue中的一个队列。在G中，ai和aj之间有一条起于ai止于aj的有向连线的充分必要条件是ai<aj。具体地说，比如S={a1，a2, ... ,a10}，而<如表1-3所示，则G(V,E)如图1-7，而Q={a7，a9，a1，a2，a4，a6，a3，a5，a8，a10}。这个Q只是问题的一个解。显然问题的解不唯一，容易举出Q'={a1，a2，a7,a9，a10，a4，a6，a3，a5，a8}是另一个解。<img src="http://algorithm.myrice.com/datastructure/ADT/images/img2.gif"><TABLE cellSpacing=0 borderColorDark=#000000 width=95 align=center borderColorLight=#000000 border=1><TR><TD width=85><DIV align=center>a1<a2 </DIV></TD></TR><TR><TD width=85><DIV align=center>a2<a4 </DIV></TD></TR><TR><TD width=85><DIV align=center>a4<a6 </DIV></TD></TR><TR><TD width=85><DIV align=center>a2<a10 </DIV></TD></TR><TR><TD width=85><DIV align=center>a4<a8 </DIV></TD></TR><TR><TD width=85><DIV align=center>a6<a3 </DIV></TD></TR><TR><TD width=85><DIV align=center>a1<a3 </DIV></TD></TR><TR><TD width=85><DIV align=center>a3<a5 </DIV></TD></TR><TR><TD width=85><DIV align=center>a5<a8 </DIV></TD></TR><TR><TD width=85><DIV align=center>a7<a5 </DIV></TD></TR><TR><TD width=85><DIV align=center>a7<a9 </DIV></TD></TR><TR><TD width=85><DIV align=center>a9<a4 </DIV></TD></TR><TR><TD width=85><DIV align=center>a9<a10 </DIV></TD></TR></TABLE>表1-3 S={a1,a2,...,a10}中的部分序在数据模型Digraph和Queue的基础上，容易拟定出算法高层的宏观运算步骤，我们称之为算法的主干部分，并用非形式的自然语言表述如下：<BLOCKQUOTE>1.φ->Q;2.检测G。(1)当G≠φ时;<BLOCKQUOTE>①在G中出任意一个无前驱的结点，记为a；②将a加到Q的末尾;③在G中删去结点a以及以a为起点的所有有向边;④转向2。</BLOCKQUOTE>(2)当C=φ时，算法结束，问题的解在Q中。</BLOCKQUOTE>用高级语言中的控制结构语句成分，替换上述主干算法中自然语言的控制转移术语，则主干算法可用自然语言和高级语言的混合语言改述如下:<PRE><CODE>φ->Q;while G≠φ do begin a:=G中任意一个无前驱的顶点; 将a加到Q的末尾; 从G中删去结点a以及以a为起点的所有有向边; end;</CODE></PRE>我们看到，其中那些还未能用高级语言表达的语句或语句成分，正是算法需要定义在数据模型Digraph和Queue上的运算。现分别将它们列出。对于Digraph中的G:<BLOCKQUOTE><OL><LI>检测G是否非空图; <LI>在G中找任意一个无前驱的结点; <LI>在G中删去一个无前驱的结点，以及以该结点为起点的所有有向边。 </LI></OL></BLOCKQUOTE>对于Queue中的Q:<BLOCKQUOTE><OL><LI>初始化Q为空队列; <LI>将一个结点加到Q的末尾。 </LI></OL></BLOCKQUOTE>如果还考虑到已知G的初始状态如何由输入形成和Q的结果状态的输出，那么，对于Digraph和Queue还需要补充定义若干有关的运算。为了简单，这里从略。由于高级语言为抽象数据类型的定义提供了很好的环境和工具，再复杂的数据模型都可以通过构造数据类型来表达，再复杂的运算都可以借助过程或函数来描述。因此，上述由数据模型和数据模型上定义的运算综合起来的抽象数据类型很容易用高级语言来定义。对于抽象数据类型mgraph，定义如下三个运算:<DL><DD>(l)function G_empty(G

igraph):boolean; <DD>{检测图G是否非空。如果G=φ，则函数返回true，否则返回false} <DD>(2)function G_front(G

igraph):nodetype； <DD>{在有向图G中找一个无前驱的结点。nodetype是结点类型名，它有待用户定义，下同} <DD>(3)Procedure delete_G_front(var G

igraph;a:nodetype); <DD>{在G中删去结点a以及以a为起点的所有有向边} </DD></DL>对抽象数据类型Queue，定义如下两个运算:<DL><DD>(l)Procedure init_Q(var Q

ueue); {初始化队列Q为空队列} <DD>(2)Procedure add_Q_rear(a:nodetype;var Q

ueue) {将结点a加到队列Q的末尾} </DD></DL>这样，我们便定义了ADT Digraph和ADT Queue。有了抽象数据类型Digraph和Queue的上述定义，拓扑排序问题的主干算法即可完全由高级语言表达成主程序。<PRE><CODE>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

ueue); ... Procedure add_Q_rear(a:nodetype;var Q:Queue); ...vara: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;</CODE></PRE>为了简明，我们在其中略去了输入、拓扑排序前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的定义不变，不管上述构造数据类型的表示和过程与函数的实现如何改变，主程序的表达都不会改变;反过来，不管主程序在哪里调用抽象数据类型上的函数或过程，上述构造数据类型的表示和过程与函数的实现都不必改变。算法顶层的设计与底层的设计之间的这种独立性，显然得益于抽象数据类型的引人。而这种独立性给算法和程序设计带来了许多好处

b · 发表于 2004-5-29 04:09:27

<H2>使用抽象数据类型带来的好处</H2><

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

b · 发表于 2004-5-29 04:09:50

<H2>数据结构、数据类型和抽象数据类型</H2><

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

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

>数据是按照数据结构分类的，具有相同数据结构的数据属同一类。同一类数据的全体称为一个数据类型。在程序设计高级语言中，数据类型用来说明一个数据在数据分类中的归属。它是数据的一种属性。这个属性限定了该数据的变化范围。为了解题的需要，根据数据结构的种类，高级语言定义了一系列的数据类型。不同的高级语言所定义的数据类型不尽相同。Pascal语言所定义的数据类型的种类如图1-8所示。<img src="http://algorithm.myrice.com/datastructure/ADT/images/img3.gif">其中，简单数据类型对应于简单的数据结构;构造数据类型对应于复杂的数据结构;在复杂的数据结构里，允许成分数据本身具有复杂的数据结构，因而，构造数据类型允许复合嵌套;指针类型对应于数据结构中成分数据之间的关系，表面上属简单数据类型，实际上都指向复杂的成分数据即构造数据类型中的数据，因此这里没有把它划入简单数据类型，也没有划入构造数据类型，而单独划出一类。数据结构反映数据内部的构成方式，它常常用一个结构图来描述:数据中的每一项成分数据被看作一个结点，并用方框或圆圈表示，成分数据之间的关系用相应的结点之间带箭号的连线表示。如果成分数据本身又有它自身的结构，则结构出现嵌套。这里嵌套还允许是递归的嵌套。由于指针数据的引入，使构造各种复杂的数据结构成为可能。按数据结构中的成分数据之间的关系，数据结构有线性与非线性之分。在非线性数据结构中又有层次与网状之分。由于数据类型是按照数据结构划分的，因此，一类数据结构对应着一种数据类型。数据类型按照该类型中的数据所呈现的结构也有线性与非线性之分，层次与网状之分。一个数据变量，在高级语言中的类型说明必须是读变量所具有的数据结构所对应的数据类型。最常用的数据结构是数组结构和记录结构。数组结构的特点是：<OL><LI>成分数据的个数固定，它们之间的逻辑关系由成分数据的序号(或叫数组的下标)来体现。这些成分数据按照序号的先后顺序一个挨一个地排列起来。 <LI>每一个成分数据具有相同的结构(可以是简单结构，也可以是复杂结构)，因而属于同一个数据类型(相应地是简单数据类型或构造数据类型)。这种同一的数据类型称为基类型。 <LI>所有的成分数据被依序安排在一片连续的存储单元中。 </LI></OL>概括起来，数组结构是一个线性的、均匀的、其成分数据可随机访问的结构。由于这种结构有这些良好的特性，所以最常被人们所采用。在高级语言中，与数组结构相对应的数据类型是数组类型，即数组结构的数据变量必须说明为array of T0 ，其中i是数组结构的下标类型，而T0是数组结构的基类型。记录结构是另一种常用的数据结构。它的特点是:<OL><LI>与数组结构一样，成分数据的个数固定。但成分数据之间没有自然序，它们处于平等地位。每一个成分数据被称为一个域并赋予域名。不同的域有不同的域名。 <LI>不同的域允许有不同的结构，因而允许属于不同的数据类型。 <LI>与数组结构一样，它们可以随机访问，但访问的途径靠的是域名。 </LI></OL>在高级语言中记录结构对应的数据类型是记录类型。记录结构的数据的变量必须说明为记录类型。抽象数据类型的含义在上一段已作了专门叙述。它可理解为数据类型的进一步抽象。即把数据类型和数据类型上的运算捆在一起，进行封装。引入抽象数据类型的目的是把数据类型的表示和数据类型上运算的实现与这些数据类型和运算在程序中的引用隔开，使它们相互独立。对于抽象数据类型的描述，除了必须描述它的数据结构外，还必须描述定义在它上面的运算(过程或函数)。抽象数据类型上定义的过程和函数以该抽象数据类型的数据所应具有的数据结构为基础

b · 发表于 2004-5-29 04:10:24

<H1>基本ADT </H1><

>这里将讨论一些基本<a href="http://algorithm.myrice.com/datastructure/ADT/chapter2.htm" target="_blank" >抽象数据类型</A>。所谓基本，只是相对而言，这些数据类型是最基本，最简单的，并且是实现其他抽象数据类型的基础。<

>在下面的讨论中，首先我们将给出各种ADT的数学性质，然后在其数学模型上定义一组运算，最后将讨论如何利用基本的数据类型（数组、指针、记录等）来具体实现各种ADT。<

>为了体现算法表达的抽象机制，在这里我将尝试用面向对象的方法来实现所有的抽象数据类型。由于基本的数据类型要牵涉到各种编程语言的具体语法特性，考虑到大家的具体需求，我将分别用Object Pascal和 C++ 语言来实现每种ADT。Object Pascal是Borland对传统Pascal语言的扩展，主要是在其中加入了面向对象的机制，语法上和传统Pascal差不多，就好像C++是C的扩展一样。这里所采用的Object Pascal将以Borland Delphi的Pascal语法为标准，采用的C++将以Microsoft Visual C++的C++语法为标准，所有的Object Pascal代码都在Delphi 5.0上调试通过，所有的C++代码都在VC6.0上调试通过。请注意，这里假设您已经很熟悉Object Pascal或C++编程，以及面向对象的编程思想，所以我的精力将主要放在各种ADT的具体实现上，而不是各种语言的语法讲解上。下面您将了解到以下常见的基本抽象数据类型的ADT操作以及这些操作用不同<a href="http://algorithm.myrice.com/datastructure/dataexpr.html" target="_blank" >数据描述方法</A>的具体实现：<UL><UL><LI><a href="http://algorithm.myrice.com/datastructure/basic/list/chapter1.htm" target="_blank" >表</A> <LI><a href="http://algorithm.myrice.com/datastructure/basic/stack/chapter1.htm" target="_blank" >栈</A> <LI><a href="http://algorithm.myrice.com/datastructure/basic/queue/chapter1.htm" target="_blank" >队列</A> <LI>串 <LI><a href="http://algorithm.myrice.com/datastructure/basic/tree/chapter1.htm" target="_blank" >树</A> <LI><a href="http://algorithm.myrice.com/datastructure/basic/binary_tree/chapter1.htm" target="_blank" >二叉树</A> <LI>图</LI></UL></UL>

		自动登录	找回密码
密码			注-册-帐-号