文档介绍：:..Projectl设计报告选题名称:最小生成树问题学院:计算机工程学院专业:计算机科学与技术NIIT班级:计算机1147姓名:刘建成学号:1141317722指导教师: 李笑平张亚红殷路 学年学期:2015〜2016学年第1学期1课题需求描述错误!未定义书签。2总体功能与数据结构设计错误!未定义书签。 错误!未定义书签。 数据结构设计4调试与测试算法设计和程序设计错误!未定义书签。5Project设计总结错误!未定义书签。参考文献1::最小生成树问题:若要在n个城市之间建设通信网络,只需要假设ml条线路即可。如何以最低的经济代价建设这个通信网,是一个网的最小生成树问题。:(1) 利用克鲁斯卡尔算法求网的最小生成树。(2) 。(3) 以文木的形式输出生成树中各条边以及他们的权值。(ac3)5、选做内容:利用堆排序(参见教科书1043节)实现选择权值最小的边数据结构设计程序主要利用图的结构生成图,再利用克鲁斯卡尔算法求出最小生成树。3:(1) 通信线路一旦建立,必然是双向的。因此,构造生成树的网一定是无向的,设图的顶点个数不超过30个,并为就简单起见,网屮边的权值设成小于100的整数,可利用c语言提供的随机函数产生。图的存储结构的选取应和所做操作相适应。(2) 为了便于选择权值最小边,此题的存储结构不应选择邻接矩阵的数组表示法,也不选取邻接表,而是以存储边(带权)的数组表示图。)抽象数据类型(ADT)如下:ADTGRAPH{数据对彖V:V是具有相同特性的数据元素的集合,成为顶点集。数据关系R:R={VR}VR={<v,w>lv,w屈于V且P(v,w),<v,w>表示从v到w的弧,谓词P(v,w)定义了弧vv,w>的意义或信息}基木操作P:CreateGmph(&G,V,VR)初始条件:v是图的顶点集,VR是图屮弧的集合。操作结果:按V和VR的定义构造图G。DestroyGraph(&G)初始条件:图G存在。操作结果:销毁图GLocateVex(G,u)初始条件:图G存在,u和G屮定点有相同特征。操作结果:若图G中存在顶点U,则返回顶点在图中的位置:否则返回其他信息。GetVex(G,v)初始条件:图G存在,v是G中某个顶点。操作结果:返冋v的值tPutVex(&G,v,value)...初始条件:图G存在。操作结果:对v賦值valueo2)存储结构typedefstmct{intbegin;intend;intweight;}edge;typedefstmct{intadj:intweight;}AdjMatrix[MAX][MAX];typedefstmct{AdjMatrixarc;intvexnum,um;}MGraph:流程图:输入给定图的边数和顶点数该函数中主要有6段代码,分别是图的构建代码,对权值排序的代码,交换权值代码,最小生成数代码,找尾代码,主函数代码。6段代码分别实现不同的功能,共同满足题目所需要求。4::调试分析终于,在老师的耐心指导和同学的帮助匚我的课设任务完成了。通过这次课程设计屮遇到的许多问题,我收获颇多,下而就谈一谈我遇到的一个主要问题及相应的产生原因。问题:,程序进入死循环。原現顶点名称与顶点数M于同一数据类型即足int整形,当出现类型冲突时,程序不能识别就会发生冲突。:测验1)事例524536656-|O|x|请输入2与3N间的权值:5请输入有边的2个顶点25请输入2与5之间的权值:3请输入有边的2个顶点53请输入5与3之间的权值I右持]—&屯丁」2、[工点56请输入5与6之间的权值:6情输入有边的2个顶点36请输入3与6之间的权值:4请输入有边的2个顶点34请输入3与4之间的权值:4请输入有边的2个顶点465>project设计总结通过这次试验更深刻的理解了什么是图,怎么样去创造图,利用图來解决实际问题,利用克鲁斯卡尔算法去解决最小生成树问题。参考文献《数据结构(Ci吾言版)》严蔚敏吴伟民编著淸华人学出版社《数据结构严蔚皱》(教学视频)《数据结构锌法实现及解析》髙一凡四安电子科技大学岀版社