数据结构论文最小生成树【最新】

《数据结构论文最小生成树【最新】》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、3课题：最小生成树问题任课老师：朱节中专业：软件工程年级：2012级班级：1班学号：20122344001姓名：董上琦67目录1.设计题目2.需求分析1）运行环境2）输入的形式和输入值的范围3）输出的形式描述4）功能描述5）测试数据3.概要设计1）抽象数据类型定义描述.2）功能模块设计3）模块层次调用关系图4.详细设计。实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法5.调试分析。包括调试过程中遇到的问题及解决的方法、算法的时间空间复杂性分析、经验体会6.用户使用说明。详细列出每一步的操作说明7.测试结果8.附录：程序设计源代码67一、

2、设计题目1).问题描述在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。2).基本要求以邻接多重表存储无向带权图，利用克鲁斯卡尔算法或普瑞姆算法求网的最小生成树。二、需求分析1）运行环境软件在JDK运行，硬件支持windows系统2）输入的形式和输入值的范围自动生成顶点数据在10~20之间；各个顶点之间权值在25~50之间；通过程序改动亦可生成已知顶点权值之间的最小生成树，需将随机生成代码改为edgeedge[]={newedge(0,1,16),new（0,2,18）......}；将已知顶点、权值通过其函数输入再生成

3、其所对应最小生成树。3）输出的形式描述输出随机生成顶点个数以及各个顶点之间权值；然后输出本次生成顶点之间构成的最小生成树。4）功能描述该程序会自动生成介于10~20个数顶点模拟各城市，再随机生成介于25~50之间数值作为权值模拟各个城市间的距离，并同时生成此次顶点、权值相对应的最小生成树，模拟各城市间的最小距离，最小生成树。如有确定城市顶点及其权值，则可改动程序令其不再随机生成顶点权值，在程序中输入如下代码:edgeedge[]={newedge(0,1,16),new（0,2,18）......}输入数组为edge数组，edge（起点，终点，权值）。通过将随机生

4、成代码改动就可以生成该城市对应权值的最小生成树。5）测试数据生成数据之后检验生成顶点数值是否介于10~20之间；检验各顶点间权值大小是否介于25~50间；同时检验其自动生成最小生成树是否正确。67三、概要设计1）抽象数据类型定义描述定义排序类sort，将各个顶点按照其两顶点之间权值大小排序，从大到小排序，用到堆排序算法；定义带权值的边edge，分别存在start（起点）、end（终点）、value(权值)三个变量；定义main类，调用sort、edge类与自身函数通过Kruskal函数实现最小生成树。2）功能模块设计主函数随机生成10~20个顶点作为城市并同时生成

5、任意两顶点间25~50的权值作为两城市距离；在界面输出随机生成顶点个数及任意两顶点间权值；再调用sort函数对权进行排序，按照权值的大小有小到大排序；排序之后实现Kruskal函数，通过kruskal函数生成最小生成树；最后输出所生成的最小生成树。3）模块层次调用关系图67三、详细设计实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法。1.定义带权值的边及其三个变量start（起点）、end（终点）、value（权值）；定义该属性为下边的根据权值排序、Kruskal实现最小生成树做下铺垫；函数实现如下：packagetree;public

6、classsort{publicstaticvoidsift(edgea[],introot,intlimit){inti=root;intj=i*2+1;//j为i的左孩子while(j<=limit)//沿较小值孩子节点向下筛选{if(ja[i].getValue())//若父亲节点值较大{edgee=a[i];//孩子节点中较小值上移a[i]=a[j];a[j]=e;i=j;j=i*2+

7、1;//i、j向下一层}else{break;//跳出循环}}}publicstaticvoidsort(edgedata[]){intlength=data.length;67for(inti=length/2-1;i>=0;i--)//创建最大堆{sift(data,i,length-1);}for(intj=length-1;j>0;j--)//每趟把最大值交换到后面字，再生成堆{edgee=data[0];data[0]=data[j];data[j]=e;sift(data,0,j-1);}}}1.随机生成介于10~20之间个顶点作为各个城市，并同时生成

8、任意两顶点