《最小生成树问题课程设计报告1》由会员分享,可在线阅读,更多相关《最小生成树问题课程设计报告1(27页珍藏版)》请在金锄头文库上搜索。
1、数据结构课程设计报告专 业: 软件工程题 目: 最小生成树问题 目录一. 设计目的2二. 设计内容2三概要设计11、功能模块图12、各个模块详细的功能描述1四详细设计21主函数和其他函数的伪码算法22、主要函数的程序流程图63、函数之间的调用关系图13五测试数据及运行结果141正常测试数据及运行结果142、非正常测试数据及运行结果15六调试情况,设计技巧及体会17七参考文献17八附录:源代码172一. 设计目的课程设计是软件设计的综合训练,包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧。能够在设计中逐步提高程序设计能力,培养科学的软件工作方法。而且通过数据结构课程设计能够在下
2、述各方面得到锻炼:1、能根据实际问题的具体情况,结合数据结构课程中的基本理论和基本算法,正确分析出数据的逻辑结构,合理地选择相应的存储结构,并能设计出解决问题的有效算法。2、提高程序设计和调试能力。通过上机实习,验证自己设计的算法的正确性。学会有效利用基本调试方法,迅速找出程序代码中的错误并且修改。3、培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度,进一步提高程序设计水平。二. 设计内容最小生成树问题:设计要求:在n个城市之间建设网络,只需保证连通即可,求最经济的架设方法。存储结构采用多种。求解算法多种。三 概要设计1、功能模块图 开始创建一个图功能选择1.建立邻接矩阵2.建立邻接表
3、3. PRIM算法4.kruscal算法结束2、各个模块详细的功能描述创建一个图:通过给用户信息提示,让用户将城市信息及城市之间的联系关系和连接权值写入程序,并根据写入的数据创建成一个图。功能选择:给用户提示信息,让用户选择相应功能。建立邻接矩阵:将用户输入的数据整理成邻接矩阵并显现在屏幕上。建立邻接表:将用户输入的数据整理成临接表并显现在屏幕上。PRIM算法:利用PRIM算法求出图的最小生成树,即:城市之间最经济的连接方案。四详细设计1主函数和其他函数的伪码算法 主函数:void main() MGraph G; Dgevalue dgevalue; CreateUDG(G,dgevalue
4、); 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; Adjacency_Matrix(G); break; case 2: cout用邻接表存储为
5、: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; 邻接矩阵和临接表的创建:int CreateUDG(MGraph & G,Dgevalue & dgevalue) /
6、构造无向加权图的邻接矩阵 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 = LocateVex(G,d
7、gevaluek.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; 邻接表的输出: void Adjacency_List(MGraph G,Dgevalue
8、 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 MiniSpanTree_PRIM(MGraph G,char u)/普里姆算法求最小生成树 int
9、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连接。endl; closedgek.lowcost = 0; for(j=0; jG.vexnu
10、m; +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 & 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