《管道铺设问题》由会员分享，可在线阅读，更多相关《管道铺设问题（41页珍藏版）》请在金锄头文库上搜索。
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文件内容为：ABCDEFGHI1232.8235.91344.63421.34567.34698.75685.65710.53756.46979.27852.51812.1898.71918.23541.1三.概要设计1.所用到得数据结构及其ADTtypedefstructnode/边表结点intNO;II邻接点域;vertexTypeadjvex;/ /EdgeTypeinfo;structnode*next;JEdgeNode;typedefstructvnode(vertexTypevertex;/EdgeNode*firstedge;/JVert
4、exNode;typedefstruct/(VertexNodeadjlistMaxVertexNum;intn,e;/JALGraph;/ALGraph基本操作：ALGraph*CreateALGraph()2.主程序流程及其模块调用关系1)主程序模块权值指向下一个邻接点的指针域顶点表节点顶点域编表头指针邻接表顶点数和边数是以邻接表方式存储的图类型/建表显示主界面建表1生成最小树k结束建表模块ALGraph*CreateALGraph()开始最小生成树模块voidtree(ALGraph*G,intm)开始sum=O;lowm=0;visitedm=O;JNO=s-info;s=s-next
5、;s=G-adjlistm.firstedge;lowi=1000;teedi=m;min=1000;j=1JN输出边顶点信息s=G-adjlistk.firstedgesum+=min;visitedk=O;visitedj0&lowjNO0&as-infoNOlows-NO=s-info;teeds-NO=k;函数调用笑系图四、详细设计1.实现每个操作的伪码，重点语句加注释1)建表模块ALGraph*CreateALGraph()/建表(intij,k;floatm;FILE*fp;EdgeNode*s,*t;ALGraph*G;fp=fopen(C:data.txtJ广)；打开文件if(
6、fp=NULL)/未找到文件(printf(Canntopenthefile!n)；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;ke;k+)(/printf(,请输入第1条边的两个端点序号，输入格式为：i,jn,k);/scanf(%d,%d,&i,&j
7、);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-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
8、-next=G-adjlistj.firstedge;G-adjlistj.firstedge=t;fclose(fp);/关闭文件returnG;)2)生成最小生成树模块voidtree(ALGraph*G,intm)(floatlow100;intteed100;intk,i,j;floatmin,sum=0;EdgeNode*s;lowm=0;visitedm=0;for(i=1;in;i+)(lowi=1000;teedi=m;)s=G-adjlistm.firstedge;while(s!=NULL)数组初始化lows-NO=s-info;s=s-next;)for(i=1;in;i
9、+)(min=1000;for(j=1;jn;j+)找到最小权值if(visitedj0&lowjadjlistk.firstedge;while(s!=NULL)(if(visiteds-NO0&s-infoNO)/(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,lowi);printf(u最小权值为:%.2fn;sum);)3)主函数模块voidmain()(ALGraph*G;inti;time_traw
10、time;structtm*timeinfo;time(&rawtime);timeinfo=localtime(&rawtime);printf(实验名称：实验三：管道铺设施工的最佳方案printf(姓名：王亚文己）;找到最小权值n)；printf(“学号：031350102nH);An*);printf(printf(程序运行开始，)printf(Currentlocaltimeanddate:%s”,asctime(timeinfo);G=CreateALGraph();/建表printf(输入开始节点W);scanf(d”,&i);tree(Gj);生成最小树/printfALGrap
11、h(G);printf(nH);printf(Currentlocaltimeanddate:%s”,asctime(timeinfo);)五、调试分析1.设计与调试过程中遇到的问题分析、体会1)一开始对文件读写操作不熟，采用从键盘输出的方式验证正确与否，对应程序如下：intij,k;floatm;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;ke;k+)(printf(请输入第1条边的两个端点序号，输入格式为：iJnk);scanf(d,%d”,&i,&j);s=(EdgeNode*)malloc(sizeof(EdgeNode);t=(EdgeNode*)m
