管道铺设问题VIP免费

...下载可编辑.实验三：管道铺设施工的最佳方案一．问题描述1.实验题目：需要在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道铺设n-1条管道即可。假设任意两个小区之间则可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。2.基本要求：在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的存储采用邻接表的结构。3.测试数据：使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。ABCDEHGFI98.718.28.732.844.656.421.367.385.679.212.152.510.541.15.9参考解：...下载可编辑.ABCDEHGFI8.732.821.379.212.110.541.15.9二．需求分析1.程序所能达到的基本可能：在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道铺设n-1条管道即可。假设任意两个小区之间则可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。2.输入输出形式及输入值范围：程序运行后，显示提示信息：请输入顶点数和边数（输入格式为：顶点数,边数）之后程序从文件名为”C:\\data.txt读入顶点信息和边的信息，之后显示提示信息输入开始节点，执行生成最小树程序，输出生成的最小树信息。3.测试数据要求：顶点数边数为整数，顶点信息为大写字母，边的权值为浮点型，C:\\data.txt文件内容为：ABCDEFGHI1232.8235.91344.63421.34567.34698.75685.65710.53756.46979.27852.51812.1898.71918.23541.1三．概要设计1.所用到得数据结构及其ADTtypedefstructnode//边表结点{intNO;//邻接点域;vertexTypeadjvex;...下载可编辑.EdgeTypeinfo;//权值structnode*next;//指向下一个邻接点的指针域}EdgeNode;typedefstructvnode//顶点表节点{vertexTypevertex;//顶点域EdgeNode*firstedge;//编表头指针}VertexNode;typedefstruct//邻接表{VertexNodeadjlist[MaxVertexNum];intn,e;//顶点数和边数}ALGraph;//ALGraph是以邻接表方式存储的图类型基本操作：ALGraph*CreateALGraph()//建表2.主程序流程及其模块调用关系1)主程序模块开始显示主界面建表生成最小树结束建表模块ALGraph*CreateALGraph()...下载可编辑.打开文件data.txt","r");开始fp==NULL读取G->n,G->e顶点数边数printf("Cann'topenthefile!\n");打开文件失败i=1i<=G->nk=1G->adjlist[i].vertex=fgetc(fp);G->adjlist[i].firstedge=NULL;visited[i]=i;k<=G->efscanf(fp,"%d",&i);fscanf(fp,"%d",&j);fscanf(fp,"%f",&m);输入边的信息将边的信息存储到邻接表中k++i++;YNY关闭文件N结束最小生成树模块voidtree(ALGraph*G,intm)...下载可编辑.开始sum=0;low[m]=0;visited[m]=0;i=1i<=G->nlow[i]=1000;teed[i]=m;i++Ys=G->adjlist[m].firstedge;s!=NULLlow[s->NO]=s->info;s=s->next;YNi=1inmin=1000;j=1j<=G->nvisited[j]>0&&low[j]adjlist[k].firstedge;s!=NULL(visited[s->NO]>0&&s->infoNO]low[s->NO]=s->info;teed[s->NO]=k;s=s->next;i++i=1i<=G->ni!=m输出边顶点信息i++结束YYYYYNNNN...下载可编辑.函数调用关系图main()主函数CreateALGraph();建表tree(G,i);生成最小树四、详细设计1.实现每个操作的伪码，重点语句加注释1）建表模块ALGraph*CreateALGraph()//建表{inti,j,k;floatm;FILE*fp;EdgeNode*s,*t;ALGraph*G;fp=fopen("C:\\data.txt","r");//打开文件if(fp==NULL)//未找到文件{printf("Cann'topenthefile!\n");exit(1);}G=(ALGraph*)malloc(sizeof(ALGraph));...下载可编辑.printf("请输入顶点数和边数（输入格式为：顶点数,边数）\n");scanf("%d,%d",&G->n,&G->e);for(i=1;i<=G->n;i++)//建立顶点信息{G->adjlist[i].vertex=fgetc(fp);G->adjlist[i].firstedge=NULL;visited[i]=i;}for(k=1;k<=G->e;k++){//printf("请输入第%d条...