抽象数据结构

计算机技术领域术语抽象数据结构01C#堆栈对象队列堆栈的实施映射表目录0305020406基本信息抽象数据结构（AbstractDataType，ADT）是计算机科学中具有类似行为的特定类别的数据结构的数学模型；或者具有类似语义的一种或多种程序设计语言的数据类型。抽象数据类型是间接定义的，通过其上的可执行的操作以及这些操作的效果的数学约束（与可能的代价）。串(string)数组排队和栈(Queue和stack)表树方向图010302040506串(string)串是项的有序集．它可以是变长的，也可以是定长的．每项只有其相邻项的信息，因此，取一特定项时，必须从串的一端开始，顺序进行查找．在串上定义的运算有(a)两串的并置；(b)对两串作项对项的比较；(c)把串分成几部分．数组数组A是这样排列的项的集合：使得一个有序整数集唯一定义数组每项的位置，并提供直接取每项的方法．用ALGOL表示法，如果有序整数集的长度为n，那么，该数组称为n维的．有序集中各个整数称为下标．每个下标可以用任意方式定义其界限，而该界限可由若干互不相交的子界限组成。在编译程序和程序设计语言中所使用的是数组集的某一特殊子集，即所谓矩形数组集．矩形数组的每个下标界限是不变的和连读的。排队和栈(Queue和stack)排队和栈是动态改变的数据结构．任何时候它们都包含一组有序的项．对排队的情形来说，如果添加一项，就把它放在组的末端，而且只能从定义该排队组的前面取出或移摔项．列在排队中的第一项是唯一可取出的项，而且必须先移掉它．对栈的情形来说，添加的项同样是放在组的末端，不同的是要从组的末端取出和移掉项．此时最后添加的项是唯一可取出的项，并最先被移掉．项可以是可变长度的，并在项中指明其长度．表表由一组项组成，和每项相联系的是唯一的名字或关键字．通常，每项是由它的关键字连同与该关键字有关的一些信息所组成．给出项的关键字及其有关信息就能把项添到表中．反之，通过关键字能从表中取出相应的项来．树树是由一组结点组成的结构．每个结点(或者项)有这样的特点：除它所带的信息外，它还包含低层结点的指示字，在树的最低层，结点指的是叶子，叶子是由树外的数据结构组成的．层的思想是基于下述事实得来的：每株树毖有一最顶的结点，它再无别的结点指示它(通常称为树的根)，树中也没有结点能指示前面已定义的结点．后一条件保证了从根到每一个结点只有唯一的通路．第一层结点是树根所指的那些结点，第二层的结点是第一层结点所指示的那些结点，等等．方向图除低层结点可指示高层结点外，方向图是一种类似于树的结构．所以，一个结点可有几个结点指示它．因为现在已看不清图中两个结点之间的联线方向，所以，通常在图中至少要标出向上的指示线．放宽对树的一些规则的限制，就表明有可能存在一条从某结点出发再回到该结点的通路，即通常所谓的环路．方向图有一个特殊的子类是无环方向图．这和树的定义并不一致，因为，它仍然允许两个结点指示同一个结点，而这一点在树的定义中是不允许的．例如，ALGOL语言的复合语句。堆栈堆栈在此，我们先探讨一种通用常见且又名声显赫的抽象数据结构——堆栈。堆栈也是一个集合体，包含有许许多多元素。而我们已经学到过的集合体是数组和链表。如同上面已经提及的：一个抽象数据结构，就是对它进行一系列的操作定义。对于著名的堆栈，它的操作定义不多，仅仅包括下列这些东西：堆栈有时也被叫做“后进先出”数据结构，英文是“lastin，firstout(LIFO)”。之所以这样取名，是由于最后一个被加进的元素总是首先被删除。C#堆栈对象C#堆栈对象C#内部已经提供了内置的Stack类，由它来实施堆栈这种抽象数据结构。大家应该花点精力去精确理解和清晰区分这样的两类事——抽象数据结构(ADT)和它的C#言实施。现在，我们就来看看c群已经为我们提供的内置堆栈。不过，在使用Stack类之前，大家先得引人它。请大家在例文件的首部键人如下内容，以让编译器引入位于System．Collections这个命名空间中的Stack类：LISingSystem．Collections；然后在Main方法中创建一个新的堆栈，语法是这样的：Stackstack=newStack()；刚创建的堆栈是空的。是不是这样?可以用Count属性进行测试。测试的结果应是零值：Console．WriteLine(stack．Count)j堆栈应该是一种通用数据结构。其通用的含义是：大家可以把任何类型的元素添加到堆栈中。但是，在雠语言中，对堆栈的应用却有些许限制：可以被添加到堆栈中的东西，都必须是引用类型的对象，而不能是值类型对象(其原因待会儿再阐述)，比如本书中用得最多、大家最熟悉的整数(int)类型就不行。的实施运用数组来实施堆栈意义的实施意义人们应用抽象数据结构的最主要目的，是为了区分代码的提供者和代码的应用者。那些编写抽象数据结构如何实现或实施代码的人，就是代码的提供者；而那些只管把抽象数据结构拿来使用的人，就是代码的应用者。对于代码提供者来说，他们主要关心抽象数据结构实施的正确和效率，而不着重于它们的真正应用。反之，代码应用者都假定抽象数据结构的实施完全正确和十分有效，他们一般都不关心代码的细节。我们已经在多处应用过c#的内置类了，我们早已都是它们的应用者了。当然，如果我们作为代码提供者的身份，对于已编写好抽象数据结构的实施代码，也必须以代码使用者的身份编写一些应用代码，对抽象数据结构进行各种各样的测试。在编写和测试阶段，大家得仔细想想自己到底是代码编写者，还是代码使用者。在下面数节内容中，大家都得作为代码编写者运用先前已掌握的数组知识编写一些代码，来实施抽象数据结构——堆栈。运用数组来实施堆栈运用数组实施抽象结构数据——堆栈时，堆栈类的实例变量是什么?有两个：一个是由Object类型作为元素所组成的数组，该数组容纳被放人堆栈的各个成员；另一个是引用数组中下一个空位的数组索引值，即一个整数。当这个堆栈被初始化时，数组是空的，而对该数组的索引就是0。为了向堆栈增加(Push)一个新元素，就应该把这个元素放进数组相应位置上，然后再把该数组的索引值增加1。而为了从堆栈中删除(Pop)一个旧元素成员，先是把该数组的索引值减1，然后再把数组中由该索引值指定的元素返送回来。下面就是以上用文字说明的堆栈类的定义(堆栈的实施)：通常，一旦在类中确定好将要使用的一个实例变量，顺理成章地就应该在构造器里先行处理它。在此例中，先定下这个数组的长度是128个“座位”——当然，我们还必须考虑如何处理多于128位“观众”的情况，那将在后面提及。还要定义一个属性Count，用于检测堆栈中“东西”的数量：请记住