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

《数据结构课程设计-最小生成树Kruskal算法.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计-最小生成树Kruskal算法.doc（28页珍藏版）》请在三一文库上搜索。

1、课课 程程 设设 计计 报报 告告 课程设计名称：数据结构课程设计数据结构课程设计 课程设计题目：最小生成树 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

2、 参考文献参考文献.16 附附 录（录（关关键部分程序清单）键部分程序清单）.17 1 1 1 课程设计介绍课程设计介绍 1.11.1 课程设计内容课程设计内容 编写算法能够建立带权图，并能够用 Kruskal 算法求该图的 最小生成树。最小生成树能够选择图上的任意一点做根结点。最 小生成树输出采用顶点集合和边的集合的形式。 1.21.2 课程设计要求课程设计要求 1. 顶点信息用字符串，数据可自行设定。 2. 参考相应的资料，独立完成课程设计任务。 3. 交规范课程设计报告和软件代码。 2 2 2 课程设计原理课程设计原理 2.12.1 课设题目粗略分析课设题目粗略分析 根据课设题目要求，拟

3、将整体程序分为三大模块。以下是三个模 块的大体分析： 1. 要确定图的存储形式，通过对题目要求的具体分析。发现该题 的主要操作是路径的输出，因此采用边集数组（每个元素是一个结构 体，包括起点、终点和权值）和邻接矩阵比较方便以后的编程。 2. Kruskal 算法。该算法设置了集合 A，该集合一直是某最小生 成树的子集。在每步决定是否把边（u,v）添加到集合 A 中，其添加 条件是 A（u,v）仍然是最小生成树的子集。我们称这样的边为 A 的安全边，因为可以安全地把它添加到 A 中而不会破坏上述条件。 3. Dijkstra 算法。算法的基本思路是：假设每个点都有一对标号 （dj,pj）,其中

4、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, 所有未标

5、记的点 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 输入边集 显示菜单，进行 选择。 求两点间最短距 离 求两点间最短距 离 K

6、ruskal算法 结束结束 图 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;i0) i=seti; return i; void kruskal(edgeset ge,in

7、t 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;

8、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

9、 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(“

10、%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“); print

11、f(“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;

12、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

13、=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 课程设计总结：课程设计总结： 本

14、次课程设计涉及到的范围很广，让本人能够比较系统的对 C 语言和数据 结构进行一次整理和复习。同时有了很多的体会和经验。 1. 巩固了以前学过的 C 语言的知识，在这次课程设计中我体会到 C 语言超 强的逻辑性，能够熟练使用 VC+的编译环境，也对这两门课程有了新的认识， 他们既有联系，又相互区别，在编写程序过程中要灵活应用 2. 对数据结构的理解有待加强，算法的知识面也有待于提高。不同的人会 选择不同的算法，所以即使同样的程序，不同的人必然会设计出不同的方案， 所以以后的学习生活中，一定要广泛涉猎，掌握更多更好的解决问题的方法。 3. 此次设计让我意识到程序设计是脑力劳动和体力劳动相结合的，没有平 时基础的训练是不会写出高效的算法。 4. 此次课程设计时间虽短，课设的过程是短暂的，但我所收获的是永恒的。 它让我尝到了学习的快乐，成功的喜悦，更让我懂得了不少做人的道理。要完 成一项任务或把东西学好就必须有足够的信心，持久的耐心，有面对困难无所 畏惧的精神，这对我日后的学习和生活产生了深远一个影响。 指导教师评语： 指导教师(签字)： 年 月 日 课程设计成绩