数据结构最小生成树解决实际问题的课程设计(29页).doc

《数据结构最小生成树解决实际问题的课程设计(29页).doc》由会员分享，可在线阅读，更多相关《数据结构最小生成树解决实际问题的课程设计(29页).doc（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、-郑州工业应用技术学院课程设计说明书题目： 关于最小生成树解决实际问题 姓 名： 周红言 院 （系）： 信息工程学院 专业班级： 16级计算机科学与技术1班 学 号： 1601110026 指导教师： 李秀丽 成 绩： 时间： 2017 年12 月 11日至 2017 年 1 月 7 日-第 24 页-郑州工业应用技术学院课程设计任务书题目 关于最小生成树解决实际问题 专业、班级 16级计算机科学与技术1班 学号 1601110026 姓名 _周红言 主要内容：1、熟悉系统实现工具和上机环境。 2、本课题的可行性分析、开发计划，通过调研完成系统的需求分析。简要叙述技术可行性、经济可行性和操作可

2、行性等。3.根据需求分析进行总体设计、数据库设计以及系统的设计与实现等。基本要求：1.要用到图的先相关数据结构和求最小生成树的两种数据结构算法普里姆算法和克鲁斯卡尔算法，以及储存图的边和点的邻接矩阵。2. 学会使用Microsoft Visual C+ 6.0 集成开发环境。主要参考资料：1 严蔚敏. 数据结构（C语言版）M. 北京：清华大学出版社,1997.2 谭浩强. C程序设计（第三版）M. 北京：清华大学出版社，2005.1. 3 二霍红卫算法设计与分析西安西安电子科技大学出版社，2005.113-127. 完 成 期 限： 2017.12.2-2018.1.7 指导教师签名： 课程负

3、责人签名： 摘 要最小生成树是数据结构中图的一种重要应用，在图中对于n个顶点的连通网可以建立许多不同的生成树，最小生成树就是在所有生成树中总的代价最小的生成树。本课程设计是以邻接矩阵作为图的存储结构,分别采用Prim和Kruskal算法求最小生成树。Kruskal算法和Prim算法是求最小生成树的常用算法它们分别适用于稠密图和稀疏图。最小生成树的应用非常的广，如矿井通风设计和改造最优化方面以及如何搭建最短的网络线缆, 构建造价最低的通讯网络关键词：kruskal算法； prim算法；数据结构； 最小生成树目录摘 要I目录II项目背景III第一章 概述11.1 课程设计目的11.2 课程设计任务

4、11.3基本功能11.4 模块分析1第二章 概要设计说明22.1需求分析22.2数据结构分析22.3设计思路22.4模块调用图32.5数据结构设计32.5.1 抽象数据类型32.5.2 方法描述52.5.3最小生成树的算法分析5第三章 详细设计说明103.1 主函数模块103.2 邻接表输出子模块103.3 邻接矩阵输出子模块103.4 创建邻接矩阵子模块103.5 创建邻接表子模块103.6 prim子模块103.7 kruscal子模块10第四章 调试分析与体会114.1实际完成情况说明114.2 出现的问题及解决方案114.3程序中可以改进的地方11五、运行结果12结束语19参考文献20

5、第一章 概述1.1 课程设计目的本课程设计的目的是了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发。 1.2 课程设计任务问题描述: 已知一个无向连通网表示n个城市以及城市间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。对于n个点的连通网能建立许多不同的生成树，每一棵生成树都可以是一个通信网。我们要选择一棵生成树，使总的耗费最小。 在n个城市之间建设

6、网络，只需保证连同即可，求最经济的架设方法。存储结构采用多种。求解算法多种。程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。1.3 模块分析主模块：用于生成界面和调用各个子模块。Kruscal模块：以kruscal算法实现最小生成树。Prim模块：以prim算法实现最小生成树。邻接表模块：用邻接表方式存储图。邻接表输出模块：输出邻接表。邻接表矩阵模块：用邻接矩阵方式存储图。第二章 概要设计说明2.1需求分析1)建立一个图，其存储方式可以采用邻接矩阵形式，需要定义两个数组，一个存储顶点，一个存储边，存储边的数组表明节点间的连通关系和边的权值；。2)利用普里姆算法和克鲁斯卡尔算法求网的最小生

7、成树3)按顺序输出生成树中各条边以及它们的权值。2.2数据结构分析构造最小生成树的方法：最初生成树为空，即没有一个结点和一条边，首先选择一个顶点作为生成树的根，然后每次从不在生成树中的边中选择一条权值尽可能小的边，为了保证加入到生成树中的边不会造成回路，与该边邻接的两个顶点必须一个已经在生成树中，一个则不在生成树中，若网中有n个顶点（这里考虑的网是一个连通无向图），则按这种条件选择n-1边就可以得到这个网的最小生成树了。详细的过程可以描述为：设置2个集合，U集合中的元素是在生成树中的结点，V-U集合中的元素是不在生成树中的顶点。首先选择一个作为生成树根结点的顶点，并将它放入U集合，然后在那些一

8、端顶点在U集合中，而另一端顶点在V-U集合中的边中找一条权最小的边，并把这条边和那个不在U集合中的顶点加入到生成树中，即输出这条边，然后将其顶点添加到U集合中，重复这个操作n-1次。2.3设计思路问题的解决分别采用普利姆算法以及克鲁斯卡尔算法。1）普利姆算法就是先选择根，把它放到一个集合u中，剩余的顶点放在集合v中。然后选择顶点与v中顶点之间权值最小的一条边，以此类推，如果达到最后一个则返回上一个顶点。2）克鲁斯卡尔算法就是写出所有的顶点，选择权最小的边，然后写出第二小的，以此类推，最终要有一个判断是否生成环，不生成则得到克鲁斯卡尔的最小生成树。2.4模块调用图2.5数据结构设计2.5.1 抽

9、象数据类型ADT Graph数据对象V：v是具有相同特征的数据元素的集合，成为顶点集。数据关系R：R=VRVR|v,w属于v且p(v,w)表示从v到w的弧，谓词p（v,w）定义了弧的意义或信息基本操作：1)Greate Graph(&G，V，VR）初始条件：v是图的顶点集，VR是图中弧的集合。操作条件：按V和VR的定义构造图G。2)LocateVex(G,u)初始条件：图G存在，u和G中顶点有相同的特征。操作条件：若G中存在顶点U，则返回该顶点在图中的位置，则返回其它信息。3）DestoryGraph(&u)；初始条件：图G存在。操作结果：销毁图G。4）GetVex(G, v)；初始条件：图G

10、存在，v是图中某个顶点。操作结果：返回v的值。5）NextAdjVex(G, v, w)；初始条件：图G存在，v是图中某个顶点，w是v的邻接顶点。操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”。6）BFSTraverse(G, Visit( )；初始条件：图G存在，Visit是顶点的应用函数。操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit( )失败，则操作失败。存储结构Typedef struct int adj; int weight;AdjMatrixMAXMAX;Typedef struct d

11、jMatrix arc; int vexnum, arcnum; MGraph;流程图，如图所示：2.5.2 方法描述# delete int_max 10000/* 节点不可达的距离*/#define max 20/*数组最大长度*/Int creatMGraph_L(MGraph_L&G)/用邻接矩阵存储Void 1jjzprint(MGraph_L G)/输出邻接矩阵0Int creatadj(algraph &gra,MGraph_L G)/用邻接表存储图Void adjprint (algraph gra)/输出邻接表Int prim (int gmax,int n)/prim算法V

12、oid kruscal_are(MGraph_L G,algraph gra)/最小生成树kruscal算法2.5.3最小生成树的算法分析在该函数中主要有五段代码块，分别是主函数代码块、邻接矩阵定义模块代码、创建链接矩阵模块代码、最小生成树Prim算法及代价模块代码与最小生成树kruskal算法及代价模块代码，五段代码块分别有着不同的作用，共同满足了课题所需要实现的功能。 1) 主函数模块代码algraph gra; MGraph_L G; int i,d,g2020;char a=a; d=creatMGraph_L(G); vnode v;coutendl注意：若该图为非强连通图(含有多个

13、连通分量)时endl 最小生成树不存在,则显示为非法值endlendl;cout菜单endlendl;cout0、显示该图的邻接矩阵endl;cout1、最小生成树PRIM算法及代价endl;int s; char y=y;while(y=y) cout请选择菜单：s; switch(s)case 0: cout邻接矩阵显示如下：endl; ljjzprint(G); break; case 1: for(i=0;i!=G.vexnum;+i) for(intj=0;j!=G.vexnum;+j) gi+1j+1=G.arcsij.adj; coutprim:endl; prim(g,d);

14、break; coutendly; if(y=n) break; 该主函数用一个循环语句，来执行其它的函数的功能。从键盘输入顶点数和边数上限，再调用定义连接矩阵的函数，后输出创建连接矩阵的信息，再调用creatMGraph（）函数，接着进入菜单，然后再选择输入一个数确定是要输出连接矩阵还是最小生成树及代价，最后选择输入确定字母y或N确定是否继续。 2) 邻接矩阵定义模块代码typedef struct ArcCell int adj; char *info;ArcCell,AdjMatrix2020;typedef struct char vexs20; AdjMatrix arcs; int

15、 vexnum,arcnum;MGraph_L;int localvex(MGraph_L G,char v) int i=0; while(G.vexsi!=v) +i; return i;用typedef struct定义连接矩阵，通过二维数组来存储连接矩阵，并设定参数的最大值为20。3) 创建链接矩阵模块代码 int creatMGraph_L(MGraph_L &G) char v1,v2; int i,j,w; cout创建无向图（城市分布图）endl;cout 请输入图G顶点（城市）和弧（边）的个数:(4 6)不包括“()”G.vexnumG.arcnum; for(i=0;i!=

16、G.vexnum;+i) cout输入顶点（城市）iG.vexsi; for(i=0;i!=G.vexnum;+i)for(j=0;j!=G.vexnum;+j) G.arcsij.adj=int_max; G.arcsij.info=NULL; for(int k=0;k!=G.arcnum;+k) cout输入一条边依附的顶点（城市）和权（距离）:(a b 3)不包括“()”v1v2w; i=localvex(G,v1); j=localvex(G,v2); G.arcsij.adj=w; G.arcsji.adj=w; cout图G邻接矩阵创建成功！endl; return G.vexn

17、um;该语句是从键盘输入顶点数和边数，输入顶点和权值，通过循环语句的调用，最后调用creatMGraph_L（）创建连接矩阵 。4) 最小生成树Prim算法及代价模块代码 int prim(int gmax,int n) int lowcostmax,prevexmax; int i,j,k,min;int sum=o; for(i=2;i=n;i+) lowcosti=g1i; prevexi=1; lowcost1=0; for(i=2;i=n;i+) /形成n-1条边的生成树 min=inf; k=0; for(j=2;j=n;j+) if(lowcostjmin)&(lowcostj!

18、=0)min=lowcostj; k=j; printf(%d,%d)%dt,prevexk-1,k-1,min); sum+=min; lowcostk=0; for(j=2;j=n;j+) if(gkjlowcostj) lowcostj=gkj; prevexj=k; printf(n); cout最少生成树的代价:; coutsum; return 0; 该语句运用一系列的循环语句来实现的，利用前面的创建好的链接矩阵，通过各边权值的比较，最后调用prim()函数，实现最小生成树的生成，同时运用sum把最小生成树各边权值相加得到最小生成树的代价。5) 最小生成树kruskal算法及代价模

19、块代码 void MiniSpanTree(MGraphA *D)/生成最小生成树 int i, j, n, m, SUM=0; int k = 1;int parentM; edge edgesM;for ( i = 1; i vexnum; i+) for (j = i + 1; j vexnum; j+) if (D-arcij.adj = 1) edgesk.begin = i; edgesk.end = j; edgesk.weight = D-arcij.weight; k+;sort(edges, D);for (i = 1; i arcnum; i+) parenti = 0;

20、 printf(最小生成树为:n);for (i = 1; i arcnum; i+)/核心部分 n = Find(parent, edgesi.begin); m = Find(parent, edgesi.end);if (n != m) parentn = m; printf( %dn, edgesi.begin, edgesi.end, edgesi.weight);SUM=SUM+edgesi.weight;cout最少生成树的代价:; coutSUM.该语句运用一系列的循环语句来实现的，利用前面的创建好的链接矩阵，通过各边权值的比较，最后调用MiniSpanTree ()函数，实现

21、最小生成树的生成，同时运用sum把最小生成树各边权值相加得到最小生成树的代价。第三章 详细设计说明3.1 主函数模块首先用creatMGaph_L()函数进行邻接矩阵的初始化，然后调用creatadj()进行邻接表的初始化，然后根据用户输入判断switch()调用哪个模块。3.2 邻接表输出子模块判断否超出了数据的个数，如果没有则输出邻接表的头结点，如果头结点的指针域不为空则输出下一个表节点，以此类推。3.3 邻接矩阵输出子模块是否超出了数据的个数，如果没有则输出G.arcsij.adj中的值。3.4 创建邻接矩阵子模块输入顶点和弧的个数，在输入顶点与顶点之间的权值，生成邻接矩阵。3.5 pr

22、im子模块标志顶点1加入U集合，形成n-1条边的生成树，寻找满足边的一个顶点在U，另一个顶点在V中的最小边，顶点K加入U，修改由顶点K到其他顶点边的权值，最后得到最小生成树。3.6 kruscal子模块确定弧的结点，以及弧的权，比较弧的权的大小并对权小的赋值，确定结点的位置，确保不能生成换，最后的到最小生成树。第四章 调试分析与体会4.1实际完成情况说明程序完成了prim和kruscal求一个图的最小生成树，并对图以邻接表和邻接矩阵的形式进行存储。4.2 出现的问题及解决方案1)数据之间类型不同，引发数据间交换紊乱。指针空间未分配导致系统随机给出一个错误的数据2)在寻找下一个结点时，寻找到最小

23、权值边，将其两端的顶点信息及变的权值存储道辅助数组中。在设计解决这些问题时用多个for循环嵌套查找，判断。3)一些小细节尤其要注意，比如变量的定义，定义的位置。4.3程序中可以改进的地方程序中对于一些没有最小生成树的图，没有判断功能。还有就是进行完一个图的运在做的过程中遇到的问题：1、问题一：求出图中的最小值 现象：求出的最小值是0原因：图中没有连通的两个顶点之间的权值赋值为02、问题二：求最小生成树时，else语句需再调用一个函数 现象：对某些二叉树能求出最小生成树，但不能普遍适应原因：对于找最小生成树边的各种可能没有考虑全面，代码才没有广泛的适应性3、问题三：两个顶点之间的边是否是最小生成

24、树的边现象：代码的功能不能分辨出是否是最小生成树的边原因：把简单的代码写的很复杂，从而杂乱无章出现错误五、运行结果将程序员录入后,让其运行。将会出现一个菜单的界面，执行各种操作均有其对应的代码。要执行何种操作只需输入对应的指令即可进行，在每步操作后均会有相应的提示。运行程序后出界面，运行结果如下图所示：图5.1 初界图面选取选项1进行操作，运行结果如图所示：图5.2 建立邻接矩阵运行图依据提示，分别输入无向图的顶点个数与弧的个数，然后依次输入各个顶点所对应的符号及与各个顶点相关联的弧与权值，存在邻接矩阵中。若选取选项3，运行结果如下图所示：图5.3 求得最小生成树运行图图中显示了求得最小生成树

25、所对应的边、权值与最小生成树的代价结束语通过这次课程设计，我收获了不少的东西。我选择的题目是最小生成树，这个问题看这简单，但是做起来有非常大的困难。平时我们很注重理论学习，但现在看来，实践也是非常重要的，两者缺一不可。在这期间我遇到了不少的问题，问同学，查资料，虽然过程是辛苦琐碎的，但最后成果出来还是很鼓舞人心的。经过我们不懈的努力我们终于完成了本次课程设计，通过这次课程设计，我感觉到要真正做出一个程序并不很容易，但只要用心去做，总会有收获，特别是当我遇到 一个问题，想办法去解决，最后终于找到方法时，心里的那份喜悦之情真是难以形容。编写程序中遇到问题再所难免，应耐心探究其中的原因，从出现问题的

26、地方起，并联系前后程序，仔细推敲，逐个排查。直到最终搞清为止。我们本次做的是图的做小生成树问题，深刻的体会到它的实用性。通过本次课程设计我们发现我们对于C语言和数据结构还有很多地方不知道，今后需要努力学习。通过这次的课程设计过程我到了许多知识，这也是在大学里到目前为止完成的比较完整的一个项目，虽然过程中遇到了许多困难，在同学和老师的帮助下一一克服了。通过不断的发现问题，总结问题和解决问题的过程，使我在此次课程设计活动中不断的提高，和得到了宝贵的经验。最后，我最想感谢的是老师这一学期来为我们辛勤的传授课业知识以及适时地讲解以及细心的指导。我们会谨遵您的教导，将您授予的知识学以致用，将您告诉我们的

27、人生哲理作为我们人生道路的指路明灯。通过本次课程设计，使我理解和掌握了很多实用的东西，在此我表衷心的感谢！参考文献1.计算机专业课程设计中的需求分析J.集美大学学报，2009，10(2)：8992.2.高一凡. 数据结构算法实现及解析M . 西安:西安电子科技大学出版社, 20023.Pascal之父Niklaus Wirth 算法 + 数据结构 = 程序 科学出版社 20014.苏运霖 数据结构与算法 中南工业大学出版社 20025.徐宝文 李志 谭浩强C 程序设计语言(第二版新版) C+程序设计 机械工业出版社 20046.Shaffer 数据结构与算法分析(C+版、JAVA版) 电子工业

28、出版社 1999附 录源代码#include #include #include /using namespace std;#define int_max 10000#define inf 9999#define max 20typedef struct ArcCellint adj;char *info;ArcCell,AdjMatrix2020;typedef struct char vexs20;/定义一个顶点数组AdjMatrix arcs;/定义一个邻接矩阵int vexnum; int arcnum;MGraph_L;int localvex(MGraph_L G,char v)

29、int i=0; while(G.vexsi!=v) +i; return i;int creatMGraph_L(MGraph_L &G)char v1,v2;int i,j,w;cout请输入城市个数和总道路的个数:G.vexnumG.arcnum;for(i=0;i!=G.vexnum;+i)cout输入城市名i+1G.vexsi;for(i=0;i!=G.vexnum;i+)for(j=0;j!=G.vexnum;+j)G.arcsij.adj=int_max;G.arcsij.info=NULL;for(int k=0;k!=G.arcnum;+k)cout请输入两城市之间的距离:v

30、1v2w;/输入一条边依附的两点及权值i=localvex(G,v1);j=localvex(G,v2);G.arcsij.adj=w;/G.arcsji.adj=w;cout*endl; cout图创建成功endl; cout请根据如下进行操作endl;return G.vexnum;void ljjzprint(MGraph_L G)/输出邻接矩阵int i,j;for(i=0;i!=G.vexnum;+i)for(j=0;j!=G.vexnum;+j)if(G.arcsij.adj=10000)cout0 ;elsecoutG.arcsij.adj ;coutendl;typedef s

31、truct arcnode /定义表结点int adjvex;/该弧指向的顶点在图中的位置struct arcnode *nextarc;/链域，指向下一条边或弧的结点char *info;/该弧的信息arcnode;typedef struct vnode/临街链表顶点头结点char data;/数据arcnode *firstarc;/链域vnode,adjlist;typedef struct /表的定义adjlist verticesmax;/定义头结点int vexnum,arcnum;/图的当前顶点数和弧数int kind;/图的种类标志algraph;typedef struct

32、 acr/弧的定义int pre;/弧的一结点int bak;/弧的另一结点int weight;/弧的权edg;int creatadj(algraph &gra,MGraph_L G)/用邻接表存储图int i=0,j=0;arcnode *arc,*tem,*p;for( i=0;i!=G.vexnum;+i)/邻接表的初始化gra.verticesi.data=G.vexsi;/将abcde放入顶点信息域gra.verticesi.firstarc=NULL;/指针域为空for( i=0;iG.vexnum;i+)for( j=0;jG.vexnum;j+)if(gra.vertice

33、si.firstarc=NULL)if(G.arcsij.adj!=int_max&jadjvex=j; gra.verticesi.firstarc=arc; arc-nextarc=NULL; p=arc;elseif(G.arcsij.adj!=int_max&j!=G.vexnum)tem=(arcnode *)malloc(sizeof(arcnode); tem-adjvex=j; p-nextarc=tem; tem-nextarc=NULL; p=tem;gra.vexnum=G.vexnum;gra.arcnum=G.arcnum;return 1;void adjprint

34、(algraph gra)/输出邻接表int i;for(i=0;i!=gra.vexnum;+i)arcnode *p;coutgra.verticesi.datai;p=gra.verticesi.firstarc;while(p!=NULL)coutadjvex;p=p-nextarc;coutendl;typedef struct int adjvex; int lowcost;closedge;int prim(int gmax,int n)/prim算法 int lowcostmax,prevexmax;/lowcost存储当前集合U分别到剩余结点的最短路径prevex存储最短路径

35、在U中的结点 int i,j,k,min; for(i=2;i=n;i+) lowcosti=g1i;/初始化 prevexi=1;/顶点未加入到最小生成树中 lowcost1=0;/标志顶点1加入U集合 for(i=2;i=n;i+)/形成n-1条边的生成树 min=inf; k=0; for(j=2;j=n;j+) if(lowcostjmin)&(lowcostj!=0) min=lowcostj; k=j; printf(%d,%d) %dt,prevexk-1,k-1,min); lowcostk=0;/顶点K加入U for(j=2;j=n;j+) if(gkj0) f=arcvis

36、itedf;return f;void kruscal_arc(MGraph_L G ,algraph gra) /最小生成树kruscal算法edg edgs20;int i,j,k=0;for(i=0;i!=G.vexnum;+i)for(j=i;j!=G.vexnum;+j)if(G.arcsij.adj!=10000)edgsk.pre=i;edgsk.bak=j;edgsk.weight=G.arcsij.adj;+k;int x,y,m,n;int buf,edf;for(i=0;i!=gra.arcnum;+i)arcvisitedi=0;for(j=0;j!=G.arcnum;

37、+j) m=10000; for(i=0;i!=G.arcnum;+i) if(edgsi.weightm) m=edgsi.weight; x=edgsi.pre; y=edgsi.bak; n=i; buf=find(arcvisited,x); edf=find(arcvisited,y); edgsn.weight=10000; if(buf!=edf) arcvisitedbuf=edf; cout(x,y)m; coutendl; void main()algraph gra;MGraph_L G;int i,j,d,g2020;char a=a;d=creatMGraph_L(G);creatadj(gra,G);cout*endl;cout*1.用邻接矩阵存储:*endl;cout*2.用邻接表存储:*endl;cout*3.PRIM算法实现:*