数据结构课程设计-最小生成树课程设计报告.doc

数据结构课程设计学 院 专 业 班 级 姓 名 学 号 指导教师 2011 年 x 月 x 日一需求分析1.可以用连通网来表示n个城市间可能设置的通信网络，其中 网的顶点表示城市，边表示两城市之间的路线，边的权值表示相应的费用。 对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，我们要选择这样一棵生成树，它使总的费用最少，这棵树就是最小生成树。一棵生成树的费用就是树上各边的费用之和。 2.本程序的目的是要建设一个最经济的通信网，根据用户输入的网，输出相应的最小生成树。在这里城市以及两城市之间的费用都用整型数来代替。3程序执行的命令包括：（1）利用克鲁斯卡尔算法求最小生成树。（2）构造最小生成树中的连通分量。（3）权值应存放在定义的数组中。（4）输入城市个数。（5）用堆排序找出权值最小的边。（6）输出费用最少的生成树并将数据存放在文本文档中。（7）结束。4测试数据用户自定义输入城市个数即图的顶点数及边数，输入结束后回车即显示生成的最小生成树及最小开销。二概要设计1：抽象数据类型MFSet的定义：ADT MFSet 数据对象 ：若设S是MFSet型的集合，则它由n(n0)个子集Si（i = 1,2.,n）构成，每个子集的成员代表在这个子集中的城市。数据关系 ： S1 U S2 U S3 U. U Sn = S, Si包含于S（i = 1,2,.n） Init (n): 初始化集合，构造n个集合，每个集合都是单成员，根是其本身。rank数组初始化0Find(x):查找x所在集合的代表元素。即查找根，确定x所在的集合，并路径压缩。Merge(x, y):检查x与y是否在同一个集合，如果在同一个集合则返回假，否则按秩合并这两个集合并返回真。2：主程序：int main()初始化；while (条件) 接受命令; 处理命令;return 0;3：抽象数据类型 图 的定义如下：ADT Graph数据对象V：V是具有相同特性的数据元素的集合，成为顶点集。数据关系R： R=VR VR=|v，wV且P（v，w），表示从v到w的弧，谓词P（v，w）定义了弧的意义或信息 基本操作P：CreateGraph（&G，V，VR）； 初始条件：V是图的顶点集，VR是图中弧的集合。 操作结果：按V和的VR定义构造图G。DestoryGraph（&G）； 初始条件：图G存在。 操作结果：销毁图G。LocateVex（G，u）； 初始条件：图G存在，u和G中是顶点有相同特征。 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。GetVex（G，v）； 初始条件：图G存在，v是G中某个顶点。 操作结果：返回v的值。PutVex（&G，v，value）； 初始条件：图G存在，v是G中某个顶点。 操作结果：对V赋值value，FirstAdjVex（G，v）； 初始条件：图G存在，v是G中某个顶点。操作结果：返回v的第一个邻接顶点。若顶点在G中没有顶点，则返回“空”。NextAdjVex（G，v，w）； 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接顶点，则返回“空”。InsertVex（&G，v）； 初始条件：图G存在，v和途中顶点有相同特征。 操作结果：在图G中添加新顶点v。DeleteVex（&G，v）； 初始条件：图G存在，v是G中某个顶点。 操作结果：删除G中顶点v及其相关的弧。InsertArc（&G，v，w）； 初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中添加弧，若G是无向的，则还增添对称弧。DeleteArc（&G，v，w）； 初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中删除弧，若G是无向的，则还删除对称弧。DFSTravrese（G，Visit（）； 初始条件：图G存在，Visit是顶点的应用函数。操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用函数 Visit一次且仅一次。一旦Visit（）失败，则操作失败。BFSTravrese（G，Visit（）； 初始条件：图G存在，Visit是顶点的应用函数。操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦Visit（）失败，则操作失败。 ADT Graph4:本程序包括两个模块，调用关系比较简单：（1）主程序模块（2）带权无向图模块。 程序各模块之间的调用关系如下：主函数void main()调用以下函数 VoidHeapAdjust(int *arc,int s,int m)create(Graph &G)void HeapSort(Graph &G)克鲁斯卡尔算法求最小生成树三详细设计1、 主函数void main()Graph G;/定义图为Gcreate(G);/创建图HeapSort(G);/堆排序2、宏定义#define INFINITY 0 /最小值#define MAX_VERTEX_NUM 30 /最大顶点个数#define MAX_ARC_NUM 300 /最大的边数#define V 8#define A 143、定义顶点及边的类型typedef struct arcchar be; /边的起点char end; /边的终点int lengh; /边的权值AR; /边的类型4、定义图的类型typedef struct AR arMAX_ARC_NUM;int vexnum,arcnum; /图当前的顶点树和弧数Graph; /图的类型5、创建图，输入各顶点及权值int create(Graph &G)/创建图int locatevex(Graph &G,char c);char m,n;int i,j,k,qc;printf(请输入图的顶点数，边数n);/构造顶点向量scanf(%d%d,&G.vexnum,&G.arcnum);for(i=0;iG.vexnum;i+)printf(请输入第%d个顶点n,i);/构造顶点向量getchar();scanf(%c,&G.vexsi);printf(请输入第%d条边依附的顶点（俩个）及权值n,i);getchar();6、判断再次输入的边是否是之前的平行边或是否会构成回路scanf(%c,%c,%d,&G.ari.be,&G.ari.end,&G.ari.lengh);if(G.ari.be=G.ari.end) /判断是否会成回路printf(输入边的顶点相同，不符合和要求，请重新输入:n);while(G.ari.be=G.ari.end);for(j=0,m=z,n=z;ji;j+)if(G.ari.be=G.arj.end)m=G.arj.be;if(G.ari.be=G.arj.be)n=G.arj.end;if(m=G.ari.end|n=G.ari.end)printf(已有连接这两个顶点的边，请重新输入:n); /判断是否会有平行while(m=G.ari.be|n=G.ari.end);j=locatevex(G,G.ari.be);k=locatevex(G,G.ari.end);G.arcsjk=G.ari.lengh;G.arcskj=G.arcsjk;7、用堆排序找出权值最小的边void HeapAdjust(int *arc,int s,int m)/堆排序int t,j;t=arcs;for(j=2*s;j=m;j*=2)if(jarcj+1)+j;if(tarcj)arcs=arcj;s=j;else break;arcs=t;void HeapSort(Graph &G)char verVV;/不能动态定义数组verG.vexnumG.vexnum/辅助数组int arcA+1;int i,t,e=0,j;int jilA=0;int c,d,f,qc;fprintf(fp,%c,%c,%dn,G.arj.be,G.arj.end,G.arj.lengh);for(c=0;cG.vexnum;c+)if(veroc=z)p=c;break;for(c=0;cG.vexnum;c+)if(verqc=z)r=c;break;for(c=0,f=0;c=r;c+)for(d=0;dp;d+)if(verqc=verod)continue;verop+f=verqc;f+;for(c=0;cr;c+)verqc=z;HeapAdjust(arc,1,i-1);8、用克鲁斯卡尔算法求最小生成树arci=arc1; /arci为堆排序出的最小值arc1=t; for(j=0;jG.arcnum;j+)if(arci=G.arj.lengh)if(jilj=0)jilj=j+1;break;for(c=0;cG.vexnum;c+)for(d=0;dG.vexnum;d+) if(vercd=G.arj.be)o=c;p=d;continue;else if(vercd=G.arj.end)q=c;r=d;continue;else continue;if(o!=q)/判断边的两个顶点是否在不同连通分量上printf(,%dn,G.arj.be,G.arj.end,G.arj.lengh);printf(n);e+;for9、将最小生成树及权值写入文本文档FILE *fp;fp=fopen(WGraph.txt,w+);if(fp=NULL)printf(cannot open file!n);exit(0);四.调试分析1. 在本程序中用存储边（带权）的数组表示图，而不是用邻接矩阵的数组表示法或邻接表。为了让读者能一目了然看清结果，在终端输出从顶点0开始的最短路径时，设置了输出值的宽度。 2.为了简便起见，程序中的顶点、边的权值都设置成了整形，顶点的标记从0开始，即用数字代替城市名称。3.在写程序时遇到很多有关专业名词的C语言编译，没有完全套用书上的固有解释，而是按照自己有限的英语词汇的理解去编译的。 4.由于克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，构造最小生成树的时间复杂度为O(eloge)，e为网中边的数目，所以其时间复杂度与边有关，它适用于稀疏图。普里姆算法也是求最小生成树的基本算法，其时间复杂度为O(n)，与网中的边数无关，而与定点数有关，故其适用于求