资源描述：
《实验13 快速排序11》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、实验13快速排序姓名：江婷班级：计科三班学号：09完成日期：2010/12/01一、需求分析1．本程序需要将n件任务按用时去从小到大排序，就可以得到任务依次的处理顺序。当有n件任务同时来临时，每件任务需要用时ni，求让所有任务等待的时间和最小的任务处理顺序。2．从文件中读入图的信息。3．利用克鲁斯卡尔算法求网的最小生成树。4．以文本形式生成树中各条边以及他们的权值。5．构造生成树的网一定是无向网。并设顶点数不超过30个，边权值为小于100的整数。6．根据克鲁斯卡尔算法的特点，为便于选择选择权值小的边，存储结构不选用邻接矩阵和邻接表，而是可以用存储边（带权）的数组表示图。二、概要
2、设计抽象数据类型最小生成树的初始状态为只有n个顶点而无边的非连通图，图中每个顶点自成一个连通分量，所以要定义一个图的抽象数据类型。ADTGraph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R={VR}VR={
3、v,wV且P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧的信息}基本操作P：StatusCreateDGraph(ALGraph&G，V,VR);//采用邻接表存储表示，构造有向图G（G.kind=DG）。intFirstAdjVex(G,v);//若G中存在顶点v,则返回该顶点在图中位置;//否则返回
4、-1.StatusDeleteArc(&G,v,w);//在G中删除弧。intFindInDegree(G,ndegree[]);//求顶点的入度。}ADTGraph生成树T的每个连通分量可看成是一个等价类，则构造T加入新的边的过程类似于求等价类的过程，由此可以用MFSet类型来描述T，使构造T的过程仅需O（eloge）的时间。ADTMFSet{数据对象：若设S是MFSet型的集合，则它由n(n>0)个子集S（i=1,2，…，n）构成，每个子集的成员都是子界[-maxnumber,maxnumber]内的整数；数据关系：=S基本操作：VoidInitial(&S,n,
5、)；操作结果：初始化操作。构造一个由n个子集（每个子集只含单个成员x）构成的集合S。Intfix_mfset(S,x);初始条件：S是已存在的集合，x是S中某个子集的成员。操作结果：查找函数。确定S中x所属子集S。Statusmix_mfset(&S,i,j);初始条件：S和S是S中的两个互不相交的非空集合。操作结果：归并操作。将S和S中的一个并入另一个中。}ADTMFSet;算法的基本思想最小生成树的MST性质：假设N=（V，{E}）是一个连通网，U是顶点集V的一个非空子集。若（u,v）是一条具有最小权值（代价）的边，其中uU,vV-U，则必存在一棵包含边（u,v）的最小生成
6、树。克鲁斯卡尔算法思想：假设连通网N=（V，{E}）,则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{}），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。程序的流程程序由三个模块组成：（1）输入模块：完成图中边数和顶点的输入。（2）构造最小生成树并输出模块：实现最小生成树的构建，并将结果输出到屏幕。三、详细设计物理数据类型为便于实现查找和归并操作，则ADTMFSet的树应采用双亲表示法存储结构，如下所示：
7、typedefPTreeMFSet;intfix_mfset(MFSetS,inti){//确定集合S中i所在子集，并将从i至根路径上所有结点都变成根的孩子结点。if(i<1
8、
9、i>S.n)return-1;//i不属于S中任一子集for(j=i;S.nodes[j].parent>0;j=S.nodes[j].parent);for(k=i;k!=j;k=t){t=S.nodes[k].parent;S.nodes[k].parent=j;}returnj;}//fix_mfsetStatusmix_mfset(MFSet&S,inti,intj){//S.nodes[i]和
10、S.nodes[j]分别为S的互不相交的两个子集Si和Sj的根结点。//并求集Si并Sj.if(i<1
11、
12、i>S.n
13、
14、j<1
15、
16、j>S.n)returnERROR;if(S.nodes[i].parent>S.nodes[j].parent){//Si所含成员数比Sj少S.nodes[j].parent+=S.nodes[i].parent;S.nodes[i].parent=j;}else{S.nodes[i].parent+=S.nodes[j].parent;S.nodes[j].p
