实验13 快速排序11.doc

实验13 快速排序姓名：江婷 班级：计科三班 学号：09 完成日期：2010/12/01一、需求分析1 本程序需要将n 件任务按用时去从小到大排序，就可以得到任务依次的处理顺序。当有 n 件任务同时来临时，每件任务需要用时ni，求让所有任务等待的时间和最小的任务处理顺序。2 从文件中读入图的信息。3 利用克鲁斯卡尔算法求网的最小生成树。4 以文本形式生成树中各条边以及他们的权值。5 构造生成树的网一定是无向网。并设顶点数不超过30个，边权值为小于100的整数。6 根据克鲁斯卡尔算法的特点，为便于选择选择权值小的边，存储结构不选用邻接矩阵和邻接表，而是可以用存储边（带权）的数组表示图。二、概要设计抽象数据类型最小生成树的初始状态为只有n个顶点而无边的非连通图，图中每个顶点自成一个连通分量，所以要定义一个图的抽象数据类型。ADT Graph数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R=VRVR=|v,wV且P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧的信息基本操作P：Status CreateDGraph(ALGraph &G，V,VR);/采用邻接表存储表示，构造有向图G（G.kind=DG）。int FirstAdjVex(G,v);/若G中存在顶点v,则返回该顶点在图中位置;/否则返回-1.Status DeleteArc(&G,v,w);/在G中删除弧。int FindInDegree(G,ndegree);/求顶点的入度。ADT Graph生成树T的每个连通分量可看成是一个等价类，则构造T加入新的边的过程类似于求等价类的过程，由此可以用MFSet类型来描述T，使构造T的过程仅需O（e log e）的时间。ADT MFSet数据对象：若设S是MFSet型的集合，则它由n(n0)个子集S（i=1,2，n）构成，每个子集的成员都是子界-maxnumber , maxnumber内的整数；数据关系：=S 基本操作： Void Initial(&S,n,)；操作结果：初始化操作。构造一个由n个子集（每个子集只含单个成员x）构成的集合S。Int fix_mfset(S,x);初始条件：S是已存在的集合，x是S中某个子集的成员。操作结果：查找函数。确定S中x所属子集S。Status mix_mfset(&S,i,j);初始条件：S和S是S中的两个互不相交的非空集合。操作结果：归并操作。将S和S中的一个并入另一个中。ADT MFSet;算法的基本思想 最小生成树的MST性质：假设N=（V，E）是一个连通网，U是顶点集V的一个非空子集。若（u,v）是一条具有最小权值（代价）的边，其中uU,vV-U，则必存在一棵包含边（u,v）的最小生成树。 克鲁斯卡尔算法思想：假设连通网N=（V，E）,则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V， ），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。程序的流程程序由三个模块组成：（1） 输入模块：完成图中边数和顶点的输入。（2） 构造最小生成树并输出模块：实现最小生成树的构建，并将结果输出到屏幕。三、详细设计物理数据类型为便于实现查找和归并操作，则ADT MFSet的树应采用双亲表示法存储结构，如下所示：typedef PTree MFSet;int fix_mfset(MFSet S,int i)/确定集合S中i所在子集，并将从i至根路径上所有结点都变成根的孩子结点。if(iS.n)return -1; /i不属于S中任一子集for(j=i;S.nodesj.parent0;j=S.nodesj.parent);for(k=i;k!=j;k=t)t=S.nodesk.parent;S.nodesk.parent=j;return j;/fix_mfsetStatus mix_mfset(MFSet &S,int i,int j)/S.nodesi和S.nodesj分别为S的互不相交的两个子集Si和Sj的根结点。/并求集Si并Sj.if(iS.n|jS.n) return ERROR;if(S.nodesi.parentS.nodesj.parent)/Si所含成员数比Sj少S.nodesj.parent+=S.nodesi.parent;S.nodesi.parent=j;elseS.nodesi.parent+=S.nodesj.parent;S.nodesj.parent=i;return OK;/mix_mfset算法的具体步骤克鲁斯卡尔算法构造最小生成树的过程：1、 构造非连通图T=V，；k=i=0;/k计选中的边数。2、 当kn-1(n为顶点数)时，检查边集E中第i条权值最小的边（u,v）；3、 若（u,v）加入T后不使T中产生回路，则输出边（u,v）；且k+；算法的时空分析利用fix_mfset和mix_mfset算法和划分大小为n的集合为等价类的时间复杂度为O(n)。其中是一个增长极其缓慢的函数，。克鲁斯卡尔算法至多对e条边各扫描一次，如果用堆来存放网中的边，则每次选择最小代价的边仅需O（log e）的时间（第一次需O(e)）。又生成树T的每个连通分量可看成是一个等价类，则构造T加入新的边的过程类似于求等价类的过程，由此可以用MFSet类型来描述T，使构造T的过程仅需O（e log e）的时间，故克鲁斯卡尔算法的时间复杂度为O（e log e）。函数的调用关系图输入图的边数和顶点数fix_mfset（）/查找权值最小的边MiniSpanTree_Kruskal( )/生成最小生成树，并显示结果主程序fix