管道铺设问题

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

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

3、，顶点信息为大写字母，边的权值为浮点型，C:data.txt 文件内容为：ABCDEFGHI1 2 32.8 2 3 5.9 1 3 44.6 3 4 21.3 4 5 67.3 4 6 98.7 5 6 85.6 5 7 10.5 3 7 56.4 69 79.2 7 8 52.5 1 8 12.1 8 9 8.7 1 9 18.23541.1三.概要设计1.所用到得数据结构及其ADTtypedef struct node/边表结点int NO;II邻接点域;vertexType adj vex;/ /EdgeType info; struct node *n ext;JEdgeNode;t

4、ypedef struct vnode(vertexType vertex; /EdgeNode *firstedge;/ JVertexNode;typedef struct/(VertexNode adjlistMaxVertexNum;int n,e;/JALGraph;/ ALGraph基本操作：ALGraph * CreateALGraph()2.主程序流程及其模块调用关系1)主程序模块权值指向下一个邻接点的指针域顶点表节点顶点域编表头指针邻接表顶点数和边数是以邻接表方式存储的图类型/建表显示主界面建表1生成最小树k结束 建表模块 ALGraph * CreateALGraph()开

5、始最小生成树模块 void tree(ALGraph *G,i nt m)开始sum=O;lowm=0;visitedm=O;J< s!=NULLlows->NO=s->info; s=s->next;s=G- >adjlistm.first edge;lowi=1000;teedi=m;min=1000;j=1JN输出边顶点信息s=G->adjlistk.firstedgesum+=min; visitedk=O;visitedj>0&&lowj<min/A s!=NULLmin=lowj;k=j；j+(visiteds->

6、;NO>0&as->info<lows->NOlows->NO=s->info;teeds->NO=k;函数调用笑系图四、详细设计1 .实现每个操作的伪码，重点语句加注释1)建表模块ALGraph * CreateALGraph() /建表(int ij,k;float m;FILE *fp;EdgeNode *s,*t;ALGraph *G;fp=fope n( "C:data.txt"J广)；打开文件if(fp=NULL)/未找到文件(prin tf("Ca nn't open the file!n &

7、quot;)；ex计；)G=(ALGraph *)malloc(sizeof(ALGraph);printf("请输入顶点数和边数(输入格式为：顶点数，边数)n");scanf("%d,%d",&G->n,&G->e);for(i=1 ;iv=G->n;i+) 建立顶点信息(G->adjlisti.vertex=fgetc(fp);G->adjlisti.firstedge=NULL; visitedi=i;)for(k=1 ;k<=G->e;k+)(/ printf(,请输入第1条边的两个端点序

8、号，输入格式为：i,jn",k);/scanf("%d,%d",&i,&j);fscanf(fp,"%d",&i);fscanf(fp,"%d",&j);s=(EdgeNode *)malloc(sizeof(EdgeNode); t=(EdgeNode*)malloc(sizeof(EdgeNode); print"'请输入第4条边的对应权值n”,k);fscanf(fp,"f”,&m);保存边信息，以无向网方式s->NO=j;s->adjve

9、x=G->adjlistj.vertex;s->info=m;s->next=G->adjlisti.firstedge;G->adjlisti.firstedge=s;t->NO=i;t->adjvex=G->adjlisti.vertex;t->info=m;t->next=G->adjlistj.firstedge;G->adjlistj.firstedge=t;fclose(fp);/ 关闭文件return G;)2)生成最小生成树模块void tree(ALGraph *G,int m)(float low100

10、;int teed100;int k,i,j;float min,sum=0;EdgeNode *s;lowm=0;visitedm=0;for(i=1 ;i<=G->n;i+)(lowi=1000;teedi=m;)s=G->adjlistm.firstedge;while(s!=NULL)数组初始化lows->NO=s->info;s=s->next;)for(i=1 ;i<G->n;i+)(min=1000;for(j=1 ;j<=G->n;j+)找到最小权值if(visitedj>0&&lowj<m

11、in)/ min=lowj；k=j；/标记节点)sum+=min;visitedk=O;s=G->adjlistk.firstedge;while(s!=NULL)(if(visiteds->NO>0&&s->info<lows->NO)/(lows->NO=s->info;teeds->NO=k;)s=s->next;)printfC,最佳铺设方案W);for(i=1 ;iv=G->n;i+)输出最小生成树信息if(i!=m)printf("(%d,%d)%.2ft",i,teedi,low

12、i);printf(u 最小权值为:%.2fn'sum);)3)主函数模块void main()(ALGraph *G;inti;time_t rawtime;struct tm * timeinfo;time (&rawtime);timeinfo = localtime (&rawtime);printf("实验名称：实验三：管道铺设施工的最佳方案printf("姓名：王亚文己）;找到最小权值n")；printf(“学号：031350102nH);An'*);printf("printf("程序运行开始，)p

13、rintf("Current local time and date:%s”,asctime(timeinfo);G=CreateALGraph();/ 建表printf("输入开始节点W);scanf("d”,&i);tree(Gj); 生成最小树/printfALGraph(G);printf("nH);printf("Current local time and date:%s”,asctime(timeinfo);)五、调试分析1.设计与调试过程中遇到的问题分析、体会1)一开始对文件读写操作不熟，采用从键盘输出的方式验证正确与否

14、，对应程序如下：int ij,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 ;iv=G->n;i+) 建立顶点信息G->adjlisti.vertex=fgetc(fp);G->adjlisti.firstedge=NULL; visitedi=i;)for(k=1 ;k&l

15、t;=G->e;k+) (printf("请输入第1条边的两个端点序号，输入格式为：iJ'n'k);scanf("d,%d”,&i,&j);s=(EdgeNode *)malloc(sizeof(EdgeNode);t=(EdgeNode *)malloc(sizeof(EdgeNode);printf(H请输入第 4条边的对应权值n”,k);scanf("%f”,&m);保存边信息，以无向网方式s->NO=j;s->adjvex=G->adjlistj.vertex;s->info=m;s-&

16、gt;next=G->adjlisti.firstedge;G->adjlisti.firstedge=s;t->NO=i;t->adjvex=G->adjlisti.vertex;t->info=m;t->next=G->adjlistj.firstedge;G->adjlistj.firstedge=t;)return G;)对应截屏如下：发现这种方式输入耗时长，而且在生成树程序不正确时修改程序需要重复输 入，较为麻烦PAS；号 Hi二号疔|刃|.U:uPIMI目!I)输入格式为. i-J输入格式为：输入格式为：i BvjNc输入格:0

17、1边的对应权11B接辽接|?0S XAO C 44,60C3j2>5.9011)12-10<4.3>21.30<9,8)8.73<5.3>输出彳&的邻接点尺权值：E41-10G S&.46D0的邻接点及权值，F?8_?()E67.30C卫的邻接点及权值,C41,1()G10.5RPF的邻接点刃权值：I79-20E85.60DG的邻菽点及权值：HC 56.46 EH凶邻接点坡权值：I S.7B A 12.H1 CI的邻接点尺权值：11 18.20 H 8.70 FPress anv kev to cont2».21.30 AB 5.9

18、0.22)为检验所建立的无向网，编写了一个输出函数，输出各个顶点以及与该顶点相邻的其他顶点以及对应权值，输出函数为void prin tfALGraph(ALGraph *G)/输出表inti;EdgeNode *s;printf(H 输出信息 n");for(i=1 ;i<=G->n;i+) printf("%c 的邻接点及权值:nM,G->adjlisti.vertex); s=G->adjlisti.firstedge; while(s!=NULL)(printf("%c %.2f ”,s->adjvex,s>info);

19、s=s->next;)printf("nH);输出测试截屏如下证明从文件读写的与所需要建立的无向网相符fC:USERSADMINISTRATODESKTCPVCDebugsa.exeI字号./实三,管道南设施工的最佳方案031350102姓名。王亚文程序运行开始.Current local tine and date：Thn 请端人顶点喊和边数（输入格式为，Nnu 12 1S：29：12201s顶点数,边数）谿攵开始节点1<9,8>8.90<6,9>79.20A的邻接点及权值:<2.1>32.90<7,5)10.S0<3,2>

20、;5.90<8,1>12.10<4.3>21.30<9.8>8.70<G>3>41.19输出信息118.20 H 12.18B的邻接点及权值：CA 32.85日的邻捂点及权值：E 41.10 G 56.4044.6021.3032.8044.60 B 5.90II休邻接点及权值、，98.70 E 67.30的邻接点及权值：21.30C 41el0 C 10.50F的邻接点及权值：I 79.20 E 85606的邻接点及权值：H 52.50 C 56.40H的邻接点及权值：I 8.70 A 12.10I的邻接点及权值： n 18.20 II

21、9.70 Current local tine85.6098.7010.5052.5079.20and date：Thu67.30Hov 12 15：29：122015ress any key to continue2.主要算法的时间复杂度分析六、使用说明程序运行后，显示提示信息：请输入顶点数和边数（输入格式为：顶点数，边数）之后程序从文件名为" C:data.txt读入顶点信息和边的信息，之后显示提示信息输入开始节点，执行生成最小树程序，输出生成的最小树信息。七、测试结果，,管道铺设施工的最任方案 字号,031357 R2lb： 3J = 44 2kllb家三序运彳 丁千干始，Cu

22、rrent _L ocal time and dateiTliu MOM号裔入顶点数和边数（输入格式如顶点数，边数）餐人开始节点隈性铺设方菜K±4>32-80<?,E>13.&G<3,2>5.?G<SA1>1£-10<4,3521.36<5,3>41.10v9,e?e .70最小权值为furrent local time and dateAThu Nov 12 15： 33=44 2B15 *ress anyp key to continue因为边的顶点信息是大写英文字母，一后来采用在定义时考虑多定义一个量

23、，原程序：边表结点邻接点域;3）这个程序遇到的第开嫡关图g题是在建表过程权值的ASCLL码值，typedef stru施用不方便，指向下一个邻接点的指针域nodevertexType adjvex;EdgeType info;struct node *n ext;JEdgeNode;边表结点/"邻接点域;修正后的程序为：typedef struct node(int NO;权值指向下一个邻接点的指针域JEdgeNode;这样多定义了一个量在后面的过程中会简单许多，其次书上给的程序是生成有向网的，-vertexType adjvex;EdgeType info;/开始我是考虑的将边输入

24、两边，就是在循环时的终止条件设为k<=2*G->e ;这样虽然能解决无向网问题，但是一条边重复输入两边，较为麻烦，后期修正为：s->NO=j;s->adjvex=G->adjlistj.vertex;s->info=m;s->next=G->adjlisti.firstedge;G->adjlisti.firstedge=s;t->NO=i;t->adjvex=G->adjlisti.vertex;t->info=m;t->next=G->adjlistj.firstedge;G->adjlistj

25、.firstedge=t;修正后的函数虽然语句较之前的多了 5句但在输入时少输了一半的边信息。其次解决耗时最长的一个错误是在建表中，原程序：邻接表typedef VertexNode AdjlistMaxVertexNum;typedef structAdj list adjlist;/int n,e;顶点数和边数int n;int e;JALGraph;/ ALGraph是以邻接表方式存储的图类型这个程序是抄的书上的，一开始不觉得书上的程序会是错的，结果一直没有看这个定义，在输入边的信息时循环次数总是不对，一直尝试着改动写的输入信息，弄了一下午也没有搞定这个问题，于是去求助研究生学长，下面是

26、研究生学长发过来的邮件帮我指出错误所在，看了学长的这封邮件后，重新改了一下自己的程序，修正后的程序为typedef struct / 邻接表VertexNode adjlistMaxVertexNum;int n,e;/顶点数和边数JALGraph;/ ALGraph是以邻接表方式存储的图类型语句定义错谋，上闻题所在:结构体ALGraph红色标记静分)中jAdjlist昭1也炉 面没有宇义Adjlist这个类率；I 解决方案：考虑在主函鞭main)中将全扃结榕体数组typedefVertexNodeAdjl(5tMaxVerteMNium;中数组名作为参数进入ALGraph *CreateAL

27、Graph()町 ALGraph * CreatsALGraphfVertexNode * adjirst);将3adjW舌的访恻方式史改为adjli$ti)G原因;该结构体数组定义为全局结构体 数红无须通过ALGraph结构佛播针G来讪凤使用数组1S针VertewNode审mdjli眈方便程序修正后输入正常了，就开始进入下一个阶段生成最小树的程序。3)在生成最小树这个程序的编写中，开始因为编程序是在老师讲解生成树之前，所以一开始是完全没有地方下手，网上百度了一下如何生成最小树，发现有两种方法，Kruskal和prim算法，但研究生学长这个适合用prim算法，Kruskal算法适合与边稀疏的连

28、通图求解最小生成树，所以在编写时主要研究的是用prim算法，在编写prim算法时除了很多问题，例如一开始我并没有在循环中写te6di=m;这句话，导致在最后输出边的信息时会有随机数产生，截图如下：<2r858993460>32.8Q20<7 5)1()5() I v3.2x.90<4,3>2L30 v5,3>41,16，|<8 r3589934G0>12.10v9,8>8.70 最小权值为二211,6想到随机数产生可能是因为没有赋值，所以加上teedi=m;这句话果然最后就输出正确了，再次在输出时，产生的结果中有重复的一个节点，<1,

29、1 >1000.00这个不应该被输出，所以考虑在输出时加一个限制条件i f ( i ! = m ) 再次输出就没有了最佳铺设方案tZ,l>J2-80<6f9>79-23(7.5>10.50<8,1>12,10<9,8)8,70矗 洞就)口乞 11 J中间编写时问题不大，之前有看过prim算法的详细介绍，所以在主思路上没有太大的错误，相对写起来也比 较顺利。2)建立邻接表的复杂度为0(n+e);Prim算法的时间复杂度为O(elogn);八、附录#include <stdio.h>#include <malloc.h>#in

30、clude <stdlib.h>时表示未访问，C-3，D-4，E-5，F-6，G-7，H-8，1-9输入序号与字母对应关系A-1B-2#define MaxVertexNum 100 typedef char vertexType;typedef float EdgeType;边表结点struct node /int NO; / vertexType adjvex;邻接点域；EdgeType info;/struct node *next;/权值JEdgeNode;指向下一个邻接点的指针域typedef struct vnode /顶点表节点vertexType vertex;/E

31、dgeNode *firstedge;顶点域/ JVertexNode;编表头指针邻接表int visited100; 访问变量，为一 typedeftypedef struct /VertexNode adjlistMaxVertexNum;顶点数和边数int n,e;/是以邻接表方式存储的图类型JALGraph;/ ALGraphALGraph * CreateALGraph()/建表intfloat m;FILE *fp;EdgeNode *s,*t;ALGraph *G;fp=f。pen(”C:data.txtTr");打开文件if(fp=NULL)/未找到文件(printf

32、("Cann't open the file!n"); exit(1);)G=(ALGraph *)malloc(sizeof(ALGraph);printf("请输入顶点数和边数(输入格式为：顶点数，边数)nu);scanf(',%d,%d,&G->n,&G->e);for(i=1 ;iv=G->n;i+) 建立顶点信息(G->adjlisti.vertex=fgetc(fp);G->adjlisti.firstedge=NULL; visitedi=i;for(k=1 ;k<=G->e;

33、k+)(/ printf(,1请输入第% d条边的两个端点序号，输入格式为：/scanf(H%d,%d",&i,&j);fscanf(fpcT,&i);fscanf(fp/d”,&j);s=(EdgeNode *)malloc(sizeof(EdgeNode); t=(EdgeNode*)malloc(sizeof(EdgeNode);/ printf(u请输入第% 4条边的对应权值n”,k);fscanf(fp,"R&m);保存边信息，以无向网方式s->NO=j;s->adjvex=G->adjlistj.vert

34、ex;s->info=m;s->next=G->adjlisti.firstedge;G->adjlisti.firstedge=s;t->NO=i;t->adjvex=G->adjlisti.vertex;t->info=m;t->next=G->adjlistj.firstedge;G->adjlistj.firstedge=t;)fclose(fp);/ 关闭文件return G;void tree(ALGraph *GJnt m) (float low100;int teed100;int kJJ;float min,s

35、um=0;EdgeNode *s;lowm=0;visitedm=0;for(i=1 ;i<=G->n;i+)(lowi=1000;teedi=m; s=G->adjlistm.firstedge; while(s!=NULL)/ 数组初始化lows->NO=s->info;s=s->next;for(i=1 ;i<G->n;i+)(min=1000;for(j=1 ;j<=G->n;j+)(if(visitedj>0&&lowj<min)/ 找到最小权值(min=lowj；k=j；/标记节点)sum+=m

36、in;visitedk=O;s=G->adjlistk.firstedge;while(s!=NULL)(if(visiteds->NO>0&&s->info<lows->NO)/ 找到最小权值( lows->NO=s->info;teeds->NO=k;)s=s->next;printf("最佳铺设方案n");for(i=1 ;iv=G->n;i+)输出最小生成树信息if(i!=m)printf("(%d,%d)%.2ft"Ji,teedi,lowi);printf(&q

37、uot;最小权值为:%.2fn'sum);)/*void printfALGraph(ALGraph *G) / 输出表int i;EdgeNode *s;printf("输出信息 n”)；for(i=1 ;iv=G->n;i+)(printf("%c 的邻接点及权值:n",G->adjlisti.vertex);s=G->adjlisti.firstedge;while(s!=NULL)(printf("%c %.2f ”,s->adjvex,s->info);s=s->next;)printf("nn);)7void main()(ALGraph *G;int i;time_t rawtime;struct tm * timeinfo;time (&rawtime);timeinfo = localtime (&rawtime);pri