管道铺设施工的最佳方案问题52

1、WORD整理版优质参考资料优质参考资料问题描述：实验题目：需要在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道即可。假设任意两个小区之间都可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。2基本要求：在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的存储采用邻接表的结构。3测试数据：使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。右侧是给出的参考解。4简述每一部分的对象、目的和要求：主函数部分：对象

2、：图G；目的：为图G分配空间，以作为后续调用函数的参数；要求：无。Create_ALGraph()函数部分：对象：顶点，边及其权值；目的：将顶点，边存放在一起，构成图；要求：构造顶点表，各顶点的邻接表以构造图。Create_WLGraph()函数部分：对象：图G；目的：将图中的权值只存放一次，存放到w指向的结构体中;要求：权值只存放一次，再分别存放该边的左右顶点。selectnfo()函数部分：对象：w指向的结构体；目的：将该结构体中的各权值以升序排列；要求：采用简单选择法进行排序。Create_TLGraph()函数部分：对象：排序后的w指向的结构体；目的：找到构成最小生成树的边；要求：依权

3、值升序排列，判断各边是否构成回路来取舍各边。需求分析1程序所能达到的基本可能：在n个小区m条管道中，选取n-1条管道，实现连通这n个小区，同时权值之和为最小。输入输出形式及输入值范围：程序运行后，用户可根据提示信息：Pleaseinputtheverticesandtheedges:输入顶点数和边数，再根据提示信息：Pleaseinputtheinformationofthevertices:输入顶点信息，然后进入循环，创建各个顶点的邻接表，即根据提示信息Pleaseinputtheinformationofedges:和Pleaseinputtheinformationofweight:依次

4、输入各顶点与其他顶点本身以及两者之间的权值，创建图完毕。用户输入完毕后，程序自动输出运行结果。输入值必须为字母和浮点数，可以不必区分大小写。测试数据要求：用户输入字母时，输入大写或小写，都可以被该程序识别，正常运行。但必须根据提示信息后面给出的参考形式，有针对性地输入逗号。概要设计为了实现上述功能，该程序以邻接表来存储图，因此需要图这个抽象数据类型。1.图抽象数据类型定义：ADTALGraph数据对象：D=ai,bi,Ci|aAdjList,int,qint，i=1,2,3.,n,n_0数据关系：R=;基本操作：Create_ALGraph(G);/创建图Create_WLGraph(G);/

5、将图G中各顶点以及权值存放到新图中，权值只存放一次selectnfo(W,G)；/将新图W中的权值按升序排列Create_TLGraph(w,G);/将最小生成树以顶点对(i,j)的形式输出ADTALGraph2本程序保护模块：主函数模块图模块调用关系:3.主要算法流程图:Create_ALGraph()算法流程图:Create_WLGraph()算法流程图:开始J读入顶点数和边数i=0i=01FFT读入顶点信息i=i+1K=0读入边的对应顶点及权值T读入该权值及左右顶点编号s=s-nexti=i+1将新边表结点插入到顶点Vi的边表头部结束结束Create_TLGraph()算法流程图:详细设

6、计1相关头文件的调用说明：#include#include#defineMaxVerNum1002元素类型、结点类型和结点指针类型：staticvoidforcefloat(float*p)floatf=*p;forcefloat(&f);typedefstructnodeintadjvex;floatinfo;structnode*next;EdgeNode;typedefstructvnodecharvertex;EdgeNode*firstedge;VertexNode;typedefVertexNodeAdjListMaxVerNum;structbianint乙y;floatinfo

7、;；typedefstructcharvMaxVerNum;structbianeMaxVerNum;WGraph;structvisitvisitedMaxVerNum;positionMaxVerNum;vvppMaxVerNumMaxVerNum;3邻接表类型：typedefstructAdjListadjlist;intn,e;ALGraph;/部分基本操作的伪码实现Create_ALGraph(ALGraph*G)inti,j;charp,q;intk;/*intx=0;*/EdgeNode*s;chara,b;printf(Pleaseinputtheverticesandthee

8、dges:n);seanf(%d,%d,&(G-n),&(G-e);printf(Pleaseinputtheinformationofthevertiees:n);getehar();for(i=0;in);i+)seanf(%e，&(G-adjlisti.vertex);G-adjlisti.firstedge=NULL;/*if(G-adjlisti.vertex!=&G-adjlisti.vertex!=n&G-adjlisti.vertex!=)x+;*/for(k=0;ke);k+)printf(Pleaseinputtheinformationofedges:n);getehar

9、();scanf(%e,%e,&p,&q);s=(EdgeNode*)malloc(sizeof(EdgeNode);s-adjvex=q-64;i=p-64;getehar();printf(Pleaseinputtheinformationofweight:n);scanf(%f,&(s-info);WORD整理版WORD整理版优质参考资料优质参考资料s-next=G-adjlisti-1.firstedge;G-adjlisti-1.firstedge=s;/*printf(Pleaseoutputtheinformation:n);printf(%d,%dn,G-n,G-e);prin

10、tf(x=%dn,x);for(i=0;in;i+)printf(%cn,G-adjlisti.vertex);s=G-adjlisti.firstedge;while(s!=NULL)printf(thelinbianis%d,theinfois%.1fn,s-adjvex,s-info);s=s-next;*/intPanduan_Vertex(intk,inti,WGraph*w,EdgeNode*s)intt;for(t=0;tet).y=i+1&(w-et).z=s-adjvex)return1;return0;AJCUr)七ds4u=a)eML:L.&=)七d(+(八0)乂0上)0

11、hnsa.snsa.shnsa.sNSA.SiTr04u=a)eMO4U=a)eMH04u二darAMOJU二darAMHD(llid)七-Ird(04U二da)eMV04u一sAM)七(+r(O)VL+HDO4._Hd)(+(八6)乂0上)04reo匸MdTg(0*lldeo-lWORD整理版WORD整理版优质参考资料优质参考资料intjudge_vertex(WGraph*w,inti,structvisit*vp)if(vp_visitedw_ei.z_1=_1&vp_visitedw_ei.y_1=_1)return1;elseif(vp-visitedw-ei.z-1=-1&vp-v

12、isitedw-ei.y-1=1)return2;elseif(vp-visitedw-ei.y-1=-1&vp-visitedw-ei.z-1=1)return3;elseif(vp-visitedw-ei.z-1=1&vp-visitedw-ei.y-1=1)return4;voidCreate_TLGraph(WGraph*w,ALGraph*G)WGraphT;inti,j,t,h,k=2;intm=1;intabc,bcd;structvisit*vp;vp=(structvisit*)malloc(sizeof(structvisit);for(i=0;in);i+)vp-visi

13、tedi=-1;vp-positioni=-1;vp-vvppi0=i+1;for(j=1;jn;j+)vp-vvppij=O;T.v0=w-vw-e0.z-1;T.v1=w-vw-e0.y-1;vp-visitedw-e0.z-1=1;vp-positionw-e0.z-1=w-e0.z;for(j=0;jn);j+)if(vp-vvppw-e0.z-1j=0)vp-vvppw-e0.z-1j=w-e0.y;break;vp-visitedw-e0.y-1=1;vp-positionw-e0.y-1=w-e0.z;T.=;T.e0.z=w-e0.z;T.e0.

14、y=w-e0.y;for(i=1;ie);i+)t=judge_vertex(w,i,vp);if(t=4)if(vp-positionw-ei.z-1=vp-positionw-ei.y-1)continue;elseabc=0;bcd=0;WORD整理版WORD整理版WORD整理版优质参考资料优质参考资料优质参考资料for(j=0;jn;j+)if(vp-vvppvp-positionw-ei.y-1-1j!=0)abc+;for(j=0;jn;j+)if(vp-vvppvp-positionw-ei.z-1-1j!=0)bcd+;for(j=bcd,h=0;jn&hvvpp(vp-pos

15、itionw-ei.z-1)-1j=vp-vvpp(vp-positionw-ei.y-1)-1h;vp-vvppvp-positionw-ei.y-1-1h=0;for(h=bcd;hposition(vp-vvppvp-positionw-ei.z-1-1h)-1=vp-positionw-ei.z-1;T.=;T.em.z=w-ei.z;T.em.y=w-ei.y;m+;elseif(t=1)vp-visitedw-ei.z-1=1;vp-visitedw-ei.y-1=1;T.vk+=w_vw_ei.z_1;T.vk+=w_vw_ei.y_1;T.em.

16、info=;T.em.z=w-ei.z;T.em.y=w-ei.y;m+;vp-positionw-ei.z-1=w-ei.z;vp-positionw-ei.y-1=w-ei.z;vp-vvppw-ei.z-11=w-ei.y;vp-vvppw-ei.y-10=0;elseif(t=2)vp-visitedw-ei.z-1=1;vp-positionw-ei.z-1=vp-positionw-ei.y-1;for(j=0;jn);j+)if(vp-vvppvp-positionw-ei.y-1-1j=0)vp-vvppvp-positionw-ei.y-1-1j=w-ei.

17、z;break;vp-vvppw-ei.z-10=0;T.vk+=w_vw_ei.z_1;T.=;T.em.z=w-ei.z;T.em.y=w-ei.y;m+;elseif(t=3)vp-visitedw-ei.y-1=1;vp-positionw-ei.y-1=vp-positionw-ei.z-1;for(j=0;jn);j+)if(vp-vvppvp-positionw-ei.z-1-1j=0)vp-vvppvp-positionw-ei.z-1-1j=w-ei.y;break;vp-vvppw-ei.y-10=0;T.vk+=w-vw-ei.y-1;T.

18、=;T.em.z=w-ei.z;T.em.y=w-ei.y;m+;WORD整理版WORD整理版优质参考资料优质参考资料printf(Pleaseoutputtheinformation:n);for(i=0;in)-1;i+)printf(%c,%c)n,T.ei.z+64,T.ei.y+64);voidCreate_WLGraph(ALGraph*G)inti,j,t,m,k=0;EdgeNode*s,*p;WGraph*W;W=(WGraph*)malloc(sizeof(WGraph);W-v0=G-adjlist0.vertex;s=G-adjlist0

19、.firstedge;while(s!=NULL)W-ek.z=1;W-ek.y=s-adjvex;W-=s-info;k+;s=s-next;for(i=1;in);i+)W-vi=G-adjlisti.vertex;s=G-adjlisti.firstedge;while(s!=NULL)m=Panduan_Vertex(k,i,W,s);if(m=1)s=s-next;continue;elseW-ek.z=i+1;W-ek.y=s-adjvex;W-=s-info;k+;s=s-next;/*printf(Pleaseoutputtheinformation

20、:n);for(i=0;in;i+)printf(%cn,W-vi);for(i=0;ie;i+)printf(%d,%d,%.1fn,W-ei.z,W-ei.y,W-);*/select_info(W,G);Create_TLGraph(W,G);4.主函数的伪码:main()ALGraph*G;G=(ALGraph*)malloc(sizeof(ALGraph);Create_ALGraph(G);Create_WLGraph(G);5.函数调用关系：调用select_info()函数调试分析1出现问题及解决方法：在刚开始写程序时，由于考虑不全面，在去除连通图闭合回路的算法中

21、遇到WORD整理版WORD整理版优质参考资料优质参考资料很大困难，后来采用以下方法解决了这个问题：将每个顶点分别放在一个结构体中，结构体中的数组visitedi记录顶点Vi是否被访问过的情况，positioni记录顶点Vi的具体位置，二维数组vvppij记录已经将以该顶点为左顶点或右顶点的权值存入T中后，该权值的右顶点或左顶点的编号。其具体思想是：只要将一个权值存入T中，就将相应的左右顶点放到同一个二维数组中，之后每欲将一个权值加入T中，先检验该权值的两顶点是否在同一个二维数组中。若不在，则将该权值存入T中；若在，将该权值舍去(因为再将该权值加入T中，就会出现回路)。2方法优缺点分析：优点：思

22、想比较简单，容易令人理解；在写核心算法时，先将字母顶点用相应的数字代替，所以在将数字转化成字母回去时，利用数字与ASCII码值的固定差值，可以保证用户在输入时的大小写字母都可以被该程序识别。缺点：由于采用数字来代替字母，中间的转换关系比较复杂，尤其是将对应关系理清需要足够的耐心和细心。3主要算法的时间和空间复杂度分析：由于Create_ALGraph()算法中将读入顶点的操作执行了n次，读入边的操作执行了2m次，故其时间复杂度为O(n+2m);由于Create_WLGraph()算法将读入权值及其左右顶点的操作执行了n次，故其时间复杂度为O(n);由于Create_TLGraph()算法中根据

23、判断是否构成回路来取舍边，因为有n条边，故要执行n次，所以时间复杂度是O(n);由于selectnfo()函数采用简单选择法排序，时间复杂度是O(n2)；所有算法的空间复杂度都是O(1)。使用说明程序运行后，用户根据提示输入顶点数，边数，顶点信息，边的信息，权值,输入完毕后程序会自动以顶点对(i,j)的形式输出最小生成树的边。调试结果输入数据：“9”，“15”，“ABCDEFGHI”，“A,B”，“32.8”，“A,C”，“44.6”，“A,H”,“12.1”，“A,l”，“18.2”，“B,A”，“32.8”，“B,C”，“5.9”，“C,A”，“44.6”，“C,B”，“5.9”，“c,D

24、”，“21.3”,“C,E”，“41.1”，“C,G”，“56.4”，“D,C”，“21.3”，“D,E”，“67.3”，“D,F”，“98.7”，“E,C”，“41.1”，“E,D”，“67.3”，“E,F”“85.6”,“79.2”，“G,C”，“56.4”,“H,G”，“52.5”，“H,l”，(双引号不需输入)“E,G”，“10.5”，“F,D”,“98.7”，“F,E”，“85.6”，“F,l”,“G,E”，“10.5”，“G,H”，“52.5”，“H,A”，“12.1”,“8.7”,“I,A”,“18.2”,“l,F”,“79.2”,“l,H”,“8.7”输出数据：(B,C),(H

25、,I),(E,G),(A,H),(C,D),(A,B),(C,E),(F,I)运行结果截屏:swwswsswsswswwswssws=录aA2A5AasAABAaAA2AA2aaACIGHDBEI附ale-ece5E0-eHe-eAe二Ga-ele?eAe二Fe-67ezz-:L*191i.&l1.0Li.21izllii(l&L!-iiBHEACACF卩卩戸7卩仑丘戸心戸九卩匚戸卩3:卩萱卩”卩5:戸：1:卩卩1戸丄戸1丘7戸1卩00卩|A源程序清单:#include#include/*调用的头文件库说明*/#defineMaxVerNum100staticvoidforcefloat(fl

26、oat*p)floatf=*p;forcefloat(&f);typedefstructnodeintadjvex;floatinfo;structnode*next;EdgeNode;/*由于我的TC中不支持浮点数，故添加了这个程序段*/*构造邻接表的结构体*/*存放权值*/*指向下一个邻接点的指针域*/*构造顶点表的结构体*/*顶点域*/*边表头指针*/typedefstructvnodecharvertex;EdgeNode*firstedge;VertexNode;typedefVertexNodeAdjListMaxVerNum;/*构造图的结构体*/*邻接表*/*顶点数和边数*/t

27、ypedefstructAdjListadjlist;intn,e;ALGraph;structbianint乙y;floatinfo;typedefstructcharvMaxVerNum;structbianeMaxVerNum;WGraph;structvisit/*存放权值及其左右顶点的结构体*/*用该结构体来只存放一次权值及其相应的顶点*/visitedMaxVerNum;positionMaxVerNum;vvppMaxVerNumMaxVerNum;Create_ALGraph(ALGraph*G)inti,j;charp,q;intk;/*用该结构体来存放各结点被访问的情况,位

28、置，和其他结点的关系*/*创建图*/EdgeNode*s;chara,b;printf(Pleaseinputtheverticesandtheedges:n);/*输入顶点数和边数*/scanf(%d,%d,&(G-n),&(G-e);printf(Pleaseinputtheinformationofthevertices:n);getchar();for(i=0;in);i+)scanf(%c,&(G-adjlisti.vertex);G-adjlisti.firstedge=NULL;for(k=0;ke);k+)/*建立有n各顶点的顶点表*/*读入顶点信息*/*建立边表*/print

29、f(Pleaseinputtheinformationofedges:n);getchar();scanf(%c,%c,&p,&q);/*读入边的顶点*/s=(EdgeNode*)malloc(sizeof(EdgeNode);s_adjvex=q_64;i=p-64;/*邻接点的序号为q-64*/getchar();printf(Pleaseinputtheinformationofweight:n);/*读入权值*/*判断该边是不是已经读向的结构体中*/*将w指向的结构体中各权值排列*/*简单选择排序*/*将两条边的权值左右顶点都进行交换*/scanf(%f,&(s_info);s-nex

30、t=G-adjlisti-1.firstedge;/*将新边表结点s插入到顶点Vi的边表头部*/G-adjlisti-1.firstedge=s;intPanduan_Vertex(intk,inti,WGraph*w,EdgeNode*s)入到w指intt;for(t=0;tet).y=i+1&(w_et).z=s_adjvex)return1;return0;voidselect_info(WGraph*W,ALGraph*G)按升序inti,j,p,k;floatt;for(i=0;ie);i+)p=i;for(j=i+1;je);j+)if(W-)p=j;i

31、f(p!=i)t=W-;W-=W-;W-=t;k=W-ep.z;W-ep.z=W-ei.z;W-ei.z=k;k=W-ep.y;W-ep.y=W-ei.y;W-ei.y=k;/*for(i=0;ie);i+)printf(%.1f,W-);printf(n);*/intjudge_vertex(WGraph*w,inti,structvisit*vp)/*判断顶点的访问情况*/if(vp-visitedw-ei.z-1=-1&vp-visitedw-ei.y-1=-1)return1;elseif(vp-visitedw-e

32、i.z-1=-1&vp-visitedw-ei.y-1=1)return2;elseif(vp-visitedw-ei.y-1=-1&vp-visitedw-ei.z-1=1)return3;elseif(vp-visitedw-ei.z-1=1&vp-visitedw-ei.y-1=1)return4;voidCreate_TLGraph(WGraph*w,ALGraph*G)/*生成最小生成树*/WGraphT;inti,j,t,h,k=2;intm=1;intabc,bcd;structvisit*vp;vp=(structvisit*)malloc(sizeof(structvisit

33、);for(i=0;in);i+)/*将各顶点的被访问情况，位置，与其他顶点vp-visitedi=-1;的相互关系进行初始化*/vp-positioni=-1;vp-vvppi0=i+1;for(j=1;jn;j+)vp-vvppij=0;T.v0=w-vw-e0.z-1;T.v1=w-vw-e0.y-1;vp-visitedw-e0.z-1=1;vp-positionw-e0.z-1=w-e0.z;for(j=0;jn);j+)if(vp-vvppw-e0.z-1j=0)vp-vvppw-e0.z-1j=w-e0.y;break;vp-visitedw-e0.y-1=1;vp-positi

34、onw_e0.y_1=w_e0.z;T.=;T.e0.z=w-e0.z;T.e0.y=w-e0.y;for(i=1;ie);i+)TOC o 1-5 h zt=judge_vertex(w,i,vp);/*根据不同的顶点访问情况选取相应操作*/if(t=4)/*两顶点均已被访问过的情况*/if(vp-positionw-ei.z-1=vp-positionw-ei.y-1)/*两顶点位置相同*/continue;/*舍去这条边，否则会构成回路*/elseabc=0;bcd=0;/*倘若两顶点位置不同*/for(j=0;jn;j+)if(vp-vvppvp-pos

35、itionw_ei.y_1_1j!=0)abc+;for(j=0;jn;j+)if(vp-vvppvp-positionw-ei.z-1-1j!=0)bcd+;将两顶点放在同一个数组for(j=bcd,h=0;jn&hvvpp(vp-positionw-ei.z-1)-1j=vp-vvpp(vp-positionw_ei.y_1)-1h；vp-vvppvp-positionw-ei.y-1-1h=0;/*将原数组置零*/for(h=bcd;hposition(vp_vvppvp_positionw-ei.z-1-1h)-1=vp-positionw-ei.z-1;T.=w-ei.

36、info;/*将该边存入T中*/T.em.z=w-ei.z;T.em.y=w_ei.y;m+;elseif(t=1)/*两顶点都未被访问的情况*/vp_visitedw_ei.z_1=1;vp_visitedw_ei.y_1=1;T.vk+=w_vw_ei.z_1;/*将该边存入T中*/*将两顶点的位置改为相同*/*将两顶点存放到一个数组中*/T.vk+=w_vw_ei.y_1;T.=;T.em.z=w-ei.z;T.em.y=w-ei.y;m+;vp-positionw-ei.z-1=w-ei.z;vp-positionw_ei.y_1=w_ei.z;vp_vvppw_ei.z_11=w_ei.y;vp-vvppw-ei.y-10=0;elseif(t=2)/*左顶点未被访问，右顶点已被访问的情况*/vp_visitedw_ei.z_1=1;vp-positionw-ei.z-1=vp-positionw-ei.y-1;/*将左顶点的位置改为右顶点的位置*/for(j=0;jn);j+)/*将两顶点存放到一个数组中*/if(vp-vvppvp-positionw-ei.y-1-1j=0)vp-vvppvp-posi