管道铺设施工的最佳方案问题

管道铺设施工的最佳方案问题

ID:24960369

大小:624.50 KB

页数:23页

时间:2018-11-17

管道铺设施工的最佳方案问题_第1页
管道铺设施工的最佳方案问题_第2页
管道铺设施工的最佳方案问题_第3页
管道铺设施工的最佳方案问题_第4页
管道铺设施工的最佳方案问题_第5页
资源描述:

《管道铺设施工的最佳方案问题》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库

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

2、要求:I.主函数部分:对象:图G;目的:为图G分配空间,以作为后续调用函数的参数;要求:无。II.Create_ALGraph()函数部分:对象:顶点,边及其权值;目的:将顶点,边存放在一起,构成图;要求:构造顶点表,各顶点的邻接表以构造图。III.Create_WLGraph()函数部分:对象:图G;目的:将图中的权值只存放一次,存放到w指向的结构体中;要求:权值只存放一次,再分别存放该边的左右顶点。IV.select_info()函数部分:对象:w指向的结构体;目的:将该结构体中的各权值以升序排列;要求:采用简单选择法进行排序。V.Create

3、_TLGraph()函数部分:对象:排序后的w指向的结构体;目的:找到构成最小生成树的边;要求:依权值升序排列,判断各边是否构成回路来取舍各边。二.需求分析1.程序所能达到的基本可能:在n个小区m条管道中,选取n-1条管道,实现连通这n个小区,同时权值之和为最小。2.输入输出形式及输入值范围:程序运行后,用户可根据提示信息:"Pleaseinputtheverticesandtheedges:"输入顶点数和边数,再根据提示信息:"Pleaseinputtheinformationofthevertices:"输入顶点信息,然后进入循

4、环,创建各个顶点的邻接表,即根据提示信息"Pleaseinputtheinformationofedges:"和"Pleaseinputtheinformationofweight:"依次输入各顶点与其他顶点本身以及两者之间的权值,创建图完毕。用户输入完毕后,程序自动输出运行结果。输入值必须为字母和浮点数,可以不必区分大小写。3.测试数据要求:用户输入字母时,输入大写或小写,都可以被该程序识别,正常运行。但必须根据提示信息后面给出的参考形式,有针对性地输入逗号。三.概要设计为了实现上述功能,该程序以邻接表来存储图,因此需要图这个抽象数据类

5、型。1.图抽象数据类型定义:ADTALGraph{数据对象:D={,i=1,2,3....,n,n}数据关系:R=;基本操作:Create_ALGraph(G);//创建图Create_WLGraph(G);//将图G中各顶点以及权值存放到新图中,权值只存放一次select_info(W,G);//将新图W中的权值按升序排列Create_TLGraph(w,G);//将最小生成树以顶点对(i,j)的形式输出}ADTALGraph2.本程序保护模块:主函数模块图模块调用关系:3.主要算法流程图:Create_ALGraph()算法流程图:Create

6、_WLGraph()算法流程图:Create_TLGraph()算法流程图:三.详细设计1.相关头文件的调用说明:#include#include#defineMaxVerNum1002.元素类型、结点类型和结点指针类型:staticvoidforcefloat(float*p){floatf=*p;forcefloat(&f);}typedefstructnode{intadjvex;floatinfo;structnode*next;}EdgeNode;typedefstructvnode{charvert

7、ex;EdgeNode*firstedge;}VertexNode;typedefVertexNodeAdjList[MaxVerNum];structbian{intz,y;floatinfo;};typedefstruct{charv[MaxVerNum];structbiane[MaxVerNum];}WGraph;structvisit{visited[MaxVerNum];position[MaxVerNum];vvpp[MaxVerNum][MaxVerNum];}3.邻接表类型:typedefstruct{AdjListadjlist

8、;intn,e;}ALGraph;//部分基本操作的伪码实现Create_ALGraph(ALGraph*G){inti,

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

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

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