《工程软件开发技术》-第6 章

6.1概论6.1.1引言一般来说，用计算机解决一个具体问题时大致需要经过下列几个步骤：首先要从具体问题抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编写出程序，进行测试、调试直至得到最终解答。寻求数学模型实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。6.1.2有关概念和术语在系统地学习算法和数据结构知识之前，先对一些基本概念和术语赋予确切的含义。下一页返回6.1概论数据（Data）是信息的载体，是描述客观事物的数、字符以及所有能输入到计算机中并能被计算机程序识别和处理的符号的集合。现实世界信息的分析、复制、传播首先要符号化，以便于计算机的处理。数据分为两类：数值型数据（主要用于数值计算）和非数值型数据（文字、图形、图像、音频、视频等）。数据元素（DataElement）是数据的基本单位。在不同的条件下，数据元素又可称为元素、节点、顶点、记录等。一个数据元素可由不可分割的若干个数据项（DataItem)组成。数据项是数据的不可分割的最小单位。上一页下一页返回6.1概论数据对象（DataObject）是性质相同的数据元素的集合，是数据的一个子集。在具体问题中，数据元素都具有相同的性质（元素值不一定相等），例如英文字符集是数据的一个子集，它由能够表示单词这样的共同属性的26个字母组成一个数据对象。数据元素是数据对象的一个实例。数据结构（DataStructure）是指相互之间存在着一种或多种关系的数据元素的集合。在任何问题中数据元素之间总是存在着联系。把某一数据对象及该数据对象中所有数据成员之间的关系组成的实体叫做数据结构。根据数据元素间关系的不同特性，通常有下列4类基本的结构：上一页下一页返回6.1概论（1）集合结构。在集合结构中，数据元素间的关系是属于同一个集合。集合是元素关系极为松散的一种结构。（2）线性结构。该结构的数据元素之间存在着一对一的关系。（3）树型结构。该结构的数据元素之间存在着一对多的关系。（4）图形结构或网状结构。该结构的数据元素之间存在着多对多的关系。图形结构也称为网状结构，如城市交通图。图6-1为表示上述4种基本结构的示意图。由于集合是数据元素之间关系极为松散的一种结构，因此也可用其他结构来表示。上一页下一页返回6.1概论数据类型（DataType）是和数据结构密切相关的一个概念，它最早出现在高级程序语言中，用以刻画程序操作对象的特性。在高级程序语言编写的程序中，每个变量、常量或表达式都有一个它所属的确定的数据类型。类型明显或隐含地规定了在程序执行期间变量或表达式所有可能取值的范围，以及在这些值上允许的操作。因此数据类型是一个值的集合和定义在该值集上的一组操作的总称。按“值”的不同特性，高级程序语言中的数据类型可分为两类：一类是非结构的原子类型。原子类型的值是不可分解的，如int类型。另一类是结构类型。结构类型的值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是非结构的，也可以是结构的。上一页下一页返回6.1概论抽象数据类型（AbstractDataType，ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。抽象数据类型可以使我们更容易描述现实世界。抽象数据类型和数据类型实质上是一个概念。另一方面，抽象数据类型范畴更广，它不再局限于前述各处理器中已定义并实现的数据类型，还包括用户在设计软件系统时自己定义的数据类型。抽象数据类型的特征是使用与实现相分离，实行封装和信息隐蔽。上一页下一页返回6.1概论也就是说，在抽象数据类型设计时，把类型的定义与其实现分离开来。抽象数据类型的定义可由一种数据结构和定义在其上的一组操作组成。而数据结构又包括数据元素及元素间的关系，因此抽象数据类型一般由元素、关系及操作3种要素来定义。抽象数据类型可用三元组来表示：（D，R，P）其中D是数据对象，R是D上的关系集；P是对D的基本操作集。6.1.3算法与数据结构研究内容与关系算法和数据结构研究的是计算机科学中许多最基本的问题，是研究问题求解技术、算法设计、程序设计的基础。上一页下一页返回6.1概论21世纪60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们越来越重视数据结构。从20世纪70年代中期到80年代，各种数据结构著作相继出现。目前，数据结构的发展并未终结，一方面，面向个专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型和面向对象的观点来讨论数据结构已成为一种新的趋势，越来越被人们重视。数据结构和算法这两者之间有着十分密切的关系。数据结构与数学、计算机硬件和软件有十分密切的关系。上一页下一页返回6.1概论数据结构是计算机科学与技术专业的核心课程，是编译原理、操作系统、数据库、人工智能等课程的基础。同时，在信息科学、系统工程、应用数学等工程技术领域中也广泛地使用数据结构技术。数据结构中的算法是十分重要的内容。实现算法、表达算法、验证算法、分析算法，研究和改进算法，构成了计算机科学的多个分支。上一页返回6.2算法算法是程序的核心、编程的基础。在算法设计时先要确定相应的数据结构，而在讨论某种数据结构时也必然会涉及相应的算法。6.2.1算法的定义当有了数据表示之后，就要考虑数据操作，把这些操作有效集成来完成各项任务，就是算法。算法（Algorithm）是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。算法应该具有下列特性：（1）有穷性：算法必须总是（对任何合法的输入值）在有穷步之后结束，且每一步都可在有穷时间内完成。下一页返回6.2算法（2）确定性：算法中的每一条指令必须有确切的含义，无二义性。在任何条件下，算法只有唯一的一条执行路径，即对相同的输入只能得出相同的输出。（3）可行性：算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。（4）输入：算法具有零个或多个输入，这些输入取自特定的数据对象集合。（5）输出：算法具有一个或多个输出，这些输出同输入之间存在某种特定的关系。上一页下一页返回6.2算法6.2.2算法设计的要求要设计一个好的算法，通常要考虑以下要求：（1）正确性：算法的执行结果应当满足预先规定的功能和性能要求。通常一个大型问题的要求，要以特定的规格说明方式给出，目前多数是用自然语言描述需求，它至少应当包括对于输入、输出和加工处理等的明确无歧义性的描述。设计或选择的算法应能正确地反映这种需求。通常认为，算法对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果即为合格的算法。(2)可读性：算法应当思路清晰、层次分明、简单明了、易读易懂。上一页下一页返回6.2算法（3）健壮性；当输入不合法的数据时，算法应能进行适当处理，不致于引起严重后果。（4）高效性：算法应当有效使用存储空间和有较高的时间效率。6.2.3算法表示形式同一个算法会有不同的表示形式，一般来讲，主要有4种表示形式：（1）文本：是用文字来说明解决问题的具体步骤。（2）流程图：使用规范的图形符号来说明解决问题的具体步骤。（3）伪代码：混合使用程序设计语言的语句和自然语言来说明解决问题的具体步骤。上一页下一页返回6.2算法（4）程序代码：直接以程序设计语言的语句来说明解决问题的具体步骤。流程图是一种描述程序处理过程的图示方法。常用的流程图是用一些具有特定含义的框和流向线组成。常用的流程图符号如图6-2所示。流程图表示了程序处理过程和步骤，又表示了程序的结构，简单、直观，在程序设计中被广泛采用。6.2.4算法性能分析算法与数据结构是相辅相成的。解决某一特定类型问题的算法可以选择不同的数据结构，而且选择恰当与否直接影响算法的效率。反之，一种数据结构的优劣由各种算法的执行来体现。上一页下一页返回6.2算法一个问题可能有多种不同的算法，一些算法比其他算法效率高。进行算法分析的目的是寻找高效的算法来解决不同的问题，提高工作效率。衡量算法效率的方法主要有两大类：事后统计方法（后期测试）和算法的事前分析估算方法。1．事后统计方法主要是在算法的关键部位插入计时器，当算法执行时，打开计时器，终止时关闭，这样可以得到算法执行时间的差值，从而衡量算法的效率。但这种方法存在一个明显缺陷，即它与计算机软硬件相关，并不能确切地反映多个算法的差别，不利于较大范围内的算法比较（异地、异时、异境）。上一页下一页返回6.2算法2．事前分析估算方法当我们将一个算法转换成程序并在计算机上执行时，其运行所需要的时间取决于下列因素：（1）算法选用何种策略。（2）机器执行指令的速度。（3）书写程序的语言。实现语言的级别越高，其执行效率就越低。（4）编译程序所生成目标代码的质量。对于代码优化较好的编译程序，其所生成的程序质量较高。（5）问题的规模。随着处理问题的数据增大，处理会越来越困难，把描述数据增大程度的量叫做问题规模。规模越大，消耗时间越多。上一页下一页返回6.2算法算法度量可以从时间复杂度和空间复杂度两方面进行。分析算法是一个复杂的工作，需要如图论、集合论、组合分析、概率论等方面的理论基础，这方面内容可以参考其他资料。6.2.5常用算法算法是对某个问题求解过程的描述。同一问题有多种算法描述，问题的种类很多，算法更多。总体上可以把算法分为两大类：数值算法和非数值算法。常用算法有以下几种。1．累加、连乘在循环结构中，最常用的算法是累加和连乘。累加是在原有和的基础上每次加一个数，连乘则是在原有积的基础上每次乘一个数。上一页下一页返回6.2算法在该算法中，累积个数与连乘次数都通过循环变量来控制。2．求素数素数也称为质数，就是一个大于2的整数；并只能被1和它本身整除，而不能被其他整数整除的数。判别某数m是否为素数的方法很多，最简单的是从素数的定义来求解，其算法思想是：m从i=2，3…，m-1判别是否被i整除，只要有一个能整除，m就不是素数；否则m是素数。3．穷举算法又称“枚举法”，即将可能出现的各种情况一一测试，判断是否满足条件，一般采用循环来实现。循环次数都与运算量成正比。上一页下一页返回6.2算法因此，在多重循环中，为提高运行速度，对程序更要考虑优化，应考虑以下方面：（1）尽量利用已知条件，减少循环重数。（2）合理选择内外层的循环控制变量，即将循环次数多的放在内循环。（3）尽量少用变体类型变量（可将上例中变量声明语句去掉加以比较）。4．递推算法“递推算法”又称为“迭代算法”，其基本思想是把一个复杂的计算过程转化为简单过程的多次重复。上一页下一页返回6.2算法每次重复都从旧值的基础上递推出新值，并由新值代替旧值。5．求最大值或最小值在若干个数中求最大值，一般先假设一个较小的数为最大值的初值，若无法估计较小的值，则取第一个数为最大值的初值；然后将每一个数与最大值比较，若该数大于最大值，将该数替换为最大值；依次逐一比较。求最小值的算法类似，只是先假设一个较大的数为最小值。上一页返回6.3数据结构数据结构的研究内容是构造复杂软件系统的基础，它的核心技术是分解与抽象。通过分解可以划分出数据的3个层次；再通过抽象，舍弃数据元素的具体内容，就得到逻辑结构。类似地，通过分解将处理要求划分成各种功能，再通过抽象舍弃实现细节，就得到运算的定义。上述两个方面的结合可以将问题变换为数据结构。这是一个从具体（即具体问题）到抽象（即数据结构）的过程。然后，通过增加对实现细节的考虑进一步得到存储结构和实现运算，从而完成设计任务。这是一个从抽象（即数据结构）到具体（即具体实现）的过程。6.3.1数据结构概论对于每种数据结构，都要考虑它的代价和效益。下一页返回6.3数据结构对于要解决的问题，都有时间和空间上的限制。在选择数据结构时，需要考虑存储空间和操作时间的限制，要选择适合问题的最好的数据结构。1．数据结构的定义一个数据结构有3个要素：一是数据元素的集合；二是关系的集合；三是进行的运算。在形式上，数据结构通常可以采用一个二元数组来表示。数据结构的形式定义为：Data_Structure=(D，R)其中，D是数据元素的有限集，R是关系上的有限集。上一页下一页返回6.3数据结构把常用的数据结构按照它们的表示方法和行为特性进行分类，可分为顺序表、链表、堆栈、队列、树、二叉树、图、集合等。2．数据结构的逻辑结构与物理结构数据结构定义中的关系是指数据之间的逻辑关系，故也称为数据结构的逻辑结构。数据结构的逻辑结构仅仅刻画了数据元素之间的逻辑关系，但我们并不清楚这些结构在计算机内部是如何实现的，为此需要考虑数据结构在计算机的内存中是如何存放的。数据结构在计算机中的表示称为物理结构，又称存储结构。它所研究的是数据结构在计算机中的实现方法，包括数据结构中元素的表示和元素间关系的表示。一种逻辑结构可以采用多种存储表示。上一页下一页返回6.3数据结构通常，数据结构的存储结构采用顺序存储或链式存储的方法。显然，它是依赖于计算机的。若逻辑结构相同、物理结构不同，则为不同的数据结构，用不同的名称来标识它们。我们可以按照数据的结构（逻辑结构和物理结构）特性在该结构存在期间的变动情况，将它们划分为静态结构、半静态结构和动态结构。其中静态结构就是在数据结构存在期间总是不变动的。3．数据结构常用算法数据的运算是定义在数据的逻辑结构上，但运算的具体实现要在存储结构上进行。上一页下一页返回6.3数据结构一般有以下几种常用运算：（1）检索。检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值，找具有该字段值的节点。（2）插入。往数据结构里增加新的节点。（3）删除。把指定的结点从数据结构中去掉。（4）更新。改变指定节点的一个或多个字段的值。（5）排序。把节点按某种指定的顺序重新排列。例如递增或递减。6.3.2线性表线性表是一种线性结构。上一页下一页返回6.3数据结构它是最简单、最基本也是最常用的一种线性结构，经常用于构造更复杂、通用的数据结构。线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个地排列”，也就是说，在数据元素的非空有限集中，数据元素的排列是顺序的，排列在某个数据元素b之前的数据元素a称为b的前驱，而数据元素b称为a的后继。线性结构是除第一个元素之外，集合中的每个元素均有且只有一个前驱；除最后一个数据元素外，均有且只有一个后继。定义线性表如下：线性表是具有相同数据类型的n个数据元素的有限序列，通常记为：上一页下一页返回6.3数据结构其中，n为表长，n=0时称为空表。在线性表中数据元素可以是任意类型，但必须是相同类型的，也就是说必须属于同一数据对象。逻辑上形式地可以定义为：一种数据结构D_S=(D，R)，其中线性结构的物理实现，通常使用顺序存储法和链接存储法，即顺序表和链表。选择哪种物理结构是根据具体应用中主要作何种运算而定。上一页下一页返回6.3数据结构1．向量（一维数组）定义：向量结构逻辑上是有限元素的有序集合，并且用一个整数符号（亦称下标）标志向量中各元素。又称一维数组。向量结构具有以下两个极为重要的特性：（1）均匀性。向量的所有元素具有相同的元素描述，即向量中每个元素的数据类型相同。（2）有序性。向量中各元素是有序的，元素之间的顺序在其存在期间是不能改变的，下标唯一确定了元素在向量中的位置。向量的物理结构，即向量在计算机内存中存放的组织形式。上一页下一页返回6.3数据结构通常要求分配一块连续存储空间，按向量元素的逻辑顺序，一个接一个地存放元素。对向量要经常进行的运算有以下几种：（1）取出向量中第i个元素。（2）更新向量中第i个元素。（3）在向量第i个元素之后插入新元素。（4）删除向量中第i个元素。（5）重新排序向量中元素。在插入运算中，首先把第i个元素之后的所有元素都向后移动一个元素的位置，以空出位置插入新元素。上一页下一页返回6.3数据结构在删除运算中，为保持向量元素的顺序，必须把ai，ai+1，…，an元素向上移动一个位置。因此，这两个运算开销较大。2．栈栈是一种“限定性的线性表”，对于它所有插入和运算都限制在表的同一端进行，这一端称为栈的“顶”，另一端称为栈的“底”。栈在计算机系统中很有用，一般用来保存一些尚未处理和等待处理的数据项。栈对数据项的处理是遵循“后进先出”的原则，即每次删除的数据项即是最后插入的数据项，而最先插入的数据项被放在栈底，最后才处理它。因此，栈又称为“后进先出表（LIFO）”或下推表。上一页下一页返回6.3数据结构一个典型的顺序分配的栈可以用一维数组表示它的物理结构，用一个指针sp指向它的栈顶元素，变量sp中存放着栈顶元素对应的下标地址。图6-5（a）是一个栈的示意图，进栈和出栈运算都是依靠改变sp指针来实现的。在栈上定义的运算主要是在栈顶上作进栈（插入）和出栈（删除）操作。下面通过一个实例来分析一下进栈和出栈运算的具体执行情况。假设我们定义一个由3个单元组成的一维数组作为栈存储区，用一个单元sp存放栈的下标地址。见图6-5（b）。栈的基本运算有以下两种：上一页下一页返回6.3数据结构（1）进栈push（x）。往栈stack中插入（或压入）一个值为x的表目。（2）出栈pop（）。从栈stack中删除（或弹出）一个表目。在计算机所使用的各种数据结构中，栈的应用十分广泛：1）算术表达式的计算表达式通常形式如下：(A+B)*D+E/(F+A*D)+C一般情况是左、右各一个运算对象，中间为运算符；只有单目运算是一个运算符和右边一个运算对象（如~x），这种表达式称为表达式的中缀表示。上一页下一页返回6.3数据结构编议程序为了处理方便，首先把中缀表达式转换为后缀表达式，即两个运算对象在前，它们的运算符在后，这种表达式也称为逆波兰表达式。上式转换后，形式为：AB+D*EFAD*+/+C+从上式可以看到，转换后的形式不再有括号。这种转换可以通过栈来实现。对表达式中的字符一个一个地自左至右进行扫描，当遇到运算对象时就直接输出或存入一个数组中，而遇到运算符时就进栈。进栈的原则是要保持栈顶的运算符的优先级最高，也就是当前遇到的运算符的优先级若高于栈顶运算符的优先级时，则进栈作为栈顶元素，否则将栈顶运算符退栈输出，然后把优先级低的运算符进栈。上一页下一页返回6.3数据结构当扫描时遇到开括弧“（”就直接进栈，但在遇到闭括弧“）”时则将相应开括弧后面的全部运算符退栈输出，然后再退出开括弧。括号内的运算符同样按上述进栈原则处理。3．队列队列也是一种限定性的线性表，对于它的所有插入都在表的一端进行，所有删除都在表的另一端进行。进行删除的一端称为队列的头，进行插入的一端称为队列的尾。队列结构在日常生活中也不少见，我们经常要排队买东西，排队时大家都遵守一条原则，就是迟来者必须排在队的后面，先来者先服务。上一页下一页返回6.3数据结构队列和栈一样，用来存放尚未处理而等待处理的数据。然而，数据项的处理顺序与栈不同，队列是依据“先进先出”的原则，因此，队列又可称为“FIFO”表。队列的物理实现，一般是采用顺序存储方法，要求系统分配一块连续存储空间，并用两个变量作为指针，指向队列的头和尾。顺序队列基本运算有以下两种:1）在队列中插入一个值为x的表目；2）在队列中删除一个表目。当进队时，队头指针head不动，只改变队尾指针tail，进队前应先判断队满否，若队满，提示出错。上一页下一页返回6.3数据结构当出队时，尾指针tail不动，只改变队头指针head，出队前应先判断队满否，若队满，提示出错。从图6-6中还可以看到，随着队列操作的执行，整个队列会沿一个方向不断移动。最终结果是队列前面有许多单元未被利用，由于不断进队，队尾可能已达到存储区边缘，而无法再往队列中添加数据。为了充分利用存储空间，可以把队列构成环状结构，使其头尾相接。为了使队列正常工作，还必须满足队列满和空的条件。不失一般性，假设每个表目占一个单元，为队列分配了M个单元的空间（从Q0到Q0+M-1），在队列初始化时，置head=tail=0。下面讨论队空和队满条件。上一页下一页返回6.3数据结构队空实际意义是读出（出队）赶上写入（进队），因此，队空条件为:head=tail当初始化时，显然满足队空条件。队满实际意义是写入（进队）赶上读出（出队）。当赶上读时，对循环队列队满条件为:(head-tail+M)=1栈和队列在端点运算上都有很强的限制。栈只能作插入和删除运算，而队列可以分别在两端进行插入和删除。我们也可以使队列的两端都具有栈的特性。上一页下一页返回6.3数据结构队列在计算机操作系统和管理系统中有着广泛的用途。例如，由于主机处理一个字符速度极快，而打印机打印一个字符相对于主机来讲速度慢得多，解决这个问题要建立一个缓冲区，存放要求打印的数据，打印机从缓冲区中逐个取出字符打印，这样的缓冲区实际上是一个“队列”，按先进先出原则取数。4．链表前面讨论向量、栈和队列都属于顺序表，占用的内存单元较少，查找方便，但对它进行插入、删除、重新排列时要求大量地移动数据，将耗费主机时间，效率比较低。因此，只有静态线性结构适宜于采用顺序表。上一页下一页返回6.3数据结构以链式结构存储的线性表称为线性链表，可以克服以上不足，适用于进行插入、删除等操作，操作简单、花费时间少，并且不要求预先分配一块连续存储空间，所以链接结构适用于动态线性结构。1）单链表这是动态结构中最简单的一种基本类型，逻辑上仍是一组有序元素的集合，但物理上是无序的。因此，为了保持在线性表中的顺序，除了存储各元素的数据外，还必须保持一个指向下一个元素的指针。在单链表里分配给每个结点的存储单元分为两部分：一部分存放结点的数据，称作值域；另一部分存放指向后继节点的指针，称为链域。上一页下一页返回6.3数据结构终端节点没有后继，它的链域（link）为NULL（图中用^表示空域，在计算机中可以表示成零和负数），另外还需要一个表头指针head，保存第一个结点的地址。链表就是通过指针保证了逻辑上的有序性。单链表存储结构如图6-7所示。在单链表中经常要执行的运算，也就是在一般向量中要执行的运算，只是实现方法和顺序存储不同。在向量中访问一个节点，只要根据给出的下标变量值直接可以存取任一元素，在链表中，必须从head所指出的节点开始，沿着link域所组成的链一个一个节点往下查找，直到第i个节点为止，因此，查找Ki

节点所需要的时间代价与i的大小成正比。上一页下一页返回6.3数据结构在单链表上可以定义以下运算：（1）查找Ki节点;（2）删除Ki节点;（3）在Ki节点后插入新节点；（4）打印Ki节点前驱点和后继点；（5）重新排序单链表中的节点（按递增或递减）。在单链表中实现删除操作是方便的，只需要改变Ki-1

节点的link域，使其指向Ki+1节点，如图6-8所示。当删除第一个节点时，要修改头指针head。上一页下一页返回6.3数据结构实现插入操作只需要修改Ki

节点的链域，使其指向新节点，而新节点的链域指向Ki+1节点，如图6-9所示。当i=0作为第一节点插入时要修改头指针head。按一定规则重新排列单链表中的节点，如要求值域数据递增（或递减）重排。在重排过程中，链域部可以不修改，只需要交换值域。2）循环链表对单链表稍作修改，把它最后一个节点的指针不为空域（^）而让它指向第一个节点，这就得到了循环链表。上一页下一页返回6.3数据结构图6-10为单循环链表示意图，使用图6-10（a）结构时，为了找到最后一个节点，则必须从表头head出发访问每一个节点，如果改用表尾tail指针，保存指向终端节点的地址，从Kn

的link域立即可以得到节点Ki，如图6-10（b）所示。这样，无论是查找第一个节点还是查找最后一个节点都很方便，所以在使用中多采用后一种方式。循环列表的优点是：从循环表任一节点出发都能访问到所有的节点。在循环链表中的插入和删除运算类似于单链表。3）双向循环链表上一页下一页返回6.3数据结构上两节讨论的两种链表，从任何一个节点的链域可以直接得到后继节点，但不能直接找出它的前驱节点。如果在每一个节点中增加一个指向前驱节点的指针，就得到双向循环链表。图6-11为双向循环链表的示意图。在实际应用中还可以根据运算的要求设计各种不同的双向循环链表。同单链表相比较，在双链表中除了多占用存储空间外，在进行查找、插入和删除运算时都比较方便。4）链式栈和链式队列当存储器只有许多不连续的小块存储空间可用时，可以动态地分配给栈和队列使用。上一页下一页返回6.3数据结构用“链”连接构成的栈和队列叫做链式栈和链式队列，或称为离散栈和离散队列。6.3.3树和二叉树树形结构是非线性数据结构的重要形式，在计算机科学及软件工程中有极其广泛的应有，它可以表示一些复杂的层次（分支）结构。例如，在编译程序中，可以用树来表示源程序的语法结构；在数据库系统，可以用树来组织信息等。1．树的概念及术语树（Tree）T是n（n>0）个点的有限集合，任何一个非空树都满足如下两个条件：上一页下一页返回6.3数据结构（1）有且只有一个特定的称为根的节点；（2）除根以外的其余节点被分成m（m>0）个不相交的有限集合，T1，T2，…，Tm，其中每一个集合又是一棵树，并且是称为根的子树。由上述可知，树的递归定义阐述了树的固有属性，即一棵树由若干子树构成，而子树又由若干更小的子树构成。如图6-12所示。树是由根节点、分支节点、叶节点和树枝组成。（1）根节点：树中最上面的节点叫“树根节点”，简称“根”。（2）分支节点：至少有一棵子树的节点，成为分支节点或非终端节点（即至少有一个后继节点的节点）。上一页下一页返回6.3数据结构（3）叶节点：没有子树的节点称为叶节点或终端节点（即没有后继节点的节点）。（4）树枝：两个节点之间的连线称为树枝，简称“枝”。（5）树的层次：从根算起，跟节点的层次为1；沿树可以从根节点直接到达的节点层次为2；从层次2直接到达的节点层次为3，其余类推。（6）树的深度：在数中节点最大层次，成为这棵树的深度。（7）度：一个节点的子树的个数成为该节点的度。（8）树的度：在树的节点中最大的度称为树的度。上一页下一页返回6.3数据结构树形结构中常使用家族树的一些惯用词。（1）节点的孩子：节点的子树的根称为该节点的孩子。（2）节点的双亲：孩子的根为双亲.（3）兄弟：同一个双亲孩子之间称为兄弟。（4）祖父：孩子双亲的双亲称为祖父。（5）祖先（长辈）：一个节点的祖先是指从根到该节点的路径上所有的节点。（6）堂兄弟：双亲在同一层的孩子之间为堂兄弟。2．树的逻辑结构和物理结构上一页下一页返回6.3数据结构树逻辑结构除图6-12表示方法以外，还可以用圆括号表示为广义表：（A（B（D，E），C（F，G（J），H）））其表示方法归纳如下：首先将根点放入表中，把它的子树用圆括号括起来，按从左到右的次序依次放入表中，且以逗号分开，对子树也采用同样方法处理。该表显示了树的层次。树的物理结构一般由多重链表、双重链表、三重链表3种形式实现。3．树结构的应用上一页下一页返回6.3数据结构树结构有着广泛的应用，下面列举它的几个方面的应用。（1）常用树结构来定义层次关系。（2）有序树可以指明节点的子树间的某种顺序关系。（3）判定树。树的另一种非常有价值的应用是进行判断。4．树的操作在使用树结构时经常进行如下的操作：（1）查找树中具有某种性质的节点。（2）按某种次序搜索树中全部节点。（3）找出树中某个节点的前驱节点。（4）找出树中某个节点的后继节点。上一页下一页返回6.3数据结构（5）从已知树中除去某一棵子树。（6）用某棵树去替换指定的叶。5．二叉树1）二叉树的概念二叉树是度为2的有序树。在树结构的应用中，二叉树起着特别重要的作用。一般树很容易的转换化成二叉树的表示。定义：二叉树由节点有限集合构成，这个有限集合或者为空集，或者由一个根节点及两个不相交的分别称为左子树或右子树的二叉树（它们也是节点的集合）组成。上一页下一页返回6.3数据结构这是个递归的定义。二叉树可以是空集合，根可以是有空的左子树或右子树，或者左右子树皆为空。图6-17表示二叉树5种基本形式。二叉树不是树的特殊情形，树和二叉树之间的区别是：（1）树至少要有一个节点，树中每个节点可以有0、1、2、…，棵子树；（2）二叉树可以是空集，二叉树的节点的子树最多只有两棵（即度<=2），并区分为左子树和右子树，图6-17中（c）和（d）为两棵不同的二叉树，但如果是树，它们就是相同的树。二叉树的概念非常重要。上一页下一页返回6.3数据结构首先，从许多实际问题中抽象出来的数据结构往往是二叉树形式，而且许多算法问题用二叉树形式来解决非常简单方便。2）二叉树的性质性质1:在二叉树中，第i层的节点数最多为2i-1

（i>=1），其深度为k的二叉树的节点总数最多为2k-1个（k>=1）。性质2:对任一棵二叉树，如果叶节点数为n0，而其度为2的节点数为n2，则n0=n2+1k=log2(n)+1上一页下一页返回6.3数据结构性质4:如果有n个节点的顺序二叉树（其深度k=[log2(n)]+1），则对任意节点i，1≤i≤n，有:（1）若i≠1，则i的双亲是[i/2]；若i=1，则i是根，无双亲。（2）若2i≤n，则i的左孩子是2i；若2i>n，则i无右孩子。（3）若2i+1≤n，则i的右孩子是2i+1；若2i+1>n，则i无右孩子。对于满二叉树或顺序二叉树，可用向量表示。一般情况下，采用链接存储方法。3）周游二叉树上一页下一页返回6.3数据结构周游二叉树也称为遍历二叉树，就是按某种规则对二叉树中的每个节点访问一次。在访问每个节点时，可以打印节点的有关信息，也可以对节点进行其他一些操作。对线性结构这是一件容易解决的问题，但二叉树是非线性结构，这就需要找到一个完整而有规则的周游方法，以便得到二叉树中各节点信息的一个线性排序。考虑到二叉树的基本组成部分是（N，L，R），如图6-18所示。如果限定先左后右的次序，则有以下3种主要形式（均为递归定义）：（1）前序周游（NLR）：先访问根，然后按前序周游左子树，再按前序周游右子树。上一页下一页返回6.3数据结构（2）中序周游（LNR）：按中序周游左子树，再处理根，最后按中序周游右子树。（3）后序周游（LRN）：按后序周游左子树，再按后序周游右子树，最后处理根（以图6-19为例）。栈是实现递归的最常用的结构，所以对于递归定义的二叉树周游运算，最自然的实现方式是利用一个栈来记下尚待周游的节点或子树，以备以后访问。下面简单讨论3种周游的算法。（1）前序周游算法：从已知二叉树的根节点开始访问，处理完根节点后，只要有左子树就应该继续向左访问，但同时应把该节点的右子树（如果存在的话）的指向进栈保存，以便左子树访问完后进一步按前序访问右子树。上一页下一页返回6.3数据结构（2）中序周游算法：在中序周游时首先查看该节点是否有左子树，如果有的话，则应向左继续搜索下去，直到左子树叶节点为止。待中序处理完该节点的左子树后，于访问该节点，然后，转向右子树进行搜索，并以同样方法处理右子树的每个节点。这样，在每次找到一个节点后，应该先把该节点进栈保存，待处理完该节点的左子树返回时再访问该节点。（3）后序周游算法：在后序周游时，先查看该节点的左子树（如果存在的话），在按后序访问该节点的左子树时，该节点应该进栈保存，以便返回时再进一步按后序访问它的右子树。由于后序周游最后一步是访问该节点，所以在转向按后序访问它的右子树时，该节点仍应该进栈保存。上一页下一页返回6.3数据结构这样，在后序周游二叉树时，树中每个节点必须进栈两次，并且只有在访问完该节点的右子树后（左子树已访问过）才能访问该节点。为了区别当前正在访问该节点的是左子树还是右子树这两种情况，在两次进站时对该节点加以不同标志，以表示当前正在处理它的是左子树还是右子树。二叉树上的前序、中序、后序周游有很大的用途。如果我们把算术表达式构成二叉树的形式，那么对二叉树的前序、后序周游，它的输出结果就是相应的简单算术表达式的前缀和后缀表达式的形式。6.3.4图1．图的定义及基本术语上一页下一页返回6.3数据结构图的定义：一个图G由两个集合V和E组成，V是有限的非空顶点集，E是有限边集，分别用V（G）和E（G）表示顶点集和边集，G=（V，E）表示图。在图中的节点可以称为图的顶点。图的逻辑结构可以这样描述：设数据结构B=（K，R），K为节点的有限集合，R为K上的一个任意关系。如果对于K中节点相对于关系R的前驱、后继节点个数不加限制，则B成为图结构。图中的有关术语：（1）边：在图G中，若有（K，K‘）∈E（G），则称K与K’之间存在一条边。上一页下一页返回6.3数据结构若（K，K‘）是有序偶，则称K与K'之间有一条有向边，用﹤K，K'﹥表示，边的起点为K，终点为K'。（2）有向图：在图G中，对每一个二元组（K，K‘）∈E（G）都是有序偶，则称具有这种关系的图G为有向图。（3）无向图：在图G中，对每一个二元组（K，K‘）∈E（G）都是无序偶，则称具有这种关系的图G为无向图。（4）节点的度：就是与该节点有关联的边的数目。（5）图的度：指图中各节点度数的最大值。图G3是一个度为3的图。（6）叶：指的是图中的终端节点（即没有后继节点）。在有向图中终端节点的出度为0。图G3中V3位叶节点。上一页下一页返回6.3数据结构（7）子图：图G=(V,E)，G'=(V',E')中，若V'V，E'E，并且E'中的边所关联的节点都在V'中，则称G'是图G的子图。（8）路径：在图G=(V,E)中，如果存在节点序列Vp,Vi1,Vi2,…,Vin,Vg,使得<Vp，Vi1>，<Vi1，Vi2>，…，<Vin，Vg>都在E中（若对有向图，则使得<Vp，Vi1>，<Vi1，Vi2>，……,<Vin，Vg>都在E中），则称从节点Vp到节点Vg存在一条路径。路径长度定义为这条路径上的边数。（9）简单路径：如果在一条路径上的节点除Vp和Vg可以相同外，其他节点都不相同，则称此路径为简单路径。上一页下一页返回6.3数据结构（10）圈（环）：若路径上第一个节点和最后一个节点相同，即Vp=Vg，则称此简单路径为圈（也称为环或回路）。（11）有根图：在图中至少有一个节点V，从V出发可以到达图中任何一个节点，即V到每个节点都有路径，则称图为有根图，V是图的根。图6-23为有根图。根为V1。（12）连通图：对无向图G=(V,E)而言，如果V1到V2有一条路径（从V2到V1也一定有一条路径），我们称V1和V2是连通的。若图G中任意两个节点Vi和Vj（Vi≠Vj）都是连通的，则称无向图G是连通图。图6-21中G1和G2是连通图。（13）连通分量：无向图G中的连通分量是G中的极大连通子图。上一页下一页返回6.3数据结构图6-24所示的G1的两个子图H1和H2组成的图G4是不连通的，而H1和H2是连通的，称它们为G4的连通分量，即为图G4的极大连通子图。（14）强连通子图：对有向图G=（V，E）而言，若对于G中任意两个节点Vi和Vj（Vi≠Vj），都有一条从Vi到Vj的有向路径，同时还有一条从Vj到Vi的有向路径，则称有向图G是强连通图。图6-21中G3不是强连通图，因为从V3到V2不存在路径。若图6-23中加上V4到V1的有向路径，则此有根图为强连通图。（15）强连通分量：有向图中极大的强连通子图称为强连通分量。G3的强连通分量如图6-25所示。上一页下一页返回6.3数据结构（16）加权图：给图中每条边加上带数字的权，称为加权图。带权的连通图又称为“网络”。如图6-26所示。图是一种非常有用的数据结构。因为图的结构复杂而使用广泛，所以其存储表示方法也是多种多样的，对应于不同的应用问题有不同的表示方法，常用的有相邻矩阵、邻接表和邻接多重表等。2．图的周游和生成树周游图的定义：对一个图G，从图中任意一个节点V0出发，系统地访问G中所有的节点，且只访问一次，称为图的周游。上一页下一页返回6.3数据结构图的周游比树的周游复杂，因为图中任意一个节点可以和其余任何节点相邻接，故在访问了某个节点后，可能顺着某条路径又一次访问该节点，为了避免多次访问，故增加了一个标志mark，当mark=i时，表示第i个节点已访问过。常用的图的周游方法有：（1）纵向优先搜索法（即按深度方向周游）：从起点V0开始，访问节点V0，然后选取与V0邻接的未被访问的任一顶点V1，访问V1后，再从V1出发，按深度方向周游，再选取与V1邻接的未被访问的任一个节点，重复上述过程，当遇到一个所有邻接节点都访问过的节点时，上一页下一页返回6.3数据结构回到已访问节点序列中最后一个还有未被访问的相邻节点的节点w，再从w出发按深度方向周游，最后，当任何已被访问过的节点都不存在未被访问的相邻节点时，周游结束。（2）横向优先搜索法（即按宽度方向周游）：从图中某个节点V0出发，访问节点V0，然后访问与该节点相邻的全部节点V1,V2,…,Vt，然后再依次访问与V1,V2,…,Vt相邻接的所有未被访问过的节点，如此进行下去，直到访问完所有的节点为止。上一页返回6.4数组6.4.1数组概念数组是一组相同类型的变量的集合，它不是一种数据类型。在VB中有两种类型的数组，即变量数组和控件数组。变量数组又分为静态（定长）数组和动态（不定长）数组。6.4.2数组的声明数组要先声明后使用，声明就是定义数组的名字、维数和类型。1）静态数组格式：Dim<数组名>（<维数>）[As<类型>]功能：定义一个数组，并为其分配存储空间。下一页返回6.4数组说明：（1）数组名的命名规则与简单变量相同。（2）<维数>定义数组的大小。其形式为：[<下标下界1>To]<下标上界>,[<下标下界2>To<下标上界2>]，…下标的范围为-2147483648~2147483647，默认的下标下界为0，也可由OptionBase1指定为1。只有一个下标的数组为一维数组，有两个及两个以上下标的数组为多维数组。上一页下一页返回6.4数组（3）如指定数据类型，则数组元素都具有相同的数据类型；如不指定数组类型，则默认为变体类型，这是数组中的元素可以有不同的数据类型。2）动态数组动态数组在声明时未给出维数，在使用数组时根据实际情况再决定数组大小，这样可以节省内存。建立动态数组的方法为：（1）在声明数组时不给出具体维数，如：Dima（）AsInteger。（2）在过程中用Redim语句确定数组的大小，如Redima（1To20）。上一页下一页返回6.4数组6.4.3数组赋值在用Dim语句给出数组声明之后，数值型数组的元素都初始化0，字符型数组的元素都初始化为空。我们在使用数组时都要给它赋予一定的初值，给数组赋初值常用以下方法：1）用循环语句给数组赋值2）用Array函数给数组赋值数组变量名=Array（arglist）对数组元素的使用需给出变量名和下标3）通过文本控件或InputBox（）函数赋值4）数组间赋值上一页下一页返回6.4数组VB6.0提供了可对数组整体赋值的新功能,方便了数组对数组的赋值操作。但真正使用不那么方便,有不少限制。数组赋值形式如下:数组名2=数组名16.4.4数组的算法数组是程序设计中使用最多的数据结构。将数组元素的下标和循环语句结合使用，能解决大量的实际问题。关键是要掌握数组下标与循环变量之间的关系。需要注意的是，数组定义时用数组名表示该数组的整体，但在具体操作时是针对每个数组元素进行的。上一页下一页返回6.4数组1．数组排序排序是将一组数按递增或递减的次序排列。排序的算法很多（详见6.5节），此处着重介绍数组操作时，数组下标如何与循环变量进行有机的联系。2．分类统计分类统计是经常遇到的运算，是将一批数据中按分类的条件统计每一类中包含的个数。3．大量数据的输入和编辑6.4.5控件数组1．控件数组的概念上一页下一页返回6.4数组控件数组就是具有相同名称和类型的一组控件。每个控件都有唯一的一个索引号（Index），以此来区分不同的控件。使用控件数组添加控件所消耗的资源比直接向窗体添加多个相同类型的控件所消耗的资源要少，控件数组可以共享同样的事件过程。在系统运行中，可以利用系统返回的索引值来识别事件是由哪个控件引发的。另外，若要在运行时创建新控件，则新控件必须是控件数组的成员，没有控件数组机制是不可能在运行时创建新控件的。使用控件数组时，每个新成员都继承数组的公共事件过程。2．控件数组的建立上一页下一页返回6.4数组可以使用下列方法之一来创建控件数组：（1）给控件起相同的名字。（2）复制现有的控件。（3）将控件Index的属性设置为非Null数值。下面介绍用第一种方法建立控件数组：（1）画出控件数组中要添加的控件，并确定哪一个控件是数组中的第一个控件。（2）将选定控件的Name属性设置为数组名。（3）在为数组中的其他控件输入相同名称时，VB将显示一个对话框，问是否要创建控件数组，此时要选择“是”上一页返回6.5排序6.5.1排序概述排序是指将一组任意排列的关键字按照指定的次序重新排列的过程。排序的目的是为了更快速和更方便的查找到指定的关键字。排序操作是计算机系统的基本操作。一般根据排序操作执行的地方不同分为两类：（1）内部排序：在计算机内存中进行，不需要访问外存就可完成的排序。（2）外部排序：参加排序的记录量很大，需要在计算机外存中进行的排序。上一页下一页返回6.5排序内部排序方法如图6-33所示：一般来说，在排序过程中有两种基本操作：一是比较两个关键字的大小；二是移动记录位置。前一种操作对大多数排序方法都是必要的，而后者可通过改变记录的存储方式来避免。待排序记录通常有3种存储结构：（1）以数组为存储结构的顺序存储方法，排序过程通过记录的多次比较和移动来实现；（2）以链表为存储结构的链式存储方法，排序过程无需移动记录，只需比较关键字和修改指针即可，一般把这类排序称为表排序；上一页下一页返回6.5排序（3）一些排序方法不宜在链表上实现，若仍需避免移动记录，则可建立一个辅助表来登记建立的关键字和存储地址等信息，排序过程只针对辅助表进行，不需移动记录本身。衡量评价不同排序方法的优劣有两点：一是在数据规模一定的条件下，算法执行所耗时间，一般高效算法应尽可能少的比较次数和数据元素移动次数；二是执行算法所需要的辅助存储空间。理想的空间效率是算法执行期间所需要的辅助空间与待排序的数据量无关。6.5.2排序方法1．冒泡排序上一页下一页返回6.5排序冒泡排序时一种简单的排序方法。它的基本思想是通过比较相邻两个元素来决定是否需要进行交换，通过交换把关键字较小的元素由底部向顶部移动（如同气泡在水中的运动），这样关键字较大的元素由顶部向底部移动。具体来讲，冒泡就是从R数组（n个元素）的下标值较大的存储位置移到下标值较小的存储位置。冒泡排序的关键操作：（1）冒泡趟数：首先将第一个元素与第二个元素进行比较，若为逆序，则要交换，然后比较第二个与第三个元素。依此类推，直到第n-1个和第n个记录为止。经过此趟处理，目前最大元素被移动到数组最后一个位置上。然后对前n-1个元素进行类似的处理，直至对前2个元素处理为止。上一页下一页返回6.5排序总共进行了n-1遍处理，所以外循环变量i从1开始到n变化。（2）每一趟冒泡操作都会减少一个比较元素，这体现在内循环变量j会根据外循环变量i的值决定循环比较次数。（3）如果相邻元素是否交换取决于比较符，若相等也要交换，则排序是不稳定。冒泡排序方法算法：上一页下一页返回6.5排序2．选择顺序（直接选择排序）选择顺序也是一种简单排序方法。它的基本思想是在每一遍处理中选择出关键字最小的元素，与其最后对应位置的元素交换。直接选择排序的基本过程是：从所有n个元素中选择出关键字最小的元素，作为有序序列的第一个元素，与第一个元素交换，这是第一遍处理。接着再从n-1个记录中选择出最小的元素与第2个元素交换，以此类推。经过n-1遍处理之后，次大元素在n-1号位置，最大元素在n号位置，排序过程结束。直接选择排序的关键步骤：（1）选择最小值的开始位置i，从1开始到n，每趟减少一个数据。上一页下一页返回6.5排序（2）确定每趟查找的范围，从j到n。（3）在每趟选择过程，只要发现有比当前最小元素min小的元素，立