数据结构课程设计报告-最小生成树Kruskal算法.doc

课课 程程 设设 计计 报报 告告 课程设计名称：数据结构课程设计数据结构课程设计 课程设计题目：最小生成树 Kruskal 算法 院（系）： 专 业： 班 级： 学 号： 姓 名： 指导教师： I 目目 录录 1 1 课程设计介绍课程设计介绍.1 1.1 课程设计内容.1 1.2 课程设计要求.1 2 2 课程设计原理课程设计原理.2 2.1 课设题目粗略分析.2 2.2 原理图介绍.4 2.2.1 功能模块图.4 2.2.2 流程图分析.5 3 数据结构分析数据结构分析.11 3.1 存储结构.11 3.2 算法描述.11 4 4 调试与分析调试与分析.13 4.1 调试过程.13 4.2 程序执行过程.13 参考文献参考文献.16 附附 录（录（关关键部分程序清单）键部分程序清单）.17 1 1 1 课程设计介绍课程设计介绍 1.11.1 课程设计内容课程设计内容 编写算法能够建立带权图，并能够用 Kruskal 算法求该图的 最小生成树。最小生成树能够选择图上的任意一点做根结点。最 小生成树输出采用顶点集合和边的集合的形式。 1.21.2 课程设计要求课程设计要求 1. 顶点信息用字符串，数据可自行设定。 2. 参考相应的资料，独立完成课程设计任务。 3. 交规范课程设计报告和软件代码。 2 2 2 课程设计原理课程设计原理 2.12.1 课设题目粗略分析课设题目粗略分析 根据课设题目要求，拟将整体程序分为三大模块。以下是三个模 块的大体分析： 1. 要确定图的存储形式，通过对题目要求的具体分析。发现该题 的主要操作是路径的输出，因此采用边集数组（每个元素是一个结构 体，包括起点、终点和权值）和邻接矩阵比较方便以后的编程。 2. Kruskal 算法。该算法设置了集合 A，该集合一直是某最小生 成树的子集。在每步决定是否把边（u,v）添加到集合 A 中，其添加 条件是 A（u,v）仍然是最小生成树的子集。我们称这样的边为 A 的安全边，因为可以安全地把它添加到 A 中而不会破坏上述条件。 3. Dijkstra 算法。算法的基本思路是：假设每个点都有一对标号 （dj,pj）,其中 d 是从起源点到点 j 的最短路径的长度（从顶点到其本 身的最短路径是零路（没有弧的路） ，其长度等于零） ；pj则是从 s 到 j 的最短路径中 j 点的前一点。求解从起源点 s 到点 j 的最短路径算法 的基本过程如下： 1）初始化。起源点设置为：ds=0,ps为空；所有其它点： di=,pi=？；标记起源点 s，记 k=s，其他所有点设为未标记的。 2）k 到其直接连接的未标记的点 j 的距离，并设置： dj=mindj, dk+lkj 3 式中，lkj是从点 k 到 j 的直接连接距离。 3）选取下一个点。从所有未标记的结点中，选取 dj中最小的一个 i： di=mindj, 所有未标记的点 j 点 i 就被选为最短路径中的一点，并设为已标记的。 4）找到点 i 的前一点。从已标记的点中找到直接连接到 i 的点 j*，作 为前一点，设置： i=j* 5)标记点 i。如果所有点已标记，则算法完全推出，否则，记 k=i，转 到 2）再继续。 而程序中求两点间最短路径算法。其主要步骤是： 调用 dijkstra 算法。 将 path 中的第“终点”元素向上回溯至起点，并显示出来。 4 2.22.2 原理图介绍原理图介绍 2.2.12.2.1 功能模块图功能模块图 开始开始 输入顶点个数 n 输入边数 e 输入边集 显示菜单，进行 选择。 求两点间最短距 离 求两点间最短距 离 Kruskal算法 结束结束 图 2.1 功能模块图 5 2.2.2 流程图分析流程图分析 1. 主函数 开始开始 输入顶点个数 n 输入边数 e 输入选项 a a=1 调用 insertsort，krus kal 函数 a=2 输入 v0 调用 dijkstra，printp ath1 函数 a=3 输入 v0,v1 调用 dijkstra，printpa th2 函数 输入 a=4 结束结束 图 2.2 主函数流程图 2. insertsort 函数 6 开始开始 int i,j for(i=2;i=e;i+) gei.w gei- 1.w ge0=gei; j=i-1; ge0. wgej .w gej+1=gej; j-; Y gej+1=ge0; N Y 结束结束 N 3. 图 2.3 insertsort 函数流程图 7 3Kruskal 函数 开始开始 int setMAXE,v1,v2,i,j; for(i=1;in+1;i+) seti=0; i=1; j=1; j=e v2=seeks(set,gej.tv); printf(%d,%d):%dn,gej.bv,g ej.tv,gej.w); setv1=v2; i+; j+; Y Y 结束结束 N N 图 2.4 Kruskal 函数流程图 8 4. dijkstra 函数 开始开始 int u,vnum,w,wm; for(w=1;w=n;w+) distw=costv0w; if(costv0w32767) pathw=v0;vnum=1; vnumn-1 wm=32767; u=v0; for(w=1;w=n;w+) if(sw=0wm=distw; su=1;vnum+; for(w=1;w=n;w+) if(sw=0pathw=u; Y 结束结束 N 图 2.5 dijkstra 函数流程图 9 5. printpath1 函数 开始开始 int i,k; for(i=1;i=n;i+) si=1 k=i; while(k!=v0) printf(%d-,k); k=pathk; printf(%d:%dn,k,disti); printf(%d- %d:32767n,i,v0); 结束结束 Y N 图 2.6 printpath1 函数流程图 10 6. printpath2 函数 开始开始 int k; k=v1; while(k!=v0) printf(%d-,k);k=pathk; printf(%d:%dn,k,distv1); 结束结束 图 2.7 printpath2 函数流程图 11 3 数据结构分析数据结构分析 3.13.1 存储结构存储结构 定义一个结构体数组，其空间足够大，可将输入的字符串存于数组中。 struct edges int bv; int tv; int w; ; 3.23.2 算法描述算法描述 1. Kruskal 函数： 因为 Kruskal 需要一个有序的边集数组，所以要先对边集数组 排序。其次，在执行中需要判断是否构成回路，因此还需另有一个判 断函数 seeks，在 Kruskal 中调用 seeks。 2. dijkstra 函数： 因为从一源到其余各点的最短路径共有 n-1 条，因此可以设一 变量 vnum 作为计数器控制循环。该函数的关键在于 dist 数组的重新 置数。该置数条件是：该顶点是被访问过，并且新起点到该点的权值 加上新起点到源点的权值小于该点原权值。因此第一次将其设为： 12 if（sw=0 return i; void kruskal(edgeset ge,int n,int e) 18 int setMAXE,v1,v2,i,j; for(i=1;in+1;i+) seti=0; i=1; j=1; while(j=e 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) 19 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; 20 if(costv0w32767) pathw=v0; vnum=1; while(vnumn-1) wm=32767; u=v0; for(w=1;w=n;w+) if(sw=0 wm=distw; su=1; vnum+; for(w=1;w=n;w+) if(sw=0 pathw=u; 21 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) 22 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,v 1; printf(请输入顶点个数:); scanf(%d, printf(请输入边的条数:); scanf(%d, printf(请输入边的信息（起点，终点，权值）:n); 23 for(i=1;i=e;i+) scanf(%d,%d,%d, printf(在下列菜单中进行选择：n); printf(1.kruskal 算法（起点，终点）权值）：n); printf(2.shortpath（终点-起点）：n); printf(3.shortpath between two point（终点-起点）：n); printf(4.exit（退出）：n); scanf(%d, while(a!=4) switch(a) case 1:insertsort(ge,e); kruskal(ge,n,e); break; case 2:printf(请输入起始顶点序号:); scanf(%d, for(i=1;i=n;i+) for(j=1;j=n;j+) costij=32767; for(k=1;k=e;k+) 24 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, printf(请输入终点序号:); scanf(%d, for(i=1;i=n;i+) for(j=1;j=n;j+) costij=32767; for(k=1;k=e;k+) i=gek.bv; 25 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（终点-起点）：n); printf(4.exit（退出）：n); scanf(%d, return 1; 26 课程设计总结：课程设计总结： 本次课程设计涉及到的范围很广，让本人能够比较系统的对 C 语言和数据 结构进行一次整理和复习。同时有了很多的体会和经验。 1. 巩固了以前学过的 C 语言的知识，在这次课程设计中我体会到 C 语言超 强的逻辑性，能够熟练使用 VC+的编译环境，也对这两门课程有了新的认识， 他们既有联系，又相互区别，在编写程序过程中要灵活应用 2. 对数据结构的理解有待加强，算法的知识面也有待于提高。不同的人会 选择不同的算法，所