[科普中国]-抽象数据结构

啊1

抽象数据结构到目前为止，我们所看到的数据结构都属于具体的数据结构。所谓具体的数据结构，是指它们的具体结构和对它们的操作方法完全都由我们自己来定义。例如，利用两个整型的数或者枚举类型的数来表示扑克牌的Card类，用两个浮点数来定义的复数类。

抽象数据结构，或者叫做ADT(abstract data type)，虽是定义了一系列的操作(或者直接叫方法)和这些操作的作用(它们做什么)，但我们却并不指定这些操作过程如何具体予以实施的办法(即不编写具体的代码)。这样出现的数据结构就是抽象数据结构。

例如，抽象的堆栈（stack）由3个操作定义：推入push，弹出pop（接受约束：每次弹出返回的是最新被推入且没有被弹出的数据，也就是后进先出），查看堆栈顶端数据peek。当分析使用堆栈算法的效率，所有这3个操作用时相同，无论堆栈中包含多少项数据；并且对每项数据栈使用了常量大小的存储。 抽象数据类型（ADT）是纯粹理论实体，用于简化描述抽象算法，分类与评价数据结构，形式描述程序设计语言的类型系统。一个ADT可以用特定数据类型或数据结构实现，在许多程序设计语言中有许多种实现方式；或者用形式规范语言描述。ADT常实现为模块（module）：模块的接口声明了对应于ADT操作的例程（procedure），有时用注释描述了约束。

这样虚虚的东西有什么用?它有下列作用：

可以简化编写算法程序的任务。这时，我们可以早早指定某一项操作，但又不必当时就编写这些操作如何具体实施的代码。

对应一种抽象数据，可能找到各种各样实施途径。于是，当编写了一个算法后，就可以在相当多的其他类似场合应用和共享。

像本章中即将讨论声名显赫的堆栈这类抽象数据结构那样，人们早已编写了它的实施代码，并常常被放在标准库中，以利大家改写或者直接应用于各种程序场合。

对于抽象数据结构的操作，又为高级语言提供了编写或者讨论算法的最好背景。

当讨论抽象数据结构时，我们通常要区分哪些是运用抽象数据结构的代码(称为应用代码)，哪些是抽象数据结构的实施代码(称为服务代码)。后者常常提供一系列的标准服务。

抽象数据结构我们把数据结构定义为一组规则和约束条件，它们表示数据块之间存在的关系．这种结构并末涉及可能出现的各个数据块是什么．在某种意义上讲，只要求它们保持这种结构，然而，包含在数据项内的任何信息是不依赖于该结构的．这里使用了项这个术语去表示一个抽象数据结构的块．项本身也可以是其他的数据结构，这样就建立了数据结构的层次集合．

串(string)串是项的有序集．它可以是变长的，也可以是定长的．每项只有其相邻项的信息，因此，取一特定项时，必须从串的一端开始，顺序进行查找．在串上定义的运算有

(a)两串的并置；

(b)对两串作项对项的比较；

(c)把串分成几部分．

数组数组A是这样排列的项的集合：使得一个有序整数集唯一定义数组每项的位置，并提供直接取每项的方法．用ALGOL表示法，如果有序整数集的长度为n，那么，该数组称为n维的．有序集中各个整数称为下标．每个下标可以用任意方式定义其界限，而该界限可由若干互不相交的子界限组成。

在编译程序和程序设计语言中所使用的是数组集的某一特殊子集，即所谓矩形数组集．矩形数组的每个下标界限是不变的和连读的。

排队和栈(Queue和stack)排队和栈是动态改变的数据结构．任何时候它们都包含一组有序的项．对排队的情形来说，如果添加一项，就把它放在组的末端，而且只能从定义该排队组的前面取出或移摔项．列在排队中的第一项是唯一可取出的项，而且必须先移掉它．对栈的情形来说，添加的项同样是放在组的末端，不同的是要从组的末端取出和移掉项．此时最后添加的项是唯一可取出的项，并最先被移掉．项可以是可变长度的，并在项中指明其长度．

表表由一组项组成，和每项相联系的是唯一的名字或关键字．通常，每项是由它的关键字连同与该关键字有关的一些信息所组成．给出项的关键字及其有关信息就能把项添到表中．反之，通过关键字能从表中取出相应的项来．

树树是由一组结点组成的结构．每个结点(或者项)有这样的特点：除它所带的信息外，它还包含低层结点的指示字，在树的最低层，结点指的是叶子，叶子是由树外的数据结构组成的．层的思想是基于下述事实得来的：每株树毖有一最顶的结点，它再无别的结点指示它(通常称为树的根)，树中也没有结点能指示前面已定义的结点．后一条件保证了从根到每一个结点只有唯一的通路．第一层结点是树根所指的那些结点，第二层的结点是第一层结点所指示的那些结点，等等．

方向图除低层结点可指示高层结点外，方向图是一种类似于树的结构．所以，一个结点可有几个结点指示它．因为现在已看不清图中两个结点之间的联线方向，所以，通常在图中至少要标出向上的指示线．放宽对树的一些规则的限制，就表明有可能存在一条从某结点出发再回到该结点的通路，即通常所谓的环路．方向图有一个特殊的子类是无环方向图．这和树的定义并不一致，因为，它仍然允许两个结点指示同一个结点，而这一点在树的定义中是不允许的．例如，ALGOL语言的复合语句。

堆栈在此，我们先探讨一种通用常见且又名声显赫的抽象数据结构——堆栈。堆栈也是一个集合体，包含有许许多多元素。而到目前为止，我们已经学到过的集合体是数组和链表。

如同上面已经提及的：一个抽象数据结构，就是对它进行一系列的操作定义。对于著名的堆栈，它的操作定义不多，仅仅包括下列这些东西：

Constructor(构造器)：创建一个新的空堆栈。

Push：在堆栈中增加一个元素。

Pop：从堆栈中删除一个元素，同时返回这个元素，并且，这个元素总是我们最后增加的那个元素。

Count：获取包含在堆栈中的元素数。

堆栈有时也被叫做“后进先出”数据结构，英文是“last in，first out(LIFO)”。之所以这样取名，是由于最后一个被加进的元素总是首先被删除。

C#堆栈对象C#内部已经提供了内置的Stack类，由它来实施堆栈这种抽象数据结构。大家应该花点精力去精确理解和清晰区分这样的两类事——抽象数据结构(ADT)和它的C#言实施。现在，我们就来看看c群已经为我们提供的内置堆栈。不过，在使

用Stack类之前，大家先得引人它。

请大家在例文件的首部键人如下内容，以让编译器引入位于System．Collections这个命名空间中的Stack类：

LISing System．Collections；

然后在Main方法中创建一个新的堆栈，语法是这样的：

Stack stack=new Stack()；

刚创建的堆栈是空的。是不是这样?可以用Count属性进行测试。测试的结果应是零值：

Console．WriteLine(stack．Count)j

堆栈应该是一种通用数据结构。其通用的含义是：大家可以把任何类型的元素添加到堆栈中。但是，在雠语言中，对堆栈的应用却有些许限制：可以被添加到堆栈中的东西，都必须是引用类型的对象，而不能是值类型对象(其原因待会儿再阐述)，比如本书中用得最多、大家最熟悉的整数(int)类型就不行。

在此就给出第一个例子。在此例子中，我们要使用的元素就是上一章的Node(节点)对象。现在就让我们开始创建并且打印短短的一个链表：

list．AddFirst(

list．AddFirst (

list．AddFirst(

liSt．PrintList

抽象数据结构的实施意义人们应用抽象数据结构的最主要目的，是为了区分代码的提供者和代码的应用者。那些编写抽象数据结构如何实现或实施代码的人，就是代码的提供者；而那些只管把抽象数据结构拿来使用的人，就是代码的应用者。对于代码提供者来说，他们主要关心抽象数据结构实施的正确和效率，而不着重于它们的真正应用。

反之，代码应用者都假定抽象数据结构的实施完全正确和十分有效，他们一般都不关心代码的细节。我们已经在多处应用过c#的内置类了，我们早已都是它们的应用者了。

当然，如果我们作为代码提供者的身份，对于已编写好抽象数据结构的实施代码，也必须以代码使用者的身份编写一些应用代码，对抽象数据结构进行各种各样的测试。在编写和测试阶段，大家得仔细想想自己到底是代码编写者，还是代码使用者。

在下面数节内容中，大家都得作为代码编写者运用先前已掌握的数组知识编写一些代码，来实施抽象数据结构——堆栈。

运用数组来实施堆栈运用数组实施抽象结构数据——堆栈时，堆栈类的实例变量是什么?有两个：一个是由Object类型作为元素所组成的数组，该数组容纳被放人堆栈的各个成员；另一个是引用数组中下一个空位的数组索引值，即一个整数。当这个堆栈被初始化时，数组是空的，而对该数组的索引就是0。

为了向堆栈增加(Push)一个新元素，就应该把这个元素放进数组相应位置上，然后再把该数组的索引值增加1。而为了从堆栈中删除(Pop)一个旧元素成员，先是把该数组的索引值减1，然后再把数组中由该索引值指定的元素返送回来。

下面就是以上用文字说明的堆栈类的定义(堆栈的实施)：

|| ||

通常，一旦在类中确定好将要使用的一个实例变量，顺理成章地就应该在构造器里先行处理它。在此例中，先定下这个数组的长度是128个“座位”——当然，我们还必须考虑如何处理多于128位“观众”的情况，那将在后面提及。

还要定义一个属性Count，用于检测堆栈中“东西”的数量：

|| ||

请记住，堆栈中数组里“有东西”元素的数量并不是数组的长度。初始化后，数组的长度是128，但是数组里“有东西”元素的数量却是0。

自然，现在应该是编写Push和Pop两个方法实施代码的时候了：

|| ||

为了测试以上代码运行情况，大家可以重新利用本章中已经应用于雠内置堆栈上的那些代码。当然，代码得有一点儿改动。改动之处是在“using System．Collections”这一行开头之处加上“∥”号，即把这一行的内容变成注释。这样，C#运行时就不会引入来自c聊录准库里的堆栈，而是运用我们刚才编写的堆栈了。

如果我们代码编写得完全正确，运用内置堆栈或运用自编堆栈运行程序的结果应该完全一样。这实际例子说明：抽象数据结构运用具有两面性，可以仅仅改变它的实施部分(提供代码)，而不必改变它的利用部分(应用代码)。

队列抽象数据结构一个抽象的队列数据结构总得由下列的一些基本操作组成：

构造器：创建一个新的空队列。

Enqueue：向队列的尾部新增加一项。

Dequeue：从队列中删除一项且把该项返回，该项应是整个队列的首项。

Count：检测队列包含的元素数量。

映射表抽象数据结构就像另外那些我们已经学过的抽象数据结构一样，映射表也由一系列应该具有的操作所定义：

构造器：创建一个新的空的映射表。

[ ]：索引器。把键字作为索引，如果放在赋值号的左边，存放与键字相对应的一个键值；如果放在赋值号的右边，取出与键字相对应的一个键值。

ContainsKey：如果映射表中含有给定键字的条目，返回真。

Keys：属性。返回映射表中所有键字的全体集合。

Values：属性。返回映射表中所有键值的全体集合。