图的建立与输出设计

《图的建立与输出设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、湖南商学院《计算机软件设计》课程设计报告题　目N个城市的最小生成树姓名:房先明学号:专业:电子信息工程班级:电信0802指导教师:周红静职称:讲师计算机与电子工程学院2011年11月目录1.设计任务与要求11.1.设计任务11.2.设计要求12.系统功能描述13.总体设计13.1.定义图的类型13.2.初始化邻接矩阵图13.3.建立邻接矩阵图23.4.模块间的调用关系图24.详细设计24.1.流程图24.2.N个城市的表示34.3.初始化图34.4.创建邻接矩阵图34.5.显示打印矩阵图44.6.普利姆算法求最小生成树45.

2、运行调试56.最后结果57.收获和总结6参考文献8附录91.课程设计(实习)评审表姓名房先明学院计电学院学号专业班级电信0802题目N个城市的最小生成树评审意见评审成绩指导教师签名职称评审时间年月日课程设计(实习)作品验收表题目N个城市的最小生成树参与人员姓名房先明班级电信0802学号设计任务与要求：1.独立设计一个由N个城市组成的图的最小生成树。2.根据设计要求，详细分析设计过程。3.编程简练，功能齐全，能正确运行。4.思路清晰，结构明确，并要有详细说明图，设计流程图。作品完成情况：1.程序功能大致全部实现。2.用了邻接矩

3、阵表示法表示图。3.函数模块化设计，解释清晰。4.函数简单明了，设计说明详细。5.功能简单，扩展匮乏。验收情况：验收教师签名：___________　　　　　　年月日注：1.除“验收情况”栏外，其余各栏均由学生在作品验收前填写。2.“验收情况”栏由验收小组按实际验收的情况如实填写。N个城市的最小生成树1.设计任务与要求1.1.设计任务在指导老师的指导下，运用C/C++软件设计方法，进行软件综合设计和实现，独立设计和开发一个软件系统，此软件系统能够完成生成N个城市的最小生成树。1.2.设计要求本设计要求以C/C++为主要编程工

4、具，独立完成课题的分析、设计、编码、调试、测试和文档撰写工作。要有详细的设计说明，详细的流程图。画出模块间调用关系图。根据题目要求，充分理解和分析其类型，明确要做什么。对问题描述设计相关的数据类型，结构化程序设计，认真整理源程序及其注释，要有良好的编程格式以及风格。列出调试阶段所遇到的问题和困难。2.系统功能描述N个城市用N个顶点表示，他们之间的路程表示权值，自动生成N个顶点的无向带权图，用邻接矩阵表示，并在屏幕上打印出来。用普利姆算法求得最小生成树。3.总体设计3.1.定义图的类型定义邻接矩阵图类型，其顶点表示各城市，权值

5、表示个城市之间的路程，INF表示不可达，即两城市之间不是直接相连的。3.2.初始化邻接矩阵图构造一个函数Init_Mgraph()，传入定义的图类型，初始化为NULL。131.1.建立邻接矩阵图自动生成N个顶点的无向带权图，用邻接矩阵表示法表示，用rand()函数自动分配权值和顶点值。打印邻接矩阵图，以二维数组表示。主函数Main()1.2.模块间的调用关系图打印图Disp_mg()创建邻接矩阵图Create_Mgraph()初始化图Init_mg()普利姆算法Prim()2.详细设计开始2.1.流程图初始化图创建图打印图结

6、束131.1.N个城市的表示邻接矩阵图#defineN5#defineINF100//表示无穷，即不直接到达typedefstructvertex{intno;//顶点编号charinfo[64];//顶点其他信息}VerNode;//顶点类型typedefstructgraph{intedges[N][N];//邻接矩阵边数组intn,e;//顶点数边数VerNodeVertex[N];//存放顶点信息}MGraph;//图的类型1.2.初始化图voidInit_mg(MGraph*mg){mg=NULL;}1.3.创建邻

7、接矩阵图voidCreate_mg(MGraph*mg){inti,j;intedge=0;//边数if(mg==NULL)mg=(MGraph*)malloc(sizeof(MGraph));if(mg==NULL){printf("mallocmgfailed!");return;}for(i=0;iedges[i][j]=rand()%N;if(i==j)mg->edges[i][j]=0;if(i!=j&&(mg->edges[i][j]==0))mg-

8、>edges[i][j]=INF;if(i!=j&&(mg->edges[i][j]!=INF))edge++;mg->edges[j][i]=mg->edges[i][j];}mg->n=N;mg->e=edge;}1.1.显示打印矩阵图voidDisp_mg(MGraphmg){int