图的建立与输出设计

湖南商学院计算机软件设计课程设计报告题目N个城市的最小生成树姓名房先明学号080910066专业电子信息工程班级电信0802指导教师周红静职称讲师计算机与电子工程学院2011年11月目录1设计任务与要求111设计任务112设计要求12系统功能描述13总体设计131定义图的类型132初始化邻接矩阵图133建立邻接矩阵图234模块间的调用关系图24详细设计241流程图242N个城市的表示343初始化图344创建邻接矩阵图345显示打印矩阵图446普利姆算法求最小生成树45运行调试56最后结果57收获和总结6参考文献8附录9课程设计实习评审表学号080910066姓名房先明学院计电学院专业班级电信0802题目N个城市的最小生成树评审意见评审成绩指导教师签名职称评审时间年月日课程设计实习作品验收表题目N个城市的最小生成树姓名房先明班级电信0802参与人员学号080910066设计任务与要求1独立设计一个由N个城市组成的图的最小生成树。2根据设计要求，详细分析设计过程。3编程简练，功能齐全，能正确运行。4思路清晰，结构明确，并要有详细说明图，设计流程图。作品完成情况1程序功能大致全部实现。2用了邻接矩阵表示法表示图。3函数模块化设计，解释清晰。4函数简单明了，设计说明详细。5功能简单，扩展匮乏。验收情况验收教师签名_年月日注1除“验收情况”栏外，其余各栏均由学生在作品验收前填写。2“验收情况”栏由验收小组按实际验收的情况如实填写。N个城市的最小生成树1设计任务与要求11设计任务在指导老师的指导下，运用C/C软件设计方法，进行软件综合设计和实现，独立设计和开发一个软件系统，此软件系统能够完成生成N个城市的最小生成树。12设计要求本设计要求以C/C为主要编程工具，独立完成课题的分析、设计、编码、调试、测试和文档撰写工作。要有详细的设计说明，详细的流程图。画出模块间调用关系图。根据题目要求，充分理解和分析其类型，明确要做什么。对问题描述设计相关的数据类型，结构化程序设计，认真整理源程序及其注释，要有良好的编程格式以及风格。列出调试阶段所遇到的问题和困难。2系统功能描述N个城市用N个顶点表示，他们之间的路程表示权值，自动生成N个顶点的无向带权图，用邻接矩阵表示，并在屏幕上打印出来。用普利姆算法求得最小生成树。3总体设计31定义图的类型定义邻接矩阵图类型，其顶点表示各城市，权值表示个城市之间的路程，INF表示不可达，即两城市之间不是直接相连的。32初始化邻接矩阵图构造一个函数INIT_MGRAPH，传入定义的图类型，初始化为NULL。33建立邻接矩阵图自动生成N个顶点的无向带权图，用邻接矩阵表示法表示，用RAND函数自动分配权值和顶点值。打印邻接矩阵图，以二维数组表示。34模块间的调用关系图4详细设计41流程图创建图初始化图结束开始主函数MAIN创建邻接矩阵图CREATE_MGRAPH普利姆算法PRIM打印图DISP_MG初始化图INIT_MG打印图42N个城市的表示邻接矩阵图DEFINEN5DEFINEINF100/表示无穷，即不直接到达TYPEDEFSTRUCTVERTEXINTNO/顶点编号CHARINFO64/顶点其他信息VERNODE/顶点类型TYPEDEFSTRUCTGRAPHINTEDGESNN/邻接矩阵边数组INTN,E/顶点数边数VERNODEVERTEXN/存放顶点信息MGRAPH/图的类型43初始化图VOIDINIT_MGMGRAPHMGMGNULL44创建邻接矩阵图VOIDCREATE_MGMGRAPHMGINTI,JINTEDGE0/边数IFMGNULLMGMGRAPHMALLOCSIZEOFMGRAPHIFMGNULLPRINTF“MALLOCMGFAILEDN“RETURNFORI0IEDGESIJRANDNIFIJMGEDGESIJ0IFIJIFIJMGEDGESJIMGEDGESIJMGNNMGEEDGE45显示打印矩阵图VOIDDISP_MGMGRAPHMGINTI,JPRINTF“TT“FORI0IINCLUDEDEFINEN10DEFINEINF100/表示无穷，即不直接到达TYPEDEFSTRUCTVERTEXINTNO/顶点编号CHARINFO64/顶点其他信息VERNODE/顶点类型TYPEDEFSTRUCTGRAPHINTEDGESNN/邻接矩阵边数组INTN,E/顶点数边数VERNODEVERTEXN/存放顶点信息MGRAPH/图的类型/函数声明VOIDINIT_MGMGRAPHMGVOIDCREATE_MGMGRAPHMGVOIDDISP_MGMGRAPHMGVOIDPRIMMGRAPHMG,INTV/主函数MAIN调用函数INIT_MGMGRAPHMG初始化图CREATE_MGMGRAPHMG创建N个城市的带权无向图DISP_MGMGRAPHMG矩阵形式打印图PRIMMGRAPHMG,INTV普里姆算法求最小生成树函数返回0；正常返回/INTMAINMGRAPHMGINIT_MG/初始化图CREATE_MG/创建图DISP_MGMG/打印邻接矩阵图PRINTF“这N个城市的最小生成树N“PRIMMG,0/采用普里姆算法，起始为0RETURN0/函数名INIT_MG函数说明初始化图MG传入参数MGRAPHMG图MG的地址传出参数MGRAPHMG图MG的地址函数返回VOID/VOIDINIT_MGMGRAPHMGMGNULL/函数名CREATE_MG传入参数MGRAPHMG图MG的入口地址传出参数MGRAPHMG图MG的入口地址函数返回VOID/VOIDCREATE_MGMGRAPHMGINTI,JINTEDGE0/边数IFMGNULLPRINTF“MALLOCMGFAILEDN“RETURNSRANDTIMENULLFORI0IEDGESIJRANDNIFIJMGEDGESIJ0IFIJIFIJMGEDGESJIMGEDGESIJMGNNMGEEDGE/函数名DISP_MG传入参数MGRAPHMG图MG的描述符传出参数VOID函数说明以二维数组形式打印邻接矩阵图/VOIDDISP_MGMGRAPHMGINTI,JPRINTF“NTT“FORI0INIPRINTF“6D“,IPRINTF“NN“FORI0INIPRINTF“T6DT“,IFORJ0JNJPRINTF“6D“,MGEDGESIJPRINTF“N“PRINTF“N个城市有D条线路N“,MGE/函数名PRIM传入参数MGRAPHMG图MG的描述符INTV以V为根节点开始的最小生成树传出参数VOID函数说明用普里姆算法求的以V为开始节点的最小生成树/VOIDPRIMMGRAPHMG,INTVINTLOWCOSTNINTMININTCLOSESTN,I,J,KINTSUM0/最小生成树代价初始化为0FORI0INILOWCOSTIMGEDGESVICL