(软考软件设计师)专题九：数据结构知识

专题九：数据结构知识数据结构是计算机软件的一门基础课程 , 计算机科学各个领域及有关的应用软件都要用到各种数据结构语言编译要使用栈、散列表及语法树；操作系统中用队列、存储管理表及目录树等；数据库系统运用线性表、多链表及索引树等进行数据管理；而在人工智能领域，依求解问题性质的差异将涉及到各种不同的数据结构，如广义表、集合、搜索树及各种有向图等等。学习数据结构目的是要熟悉一些最常用的数据结构，明确数据结构内在的逻辑关系，知道它们在计算机中的存储表示，并结合各种典型应用说明它们在进行各种操作时的动态性质及实际的执行算法，进一步提高软件计和编程水平。通过对不同存储结构和相应算法的对比，增强我们根据求解问题的性质选择合理的数据结构，并将问题求解算法的空间、时间及复杂性控制在一定范围的能力。软件设计师考试大纲对数据结构部分的要求是熟练掌握常用数据结构和常用算法，因此，本专题从数据结构的概述出发，对基本的概念引出常用的数据结构类型的介绍和讲解，同时在讲解各种数据结构中间采用算法与数据结构相结合的方式，在算法步骤中使用数据结构，对数据结构的重点、难点进行了分析，最后讲解了与数据结构紧密相关的排序和查找算法，以及一些以往考试卷的分析。1. 数据结构概述数据结构 研究了计算机需要处理的数据对象和对象之间的关系；刻画了应用中涉及到的数据的逻辑组织；也描述了数据在计算机中如何存储、传送、转换。学习数据结构注意的问题：系统掌握基本数据结构的特点及其不同实现。了解并掌握各种数据结构上主要操作的实现及其性能时间、空间）的分析。掌握各种数据结构的使用特性，在算法设计中能够进行选择。掌握常用的递归、回溯、迭代、递推等方法的设计掌握自顶向下、逐步求精的程序设计方法。掌握自顶向下、逐步求精的程序设计方法。在学习数据结构的知识之前，我们要了解一下数据结构中的基本概念。数据：对客观事物的符号表示，在计算机中就是指所有能输入到计算机中并被计算机程序所处理的符号的总称。数据项：是数据的不可分割的最小单位；1/48数据元素： 是数据的基本单位，在计算机程序中通常作为一个整体进行处理；一个数据元素可由若干个数据项组成。数据对象： 是性质相同的数据元素的集合，是数据的一个子集。数据结构上的基本操作：插入操作删除操作更新操作查找操作排序操作数据结构是指数据对象及相互关系和构造方法，一个数据结构B 形式上可以用一个二元组表示为B=A， R）。其中， A 是数据结构中的数据称为结点）的非空有限集合， R是定义在 A 上的关系的非空有限集合。根据数据元素之间的关系的不同特性，通常有下列4 类基本结构。集合结构中的数据元素除了“同属于一个集合”的关系外，别无其他关系。线性结构结构中的数据元素之间存在一个对一个的关系。树形结构结构中的元素之间存在一个对多个的关系。图状结构或网状结构结构中的元素之间存在多个对多个的关系。数据结构中，结点与结点间的相互关系是数据的逻辑结构。数据结构在计算机中的表示 又称为映象）称为数据的物理结构，也称存储结构。数据元素之间的关系在计算机中有两种不同的表示方式：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。任何一个算法的设计取决于选定的数据 逻辑）结构，而算法的实现依赖于采用的存储结构。数据的逻辑结构分为两类：线性结构：线性表、栈、队列和串非线性结构：树、图数据的存储方法有四类：顺序存储方法链接存储方法索引存储方法散列存储方法2. 常用数据结构2.1 线性表在数据结构中，线性结构常称为线性表，是最简单、最常用的一种数据结构，它是由 n 个相同数据类型的结点组成的有限序列。2/48其特点是：在数据元素的非空有限集合中，存在唯一的一个被称做“第一个”的数据元素存在唯一的一个被称做“最后一个”的元素数据元素除第一个之外，集合中的每个数据元素均只有一个前驱除最后一个之外，集合中每个数据元素均只有一个后继一个由 n 个结点 e0，e1 ， en-1 组成的线性表记为：e0， e1 ， en-1 ）。线性表的结点个数称为线性表的长度，长度为0 的线性表称为空的线性表，简称空表。对于非空线性表，e0 是线性表的第一个结点，en-1 是线性表的最后一个结点。线性表的结点构成了一个序列，对序列中两个相邻结点ei 和 ei-1 ，称前者是后者的前驱结点，后者是前者的后继结点。线性表最重要的性质是线性表中结点和相对位置是确定的。线性表的结点也称为表元，或称为记录，要求线性表的结点一定是同一类型的数据。线性表的结点可由若干个成分组成，其中唯一标识表元的成分成为关键字，简称键。线性表是一个相当灵活的数据结构，它的长度可以根据需要增长或缩短。对线性表的基本运算如下：INITIATEL ）初始化操作LENGTHL）求长度函数GETL， i ）取元素函数PRIORL， elm）求前驱函数NEXTL，elm） 求后继函数LOCATEL， x） 定位函数INSERTL， i ， b）插入操作DELETEL， i ）删除操作有多种存储方式能将线性表存储在计算机内，其中最常用的是顺序存储和链接存储。根据存储方式的不同，其上述的运算实现也不一样。顺序存储：是最简单的存储方式，其特点是逻辑关系上相邻的两个元素在物理位置上也相邻。通常使用一个足够大的数组，从数组的第一个元素开始，将线性表的结点依次存储在数组中。顺序存储方式优点：能直接访问线性表中的任意结点。线性表的第i 个元素 ai的存储位置可以使用以下公式求得：LOCai） =LOCa1） +i-1）*l3/48式中 LOC线性表的大小固定，浪费大量的存储空间，不利于节点的增加和减少；执行线性表的插入和删除操作要移动其他元素，不够方便；链式存储线性表链接存储是用链表来存储线性表。单链表 由于要存储地址指针，所以浪费空间；直接访问节点不方便；循环链表：循环链表是另一种形式的链式存储结构，是单链表的变形。它的特点就是表中最后一个结点的指针域指向头结点，整个链表形成一个环。因此，从表中任意一个结点出发都可以找到表中的其他结点。循环链表和单向链表基本一致，差别仅在于算法中循环的条件不是结点的指针是否为空，而是他们的指针是否等于头指针，循环链表最后一个结点的link指针不为 0 ( NULL，而是指向了表的前端。为简化操作，在循环链表中往往加入表头结点。循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。循环链表的示例：带表头结点的循环链表：4/48双向链表：双向链表是另一种形式的链式结构，双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。双向链表克服了单链表的单向性的缺点。前驱方向后继方向双向链表也可以有循环表，链表中存在两个环。一个结点的前趋的后继和该结点的后继的前趋都是指向该结点的。p =plLinkrLink = p rLink lLink2.2栈栈Stack ）是限定仅在表尾进行插入或删除操作的线性表。表尾端称栈顶top ），表头端称栈底 bottom ）。若有栈S=return (s-top= =stacksize-1。进栈：voidpush(seqstack *s,datatypexif (stackfull(serror(“ stack verflow” 。s-data+s-top=x。判断栈空：int stackempty(seqstack *s6/48return (s-top= = -1出栈：datatype pop(seqstack *sif (stackempty(serror(“stack underflow”。x=s-datatop。s-top-。return (x。链接存储栈：用链表实现的栈，链表第一个元素是栈顶元素，链表的末尾是栈底节点，链表的头指针就是栈顶指针，栈顶指针为空则是空栈。若同时需要两个以上的栈，最好采用链表作存储结构链接存储的栈的操作如下：进栈：Void push(linkstack *p,datatype xstacknode *q q=(stacknode*malloc(sizeof(stacknode。q data=x 。q next=p top 。p top=q 。出栈：7/48Datatypepop(linkstack*pdatatypex 。stacknode*q=p top 。if(stackempty(perror(“ stack underflow.”。x=q data 。p top=q next 。free(q。return x。多栈处理栈浮动技术：n 个栈共享一个数组空间V mn 设立栈顶指针数组t n+1和 栈底指针数组b n+1，t i 和 b i 分别指示第i个栈的栈顶与栈底，b n 作为控制量，指到数组最高下标各栈初始分配空间s= m/n指针初始值t0 =b0 = -1 =-1b nmti = =-1 +,i=1,2, -1b ib isn2.3 队列队列是只允许在一端进行插入，另一端进行删除运算的线性表。允许删除的那一端称为队首 front ），允许插入运算的另一端称为队尾 rear ）。通常称队列的结点插入为进队，队列的结点删除为出队。若有队列8/48Q=是进栈函数，形参top 是栈顶指针的指针，形参e是入栈元素。int pop(PNODE *top，int oe是出栈函数，形参top 是栈顶指针的指针，形参e作为返回出栈元素使用。int enQueue(PNODE *tail，int e是入队函数，形参tail是队尾指针的指针，形参 e 是入队元素。 int deQueue(PNODE *tail， int *e是出队函数，形参tail是队尾指针的指针，形参 e 作为返回出队元素使用。定义结点的结构如下：typedef struct nodeint value。struct node *next。9/48NODE， *PNODE。函数int push(PNODE *top， int ePNODE p = (PNODEmalloc(sizeof(NODE 。if(!preturn 1。p-value = e。p-next = *top*top = p。return 0。 /指向栈顶指针函数int pop(PNODE *top， int *ePNODE p = *top 。if(p = NULL return 1。*e = p-value。*top = p-next。/ 栈顶指向取出的数的指针free(p 。return 0。函数int enQueue(PNODE *tail， int ePNODE p，t ；t = *tail。p = (PNODEmalloc(sizeof(NODE ；if(!p return l 。p value = e。p next = t next 。t-next = p。/将元素加在尾指针后*tail = p。return 0。10/48函数int deQueue(PNODE *tail， int ePNODE p，q；if(*tail-next = *tail return 1。 / 队列已经空p = (*tail-next。/p获得尾指针q = p-next。e = q-value。p-next = q-next。if(*tail = q*tail = p。 /尾指针指向最后节点free(q。return 0。循环队列 (Circular Queue:存储队列的数组被当作首尾相接的表处理。队头、队尾指针加1 时从 maxSize -1 直接进到 0，可用语言的取模( 余数 运算实现。队头指针进1:front= ( front+ 1 %maxSize。队尾指针进1:rear = ( rear+ 1 % maxSize。队列初始化： front=rear = 0 。队空条件： front=rear 。队满条件： ( rear + 1 %maxSize = front循环队列的进队和出队:11/48优先级队列：是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素2.4串字符串是非数值处理应用中重要的处理对象。字符串是由某字符集上的字符所组成的任何有限字符序列。当一个字符串不包含任何字符时，称它为空字符串。一个字符串所包含的有效字符个数称为这个字符串的长度。一个字符串中任一连续的子序列称为该字符串的子串。包含子串的字符串相应称为主串。通常称该字符在序列中的序号为该字符在串中的位置。字符串的串值必须用单引号括, c1c2c3cn 起来，但单引号本身不属于串，它的作用是为了避免于变量名和数的常量混淆。在C 语言中，字符串常量是用一对双引号括住若干字符来表示，如“I am a student”字符串通常存于字符数组中，每个字符串最后一个有效字符后跟一个字符串结束符“0 ”. 系统提供的库函数形成的字符串会自动加结束符号，而用户的应用程序中形成的字符串必须由程序自行负责添加字符串结束符号。两个串相等当且仅当两个串的值相等，长度相等并且各个对应位置的字符都相等。常用的字符串的基本操作有7 种。ASSINGs， t ）和 CREATs， ss）赋值操作EQUALs， t ）判等函数LENGTHs）求长度函数CONCATs， t ）联接函数SUBSTRs， start， len ）求子串函数INDEXs， t ）定位函数REPLACEs，t ， v）置换函数INSERTs， pos，t ）插入函数DELETE 求字符串长 ,int strlen(char schar *strcpy(char to,char from。该函数将串from 复制到串to中，并且返回一个指向串to的开始处的指针。12/48(3 联接 (concatenationcharstrcat(char to,char from该函数将串from 复制到串to的末尾，并且返回一个指向串to的开始处的指针。(4 串比较 int strcmp(chars1,char s2。该函数比较串s1 和串 s2 的大小，当返回值小于0，等于 0 或大于 0 时分别表示s1s2例如： result=strcmp(“baker ”, ” Baker ”result0result=strcmp(“12”,”12” 。result=0result=strcmp(“Joe”,”Joseph” 。result0char strchr(char s,char c。该函数是找c 在字符串中第一次出现的位置，若找到则返回该位置，否则返回NULL。字符串的静态存储： 顺序存储，用一组地址连续的地址单元存储串的字符序列，特别是在 PASCAL程序语言中还可以采用紧缩数组来实现。字符串的动态存储：采用链表的方式存储字符串，节点的大小可以不同，即每个节点可以存放的字符数是不同的。对于节点大小大于1 的链表，需要设置头指针和尾指针来定位和串连接。存储密度： 串值所站的存储位/ 实际分配的存储位实际应用的串处理系统中采用的是动态存储结构，每个串的值各自存储在一组地址连续的存储单元中，存储地址在程序执行过程中动态分配。利用串名和串值之间的的对应关系来建立存储映象来访问串。2.5数组数组是最常用的数据结构之一，在程序中，数组常用来实现顺序存储的线性表。数组由固定个数的元素组成，全部元素的类型相同，元素依次顺序存储。每个元素对应一个下标，数组元素按数组名和元素的下标引用，引用数组元素的下标个数称为数组的维数。13/48C语言按行在 C 语言中， n 个元素的数组中，第一个元素的下标为0，最后一个的下标为n-1。数组可以分为一维、二维 N 维数组，取决于引用数组元素的下标的个数；一维数组：二维数组和三维数组：数组可以分为静态数组和动态数组两类，所谓静态就是指数组的空间存储分配是在使用之前还是在程序运行当中分配，静态数组就是在定义时必须进行空间分配，也就是固定数组的大小，这样就不利于数组的扩展。同样动态数组就是在程序运行过程中进行数组的赋值或者是空间的分配，动态数组一般采用链表的存储结构，而静态数组一般采用顺序存储结构。数组元素可以是任何类型的，当元素本身又是数组时，就构成多维数组。多维数组是一维数组的推广，多维数组中最常用的是二维数组。多维数组的所有元素并未排在一个线性序列里，要顺序存储多维数组按需要按一定次序把所有的数组元素排在一个线性序列里，常用的排列次序有行优先顺序和列优先顺序。对于多维数组，优先顺序存放。对于数组，通常只有两种操作：给定一个下标，存取相应的数据元素给定一组下标，修改相应数据元素的某一个或几个数据项的值。一般用多维数组表示矩阵，具体有以下几种类型：对称矩阵： Ai,j= =Aj,i14/48三角矩阵：以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵中，它的下三角/2中， sak 和 aij的对应关系是：k =3、对角矩阵对角矩阵中，所有的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。当 i-j 1 时，元素 ai,j=0。LOC(i,j=LOC(0,0+3*i-1+(j-i+1 =LOC(0,0+(2i+j4. 稀疏矩阵简单说，设矩阵 A 中有 s 个非零元素，若 s 远远小于矩阵元素的总数 即 smn），并且分布没有一定规律。用顺序存储结构的三元组对稀疏矩阵进行存储，分别记录行、列和值十字链表：15/48由于非零元的位置和个数变化，所以用链表存储更恰当；在这种情况下采用十字链表来表示，每个非零元用一个节点表示，节点中有行、列还有向下的域和线右的域；此外还需要一个指向列链表的表头节点和指向行链表的表头节点。还可以设置一个指向整个十字链表的表头节点。还可以把列表头和行表头节点组成数组，便于操作；各种广义表示意图2.6树概述树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构。树是由一个或多个结点组成的有限集T，它满足以下两个条件：I. 有一个特定的结点，成为根结点II.其余的结点分成m=0）个互不相交的有限集T0，T1， ， Tm-1。其中每个集合又都是一棵树，称T0，T1， ， Tm-1 为根结点的子树。这里可以看出树的定义是递归的，即一棵树由子树构成，子树又由更小的子树构成。一个结点的子树数目，称为结点的度。树中各结点的度的最大值则称为树的度。树中结点的最大层次称为树的深度。如果将树中结点的各子树看成从左到右是有次序的 即不能交换），则称该树为有序树，否则为无序树。森林是 m=0）棵互不相交的树的集合。存储结构树是非线性的结构，不能简单地用结点的线性表来表示。树有多种形式地存储结构，最常用的是标准存储形式和带逆存储形式。在树的标准存储结构中，树中的结点可分成两部分：结点的数据和指向子结点的指针。当程序需从结点返回到其父结点时，需要在树的结点中存储其父结点的位置信息，这种存储形式就是带逆存储结构。具体使用的链表结构有：16/48双亲表示法：利用每个节点只有一个双亲的特点；求节点的孩子时要遍历整个向量孩子表示法：把每个节点的孩子都排列起来，一单链表存储，则n 个节点有 n个孩子链表，而n 个头指针又组成了一个线性表。孩子兄弟表示法 又称二叉树表示法，或二叉链表表示法）：节点两个指针分别指向该节点的第一个孩子和下一个兄弟节点。树的遍历在应用树结构时，常要求按某种次序获得树中全部结点的信息，这可通过树的遍历操作来实现。常用的树的遍历方法有：树的前序遍历：首先访问根结点，然后从左到右遍历根结点的各棵子树。树的后序遍历：首先从左到右按后序遍历根结点的各棵子树，然后访问根结点。树的层次遍历：首先访问处于0 层上的根结点，然后从左到右依次访问处于 1 层、 2 层 上的结点，即自上而下从左到右逐层访问树各层上的结点。二叉树概述与一般的树的结构比较，二叉树在结构上更规范和更有确定性，应用也比树更为广泛。二叉树的特点是每个结点至多只有二棵子树 即二叉树中不存在度大于 2 的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。二叉树与树不同的地方在于，首先二叉树可以为空，空的二叉树没有结点；另外，在二叉树中，结点的子树是有序的，分左右两棵子二叉树。二叉树采用类似树的标准存储形式来存储。二叉树的性质 :二叉树具有下列重要特性。i 层至多有个结点 =1 ）。k 的二叉树至多有-1 个结点 =1）。对任何一棵二叉树T，如果其终端结点数为n0，度为2 的结点数为n2，则n0=n2+1。n 个结点的完全二叉树的深度为。二叉树的遍历17/48树的所有遍历方法都适用于二叉树，常用的二叉树遍历方法有3 种。#include#include#define NULL 0Typedef struct nodechar data。struct node *lchild,*rchild。TREENODE。TREENODE *root。前序遍历 :访问根结点，按前序遍历根结点的左子树，按前序遍历根结点的右子树。中序遍历 :按中序遍历根结点的左子树，访问根结点，按中序遍历根结点的右子树。中序遍历算法 :Void inorder(TREENODE *pif(p!=NULL inorder(p lchild。printf(“ %c” ,p datainorder(prchild。后序遍历 :按后序遍历根结点的左子树，按后序遍历根结点的右子树，18/48访问根结点。以上 3 种遍历方法都是递归定义的。哈夫曼及其应用：又称为最优树，是一类带权路径长度最短的树路径长度：从树中一个节点到另一个节点之间的分支构成的这两个节点之间的路径，路径上的分支树木就称为路径长度；树的路径长度：从树根到每一节点的路径长度之和；树的带权路径长度：树中所有叶子节点的带权路径长度之和；哈夫曼树就是一棵n 个叶子节点的二叉树，所有叶子节点的带权之和最小。算法描述：给定 n 个节点的集合，每个节点都带权值；选两个权值最小的节点构造一棵新的二叉树，新二叉树的根节点的权值就是两个子节点权值之和；从 n 个节点中删除刚才使用的两个节点，同时将新产生的二叉树根节点放在节点集合中。重复 2， 3 步，知道只有一棵树为止。例题：已知节点的前序序列和中序序列分别为：前序序列： ABCDEFG中序序列： CBEDAFG求出整个二叉树，以及构造过程2.7 图基本概念 :图是一种较线性表和树更为复杂的数据结构。在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。一个图 G由非空有限的顶点集合V 和有限的边的集合E 组成，记为G=V，E）。图一般分为两种类型。19/48无向图的边是顶点的无序偶，用i ， j ）来表示顶点i 和 j 之间的边。有向图的边是顶点的有序偶，有向图的边也成为弧，用 来表示顶点i和 j之间的弧。其中，有条边的无向图称为完全图，而具有n(n-1 条弧的有向图成为有向完全图。有时图的边或弧具有与它相关的树，这种与图的边或弧相关的数称作权。带权图也简称为网。如果同为无向图或同为有向图的两个图G1=V， E1）和 G2=表示顶点 Vi 的度。在图 G=V，E）中，如果存在顶点序列v0， v ， ， v），其中 v=p ， v=q ，且1k0kv0 ， v1）， v1 ， v2） ， vk-1 ， vk ）都在 E 中，则称顶点p 到顶点 q 有一条路径，并用 v0 ， v1， ， vk ）表示这条路径，路径的长度就是路径上的边或弧的数目，这条路径的长度为k 。如果第一个顶点和最后一个顶点相同的路径称为回路或环。序列中顶点不重复出现的路径称为简单路径。对无向图而言，如果从任意两个不同顶点i 和 j 之间都有路径，则该无向图是连通的。无向图中的极大连通子图为该图的连通分量。对有向图而言，如果任意两个不同顶点i到 j有路径，同时 j 到 i 也有路径，则该有向图是强连通的。同样，无向图中的极大连通强子图为该图的强连通分量。存储结构 : 最常用的存储结构是有两种。邻接矩阵 :这是反映顶点间邻接关系的矩阵。定义如下：设 G=V， E）是具有 nn1）个顶点的图， G的邻接矩阵 M是一个 n 行 n 列的矩阵，若i ， j ）或 E，则 Mij=1；否则 Mij=0。邻接表 : 这是图的链式存储结构。20/48图的每个顶点都建立了一个链表，且第i 个链表中的结点代表与顶点i 相关联的一条边或由顶点i 出发的一条弧。而这些链表的头指针则构成一个顺序线性表。另外，还有其他的一些存储结构，如十字链表和邻接多重表，分别用来存储有向图和无向图。图的遍历 :图的遍历是指从图中的某个顶点出发，沿着图中的边或弧访问图中的每个顶点，并且每个顶点只被访问一次。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。通常有两种方法，它们对无向图和有向图都适用。深度优先搜索 :类似于树的先根遍历。广度优先搜索 :类似于树的层次遍历。这两种算法的时间复杂度相同，不同之处仅仅在于对顶点访问的顺序不同。图的有关算法涉及到图的有关算法比较多，这里只简单归纳介绍一下，具体算法希望大家参考有关资料。求最小代价生成树设 G=V， E）是一个连通的无向图，若 G1 是包含 G 中所有顶点的一个无回路的连通子图，则称 G1 为 G 的一棵生成树。其中代价最小 各条边的权值之和最小）的生成树就称为最小代价生成树 简称最小生成树）。这里提供两种算法来求解这一问题：普里姆 Prim）算法和克鲁斯卡尔 和 O(eloge:v到子树 T0 的直接距离。 E 是边集合。输入加权连通图的带权邻接矩阵C=T0- 空集， CT0）对每一点 v 属于 V-V ， Lv） 。 如果 (v, v0不属于 E，则 C(v, v=100无穷大 21/48(3若 V =V, 则输出 T ， C在 V-V中找一点u, 使 L|v属于 (V-V , 并记在 V 中与 u 相邻的点111为 w,e=(w,u(5T0 -T 0， CT0） - CT 0）+ Ce） , V 1 对所有的v 属于 V-V1，若 C(v, uLv ） , 则 Lv） ,否则 L转 3克鲁斯卡尔 Kruskal ）算法基本思想：最初把图的n 个顶点看作n 个分离的部分树，每个树具有一个顶点，算法的每一步选择可连接两分离树的边中权最小的边连接两个部分树，合二为一，部分树逐步减少，直到只有一个部分树，便得到最小生成树。克鲁斯卡尔 : 最小生成树的权，初值为0；VS：部分树的顶点集合，其初值为v v v01n输入边的端点数组 A。(1T0 为空， C(T0对所有的 v 属于 V， VS-v。(3若 |VS|=1 ，输出 T0 ， C(T0 ，停止，否则转下一步；(4从 Q中取出排头边 u,v ），并从 Q中删除 如 u,v 杂 VS 的同一个元素集V1 中，则转4，否则分属于两个几个V1V2 ，进行下一步；(6T0- T 0，V+ C(u,v,转 3求最短路径在图中求最短路径问题有两种提法，一是求从某个源点到其他顶点的最短路径，二是求每一对顶点之间的最短路径。对于前者，一般采用迪杰斯特拉。迪杰斯特拉 Dijkstra ）算法的基本思想：生长一棵以v0 为根的最短路树，在这棵树上每一顶点与根之间的路径都是最短路径。由于网络不存在负权，最短路树的生长过程中各顶点将按照距v0 的远近及顶点的相邻关系，逐次长入树中，先近后远，直至所有顶点都已经在树中。22/48解决后面一种问题的方法是：每次以一个顶点为源点，重复执行迪杰斯特拉算法n次。另外还可以使用一种弗洛伊德。弗洛伊德 Floyd）算法基本思想：直接在图的带权邻接矩阵中用插入顶点的方法依次 ） ） 是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素某个项值有序的序列。作为排序依据的数据项称为“排序码”，也即数据元素的关键码。为了便于查找，通常希望计算机中的数据表是按关键码有序的。如有序表的折半查找，查找效率较高。还有，二叉排序树、B-树和 B+树的构造过程就是一个排序过程。若关键码是主关键码，则对于任意待排序序列，经排序后得到的结果是唯一的；若关键码是次关键码，排序结果可能不唯一，这是因为具有相同关键码的数据元素，这些元素在排序结果中，它们之间的的位置关系与排序前不能保持。若对任意的数据元素序列，使用某个排序方法，对它按关键码进行排序：若相同关键码元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；而不能保持一致的排序方法则称为不稳定的。排序分为两类：内排序和外排序。内排序：指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。23/48外排序：指排序过程中还需访问外存储器，足够大的元素序列，因不能完全放入内存，只能使用外排序。对于有 n 个结点的线性表 假设线性表的前面I 个结点序列 e0，e1， ， eI-1 是已排序的。对结点在这有序结点 ei 序列中找插入位置，并将 ei 插入，而使 i+1 个结点序列 e0，e1， ， ei 也变成排序的。依次对 i=1，2， ， n-1分别执行这样的插入步骤，最终实现线性表的排序。平均时最坏情辅助存是否稳间况储定O(O(O(1不稳定O(O(O(1稳定24/48对当前还未排好序的范围内的全部结点，自上而下对相邻的两个结点依次进行比较和调冒泡 整，让键值大的结点往下沉，排序 键值小的结点往上冒。即，每当两相邻比较后发现它们的排列顺序与排序要求相反时，就将它们互换。对直接插入排序一种改进，又称“缩小增量排序”。先将整个待排序列分割成为若干子序列分别进行直接插入排序，待希尔排序整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。 ,如果待排序记录序列为“正序“时，复杂度可达到 O(n对冒泡排序的一种本质的改进。通过一趟扫视后，使待排序序列的长度能大幅度的减少。在一趟扫视后，使某个结点移到中间的正确位置，并使在它左边序列的结点的键值都比它的小，而它右边序列的结快速排序点的键值都不比它的小。称这样一次扫视为“划分”。每次划分使一个长序列变成两个新的较小子序列，对这两个小的子序列分别作同样的划分，直至新的子序列的长度为 1 使才不再划分。当所有子序列长度都为 1 时，序列已是排好序的O(O(O(1稳定kn ln nO(O(logn不稳定O(nlognO(O(logn不稳定25/48了。