数据课程设计报告--最小生成树

课程设计报告课程设计名称：数据结构课程设计课程设计题目：最小生成树研究院（系）：专业：班级：学号：姓名：指导教师：完成日期：-I-目录第1章概要设计..........................................................................................................11.1题目介绍.................................................................................................................11.2功能要求.................................................................................................................11.3总体结构.................................................................................................................1第2章详细设计..........................................................................................................22.1主函数的流程图....................................................................................................22.2权值位置判断流程图............................................................................................32.3创建邻接矩阵流程图............................................................................................42.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.1主函数流程图开始创建邻接矩阵欢迎建设通信系统生成最小生成树结束-3-2.2权值位置判断流程图此函数的功能在于判断权值在邻接矩阵的位置，便于存储！图2.2判断权值位置流程图开始输入图G及uiG-vexnumStrcmp(G-vexs[i],u)==0输出i输入图G及u结束YNYN-4-2.3创建邻接矩阵流程图此函数的功能在于以邻接矩阵的存储形式创建无向网！图2.3创建邻接矩阵流程图开始输入顶点数及边数初始化邻接矩阵输入顶点及权值结束-5-2.4最小生成树流程图此函数的功能在于生成最小生成树，并且输出各条边的顶点及权值！图2.4最小生成树流程图开始创建set[MAX]数组输入图Gset[a]!=set[b]输出顶点数及权值结束求得Min为最小值NY-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-附录（程序清单）代码：#includestdio.h#includestdlib.h#includestring.h#defineMAX100#defineMAX_VERTEXNUM20typedefcharVertex[MAX];//顶点字符串typedefintAdjmatrix[MAX_VERTEXNUM][MAX_VERTEXNUM];//邻接矩阵typedefstruct//定义图{Vertexvexs[MAX_VERTEXNUM];Adjmatrixarcs;intvexnum,arcnum;}MGraph;intLocateVex(MGraph*G,Vertexu)//判断权值在矩阵的位置{inti;for(i=0;iG-vexnum;++i){if(strcmp(G-vexs[i],u)==0)returni;}return-1;}voidCreateGraph(MGraph*G)//创建邻接矩阵-11-{inti,j,k,w;Vertexva,vb;printf(请输入顶点数和边数：（用空格隔开）\n);scanf(%d%d,&G-vexnum,&G-arcnum);printf(请输入%d个顶点的信息：（用空格隔开）\n,G-vexnum);for(i=0;iG-vexnum;++i)scanf(%s,G-vexs[i]);for(i=0;iG-vexnum;++i)for(j=0;jG-vexnum;++j)G-arcs[i][j]=MAX;printf(请输入%d条边的两个顶点及权值：（用空格隔开）\n,G-vexnum);for(k=0;kG-arcnum;++k){scanf(%s%s%d*c,va,vb,&w);i=LocateVex(G,va);j=LocateVex(G,vb);G-arcs[i][j]=G-arcs[j][i]=w;}}voidkruskal(MGraphG)//最小生成树{intset[MAX_VERTEXNUM],i,j;intk=0,a=0,b=0,min=G.arcs[a][b];for(i=0;iG.vexnum;++i)set[i]=i;printf(最小生成树的各条边及权值为：\n);while(kG.vexnum-1)-12-{for(i=0;iG.vexnum;++i)for(j=0;jG.vexnum;++j)if(G.arcs[i][j]min){min=G.arcs[i][j];a=i;b=j;}if(set[a]!=set[b]){printf(%s-%s-%d\n,G.vexs[a],G.vexs[b],G.arcs[a][b]);k++;for(i=0;G.vexnum;i++)if(set[i]==set[b])set[i]=set[a];min=G.arcs[a][b]=G.arcs[b][a]=MAX;}}}voidmain(){printf(欢迎建设通信网\n);MGraphG;CreateGraph(&G);kruskal(G);}-13-课程设计总结：通过这次课设学习我对数据结构知识有了更深一层的了解，了提高了对C语言的认识及实践操作能力。在课设的过程中虽然遇到了许多困难，但是通过上网查资料和与同学互相讨论，最后顺利完成了课设。在课设过程中深刻体会到了数据结构的应用，也能更好的使用函数。通过这次学习进一步锻炼了实践能力，同时深刻的认识到了熟练运用基本知识是完成程序的基础，这也对我今后的学习奠定了基础，可以让我学习其他语言及知识。这次课程设计让我受益匪浅，也谢谢老师的淳淳教诲！指导教师评语：指导教师(签字)：年月日课程设计成绩