数据课程设计报告

1、课程设计报告课程设计名称：数据结构课程设计课程设计题目：最小生成树研究院（系）：专 业:班 级:学 号：姓 名：指导教师:完成日期: TOC o 1-5 h z HYPERLINK l bookmark4 o Current Document 第1章概要设计1 HYPERLINK l bookmark7 o Current Document 1.1题目介绍1 HYPERLINK l bookmark13 o Current Document 1.2功能要求1 HYPERLINK l bookmark19 o Current Document 1.3总体结构1 HYPERLINK l bookm

2、ark22 o Current Document 第2章详细设计2 HYPERLINK l bookmark25 o Current Document 2.1主函数的流程图22.2权值位置判断流程图32.3创建邻接矩阵流程图42.4最小生成树流程图5 HYPERLINK l bookmark28 o Current Document 第3章调试分析6 HYPERLINK l bookmark51 o Current Document 第4章使用说明8 HYPERLINK l bookmark64 o Current Document 参考文献9 HYPERLINK l bookmark73 o

3、 Current Document 附录（程序清单）10第1章概要设计1.1题目介绍若要在n个城市之间建设通讯网络，只需要架设n-1条路线即可。如何让以 最低的经济代价建设这个通讯网，是一个网的最小生成树问题。实现：输入网的顶点集及边集，及边上的权值；利用克鲁斯卡尔算法求网的最小生成树；以文本的形式输出生成树种的各条边以及他们的权值。1.2功能要求独立完成系统的分析、设计、编码、调试以及系统测试；用C语言实现；以文本形式输出生成树种的各条边以及他们的权值。1.3总体结构本程序主要分为两个模块（功能模块图见图1.1）:创建邻接矩阵模块，最小 生成树模块。创建邻接矩阵模块：以邻接矩阵的存储形式创建

4、无向网。最小生成 树模块：生成最小生成树，输出其各条边及权值。图1.1功能模块图第2章详细设计2.1主函数的流程图控制整个程序的运行，控制菜单操作，通过主函数模块分别调用各个模块， 实现各项功能，流程如图2.1所示。图2.1主函数流程图此函数的功能在于判断权值在邻接矩阵的位置，便于存储!图2.2判断权值位置流程图图2.3创建邻接矩阵流程图此函数的功能在于生成最小生成树，并且输出各条边的顶点及权值!图2.4最小生成树流程图第3章调试分析主界面:i青输入顶熹教和边数：（用空格隔开）1、输入顶点数及边数的信息:欢迎建设覆信网请输入顶食损和边数：（用空格隔开）3 32、输入顶点信息:欢迎建设谑信网请输

5、入顶熹妙和边数：（用空格隔开）蠢入3个顶点的信息：（用空格隔开）12 33、输入顶点及权值:陶迎建设通信网清输入顶徵和边数：（用空格隔开）品入3个顶点的信息：（用空格隔开）12 3请输入3条边的两个顶点及权值：（用空格隔开）13S 3 34、输出最小生成树及权值:5、错误分析：（1）变量没定义就使用；解决：定义完变量在使用。（2）子函数嵌套定义；解决：子函数单独定义，可调用。（3）使用数组是越界；解决：注意数组的值，注意不能越界。第4章使用说明1、在VC+环境下，将程序代码输入。2、对输入好的程序进行编译。3、修改编译中出现的错误。4、运行程序。5、在界面中选择相应的功能：（1）输入顶点数及边

6、数（2）输入顶点信息（3）输入顶点及权值（4）输出最小生成树的边及权值6、运行完成结束程序！参考文献严蔚敏、吴伟民.数据结构M.北京：清华大学出版社，2007戴艳等.零基础学算法（第二版）.北京：机械工业出版社，2012.2谭浩强.C语言程序设计（第三版）.北京：清华大学出版社，2005张清国.C语言程序设计教程（第二版）.北京：清华大学出版社，2009张长海.C语言设计M.北京：高等教育出版社，2006吴文虎.程序设计基础（第二版）.北京：清华大学出版社，2004附录（程序清单）代码：#include#include#include#define MAX 100#define MAX_VER

7、TEXNUM 20typedef 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 CreateGra

8、ph(MGraph *G)/创建邻接矩阵Vertex va,vb;printf (-请输入顶点数和边数：(用空格隔开)n)；scanf(%d%d”,&G-vexnum,&G-arcnum);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”

9、,va,vb,&w);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)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(&G);kruskal(G);课程设计总结：通过这次课设学习我对数据结构知识有了更深一层的了解，了提高了对C 语言的认识及实践操作能力。在课设的过程中虽然遇到了许多困难，但是通过上 网查资料和与同学互相讨论，最后顺利完成了课