1、中国软考联盟，中国最权威的软考辅导和培训机构！ 以考带学，始于证书，止于无限专题九：数据结构知识数据结构是计算机软件的一门基础课程,计算机科学各个领域及有关的应用软件都要用到各种数据结构语言编译要使用栈、散列表及语法树；操作系统中用队列、存储管理表及目录树等；数据库系统运用线性表、多链表及索引树等进行数据管理；而在人工智能领域，依求解问题性质的差异将涉及到各种不同的数据结构，如广义表、集合、搜索树及各种有向图等等。学习数据结构目的是要熟悉一些最常用的数据结构，明确数据结构内在的逻辑关系，知道它们在计算机中的存储表示，并结合各种典型应用说明它们在进行各种操作时的动态性质及实际的执行算法，进一步提
2、高软件计和编程水平。通过对不同存储结构和相应算法的对比，增强我们根据求解问题的性质选择合理的数据结构，并将问题求解算法的空间、时间及复杂性控制在一定范围的能力。软件设计师考试大纲对数据结构部分的要求是熟练掌握常用数据结构和常用算法，因此，本专题从数据结构的概述出发，对基本的概念引出常用的数据结构类型的介绍和讲解，同时在讲解各种数据结构中间采用算法与数据结构相结合的方式，在算法步骤中使用数据结构，对数据结构的重点、难点进行了分析，最后讲解了与数据结构紧密相关的排序和查找算法，以及一些以往考试题的分析。1. 数据结构概述数据结构研究了计算机需要处理的数据对象和对象之间的关系；刻画了应用中涉及到的数
3、据的逻辑组织；也描述了数据在计算机中如何存储、传送、转换。学习数据结构注意的问题：n 系统掌握基本数据结构的特点及其不同实现。n 了解并掌握各种数据结构上主要操作的实现及其性能（时间、空间）的分析。n 掌握各种数据结构的使用特性，在算法设计中能够进行选择。n 掌握常用的递归、回溯、迭代、递推等方法的设计n 掌握自顶向下、逐步求精的程序设计方法。n 掌握自顶向下、逐步求精的程序设计方法。在学习数据结构的知识之前，我们要了解一下数据结构中的基本概念。数据：对客观事物的符号表示，在计算机中就是指所有能输入到计算机中并被计算机程序所处理的符号的总称。数据项： 是数据的不可分割的最小单位；数据元素：是数
4、据的基本单位，在计算机程序中通常作为一个整体进行处理；一个数据元素可由若干个数据项组成。数据对象：是性质相同的数据元素的集合，是数据的一个子集。数据结构上的基本操作： 插入操作 删除操作 更新操作 查找操作 排序操作数据结构是指数据对象及相互关系和构造方法，一个数据结构B形式上可以用一个二元组表示为B=（A，R）。其中，A是数据结构中的数据（称为结点）的非空有限集合，R是定义在A上的关系的非空有限集合。根据数据元素之间的关系的不同特性，通常有下列4类基本结构。 集合结构中的数据元素除了“同属于一个集合”的关系外，别无其他关系。 线性结构结构中的数据元素之间存在一个对一个的关系。 树形结构结构中
5、的元素之间存在一个对多个的关系。 图状结构或网状结构结构中的元素之间存在多个对多个的关系。数据结构中，结点与结点间的相互关系是数据的逻辑结构。数据结构在计算机中的表示（又称为映象）称为数据的物理结构，也称存储结构。数据元素之间的关系在计算机中有两种不同的表示方式：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构。数据的逻辑结构分为两类： 线性结构：线性表、栈、队列和串 非线性结构：树、图数据的存储方法有四类： 顺序存储方法 链接存储方法 索引存储方法 散列存储方法2. 常用数据结构2
6、.1线性表 在数据结构中，线性结构常称为线性表，是最简单、最常用的一种数据结构，它是由n个相同数据类型的结点组成的有限序列。其特点是：在数据元素的非空有限集合中，u 存在唯一的一个被称做“第一个”的数据元素u 存在唯一的一个被称做“最后一个”的元素数据元素u 除第一个之外，集合中的每个数据元素均只有一个前驱u 除最后一个之外，集合中每个数据元素均只有一个后继 一个由n个结点e0，e1，en-1组成的线性表记为：（e0，e1，en-1）。线性表的结点个数称为线性表的长度，长度为0的线性表称为空的线性表，简称空表。对于非空线性表，e0是线性表的第一个结点，en-1是线性表的最后一个结点。线性表的结
7、点构成了一个序列，对序列中两个相邻结点ei和ei-1，称前者是后者的前驱结点，后者是前者的后继结点。线性表最重要的性质是线性表中结点和相对位置是确定的。 线性表的结点也称为表元，或称为记录，要求线性表的结点一定是同一类型的数据。线性表的结点可由若干个成分组成，其中唯一标识表元的成分成为关键字，简称键。 线性表是一个相当灵活的数据结构，它的长度可以根据需要增长或缩短。对线性表的基本运算如下：u INITIATE（L）初始化操作u LENGTH（L） 求长度函数u GET（L，i） 取元素函数u PRIOR（L，elm）求前驱函数u NEXT（L，elm） 求后继函数u LOCATE（L，x） 定
8、位函数u INSERT（L，i，b）插入操作u DELETE（L，i） 删除操作有多种存储方式能将线性表存储在计算机内，其中最常用的是顺序存储和链接存储。根据存储方式的不同，其上述的运算实现也不一样。u 顺序存储：是最简单的存储方式，其特点是逻辑关系上相邻的两个元素在物理位置上也相邻。通常使用一个足够大的数组，从数组的第一个元素开始，将线性表的结点依次存储在数组中。顺序存储方式优点：能直接访问线性表中的任意结点。线性表的第i个元素ai的存储位置可以使用以下公式求得： LOC（ai）=LOC（a1）+（i-1）*l式中LOC（a1）是线性表的第一个数据元素a1的存储位置，通常称做线性表的起始位置
9、或基地址。顺序存储的缺点：1) 线性表的大小固定，浪费大量的存储空间，不利于节点的增加和减少；2) 执行线性表的插入和删除操作要移动其他元素，不够方便；链式存储线性表链接存储是用链表来存储线性表，。单链表（线性链表）：从链表的第一个表元开始，将线性表的结点依次存储在链表的各表元中。链表的每个表元除要存储线性表结点的信息以外，还要有一个成分来存储其后继结点的指针。线性链表的特点是：每个链表都有一个头指针，整个链表的存取必须从头指针开始，头指针指向第一个数据元素的位置，最后的节点指针为空。当链表为空时，头指针为空值；链表非空时，头指针指向第一个节点。链式存储的缺点：1) 由于要存储地址指针，所以浪
10、费空间；2) 直接访问节点不方便；3)4)5)6)7)循环链表：循环链表是另一种形式的链式存储结构，是单链表的变形。它的特点就是表中最后一个结点的指针域指向头结点，整个链表形成一个环。因此，从表中任意一个结点出发都可以找到表中的其他结点。循环链表和单向链表基本一致，差别仅在于算法中循环的条件不是结点的指针是否为空，而是他们的指针是否等于头指针，循环链表最后一个结点的 link 指针不为 0 (NULL)，而是指向了表的前端。为简化操作，在循环链表中往往加入表头结点。循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。循环链表的示例：带表头结点的循环链表 ：双向链表：双向
11、链表是另一种形式的链式结构，双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。双向链表克服了单链表的单向性的缺点。前驱方向 后继方向双向链表也可以有循环表，链表中存在两个环。一个结点的前趋的后继和该结点的后继的前趋都是指向该结点的。p = plLinkrLink = prLinklLink 2.2 栈栈（Stack）是限定仅在表尾进行插入或删除操作的线性表。表尾端称栈顶（top），表头端称栈底（bottom）。若有栈S=（s0，s1，sn-1）则s0为栈底结点，sn-1为栈顶结点。通常称栈的结点插入为进栈，栈的结点删除为出栈。因为最后进栈的结点必定最先出栈，所以栈具有后进先出的
12、特点。可以用一下一个图形来形象的表示：栈有两种存储结构：顺序栈和链栈顺序栈即栈的顺序存储结构是，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设指针top指示栈顶元素的当前位置。栈也可以用链表实现，链式存储结构的栈简称链栈。若同时需两个以上的栈，则最好采用这种结构。对于栈上的操作，总结如下，大家可以仔细看一下这些程序，一个大的程序都是由一些对数据结构的小的操作组成的。顺序存储的栈的基本操作如下：判断栈满：int stackfull(seqstack *s) return (s-top= =stacksize-1);进栈：void push(seqstack *s,datatyp
13、e x) if (stackfull(s)error(“stack verflow”); s-data+s-top=x;判断栈空：int stackempty(seqstack *s) return (s-top= = -1)出栈：datatype pop(seqstack *s)if (stackempty(s)error(“stack underflow”);x=s-datatop;s-top-;return (x);链接存储栈：用链表实现的栈，链表第一个元素是栈顶元素，链表的末尾是栈底节点，链表的头指针就是栈顶指针，栈顶指针为空则是空栈。若同时需要两个以上的栈，最好采用链表作存储结构链接
14、存储的栈的操作如下：进栈：Void push(linkstack *p,datatype x) stacknode *q q=(stacknode*)malloc(sizeof(stacknode); qdata=x; qnext=ptop; ptop=q;出栈：Datatype pop(linkstack *p) datatype x; stacknode *q=ptop; if(stackempty(p) error(“stack underflow.”); x=qdata; ptop=qnext; free(q); return x;多栈处理 栈浮动技术：n 个栈共享一个数组空间Vmn设
15、立栈顶指针数组 t n+1 和 栈底指针数组 b n+1，ti和bi分别指示第 i 个栈的栈顶与栈底，bn作为控制量，指到数组最高下标各栈初始分配空间 s = m/n指针初始值 t0 = b0 = -1 bn = m-1 ti = bi = bi-1 + s, i = 1, 2, , n-1 2.3队列队列是只允许在一端进行插入，另一端进行删除运算的线性表。允许删除的那一端称为队首（front），允许插入运算的另一端称为队尾（rear）。通常称队列的结点插入为进队，队列的结点删除为出队。若有队列Q=（q0，q1，qn-1）则q0为队首结点，qn-1为队尾结点。因最先进入队列的结点将最先出队，所
16、以队列具有先进先出的特性。可以用顺序存储线性表来表示队列，也可以用链表实现，用链表实现的队列称为链队列。队列操作：int push(PNODE *top，int e)是进栈函数，形参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作为返回出队元素使用。定义
17、结点的结构如下：typedef struct nodeint value;struct node *next;NODE，*PNODE;函数int push(PNODE *top，int e)PNODE p = (PNODE)malloc(sizeof(NODE);if(!p) return 1;p-value = e;p-next = *top; /指向栈顶指针*top = p;return 0;函数int pop(PNODE *top，int *e)PNODE p = *top;if(p = NULL) return 1;*e = p-value;*top = p-next; /栈顶指向取出
18、的数的指针free(p);return 0;函数int enQueue(PNODE *tail，int e) PNODE p，t；t = *tail;p = (PNODE)malloc(sizeof(NODE)；if(!p) return l;pvalue = e;pnext = tnext;t-next = p; /将元素加在尾指针后*tail = p;return 0;函数int deQueue(PNODE *tail，int e) PNODE p，q；if(*tail)-next = *tail) return 1;/队列已经空p = (*tail)-next; /p获得尾指针q = p
19、-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
20、 + 1) % maxSize = front 循环队列的进队和出队:优先级队列：是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素2.4 串字符串是非数值处理应用中重要的处理对象。字符串是由某字符集上的字符所组成的任何有限字符序列。当一个字符串不包含任何字符时，称它为空字符串。一个字符串所包含的有效字符个数称为这个字符串的长度。一个字符串中任一连续的子序列称为该字符串的子串。包含子串的字符串相应称为主串。通常称该字符在序列中的序号为该字符在串中的位置。字符串的串值必须用单引号括, c1c2c3cn起来，但单引号本身不属于串，它的作用是为了避免于变量名和数的常量混淆。在
21、C语言中，字符串常量是用一对双引号括住若干字符来表示，如“I am a student”字符串通常存于字符数组中，每个字符串最后一个有效字符后跟一个字符串结束符“0”.系统提供的库函数形成的字符串会自动加结束符号，而用户的应用程序中形成的字符串必须由程序自行负责添加字符串结束符号。两个串相等当且仅当两个串的值相等，长度相等并且各个对应位置的字符都相等。常用的字符串的基本操作有7种。u ASSING（s，t）和CREAT（s，ss）赋值操作u EQUAL（s，t）判等函数u LENGTH（s）求长度函数u CONCAT（s，t）联接函数u SUBSTR（s，start，len）求子串函数u IN
22、DEX（s，t）定位函数u REPLACE（s，t，v）置换函数u INSERT（s，pos，t）插入函数u DELETE（s，pos，t）删除函数(1)求字符串长,int strlen(char s)（2）串复制(copy) char *strcpy(char to,char from); 该函数将串from复制到串to中，并且返回一个指向串to的开始处的指针。(3)联接(concatenation) char strcat(char to,char from) 该函数将串from复制到串to的末尾，并且返回一个指向串to的开始处的指针。(4)串比较（compare) int strcmp(
23、chars1,char s2); 该函数比较串s1和串s2的大小，当返回值小于0，等于0或大于0时分别表示s1s2 例如：result=strcmp(“baker”,”Baker”) result0 result=strcmp(“12”,”12”); result=0 result=strcmp(“Joe”,”Joseph”); result1时，元素ai,j=0。LOC(i,j)=LOC(0,0)+3*i-1+(j-i+1) =LOC(0,0)+(2i+j)4. 稀疏矩阵简单说，设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即smn），并且分布没有一定规律。用顺序存储结构的三元组对稀
24、疏矩阵进行存储，分别记录行、列和值十字链表：由于非零元的位置和个数变化，所以用链表存储更恰当；在这种情况下采用十字链表来表示，每个非零元用一个节点表示，节点中有行、列还有向下的域和线右的域；此外还需要一个指向列链表的表头节点和指向行链表的表头节点。还可以设置一个指向整个十字链表的表头节点。还可以把列表头和行表头节点组成数组，便于操作；各种广义表示意图2.6 树2.6.1概述树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构。树是由一个或多个结点组成的有限集T，它满足以下两个条件：I. 有一个特定的结点，成为根结点II. 其余的结点分成m（m=0
25、）个互不相交的有限集T0，T1，Tm-1。其中每个集合又都是一棵树，称T0，T1，Tm-1为根结点的子树。这里可以看出树的定义是递归的，即一棵树由子树构成，子树又由更小的子树构成。一个结点的子树数目，称为结点的度。树中各结点的度的最大值则称为树的度。树中结点的最大层次称为树的深度。如果将树中结点的各子树看成从左到右是有次序的（即不能交换），则称该树为有序树，否则为无序树。森林是m（m=0）棵互不相交的树的集合。存储结构树是非线性的结构，不能简单地用结点的线性表来表示。树有多种形式地存储结构，最常用的是标准存储形式和带逆存储形式。在树的标准存储结构中，树中的结点可分成两部分：结点的数据和指向子结
26、点的指针。当程序需从结点返回到其父结点时，需要在树的结点中存储其父结点的位置信息，这种存储形式就是带逆存储结构。具体使用的链表结构有：u双亲表示法：利用每个节点只有一个双亲的特点；求节点的孩子时要遍历整个向量u孩子表示法：把每个节点的孩子都排列起来，一单链表存储，则n个节点有n个孩子链表，而n个头指针又组成了一个线性表。u孩子兄弟表示法（又称二叉树表示法，或二叉链表表示法）：节点两个指针分别指向该节点的第一个孩子和下一个兄弟节点。树的遍历 在应用树结构时，常要求按某种次序获得树中全部结点的信息，这可通过树的遍历操作来实现。常用的树的遍历方法有：u树的前序遍历：首先访问根结点，然后从左到右遍历根
27、结点的各棵子树。u树的后序遍历：首先从左到右按后序遍历根结点的各棵子树，然后访问根结点。u树的层次遍历：首先访问处于0层上的根结点，然后从左到右依次访问处于1层、2层上的结点，即自上而下从左到右逐层访问树各层上的结点。2.6.2二叉树n概述与一般的树的结构比较，二叉树在结构上更规范和更有确定性，应用也比树更为广泛。二叉树的特点是每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。二叉树与树不同的地方在于，首先二叉树可以为空，空的二叉树没有结点；另外，在二叉树中，结点的子树是有序的，分左右两棵子二叉树。二叉树采用类似树的标准存储形式来存储
28、。二叉树的性质: 二叉树具有下列重要特性。u在二叉树的第i层至多有个结点（i=1）。u深度为k的二叉树至多有-1个结点（k=1）。对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。u具有n个结点的完全二叉树的深度为。二叉树的遍历树的所有遍历方法都适用于二叉树，常用的二叉树遍历方法有3种。#include#include#define NULL 0Typedef struct node char data; struct node *lchild,*rchild; TREENODE;TREENODE *root;前序遍历:u 访问根结点，u 按前序遍历根结点的左
29、子树，u 按前序遍历根结点的右子树。中序遍历:u 按中序遍历根结点的左子树，u 访问根结点，u 按中序遍历根结点的右子树。中序遍历算法: Void inorder(TREENODE *p) if(p!=NULL) inorder(plchild);printf(“%c”,pdata) inorder(prchild);后序遍历:u 按后序遍历根结点的左子树，u 按后序遍历根结点的右子树，u 访问根结点。以上3种遍历方法都是递归定义的。哈夫曼及其应用：又称为最优树，是一类带权路径长度最短的树路径长度：从树中一个节点到另一个节点之间的分支构成的这两个节点之间的路径，路径上的分支树木就称为路径长度；
30、树的路径长度：从树根到每一节点的路径长度之和；树的带权路径长度：树中所有叶子节点的带权路径长度之和；哈夫曼树就是一棵n个叶子节点的二叉树，所有叶子节点的带权之和最小。算法描述：给定n个节点的集合，每个节点都带权值；选两个权值最小的节点构造一棵新的二叉树，新二叉树的根节点的权值就是两个子节点权值之和；从n个节点中删除刚才使用的两个节点，同时将新产生的二叉树根节点放在节点集合中。重复2，3步，知道只有一棵树为止。例题：已知节点的前序序列和中序序列分别为：前序序列：A B C D E F G中序序列：C B E D A F G求出整个二叉树，以及构造过程2.7图基本概念:图是一种较线性表和树更为复杂
31、的数据结构。在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。一个图G由非空有限的顶点集合V和有限的边的集合E组成，记为G=（V，E）。图一般分为两种类型。u无向图无向图的边是顶点的无序偶，用（i，j）来表示顶点i和j之间的边。u有向图有向图的边是顶点的有序偶，有向图的边也成为弧，用来表示顶点i和j之间的弧。其中，有条边的无向图称为完全图，而具有n(n-1)条弧的有向图成为有向完全图。有时图的边或弧具有与它相关的树，这种与图的边或弧相关的数称作权。带权图也简称为网。如果同为无向图或同为有向图的两个图G1=（V1，E1）和G2=（V2，E2）满足 V2V1 E2E1则
32、称图G2是图G1的子图。顶点的度就是指和顶点相关联的边的数目。在有向图中，以顶点v为头的弧的数据成为v的入度；以v为尾的弧成为v的出度。这里有一个重要的公式反映了顶点和边的关系。其中，e表示边的数目，n表示顶点个数，TD(Vi)表示顶点Vi的度。在图G=（V，E）中，如果存在顶点序列（v0 ，v1，vk），其中v0 =p，vk =q，且（v0 ，v1），（v1 ，v2），（vk-1 ，vk）都在E中，则称顶点p到顶点q有一条路径，并用（v0 ，v1，vk）表示这条路径，路径的长度就是路径上的边或弧的数目，这条路径的长度为k。 如果第一个顶点和最后一个顶点相同的路径称为回路或环。序列中顶点不重复
33、出现的路径称为简单路径。对无向图而言，如果从任意两个不同顶点i和j之间都有路径，则该无向图是连通的。无向图中的极大连通子图为该图的连通分量。对有向图而言，如果任意两个不同顶点i到j有路径，同时j到i也有路径，则该有向图是强连通的。同样，无向图中的极大连通强子图为该图的强连通分量。存储结构:最常用的存储结构是有两种。邻接矩阵:这是反映顶点间邻接关系的矩阵。定义如下：设G=（V，E）是具有n（n1）个顶点的图，G的邻接矩阵M是一个n行n列的矩阵，若（i，j）或E，则Mij=1；否则Mij=0。邻接表:这是图的链式存储结构。图的每个顶点都建立了一个链表，且第i个链表中的结点代表与顶点i相关联的一条边
34、或由顶点i出发的一条弧。而这些链表的头指针则构成一个顺序线性表。另外，还有其他的一些存储结构，如十字链表和邻接多重表，分别用来存储有向图和无向图。图的遍历:图的遍历是指从图中的某个顶点出发，沿着图中的边或弧访问图中的每个顶点，并且每个顶点只被访问一次。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。通常有两种方法，它们对无向图和有向图都适用。深度优先搜索:类似于树的先根遍历。广度优先搜索:类似于树的层次遍历。这两种算法的时间复杂度相同，不同之处仅仅在于对顶点访问的顺序不同。n 图的有关算法 涉及到图的有关算法比较多，这里只简单归纳介绍一下，具体算法希望大家参考有关资料。u求
35、最小代价生成树设G=（V，E）是一个连通的无向图，若G1是包含G中所有顶点的一个无回路的连通子图，则称G1为G的一棵生成树。其中代价最小（各条边的权值之和最小）的生成树就称为最小代价生成树（简称最小生成树）。这里提供两种算法来求解这一问题：普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。分别适用于求边稠密的网的最小生成树和边稀疏的网的最小生成树，其时间复杂度分别是O(n2)和O(eloge)（e为网中边的数目）。其中prim算法基本思想：任选一个顶点v0开始，连接与v0最近的顶点v1，得子树T1，再连接与T1最近的顶点v2，得子树T2，如此进行下去，直到所有顶点都用到为止。L(v):
36、v 到子树T0的直接距离。E是边集合。输入加权连通图的带权邻接矩阵C=（Cij）n*n.(1) T0-空集，C（T0）-0,V1=v0(2) 对每一点v属于V-V1，L（v）-C(v, v0);如果(v, v0)不属于E，则C(v, v0)=无穷大(3) 若V1=V,则输出T0，C（T0），停机。否则转到下一步；(4) 在V-V1中找一点u,使L（u）=minL(v)|v属于(V-V1),并记在V1中与u相邻的点为w,e=(w,u)(5) T0 -T0，C（T0）- C（T0）+ C（e）, V1 -V1(6) 对所有的v属于V-V1，若C(v, u)L（v）,则L（v）- C(v, u),否
37、则L（v）不变。(7) 转3克鲁斯卡尔（Kruskal）算法基本思想：最初把图的n个顶点看作n个分离的部分树，每个树具有一个顶点，算法的每一步选择可连接两分离树的边中权最小的边连接两个部分树，合二为一，部分树逐步减少，直到只有一个部分树，便得到最小生成树。克鲁斯卡尔（Kruskal）算法步骤：T0 :存放生成树的边的集合，初态为空；C(T0):最小生成树的权，初值为0；VS：部分树的顶点集合，其初值为v0 v1 vn输入边的端点数组A（e）,边的权值w(e);(1) T0 为空，C(T0)-0;VS为空，将E中的边按从小到大的顺序排列成队列Q；(2) 对所有的v属于V，VS-v;(3) 若|VS|=1，输出T0 ，C(T0) ，停止，否则转下一步；(4) 从Q中取出排头边（u,v），并从Q中删除（u,v）;(5) 如u,v杂VS的同一个元素集V1 中，则转4，否则分属于两个几个V1 V2 ，进行下一步；(6)
