数据结构课程设计报告-最小生成树研究.doc

课课 程程 设设 计计 报报 告告 课程设计名称：数据结构课程设计 课程设计题目：最小生成树研究 院（系）： 专 业： 班 级： 学 号： 姓 名： 指导教师： 完成日期： -I- 目目 录录 第第 1 章章 概要设计概要设计.1 1.1 题目介绍.1 1.2 功能要求.1 1.3 总体结构.1 第第 2 章章 详细设计详细设计.2 2.1 主函数的流程图.2 2.2 权值位置判断流程图.3 2.3 创建邻接矩阵流程图.4 2.4 最小生成树流程图.5 第第 3 章章 调试分析调试分析.6 第第 4 章章 使用说明使用说明.8 参考文献参考文献.9 附附 录（程序清单）录（程序清单）.10 -1- 第 1 章 概要设计 1.1 题目介绍题目介绍 若要在 n 个城市之间建设通讯网络，只需要架设 n-1 条路线即可。如何让以 最低的经济代价建设这个通讯网，是一个网的最小生成树问题。实现： 1.输入网的顶点集及边集，及边上的权值； 2.利用克鲁斯卡尔算法求网的最小生成树； 3.以文本的形式输出生成树种的各条边 以及他们的权值。 1.2 功能要求功能要求 1.独立完成系统的分析、设计、编码、调试以及系统测试； 2.用 C 语言实现； 3.以文本形式输出生成树种的各条边以及他们的权值。 1.3 总体结构总体结构 本程序主要分为两个模块（功能模块图见图 1.1）：创建邻接矩阵模块，最 小生成树模块。创建邻接矩阵模块：以邻接矩阵的存储形式创建无向网。最小生 成树模块：生成最小生成树，输出其各条边及权值。 最小生成树研究 创 建 邻 接 矩 阵 生 成 最 小 生 成 树 图图 1.1 功能模块图功能模块图 -2- 第 2 章 详细设计 2.1 主函数的流程图主函数的流程图 控制整个程序的运行，控制菜单操作，通过主函数模块分别调用各个模块， 实现各项功能，流程如图 2.1 所示。 图图 2.12.1 主函数流程图主函数流程图 开 始 创建邻接矩阵 欢迎建设通信系统 生成最小生成树 结 束 -3- 2.2 权值位置判断流程图权值位置判断流程图 此函数的功能在于判断权值在邻接矩阵的位置，便于存储！ 图图 2.2 判断权值位置流程图判断权值位置流程图 开 始 输入图 G 及 u ivexnum Strcmp(G-vexsi,u)=0 输出 i输入图 G 及 u 结 束 Y N Y N -4- 2.3 创建邻接矩阵流程图创建邻接矩阵流程图 此函数的功能在于以邻接矩阵的存储形式创建无向网！ 图图 2.3 创建邻接矩阵流程图创建邻接矩阵流程图 开 始 输入顶点数及边数 初始化邻接矩阵 输入顶点及权值 结 束 -5- 2.42.4 最小生成树流程图最小生成树流程图 此函数的功能在于生成最小生成树，并且输出各条边的顶点及权值！ 图图 2.4 最小生成树流程图最小生成树流程图 开 始 创建 setMAX数组 输入图 G seta!=setb 输出顶点数及权值 结 束 求得 Min 为最小值 N Y -6- 第 3 章 调试分析 主界面： 1、输入顶点数及边数的信息： 2、输入顶点信息： 3、输入顶点及权值： -7- 4、输出最小生成树及权值： 5、错误分析： （1）变量没定义就使用； 解决：定义完变量在使用。 （2）子函数嵌套定义； 解决：子函数单独定义，可调用。 （3）使用数组是越界； 解决：注意数组的值，注意不能越界。 -8- 第 4 章 使用说明 1、在 VC+环境下，将程序代码输入。 2、对输入好的程序进行编译。 3、修改编译中出现的错误。 4、运行程序。 5、在界面中选择相应的功能： （1）输入顶点数及边数 （2）输入顶点信息 （3）输入顶点及权值 （4）输出最小生成树的边及权值 6、运行完成结束程序! -9- 参考文献 1 严蔚敏、吴伟民.数据结构M.北京：清华大学出版社，2007 2 戴艳等.零基础学算法（第二版）.北京：机械工业出版社，2012.2 3 谭浩强.C 语言程序设计（第三版）.北京：清华大学出版社，2005 4 张清国.C 语言程序设计教程（第二版）.北京：清华大学出版社，2009 5 张长海.C 语言设计M .北京：高等教育出版社，2006 6 吴文虎.程序设计基础（第二版）.北京：清华大学出版社，2004 -10- 附 录（程序清单） 代码： #include #include #include #define MAX 100 #define MAX_VERTEXNUM 20 typedef char VertexMAX;/顶点字符串 typedef int AdjmatrixMAX_VERTEXNUMMAX_VERTEXNUM;/邻接矩阵 typedef struct/定义图 Vertex vexsMAX_VERTEXNUM; Adjmatrix arcs; int vexnum,arcnum; MGraph; int LocateVex(MGraph* G,Vertex u)/判断权值在矩阵的位置 int i; for(i=0;ivexnum;+i) if(strcmp(G-vexsi,u)=0) return i; return -1; void CreateGraph(MGraph *G)/创建邻接矩阵 -11- int i,j,k,w; Vertex va,vb; printf(请输入顶点数和边数：（用空格隔开）n); scanf(%d%d, printf(请输入%d 个顶点的信息：（用空格隔开）n,G-vexnum); for(i=0;ivexnum;+i) scanf(%s,G-vexsi); for(i=0;ivexnum;+i) for(j=0;jvexnum;+j) G-arcsij=MAX; printf(请输入%d 条边的两个顶点及权值：（用空格隔开）n,G-vexnum); for(k=0;karcnum;+k) scanf(%s%s%d*c,va,vb, i=LocateVex(G,va); j=LocateVex(G,vb); G-arcsij=G-arcsji=w; void kruskal(MGraph G)/最小生成树 int setMAX_VERTEXNUM,i,j; int k=0,a=0,b=0,min=G.arcsab; for(i=0;iG.vexnum;+i) seti=i; printf(最小生成树的各条边及权值为：n); while(kG.vexnum-1) -12- for(i=0;iG.vexnum;+i) for(j=0;jG.vexnum;+j) if(G.arcsijmin) min=G.arcsij; a=i; b=j; if(seta!=setb) printf(%s-%s-%dn,G.vexsa,G.vexsb,G.arcsab); k+; for(i=0;G.vexnum;i+) if(seti=setb) seti=seta; min=G.arcsab=G.arcsba=MAX; void main() printf(欢迎建设通信网n); MGraph G; CreateGraph( kruskal(G); -13- 课程设计总结：课程设计总结： 通过这次课设学习我对数据结构知识有了更深一层的了解，了提高了对 C 语言的认识及实践操作能力。在课设的过程中虽然遇到了许多困难，但是通 过上网查资料和与同学互相讨论，最后顺利完成了课