管道铺设问题

管道铺设问题

ID:21996589

大小:1.59 MB

页数:25页

时间:2018-10-26

管道铺设问题_第1页
管道铺设问题_第2页
管道铺设问题_第3页
管道铺设问题_第4页
管道铺设问题_第5页
资源描述:

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

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]

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。