构成可以使n个城市连接的最小生成树.doc

《构成可以使n个城市连接的最小生成树.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、题　目:构成可以使n个城市连接的最小生成树姓名:熊彬学号:100912042专业:电子信息工程班级:电信1021指导教师:梁英职称:讲师计算机与电子工程学院2012年1月课程设计(实习)评审表姓名熊彬学院电子信息工程学号100912042专业班级电信1021题目构成可以是n个城市连接的最小生成树评审意见评审成绩指导教师签名职称评审时间年月日课程设计(实习)作品验收表题目构成可以使n个城市连接的最小生成树参与人员姓名熊彬班级电信1021学号10

2、0912042设计任务与要求：作品完成情况：验收情况：验收教师签名：___________　　　　　　年月日目录一．需求分析21.1设计的任务21.2程序所能达到的功能21.3程序执行命令2二．概要设计32.1抽象数据类型结构体数组的定义：32.2程序模块42.3流程图4三．详细设计53.1数据类型定义53.2程序主要模块5四．调试分析和测试结果84.1调试分析84.2测试结果9五．总结10六．参考文献10七．致谢11八．附录11构造可以使N个城市连接的最小生成树一．需求分析1.1设计的任务给定一个地区的n个城市间的

3、距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。1.2程序所能达到的功能1.2.1城市间的道路网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。1.2.2显示出城市间道路网的邻接矩阵。1.2.3最小生成树中包括的边及其权值，并显示得到的最小生成树的总代价。1.3程序执行命令输入城市数、道路数→输入城市名→输入道路信息→执行Kruskal算法→执行Prim算法→输出最小生成树二．概要设计2.1抽象数据

4、类型结构体数组的定义：#ifndefADJACENCYMATRIXED//防止该头文件被重复引用#defineADJACENCYMATRIXED//而引起的数据重复定义#defineINFINITY32767//最大值∞#defineMAX_VERTEX_NUM20//最大顶点个数typedefintVRType;//权值，即边的值typedefcharInfoType;//附加信息的类型，后面使用时会定义成一个指针typedefcharVertexType[MAX_VERTEX_NUM];//顶点类型typedef

5、enum{DG=1,DN,UDG,UDN}GraphKind;//{有向图，有向网，无向图，无向网}typedefstructArcCell{VRTypeadj;//VRType是顶点关系类型。对无权图，用1或0表示相邻否；对带权图，则为权值类型。InfoType*info;//该弧关系信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量AdjMatrixa

6、rcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数GraphKindkind;//图的种类标志}MGraph;typedefstruct//普里姆算法辅助数组的定义{VertexTypeadjvex;VRTypelowcost;}closedge[MAX_VERTEX_NUM];#endif//结束if2.2程序模块MGraphG;//网G，唯一的全局变量intmain(intargc,char*argv[]);//主函数StatusLocateVex(MGraphG,VertexType

7、v);//判断城市v在网G中的位置StatusCreateUDN(MGraph&G);//创建网G的邻接矩阵voidDisplayNet(MGraphG);//以邻接矩阵的形式显示网GvoidMiniSpanTree_KRUSKAL(MGraphG);//最小生成树的Kruskal算法voidMiniSpanTree_PRIM(MGraphG,VertexTypeu);//最小生成树的Prim算法StatusMinimum(closedgecloseEdge,intn);//Prim算法中求下一个城市的函数voidD

8、eleteInfo(MGraph&G);//释放堆内存上动态申请的空间2.3流程图创建用邻接矩阵表示的城市道路网输入城市数G.vexnum、道路数G.arcnum输入城市名G.vexs[i]输入表示道路的两个城市及道路值G.arcs[i][j].adj返回OK2.3.1创建邻接矩阵的流程图(N-S图)Prim算法化辅助数组closeEdgefo