管道铺设问题.doc

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

2、. 71 8 . 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.输入输出形式及

3、输入值范围：程序运行后，显示提示信息：请输入顶点数和边数（输入格式为：顶点数,边数）之后程序从文件名为”C:data.txt 读入顶点信息和边的信息，之后显示提示信息输入开始节点，执行生成最小树程序，输出生成的最小树信息。3.测试数据要求：顶点数边数为整数，顶点信息为大写字母，边的权值为浮点型，C:data.txt 文件内容为：ABCDEFGHI1 2 32.8 2 3 5.9 1 3 44.6 3 4 21.3 4 5 67.3 4 6 98.7 5 6 85.6 5 7 10.5 3 7 56.4 6 9 79.2 7 8 52.5 1 8 12.1 8 9 8.7 1 9 18.2 3

4、5 41.1三概要设计1. 所用到得数据结构及其 ADT typedef struct node /边表结点int NO; /邻接点域; vertexType adjvex;EdgeType info; /权值struct node *next; /指向下一个邻接点的指针域EdgeNode;typedef struct vnode /顶点表节点vertexType vertex; /顶点域EdgeNode *firstedge; /编表头指针VertexNode;typedef struct /邻接表 VertexNode adjlistMaxVertexNum;int n,e; /顶点数和边

5、数ALGraph; / ALGraph 是以邻接表方式存储的图类型基本操作：ALGraph * CreateALGraph() /建表2. 主程序流程及其模块调用关系 1)主程序模块开始显示主界面建表生成最小树结束建表模块 ALGraph * CreateALGraph() 最小生成树模块 void tree(ALGraph *G,int m)函数调用关系图 m a i n ( ) 主函数C r e a t e A L G r a p h ( ) ; 建表t r e e ( G , i ) ; 生成最小树四、 详细设计 1. 实现每个操作的伪码，重点语句加注释 1）建表模块ALGraph *

6、CreateALGraph() /建表int i,j,k;float m;FILE *fp;EdgeNode *s,*t;ALGraph *G;fp=fopen(“C:data.txt“,“r“);/打开文件if(fp=NULL)/未找到文件printf(“Cannt open the file!n“);exit(1);G=(ALGraph *)malloc(sizeof(ALGraph);printf(“请输入顶点数和边数（输入格式为：顶点数,边数）n“);scanf(“%d,%d“,for(i=1;in;i+)/建立顶点信息G-adjlisti.vertex=fgetc(fp);G-adj

7、listi.firstedge=NULL;visitedi=i;for(k=1;ke;k+) / printf(“请输入第%d 条边的两个端点序号，输入格式为：i,jn“,k);/ scanf(“%d,%d“,fscanf(fp,“%d“,fscanf(fp,“%d“,s=(EdgeNode *)malloc(sizeof(EdgeNode);t=(EdgeNode *)malloc(sizeof(EdgeNode);/ printf(“请输入第%d 条边的对应权值n“,k);fscanf(fp,“%f“,/保存边信息，以无向网方式s-NO=j;s-adjvex=G-adjlistj.vert

8、ex;s-info=m;s-next=G-adjlisti.firstedge;G-adjlisti.firstedge=s;t-NO=i;t-adjvex=G-adjlisti.vertex;t-info=m;t-next=G-adjlistj.firstedge;G-adjlistj.firstedge=t;fclose(fp);/关闭文件return G;2）生成最小生成树模块void tree(ALGraph *G,int m)float low100;int teed100;int k,i,j;float min,sum=0;EdgeNode *s;lowm=0;visitedm=0

9、;for(i=1;in;i+)lowi=1000;teedi=m;s=G-adjlistm.firstedge;while(s!=NULL)/数组初始化lows-NO=s-info;s=s-next;for(i=1;in;i+)min=1000;for(j=1;jn;j+)if(visitedj0while(s!=NULL)if(visiteds-NO0teeds-NO=k;s=s-next;printf(“最佳铺设方案n“);for(i=1;in;i+)/输出最小生成树信息if(i!=m)printf(“(%d,%d)%.2ft“,i,teedi,lowi);printf(“最小权值为:%.

10、2fn“,sum);3）主函数模块void main() ALGraph *G;int i;time_t rawtime;struct tm * timeinfo;time (timeinfo = localtime (printf(“ 实验名称：实验三：管道铺设施工的最佳方案n“);printf(“ 学号：031350102n“);printf(“ 姓名：王亚文n“);printf(“=n“);printf(“程序运行开始，“);printf(“Current local time and date:%s“,asctime(timeinfo);G=CreateALGraph();/建表pri

11、ntf(“输入开始节点n“);scanf(“%d“, tree(G,i); /生成最小树/printfALGraph(G);printf(“n“);printf(“Current local time and date:%s“,asctime(timeinfo);五、 调试分析 1. 设计与调试过程中遇到的问题分析、体会 1）一开始对文件读写操作不熟，采用从键盘输出的方式验证正确与否，对应程序如下：int i,j,k;float m;EdgeNode *s,*t;ALGraph *G;G=(ALGraph *)malloc(sizeof(ALGraph);printf(“请输入顶点数和边数（输入格式为：顶点数,边数）n“);scanf(“%d,%d“,for(i=1;in;i+)/建立顶点信息