|
|
|
21世纪以来，计算机科学和软硬件技术得到了飞速的发展，计算机应用领域也从最初的科学计算逐步发展到了人类活动的各个领域，人们已经认识到，计算机知识已成为人类当代文化的一个重要组成部分。今天，计算机的应用已经渗透到了生活中的各个领域，无处不在。要开发出一种性能良好的软件，不仅需要根据实际的需要掌握至少一种适合的计算机高级语言或者软件开发工具，也要通过比较和分析选出较好的设计方案才可以，这正是数据结构和算法要解决的问题。
|
|
|
|
本章通过对数据结构的基础、线性表、栈、数组、树和图以及算法的描述和评价等内容，简要介绍了数据结构和算法的基础知识。
|
|
|
|
|
|
|
|
随着计算机技术的飞速发展，再把计算机简单地看作是进行数值计算的工具，把数据仅理解为纯数值性的信息，就显得太狭隘了。现代计算机科学的观点，是把计算机程序处理的一切数值的、非数值的信息，乃至程序统称为数据（Data），而电子计算机则是加工处理数据（信息）的工具。
|
|
|
|
由于数据的表示方法和组织形式直接关系到程序对数据的处理效率，而系统程序和许多应用程序的规模很大，结构相当复杂，处理对象又多为非数值性数据。因此，单凭程序设计人员的经验和技巧已难以设计出效率高、可靠性强的程序。于是，就要求人们对计算机程序加工的对象进行系统的研究，即研究数据的特性以及数据之间存在的关系——数据结构（Date Structure）。
|
|
|
|
计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法（Algorithm）,最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。
|
|
|
|
计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。
|
|
|
|
|
|
|
|
数据（Data）是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。
|
|
|
|
数据元素（Data Element）简称元素，是数据的基本单位，通常作为一个整体进行考虑和处理。对于一个文件而言，每个记录就是它的数据元素；对于一个字符串而言，每个字符就是它的数据元素。数据和数据元素是相对而言的。有时，一个数据元素可以由若干个数据项（Data Item）组成。
|
|
|
|
数据记录（Data Record）简称记录，它是数据处理领域组织数据的基本单位，数据中的每个数据元素在许多应用场合被组织成记录的结构。一个数据记录由一个或多个数据项组成，每个数据项可以是简单数据项，也可以是组合数据项。
|
|
|
|
关键项（Key Item）指的是在一个表或者文件中，若所有记录的某个数据项的值都不同，也就是每个值能唯一标识一个记录时，则可以把这个数据项作为记录的关键数据项，简称关键项。其中关键项的每一个值称做所在记录的关键字（Key Word或Key）。
|
|
|
|
数据处理（Data Processing）是指对数据进行查找、插入、删除、合并、排序、统计、简单计算、转换、输入、输出等的操作过程。
|
|
|
|
数据结构（Data Structure），简单地说，指数据以及相互之间的关系。它是研究数据元素（Data Element）之间抽象化的相互关系和这种关系在计算机中的存储表示（即所谓数据的逻辑结构和物理结构），并对这种结构定义相适应的运算，设计出相应的算法，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。
|
|
|
|
数据类型（Data Type）是对数据的取值范围、每一数据的结构以及允许施加操作的一种描述。换言之，它是一个值的集合和定义在这个值集上的一组操作的总称。
|
|
|
|
数据对象（Data Object）简称对象，是性质相同的数据元素的集合，是数据的一个子集。如25为一个整形数据对象，‘A’为一个字符数据对象等。
|
|
|
|
除了上述常见概念之外，数据结构还有许多别的概念，例如算法、线性结构、集合、图、树等，这些都将在以后的章节中一一介绍。
|
|
|
|
|
|
算法（algorithm）就是解决特定问题的方法。描述一个算法可以采用文字描述，也可以采用传统流程图、N-S图或PAD图等。作为一个算法应该具备以下5个特性：
|
|
|
|
|
|
.确定性。算法的每一步都应该具有确切的含义，没有二义性。
|
|
|
|
|
|
|
|
.输出。一个算法执行结束后至少要有一个输出量，表示算法对输入量进行运算和处理的结果。
|
|
|
|
注意，算法和程序是有区别的——程序未必能满足有穷性。在本书中，只讨论满足动态有穷的程序，因此“算法”和“程序”是通用的。
|
|
|
|
算法可以借助各种工具描述出来。一个算法可以是用自然语言、数字语言或约定的符号来描述，也可以用计算机高级程序语言来描述，如流程图、Pascal语言、C语言、伪代码或决策表等。下面以从n个元素中查找最大值为例，来讲解用流程图和伪代码这两种常见方法对算法的不同描述：
|
|
|
|
|
|
从n个整数元素中查找出最大值，若用流程图描述如下图所示。
|
|
|
|
|
|
|
|
|
|
除了可以用流程图描述之外，还可以用伪代码来进行描述。
|
|
|
|
|
|
|
|
一般地说，设计一个“好”的算法应该考虑达到以下目标。
|
|
|
|
（1）正确性（correctness）。算法应该是满足具体问题的需求。
|
|
|
|
（2）可读性（readability）。算法主要是为了便于人的阅读和交流。可读性好的算法有利于人的理解。
|
|
|
|
（3）健壮性（robustness）。指的是，当输入数据非法时，算法也能适当地做出反应或对它进行处理，而不会产生莫名其妙的输出结果。
|
|
|
|
（4）效率和低存储量需求。效率指的是算法执行的时间。对于同一个问题，执行时间短的算法效率高。存储量需求指的是算法执行过程中所需要的最大存储空间。
|
|
|
|
一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上，所需资源越多，该算法的复杂性越高；反之，所需资源越少，该算法的复杂性越低。其中最重要的就是算法的时间复杂性和空间复杂性。
|
|
|
|
一般情况下，算法中的基本操作重复执行的次数是问题规模n的某个函数f（n），算法的时间量度记作
|
|
|
|
|
|
它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同，称做算法的渐进时间复杂度（Asymptotic Time Complexity），简称时间复杂度。被称为问题的基本操作的原操作应是其重复执行次数和算法的执行时间成正比的原操作。语句的频度（Frequency Count）指的是该语句重复执行的次数。
|
|
|
|
和算法的时间复杂度类似的，空间复杂度（Space Complexity）指的是算法所需存储空间的量度，记作：
|
|
|
|
|
|
其中，n为问题的规模或大小。根据算法的时间复杂度和空间复杂度，可以对算法进行评价。
|
|
|
|
|
|
在计算机领域，一个算法实质上是针对所处理的问题的需要，在数据的逻辑结构和存储结构的基础上施加的一种运算。由于数据的逻辑结构和存储结构不是唯一的，在很大程度上可以由用户自行选择和设计，所以处理同一问题的算法也并不是唯一的。况且，即使是相同的逻辑结构和存储结构，算法的设计思想和技巧也不一定相同，编写出来的算法也大不相同。
|
|
|
|
学习数据结构就是要学会根据数据处理问题的需要，为待处理的数据选择合适的逻辑结构和存储结构，进而按照结构化、模块化以及面向对象的程序设计方法设计出比较满意的算法。
|
|
|
|
|
|
|
|
线性表（linear_list）是最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。一个数据元素可以由若干个数据项（item）组成，通常称为记录（record）,含有大量记录的线性表又被称为文件（file）。设序列中第i个元素为ai（1≤i≤n），则线性表一般表示为：
|
|
|
|
（a1,a2,…,ai-1, a?, ai+1，…，an）
|
|
|
|
其中，ai-1在均ai的前面，称为ai的直接前驱元素。ai+1在ai的后面称为ai的直接后继元素。线性表中元素的个数n（n≥0）称为线性表的长度。当n=0时，线性表成为空表。
|
|
|
|
一个线性表也可以用标志符来命名，例如用A命名上面的线性表，则：
|
|
|
|
A=（a1, a2,…,ai-1,ai, ai+1,…, an）
|
|
|
|
|
|
|
|
|
|
数据对象A=｛ai| 1≤i≤n,n≥0，ai为数据元素｝
|
|
|
|
数据关系R=｛i, ai+1>| 1≤i≤n-1｝
|
|
|
|
|
|
|
|
|
|
线性表是一个非常灵活的数据结构，对线性表的数据元素不仅可以访问，还可以对其进行诸如插入、删除等操作。因此，线性表的抽象数据类型包括了数据对象和数据关系两大部分，抽象数据类型的线性表定义如下所示：
|
|
|
|
|
|
|
|
线性表的存储结构有顺序、链接、散列等多种方式，顺序存储结构是其中最简单、最常见的一种。线性表的顺序存储结构就是用一组地址连续的存储单元依次存储线性表中的所有元素。因此，假设一个线性表中的每个元素需要占用k个存储单元，并且以该元素的第一个存储单元的地址作为该元素的存储位置。线性表中的第i个元素和第i+1个元素的存储位置有如下关系：
|
|
|
|
|
|
也就是说：LOC（ai）=LOC（a1）+（i-1）*k；
|
|
|
|
线性表的特点就在于它为线性表中相邻元素赋以了相邻的存储位置。只要确定了线性表的起始位置，就可以获得线性表的任意元素的存储位置。它的顺序存储结构图如下图所示。
|
|
|
|
|
|
|
|
为了便于线性表的操作，可以用记录类型来定义一个线性表List：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
线性表的顺序存储结构使得线性表的存储位置可以用一个简单、直观的公式来表示，但是在插入或删除操作的时候，需要移动大量的元素，十分不便。链式存储结构弥补了它的这个缺点。链式存储结构的特点是可以用一组任意的存储单元来存储线性表中的元素的存储结构，这些存储单元可以连续，也可以不连续。所以，为了表示数据元素ai与它的直接后继元素ai+1的逻辑关系，除了元素ai的基本信息之外，还存储了一个可以指明它的直接后继元素ai+1的存储位置的内容。它们共同组成ai的存储映像，称为结点（node）。存储元素ai的信息，被称为数据域，存储直接后继元素的存储位置的域，被称为指针域。n个结点（ai（1≤i≤n））组成一个链表，也就是线性表（a1，a2，…, an）的链式存储结构。其结构示意图如下图所示。
|
|
|
|
|
|
|
|
上图分别画出了链表的三种不同链式存储结构。若一个指针域的值为空，则在图形中通常用符号“Λ”表示，由于线性表中的第一个元素没有前驱元素，最后一个元素没有后继元素，所以用“Λ”表示。
|
|
|
|
循环链表是另一种形式的链式存储结构，它的特点是表中的最后一个结点的指针域指向头结点，整个链表形成一个环状结构，从表中任意一个结点出发都可以到达其他节点。操作与线性链表基本一致。
|
|
|
|
|
|
|
|
栈（Stack）是一种特殊的线性表，是限定仅在表尾进行插入或者删除操作的线性表。进行插入和删除的那一端称为栈顶（top），另一端称为栈底（bottom）。栈的插入操作和删除操作也分别简称进栈和出栈。
|
|
|
|
如果栈中有n个结点｛k0，k1，k2，…, kn-1｝，k0为栈底，kn-1是栈顶，则栈中结点的进栈顺序为k0, k1, k2，…，kn-1，而出栈的顺序为kn-1, kn-2，…, k1,k0，如下图所示。
|
|
|
|
|
|
|
|
栈的主要操作是桟的初始化、插入和删除运算、判断栈是否为空以及读取栈顶结点的值等操作。栈的类型的描述如下：
|
|
|
|
|
|
和顺序表类似，栈的实现方式一般也有两种：顺序存储和链式存储。下面主要介绍顺序栈。由于栈的顺序存储方式就是在顺序表的基础上对插入和删除操作限制，使得它们仅能在顺序表的同一端进行，所以同顺序表一样也可用一维数组表示。一般地，可以设定一个足够大的一维数组存储栈，数组中下标为0的元素就是栈底，对于栈顶，可以设一个指针top指示它。为了方便，设定top所指的位置是下一个将要插入的结点的存储位置，这样，当top=0时就表示是一个空的栈。一个栈的几种状态以及在这些状态下栈顶指针top和栈中结点的关系如下图所示。
|
|
|
|
|
|
|
|
|
|
|
|
顺序存储栈的几个基本操作的具体实现，具体如下所示：
|
|
|
|
|
|
|
|
表达式求值是程序设计语言编译中的一个最基本问题。它的实现方法是栈的一个典型的应用实例。
|
|
|
|
在计算机中，任何一个表达式都是由操作数（operand）、运算符（operator）和界限符（delimiter）组成的。其中操作数可以是常数，也可以是变量或常量的标识符；运算符可以是算术运算体符、关系运算符和逻辑符；界限符为左右括号和标识表达式结束的结束符。在本节中，仅讨论简单算术表达式的求值问题。在这种表达式中只含加、减、乘、除四则运算，所有的运算对象均为单变量。表达式的结束符为“#”。
|
|
|
|
|
|
|
|
中缀表达式是通常使用的一种表达式，中缀表达式的计算规则如下。
|
|
|
|
（1）括号内的操作先执行，括号外的操作后执行。如有多层括号，则先执行内层括号内的操作，再执行外括号内的操作。
|
|
|
|
|
|
（3）在有多个乘除或加减运算可选择时，按从左到右的顺序执行，即优先级相同的操作符按先后次序进行。
|
|
|
|
|
|
后缀表达式中只有操作数和操作符，它不再含有括号，操作符在两个操作数之后。它的计算规则非常简单，严格按照从左向右的次序依次执行每一个操作。每遇到一个操作符，就将前面的两个操作数执行相应的操作。
|
|
|
|
|
|
队列（queue）是一种只允许在一端进行插入，而在另一端进行删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入的一端称为队尾（rear），只允许进行删除的一端称为队头（front）。队列的插入操作通常称为入队列或进队列，而队列的删除操作则称为出队列或退队列。当队列中无数据元素时，称为空队列。队头元素总是最先进队列的，也总是最先出队列；队尾元素总是最后进队列，因而也是最后出队列。这种表是按照先进先出（FIFO，first in first out）的原则组织数据的，因此，队列也被称为“先进先出”表。下面用C语言描述队列类型为：
|
|
|
|
|
|
队列分为链队列和循环队列。链队列主要采取顺序存储方式，下面主要介绍链队列的顺序存储。队列的顺序存储在c语言中可以用一维数组表示，为了标识队首和队尾，需要附设两个指针front和rear，front指示的是队列中最前面，即队首结点在数组中元素的下标，rear指示的是队尾结点在数组中元素的下标的下一个位置，也就是说rear指示的是即将插入的结点在数组中的下标。下图所示的是队列的几种状态：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
链队列还有链式存储结构，与顺序表的链式存储结构类似。循环队列的操作与链队列相似，这里就不再累述了。
|
|
|
|
|
|
|
|
数组是大家都已经很熟悉的一种数据类型，几乎所有高级语言程序设计中都设定了数组类型。数组可以看成是线性表的推广，数组的每个元素由一个值和一组下标确定，在数组中，对于每组有定义的下标都存在一个与之相对应的值；而线性表是有限结点的有序集合，若将其每个结点的序号看成下标，线性表就是一维数组（向量）；当数组为多维数组时，其对应线性表中的每个元素又是一个数据结构而已。数组使用时需要的内存空间远远大于普通变量的空间，所以按内存开辟空间的时机来划分数组，在程序编译时开辟内存区的数组称为静态数组，运行时根据需要开辟内存区的数组称做动态数组。简单来说，使用数值常量或符号常量定义下标的数组为静态数组，首先声明一个没有下标的数组名，然后在使用时再次声明数组的下标，称为动态数组。用C语言来描述数组如下：
|
|
|
|
|
|
由于数组一般不做插入或删除操作，也就是说，一旦建立了数组，则结构中的数组元素个数和元素之间的关系就不再发生变动，即它们的逻辑结构就固定下来了，不再发生变化。因此，一般采用顺序存储结构表示数组。多维数组的顺序存储有两种形式：以列序为主序和以行序为主序。
|
|
|
|
|
|
行优先顺序也称为低下标优先或左边下标优先于右边下标。具体实现时，按行号从小到大的顺序，先将第一行中元素全部存放好，再存放第二行元素，第三行元素，依次类推……
|
|
|
|
在Basic语言、Pascal语言、C/C++语言等高级语言程序设计中，都是按行优先顺序存放的。例如，对刚才的Am×n二维数组，可用如下形式存放到内存：a00，a01,…a0 n-1, a10，all，…，a1 n-1, …，am-1 0, am-1 1,…，am-1 n-1。即二维数组按行优先存放到内存后，变成了一个线性序列（线性表）。
|
|
|
|
因此，可以得出多维数组按行优先存放到内存的规律：最左边下标变化最慢，最右边下标变化最快，右边下标变化一遍，与之相邻的左边下标才变化一次。因此，在算法中，最左边下标可以看成是外循环，最右边下标可以看成是最内循环。
|
|
|
|
|
|
由于多维数组在内存中排列成一个线性序列，因此，若知道第一个元素的内存地址，如何求得其他元素的内存地址？可以将它们的地址排列看成是一个等差数列，假设每个元素占1个字节，元素aij的存储地址应为第一个元素的地址加上排在aij前面的元素所占用的单元数，而aij的前面有i行（0～i-1）共i×n个元素，而本行前面又有j个元素，故aij的前面一共有i×n+j个元素，设a00的内存地址为LOC （a00），则aij的内存地址按等差数列计算为LOC （aij）=LOC（a00）+（i×n+j）×1。同理，三维数组Am×n×p按行优先存放的地址计算公式为：LOC （aijk）=LOC（a000）+（i×n×p+j×p+k）×1。
|
|
|
|
|
|
广义表是5.2节提到的线性表的推广。线性表中的元素仅限于原子项，即不可以再分，而广义表中的元素既可以是原子项，也可以是子表（即另一个线性表）。它是n≥0个元素a1, a2, …，an的有限序列，其中每一个ai或者是原子，或者是一个子表。广义表通常记为LS=（a1, a2, …，an），其中LS为广义表的名字，n为广义表的长度，每一个ai为广义表的元素。但在习惯中，一般用大写字母表示广义表，小写字母表示原子。
|
|
|
|
|
|
（1）用LS=（a1， a2, …，an）形式，其中每一个ai为原子或广义表。
|
|
|
|
|
|
（2）将广义表中所有子表写到原子形式，并利用圆括号嵌套。
|
|
|
|
|
|
|
|
（3）将广义表用树和图来描述，一个广义表的深度指的是该广义表展开后所含括号的层数。例如，A=（b，c）的深度为1，B=（A，d）的深度为2，C=（f，B,h）的深度为3；如下图所示。
|
|
|
|
|
|
|
|
由于广义表的元素类型不一定相同，因此，难以用顺序结构来存储表中的元素，通常采用链接存储方法来存储广义表中元素，并称之为广义链表。广义表需要两种结构的结点，一种是表结点，表示列表；一种是原子节点，表示原子。一个表结点可以由标志域、指示表头的指针域和指示表尾的指针域组成；而原子结点由标志域和值域组成，如下图所示。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
树（tree）是n（n≥0）个结点的有限集。n=0的树称为空树；当n≠0时，树中的结点应该满足以下两个条件：
|
|
|
|
|
|
（2）其余结点分成m （m≥0）个互不相交的有限集合T1,T2,…,Tm，其中每一个集合又都是一棵树，称T1,T2,…，Tm为根结点的子树。
|
|
|
|
以上定义是一个递归定义，它反映了树的固有特性，因为一棵树是由根和它的子树构成，而子树又是由子树的根和更小的子树构成。如下图所示的树中，A是根结点，其余结点分成三个互不相交的子集：S1=｛B，E，F｝, S2=｛C｝，S3=｛D, G，H，I，J，K｝,这三个集合分别构成了A的三棵子树；在S3构成的子树中，D是根结点，D又具有三棵子树，这三棵子树的根结点分别是G，H和I；对于结点G和I，它们的子树均为空。
|
|
|
|
|
|
|
|
图中树的表示类似于自然界中一棵倒长的树，“树型结构”由此得名，这种表示方法比较形象、直观，因而容易为人们所接受，是树的一种最常用的表示方法。树型结构除以上表示方法外，还有括号表示法、凹入表示法和嵌套集合表示形式。下图给出了上图中树的这三种表示形式。
|
|
|
|
|
|
|
|
在下图的树中，采用线段连接两个相关联的结点，如A和B，D和H等。其中A和D是上端结点，B和H是下端结点。称A、D分别是B、H的双亲（或父母或前件），B和H分别为A和D的子女（或孩子或后件）。由于E和F的双亲为同一结点，称E和F互为兄弟。在任何一棵树中，除根结点外，其他任何一个结点有且仅有一个双亲，有0个或多个子女，且它的子女恰巧为其子树的根结点。将一结点拥有的子女数称为该结点的度，树中所有结点度的最大值称为树的度。称树中连接两个结点的线段为树枝。在树中，若从结点Ki开始沿着树枝自上而下能到达结点Kj，则称从Ki到Kj存在一条路径，路径的长度等于所经过的树枝的条数。在下图中，从结点A到结点J存在一条路径，路径的长度为3；从D到K也存在一条路径，路径的长度为2。将从树根到某一结点Ki的路径中Ki前所经过的所有结点称为Ki的祖先；反之，以某结点Ki为根的子树中的任何一个结点都称为Ki的子孙。下图中，A、D、H均为J和K的祖先，而G、H、I、J和K均为D的子孙。
|
|
|
|
树中结点的层次：从树根开始定义，根结点为第一层，根的子女结点构成第二层，依次类推，若某结点Kj位于第i层，则其子女就位于第i+1层。称树中结点的最大层次数为树的深度或高度。下图中，A结点位于第一层，B、C、D位于第2层，E、F、G、H和I位于第三层等，整棵树的高度为4。
|
|
|
|
|
|
|
|
如果树中任意结点的子树均看成是从左到右有次序的，不能随意交换，则称该树是有序树；否则称之为无序树。如下图所示的两棵树，若看成是有序树，它们是不等价的；若看成是无序树，两者相等。
|
|
|
|
|
|
|
|
由m（m≥0）棵互不相交的树构成的集合称为森林。森林和树的概念十分相近，每个结点的子树的集合即为一个森林；而在森林中的每棵树之上加一个共同的根，森林就成为了一棵树。
|
|
|
|
二叉树（Binary Tree）是另一种树型结构，它的特点是每个结点至多只有两棵子树，在二叉树中不存在度大于2的结点，并且二叉树的子树有左右之分，它的次序是不能任意颠倒的。
|
|
|
|
|
|
存储结构的选择不仅要考虑数据元素如何存储，更重要的是要考虑数据元素之间的关系如何体现。根据数据元素之间关系的不同表示方式，常用的树存储结构主要有三种：双亲表示法、孩子表示法和孩子兄弟表示法。本节主要讨论树的双亲表示法，如下图所示。
|
|
|
|
|
|
|
|
在树中，除根结点没有双亲外，其他每个结点的双亲是唯一确定的。因此，根据树的这种性质，存储树中结点时，应该包含两个信息：结点的值data和体现结点之间相互关系的属性——该结点的双亲parent。借助于每个结点的这两个信息便可唯一地表示任何一棵树。这种表示方法称为双亲表示法，为了查找方便，可以将树中所有结点存放在一个一维数组中，具体类型定义如下。
|
|
|
|
|
|
其中datatype应根据结点值的具体类型给出定义，在此假设为字符型。这里值得一提的是，根结点在树中有着与其他结点不同的地位，树根的位置是非常关键的，正如单链表中抓住了表头指针，就掌握了整个链表一样，树中只要知道树根在哪里，便可以访问到树中所有的结点，因此树的存储结构中要特别考虑根结点的存储。
|
|
|
|
其中parent的值为-1表示结点的双亲不存在。本树中root域的值为0,表示树的根结点存放在数组的第一个元素中。
|
|
|
|
|
|
所谓树的遍历，指按某种规定的顺序访问树中的每一个结点一次，且每个结点仅被访问一次。根据根结点的访问位置不同，树的遍历可以分为前序遍历和后序遍历；又由于树具有层次性，遍历树中结点时可以按层次自上而下访问每个结点，因此树的遍历方式分为以下三种：
|
|
|
|
|
|
首先访问根结点，再依次按前序遍历的方式访问根结点的每一棵子树。
|
|
|
|
|
|
首先按后序遍历的方式访问根结点的每一棵子树，然后再访问根结点。
|
|
|
|
|
|
首先访问第一层上的根结点，然后从左到右依次访问第二层上的所有结点，再以同样的方式访问第三层上的所有结点……最后访问树中最低一层的所有结点。
|
|
|
|
如下图所示的树对其进行三种遍历的结果分别为：前序遍历的结果——ABCEFHIGD；后序遍历的结果——BEHIFGCDA；层次遍历的结果——ABCDEFGHI。
|
|
|
|
|
|
|
|
显然，树的前序遍历和后序遍历的定义具有递归性，因此采用递归方式实现树的前、后序遍历算法十分方便，只要按照其各自规定的顺序，访问根结点时就输出根结点的值，访问子树时进行递归调用即可。以下以指针方式的孩子表示法作为树的存储结构，分别给出树的前序遍历和后序遍历算法的实现。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
图是由一个非空的顶点集合和一个描述顶点之间多对多关系的边（或弧）集合组成的一种数据结构，它可以形式化地表示为：
|
|
|
|
|
|
其中V=｛x|x?某个数据对象集｝，它是顶点的有穷非空集合；E=｛（x，y） |x, y? V｝或E=｛|x，y?V且Path （x, y）｝,它是顶点之间关系的有穷集合，也称为边集合，PathP （x，y）表示从x到y的一条单向通路。
|
|
|
|
通常，也将图G的顶点集和边集分别记为V （G）和E （G）。E （G）可以是空集，若E （G）为空，则图G只有顶点而没有边。
|
|
|
|
若图G中的每条边都是有方向的，则称G为有向图。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。例如，有序对有向边i，vj>表示一条由vi到vj的有向边。有向边又称为弧，也称为边弧，边弧的始点vi称为弧尾（Tail），边弧的终点vj称为弧头（Head）。若图G中的每条边都是没有方向的，则称G为无向图。无向图中的边均是顶点的无序对，无序对通常用圆括号表示。
|
|
|
|
|
|
设G=（V，E）是有n （n31）个顶点的图，在图的邻接矩阵表示法中，可用两个表格分别存储数据元素（顶点）的信息和数据元素之间的关联（边）信息。通常用一维数组（顺序表）存储数据元素的信息，用二维数组（邻接矩阵）存储数据元素之间的关系。
|
|
|
|
|
|
给定图G=（V，E），其中V（G）=｛v0，…，vi, …，vn-1｝，G邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵，G的邻接矩阵是具有如下性质的n阶方阵：
|
|
|
|
|
|
若图中顶点信息是0至n-1的编号，则仅需令权值为1，存储一个邻接矩阵就可以表示图。若是网络，则adjtype为权的类型。由于无向图或无向网络的邻接矩阵是对称的，故可采用压缩存储的方法，仅存储下三角阵（不包括对角线上的元素）中的元素即可。显然，邻接矩阵表示法的空间复杂度S（n）=O（n2）。
|
|
|
|
|
|
给定图G=（V，E）和V （G）中的某一顶点v，从v出发访问G中其余顶点，且使每个顶点位置仅被访问一次，这一过程称为图的遍历。
|
|
|
|
深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法，它们对无向图和有向图均适用。
|
|
|
|
|
|
深度优先搜索（Depth-First Search）的基本思想是：对于给定的图G=（V，E），首先将V中每一个顶点都标记为未被访问，然后，选取一个源点将v标记为已被访问，再递归地用深度优先搜索方法，依次搜索v的所有邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历。如果从v出发有路的顶点都已被访问过，则从v的搜索过程结束。此时，如果图中还有未被访问过的顶点（该图有多个连通分量或强连通分量），则再任选一个未被访问过的顶点，并从这个顶点开始做新的搜索。上述过程一直进行到V中所有顶点都已被访问过为止。
|
|
|
|
|
|
图的广度优先遍历的基本思想是：给定图G=（V，E），从图中某个源点v出发，在访问了顶点v之后，接着就尽可能先在横向搜索v的所有邻接点。在依次访问v的各个未被访问过的邻接点w1，w2，…，wk之后，分别从这些邻接点出发依次访问与w1，w2, …，wk邻接的所有未曾访问过的顶点。依此类推，直至图中所有和源点v有路径相通的顶点都已访问过为止，此时从v开始的搜索过程结束。若G是连通图，则遍历完成；否则，在图G中另选一个尚未访问的顶点作为新源点继续上述的搜索过程，直至图G中所有顶点均已被访问为止。采用广度优先搜索法遍历图的方法称为图的广度优先遍历。
|
|
|
|
为确保先访问的顶点其邻接点亦先被访问，在搜索过程中可使用队列来保存已访问过的顶点。当访问v和u时，这两个顶点相继入队，此后，当v和u相继出队时，分别从v和u出发搜索其邻接点v1，v2，…，vs和u1，u2, …，ut，对其中未访者进行访问并将其入队。这种方法是将每个已访问的顶点入队，保证了每个顶点至多只有一次入队。
|
|
|
