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

《最小生成树数据结构课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、河北科技大学课程设计报告学生姓名：白云学号：Z110702301专业班级：计算机113班课程名称：数据结构课程设计学年学期：2013—2014学年第2学期指导教师：郑广2014年6月课程设计成绩评定表学生姓名白云学号Z110702301成绩专业班级计算机113起止时间2014.6.23—2014.6.27设计题目指导教师评语学习态度出勤情况：好□较好□一般□较差□课题工作量：饱满□较大□合理□较小□综合运用知识能力：好□较好□一般□较差□方案设计情况：合理□较合理□基本合理□不合理□课题结果分析能力：强□较强□一般□较差□设计实现情况：全部□

2、大部分□部分□未实现□设计报告内容：详细□完整□较完整□不完整□设计报告文档格式：规范□较规范□基本规范□不规范□独立动手能力：强□较强□一般□较差□指导教师：年月日目录一、需求分析说明11.1最小生成树总体功能要求11.2基本功能11.3模块分析1二、概要设计说明12.1设计思路12.2模块调用图22.3数据结构设计22.3.1.抽象数据类型22.3.2方法描述2三、详细设计说明33.1主函数模块33.2邻接表输出子模块33.3邻接矩阵输出子模块33.4创建邻接矩阵子模块33.5创建邻接表子模块33.6Prim子模块33.7Kruscal子模块4

3、四、调试分析44.1实际完成情况说明44.2出现的问题及解决方案44.3程序中可以改进的地方4六、课程设计总结7七、测试数据7八、参考书目7一、需求分析说明1.1最小生成树总体功能要求在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。1.2基本功能在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。1.3模块分析主模块：用于生成界面和调用各个子模块。Kruscal模块：以kruscal算法实现最小生成树。Prim模块

4、：以prim算法实现最小生成树。邻接表模块：用邻接表方式存储图。邻接表输出模块：输出邻接表。邻接矩阵模块：用邻接矩阵方式存储图。邻接矩阵模块：输出邻接矩阵。二、概要设计说明2.1设计思路问题的解决分别采用普利姆算法以及克鲁斯卡尔算法。1)普利姆算法就是先选择根，把它放入一个集合U中，剩余的顶点放在集合V中。然后选择该顶点与V中顶点之间权值最小的一条边，以此类推，如果达到最后一个则返回上一个顶点。2)克鲁斯卡尔算法就是写出所有的顶点，选择权最小的边，然后写出第二小的，以此类推，最终要有一个判断是否生成环，不生成则得到克鲁斯卡尔的最小生成树。122.2

5、模块调用图主模块Kruscal模块Prim模块邻接表输出模块邻接矩阵输出模块邻接表模块邻接矩阵模块2.3数据结构设计2.3.1.抽象数据类型ADTGraph{数据对象V：v是具有相同特征的数据元素的集合，成为顶点集。数据关系R：R={VR}VR={v,w属于v且p(v,w)表示从v到w的弧，谓词p(v,w)定义了弧的意义或信息}基本操作：1）GreatGraph(&G,V,VR)初始条件：V是图的顶点集，VR是图中弧的集合。操作条件：按V和VR的定义构造图G。2）LocateVex(G,u)初始条件：图G存在，u和G中顶点有相同

6、的特征。操作条件：若G中存在顶点u，则返回该顶点在图中的位置，否则返回其他信息。2.3.2方法描述#defineint_max10000/节点不可达的距离/#definemax20/数组最大长度/intcreatMGraph_L(MGraph_L&G)//用邻接矩阵存储voidljjzprint(MGraph_LG)//输出邻接矩阵intcreatadj(algraph&gra,MGraph_LG)//用邻接表存储图12voidadjprint(algraphgra)//输出邻接表intprim(intg[][max],intn)//prim算法v

7、oidkruscal_arc(MGraph_LG,algraphgra)//最小生成树kruscal算法三、详细设计说明3.1主函数模块首先调用creatMGraph_L()函数进行邻接矩阵的初始化，然后调用creatadj()函数进行邻接表的初始化，然后根据用户输入判断switch()调用哪个模块。3.2邻接表输出子模块首先判断是否超出了数据的个数，如果没有则输出邻接表的头节点，如果头节点的指针域不为空则输出下一个表结点，以此类推。3.3邻接矩阵输出子模块判断是否超出了数据的个数，如果没有则输出G.arcs[i][j].adj中的值。3.4创建邻

8、接矩阵子模块输入顶点和弧的个数，再输入顶点与顶点之间的权值，生成邻接矩阵3.5创建邻接表子模块根据表结构定义一个表，设置表