软件技术概论与基础 课件 第4章 数据结构与算法

软件技术概论与基础第4章数据结构与算法学习导入随着计算机的应用领域，不再局限于数值数据的处理，文本、图形、图像等非数值数据的加工处理问题显得越来越重要。如果想要设计出一个结构好、效率高的程序，有效地解决实际问题，就必须研究这些数据的特性、数据之间的关系及其对应的存储表示，从而设计出相应的算法。通过对本章内容的学习，读者将对数据结构的研究内容有一定的了解。思维导图学习目标了解数据结构的研究内容了解线性表的逻辑结构了解栈和队列的定义、特性及应用了解树形结构的特点及二叉树的应用了解图形结构的特点及应用了解常用的操作：查找和排序重点难点学习重点数据结构的概念及研究内容算法的概念及常见算法的实现学习难点常见算法的实现相关知识4.1数据结构的概念4.2常见的数据结构4.3算法4.4线性表4.5栈和队列4.6树与二叉树4.7图4.8查找4.9排序数据（Data）：数据是信息的载体，它能被计算机识别、存储和加工处理，包括数字、字符串、表格、图像等。数据项（DataItem）：数据项是指数据的不可分割的、具有独立意义的最小单位，数据项有时也被称为字段（Field）或域。数据元素（DataElement）：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可以由若干个数据项组成，也可以只由一个数据项组成。数据元素又被称为元素（Element）、节点（Node）或记录（Record）。数据、数据元素、数据项实际上反映了数据组织的3个层次：数据可以由若干个数据元素构成，而数据元素又可以由一个或若干个数据项组成。一4.1数据结构的概念数据结构是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。一4.1数据结构的概念数据结构包括数据的两种结构：数据的逻辑结构、数据的存储结构（物理结构）。4.2.1数据的逻辑结构数据元素之间都存在着一种或多种特定的关系，这种关系被称为数据的逻辑结构。4种基本的逻辑结构如图4-1所示。一4.2常见的数据结构图4-14.2.2数据的存储结构数据的存储结构是指数据元素及其关系在计算机中的存储方式。数据的存储结构也被称为物理结构，有顺序存储和链式存储两种存储方法。顺序存储方法是把逻辑上相邻的元素存储在物理位置相邻的存储单元中。链式存储方法对逻辑上相邻的元素不要求其物理位置相邻，元素之间的关系可以通过附加的指针来表示。一4.2常见的数据结构4.3.1算法的定义算法（Algorithm）是对特定问题求解步骤的一种描述，是求解步骤（指令）的有限序列。一个算法应该具有下列特性：①有穷性。一个算法应在执行有穷步后结束。②确定性。算法中的每条指令必须有确切的含义，并且无歧义。③可行性。算法中的每条指令都应切实可行。④输入。一个算法应具有零个或多个输入。⑤输出。一个算法应具有一个或多个输出。一4.3算法4.3.2算法的表示1．自然语言2．程序流程图和N-S图等算法描述工具3．伪代码4．编程语言一4.3算法4.3.3算法的性能分析与度量1．时间复杂度设问题规模为n，f(n)代表算法中频度最大语句的频度，算法的渐近时间复杂度记作T(n)=O(f(n))，表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，简称时间复杂度。算法的时间复杂度不是算法的精确执行次数，而是估算的数量级。一1.2软件行业的发展现状及发展前景4.3.3算法的性能分析与度量例如，求下列算法的时间复杂度：(a)x++;(b)for(i=1;i＜=n;i++)x++;(c)for(i=1;i＜=n;i++)for(j=1;j＜=n;j++)x++;在以上3个算法中，“x++;”语句的执行次数分别是1、n和n2，因此，时间复杂度分别可以记为O(1)、O(n)和O(n2)。算法的时间复杂度考虑的是对于问题规模n的增长率，按增长率递增排列可以得到以下排列顺序：O(1)＜O(log2n)＜O(n)＜O(nlog2n)＜O(n2)＜O(n3)＜…＜O(2n)一1.2软件行业的发展现状及发展前景4.3.3算法的性能分析与度量2．空间复杂度执行算法所需占用的存储空间包括算法本身所占用的存储空间、数据的存储空间，以及算法在运行过程中的工作空间和其他的辅助空间。类似于时间复杂度，空间复杂度可以表示为S(n)=O(f(n))，其中n为问题的规模。一1.2软件行业的发展现状及发展前景4.4.1线性表的定义线性结构包括线性表、栈、队列、字符串、数组等，其中，最简单、最常用的是线性表。线性表（LinearList）是由具有相同数据类型的数据元素组成的一个有限序列，可以表示为：L=（a1,a2,…,ai-1,ai,ai+1,…,an）其中，n为线性表的长度，当n为零时，线性表称为空表；ai（1≤i≤n）代表了线性表中的数据元素，可以是一个数、一个符号或其他更复杂的信息。一4.4线性表根据线性表的定义，可以将非空线性表的逻辑结构特征描述如下：①“起点”数据元素和“终点”数据元素都是唯一的。②除“起点”数据元素以外，其他数据元素均只有一个直接前驱。③除“终点”数据元素以外，其他数据元素均只有一个直接后继。④同一线性表中的所有数据元素必须具有同一特性。一4.4线性表4.4.2线性表的存储与实现1．线性表的顺序存储线性表的顺序存储是指用一组地址连续的存储单元依次存放线性表中的数据元素。我们把采用顺序存储结构的线性表称为顺序表，它的特点是：线性表中相邻的数据元素在存储器中的存储位置也是相邻的，并且方向保持一致。由于线性表中所有数据元素的数据类型相同，因此每个数据元素在存储器中所占用的存储空间的大小都是相等的。一4.4线性表假设顺序表中第一个元素a1的存放地址用LOC(a1)表示，也被称为首地址，每个元素占用的存储空间为d字节，则表中任意一个数据元素ai的存放地址为：LOC(ai)=LOC(a1)+(i-1)*d一4.4线性表2．线性表的链式存储线性表的链式存储是指用一组地址任意的存储单元存放线性表中的数据元素，这组存储单元可以是连续的，也可以是不连续的。我们把采用链式存储结构的线性表称为链表，包括单链表、循环链表、双向链表等。一4.4线性表1）单链表在单链表中，每个数据元素ai除存储本身信息以外，还需存储其直接后继元素的存储位置。每个节点包括两个域：存储数据元素信息的数据域（data）和存储直接后继节点地址的指针域（next）。单链表中的节点结构如图4-3所示。图4-3单链表中的节点结构图4-4所示为带头节点的单链表的存储结构示意图，an是最后一个节点，因此它的指针域为空，用“∧”表示。图4-4带头节点的单链表的存储结构示意图一4.4线性表datanext2）循环单链表循环链表是一种首尾相接的链表。例如，只需将单链表中终端节点的指针域NULL改为指向单链表的第一个节点，就得到单链形式的循环链表。图4-5所示为循环单链表的存储结构示意图。图4-5循环单链表的存储结构示意图一4.4线性表3）双向链表在双向链表中，每个节点除数据域以外，还包括两个指针域：指针prior指向该节点的直接前驱节点，指针next指向该节点的直接后继节点。双向链表中的节点结构如图4-6所示。图4-6双向链表中的节点结构双向链表是一种对称结构，既有前向链，又有后向链，可以从两个方向搜索某个节点，这就使得双向链表上的某些操作变得更加方便。图4-7所示为双向链表的存储结构示意图。图4-7双向链表的存储结构示意图一4.4线性表priordatanext算法举例：在双向链表中p指针指向的节点前插入一个新节点d，如图4-8所示。图4-8在双向链表中的节点p前插入一个节点d用C语言描述上述在双向链表中插入节点的操作，算法如下：voidDinsertbefore(ELEMTPd,DLinkList*p){DLinkList*s；s=malloc(sizeof(DLinkList)); //生成一个新的节点ts→data=d； //将d赋给t的数据域s→prior=p→prior； //对应图4-8中的①s→next=p； //对应图4-8中的②(p→prior)→next=s； //对应图4-8中的③p→prior=s； //对应图4-8中的④}一4.4线性表3．顺序表与链表的比较如果在线性表上主要进行查找、读取操作而很少进行插入和删除操作，则宜采用顺序表结构。在顺序表中插入和删除元素时，平均要移动表中一半的元素，而在链表中插入和删除元素时则只需要修改指针。因此，当需要在线性表上频繁进行插入和删除操作时，宜采用链表结构。总之，线性表的顺序存储结构和链式存储结构各有优点与缺点，在实际应用中应根据具体问题进行综合考虑，最终选择适合的存储结构。一4.4线性表4.5.1栈1．栈的定义栈（Stack）是一种限定仅在表尾进行插入或删除操作的线性表，表尾称为栈顶（top），表头称为栈底（bottom），不含元素的栈称为空栈。向栈中插入元素称为入栈或压栈，从栈中删除元素称为出栈或退栈。因为最先入栈的元素在栈底，最后入栈的元素在栈顶，删除元素时则刚好相反，所以，栈也被称为后进先出（LastInFirstOut，LIFO）的线性表，简称LIFO表。栈的示意图如图4-9所示。一4.5栈和队列图4-9栈的示意图2．栈的存储结构栈的存储结构有顺序存储结构和链式存储结构两种。1）栈的顺序存储结构栈的顺序存储结构简称顺序栈，是指利用一组地址连续的存储单元依次存放栈中的数据元素，由于栈底位置是固定不变的，因此可以将栈底设置在数组的两端中的任意一端，一般设置在数组下标为0的那一端；栈顶位置是随着入栈和出栈操作而变化的，所以需要用一个整型变量top来指示当前栈顶的位置，通常将top称为栈顶指针。2）栈的链式存储结构用链式存储结构实现的栈称为链栈，通常用单链表来表示。因此，链栈中的节点是动态分配的，top指针指向栈顶元素，top唯一地确定一个链栈。当top为NULL时，该链栈为空栈，链栈没有栈满的问题。一4.5栈和队列3．栈的应用栈的应用非常广泛，如数据转换、行编辑语法检查等。例如，将十进制数N转换成d进制数。分析：将十进制数N转换成d进制数，方法是重复以下两步，直到N为0。①x=N%d，其中“%”表示求余。②N=N/d，其中“/”表示求商。以N=225、d=2为例，图4-12所示为数制转换过程。图4-12从低位到高位顺序产生二进制数各个数位上的数，而输出则应从高位到低位进行，刚好符合栈的“先进后出”特点。一4.5栈和队列4.5.2队列队列（Queue）也是一种运算受限的线性表。它只允许在表的一端队头（front）进行插入，而在另一端队尾（rear）进行删除。当队列中没有元素时称为空队列。在空队列中依次将元素a1、a2、…、an入队后，a1是队头元素，an是队尾元素；出队的次序也是a1、a2、…、an，因此队列也被称作先进先出（FirstInFirstOut，FIFO）的线性表，简称FIFO表。队列的示意图如图4-13所示。图4-13队列的示意图队列的基本操作有初始化队列、入队、出队、置空队列、获取队头元素、判断队列是否为空等。一4.5栈和队列2．队列的存储结构队列的存储结构有顺序存储结构和链式存储结构两种。1）队列的顺序存储结构队列的顺序存储结构是指利用一组地址连续的存储单元依次存放队列中的数据元素，简称顺序队列。由于队列的队头和队尾是随着入队和出队操作变化的，因此设两个整型变量front和rear，并约定front总是指向队头元素的前面一个位置，rear总是指向队尾元素所在的位置。当元素入队时rear加1，当元素出队时front加1。2）队列的链式存储结构在队列中，用线性链表表示的队列称为链队列。对于数据元素变动较大的数据结构，用链式存储结构更有利。链队列的基本运算有初始化队列、入队和出队等。一4.5栈和队列4.6.1树1．树的定义及相关术语树（Tree）是n（n≥0）个节点的有限集T。当n=0即T为空时，称为空树；当n＞0时，T满足以下两个条件：①有且仅有一个特定的称为根（Root）的节点，它没有直接前驱节点，但有零个或多个直接后继节点。②其余的n-1个节点可以分为m（m≥0）个互不相交的子集T1、T2、…、Tm，其中每个子集本身又是一棵树，将其称为根的子树（Subtree）。树的定义是递归的，因为在树的定义中又用到了树的定义。不包括任何节点的树称为空树。一4.6树与二叉树4.6.1树图4-16所示为一般的树。图4-16一般的树一4.6树与二叉树4.6.1树2．树的存储及应用树的存储要求既要存储节点的数据元素本身，又要存储节点之间的逻辑关系。树的存储结构有很多，常用的有双亲链表表示法、孩子链表表示法、双亲孩子链表表示法和孩子兄弟表示法。一4.6树与二叉树4.6.2二叉树二叉树是树形结构的一个重要类型，许多实际问题抽象出来的数据结构往往是二叉树形式，所以，二叉树具有很重要的地位。1．二叉树的定义二叉树（BinaryTree）是n（n≥0）个节点的有限集T，它或者是空集（n=0），或者同时满足以下两个条件：①有且仅有一个称为根的节点。②其余节点分为两个互不相交的集合T1和T2，T1和T2分别称为根的左子树和右子树。二叉树的特点是每个节点的度不大于2，并且二叉树的子树有左右之分。一4.6树与二叉树一4.6树与二叉树2．二叉树的主要性质性质1：二叉树第i层上的节点数目最多为2i-1（i≥1）。性质2：深度为k的二叉树至多有2k-1个节点（k≥1）。性质3：在任意一棵二叉树中，如果终端节点的个数为n0，度为2的节点的个数为n2，则n0=n2+1。性质4：具有n（n＞0）个节点的完全二叉树的深度为

log2n+1

或

log2n

+1。说明：

x

表示不小于x的最小整数，

x

表示不大于x的最大整数。二叉树的存储结构有两种：顺序存储结构和链式存储结构。一4.6树与二叉树3．二叉树的遍历二叉树的遍历是指按照一定次序依次访问树中所有节点的过程，并且每个节点仅被访问一次。遍历是二叉树中常用的一种操作。在遍历一棵非空二叉树时，根据访问根节点（D）、遍历左子树（L）和遍历右子树（R）的先后顺序不同，可以有6种遍历方法：DLR、DRL、LDR、RDL、LRD、RLD。如果规定左子树（L）在右子树（R）之前遍历，则对非空二叉树有3种递归遍历方法：DLR（先序遍历）、LDR（中序遍历）、LRD（后续遍历）。一4.6树与二叉树1）先序遍历先序遍历又称先根遍历，记为DLR，过程如下：（1）访问根节点。（2）先序遍历左子树。（3）先序遍历右子树。2）中序遍历中序遍历又称中根遍历，记为LDR，过程如下：（1）中序遍历左子树。（2）访问根节点。（3）中序遍历右子树。3）后序遍历后序遍历又称后根遍历，记为LRD，过程如下：（1）后序遍历左子树。（2）后序遍历右子树。（3）访问根节点。一4.6树与二叉树课堂练习：写出下图的先序遍历、后序遍历和后序遍历序列一4.6树与二叉树4）由遍历序列恢复二叉树图4-19所示的5棵二叉树的先序遍历序列都为ABC，由此可知，仅由先序遍历序列（或中序遍历序列，或后序遍历序列）无法唯一确定一棵二叉树。但是，如果同时知道一棵二叉树的先序遍历序列和中序遍历序列，或者同时知道一颗二叉树的中序遍历序列和后序遍历序列，就能唯一确定这棵二叉树。图4-19一4.6树与二叉树4．最优二叉树及应用1）最优二叉树的定义最优二叉树也称哈夫曼树，是一种带权路径长度最短的树，它有着广泛的应用。在很多应用中，常将树中节点赋予一个具有某种实际意义的实数，称为该节点的权。节点的带权路径长度是指从根到该节点的路径长度与该节点的权的乘积。树的带权路径长度定义为树中所有叶节点的带权路径长度之和，通常记为：其中，n表示叶子节点的数目，wi和li分别表示叶子节点ki的权值和根到节点ki之间的路径长度。在所有由n个带权叶子节点构成的二叉树中，WPL最小的二叉树称为最优二叉树。这个算法最早由哈夫曼（Huffman）于1952年提出，所以也被称为哈夫曼树。一4.6树与二叉树2）最优二叉树的构造算法如何构造一棵最优二叉树呢？哈夫曼首先给出了构造最优二叉树的方法，我们将其称为哈夫曼算法，其基本思想如下：（1）用给定的n个权值（w1、w2、…、wn）对应的n个节点构成n棵二叉树的森林T={T1,T2,…,Tn}，其中每棵二叉树Ti（1≤i≤n）中都只有一个权值为wi的根节点，其左子树和右子树均为空。（2）在森林T中选取两棵根节点权值最小的二叉树分别作为一棵新的二叉树的左子树和右子树，并标记新的二叉树的根节点权值为其左子树和右子树根节点的权值之和。（3）在森林T中，用新得到的二叉树代替这两棵树。（4）重复（2）和（3），直到T只含一棵二叉树为止。此时，这棵二叉树便是哈夫曼树。由哈夫曼树的定义可知，权值越大的叶子节点越靠近根节点，而权值越小的叶子节点越远离根节点。一4.6树与二叉树3）哈夫曼编码哈夫曼树的应用十分广泛。在不同的应用中，叶子节点的权值被赋予不同的含义。例如，在信息编码中，权值可以看作是某个符号出现的频率；当应用到判定过程中时，权值可以看作是某一类数据出现的频率。在数据通信中，常常需要将传送的信息转换成由二进制数1和0组成的字符串来传送，为了使传送的电文编码总长度最短，使用频率越高的字符编码应尽可能短，哈夫曼编码能达到这个目的。一4.6树与二叉树例如，假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.05,0.11,0.04,0.08,0.38,0.03,0.22,0.09}。为这8个字母构造哈夫曼树，并写出哈夫曼编码。分析过程：以电文中的8个字母a、b、c、d、e、f、g和h作为叶子节点，以它们出现的频率分别作为对应节点的权值构造哈夫曼树，并给树中所有的左分支标上0，给所有的右分支标上1。为8个字母构造的哈夫曼树如图4-23所示，8个字母的哈夫曼编码分别如下：一4.7图4.7.1图的基本概念1．图的定义图（Graph）是一种数据结构，可记为G=（V,E）。其中，G表示一个图，V是顶点的有穷非空集合，E是V中顶点偶对（称为边）的有穷集合。在一个图中，如果每条边都没有方向，则称该图为无向图，无向图中的边均是顶点的无序对，无序对通常用圆括号表示，如（vi,vj）和（vj,vi）表示同一条边。在一个图中，如果每条边都有方向，则称该图为有向图，有向图中的边均是顶点的有序对，有序对通常用尖括号表示，如<vi,vj>和<vj,vi>表示两条不同的有向边号呢？一4.7图在图4-24所示的图中，（a）是无向图，（b）是有向图。（a）无向图

（b）有向图一4.7图2．图的相关术语1）顶点、边、弧、弧头和弧尾在无向图中，如果顶点vi和顶点vj之间有一条直接连线，则称这条连线为边，边用顶点的无序偶对（vi,vj）来表示，表示顶点vi和顶点vj互为邻接点。在有向图中，如果顶点vi到顶点vj之间有一条直接的有向连线，则一般称这条连线为弧，弧用顶点的有序偶对<vi,vj>表示。有序偶对的第一个节点vi称为始点（或弧尾），在图中不带箭头的一端；有序偶对的第二个节点vj称为终点（或弧头），在图中带箭头的一端。一4.7图2．图的相关术语2）无向完全图在一个无向图中，如果任意两个顶点之间都有一条直接边相连接，则称该图为无向完全图。在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。3）有向完全图在一个有向图中，如果任意两个顶点之间都有方向相反的两条弧相连接，则称该图为有向完全图。在一个含有n个顶点的有向完全图中，有n(n-1)条边。一4.7图4）顶点的度、入度和出度顶点vi的度（degree）是指图中与顶点vi相连的边数，通常记为D（vi）。在有向图中，要区别顶点的入度和出度的概念。顶点vi的入度是指以顶点vi为终点的弧的数目，记为ID（vi）；顶点vi的出度是指以顶点vi为始点的弧的数目，记为OD（vi）。其中，D（vi）=ID（vi）+OD（vi）。在图4-24（a）所示的无向图中，顶点v1的度为2，顶点v4的度为3；在图4-24（b）所示的有向图中，顶点v1的度为2，其中，入度为1，出度为1。无论是有向图还是无向图，顶点数n、边数e和度数之间都有如下关系：一4.7图5）路径、路径长度在无向图G中，顶点vp到顶点vq之间的路径是指顶点序列vp、vi1、vi2、…、vim、vq。其中，（vp,vi1）、（vi1,vi2）、…、（vim,vq）分别为图中的边。如果G是有向图，则路径也是有向的，它由有向边<vp,vi1>、<vi1,vi2>、…、<vim,vq>组成。路径上边的数目称为路径长度。6）回路、简单路径和简单回路第一个顶点和最后一个顶点相同的路径称为回路或环（cycle）。序列中顶点不重复出现的路径称为简单路径。除第一个顶点与最后一个顶点以外，其他顶点不重复出现的回路称为简单回路。7）子图对于图G=（V,E）和图G’=（V’,E’），如果存在V’是V的子集，E’是E的子集，则称图G’是图G的一个子图。一4.7图8）连通的、连通图和连通分量在无向图中，如果从一个顶点vi到另一个顶点vj（i≠j）有路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图为连通图。无向图的极大连通子图称为连通分量。9）生成树连通图G的生成树是G的包含其全部n个顶点的一个极小连通子图。它必定包含且仅包含G的n-1条边。10）带权图图中每条边都可以附有一个对应的数值，称为权（weight）。权可以表示从一个顶点到另一个顶点的距离或花费的代价等。边上带权的图称为带权图，也称网络（network）。图的存储表示方法有很多，最常用的是邻接矩阵、邻接表和十字链表表示法。

4.7.2图的遍历图的遍历是指从图中的任意一个顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历有深度优先搜索和广度优先搜索两种方法，它们对无向图和有向图都适用。图的遍历是图的一种基本操作，是求解图的连通性问题、拓扑排序和关键路径等算法的基础。一4.7图4.7.2图的遍历1．深度优先搜索图的深度优先搜索DFS（Depth-FirstSearch）类似于树的先序遍历。假设图G的初态是所有顶点均未被访问过，在图G中任选一个顶点v为初始出发点（源点），首先访问顶点v，然后依次从顶点v的未被访问的邻接点出发继续深度优先搜索图中的其余顶点，直到图中所有与顶点v有路径相通的顶点均已被访问；如果此时图G中仍有未被访问的顶点，则在图G中另选一个尚未被访问的顶点作为新的源点重复上述过程，直到图G中所有顶点均已被访问。一4.7图4.7.2图的遍历2．广度优先搜索图的广度优先搜索BFS（Breadth-FirstSearch）类似于树的层次遍历。假设图G的初态是所有顶点均未被访问过，在图G中任选一个顶点v为初始出发点（源点），首先访问顶点v，接着依次访问顶点v的所有邻接点w1、w2、…、wt，然后依次访问与w1、w2、…、wt邻接的所有未被访问过的顶点，依此类推，直到图中所有和源点v有路径相通的顶点都已被访问。如果此时图中仍有未被访问的顶点，则在图G中另选一个尚未被访问的顶点作为新源点重复上述的搜索过程，直到图G中所有顶点均已被访问。一4.7图4.7.2图的应用1．最小生成树在一个无向连通网的所有生成树中，各条边的权值总和最小的生成树称为最小生成树，也称最小代价生成树。想要构造有n个顶点的无向连通带权图的最小生成树，必须满足以下3个条件：（1）必须包括n个顶点。（2）有且仅有n-1条边。（3）不存在回路。一4.7图4.7.2图的应用最小生成树有多种构造算法，其中大多数构造算法都是利用了最小生成树的性质（简称MST性质）：假设G=（V,E）是一个连通网络，U是顶点集V的一个真子集。如果（u,v）是G中所有的一个端点在U（u∈U）里、另一个端点不在U（即v∈V-U）里的边中具有最小权值的一条边，则一定存在G的一棵最小生成树包括边（u,v）。在最小生成树的构造方法中，最典型的是普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。最小生成树的概念可以解决很多实际问题。例如，要在n个城市之间构造一个费用最低的通信网络，在网络中，每个顶点表示城市，边表示城市之间可以构造通信线路，每条边的权值表示该条通信线路的费用，要想使总的费用最低，实际上就是寻找该网络的最小生成树。一4.7图2．AOV网与拓扑排序1）AOV网的定义在有向图中，如果用顶点表示活动，用有向边表示活动之间的先后关系，则称该有向图为顶点表示活动的网络（ActivityOnVertexNetwork），简称AOV网。在AOV网中，如果从顶点i到顶点j之间存在一条有向路径，则称顶点i是顶点j的前驱，或者称顶点j是顶点i的后继。如果<i,j>是图中的边，则称顶点i是顶点j的直接前驱，顶点j是顶点i的直接后继。2）拓扑排序对于一个AOV网G=(V,E)，如果V中顶点的线性序列（v1,v2,...,vn）满足条件“如果在G中从顶点vi到顶点vj有一条路径，则在序列中顶点vi必在顶点vj之前”，则称该线性序列为G的一个拓扑序列。构造有向图的一个拓扑序列的过程称为拓扑排序。一4.7图关于拓扑序列，有以下说明：（1）在AOV网中，如果不存在回路，则所有活动可以排成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，从而使整个工程顺序执行。（2）拓扑序列不是唯一的。（3）AOV网不一定都有拓扑序列。3）拓扑排序算法对AOV网进行拓扑排序的步骤如下：（1）从AOV网中选择一个入度为0的顶点，输出它。（2）从AOV网中删去该顶点及以它为弧尾的所有有向边。（3）重复上述两个步骤，直到剩余的网中不再存在入度为0的顶点。利用图的相关知识还可以解决很多实际问题，如最短路径、关键路径等。一4.7图4.8.1查找的定义查找（search）又称检索，给定一个值k，在含有n个节点的表中找出关键字等于给定值k的节点。如果存在，则查找成功；否则，查找失败。查找操作是计算机应用中常用的操作之一。查找通常是在文件中进行的。在计算机中，查找主要分静态查找、动态查找和哈希查找。静态查找主要是在查找表中查找给定的数据元素是否在表中；动态查找是指在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素；哈希查找是利用哈希函数通过计算求取待查找元素的存储地址。一4.8查找4.8.2常用查找方法1．顺序查找顺序查找又称线性查找，是一种最简单、最基本的查找方法。顺序查找既适用于顺序表，也适用于链表。顺序查找的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的记录关键字的值和给定值k进行比较，如果相等，则查找成功，并给出关键字k在表中的位置；如果扫描结束后仍未找到关键字的值等于k的记录，则查找失败，返回0。SeqSearch(SeqlistS[],ElemTypek){//在顺序表S中顺序查找关键字的值等于k的记录inti;S.elem[0].key=k; //监视哨for(i=S.length;S.elem[i].key!=k;i--) //从表中最后一个元素开始往前查找;returni; //当查找成功时返回找到的记录位置，当查找失败时返回0}一4.8查找4.8.2常用查找方法1．顺序查找在等概率的情况下，概率pi=1/n(1≤i≤n)，因此查找成功的平均查找长度为(n+…+2+1)/n=(n+1)/2，即查找成功时的平均比较次数约为表长的一半；如果k值不在表中，则需进行n+1次比较之后才能确定查找失败，因此顺序查找算法的时间复杂度为O(n)。顺序查找算法简单，对表的结构无要求，既适用于顺序表，也适用于链表，无论节点之间是否按关键字排序都同样适用。但顺序查找的效率低，因此，当n较大时不宜采用顺序查找。一4.8查找4.8.2常用查找方法2．折半查找折半查找（BinarySearch）也称二分查找，要求线性表是有序表。折半查找的基本思想如下：假设r[low…high]是当前查找区间，①假设有序表有n个元素且递增有序，中间位置记录的序号为mid=(n+1)/2，相应记录的关键字的值为rmid.key。②将给定值k与rmid.key进行比较，如果k=rmid.key，则查找成功，返回该元素的下标mid，结束查找；如果k＜rmid.key，由于有序表中的元素是递增的，因此若表中存在k，则其必定在左半部分，接着只要在左半部分r[1…mid-1]中继续使用折半查找即可。如果k＞rmid.key，若表中存在k，则其必定在右半部分，继续对右半部分r[mid+1…n]使用折半查找即可。每经过一次比较，查找空间就缩小一半，重复这一过程直至查找成功，或者直至当前查找区域为空，则宣告查找失败。一4.8查找4.8.2常用查找方法2．折半查找intBin_Search(Seqlistr,intn,ElemTypek){//在有序表r中折半查找关键字的值等于k的元素intlow=1,high=n;while(low<=high){mid=(low+high)/2;if(k==r[mid].key)returnmid;elseif(k>r[mid].key)high=mid-1;elselow=mid+1;}return-1;}查找方法还有很多，如分块查找、二叉排序树查找、哈希查找等，在实际工作中解决问题时，应根据实际情况进行选择。一4.8查找4.9.1排序的定义排序（sorting）是将数据元素（或记录）的任意序列通过某些方法重新排列成一个按关键字排序的序列。排序也是计算机程序设计中的一种重要操作。对于关键字相同的数据元素，如果通过某种方法排序后，数据元素的位置关系在排序前与排序后保持一致，则称这种排序方法是稳定的，反之，则称这种排序方法是不稳定的。排序方法可以分为内部排序和外部排序两大类。内部排序是指待排序的记录都存放在计算机内存中的排序；外部排序是指因待排序的数据量大，以至于内存不能容纳全部记录，在排序中需对外存进行访问的排序。一4.9排序4.9.2常用排序方法1．冒泡排序冒泡排序（BubbleSort）是一种交换排序，在排序过程中，主要通过两两比较待排序记录的关键字的值进行排序，如果逆序就进行交换，直到所有记录都排好序。冒泡排序简单易懂，但效率很低，适用于排序量不大的情况。冒泡排序的基本思想是：假设有n个记录待排序，首先对r[1].key和r[2].key进行比较，如果r[1].key>r[2].key，就交换这两个记录；然后继续对r[2].key和r[3].key进行比较，并进行相同的处理。重复上述过程，直到r[n-1].key和r[n].key比较完成。经过一趟冒泡排序后，关键字的值最大的记录被“沉”到了最下面。继续对前n-1个记录进行冒泡排序。如果在一趟排序过程中没有对记录进行交换，则排序结束。一4.9排序4.9.2常用排序方法1．冒泡排序例如，假设有一个原始序列，关键字的值分别为40、25、17、30、35、6、20、5，采用冒泡排序方法进行排序的过程如图4-27所示。一4.9排序图4-27采用冒泡排序方法进行排序的过程4.9.2常用排序方法用C语言描述冒泡排序，算法如下：voidBubbleSort(RTyper[],intn){//对表r[1…n]中的n个记录进行冒泡排序for(i=1;i<n;i++){flag=1; //flag=1表示本趟没有数据交换for(j=1;j<n-i;j++)if(r[j+1].key<r[j].key){flag=0； //flag=