管道铺设问题.doc

实验三：管道铺设施工的最佳方案一问题描述1.实验题目：需要在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道铺设n-1条管道即可。假设任意两个小区之间则可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。2. 基本要求： 在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的存储采用邻接表的结构。3. 测试数据： 使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。参考解：二需求分析1.程序所能达到的基本可能：在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道铺设n-1条管道即可。假设任意两个小区之间则可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。2.输入输出形式及输入值范围：程序运行后，显示提示信息：请输入顶点数和边数（输入格式为：顶点数,边数）之后程序从文件名为”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 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; /顶点数和边数ALGraph; / ALGraph是以邻接表方式存储的图类型基本操作：ALGraph * CreateALGraph() /建表2. 主程序流程及其模块调用关系 1) 主程序模块建表模块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;in;i+)/建立顶点信息 G-adjlisti.vertex=fgetc(fp);G-adjlisti.firstedge=NULL;visitedi=i;for(k=1;ke;k+) /printf(请输入第%d条边的两个端点序号，输入格式为：i,jn,k);/scanf(%d,%d,&i,&j);fscanf(fp,%d,&i);fscanf(fp,%d,&j);s=(EdgeNode *)malloc(sizeof(EdgeNode);t=(EdgeNode *)malloc(sizeof(EdgeNode); /printf(请输入第%d条边的对应权值n,k);fscanf(fp,%f,&m);/保存边信息，以无向网方式s-NO=j;s-adjvex=G-adjlistj.vertex; 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; 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(visitedj0&lowjadjlistk.firstedge;while(s!=NULL)if(visiteds-NO0&s-infoNO)/找到最小权值lows-NO=s-info;teeds-NO=k;s=s-next; printf(最佳铺设方案n); for(i=1;in;i+)/输出最小生成树信息 if(i!=m) printf(%d,%d)%.2ft,i,teedi,lowi); printf(最小权值为:%.2fn,sum);3） 主函数模块 void main() ALGraph *G;int i;time_t rawtime;struct tm * timeinfo; time (&rawtime);timeinfo = localtime (&rawtime); printf( 实验名称：实验三：管道铺设施工的最佳方案n);printf( 学号：031350102n); printf( 姓名：王亚文n); printf(=n);printf(程序运行开始，);printf(Current local time and date:%s,asctime(timeinfo);G=CreateALGraph();/建表printf(输入开始节点n);scanf(%d,&i); 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,&G-n,&G-e);for(i=1;in;i+)/建立顶点信息 G-adjlisti.vertex=fgetc(fp);G-adjlisti.firstedge=NULL;visitedi=i;for(k=1;ke;k+) printf(请输入第%d条边的两个端点序号，输入格式为：i,jn,k); scanf(%d,%d,&i,&j);s=(EdgeNode *)malloc(sizeof(EdgeNode);t=(EdgeNode *)malloc(sizeof(EdgeNode); printf(请输入第%d条边的对应权值n,k);scanf(%f,&m);/保存边信息，以无向网方式s-NO=j;s-adjvex=G-adjlistj.vertex; 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;return G;对应截屏如下：发现这种方式输入耗时长，而且在生成树程序不正确时修改程序需要重复输入，较为麻烦2）为检验所建立的无向网，编写了一个输出函数，输出各个顶点以及与该顶点相邻的其他顶点以及对应权值，输出函数为void printfALGraph(ALGraph *G) /输出表int i;EdgeNode *s;printf(输出信息n); for(i=1;in;i+)printf(%c的邻接点及权值:n,G-adjlisti.vertex);s=G-adjlisti.firstedge;while(s!=NULL)printf(%c %.2f ,s-adjvex,s-info);s=s-next;printf(n);输出测试截屏如下证明从文件读写的与所需要建立的无向网相符2. 主要算法的时间复杂度分析 六、 使用说明程序运行后，显示提示信息：请输入顶点数和边数（输入格式为：顶点数,边数）之后程序从文件名为”C:data.txt读入顶点信息和边的信息，之后显示提示信息输入开始节点，执行生成最小树程序，输出生成的最小树信息。七、 测试结果 3） 这个程序遇到的第一个主要问题是在建表过程，因为边的顶点信息是大写英文字母，一开始我是用的ASCLL码值，使用不方便，后来采用在定义时考虑多定义一个量，原程序：typedef struct node /边表结点vertexType adjvex; /邻接点域; EdgeType info; /权值struct node *next; /指向下一个邻接点的指针域EdgeNode;修正后的程序为：typedef struct node /边表结点int NO; /邻接点域; vertexType adjvex;EdgeType info; /权值struct node *next; /指向下一个邻接点的指针域EdgeNode;这样多定义了一个量在后面的过程中会简单许多，其次书上给的程序是生成有向网的， 一开始我是考虑的将边输入两边，就是在循环时的终止条件设为ke；这样虽然能解决无向网问题，但是一条边重复输入两边，较为麻烦，后期修正为：s-NO=j;s-adjvex=G-adjlistj.vertex; 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;修正后的函数虽然语句较之前的多了5句但在输入时少输了一半的边信息。其次解决耗时最长的一个错误是在建表中，原程序：typedef VertexNode AdjlistMaxVertexNum;typedef struct /邻接表Adjlist adjlist; /int n,e; /顶点数和边数int n;int e;ALGraph; / ALGraph是以邻接表方式存储的图类型这个程序是抄的书上的，一开始不觉得书上的程序会是错的，结果一直没有看这个定义，在输入边的信息时循环次数总是不对，一直尝试着改动写的输入信息，弄了一下午也没有搞定这个问题，于是去求助研究生学长，下面是研究生学长发过来的邮件帮我指出错误所在，看了学长的这封邮件后，重新改了一下自己的程序，修正后的程序为typedef struct /邻接表 VertexNode adjlistMaxVertexNum;int n,e; /顶点数和边数ALGraph; / ALGraph是以邻接表方式存储的图类型程序修正后输入正常了，就开始进入下一个阶段生成最小树的程序。3） 在生成最小树这个程序的编写中，开始因为编程序是在老师讲解生成树之前，所以一开始是完全没有地方下手，网上百度了一下如何生成最小树，发现有两种方法，Kruskal和prim算法，但研究生学长这个适合用prim算法，Kruskal算法适合与边稀疏的连通图求解最小生成树，所以在编写时主要研究的是用prim算法，在编写prim算法时除了很多问题，例如一开始我并没有在循环中写teedi=m;这句话，导致在最后输出边的信息时会有随机数产生，截图如下：想到随机数产生可能是因为没有赋值，所以加上teedi=m;这句话果然最后就输出正确了，再次在输出时，产生的结果中有重复的一个节点，1000.00这个不应该被输出，所以考虑在输出时加一个限制条件if(i!=m)再次输出就没有了，中间编写时问题不大，之前有看过prim算法的详细介绍，所以在主思路上没有太大的错误，相对写起来也比较顺利。2） 建立邻接表的复杂度为O(n+e); Prim算法的时间复杂度为O(elogn);八、 附录 #include #include #include #include /输入序号与字母对应关系A-1,B-2，C-3，D-4，E-5，F-6，G-7，H-8，I-9#define MaxVertexNum 100typedef char vertexType;typedef float EdgeType;int visited100;/访问变量，为一时表示未访问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; /顶点数和边数ALGraph; / ALGraph是以邻接表方式存储的图类型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;in;i+)/建立顶点信息 G-adjlisti.vertex=fgetc(fp);G-adjlisti.firstedge=NULL;visitedi=i;for(k=1;ke;k+) /printf(请输入第%d条边的两个端点序号，输入格式为：i,jn,k);/scanf(%d,%d,&i,&j);fscanf(fp,%d,&i);fscanf(fp,%d,&j);s=(EdgeNode *)malloc(sizeof(EdgeNode);t=(EdgeNode *)malloc(sizeof(EdgeNode); /printf(请输入第%d条边的对应权值n,k);fscanf(fp,%f,&m);/保存边信息，以无向网方式s-NO=j;s-adjvex=G-adjlistj.vertex; 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;void tree(ALGraph *G,int m)float low100;int teed100;int k,i,j;float min,sum=0;EdgeNode *s;lowm=0;visitedm=0; 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(visitedj0&lowjadjlistk.firstedge;while(s!=NULL)if(visiteds-NO0&s-infoNO)/找到最小权值lows-NO=s-info;teeds-NO=k;s=s-next; printf(最佳铺设方案n); for(i=1;in;i+)/输出最小生成树信息 if(i!=m) printf(%d,%d)%.2ft,i,teedi,lowi); printf(最小权值为:%.2fn,sum);/*void printfALGraph(ALGraph *G) /输出表int i;EdgeNode *s;printf(输出信息n); for(i=1;in;i+)printf(%c的邻接点及权值:n,G-adjlisti.vertex);s=G-adjlisti.firstedge;while(s!=NULL)printf(%c %.2f ,s-adjvex,s-info);s=s-next;printf(n);*/void main() ALGraph *G;int i;time_t rawtime;struct tm * timeinfo; time (&rawtime);timeinfo = localtime (&rawtime); printf( 实验名称：实验三：管道铺设施工的最佳方案n);printf( 学号：031350102n); printf( 姓名：王亚文n); printf(=n);printf(程序运行开始，);printf(Current local time and date:%s,asctime(timeinfo);G=CreateALGraph();/建表printf(输入开始节点n);scanf(%d,&i); tree(G,i);/生成最小树/printfALGraph(G); printf(n);printf(Curren