《最小生成树问题课程设计报告.docx》由会员分享，可在线阅读，更多相关《最小生成树问题课程设计报告.docx（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构课程设计目录一.设计目的错误!未定义书签。二 .设计内容1.概要设计11、功能模块图12、各个模块详细的功能描述2.详细设计31 .主函数和其他函数的伪码算法32、主要函数的程序流程图73、函数之间的调用关系图15.测试数据及运行结果151 .正常测试数据及运行结果162、非正常测试数据及运行结果17.调试情况，设计技巧及体会18三 .参考文献19.附录：源代码19开始开始否基本思想：假设WN=(V,E)是一个含有n个顶点的连通网，TV是WN上最小 生成树中顶点的集合，TE是最小生成树中边的集合。显然，在算法 执行结束时，TV=V,而TE是E的一个子集。在算法开始执行时， TE为空集，
2、TV中只有一个顶点，因此，按普利姆算法构造最小生成 树的过程为：在所有“其一个顶点已经落在生成树上，而另一个顶点 尚未落在生成树上”的边中取一条权值为最小的边，逐条加在生成树 上，直至生成树中含有n-1条边为止。在此系统中，N是你所需要输 入的城市个数。而每条边的权值就是你所输入的每两个城市之间的建 设成本。XMiniSpanTree_KRSL ()克鲁斯卡尔算法:基本思想：假设WN=(V, E)是一个含有N个顶点的连通网。则按照克鲁斯 卡尔算法构造最小生成树的过程为：先构造一个只含n个顶点，而边 集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则 它是一个含有n棵树的一个森林。之后
3、，从网的边集E中选取一条权 值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图， 也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该 条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值 最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含 有n-1条边为止。在此系统中，N是你所需要输入的城市个数。而每 条边的权值就是你所输入的每两个城市之间的建设成本。创建标记数 组并初始化创建标记数 组并初始化将所有权值按 从小到大排序是否扫描完 全部线路寸用标记数组判 断是否形成环输出权值 最小线路形成最小 生成树X Locate Vex ()节点位置函数:结束X Min
4、imum。权值比较函数:开始X Sortdge。权值排序函数：3、函数之间的调用关系图CreateUDGAdjacency_Matrix ()Adjacency_List ()rtiniSpanTree_PRIMOiniSpanTree_KRSLOLocat eVex ()Locat eVex () Sort dge ()Minimum ()Locat eVex ()五.测试数据及运行结果1 .正常测试数据及运行结果6 5 )4人0 3输 工2要 6 11j6 :接 曹连 知符严豚 连费 可营 的罂 之3及 rW名6 5 )4人0 3输 工2要 6 11j6 :接 曹连 知符严豚 连费 可营
5、的罂 之3及 rW名数一 个城城 市T币币城各两AI入入6fs 2一请富111364263345图创建成功。请根据如下菜单选择操作。*工、用邻按矩阵存储:二;：颦i整崔*一里姆算法求最经皆的连接方案* I、克鲁斯卡东算法求息经济而由妾方案*XXXXX-XXXXX-XXXXXX-XXXXXX-X* X-XXXXX x-x请选择菜单:xxxxxxxxxxxxxxxxxxwxxxxxxxxxxxxxxxxxxxxxx请选择菜单：1用邻接矩阵存储为:6 05 0300360 060 042 60是否继续？， 懵选择菜单:y/n : y2用邻接表存储为：1-2-3-42-1-3-53-1-2-4-5-6
6、4-1-3-65-2-3-6634 - 5星不继绩？Si请选择菜单:是否继续？ y/n：nPress anu keu to continue三y :n总连连连声连 直 3 6 5 6 3 法币币币币币1翦连连连连连6 4 2 5 经、币币币币币币 0SHM 法始与与与与与 聿己-13 6 3 2 醺U币币币币币 3晋请是否继续？ 看选择菜单 黄髀卡在城市4与2、非正常测试数据及运行结果是否继续？ 簿选择菜单：用邻接表存储为：1-2-32-1-53-1-645-26-3?单 继择 否选?单 继择 否选算起112 3币币币币经、币币币币币法始与与与与为 案 方 接工zuixiaoshengchen
7、gshu.exe 已停Iki作出现了一个问意,导致程序停止正常工作。如果有可用的解决 方案，Windows将关闭程序并通知您。关闭程序(C)六.调试情况，设计技巧及体会通过此次课程设计，我更深刻地理解了最小生成树问题，知道如何在n个 城市之间建设网络，只需保证连通即可，求最经济的架设方法。并且用了多种求 解方式。数据结构是学习计算机的一门重要的基础课，在学习数据结构之前我们学习 了 C语言在我们看来数据结构就是学习C语言的延续。这几天的课程设计让 我 充分地体会到了上机实践对于计算机编程的重要性。其实在于计算机语言这类课 程看重的就是上机的实际操作，不满足于基本理论的学习。上机操作才能让我们
8、更加好的掌握我们所要学习的计算机语言知识。只顾学习理论是远远不够的。实践中可以发现许许多多的问题，然后通过 同学老师的帮助，得以解决，让自己的编程能力得到极大的提升。此外，也让我 更加明白编程是要解决现实问题的。只有拥有把现实问题理论化的能力，才是编 程真正需要达到的境界。设计目的课程设计是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、 程序设计基本技能和技巧。能够在设计中逐步提高程序设计能力，培养科学的软 件工作方法。而且通过数据结构课程设计能够在下述各方面得到锻炼：1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应
9、的存储结构，并能设计出解决 问题的有效算法。2、提高程序设计和调试能力。通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。3、培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一 步提高程序设计水平。二.设计内容最小生成树问题：设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。 存储结构采用多种。求解算法多种。三.概要设计1、功能模块图七.参考文献新编C语言课程设计教程周二强编著清华大学出版社数据结构（C语言版）严蔚敏吴伟民编著 清华大学出版社八.附录：源代码#include#include#include#d
10、efine MAX_VERTEX_NUM 20#define OK 1#define ERROR 0#define MAX 1000typedef struct Arcell (double adj; ArcelLAdjMatrix M AX_VERTEX_NUM M AX_VERTEX_NUM;typedef struct (char vexsMAX_VERTEX_NUM; 节点数组Adj Matrix arcs; 邻接矩阵int vexnum,arcnum; /图的当前节点数和弧数MGraph;typedef struct Pnode 用于普利姆算法(什char adj vex; 节点do
11、uble lowcost; /权值Pnode,ClosedgeMAX_VERTEX_NUM; 记录顶点集U到V-U的代价最小的边 的辅助数组定义typedef struct Knode/用于克鲁斯卡尔算法中存储一条边及其对应的2个节点 (char ch 1; 节点 1char ch2; /节点 2double value;/权值 Knode,DgevalueMAX_VERTEX_NUM;/int CreateUDG(MGraph & G,Dgevalue & dgevalue);int LocateVex(MGraph G,char ch);int Minimum(MGraph QClosed
12、ge closedge);void 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 ij,k;COUtVV”请输入城市个数及其之间的可连接线路数目：”；cinG.vexnumG.arcnum;cout”
13、请输入各个城市名称(分别用一个字符代替)：”；for(i=0;iG.vexnum;+i)cinG.vexsi;for(i=0;iG.vexnum;+i) 初始化数组for(j=0 ;j G.vexnum ;+j)(G.arcsij.adj=MAX;)coutv”请输入两个城市名称及其连接费用(严禁连接重复输入!)： endl;for(k=0;kG.arcnum;+k)(cin dgevaluek.chl dgevaluek.ch2 dgevaluek.value;i 二 LocateVex(G,dgevaluek.chi);j = Locate Vex(G,dgevaluek.ch2);G.a
14、rcsij.adj = dgevaluek. value;G.arcsji.adj = G.arcsij.adj;)return OK;)int 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 MiniSpanTrcc_PRIM(MGraph Qchar u)普里姆算法求最小生成树int ij,k;Closedge closedge;k = Locate Vex(G,u);for(j=0; jG.vexn
15、um; j+)辅助数组初始化if(j!=k) ( closedgej.adjvex = u; closedgej .lowcost = G.arcskJj.adj;)closedgek.lowcost = 0;for(i=l; iG,vexnum; i+) (k = Minimum(G,closedge);coutn城市vclosedgek.adjvex与城市”vGvexskvv”连接。nendl;closedgek.lowcost = 0;for(j=0; jG.vexnum; +j)(if(G.arcskj.adj closedgej.lowcost) (closedgej.adjvex
16、= Gvexsk;closedgej.lowcost= G.arcskj.adj;)int Minimum(MGraph QClosedge 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 = l;) return j;)void MiniSpanTree_KRSL(MGraph G,Dgevalue &
17、dgevalue)/克鲁斯卡尔算法求最 小生成树intpl,p2JJ；int bjMAX_VERTEX_NUM; 标记数组for(i=0; iG.vexnum; i+) 标记数组初始化bji=i；Sortdge(dgevalue,G);将所有权值按从小到大排序for(i=0; iGarcnum; i+) (pl = bj Locate Vex(G,dgevaluei .ch 1);p2 = bj Locate Vex(G,dgevaluei .ch2);if(pl !=p2) coutn城市 vdgevaluei.chlvv”与城市vdgevaluei.ch2v”连接。endl;for(j=0
18、; jG.vexnum; j+) (if(bjj = p2) bjj =pl；)void Sortdge(Dgevalue & dgevalue,MGraph G)对 dgevahie 中各元素按权值按从小 到大排序(int ij;double temp;char chl,ch2;for(i=0; iG.arcnum; i+) (for(j=i; j dgevaluefj.value) (temp = dgevaluei. value;dgevaluei.value 二 dgevaluej.value;dgevaluefj.value 二 temp;chi = dgevaluei.chl;dg
19、evaluei.chl = dgevaluej.chl;dgevaluej.chl = chi;ch2 = dgevaluei.ch2;dgcvaluci.ch2 = dgcvalucj.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)cout0n H; elsecoutG.arcsij.adjn n;coutendl;)void Adjacency_List
20、(MGraph G,Dgevalue dgevalue) /用邻接表储存数据 (int ij;for(i=();iH;for(j =0;j n;else if(dgevaluej.chl !=G.vexsi&dgevaluej.ch2G.vexsi) coutdge value j .ch 1n -M;coutnbb nendl;)void main()(MGraph G;Dgevalue dgevalue;CreateUDG(Qdgevalue);char u;coutvv图创建成功。cout”请根据如下菜单选择操作。n”；coutn1 1卜卜彳、卜.卜卜彳、；、卜卜彳、卜、彳、卜、.卜 q
21、.卜I coutncoutn*、令R矢目车. *endlcout*2、用令* *”cndl，coutn*3、普里姆算法求最经济的连接方案*”vendl;coutn*4、克鲁斯卡尔算法求最经济的连接方案*”endl;coutnendlendl;int s;char 尸y;while(y=y)(coutv请选择菜单：endl;cins;switch(s)(case 1:coutvv”用邻接矩阵存储为：” vvendl;Adj acency_Matrix(G);break;case 2:cout”用邻接表存储为：“ endl;Adjacency_List(G,dgevalue);break;case
22、 3:cout普里姆算法最经济的连接方案为:”endl;cout ”请输入起始城市名称：”；cinu;MiniSpanTree_PRIM(G,u);break;case 4:cout”克鲁斯卡尔算法最经济的连接方案为:“endl;MiniSpanTree_KRSL(G,dgevalue);break;default:coutvv”您的输入有误!”;break;)coutvendl是否继续？ y/n:H;ciny;if(尸，n)break;)2、各个模块详细的功能描述创建一个图：通过给用户信息提示，让用户将城市信息及城市之间的联系 关系和连接权值写入程序，并根据写入的数据创建成一个图。功能选择：
23、给用户提示信息，让用户选择相应功能。建立邻接矩阵：将用户输入的数据整理成邻接矩阵并显现在屏幕上。建立邻接表：将用户输入的数据整理成临接表并显现在屏幕上。PRIM算法：利用PRIM算法求出图的最小生成树，即：城市之间最经济的 连接方案。四.详细设计1.主函数和其他函数的伪码算法主函数：void main()(MGraph G;Dgevalue dgevalue;CreateUDG(G,dgevalue);char u;cout”图创建成功。”；cout coutn coutH coutH coutn coutn int s;char y=V； while(y=y,)cout”请根据如下菜单选择操
24、作。nn;*1* 7，7，*1* 7，*1* 7，*1* 7，7, 7, 7，.!* 7，7，7，*1* 7, 7，*1* 7，7，*1* 7，7，, 1 ，1 I*T*rT*7* 力、rT* *7* rT*I *1、用邻接矩阵存储：*end* *2、用令R接表存储：*”endl，*3、普里姆算法求最经济的连接方案*”endl;* *4、克鲁斯卡尔算法求最经济的连接方案*”endl;|c|c |cJc nendlendl;coutv请选择菜单：endl;cins;switch(s)(case 1:cout ”用邻接矩阵存储为： endl;Adj acency_Matrix(G);break;c
25、ase 2:cout”用邻接表存储为：Hendl;Adjacency_List(G,dgevalue);break;case 3:cout 普里姆算法最经济的连接方案为:” endl;coutvv”请输入起始城市名称：”;cinu;MiniSpanTree_PRIM(G,u);break;case 4:cout ”克鲁斯卡尔算法最经济的连接方案为:” endl;MiniSpanTree_KRSL(G,dgevalue);break;default:cout ”您的输入有误匕break;)coutendl”是否继续？ y/n:n;ciny;if(y=nf)break;)邻接矩阵和临接表的创建：i
26、nt CreateUDG(MGraph & QDgevalue & dgevalue) 构造无向力口权图的邻接矩阵 (int ij,k;COUtVV”请输入城市个数及其之间的可连接线路数目：”；cinG.vexnumG. arcnum;cout”请输入各个城市名称(分别用一个字符代替)：”；for(i=0;iG.vexnum;+i)cinG.vexsi;for(i=0;iGvexnum;+i) 初始化数组for(j=0;jG.vexnum;+j)(G.arcsij.adj=MAX;)coutv”请输入两个城市名称及其连接费用(严禁连接重复输入!)： nendl;for(k=0;kG.arcnu
27、m;+k)(cin dgevaluek.chl dgevaluek.ch2 dgevaluek.value;i = Locate Vex(G,dgevaluek .chi);j = Locate Vex(G,dgevaluek.ch2);G.arcsijl.adj = dgevaluefk. value;G.arcsji.adj = G.arcsij.adj;)return OK;)临接矩阵的输出：void Adjacency_Matrix(MGraph G) 用邻接矩阵存储数据(int ij;for(i=0; iG.vexnum; i+)(for(j=0; jG.vexnum; j+)if(
28、G.arcsij.adj=MAX)cout0n H;elsecoutG.arcsij.adjn n;coutendl;)邻接表的输出:用邻接表储存数据void Adjacency_List(MGraph G,Dgevalue dgevalue)inti J;for(i=0;in;for(j=();jn;else if(dgevaluej.chl !=G.vexsi&dgevaluej.ch2G.vexsi) coutdge value |j .ch 1;coutnbb nendl;最小生成树PRIM算法:void MiniSpanTree_PRIM(MGraph G, char u)普里姆算法
29、求最小生成树int i, j, k;Closedge closedge;k 二 LocateVex(G, u);for (j=0; jG. vexnum; j+)辅助数组初始化(if(j != k)(closedgej. adjvex = u;closedgej. lowcost = G.arcskj. adj;)closedgek. lowcost = 0;for (i=l; iG. vexnum; i+)(k = Minimum(G, closedge);coutz/ 城市(closedgek. adjvex与城市G. vexsk连 接。“Vendl;closedgek. lowcost
30、= 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, Closedge closedge) 求 closedge 中权值最小的边, 并返回其顶点在vexs中的位置double k = 1000;for(i=0; iG. vexnum; i+)(if(closedgei. lowcost != 0 & closedgei. lowcost k)k
31、二 closedgei. lowcost; J = 1;)return j;)最小生成树kruscal算法：void MiniSpanTree_KRSL(MGraph G,Dgevalue & dgevalue)/克鲁斯卡尔算法求最 小生成树(intpl,p2,ij;int bjMAX_VERTEX_NUM; /标记数组for(i=0; iG.vexnum; i+) 标记数组初始化bji=i;Sortdge(dgevalue,G);将所有权值按从小到大排序for(i=0; iG.arcnum; i+)(pl = bjLocateVex(G,dgevaluei.ch 1);p2 = bj Loc
32、ate Vex(G,dgevaluei .ch2);if(pl !=p2)(cout 城 市 ndgevaluei .ch 1 与城市 ndgevaluei .ch2n 连接。” vvendl;for(j=0; jG.vexnum; j+)(if(bjj = p2)bjj= pl；void Sortdge(Dgevalue & dgevalue,MGraph G)对 dgevalue 中各元素按权值按从小 到大排序(int ij;double temp;char chl,ch2;for(i=0; iG.arcnum; i+)(for(j=i; j dgevaluej.value) temp =
33、 dgevaluei. value;dgevaluei. value = dgevaluej. value;dgevaluej. value = temp;chi = dgevaluei.chl;dgevaluei.chl = dgevaluej.chl;dgevaluej.chl = chi;ch2 二 dgevaluei.ch2;dgevaluei.ch2 = dgevaluej.ch2;dgevaluej.ch2 = ch2;)2、主要函数的程序流程图Xmain ()主函数X CreatUDG()M 图函数/输入城市个数/ /及连接数目/输入各城市名称输入线路 及费用X Adjacency_Matrix()邻接矩阵输出函数是XAdjacency_List()邻接表输出函数