管道铺设课程设计报告

1、编号:江西理数据结构课程设计报告班级：学号:姓名:时间：2015年6月22日2015年7月3日指导教师：2015年06月摘要引言需求分析4概要设计21.普利姆算法分析62.模块分析63.抽象数据类型分析64.全部流程6详细设计.1.算法分析7（一）信息输入模块四、五、录33(二)建立最小生成树并输出结果2.源程序代码八、测试结果14七、八、程序开始信息输入输出结果设计体会结束语141414151616参考文献摘要N(N>10)个居民区之间需要铺设煤气管道。假设任意两个居民区之间都可以铺设煤气管道，但代价不同。问题的实质就是编写相应程序求解最小生成树问题。程序要求:事先任意两个居民区之间铺

2、设煤气管道的代价存入磁盘文件中。设计一个最佳方案使得这N个居民区之间铺设煤气管道所需代价最小，并将结果以图形方式在屏幕 上输出。引言C语言作为一门最通用的语言， 从语言产生到现在，它已经成为最重要和最流行的编程语言之一。在各种流行编程语言中，都能看到C语言的影子。学习掌握 C语言是每一个计算机技术人员的基本功之一。实际生活中最小生成树的问题具有很大的意义。例如，本文所讨论的构架居民区之间铺设煤气管道代价最小，还有在若干地区铺设光缆等等。最小生成树让许多诸 如求造价最小、最短路径等最优化的现实问题找到了理论依据，并提供了有效的解 决方法。需求分析在N（ N>10）个居民区之间铺设煤气管道所

3、需代价最小，即求最小生成树问题。在我们的课本中介绍了两种求解方法：普利姆算法和克鲁斯卡尔算法。普利姆算法与网的变数无关，适宜求解边稠密的网的最小生成树。而克鲁斯卡尔算法正好相反,适宜求解边稀疏的最小生成树。由于在实际问题中，居民数量一般很有限，而任何两个居民区都可能有连线,即这样的图应该是边较为稠密的。因此，我们选择了普利姆算法对问题进行求解。四 概要设计1.普利姆算法分析1普利姆算法思想普利姆算法的思想是：在图中人去一个定点kO作为幵始点，令U=k0，W=V-U，其中V为图中所有顶点集，然后找一个顶点在U中，另一个顶点在 w中的边中最短的一条，找到后，将该边作为最小生成树的树边保存起来，并将

4、该边顶点全部加入 U集合中，并从W中删除这些顶点，然后重新调整U中顶点到 W中顶点的距离，使之保持最小，再重复此过程，直到 W为空集。2算法过程描述1）在图G=（ V，E）（ V是顶点，E是边）中，从集合 V中任取一个顶点，如kO放入集合U中，这时，U=kO，集合T（ E）为空。2）从kO出发寻找与U中顶点相邻权值最小的边的另一顶点k1，并使k1加入Uol卩U=kO，k1，同时将该边加入集合 T（E）中。3）重复（2），直到U=V为止。4）这时T（ E）中有n-1条边，T=（U，T（ E）就是一一颗最小生成树。门mm；尔整圏r 二 Q2、模块分析根据对模型的功能分析，该管道铺设设计可以具有以下

5、功能:1管道铺设信息的输入;2最小生成树信息的输出;功能模块图:3.抽象数据类型分析area num居民区总数（顶点总数）；edgenum边的总数;date 20邻接矩阵存储图结构;short-wayi边的权值;居民区i到目前生成树中所有点集 U中某个居民区的路程最小值n ear-areaiU中能使其最小的居民区5.全部流程五、详细设计1.算法分析1信息输入模块II读入图的信息，并将邻接矩阵输出Void read（）/输入顶点个数和边的条数Printf “请输入：定点数，变数：n”）；Seanf( %d,%d&areanum,&dedgenm);/初始化邻接矩阵各元素值Int

6、i, j,k;for(i=0;i<area nu m;i+) for(j=0;j<area nu m;j+) date i j=INFINIT Y;/读入边Int from,to ,s;Printf（输入边，格式为i，j，k，表示i到j的权值是k： n ”）;For(i=0;i<dege nu m;i+)Scanf( %d,%d,%d：&from,&to,&s);date fromto=s;date tofromst;/输出邻接矩阵 for(i=0;i<area nu m;i+) for(j=0;j<area nu m;j+)Printf(

7、 %dt ”,datei j);Printf( n ”);2建立最小生成树并输出结果/用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边 void Min iS pan Tree_ PRIM(MGra ph G,VertexTy pe u) /system("cls");int i,j,k;min side closedge;k=LocateVex(G,u);for(j=O;jvG.vexnum;+j) / 辅助数组初始化if(j!=k)strc py (closedgej.adjvex,u);closedgej.lowcost=G.arcskj.adj;c

8、losedgek.lowcost=0; / 初始,U=uprintf("最小代价生成树的各条边为:n");for(i=1;i<G.vex nu m;+i) /选择其余G.vexnum-1个顶点k=minimum(closedge,G);/求出T的下一个结点：第 K顶点 printf("(%s-%s)n",closedgek.adjvex,G.vexsk); / 输出生成树的边closedgek.lowcost=0; / 第 K顶点并入 U 集for(j=0;j<G.vex nu m;+j)if(G.arcskj.adj<closedge

9、j.lowcost)/新顶点并入U集后重新选择最小边 strc py(closedgej.adjvex,G.vexsk);closedgej.lowcost=G.arcskj.adj;system(" pause");2.源程序代码#i nclude <stdio.h> #i nclude <limits.h> #i nclude<stri ng.h> #in clude <malloc.h> #in clude<stdlib.h> #define MAX VERTEX NUM 20 最大顶点个数#define M

10、AX NAME 3 /顶点字符串的最大长度 +1 /#define MAX INFO 20 /相关信息字符串的最大长度 +1 #define INFINITY INT MAX /用整型最大值代替 typ edef int VRT ype;typ edef char InfoType;typ edef char VertexTy peMAX_NAME;/邻接矩阵的数据结构 typ edef structVRType adj; /顶点关系类型。对无权图，用1（是咸0（否）表示相邻否;/对带权图，则为权值类型InfoType *info; /该弧相关信息的指针（可无）ArcCell, AdjMatr

11、ixMAX_VERTEX_NUMMAX_VERTEX_NUM;/图的数据结构 typ edef structVertexType vexsMAX_VERTEX_NUM;/ 顶点向量AdjMatrix arcs;/邻接矩阵int vex num,/图的当前顶点数arcnum;/图的当前弧数 MGra ph;/记录从顶点集U到V-U的代价最小的边的辅助数组定义typ edef structVertexT ype adjvex;VRType lowcost;mi nsideMAX_VERTEX_NUM;/若G中存在顶点u,则返回该顶点在图中位置；否则返回-1。int LocateVex(MGra p

12、h G,VertexTy pe u) int i;for(i = 0; i < G.vex num; +i)if( strc mp (u, G.vexsi) = 0)return i;return -1;/代价保存为文件/代价存入文件 void wenjia n()/system("cls");FILE *fp;char s50,ch;strc py(s,"D:record.txt");if(fp=fo pen (s,"ab+")=NULL) printf（"无法打幵此文件n"）;exit(0);else/p

13、rintf（"请向磁盘中输入原点总数和边的总数：n"）;/printf（"请输入顶点数边数n"）;/sca nf("%d %d",&G.vex num, &G.arc num);/printf（"请输入各居民点:"）;/for(i nt i=1;i<=N;i+)/sea nf("%c",&G.vexsi);/in/fput(G.vexsi,fp);/printf("请向磁盘中输入各原点和边的总数同时记录原点，目的点，及相应的权值：(输入#键表示结束)n&q

14、uot;);printf("请向磁盘中输入各原点和边的总数：(输入$键表示结束)n");ch=getchar();while(ch!='$')fputc(ch,fp);ch=getchar();printf("请向磁盘中输入原点，目的点，及相应的权值：(输入#键表示结束)n");ch=getchar();while(ch!='#')fputc(ch,fp);ch=getchar();/从文件中得到信息构成图void xia nshi ()/system("cls");FILE *fp;char s50,

15、ch;strc py(s,"D:record.txt");if(fp=fo pen (s,"广)=NULL)printf（"无法打幵此文件n"）;exit(0);elsewhile(!feof(fp)ch=fgetc(fp);pu tchar(ch);putchar(10);fclose(fp);system(" pause");/ 算法 7.2P162/采用数组（邻接矩阵）表示法，构造无向网Goint CreateAN(MGra ph *G)/system("cls");int i,j,k,w;/cha

16、r sMAX_INFO,*i nfo;/ char *info;VertexT ype va,vb;printf（"请输入无向网G的顶点数，边数，（空格区分）"）;sca nf("%d%d"，&(*G).vex num,&( *G).arc num);printf("请输入 %d 个顶点的值:n",(*G).vexnum);for(i=0;i<(*G).vex num;+i) / 构造顶点向量sca nf("%s",(*G).vexsi);for(i=0;i<(*G).vex num;+

17、i) / 初始化邻接矩阵for(j=0;j<(*G).vex nu m;+j)(*G).arcsij.adj=INFINITY; / 网初始化为无穷大/(*G).arcsij.i nfo二NULL;printf（"请输入%d条边的顶点1顶点2权值（以空格作为间隔）: n",(*G).arc nu m);for(k=0;k<(*G).arc num;+k)seanf("%s%s%d%*c",va,vb，&w); / %*c 吃掉回车符i=LocateVex(*G,va);j=LocateVex(*G,vb);(*G).arcsij.ad

18、j=(*G).arcsji.adj二w; /无向/if(ln cI nfo)/gets(s);/w=strle n(s);printf（"请输入该边的相关信息（%d个字符）:",MAX_INFO）;/in fo=(char*)malloc(w+1)*sizeof(char);/strc py(i nfo,s);/(*G).arcsij.i nfo=(*G).arcsji.i nfo二i nfo; /无向/printf（"输出临接矩阵：n"）;for(i=0;i<(*G).vex num;+i)for(j=0;j<(*G).vex nu m;+

19、j) if( j%3=0) prin tf("n");prin tf("%d ", (*G).arcsij.adj);if(w)return 1;system(" pause");/ 求closedgeowcost的最小正值int minimu m(mi nside SZ,MGraph G)int i=0,j,k,mi n;while(!SZi.lowcost)i+;min=SZi.lowcost; / 第一个不为 0 的值k=i;for(j=i+1;j<G.vex nu m;j+)if(SZj.lowcost>0)if(

20、mi n>SZj.lowcost)min 二SZjo wcost;k=j;return k;/ 算法 7.9 P175/用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边 void Min iS pan Tree_ PRIM(MGra ph G,VertexTy pe u) /system("cls");int i,j,k;min side closedge;k=LocateVex(G,u);for(j=0;jvG.vexnum;+j) / 辅助数组初始化if(j!=k)strc py (closedgej.adjvex,u);closedgejo w

21、cost=G.arcskj.adj;closedgek.lowcost=0; / 初始,U=uprintf("最小代价生成树的各条边为:n");for(i=1;i<G.vex nu m;+i) /选择其余G.vexnum-1个顶点k=minimum(closedge,G);/求出T的下一个结点：第 K顶点printf("(%s-%s)n",closedgek.adjvex,G.vexsk); / 输出生成树的边closedgek.lowcost=0; / 第 K顶点并入 U 集for(j=0;j<G.vex nu m;+j)if(G.arcs

22、kj.adj<closedgej.lowcost)/新顶点并入U集后重新选择最小边strc py(closedgej.adjvex,G.vexsk);closedgejo wcost=G.arcskj.adj;system(" pause");void mai n() /system("cls");MGra ph G;int X乙while(1)/system("cls");prin tf("n");管道铺设最佳方案选择prin tf ("*n");printf("0记录保存为文

23、件n");printf("1从文件中读记录n");printf("2构造无向网n ");printf("3求出最小生成树n");p ri ntf("4退出n");prin tff * *n");printf(" 请输入操作序号(0-4):n");sca nf("%d", &xz);switch(xz) case 0: wenjia n( );break;case 1: xianshi ();break;case 2: CreateAN(&G);break;case 3:Min iS pan Tree_ PRIM(G,G.vexsO);break;case 4: exit(0);default:printf（"输入无效指令！按任意键继续r'）;system(" pau