最小生成树问的题目课程设计报告材料.doc

上传人:夺命阿水 文档编号:26600 上传时间:2022-07-20 格式:DOC 页数:25 大小:301.50KB
返回 下载 相关 举报
最小生成树问的题目课程设计报告材料.doc_第1页
第1页 / 共25页
最小生成树问的题目课程设计报告材料.doc_第2页
第2页 / 共25页
最小生成树问的题目课程设计报告材料.doc_第3页
第3页 / 共25页
最小生成树问的题目课程设计报告材料.doc_第4页
第4页 / 共25页
最小生成树问的题目课程设计报告材料.doc_第5页
第5页 / 共25页
点击查看更多>>
资源描述

《最小生成树问的题目课程设计报告材料.doc》由会员分享,可在线阅读,更多相关《最小生成树问的题目课程设计报告材料.doc(25页珍藏版)》请在课桌文档上搜索。

1、 数据结构课程设计一. 设计目的2二. 设计内容2三概要设计11、功能模块图12、各个模块详细的功能描述1四详细设计21主函数和其他函数的伪码算法22、主要函数的程序流程图63、函数之间的调用关系图13五测试数据与运行结果141正常测试数据与运行结果142、非正常测试数据与运行结果15六调试情况,设计技巧与体会17七参考文献17八附录:源代码17一. 设计目的课程设计是软件设计的综合训练,包括问题分析、总体结构设计、用户界面设计、程序设计根本技能和技巧。能够在设计中逐步提高程序设计能力,培养科学的软件工作方法。而且通过数据结构课程设计能够在下述各方面得到锻炼:1、能根据实际问题的具体情况,结合

2、数据结构课程中的根本理论和根本算法,正确分析出数据的逻辑结构,合理地选择相应的存储结构,并能设计出解决问题的有效算法。2、提高程序设计和调试能力。通过上机实习,验证自己设计的算法的正确性。学会有效利用根本调试方法,迅速找出程序代码中的错误并且修改。3、培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度,进一步提高程序设计水平。二. 设计内容最小生成树问题:设计要求:在n个城市之间建设网络,只需保证连通即可,求最经济的架设方法。存储结构采用多种。求解算法多种。三 概要设计1、功能模块图开始创建一个图功能选择1.建立邻接矩阵2.建立邻接表3. PRIM算法4.kruscal算法完毕2、各个模

3、块详细的功能描述创建一个图:通过给用户信息提示,让用户将城市信息与城市之间的联系关系和连接权值写入程序,并根据写入的数据创建成一个图。功能选择:给用户提示信息,让用户选择相应功能。建立邻接矩阵:将用户输入的数据整理成邻接矩阵并显现在屏幕上。建立邻接表:将用户输入的数据整理成临接表并显现在屏幕上。PRIM算法:利用PRIM算法求出图的最小生成树,即:城市之间最经济的连接方案。四详细设计1主函数和其他函数的伪码算法主函数:void main() MGraph G; Dgevalue dgevalue; CreateUDG(G,dgevalue); char u; cout图创建成功。; cout请

4、根据如下菜单项选择择操作。n; cout *endl; cout *1、用邻接矩阵存储:*endl; cout *2、用邻接表存储:*endl; cout *3、普里姆算法求最经济的连接方案*endl; cout *4、克鲁斯卡尔算法求最经济的连接方案*endl; cout *endlendl; int s; char y=y; while(y=y) cout请选择菜单:s; switch(s) case 1: cout用邻接矩阵存储为:endl; Adjacency_Matrix(G); break; case 2: cout用邻接表存储为:endl; Adjacency_List(G,dg

5、evalue); break; case 3: cout普里姆算法最经济的连接方案为:endl; coutu; MiniSpanTree_PRIM(G,u); break; case 4: cout克鲁斯卡尔算法最经济的连接方案为:endl; MiniSpanTree_KRSL(G,dgevalue); break; default: cout您的输入有误!; break; coutendly; if(y=n) break; 邻接矩阵和临接表的创建:int CreateUDG(MGraph & G,Dgevalue & dgevalue) /构造无向加权图的邻接矩阵 int i,j,k; co

6、utG.vexnumG.arum; cout请输入各个城市名称(分别用一个字符代替):; for(i=0;iG.vexsi; for(i=0;iG.vexnum;+i)/初始化数组 for(j=0;jG.vexnum;+j) G.arcsij.adj=MAX; cout请输入两个城市名称与其连接费用(严禁连接重复输入!):endl; for(k=0;k dgevaluek.ch1 dgevaluek.ch2 dgevaluek.value; i = LocateVex(G,dgevaluek.ch1); j = LocateVex(G,dgevaluek.ch2); G.arcsij.adj

7、= dgevaluek.value; G.arcsji.adj = G.arcsij.adj; return OK; 临接矩阵的输出:void Adjacency_Matrix(MGraph G) /用邻接矩阵存储数据int i,j;for(i=0; iG.vexnum; i+) for(j=0; jG.vexnum; j+) if(G.arcsij.adj=MAX)cout0 ; elsecoutG.arcsij.adj ; coutendl; 邻接表的输出: void Adjacency_List(MGraph G,Dgevalue dgevalue) /用邻接表储存数据int i,j;f

8、or(i=0;iG.vexnum;i+)coutG.vexsi;for(j=0;jG.arum;j+)if(dgevaluej.ch1=G.vexsi&dgevaluej.ch2!=G.vexsi)coutdgevaluej.ch2;else if(dgevaluej.ch1!=G.vexsi&dgevaluej.ch2=G.vexsi)coutdgevaluej.ch1;coutbb endl;最小生成树PRIM算法: void MiniSpanTree_PRIM(MGraph G,char u)/普里姆算法求最小生成树 int i,j,k; Closedge closedge; k = L

9、ocateVex(G,u); for(j=0; jG.vexnum; j+) /辅助数组初始化 if(j != k) closedgej.adjvex = u; closedgej.lowcost = G.arcskj.adj; closedgek.lowcost = 0; for(i=1; iG.vexnum; i+) k = Minimum(G,closedge); cout 城市closedgek.adjvex与城市G.vexsk连接。endl; closedgek.lowcost = 0; for(j=0; jG.vexnum; +j) if(G.arcskj.adj closedge

10、j.lowcost) closedgej.adjvex = G.vexsk; closedgej.lowcost= G.arcskj.adj; int Minimum(MGraph G,Closedge closedge) /求closedge中权值最小的边,并返回其顶点在vexs中的位置 int i,j; double k = 1000; for(i=0; iG.vexnum; i+) if(closedgei.lowcost != 0 & closedgei.lowcost k) k = closedgei.lowcost; j = i; return j; 最小生成树kruscal算法:

11、void MiniSpanTree_KRSL(MGraph G,Dgevalue & dgevalue)/克鲁斯卡尔算法求最小生成树 int p1,p2,i,j; int bjMAX_VERTEX_NUM; /标记数组 for(i=0; iG.vexnum; i+) /标记数组初始化 bji=i; Sortdge(dgevalue,G);/将所有权值按从小到大排序 for(i=0; iG.arum; i+) p1 = bjLocateVex(G,dgevaluei.ch1); p2 = bjLocateVex(G,dgevaluei.ch2); if(p1 != p2) cout 城市dgev

12、aluei.ch1与城市dgevaluei.ch2连接。endl; for(j=0; jG.vexnum; j+) if(bjj = p2) bjj = p1; void Sortdge(Dgevalue & dgevalue,MGraph G)/对dgevalue中各元素按权值按从小到大排序 int i,j; double temp; char ch1,ch2; for(i=0; iG.arum; i+) for(j=i; j dgevaluej.value) temp = dgevaluei.value; dgevaluei.value = dgevaluej.value; dgevalu

13、ej.value = temp; ch1 = dgevaluei.ch1; dgevaluei.ch1 = dgevaluej.ch1; dgevaluej.ch1 = ch1; ch2 = dgevaluei.ch2; dgevaluei.ch2 = dgevaluej.ch2; dgevaluej.ch2 = ch2; 2、主要函数的程序流程图main主函数CreatUDG()建图函数Adjacency_Matrix()邻接矩阵输出函数Adjacency_List()邻接表输出函数MiniSpanTree_PRIM()普里姆算法:根本思想:假设WN=(V,E)是一个含有n个顶点的连通网,T

14、V是WN上最小生成树中顶点的集合,TE是最小生成树中边的集合。显然,在算法执行完毕时,TV=V,而TE是E的一个子集。在算法开始执行时,TE为空集,TV中只有一个顶点,因此,按普利姆算法构造最小生成树的过程为:在所有“其一个顶点已经落在生成树上,而另一个顶点尚未落在生成树上的边中取一条权值为最小的边,逐条加在生成树上,直至生成树中含有n-1条边为止。在此系统中,N是你所需要输入的城市个数。而每条边的权值就是你所输入的每两个城市之间的建设本钱。开始标志顶点1参加U集合寻找满足边的一个顶点在U,另一个顶点在V的最小边形成n-1条边的生成树顶点k参加U修改由顶点k到其他顶点边的权值完毕得到最小生成树

15、MiniSpanTree_KRSL()克鲁斯卡尔算法:根本思想:假设WN=V, E是一个含有N个顶点的连通网。如此按照克鲁斯卡尔算法构造最小生成树的过程为:先构造一个只含n个顶点,而边集为空的子图,假如将该子图中各个顶点看成是各棵树上的根结点,如此它是一个含有n棵树的一个森林。之后,从网的边集E中选取一条权值最小的边,假如该条边的两个顶点分属不同的树,如此将其参加子图,也就是说,将这两个顶点分别所在的两棵树合成一棵树;反之,假如该条边的两个顶点已落在同一棵树上,如此不可取,而应该取下一条权值最小的边再试之。依次类推,直到森林中只有一棵树,也即子图中含有n-1条边为止。在此系统中,N是你所需要输

16、入的城市个数。而每条边的权值就是你所输入的每两个城市之间的建设本钱。LocateVex节点位置函数:Minimum()权值比拟函数:Sortdge()权值排序函数:3、函数之间的调用关系图五测试数据与运行结果1正常测试数据与运行结果2、非正常测试数据与运行结果六调试情况,设计技巧与体会通过此次课程设计,我更深刻地理解了最小生成树问题,知道如何在n个城市之间建设网络,只需保证连通即可,求最经济的架设方法。并且用了多种求解方式。数据结构是学习计算机的一门重要的根底课,在学习数据结构之前我们学习了C语言在我们看来数据结构就是学习C语言的延续。这几天的课程设计让我充分地体会到了上机实践对于计算机编程的

17、重要性。其实在于计算机语言这类课程看重的就是上机的实际操作,不满足于根本理论的学习。上机操作才能让我们更加好的掌握我们所要学习的计算机语言知识。只顾学习理论是远远不够的。实践中可以发现许许多多的问题,然后通过同学教师的帮助,得以解决,让自己的编程能力得到极大的提升。此外,也让我更加明白编程是要解决现实问题的。只有拥有把现实问题理论化的能力,才是编程真正需要达到的境界。七参考文献新编C语言课程设计教程 周二强 编著 清华大学数据结构C语言版 严蔚敏 吴伟民 编著 清华大学八附录:源代码#include #include #include #define MAX_VERTEX_NUM 20 #de

18、fine OK 1 #define ERROR 0 #define MAX 1000 typedef struct Arcell double adj; Arcell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct char vexsMAX_VERTEX_NUM; /节点数组 AdjMatrix arcs; /邻接矩阵 int vexnum,arum; /图的当前节点数和弧数 MGraph; typedef struct Pnode /用于普利姆算法 char adjvex; /节点 double lowcost; /权值 Pnode

19、,ClosedgeMAX_VERTEX_NUM; /记录顶点集U到V-U的代价最小的边的辅助数组定义 typedef struct Knode /用于克鲁斯卡尔算法中存储一条边与其对应的2个节点 char ch1; /节点1 char ch2; /节点2 double value;/权值 Knode,DgevalueMAX_VERTEX_NUM; /- int CreateUDG(MGraph & G,Dgevalue & dgevalue); int LocateVex(MGraph G,char ch); int Minimum(MGraph G,Closedge closedge); v

20、oid MiniSpanTree_PRIM(MGraph G,char u); void Sortdge(Dgevalue & dgevalue,MGraph G); void Adjacency_Matrix(MGraph G);void Adjacency_List(MGraph G,Dgevalue dgevalue);/- int CreateUDG(MGraph & G,Dgevalue & dgevalue) /构造无向加权图的邻接矩阵 int i,j,k; coutG.vexnumG.arum; cout请输入各个城市名称(分别用一个字符代替):; for(i=0;iG.vexs

21、i; for(i=0;iG.vexnum;+i)/初始化数组 for(j=0;jG.vexnum;+j) G.arcsij.adj=MAX; cout请输入两个城市名称与其连接费用(严禁连接重复输入!):endl; for(k=0;k dgevaluek.ch1 dgevaluek.ch2 dgevaluek.value; i = LocateVex(G,dgevaluek.ch1); j = LocateVex(G,dgevaluek.ch2); G.arcsij.adj = dgevaluek.value; G.arcsji.adj = G.arcsij.adj; return OK; i

22、nt LocateVex(MGraph G,char ch) /确定节点ch在图G.vexs中的位置 int a ; for(int i=0; iG.vexnum; i+) if(G.vexsi = ch) a=i; return a; void MiniSpanTree_PRIM(MGraph G,char u)/普里姆算法求最小生成树 int i,j,k; Closedge closedge; k = LocateVex(G,u); for(j=0; jG.vexnum; j+) /辅助数组初始化 if(j != k) closedgej.adjvex = u; closedgej.low

23、cost = G.arcskj.adj; closedgek.lowcost = 0; for(i=1; iG.vexnum; i+) k = Minimum(G,closedge); cout 城市closedgek.adjvex与城市G.vexsk连接。endl; closedgek.lowcost = 0; for(j=0; jG.vexnum; +j) if(G.arcskj.adj closedgej.lowcost) closedgej.adjvex = G.vexsk; closedgej.lowcost= G.arcskj.adj; int Minimum(MGraph G,C

24、losedge closedge) /求closedge中权值最小的边,并返回其顶点在vexs中的位置 int i,j; double k = 1000; for(i=0; iG.vexnum; i+) if(closedgei.lowcost != 0 & closedgei.lowcost k) k = closedgei.lowcost; j = i; return j; void MiniSpanTree_KRSL(MGraph G,Dgevalue & dgevalue)/克鲁斯卡尔算法求最小生成树 int p1,p2,i,j; int bjMAX_VERTEX_NUM; /标记数组

25、 for(i=0; iG.vexnum; i+) /标记数组初始化 bji=i; Sortdge(dgevalue,G);/将所有权值按从小到大排序 for(i=0; iG.arum; i+) p1 = bjLocateVex(G,dgevaluei.ch1); p2 = bjLocateVex(G,dgevaluei.ch2); if(p1 != p2) cout 城市dgevaluei.ch1与城市dgevaluei.ch2连接。endl; for(j=0; jG.vexnum; j+) if(bjj = p2) bjj = p1; void Sortdge(Dgevalue & dgev

26、alue,MGraph G)/对dgevalue中各元素按权值按从小到大排序 int i,j; double temp; char ch1,ch2; for(i=0; iG.arum; i+) for(j=i; j dgevaluej.value) temp = dgevaluei.value; dgevaluei.value = dgevaluej.value; dgevaluej.value = temp; ch1 = dgevaluei.ch1; dgevaluei.ch1 = dgevaluej.ch1; dgevaluej.ch1 = ch1; ch2 = dgevaluei.ch2

27、; dgevaluei.ch2 = dgevaluej.ch2; dgevaluej.ch2 = ch2; void Adjacency_Matrix(MGraph G) /用邻接矩阵存储数据int i,j;for(i=0; iG.vexnum; i+) for(j=0; jG.vexnum; j+) if(G.arcsij.adj=MAX)cout0 ; elsecoutG.arcsij.adj ; coutendl; void Adjacency_List(MGraph G,Dgevalue dgevalue) /用邻接表储存数据int i,j;for(i=0;iG.vexnum;i+)c

28、outG.vexsi;for(j=0;jG.arum;j+)if(dgevaluej.ch1=G.vexsi&dgevaluej.ch2!=G.vexsi)coutdgevaluej.ch2;else if(dgevaluej.ch1!=G.vexsi&dgevaluej.ch2=G.vexsi)coutdgevaluej.ch1;coutbb endl;void main() MGraph G; Dgevalue dgevalue; CreateUDG(G,dgevalue); char u; cout图创建成功。; cout请根据如下菜单项选择择操作。n; cout *endl; cout

29、 *1、用邻接矩阵存储:*endl; cout *2、用邻接表存储:*endl; cout *3、普里姆算法求最经济的连接方案*endl; cout *4、克鲁斯卡尔算法求最经济的连接方案*endl; cout *endlendl; int s; char y=y; while(y=y) cout请选择菜单:s; switch(s) case 1: cout用邻接矩阵存储为:endl; Adjacency_Matrix(G); break; case 2: cout用邻接表存储为:endl; Adjacency_List(G,dgevalue); break; case 3: cout普里姆算法最经济的连接方案为:endl; coutu; MiniSpanTree_PRIM(G,u); break; case 4: cout克鲁斯卡尔算法最经济的连接方案为:endl; MiniSpanTree_KRSL(G,dgevalue); break; default: cout您的输入有误!; break; coutendly; if(y=n) break;

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 在线阅读 > 生活休闲


备案号:宁ICP备20000045号-1

经营许可证:宁B2-20210002

宁公网安备 64010402000986号