管道铺设问题.pdf

《管道铺设问题.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、.44BH25.5.92.597C4156.4G.135.E10.12367.85.6DF98.7参考解：专业文档供参考，如有帮助请下载。AI82.12.7318.BH2.5.997C4G1.135.10.1E2DF二．需求分析1.程序所能达到的基本可能：在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道铺设n-1条管道即可。假设任意两个小区之间则可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。2.输入输出形式及输入值范

3、围：程序运行后，显示提示信息：请输入顶点数和边数（输入格式为：顶点数,边数）之后程序从文件名为”C:\data.txt读入顶点信息和边的信息，之后显示提示信息输入开始节点，执行生成最小树程序，输出生成的最小树信息。3.测试数据要求：顶点数边数为整数，顶点信息为大写字母，边的权值为浮点型，C:\data.txt文件内容为：ABCDEFGHI1232.8235.91344.63421.34567.34698.75685.65710.53756.46979.27852.51812.1898.71918.23541.1三．概要设计1.所用到得数据结构及其ADTtypedefstru

4、ctnode//边表结点{intNO;//邻接点域;vertexTypeadjvex;专业文档供参考，如有帮助请下载。EdgeTypeinfo;//权值structnode*next;//指向下一个邻接点的指针域}EdgeNode;typedefstructvnode//顶点表节点{vertexTypevertex;//顶点域EdgeNode*firstedge;//编表头指针}VertexNode;typedefstruct//邻接表{VertexNodeadjlist[MaxVertexNum];intn,e;//顶点数和边数}ALGraph;//ALGraph是以邻接表方

5、式存储的图类型基本操作：ALGraph*CreateALGraph()//建表2.主程序流程及其模块调用关系1)主程序模块开始显示主界面建表生成最小树结束建表模块ALGraph*CreateALGraph()专业文档供参考，如有帮助请下载。开始打开文件data.txt","r");fp==NULL读取G->n,G->e顶点printf("Cann'topen数边数thefile!");打开文件失败i=1Ni<=G->nk=1YG->adjlist[i].vertex=fgetc(fp);G-N>adjlist[i].firstedge=NULL;k<=G->e关闭文件结束v

6、isited[i]=i;Yfscanf(fp,"%d",&i);fscanf(fp,"%d",&j);fscanf(fp,"%f",&m);输入边的信息i++;将边的信息存储到邻接表中k++最小生成树模块voidtree(ALGraph*G,intm)专业文档供参考，如有帮助请下载。开始sum=0;low[m]=0;visited[m]=0;i=1Ns=G-i<=G->n>adjlist[m].firstedge;YNlow[i]=1000;结束s!=NULLi=1teed[i]=m;YNlow[s->NO]=s-Ni++>info;ini=1i<=G->ns=s->n

7、ext;YYi!=mmin=1000;j=1YN输出边顶点信息sum+=min;j<=G->nvisited[k]=0;s=G->adjlist[k].firstedge;Yi++visited[j]>0&&los!=NULLw[j]NO]>0&&s-k=j;j++>infoNO]low[s->NO]=s->info;teed[s->NO]=k;i++s=s->next;专业文档供参考，如有帮助请下载。函数调用关系图Cr