图的建立与输出设计.docVIP

湖南商学院 《计算机软件设计》课程设计报告 题　目 N个城市的最小生成树 姓 名: 学 号: 专 业: 班 级: 指导教师: 职 称: 讲师 计算机与电子工程学院 目 录 1. 设计任务与要求 1 1.1. 设计任务 1 1.2. 设计要求 1 2. 系统功能描述 1 3. 总体设计 1 3.1. 定义图的类型 1 3.2. 初始化邻接矩阵图 1 3.3. 建立邻接矩阵图 2 3.4. 模块间的调用关系图 2 4. 详细设计 2 4.1. 流程图 2 4.2. N个城市的表示 3 4.3. 初始化图 3 4.4. 创建邻接矩阵图 3 4.5. 显示打印矩阵图 4 4.6. 普利姆算法求最小生成树 4 5. 运行调试 5 6. 最后结果 5 7. 收获和总结 6 参考文献 8 附录 9 课程设计(实习)评审表 姓 名 房先明 学 院 计电学院 学 号 080910066 专业班级 电信0802 题 目 N个城市的最小生成树 评 审 意 见 评审成绩 指导教师签名 职称 评审时间 年 月 日 课程设计(实习)作品验收表 题目 N个城市的最小生成树 参与人员 姓 名 房先明 班 级 电信0802 学 号 080910066 设计任务与要求： 独立设计一个由N个城市组成的图的最小生成树。 根据设计要求，详细分析设计过程。 编程简练，功能齐全，能正确运行。 思路清晰，结构明确，并要有详细说明图，设计流程图。 作品完成情况： 程序功能大致全部实现。 用了邻接矩阵表示法表示图。 函数模块化设计，解释清晰。 函数简单明了，设计说明详细。 功能简单，扩展匮乏。 验收情况： 验收教师签名：___________ 　　　　　　年 月 日 注：1. 除“验收情况”栏外，其余各栏均由学生在作品验收前填写。 2. “验收情况”栏由验收小组按实际验收的情况如实填写。 N个城市的最小生成树 设计任务与要求 设计任务 在指导老师的指导下，运用C/C++软件设计方法，进行软件综合设计和实现，独立设计和开发一个软件系统，此软件系统能够完成生成N个城市的最小生成树。 设计要求 本设计要求以C/C++为主要编程工具，独立完成课题的分析、设计、编码、调试、测试和文档撰写工作。 要有详细的设计说明，详细的流程图。画出模块间调用关系图。 根据题目要求，充分理解和分析其类型，明确要做什么。对问题描述设计相关的数据类型，结构化程序设计， 认真整理源程序及其注释，要有良好的编程格式以及风格。列出调试阶段所遇到的问题和困难。 系统功能描述 N个城市用N个顶点表示，他们之间的路程表示权值，自动生成N个顶点的无向带权图，用邻接矩阵表示，并在屏幕上打印出来。用普利姆算法求得最小生成树。 总体设计 定义图的类型 定义邻接矩阵图类型，其顶点表示各城市，权值表示个城市之间的路程，INF表示不可达，即两城市之间不是直接相连的。 初始化邻接矩阵图 构造一个函数Init_Mgraph()，传入定义的图类型，初始化为NULL。 建立邻接矩阵图 自动生成N个顶点的无向带权图，用邻接矩阵表示法表示，用rand()函数自动分配权值和顶点值。打印邻接矩阵图，以二维数组表示。 模块间的调用关系图 详细设计 流程图 N个城市的表示 邻接矩阵图 #define N 5 #define INF 100 //表示无穷，即不直接到达 typedef struct vertex { int no; //顶点编号 char info[64]; //顶点其他信息 }VerNode; //顶点类型 typedef struct graph { int edges[N][N]; //邻接矩阵边数组 int n, e; //顶点数 边数 VerNode Vertex[N]; //存放顶点信息 }MGraph; //图的类型 初始化图 void Init_mg(MGraph *mg) { mg = NULL; } 创建邻接矩阵图 void Create_mg(MGraph *mg) { int i, j;