管道铺设问题探讨.doc

实验三：管道铺设施工的最佳方案 一．问题描述 1.实验题目： 需要在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道铺设n-1条管道即可。假设任意两个小区之间则可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。 基本要求： 在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的存储采用邻接表的结构。 测试数据： 使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。 参考解： 二．需求分析 1.程序所能达到的基本可能： 在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道铺设n-1条管道即可。假设任意两个小区之间则可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。 2.输入输出形式及输入值范围：程序运行后，显示提示信息：请输入顶点数和边数（输入格式为：顶点数,边数）之后程序从文件名为”C:\\data.txt读入顶点信息和边的信息，之后显示提示信息输入开始节点，执行生成最小树程序，输出生成的最小树信息。 3.测试数据要求：顶点数边数为整数，顶点信息为大写字母，边的权值为浮点型，C:\\data.txt文件内容为：ABCDEFGHI 1 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 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 adjlist[MaxVertexNum]; int n,e; //顶点数和边数 }ALGraph; // ALGraph是以邻接表方式存储的图类型 基本操作：ALGraph * CreateALGraph() //建表 主程序流程及其模块调用关系 主程序模块 建表模块ALGraph * CreateALGraph() 最小生成树模块void tree(ALGraph *G,int m) 函数调用关系图 四、 详细设计 1. 实现每个操作的伪码，重点语句加注释 1）建表模块 ALGraph * 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,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(请输入第%