数据结构笔记精品资料.doc

《数据结构笔记精品资料.doc》由会员分享，可在线阅读，更多相关《数据结构笔记精品资料.doc（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、目录第一章 概 论1第 二 章 线 性 表2第 三 章 栈 和 队 列8第 四 章 串17第 五 章 多 维 数 组 和 广 义 表21第 六 章 树23第 七 章 图27第 八 章 排 序31第 九 章 查 找35第 十 章 文 件40第一章 概 论1.数据：信息的载体,能被计算机识别、存储和加工处理。2.数据元素：数据的基本单位，可由若干个数据项组成，数据项是具有独立含义的最小标识单位。3.数据结构：数据之间的相互关系，即数据的组织形式。它包括：1）数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，独立于计算机；2）数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。3）数

2、据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用的运算：检索/插入/删除/更新/排序。4.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的存储结构是逻辑结构用计算机语言的实现。5.数据类型：一个值的集合及在值上定义的一组操作的总称。分为：原子类型和结构类型。6.抽象数据类型：抽象数据的组织和与之相关的操作。优点：将数据和操作封装在一起实现了信息隐藏。7. 抽象数据类型ADT：是在概念层上描述问题；类：是在实现层上描述问题；在应用层上操作对象（类的实例）解决问题。8.数据的逻辑结构，简称为数据结构，有：（1）线性结构，若结构是非空集则仅有一个开始和终端结点，并且所有结点

3、最多只有一个直接前趋和后继。（2）非线性结构，一个结点可能有多个直接前趋和后继。9.数据的存储结构有：1）顺序存储，把逻辑相邻的结点存储在物理上相邻的存储单元内。2）链接存储，结点间的逻辑关系由附加指针字段表示。3）索引存储，存储结点信息的同时，建立附加索引表，有稠密索引和稀疏索引。4）散列存储，按结点的关键字直接计算出存储地址。 10.评价算法的好坏是：算法是正确的；执行算法所耗的时间；执行算法的存储空间（辅助存储空间）；易于理解、编码、调试。 11.算法的时间复杂度T(n)：是该算法的时间耗费，是求解问题规模n的函数。记为O(n)。时间复杂度按数量级递增排列依次为：常数阶O(1)、对数阶O

4、(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、k次方阶O(nk)、指数阶O(2n)。13.算法的空间复杂度S(n)：是该算法的空间耗费，是求解问题规模n的函数。12.算法衡量：是用时间复杂度和空间复杂度来衡量的，它们合称算法的复杂度。13. 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。第 二 章 线 性 表1.线性表：是由n(n0)个数据元素组成的有限序列。2.线性表的基本运算有：1）InitList(L),构造空表，即表的初始化；2）ListLength(L),求表的结点个数，即表长；3）GetNode(L,i),取

5、表中第i个结点，要求1iListLength(L)；4）LocateNode(L,x)查找L中值为x的结点并返回结点在L中的位置，有多个x则返回首个，没有则返回特殊值表示查找失败。5）InsertList(L,x,i)在表的第i个位置插入值为x的新结点，要求1iListLength(L)+1；6）DeleteList(L,i)删除表的第i个位置的结点，要求1iListLength(L)；3.顺序表：把线性表的结点按逻辑次序存放在一组地址连续的存储单元里。4.顺序表结点的存储地址计算公式：Loc(ai)=Loc(a1)+(i-1)*C；1in 5.顺序表上的基本运算（1）插入void inser

6、tlist(seqlist *L,datatype x,int i)int j;if(iL-length+1) error(“position error”);if(L-length=listsize) error(“overflow”);for(j=L-length-1;j=i-1;j-) L-dataj+1=L-dataj; 结点后移L-datai-1=x;L-length+;在顺序表上插入要移动表的n/2结点，算法的平均时间复杂度为O(n)。（2）删除void delete (seqlist *L,int i)int j;if(iL-length) error(“position err

7、or”);for(j=i;jlength-1;j+) L-dataj-1=L-dataj; 结点前移 L-length-;在顺序表上删除要移动表的（n+1）/2结点，算法的平均时间复杂度为O(n)。 6.单链表：只有一个链域的链表称单链表。在结点中存储结点值和结点的后继结点的地址，data next data是数据域，next是指针域。 （1）建立单链表。时间复杂度为O(n)。加头结点的优点：1）链表第一个位置的操作无需特殊处理；2）将空表和非空表的处理统一。（2）查找运算。时间复杂度为O(n)。 1） 按序号查找。Listnode * getnode(linklist head,int i)

8、int j;listnode *p;p=head;j=0;while(p-next&jnext; 指针下移 j+;if(i=j) return p;else return NULL;2） 按值查找。Listnode * locatenode(linklist head ,datatype key)listnode *p=head-next;while(p&p-data!=key) p=p-next;return p;（3）插入运算。时间复杂度为O(n)。Void insertlist(linklist head ,datatype x, int i)listnode *p;p=getnode(

9、head,i-1);if(p=NULL); error(“position error”);s=(listnode *)malloc(sizeof(listnode);s-data=x;s-next=p-next;p-next=s; （4） 删除运算。时间复杂度为O(n)。Void deletelist(linklist head ,int i)listnode *p ,*r;p=getnode(head ,i-1);if(p=NULL|p-next=NULL) error(“position error”);r=p-next;p-next=r-next;free(r);7.循环链表：是一种首

10、尾相连的链表。特点是无需增加存储量，仅对表的链接方式修改使表的处理灵活方便。8.空循环链表仅由一个自成循环的头结点表示。9.很多时候表的操作是在表的首尾位置上进行，此时头指针表示的单循环链表就显的不够方便，改用尾指针rear来表示单循环链表。用头指针表示的单循环链表查找开始结点的时间是O(1),查找尾结点的时间是O(n)；用尾指针表示的单循环链表查找开始结点和尾结点的时间都是O(1)。10.在结点中增加一个指针域，prior|data|next。形成的链表中有两条不同方向的链称为双链表。1) 双链表的前插操作。时间复杂度为O(1)。Void dinsertbefore(dlistnode *p

11、 ,datatype x)dlistnode *s=malloc(sizeof(dlistnode);s-data=x;s-prior=p-prior;s-next=p;p-prior-next=s;p-prior=s;2) 双链表的删除操作。时间复杂度为O(1)。Void ddeletenode(dlistnode *p)p-prior-next=p-next;p-next-prior=p-prior;free(p);11.顺序表和链表的比较1） 基于空间的考虑：顺序表的存储空间是静态分配的，链表的存储空间是动态分配的。顺序表的存储密度比链表大。因此，在线性表长度变化不大，易于事先确定时，宜

12、采用顺序表作为存储结构。2） 基于时间的考虑：顺序表是随机存取结构，若线性表的操作主要是查找，很少有插入、删除操作时，宜用顺序表结构。对频繁进行插入、删除操作的线性表宜采用链表。若操作主要发生在表的首尾时采用尾指针表示的单循环链表。12.存储密度=（结点数据本身所占的存储量）/（整个结点结构所占的存储总量）存储密度：顺序表=1，链表top=-1;2)判栈空。int stackempty(seqstack *s)return s-top=-1;3)判栈满。int stackfull(seqstack *s)return s-top=stacksize-1;4)进栈。Void push(seqst

13、ack *s,datatype x)if(stackfull(s) error(“stack overflow”);s-data+s-top=x;5)退栈。Datatype pop(seqstack *s)if(stackempty(s) error(“stack underflow”);return S-datas-top-;6)取栈顶元素。Dtatatype stacktop(seqstack *s)if(stackempty(s) error(“stack underflow”);return S-datas-top;6.链栈：栈的链式存储结构称链栈。栈顶指针是链表的头指针。7.链栈上的

14、基本运算：1） 建栈。Void initstack(linkstack *s)s-top=NULL;2)判栈空。Int stackempty (linkstack *s)return s-top=NULL;3) 进栈。Void push(linkstack *s,datatype x)stacknode *p=(stacknode *)malloc(sizeof(stacknode);p-data=x;p-next=s-top;s-top=p;4) 退栈。Datatype pop(linksatck *s)datatype x;stacknode *p=s-top;if(stackempty(

15、s) error(“stack underflow”);x=p-data;s-top=p-next;free(p);return x;5) 取栈顶元素。Datatype stacktop(linkstack *s)if(stackempty(s) error(“stack is empty”);return s-top-data;8.队列是一种运算受限的线性表，允许删除的一端称队首，允许插入的一端称队尾。队列又称为先进先出线性表，FIFO表。9.队列的基本运算：1） initqueue(q),置空队；2） queueempty(q),判队空；3） queuefull(q),判队满；4） enq

16、ueue(q,x),入队；5） dequeue(q),出队；6） queuefront(q),返回队头元素。10.顺序队列：队列的顺序存储结构称顺序队列。设置front和rear指针表示队头和队尾元素在向量空间的位置。11.顺序队列中存在“假上溢”现象，由于入队和出队操作使头尾指针只增不减导致被删元素的空间无法利用，队尾指针超过向量空间的上界而不能入队。12.为克服“假上溢”现象，将向量空间想象为首尾相连的循环向量，存储在其中的队列称循环队列。i=(i+1)%queuesize13.循环队列的边界条件处理：由于无法用front=rear来判断队列的“空”和“满”。解决的方法有：1） 另设一个布

17、尔变量以区别队列的空和满；2） 少用一个元素，在入队前测试rear在循环意义下加1是否等于front；3） 使用一个记数器记录元素总数。14.循环队列的基本运算：1) 置队空。Void initqueue(cirqueue *q)q-front=q-rear=0;q-count=0;2) 判队空。Int queueempty(cirqueue *q)return q-count=0;3) 判队满。Int queuefull(cirqueue *q)return q-count=queuesize;4) 入队。Void enqueue(cirqueue *q ,datatype x)if(que

18、uefull(q) error(“queue overfolw”);q-count+;q-dataq-rear=x;q-rear=(q-rear+1)%queuesize;5) 出队。Datatype dequeue(cirqueue *q)datatype temp;if(queueempty(q) error(“queue underflow”);temp=q-dataq-front;q-count-;q-front=(q-front+1)%queuesize;return temp;6) 取队头元素。Datatype queuefront(cirqueue *q)if(queueempt

19、y(q) error(“queue is empty”);return q-dataq-front;15.链队列：队列的链式存储结构称链队列，链队列由一个头指针和一个尾指针唯一确定。16.链队列的基本运算：1) 建空队。Void initqueue(linkqueue *q)q-front=q-rear=NULL;2) 判队空。Int queueempty(linkqueue *q)return q-front=NULL&q-rear=NULL;3) 入队。Void enqueue(linkqueue *q,datatype x)queuenode *p=(queuenode *)malloc

20、(sizeof(queuenode);p-data=x;p-next=NULL;if(queueempty(q) q-front=q-rear=p;else q-rear-next=p; q-rear=p; 4) 出队。Datatype dequeue(linkqueue *q)datatype x;queuenode *p;if(queueempty(q) error(“queue is underflow”);p=q-front;x=p-data;q-front=p-next;if(q-rear=p) q-rear=NULL;free(p);return x;5) 取队头元素。Dataty

21、pe queuefront(linkqueue *q)if(queueempty(q) error(“queue is empty”);return q-front-data;第 四 章 串1.串：是由零个或多个字符组成的有限序列；包含字符的个数称串的长度；2.空串：长度为零的串称空串； 空白串：由一个或多个空格组成的串称空白串；子串：串中任意个连续字符组成的子序列称该串的子串； 主串：包含子串的串称主串；子串的首字符在主串中首次出现的位置定义为子串在主串中的位置；3.空串是任意串的子串； 任意串是自身的子串；串常量在程序中只能引用但不能改变其值； 串变量取值可以改变；4.串的基本运算1） i

22、nt strlen(char *s);求串长。2） char *strcpy(char * to,char * from);串复制。3） char *strcat(char * to,char * from);串联接。4） int strcmp(char *s1,char *s2);串比较。5） char *strchr(char *s,char c);字符定位。5.串的存储结构：（1）串的顺序存储：串的顺序存储结构称顺序串。按存储分配不同分为：1） 静态存储分配的顺序串：直接用定长的字符数组定义，以“0”表示串值终结。#define maxstrsize 256typedef char se

23、qstringmaxstrsize;seqstring s;不设终结符，用串长表示。Typedef structChar chmaxstrsize;Int length;seqstring;以上方式的缺点是：串值空间大小是静态的，难以适应插入、链接等操作。2） 动态存储分配的顺序串：简单定义：typedef char * string;复杂定义：typedef struct char *ch; int length; hstring;（2）串的链式存储：串的链式存储结构称链串。链串由头指针唯一确定。类型定义：typedef struct nodechar data;struct node *n

24、ext;linkstrnode;typedef linkstrnode *linkstring;linkstring s;将结点数据域存放的字符个数定义为结点的大小。结点大小不为1的链串类型定义：#define nodesize 80typedef struct nodechar datanodesize;struct node * next;linkstrnode;6.串运算的实现（1）顺序串上的子串定位运算。1）子串定位运算又称串的模式匹配或串匹配。主串称目标串；子串称模式串。2）朴素的串匹配算法。时间复杂度为O(n2)。比较的字符总次数为（n-m+1）m。Int naivestrmatc

25、h(seqstring t,seqstring p)int i,j,k;int m=p.length;int n=t.length;for(i=0;i=n-m;i+) j=0;k=i; while(jdata=p-data)t=t-next; p=p-next; else shift=shift-next; t=shift; p=P; if(p=NULL) return shift;else return NULL;第 五 章 多 维 数 组 和 广 义 表1.多维数组：一般用顺序存储的方式表示数组。2.常用方式有：1）行优先顺序，将数组元素按行向量排列；2）列优先顺序，将数组元素按列向量排列

26、。3.计算地址的函数：LOC(Aij)=LOC(Ac1c2)+(i-c1)*(d2-c2+1)+j-c2)*d4.矩阵的压缩存储：为多个非零元素分配一个存储空间；对零元素不分配存储空间。（1） 对称矩阵：在一个n阶的方阵A中，元素满足Aij=Aji 0=i,j(k-1)/2以行优先顺序存放的Aij与SAk的关系：k=2i+j;5.稀疏矩阵：当矩阵A中有非零元素S个，且S远小于元素总数时，称为稀疏矩阵。对其压缩的方法有顺序存储和链式存储。（1）三元组表：将表示稀疏矩阵的非零元素的三元组（行号、列号、值）按行或列优先的顺序排列得到的一个结点均是三元组的线性表，将该表的线性存储结构称为三元组表。其类

27、型定义：#define maxsize 10000typedef int datatype;typedef structint i,j;datatype v;trituplenode;typedef structtrituplenode datamaxsize;int m,n,t;tritupletable;（2）带行表的三元组表：在按行优先存储的三元组表中加入一个行表记录每行的非零元素在三元组表中的起始位置。类型定义：#define maxrow 100typedef structtritulpenode datamaxsize;int rowtabmaxrow;int m, n, t;rt

28、ritulpetable;6.广义表：是线性表的推广，广义表是n个元素的有限序列，元素可以是原子或一个广义表，记为LS。7.若元素是广义表称它为LS的子表。若广义表非空，则第一个元素称表头，其余元素称表尾。8.表的深度是指表展开后所含括号的层数。9.把与树对应的广义表称为纯表，它限制了表中成分的共享和递归；10.允许结点共享的表称为再入表；11.允许递归的表称为递归表；12.相互关系：线性表纯表再入表递归表；13.广义表的特殊运算：1）取表头head(LS)；2）取表尾tail(LS);第 六 章 树1.树：是n个结点的有限集T，T为空时称空树，否则满足：1）有且仅有一个特定的称为根的结点；2

29、）其余结点可分为m个互不相交的子集，每个子集本身是一棵树，并称为根的子树。2.树的表示方法：1）树形表示法；2）嵌套集合表示法；3）凹入表表示法；4）广义表表示法；3.一个结点拥有的子树数称为该结点的度；一棵树的度是指树中结点最大的度数。4.度为零的结点称叶子或终端结点；度不为零的结点称分支结点或非终端结点5.根结点称开始结点，根结点外的分支结点称内部结点；6.树中某结点的子树根称该结点的孩子；该结点称为孩子的双亲；7.树中存在一个结点序列K1，K2，Kn，使Ki为Ki+1的双亲，则称该结点序列为K1到Kn的路径或道路；8.树中结点K到Ks间存在一条路径，则称K是Ks的祖先，Ks是K的子孙；9

30、.结点的层数从根算起，若根的层数为1，则其余结点层数是其双亲结点层数加1；双亲在同一层的结点互为堂兄弟；树中结点最大层数称为树的高度或深度；10.树中每个结点的各个子树从左到右有次序的称有序树，否则称无序树；11.森林是m棵互不相交的树的集合。 12.二叉树：是n个结点的有限集，它或为空集，或由一个根结点及两棵互不相交的、分别称为该根的左子树和右子树的二叉树组成。13.二叉树不是树的特殊情况，这是两种不同的数据结构；它与无序树和度为2的有序树不同。14.二叉树的性质：1） 二叉树第i层上的结点数最多为2(i-1)；2） 深度为k的二叉树至多有2k-1个结点；3） 在任意二叉树中，叶子数为n0，

31、度为2的结点数为n2，则n0=n2+1；15.满二叉树是一棵深度为k的且有2k-1个结点的二叉树；16.完全二叉树是至多在最下两层上结点的度数可以小于2，并且最下层的结点集中在该层最左的位置的二叉树；17.具有N个结点的完全二叉树的深度为log2N取整加1；18.二叉树的存储结构（1）顺序存储结构：把一棵有n个结点的完全二叉树，从树根起自上而下、从左到右对所有结点编号，然后依次存储在一个向量b0n中，b1n存放结点，b0存放结点总数。各个结点编号间的关系：1） i=1是根结点；i1则双亲结点是i/2取整；2） 左孩子是2i, 右孩子是2i+1；（要小于n）3） i（n/2取整）的结点是叶子；4

32、） 奇数没有右兄弟，左兄弟是i-1；5） 偶数没有左兄弟，右兄弟是i+1；（2）链式存储结构结点的结构为：lchild|data|rchild ；相应的类型说明：typedef char data;typedef struct nodedatatype data;structnode *lchild , *rchild;bintnode;typedef bintnode * bintree;19.在二叉树中所有类型为bintnode的结点和一个指向开始结点的bintree类型的头指针构成二叉树的链式存储结构称二叉链表。20.二叉链表由根指针唯一确定。在n个结点的二叉链表中有2n个指针域，其中n

33、+1个为空。21.二叉树的遍历方式有：前序遍历、中序遍历、后序遍历。时间复杂度为O(n)。22.线索二叉树：利用二叉链表中的n+1个空指针域存放指向某种遍历次序下的前趋和后继结点的指针，这种指针称线索。加线索的二叉链表称线索链表。相应二叉树称线索二叉树。23.线索链表结点结构：lchild|ltag|data|rtag|rchild；ltag=0,lchild是指向左孩子的指针；ltag=1,lchild是指向前趋的线索；rtag=0,rchild是指向右孩子的指针；rtag=1,rchild是指向后继的线索；24.查找*p在指定次序下的前趋和后继结点。算法的时间复杂度为O(h)。线索对查找前

34、序前趋和后序后继帮助不大。25.遍历线索二叉树。时间复杂度为O(n)。26.树、森林与二叉树的转换（1）树、森林与二叉树的转换1）树与二叉树的转换：1所有兄弟间连线；2保留与长子的连线，去除其它连线。该二叉树的根结点的右子树必为空。2）森林与二叉树的转换：1将所有树转换成二叉树；2将所有树根连线。（2）二叉树与树、森林的转换。是以上的逆过程。27.树的存储结构（1）双亲链表表示法：为每个结点设置一个parent指针，就可唯一表示任何一棵树。Data|parent（2）孩子链表表示法：为每个结点设置一个firstchild指针，指向孩子链表头指针，链表中存放孩子结点序号。Data|firstch

35、ild。（3双亲孩子链表表示法：将以上方法结合。Data|parent|firstchild（4）孩子兄弟链表表示法：附加两个指向左孩子和右兄弟的指针。Leftmostchild|data|rightsibling28.树和森林的遍历：前序遍历一棵树等价于前序遍历对应二叉树；后序遍历等价于中序遍历对应二叉树。29.最优二叉树（哈夫曼树）：树的路径长度是从树根到每一结点的路径长度之和。将树中的结点赋予实数称为结点的权。30.结点的带权路径是该结点的路径长度与权的乘积。树的带权路径长度又称树的代价，是所有叶子的带权路径长度之和。31.带权路径长度最小的二叉树称最优二叉树（哈夫曼树）。32.具有2n

36、-1个结点其中有n个叶子，并且没有度为1的分支结点的树称为严格二叉树。33.哈夫曼编码 34.对字符集编码时，要求字符集中任一字符的编码都不是其它字符的编码前缀，这种编码称前缀码。35.字符出现频度与码长乘积之和称文件总长；字符出现概率与码长乘积之和称平均码长；36.使文件总长或平均码长最小的前缀码称最优前缀码37.利用哈夫曼树求最优前缀码，左为0，右为1。编码平均码长最小；没有叶子是其它叶子的祖先，不可能出现重复前缀。第 七 章 图1.图：图G是由顶点集V和边集E组成，顶点集是有穷非空集，边集是有穷集；2.G中每条边都有方向称有向图；有向边称弧；边的始点称弧尾；边的终点称弧头；G中每条边都没

37、有方向的称无向图。3.顶点n与边数e的关系：无向图的边数e介于0n(n-1)/2之间，有n(n-1)/2条边的称无向完全图；有向图的边数e介于0n(n-1)之间，有n(n-1)条边的称有向完全图；4.无向图中顶点的度是关联与顶点的边数；有向图中顶点的度是入度与出度的和。所有图均满足：所有顶点的度数和的一半为边数。5.图G（V，E），如V是V的子集，E是E的子集，且E中关联的顶点均在V中，则G(V,E)是G的子图。6.在有向图中，从顶点出发都有路径到达其它顶点的图称有根图；7.在无向图中，任意两个顶点都有路径连通称连通图；极大连通子图称连通分量；8.在有向图中，任意顺序两个顶点都有路径连通称强连

38、通图；极大连通子图称强连通分量；9.将图中每条边赋上权，则称带权图为网络。10.图的存储结构：（1）邻接矩阵表示法：邻接矩阵是表示顶点间相邻关系的矩阵。n个顶点就是n阶方阵。无向图是对称矩阵；有向图行是出度，列是入度。（2）邻接表表示法：对图中所有顶点，把与该顶点相邻接的顶点组成一个单链表，称为邻接表，adjvex|next,如要保存顶点信息加入data；对所有顶点设立头结点，vertex|firstedge,并顺序存储在一个向量中；vertex保存顶点信息，firstedge保存邻接表头指针。11.邻接矩阵表示法与邻接表表示法的比较：1） 邻接矩阵是唯一的，邻接表不唯一；2） 存储稀疏图用邻

39、接表，存储稠密图用邻接矩阵；3） 求无向图顶点的度都容易，求有向图顶点的度邻接矩阵较方便；4） 判断是否是图中的边，邻接矩阵容易，邻接表最坏时间为O(n)；5） 求边数e，邻接矩阵耗时为O(n2)，与e无关，邻接表的耗时为O(e+n)；12.图的遍历：（1）图的深度优先遍历：类似与树的前序遍历。按访问顶点次序得到的序列称DFS序列。对邻接表表示的图深度遍历称DFS，时间复杂度为O(n+e); 对邻接矩阵表示的图深度遍历称DFSM，时间复杂度为O(n2);（2）图的广度优先遍历：类似与树的层次遍历。按访问顶点次序得到的序列称BFS序列。对邻接表表示的图广度遍历称BFS，时间复杂度为O(n+e);

40、 对邻接矩阵表示的图广度遍历称BFSM，时间复杂度为O(n2);13. 将没有回路的连通图定义为树称自由树。14.生成树：连通图G的一个子图若是一棵包含G中所有顶点的树，该子图称生成树。有DFS生成树和BFS生成树，BFS生成树的高度最小。非连通图生成的是森林。15.最小生成树：将权最小的生成树称最小生成树。（是无向图的算法）（1）普里姆算法：1） 确定顶点S、初始化候选边集T0n-2；formvex|tovex|lenght2） 选权值最小的Ti与第1条记录交换；3） 从T1中将tovex取出替换以下记录的fromvex计算权；若权小则替换，否则不变；4） 选权值最小的Ti与第2条记录交换；5） 从T2中将tovex取出替换以下记录的fromvex计算权；若权小则替换，否则不变；6） 重复n-1次。初始化时间是O(n),选轻边的循环执行n-1-k次，调整轻边的循环执行n-2-k；算法的时间复杂度为O(n2)，适合于稠密图。（2）克鲁斯卡尔算法：1） 初始化确定顶点集和空边集；对原边集按权值递增顺序排序；2） 取第1条边，判断边的2个顶点是不同的树，加入空边集，否则删除；3） 重复e次。对边的排序时间是O(elog2e)；初始化时间为O(n)；执行时间是O(log2e)；算法的时间复杂度为O(elog2e)，适合于稀疏图。