数据结构课程设计--最小生成树问题.docx

数据结构课程设计报 告1 课程设计题目和内容15.最小生成树问题设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。2 程序中所采用的数据结构及存储结构的说明图试验中图的存储我采用的二种存储方法：数组表示法和邻接表表示法。数组存储法：typedef structint edgesmaxvertexmaxvertex;/图的邻接矩阵int vertex,arc;/图的顶点，边vertextype vex100;/顶点的相关信息mgraph;邻接表表示方法：typedef struct arcnodeint adjvex;/该弧所指向的顶点的位置struct arcnode *nextc;/指向下一条弧的指针inotype *info;/该弧相关信息的指针 arcnode;typedef struct vnodevertextype data;/顶点信息arcnode *firstarce;/指向第一条依附该顶点的弧的指针vnode,adjlistmax;typedef struct adjlist vertices;/图的当前顶点数和弧数int vecnum,arcnum;algraph;3 算法的设计思想求图的最小生成树主要有二种算法：普利姆算法和克鲁斯卡尔算法。普里姆算法设计思想：普利姆算法首先是选中一个顶点构成一个集合u，假设n=（v，e）是连通图，te是n上最小生成树边的集合，在所有的uu，vv的边（u，v）e中找一天代价最小的边（u0，v0）并入集合te，同时v0并入u，直到u=v为止。此时te中必有 n-1条边，则t=（v，te）为n的最小生成树。克鲁斯卡尔算法思想：克鲁斯卡尔算法算法从从另一种途径求网的最小生成树。假设连通网n=（v,e），则令最小生成树的初始状态为只有n个顶点而无边的的非连通图t=（v，），图中每个顶点自成一个连分量。在e中选择代价最小的边，若该边依附的顶点落在t中不同的连通分量上，则将此边加入到t中，否则舍去此边而选择下一条代价最小的边。以此类推，直至t中所有的顶点都在同一个连通分量上为止。4 普里姆算法和克鲁斯卡尔的比较普利姆算法的时间复杂度为o（n），与网中的边数无关因此适用于求边稠密的网的最小生成树。而克鲁斯卡尔算法恰恰相反，它的时间复杂度为o（eloge）（e为网中的边的数目），因此它适用边稀疏的网的最小生成树。5心得和总结编程要很强的逻辑思维，难度很大，但通过这次的自己亲自动手完成课程设计后，我懂得难度很多时候是因为我们自己想想它是难得，如果我们一开始就把它想象的很难，就会有心里的一种暗示，这个我是不会完成的。但是只要我们有信心，克服这中心里的障碍就一定能编写一个好程序。所以心态很重要。通过这次课程设计，发现自己对知识的掌握上还是有很多欠缺的。最主要的不足之处就是在把算法的思想有程序语言编写出来，这个对我来说有很大的难度。针对这种情况可能是我平时看程序不够多，自己练得很不够。还有就是对于图的存储上我不是很了解，以前总是觉得图的存储有太多的方法，对于在不同种情况下该用什么样的方法自己不太了解，对于她们的特点没有深入的了解，但通过这次自己在实际当中的练习，对于它们有了更深层次的认识。通过这次的课程设计要我们明白了，编程只有我们有信心，就一定能完成。6源程序清单/ 最小生成树.cpp : 定义控制台应用程序的入口点。/#include stdafx.h#include#include#define maxvertex 100#define max 10000/max表示无穷大typedef struct int no;/顶点的相关信息vertextype;typedef structint edgesmaxvertexmaxvertex;int vertex,arc;vertextype vex100;mgraph;typedef struct arcnodeint adjvex;struct arcnode *nextarc;int info;arcnode;typedef struct vnodeint data;arcnode *firstarc;vnode,adjlistmaxvertex;typedef struct adjlist vertice;int vertex,arc;algraph;typedef structint u;/边的起点int v;/边的终点int w;/边的权值edge;void creategraph(mgraph &g)/矩阵存储int i,j;g.vertex=6;g.arc=10;int a66=max,5,8,7,max,3,5,max,4,max,max,max,8,4,max,5,max,9,7,max,5,max,5,max,max,max,max,5,max,1,3,max,9,max,1,max;for(i=0;i6;i+)for(j=0;jvertex=6; a-arc=10;a=(algraph *)malloc(sizeof(algraph);for(i=0;ivertex;i+)a-verticei.firstarc=null;for(i=0;ivertex;i+)for(j=a-vertex;j=0;j-)if(g.edgesij!=0)p=(arcnode *)malloc(sizeof(arcnode);p-adjvex=j;p-info=g.edgesij;if(a-verticei.firstarc=null)a-verticei.firstarc=p;p-nextarc=null;elseq-nextarc=p;p-nextarc=null;q=p;void imputgraph(mgraph g)/输出图的邻接矩阵int i,j;for(i=0;ig.vertex;i+)for(j=0;jg.vertex;j+)if(g.edgesij=max)printf(%3c,a);elseprintf(%3d,g.edgesij);printf(n);void prim(mgraph g,int v)/普利姆算法求最小生成树int lowmaxvertex,min,n=g.vertex;int clomaxvertex,i,j,k;for(i=0;in;i+)/给low和clo赋初值lowi=g.edgesvi;cloi=v;for(i=1;in;i+)/找出n-1个顶点min=max;for(j=0;jn;j+)/在（v-u）中找出离u最近的顶点kif(lowj!=0&lowjmin)min=lowj;k=j;printf(边(%d,%d)权为:%dn,clok,k,min);lowk=0;/标记k已加入ufor(j=0;jn;j+)if(g.edgeskj!=0&g.edgeskjlowj)lowj=g.edgeskj;cloj=k;void fineedge(mgraph g,edge e)/在图中找到权值递增的边集int i,j,k=0;edge temp;for(i=0;ig.vertex;i+)for(j=0;jg.vertex;j+)if(g.edgesijmax)ek.u=i;ek.v=j;ek.w=g.edgesij;k+;for(i=1;i=0&temp.wej.w)ej+1=ej;j-;ej+1=temp;void kruskal(edge e,mgraph g)/克鲁斯卡尔算法求最小生成树int i,j,m1,m2,w,z,k;int n=g.vertex;int e=g.arc;int vsetmax;/辅助数组for(i=0;in;i+)/初始化辅助数组vseti=i;k=1;/k表示当前正在构造的第几条边j=0;/e中边的下标，初值为while(kn)m1=ej.u;m2=ej.v;w=vsetm1;z=vsetm2;if(w!=z)printf(%d,%d):%dn,m1,m2,ej.w);k+;for(i=0;in;i+)if(vseti=z)vseti=w;j+;/再开始下一条边void