最小生成树问题课程设计报告

1、数据结构课程设计报告学 号： * 姓 名： * 专 业： 软件工程题 目： 最小生成树问题 指导老师： *设计时间：第十七周 计算机科学与工程系2013年12月目录一. 设计目的2二. 设计内容2三概要设计11、功能模块图12、各个模块详细的功能描述1四详细设计21主函数和其他函数的伪码算法22、主要函数的程序流程图63、函数之间的调用关系图13五测试数据及运行结果141正常测试数据及运行结果142、非正常测试数据及运行结果15六调试情况，设计技巧及体会17七参考文献17八附录：源代码17一. 设计目的课程设计是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技

2、巧。能够在设计中逐步提高程序设计能力，培养科学的软件工作方法。而且通过数据结构课程设计能够在下述各方面得到锻炼：1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。2、提高程序设计和调试能力。通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。3、培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。二. 设计内容最小生成树问题:设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。

3、求解算法多种。三 概要设计1、功能模块图 开始创建一个图功能选择1.建立邻接矩阵2.建立邻接表3. prim算法4.kruscal算法结束2、各个模块详细的功能描述创建一个图：通过给用户信息提示，让用户将城市信息及城市之间的联系关系和连接权值写入程序，并根据写入的数据创建成一个图。功能选择：给用户提示信息，让用户选择相应功能。建立邻接矩阵：将用户输入的数据整理成邻接矩阵并显现在屏幕上。建立邻接表：将用户输入的数据整理成临接表并显现在屏幕上。prim算法：利用prim算法求出图的最小生成树，即：城市之间最经济的连接方案。四详细设计1主函数和其他函数的伪码算法 主函数：void main() mg

4、raph g; dgevalue dgevalue; createudg(g,dgevalue); char u; cout图创建成功。; cout请根据如下菜单选择操作。n; cout *endl; cout *1、用邻接矩阵存储：*endl; cout *2、用邻接表存储：*endl; cout *3、普里姆算法求最经济的连接方案*endl; cout *4、克鲁斯卡尔算法求最经济的连接方案*endl; cout *endlendl; int s; char y=y; while(y=y) cout请选择菜单：s; switch(s) case 1: cout用邻接矩阵存储为：endl;

5、adjacency_matrix(g); break; case 2: cout用邻接表存储为：endl; adjacency_list(g,dgevalue); break; case 3: cout普里姆算法最经济的连接方案为:endl; coutu; minispantree_prim(g,u); break; case 4: cout克鲁斯卡尔算法最经济的连接方案为:endl; minispantree_krsl(g,dgevalue); break; default: cout您的输入有误!; break; coutendly; if(y=n) break; 邻接矩阵和临接表的创建：

6、int createudg(mgraph & g,dgevalue & dgevalue) /构造无向加权图的邻接矩阵 int i,j,k; coutg.vexnumg.arcnum; cout请输入各个城市名称(分别用一个字符代替)：; for(i=0;ig.vexsi; for(i=0;ig.vexnum;+i)/初始化数组 for(j=0;jg.vexnum;+j) g.arcsij.adj=max; cout请输入两个城市名称及其连接费用(严禁连接重复输入!)：endl; for(k=0;k dgevaluek.ch1 dgevaluek.ch2 dgevaluek.value; i

7、= locatevex(g,dgevaluek.ch1); j = locatevex(g,dgevaluek.ch2); g.arcsij.adj = dgevaluek.value; g.arcsji.adj = g.arcsij.adj; return ok; 临接矩阵的输出： void adjacency_matrix(mgraph g) /用邻接矩阵存储数据int i,j;for(i=0; ig.vexnum; i+) for(j=0; jg.vexnum; j+) if(g.arcsij.adj=max)cout0 ; elsecoutg.arcsij.adj ; coutendl

8、; 邻接表的输出： void adjacency_list(mgraph g,dgevalue dgevalue) /用邻接表储存数据int i,j;for(i=0;ig.vexnum;i+)coutg.vexsi;for(j=0;jg.arcnum;j+)if(dgevaluej.ch1=g.vexsi&dgevaluej.ch2!=g.vexsi)coutdgevaluej.ch2;else if(dgevaluej.ch1!=g.vexsi&dgevaluej.ch2=g.vexsi)coutdgevaluej.ch1;coutbb endl;最小生成树prim算法： void mini

9、spantree_prim(mgraph g,char u)/普里姆算法求最小生成树 int i,j,k; closedge closedge; k = locatevex(g,u); for(j=0; jg.vexnum; j+) /辅助数组初始化 if(j != k) closedgej.adjvex = u; closedgej.lowcost = g.arcskj.adj; closedgek.lowcost = 0; for(i=1; ig.vexnum; i+) k = minimum(g,closedge); cout 城市closedgek.adjvex与城市g.vexsk连接

10、。endl; closedgek.lowcost = 0; for(j=0; jg.vexnum; +j) if(g.arcskj.adj closedgej.lowcost) closedgej.adjvex = g.vexsk; closedgej.lowcost= g.arcskj.adj; int minimum(mgraph g,closedge closedge) /求closedge中权值最小的边，并返回其顶点在vexs中的位置 int i,j; double k = 1000; for(i=0; ig.vexnum; i+) if(closedgei.lowcost != 0

11、& closedgei.lowcost k) k = closedgei.lowcost; j = i; return j; 最小生成树kruscal算法：void minispantree_krsl(mgraph g,dgevalue & dgevalue)/克鲁斯卡尔算法求最小生成树 int p1,p2,i,j; int bjmax_vertex_num; /标记数组 for(i=0; ig.vexnum; i+) /标记数组初始化 bji=i; sortdge(dgevalue,g);/将所有权值按从小到大排序 for(i=0; ig.arcnum; i+) p1 = bjlocatev

12、ex(g,dgevaluei.ch1); p2 = bjlocatevex(g,dgevaluei.ch2); if(p1 != p2) cout 城市dgevaluei.ch1与城市dgevaluei.ch2连接。endl; for(j=0; jg.vexnum; j+) if(bjj = p2) bjj = p1; void sortdge(dgevalue & dgevalue,mgraph g)/对dgevalue中各元素按权值按从小到大排序 int i,j; double temp; char ch1,ch2; for(i=0; ig.arcnum; i+) for(j=i; j d

13、gevaluej.value) temp = dgevaluei.value; dgevaluei.value = dgevaluej.value; dgevaluej.value = temp; ch1 = dgevaluei.ch1; dgevaluei.ch1 = dgevaluej.ch1; dgevaluej.ch1 = ch1; ch2 = dgevaluei.ch2; dgevaluei.ch2 = dgevaluej.ch2; dgevaluej.ch2 = ch2; 2、主要函数的程序流程图 main（）主函数creatudg()建图函数adjacency_matrix()邻

14、接矩阵输出函数 adjacency_list()邻接表输出函数minispantree_prim()普里姆算法：基本思想： 假设wn=(v,e)是一个含有n个顶点的连通网，tv是wn上最小生成树中顶点的集合，te是最小生成树中边的集合。显然，在算法执行结束时，tv=v，而te是e的一个子集。在算法开始执行时，te为空集，tv中只有一个顶点，因此，按普利姆算法构造最小生成树的过程为：在所有“其一个顶点已经落在生成树上，而另一个顶点尚未落在生成树上”的边中取一条权值为最小的边，逐条加在生成树上，直至生成树中含有n-1条边为止。在此系统中，n是你所需要输入的城市个数。而每条边的权值就是你所输入的每两

15、个城市之间的建设成本。开始标志顶点1加入u集合寻找满足边的一个顶点在u,另一个顶点在v的最小边形成n-1条边的生成树顶点k加入u修改由顶点k到其他顶点边的权值结束得到最小生成树minispantree_krsl()克鲁斯卡尔算法： 基本思想： 假设wn=（v, e）是一个含有n个顶点的连通网。则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含n个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有n棵树的一个森林。之后，从网的边集e中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之

16、，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有n-1条边为止。在此系统中，n是你所需要输入的城市个数。而每条边的权值就是你所输入的每两个城市之间的建设成本。locatevex（）节点位置函数： minimum()权值比较函数： sortdge()权值排序函数：3、函数之间的调用关系图五测试数据及运行结果 1正常测试数据及运行结果2、非正常测试数据及运行结果六调试情况，设计技巧及体会通过此次课程设计，我更深刻地理解了最小生成树问题，知道如何在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。并且用了多种求

17、解方式。数据结构是学习计算机的一门重要的基础课，在学习数据结构之前我们学习了c语言在我们看来数据结构就是学习c语言的延续。这几天的课程设计让 我充分地体会到了上机实践对于计算机编程的重要性。其实在于计算机语言这类课程看重的就是上机的实际操作，不满足于基本理论的学习。上机操作才能让我们更加好的掌握我们所要学习的计算机语言知识。只顾学习理论是远远不够的。实践中可以发现许许多多的问题，然后通过同学老师的帮助，得以解决，让自己的编程能力得到极大的提升。此外，也让我更加明白编程是要解决现实问题的。只有拥有把现实问题理论化的能力，才是编程真正需要达到的境界。七参考文献新编c语言课程设计教程 周二强 编著

18、清华大学出版社数据结构（c语言版） 严蔚敏 吴伟民 编著 清华大学出版社八附录：源代码#include #include #include #define max_vertex_num 20 #define ok 1 #define error 0 #define max 1000 typedef struct arcell double adj; arcell,adjmatrixmax_vertex_nummax_vertex_num; typedef struct char vexsmax_vertex_num; /节点数组 adjmatrix arcs; /邻接矩阵 int vexnum

19、,arcnum; /图的当前节点数和弧数 mgraph; typedef struct pnode /用于普利姆算法 char adjvex; /节点 double lowcost; /权值 pnode,closedgemax_vertex_num; /记录顶点集u到v-u的代价最小的边的辅助数组定义 typedef struct knode /用于克鲁斯卡尔算法中存储一条边及其对应的2个节点 char ch1; /节点1 char ch2; /节点2 double value;/权值 knode,dgevaluemax_vertex_num; /- int createudg(mgraph

20、& g,dgevalue & dgevalue); int locatevex(mgraph g,char ch); int minimum(mgraph g,closedge closedge); void minispantree_prim(mgraph g,char u); void sortdge(dgevalue & dgevalue,mgraph g); void adjacency_matrix(mgraph g);void adjacency_list(mgraph g,dgevalue dgevalue);/- int createudg(mgraph & g,dgevalu

21、e & dgevalue) /构造无向加权图的邻接矩阵 int i,j,k; coutg.vexnumg.arcnum; cout请输入各个城市名称(分别用一个字符代替)：; for(i=0;ig.vexsi; for(i=0;ig.vexnum;+i)/初始化数组 for(j=0;jg.vexnum;+j) g.arcsij.adj=max; cout请输入两个城市名称及其连接费用(严禁连接重复输入!)：endl; for(k=0;k dgevaluek.ch1 dgevaluek.ch2 dgevaluek.value; i = locatevex(g,dgevaluek.ch1); j

22、= locatevex(g,dgevaluek.ch2); g.arcsij.adj = dgevaluek.value; g.arcsji.adj = g.arcsij.adj; return ok; int locatevex(mgraph g,char ch) /确定节点ch在图g.vexs中的位置 int a ; for(int i=0; ig.vexnum; i+) if(g.vexsi = ch) a=i; return a; void minispantree_prim(mgraph g,char u)/普里姆算法求最小生成树 int i,j,k; closedge closed

23、ge; k = locatevex(g,u); for(j=0; jg.vexnum; j+) /辅助数组初始化 if(j != k) closedgej.adjvex = u; closedgej.lowcost = g.arcskj.adj; closedgek.lowcost = 0; for(i=1; ig.vexnum; i+) k = minimum(g,closedge); cout 城市closedgek.adjvex与城市g.vexsk连接。endl; closedgek.lowcost = 0; for(j=0; jg.vexnum; +j) if(g.arcskj.adj

24、 closedgej.lowcost) closedgej.adjvex = g.vexsk; closedgej.lowcost= g.arcskj.adj; int minimum(mgraph g,closedge closedge) /求closedge中权值最小的边，并返回其顶点在vexs中的位置 int i,j; double k = 1000; for(i=0; ig.vexnum; i+) if(closedgei.lowcost != 0 & closedgei.lowcost k) k = closedgei.lowcost; j = i; return j; void m

25、inispantree_krsl(mgraph g,dgevalue & dgevalue)/克鲁斯卡尔算法求最小生成树 int p1,p2,i,j; int bjmax_vertex_num; /标记数组 for(i=0; ig.vexnum; i+) /标记数组初始化 bji=i; sortdge(dgevalue,g);/将所有权值按从小到大排序 for(i=0; ig.arcnum; i+) p1 = bjlocatevex(g,dgevaluei.ch1); p2 = bjlocatevex(g,dgevaluei.ch2); if(p1 != p2) cout 城市dgevalue

26、i.ch1与城市dgevaluei.ch2连接。endl; for(j=0; jg.vexnum; j+) if(bjj = p2) bjj = p1; void sortdge(dgevalue & dgevalue,mgraph g)/对dgevalue中各元素按权值按从小到大排序 int i,j; double temp; char ch1,ch2; for(i=0; ig.arcnum; i+) for(j=i; j dgevaluej.value) temp = dgevaluei.value; dgevaluei.value = dgevaluej.value; dgevaluej.value = temp; ch1 = dgevaluei.ch1; dgevaluei.ch1 = dgevaluej.ch1; dgevaluej.ch1 = ch1; ch2 = dgevaluei.ch2; dgevaluei.ch2 = dgevaluej.ch2; dgevaluej.ch2 = ch2; void adjacency_matrix(mgraph g) /用邻接矩阵存储数据int i,j;for(i=0; ig.vexnum; i+) for(j=0; jg.vexnum; j+) if(g.arcsij.adj=max)cout0 ; else