管道铺设问题

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

2、个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道铺设n-1条管道即可。假设任意两个小区之间则可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，在可能假设的m条管道中，选取n-1条管道，使得既能连通 n个小区，又能使总投资最小。2输入输出形式及输入值范围：程序运行后，显示提示信息：请输入顶点数和边数（输入格式为：顶点数，边数）之后程序从文件名为”读入顶点信息和边的信息，之后显示提示信息输入开始节点，执行生成最小树程序，输出生成的最小树信息。3测试数据要求：顶点数边数为整数，顶点信息为大写字母，边的权值为浮点型，文件内容为：ABCD

3、EFGHI1 22 31 33 44 54 65 65 7 3 76 97 81 88 91 93 5三. 概要设计1.所用到得数据结构及其 ADTk+NininNNYmin=1000;j=1结束）结束）NinYYi! =mNinY! =mYNsum+=mi n;visite dk=0;s=G-adjlistk.firste dge;输出边顶点信息Ywj0&*s!=NULL min= lowj;k=j;j+ +(visite ds-NO0&in folows-NO=s- info; teeds-NO=k;i：s=s-next;实现每个操作的伪码，重点语句加注释1 ）建表模块ertex=fget

4、c(fp);ALGraph * CreateALGraph()G-adjlisti.firstedge=NULL; visitedi=i;for(k=1;ke;k+)ertex;s-i nfo=m;s-n ext=G-adjlisti.firstedge;G-adjlisti.firstedge=s;t-NO=i;t-adjvex=G-adjlisti.vertex; t-i nfo=m;t-n ext=G-adjlistj.firstedge;G-adjlistj.firstedge=t;fclose(fp);irstedge;while(s!=NULL)irstedge;while(s!=

5、NULL)if(visiteds-NO0&s-infoNO)ft,i,teedi,lowi);printf( 最小权值为 :%.2fn,sum);3)主函数模块void main()ALGraph *G;int i;time_t rawtime;struct tm * timeinfo;time (&rawtime);timeinfo = localtime (&rawtime);printf( 实验名称：实验三：管道铺设施工的最佳方案 n);printf( 学号： 0n);printf( 姓名：王亚文 n);printf(=n);printf( 程序运行开始， );printf(Curren

6、t local time and date:%s,asctime(timeinfo);G=CreateALGraph(); 设计与调试过程中遇到的问题分析、体会1)一开始对文件读写操作不熟，采用从键盘输出的方式验证正确与否，对应程序如下：int i,j,k;float m;EdgeNode *s,*t;ALGraph *G;G=(ALGraph *)malloc(sizeof(ALGraph);printf( 请输入顶点数和边数(输入格式为：顶点数,边数) n);scanf(%d,%d,&G-n,&G-e);for(i=1;in;i+)ertex=fgetc(fp);G-adjlisti.fi

7、rstedge=NULL;visitedi=i;for(k=1;ke;k+)i,jn,k);printf( 请输入第 %d 条边的两个端点序号，输入格式为： scanf(%d,%d,&i,&j);s=(EdgeNode *)malloc(sizeof(EdgeNode);t=(EdgeNode *)malloc(sizeof(EdgeNode);printf( 请输入第 %d 条边的对应权值 n,k); scanf(%f,&m);ertex;s-info=m;s-next=G-adjlisti.firstedge;G-adjlisti.firstedge=s;t-NO=i;t-adjvex=G

8、-adjlisti.vertex;t-info=m;t-next=G-adjlistj.firstedge;G-adjlistj.firstedge=t;return G;对应截屏如下： 发现这种方式输入耗时长， 而且在生成树程序不正确时修改程序需要重复输 入，较为麻烦I)输入格式为.i-J输入格式为：输入格式为：i爲5.90A0801)12-10C 44,6021.30 9,8)8.73输出彳21.30 AB 5.90&的邻接点尺权值：E41-10GS&.46D0的邻接点及权值，F?8_?0E67.30C卫的邻接点及权值，C41 ,10G10.5RPF的邻接点刃权值：I79-20E85.60

9、DG的邻菽点及权值：HC 56.46 EH凶邻接点坡权值：I S.7B A 12.1fl CI的邻接点尺权值：n 18.20 H 8.70 FPress any key to cont2 )为检验所建立的无向网，编写了一个输出函数，输出各个顶点以及与该顶点相邻的其他ertex);顶点以及对应权值，输出函数为void prin tfALGraph(ALGraph *G)s=G-adjlisti.firstedge;while(s!=NULL)prin tf(%c%.2f ”,s-adjvex,s-i nfo);s=s-n ext;prin tf(n ”);输出测试截屏如下证明从文件读写的与所需要

10、建立的无向网相符2.主要算法的时间复杂度分析六、使用说明程序运行后，显示提示信息：请输入顶点数和边数（输入格式为：顶点数，边数）之后程序从文件名为”读入顶点信息和边的信息，之后显示提示信息输入开始节点，执行生成最 小树程序，输出生成的最小树信息。七、测试结果C:USERSA DM! NIST RATOP D ESICTC PVCDebusa exe零验名称：实脸三；管這铺设施工的最住方案 学号 0313SA1 W.龙名 I3KB厅运彳丁讦日，Current 丄ocal tine and date tTfiu 端入顶盖数和边数输入格式为：賞入开始节点最住铺设白菜32-8010.&0Nov 12

11、lb：33：44 2Mlb5.?e顶点数，边数）41丄079.20最小权值为胡“4Current local Press any keytime and date:Thu to continueNou 12 15：33：442B153）这个程序遇到的第一个主要问题是在建表过程，因为边的顶点信息是大写英文字母，一 开始我是用的ASCLL码值，使用不方便，后来采用在定义时考虑多定义一个量，原程序： typedef struct nodeertex;s-i nfo=m;s-n ext=G-adjlisti.firstedge;G-adjlisti.firstedge=s;t-NO=i;t-adjve

12、x=G-adjlisti.vertex;t-i nfo=m;t-n ext=G-adjlistj.firstedge;G-adjlistj.firstedge=t;修正后的函数虽然语句较之前的多了5句但在输入时少输了一半的边信息。其次解决耗时最长的一个错误是在建表中，原程序：structtypedef VertexNode AdjlistMaxVertexNum;typedef问题所在:结构休ALGraph(红色标记部分沖，MAdjlist adjlistf语旬定义错冥上面没有定义Adjlist这个类舉；|解决方案：誉虑在二西数main(|中将全扇结构体数组typedef VertexNode

13、 AdjlfstMaxVerte)cMum;中 Adjlist 数组名作为参数进入 ALGraph * CreateALGraph()即 ALGraph * CreatsALGraphfVertexNode * adjirst);将3Jjl話如山的访冋方式史改为9djlisti,x原因;该结构体数组定义为全局结构体 数纵无须通过MGmph结构体播针G来筋冋点用数俎指针VertexrJode审詢list方便 ifettIft佳铺设方案t2,lJ2-80C4.3J21.3H79.200(7.510.5012,109.838.70歸佳铺设方案 32-80 207,5)10.50B5.9021.3B4

14、1,1079.12 .IB E.70最小权値为ertex=fgetc(fp);G-adjlisti.firstedge=NULL; visitedi=i;for(k=1;ke;k+)ertex;s-i nfo=m;s-n ext=G-adjlisti.firstedge;G-adjlisti.firstedge=s;t-NO=i;t-adjvex=G-adjlisti.vertex;t-i nfo=m;t-n ext=G-adjlistj.firstedge;G-adjlistj.firstedge=t;fclose(fp);irstedge;while(s!=NULL)irstedge;wh

15、ile(s!=NULL) if(visiteds-NO0&s-infoNO)ft,i,teedi,lowi);printf( 最小权值为 :%.2fn,sum);/*void printfALGraph(ALGraph *G)ertex);s=G-adjlisti.firstedge;while(s!=NULL)printf(%c %.2f ,s-adjvex,s-info);s=s-next;printf(n);*/void main()ALGraph *G;int i;time_t rawtime;struct tm * timeinfo;time (&rawtime);timeinfo

16、= localtime (&rawtime);printf( 实验名称：实验三：管道铺设施工的最佳方案 n); printf( 学号： 0n);n);printf( 姓名：王亚文 n); printf(= printf( 程序运行开始， );printf(Current local time and date:%s,asctime(timeinfo);G=CreateALGraph();/ 建表 printf( 输入开始节点 n); scanf(%d,&i); tree(G,i); / 生成最小树 /printfALGraph(G); printf(n);printf(Current loca

17、l time and date:%s,asctime(timeinfo);九、 实验收获和感想在这个管道铺设问题的程序设计中， 弄懂题意后发现其实这个题需要解决两个问题， 一个 是建立无向网的问题， 另一个就是最小生成树的求解， 所以这个程序设计还是需要模块化设 计这个思路， 首先需要解决的是如何建立无向网， 在这个过程中我编写了一个输出函数以检 验所建立的无向网是否是我们所需要的，建立无向网这个过程是我编写这个程序耗时最长 的，因为开始一味的相信书上的程序是正确的所以吃了不少苦， 最后还是多亏了研究生学长 才得以解决这个问题， 这个教训也告诫我不能一味的相信书本， 最后能输出正确结果的才是

18、正确的程序， 在之后的程序编写时不要再因为是书本的原程序就原封不动的抄上在后续出错 时也不检查是否是这个抄的程序的错误， 再次是要善于用自己所学的知识简化问题而不是只 用一种方法解决这个问题， 在这个程序中建立边表信息时再多建立一个 NO 信息就可以大大 简化问题，所以编写程序时还是要多想想其他办法， 还有就是这个测试数据有 9 个顶点信息， 15 条边的信息，在测试时挨个输入显然会很麻烦，所以善于运用文件操作会很方便的，但 是最开始我是使用的键盘输入， 并且将原语句保留在程序中， 使用时可以使用键盘输入， 或 者在定义的文件 中改变边和顶点信息，不管怎么说，使用文件操作后真的是方便很多， 在经历了一次又一次要输入 9 个顶点信息 15 条边信息后第一次使用文件操作后感悟还是蛮