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

数据结构课程设计目录一.设计目的....................................................................................................错误!未定义书签。二.设计内容....................................................................................................................................1三．概要设计.................................................................................................................................11、功能模块图.........................................................................................................................12、各个模块详细的功能描述.................................................................................................2四．详细设计...................................................................................................................................31．主函数和其他函数的伪码算法.........................................................................................32、主要函数的程序流程图.....................................................................................................73、函数之间的调用关系图...................................................................................................15五．测试数据及运行结果.............................................................................................................151．正常测试数据及运行结果...............................................................................................162、非正常测试数据及运行结果...........................................................................................17六．调试情况，设计技巧及体会.................................................................................................18七．参考文献.................................................................................................................................19八．附录：源代码.........................................................................................................................191一.设计目的课程设计是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧。能够在设计中逐步提高程序设计能力，培养科学的软件工作方法。而且通过数据结构课程设计能够在下述各方面得到锻炼：1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。2、提高程序设计和调试能力。通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。3、培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。二.设计内容最小生成树问题:设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。三．概要设计1、功能模块图2、各个模块详细的功能描述※创建一个图：通过给用户信息提示，让用户将城市信息及城市之间的联系关系和连接权值写入程序，并根据写入的数据创建成一个图。※功能选择：给用户提示信息，让用户选择相应功能。※建立邻接矩阵：将用户输入的数据整理成邻接矩阵并显现在屏幕上。※建立邻接表：将用户输入的数据整理成临接表并显现在屏幕上。※PRIM算法：利用PRIM算法求出图的最小生成树，即：城市之间最经济的连接方案。开始创建一个图功能选择1.建立邻接矩阵2.建立邻接表3.PRIM算法4.kruscal算法结束四．详细设计1．主函数和其他函数的伪码算法※主函数：voidmain(){MGraphG;Dgevaluedgevalue;CreateUDG(G,dgevalue);charu;cout图创建成功。;cout请根据如下菜单选择操作。\n;cout*****************************************endl;cout**1、用邻接矩阵存储：********************endl;cout**2、用邻接表存储：**********************endl;cout**3、普里姆算法求最经济的连接方案********endl;cout**4、克鲁斯卡尔算法求最经济的连接方案****endl;cout*****************************************endlendl;ints;chary='y';while(y='y'){cout请选择菜单：endl;cins;switch(s){case1:cout用邻接矩阵存储为：endl;Adjacency_Matrix(G);break;case2:cout用邻接表存储为：endl;Adjacency_List(G,dgevalue);break;case3:cout普里姆算法最经济的连接方案为:endl;cout请输入起始城市名称：;cinu;MiniSpanTree_PRIM(G,u);break;case4:cout克鲁斯卡尔算法最经济的连接方案为:endl;MiniSpanTree_KRSL(G,dgevalue);break;default:cout您的输入有误!;break;}coutendl是否继续？y/n:;ciny;if(y=='n')break;}}※邻接矩阵和临接表的创建：intCreateUDG(MGraph&G,Dgevalue&dgevalue)//构造无向加权图的邻接矩阵{inti,j,k;cout请输入城市个数及其之间的可连接线路数目：;cinG.vexnumG.arcnum;cout请输入各个城市名称(分别用一个字符代替)：;for(i=0;iG.vexnum;++i)cinG.vexs[i];for(i=0;iG.vexnum;++i)//初始化数组for(j=0;jG.vexnum;++j){G.arcs[i][j].adj=MAX;}cout请输入两个城市名称及其连接费用(严禁连接重复输入!)：endl;for(k=0;kG.arcnum;++k){cindgevalue[k].ch1dgevalue[k].ch2dgevalue[k].value;i=LocateVex(G,dgevalue[k].ch1);j=LocateVex(G,dgevalue[k].ch2);G.arcs[i][j].adj=dgevalue[k].value;G.arcs[j][i].adj=G.arcs[i][j].adj;}returnOK;}※临接矩阵的输出：voidAdjacency_Matrix(MGraphG)//用邻接矩阵存储数据{inti,j;for(i=0;iG.vexnum;i++){for(j=0;jG.vexnum;j++)if(G.arcs[i][j].adj==MAX)cout0;elsecoutG.arcs[i][j].adj;coutendl;}}※邻接表的输出：voidAdjacency_List(MGraphG,Dgevaluedgevalue)//用邻接表储存数据{inti,j;for(i=0;iG.vexnum;i++){coutG.vexs[i]-;for(j=0;jG.arcnum;j++)if(dgevalue[j].ch1==G.vexs[i]&&dgevalue[j].ch2!=G.vexs[i])coutdgevalue[j].ch2-;elseif(dgevalue[j].ch1!=G.vexs[i]&&dgevalue[j].ch2==G.vexs[i])coutdgevalue[j].ch1-;cout\b\bendl;}}※最小生成树PRIM算法：voidMiniSpanTree_PRIM(MGraphG,charu)//普里姆算法求最小生成树{inti,j,k;Closedgeclosedge;k=LocateVex(G,u);for(j=0;jG.vexnum;j++)//辅助数组初始化{if(j!=k){closedge[j].adjvex=u;closedge[j].lowcost=G.arcs[k][j].adj;}}closedge[k].lowcost=0;for(i=1;iG.vexnum;i++){k=Minimum(G,closedge);cout城市closedge[k].adjvex与城市G.vexs[k]连接。endl;closedge[k].lowcost=0;for(j=0;jG.vexnum;++j){if(G.arcs[k][j].adjclosedge[j].lowcost){closedge[j].adjvex=G.vexs[k];closedge[j].lowcost=G.arcs[k][j].adj;}}}}intMinimum(MGraphG,Closedgeclosedge)//求closedge中权值最小的边，并返回其顶点在vexs中的位置{inti,j;doublek=1000;for(i=0;iG.vexnum;i++){if(closedge[i].lowcost!=0&&closedge[i].lowcostk){k=closedge[i].lowcost;j=i;}}returnj;}※最