《数据结构与算法》课程设计成果报告-Kruskal算法实现.doc

河南工程学院数据结构与算法课程设计成果报告Kruskal算法实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1342 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目Kruskal算法实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标11.1课程设计目标11.2 课程设计任务12 分析与设计22.1 题目需求分析22.2 存储结构设计22.3 算法描述32.4 程序流程图42.5 测试程序说明53 程序清单64 测试114.1 测试数据114.2 测试结果分析125 总结13参考文献14 1 课程设计目标与任务1.1 课程设计目标1. 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力，增强理论与实践相结合的技巧。4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。5. 初步了解软件开发的一般过程，培养学习热情以及加强自主学习。6. 训练自己动手分析，解决问题的能力，掌握调试程序，排查错误的常用技巧。7. 增强动手能力，学会结合实际解决问题。1.2 课程设计任务1. 对给定的图结构，用KRUSKAL算法基本思想求解出所有最小生成树2. 最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来3. 给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解2 分析与设计2.1 题目需求分析根据课设题目要求，拟将整体程序分为三大模块。以下是三个模块的大体分析：1. 要确定图的存储形式，通过对题目要求的具体分析。发现该题的主要操作是路径的输出，因此采用边集数组（每个元素是一个结构体，包括起点、终点和权值）和邻接矩阵比较方便以后的编程。2. Kruskal算法。该算法设置了集合A，该集合一直是某最小生成树的子集。在每步决定是否把边（u,v）添加到集合A中，其添加条件是A（u,v）仍然是最小生成树的子集。我们称这样的边为A的安全边，因为可以安全地把它添加到A中而不会破坏上述条件。3. Dijkstra算法。算法的基本思路是：假设每个点都有一对标号（dj,pj）,其中d是从起源点到点j的最短路径的长度（从顶点到其本身的最短路径是零路（没有弧的路），其长度等于零）；pj则是从s到j的最短路径中j点的前一点。2.2 存储结构设计定义一个结构体数组，其空间足够大，可将输入的字符串存于数组中。struct edgesint bv; int tv; int w;2.3 算法描述 1. Kruskal函数： 因为Kruskal需要一个有序的边集数组，所以要先对边集数组排序。其次，在执行中需要判断是否构成回路，因此还需另有一个判断函数seeks，在Kruskal中调用seeks。2. dijkstra函数：因为从一源到其余各点的最短路径共有n-1条，因此可以设一变量vnum作为计数器控制循环。该函数的关键在于dist数组的重新置数。该置数条件是：该顶点是被访问过，并且新起点到该点的权值加上新起点到源点的权值小于该点原权值。因此第一次将其设为：if（sw=0&costuw+distudistw）。3. printpath1函数：该函数主要用来输出源点到其余各点的最短路径。因为在主函数调用该函数前，已经调用了dijkstra函数，所以所需的dist、path、s数组已经由dijkstra函数生成，因此在该函数中，只需用一变量控制循环，一一将path数组中的每一元素回溯至起点即可。其关键在于不同情况下输出形式的不同。4. printpath2函数：该函数主要用来输出两点间的最短路径。其主要部分与printpath1函数相同，只是无需由循环将所有顶点一一输出，只需将path数组中下标为v1的元素回溯至起点并显示出来。2.4 程序流程图程序以kruskal类实现求最小生成树。构造函数接受3个参数，分别是顶点个数，边数，和选项。开始输入顶点个数n输入边数e输入选项aa=1调用insertsort，kruskal函数a=2输入v0调用dijkstra，printpath1函数a=3输入v0,v1调用dijkstra，printpath2函数输入a=4结束 图2.4 主函数流程图2.5 测试程序说明在测试程序时主要遇到一下几类问题：1. 有时函数中一些数组中的数据无法存储。2. 对其进行检验发现没有申请空间大小。3. 在源程序的开头用#define定义数值大小，在使用数组时亦可知道它的空间大小。4. 此函数中有时出现负值。5. 对其进行检验发现在程序中由32767代替。若costuw=32767，那么costuw+distu肯定溢出主负值，因此造成权值出现负值。6. 但是当costuw=32767，那么distw肯定不需要重新置数。所以将if（sw=0&costuw+distudistw）改为：if(sw=0&costuw+distu0) i=seti; return i;void kruskal(edgeset ge,int n,int e)int setMAXE,v1,v2,i,j; for(i=1;in+1;i+)seti=0; i=1; j=1;while(j=e&i=n-1)v1=seeks(set,gej.bv); v2=seeks(set,gej.tv); if(v1!=v2)printf(%d,%d):%dn,gej.bv,gej.tv,gej.w); setv1=v2; i+;j+;void insertsort(edgeset ge,int e)int i,j; for(i=2;i=e;i+) if(gei.wgei-1.w) ge0=gei; j=i-1;while(ge0.wgej.w)gej+1=gej; j-; gej+1=ge0;void dijkstra(int costMAXEMAXE,int distMAXE,int pathMAXE,int sMAXE,int n,int v0)int u,vnum,w,wm; for(w=1;w=n;w+)distw=costv0w; if(costv0w32767) pathw=v0; vnum=1;while(vnumn-1)wm=32767; u=v0; for(w=1;w=n;w+) if(sw=0&distwwm)u=w; wm=distw; su=1; vnum+; for(w=1;w=n;w+) if(sw=0&distu+costuwdistw&costuw!=32767)distw=distu+costuw; pathw=u;void printpath1(int dist,int path,int s,int n,int v0)int i,k; for(i=1;i=n;i+) if(si=1)k=i; while(k!=v0) printf(%d-,k); k=pathk; printf(%d:%dn,k,disti); else printf(%d-%d:32767n,i,v0);void printpath2(int dist,int path,int v0,int v1)int k; k=v1;while(k!=v0)printf(%d-,k); k=pathk; printf(%d:%dn,k,distv1);main()edgeset geMAXE; int costMAXEMAXE,distMAXE,pathMAXE,sMAXE,a,n,e,i,j,k,v0,v1; printf(请输入顶点个数:); scanf(%d,&n); printf(请输入边的条数:); scanf(%d,&e); printf(请输入边的信息（起点，终点，权值）:n); for(i=1;i=e;i+) scanf(%d,%d,%d,&gei.bv,&gei.tv,&gei.w); printf(在下列菜单中进行选择：n); printf(1.kruskal算法（起点，终点）权值）：n); printf(2.shortpath（终点-起点）：n); printf(3.shortpath between two point（终点-起点）：n); printf(4.exit（退出）：n); scanf(%d,&a);while(a!=4)switch(a)case 1:insertsort(ge,e); kruskal(ge,n,e); break;case 2:printf(请输入起始顶点序号:); scanf(%d,&v0); for(i=1;i=n;i+) for(j=1;j=n;j+) costij=32767; for(k=1;k=e;k+) i=gek.bv; j=gek.tv; costij=gek.w; for(i=1;i=n;i+) si=0; sv0=1; dijkstra(cost,dist,path,s,n,v0); printpath1(dist,path,s,n,v0); break;case 3:printf(请输入起始顶点序号:); scanf(%d,&v0); printf(请输入终点序号:); scanf(%d,&v1); for(i=1;i=n;i+) for(j=1;j=n;j+) costij=32767; for(k=1;k=e;k+) i=gek.bv; j=gek.tv; costij=gek.w; for(i=1;i=n;i+) si=0; sv0=1; dijkstra(cost,dist,path,s,n,v0); printpath2(dist,path,v0,v1); break;printf(在下列菜单中进行选择：n);printf(1.kruskal算法（起点，终点）权值）：n);printf(2.shortpath（终点-起点）：n);printf(3.shortpath between two point（终点y cost:z其中表示节点x与y间有一条边，权值为z1-2cost:5 2-3cost:1 2-5cost:3 3-5cost:2 1-7cost:2 4-7cost:3 4-5cost:6 8-9cost:1 7-9cost:9 6-9cost:2 3-9cost:8 7-6cost:3 8-7cost:4 3-6cost:7 5-7cost:10 1-4cost:6 1-3cost:7 5-8cost:3 9-10cost:5 8-10cost:3 5-7cost:10其中，顶点数为10，边数为20。4.2 测试结果分析上述测试数据体现在代码中为： edge e=(1,3,2),(1,2,4)(3,2,1),(2,5,5),(3,5,6); kruskal test(5,4,e); couttest.solve()0) i=seti; return i;void kruskal(edgeset ge,int n,int e)int setMAXE,v1,v2,i,j; for(i=1;in+1;i+)seti=0; i=1; j=1;while(j=e&i=n-1)v1=seeks(set,gej.bv); v2=seeks(set,gej.tv); if(v1!=v2)printf(%d,%d):%dn,gej.bv,gej.tv,gej.w); setv1=v2; i+;j+;void insertsort(edgeset ge,int e)int i,j; for(i=2;i=e;i+) if(gei.wgei-1.w) ge0=gei; j=i-1;while(ge0.wgej.w)gej+1=gej; j-; gej+1=ge0;void dijkstra(int costMAXEMAXE,int distMAXE,int pathMAXE,int sMAXE,int n,int v0)int u,vnum,w,wm; for(w=1;w=n;w+)distw=costv0w; if(costv0w32767) pathw=v0; vnum=1;while(vnumn-1)wm=32767; u=v0; for(w=1;w=n;w+) if(sw=0&distwwm)u=w; wm=distw; su=1; vnum+; for(w=1;w=n;w+) if(sw=0&distu+costuwdistw&costuw!=32767)distw=distu+costuw; pathw=u;void printpath1(int dist,int path,int s,int n,int v0)int i,k; for(i=1;i=n;i+) if(si=1)k=i; while(k!=v0) printf(%d-,k); k=pathk; printf(%d:%dn,k,disti); else printf(%d-%d:32767n,i,v0);void printpath2(int dist,int path,int v0,int v1)int k; k=v1;while(k!=v0)printf(%d-,k); k=pathk; printf(%d:%dn,k,distv1);main()edgeset geMAXE; int costMAXEMAXE,distMAXE,pathMAXE,sMAXE,a,n,e,i,j,k,v0,v1; printf(请输入顶点个数:); scanf(%d,&n); printf(请输入边的条数:); scanf(%d,&e); printf(请输入边的信息（起点，终点，权值）:n); for(i=1;i=e;i+) scanf(%d,%d,%d,&gei.bv,&gei.tv,&gei.w); printf(在下列菜单中进行选择：n); printf(1.kruskal算法（起点，终点）权值）：n); printf(2.shortpath（终点-起点）：n); printf(3.shortpath between two point（终点-起点）：n); printf(4.exit（退出）：n); scanf(%d,&a);while(a!=4)switch(a)case 1:insertsort(ge,e); kruskal