资源描述：
《管道铺设问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、实验三：管道铺设施工的最佳方案一．问题描述1.实验题目：需要在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道铺设n-1条管道即可。假设任意两个小区之间则可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。2.基本要求：在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的存储采用邻接表的结构。3.测试数据：使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案
2、。参考解：二．需求分析1.程序所能达到的基本可能：在某个城市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;//邻接点域;vertexTypeadjvex;EdgeTypeinfo;//权值struc
4、tnode*next;//指向下一个邻接点的指针域}EdgeNode;typedefstructvnode//顶点表节点{vertexTypevertex;//顶点域EdgeNode*firstedge;//编表头指针}VertexNode;typedefstruct//邻接表{VertexNodeadjlist[MaxVertexNum];intn,e;//顶点数和边数}ALGraph;//ALGraph是以邻接表方式存储的图类型基本操作：ALGraph*CreateALGraph()//建表2.主程序流程及其模块调用关系1)主程序模块建
5、表模块ALGraph*CreateALGraph()最小生成树模块voidtree(ALGraph*G,intm)函数调用关系图四、详细设计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!");exit(1);}G=(ALGr
6、aph*)malloc(sizeof(ALGraph));printf("请输入顶点数和边数（输入格式为：顶点数,边数）");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条边的两个端点序号，输入格式为：i,j",k);//scanf("%d,%d"
7、,&i,&j);fscanf(fp,"%d",&i);fscanf(fp,"%d",&j);s=(EdgeNode*)malloc(sizeof(EdgeNode));t=(EdgeNode*)malloc(sizeof(EdgeNode));//printf("请输入第%d条边的对应权值",k);fscanf(fp,"%f",&m);//保存边信息，以无向网方式s->NO=j;s->adjvex=G->adjlist[j].vertex;s->info=m;s->next=G->adjlist[i].firstedge;G->adjl
8、ist[i].firstedge=s;t->NO=i;t->adjvex=G->adjlist[i].vertex;t->info=m;t->next=G->adjlist[j]
