构造可以使n个城市连接的最小生成树.doc

数据结构课程设计说明书学院:信息科学与工程学院班级:计算机11-2完成人:姓名:学号:0姓名:学号:1指导教师:山东科技大学2012年12月13日课程设计任务书一、课程设计题目:构造可以使n个城市连接的最小生成树二、课程设计应解决的主要问题:(1)邻接矩阵的构造及其存储(2)判断是否能够生成最小生成树(3)克鲁斯算法的设计(4)利用克鲁斯算法构造最小生成树时是否产生回路的判断(5)界面的设计三、任务发出日期:2012-11-28课程设计完成日期:2012-12-13小组分工说明小组编号35题目:构造可使n个城市连接的最小生成树小组分工情况:王露:算法设计,voidKruskal()函数,voidset()函数,voidfind()函数,voidUnion()函数王炜程:voidcreat()函数,voidjudge()函数,intmain()函数;intmenu()函数,voiddisplay()函数 组长签字:年月日指导教师对课程设计的评价成绩:指导教师签字:年月日目录主要问题------------------------------------------------------------------5基本要求------------------------------------------------------------------5算法基本思想描述------------------------------------------------------5详细设计------------------------------------------------------------------51、数据结构的设计-----------------------------------------5<1>存储结构-------------------------------------------------------5<2>图的表示--------------------------------------------------------62、算法的设计---------------------------------------------6<1>克鲁斯卡尔算法设计----------------------------------------------6<2>防止不能构成最小生成树的图--------------------------------------6<3>模块结构及功能--------------------------------------------------7<4>主要模块算法描述------------------------------------------------7五、源程序清单-----------------------------------------------------------------9六、测试数据及测试结果-----------------------------------------------------91、开始画面---------------------------------------------------------92、输入信息---------------------------------------------------------103、数据处理---------------------------------------------------------10(1)判断能否构成最小生成树---------------------------------------10(2)遍历所有的最小生成树-----------------------------------------10(3)退出---------------------------------------------------------11七、课程设计总结--------------------------------------------------------------11八、附录--------------------------------------------------------------------------------11参考书目--------------------------------------------------------------------------15构造可以使n个城市连接的最小生成树一、主要问题给定一个地区的n个城市间的距离网,用Prim算法或Kruskal算法建立最小生成树,并计算得到的