图的建立与输出设计.doc

湖南商学院计算机软件设计课程设计报告题目 N个城市的最小生成树 姓 名: 学 号: 专 业: 班 级: 指导教师: 职 称:讲师计算机与电子工程学院 目 录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. 运行调试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. 设计任务与要求1.1. 设计任务在指导老师的指导下，运用C/C+软件设计方法，进行软件综合设计和实现，独立设计和开发一个软件系统，此软件系统能够完成生成N个城市的最小生成树。1.2. 设计要求本设计要求以C/C+为主要编程工具，独立完成课题的分析、设计、编码、调试、测试和文档撰写工作。要有详细的设计说明，详细的流程图。画出模块间调用关系图。根据题目要求，充分理解和分析其类型，明确要做什么。对问题描述设计相关的数据类型，结构化程序设计，认真整理源程序及其注释，要有良好的编程格式以及风格。列出调试阶段所遇到的问题和困难。2. 系统功能描述N个城市用N个顶点表示，他们之间的路程表示权值，自动生成N个顶点的无向带权图，用邻接矩阵表示，并在屏幕上打印出来。用普利姆算法求得最小生成树。3. 总体设计3.1. 定义图的类型定义邻接矩阵图类型，其顶点表示各城市，权值表示个城市之间的路程，INF表示不可达，即两城市之间不是直接相连的。3.2. 初始化邻接矩阵图构造一个函数Init_Mgraph()，传入定义的图类型，初始化为NULL。3.3. 建立邻接矩阵图自动生成N个顶点的无向带权图，用邻接矩阵表示法表示，用rand()函数自动分配权值和顶点值。打印邻接矩阵图，以二维数组表示。主函数Main()3.4. 模块间的调用关系图打印图Disp_mg()创建邻接矩阵图Create_Mgraph()初始化图Init_mg()普利姆算法Prim() 4. 详细设计开始4.1. 流程图 初始化图创建图打印图结束4.2. N个城市的表示 邻接矩阵图#define N 5#define INF 100 /表示无穷，即不直接到达typedef struct vertexint no; /顶点编号char info64; /顶点其他信息VerNode; /顶点类型typedef struct graphint edgesNN; /邻接矩阵边数组int n, e; /顶点数 边数VerNode VertexN; /存放顶点信息MGraph; /图的类型4.3. 初始化图void Init_mg(MGraph *mg)mg = NULL;4.4. 创建邻接矩阵图void Create_mg(MGraph *mg)int i, j;int edge = 0; /边数if (mg = NULL)mg = (MGraph *)malloc(sizeof(MGraph);if (mg = NULL)printf(malloc mg failed!n);return;for (i=0;iN; i+)for (j=i; jedgesij = rand()%N;if (i=j)mg-edgesij = 0;if (i!=j & (mg-edgesij = 0)mg-edgesij = INF;if (i!=j & (mg-edgesij != INF)edge+;mg-edgesji = mg-edgesij;mg-n = N;mg-e = edge;4.5. 显示打印矩阵图void Disp_mg(MGraph mg)int i, j;printf(tt);for (i=0; iN; i+)printf(%6d,i);printf(nn);for (i=0; iN; i+)printf(t%6dt,i);for (j=0; jN; j+)printf(%6d,mg.edgesij);printf(n);printf(N个城市有%d条线路n,mg.e);4.6. 普利姆算法求最小生成树void Prim(MGraph mg, int v)int lowcostN;int min;int closestN,i,j,k;for (i=0; iN; i+)lowcosti = mg.edgesvi;closesti = v; for (i=1; iN; i+)min = INF;for (j=0; jN; j+)if (lowcostj!=0 & lowcostjmin)min = lowcostj;k = j; /k记录最近顶点的编号printf(边(%d, %d)的权为：%dn,closestk,k,min);lowcostk = 0;for (j=0; jN; j+)if (mg.edgeskj!=0 & mg.edgeskjlowcostj)lowcostj = mg.edgeskj;closestj = k;5. 运行调试调试步骤是按照函数模块设计来的，首先调试创建图的函数。我按照单步调试方法发现此模块设计中并没有错误，得到了正确的图。并能够正确显示。当我调试转换函数时却发现得到的邻接表图不是我创建的邻接矩阵图，对这个函数执而是打印的其他地址的数据，经过仔细调试发现错误在我传入的参数有问题，我传入的是得到的结构体类型的地址，而在打印函数中我又重新分配了一个内存地址，所以转换的图并不是我传进来的生成图。6. 最后结果7. 收获和总结终于完成了这次的课程设计，因为要考研，所以搞这课程设计的时间实在挤不出来，我仅仅抽了几天的时间来完成这次的课程设计，由于时间紧迫可能在完成的功能和细节上不够全面，不够深入。总结这几天的设计，我发现对于编程我有了更为深刻的认识，原来编程是这般的有趣。课程设计也是这般的有收获。刚开始听到要课程设计的时候我很郁闷，眼看还有几十天就要考研考试了，在这冲刺的时候哪有时间来好好完成课程设计呢，如果随意在网上下一个又觉得浪费了课程设计的初衷，因此，我还是决定花几天的时间好好完成。首先，我就题目思考要运用哪方面的知识去解决，找了一些资料发现用图来表示城市，然后再查找他的最小生成树就可以得到最小代价了。于是我又借了几本数据结构方面的书籍，好好看了下有关图方面的知识，看了几遍后有了基本的动手出发点了，经过几番编程，我终于调试成功得到了最小生成树，很兴奋。在设计的过程中遇到过很多的问题，首先是对于题目的理解，我不知道N个城市究竟该怎样表示。接着在编码的时候，发现打印生成的图时没有得到我生成了图，找了很久也没发现问题，我找了书籍，问了同学才发现是我的设计有问题，在一个函数中重新分配了空间，而打印的却是原先的地址。最后在求最小生成树的时候，我不知道该怎样表示最小生成树，究竟用图示法还是直接以文字表示。终于完成了设计，由于时间仓促，我也没能仔细的审核，不知道有没有达到目的，至于扩展我更是没有去考虑了。总之收获还是很大的，原来在学习之余再编写代码是这般的有趣，这几天的时间没有白费，这也为我写毕业设计打下了基础，让我意识到要完成这种课程设计光是说说或者找找网上资料是远远不够的。感谢这次的实习让我对专业对考研有了更迫切的追求。参考文献1 谭浩强. C语言程序设计(第四版). 北京：清华大学出版社，2010.2 霍洛维兹. 数据结构基础(C语言版). 北京：清华大学出版社，2011.3 李春葆，尹为民，等. 数据结构教程第三版M. 北京：清华大学出版社，2009.附录 程序清单 /* * 文件名：fang.c * 文件描述：建立N个城市的交通带权图，求它的最小生成树 * 作者：房先明 * 修改日期：2011-12-8 */#include #include #define N 10#define INF 100 /表示无穷，即不直接到达typedef struct vertexint no; /顶点编号char info64; /顶点其他信息VerNode; /顶点类型typedef struct graphint edgesNN; /邻接矩阵边数组int n, e; /顶点数 边数VerNode VertexN; /存放顶点信息MGraph; /图的类型/函数声明void Init_mg(MGraph *mg);void Create_mg(MGraph *mg);void Disp_mg(MGraph mg);void Prim(MGraph mg, int v);/* * 主函数：main * 调用函数：Init_mg(MGraph *mg); 初始化图 * Create_mg(MGraph *mg);创建N个城市的带权无向图 * Disp_mg(MGraph mg); 矩阵形式打印图 * Prim(MGraph mg, int v); 普里姆算法求最小生成树 * 函数返回：0；正常返回 */int main()MGraph mg;Init_mg(&mg); /初始化图Create_mg(&mg); /创建图Disp_mg(mg); /打印邻接矩阵图printf(这N个城市的最小生成树：n);Prim(mg, 0); /采用普里姆算法，起始为0return 0;/* * 函数名：Init_mg * 函数说明：初始化图mg * 传入参数：MGraph *mg; 图mg的地址 * 传出参数：MGraph *mg; 图mg的地址 * 函数返回：void */void Init_mg(MGraph *mg)mg = NULL;/* * 函数名：Create_mg * 传入参数：MGraph *mg; 图mg的入口地址 * 传出参数：MGraph *mg; 图mg的入口地址 * 函数返回：void */void Create_mg(MGraph *mg)int i, j;int edge = 0; /边数if (mg = NULL)printf(malloc mg failed!n);return;srand(time(NULL);for (i=0;iN; i+)for (j=i; jedgesij = rand()%N;if (i=j)mg-edgesij = 0;if (i!=j & (mg-edgesij = 0)mg-edgesij = INF;if (i!=j & (mg-edgesij != INF)edge+;mg-edgesji = mg-edgesij;mg-n = N;mg-e = edge;/* * 函数名：Disp_mg * 传入参数：MGraph mg;图mg的描述符 * 传出参数：void * 函数说明：以二维数组形式打印邻接矩阵图 */void Disp_mg(MGraph mg)int i, j;printf(ntt);for (i=0; iN; i+)printf(%6d,i);printf(nn);for (i=0; iN; i+)printf(t%6dt,i);for (j=0; jN; j+)printf(%6d,mg.edgesij);printf(n);printf(N个城市有%d条线路n,mg.e);/* * 函数名：Prim * 传入参数：MGraph mg; 图mg的描述符 * int v; 以v为根节点开始的最小生成树 * 传出参数：void * 函数说明：用普里姆算法求的以v为开始节点的最小生成树 */void Prim(MGraph mg, int v)int lowcostN;int min;int closestN,i,j,k;int sum = 0; /最小生成树代价 初始化为0for (i=0; iN; i+)lowcosti = mg.edgesvi;closesti = v; for (i