管道铺设数据结构课程设计报告

《数据结构课程设计》报告题目：管道铺设设计专业：软件072学号：04号姓名：指导老师：时间：6.29～7.82目录摘要-----------------------------------------------------------3一、问题重述、需求分析及研究意义-------------------------------31.1问题重述---------------------------------------------------31.2需求分析---------------------------------------------------31.3研究意义---------------------------------------------------3二、数据结构的逻辑设计和物理存储设计---------------------------42.1数据结构的逻辑设计-----------------------------------------42.2数据的物理存储结构设计------------------------------------4三、详细设计---------------------------------------------------53.1普里姆算法分析--------------------------------------------53.1.1普里姆算法思想-------------------------------------------53.1.2算法过程描述---------------------------------------------53.2各功能模块的划分------------------------------------------63.3数据结构--------------------------------------------------73.4流程描述--------------------------------------------------73.4.1信息输入模块---------------------------------------------73.4.2建立最小生成树并输出结果---------------------------------83.5算法时间复杂度分析及流程图---------------------------------83.5.1时间复杂度----------------------------------------------83.5.2流程图---------------------------------------------------93.6源程序代码-------------------------------------------------93.7程序最终实现结果------------------------------------------12四、小结------------------------------------------------------14参考文献------------------------------------------------------143摘要：N(N10)个居民区之间需要铺设煤气管道。假设任意两个居民区之间都可以铺设煤气管道，但代价不同。一、问题重述、分析及研究意义1.1问题重述N(N10)个居民区之间需要铺设煤气管道。假设任意两个居民区之间都可以铺设煤气管道，但代价不同。问题的实质就是编写相应程序求解最小生成树问题。程序要求：事先任意两居民区之间铺设煤气管道的代价存入磁盘文件中。设计一个最佳方案使得这N个居民区之间铺设煤气管道所需代价最小，并将结果以图形方式在屏幕上输出。1.2需求分析在N(N10)个居民区之间铺设煤气管道所需代价最小，即求最小生成树问题。在我们的课程中介绍了两种求解方法：普里姆（prim）算法和克鲁斯卡尔（kruskal）算法。普里姆算法与网的变数无关，时间复杂度为O（n2),适宜求解边稠密的网的最小生成树。而克鲁斯卡尔算法正好相反，时间复杂度为O（eloge）（e为网中边的数目），故而该算法适宜求边稀疏的最小生成树。由于在实际应用中，居民区数量一般很有限，而任何两个居民区间都可能有连线，即这样的图应该是边较为稠密的。因此，我们选择普里姆算法对问题进行求解。1、建立一个带权无向图的邻接矩阵，然后进行深度和广度优先搜索遍历，并输出遍历的结果序列。最后若此图是连通图，输出该网的一颗最小生成树。2、网中顶点的编号从0开始顶点的信息为字符。3、按照网的邻接矩阵定义输出该矩阵。4、在非连通图的情况下要能够按深度和广度优先搜索遍历整个网。5、用普里姆法构造最小生成树。在最小生成树算法中，应判断该网是否连通，如果非连通，则需输出提示信息并退出程序。1.3研究意义实际生活中最小生成树的问题具有很大的意义。例如，本文所讨论的构架居民区之间铺设煤气管道代价最小，还有在若干的地区见铺设光缆，等等。最小生4成树让许多诸如求造价最小、最短路径等最优化的现实问题找到了理论依据，并提供了有效的解决方法。二、数据结构的逻辑设计和物理存储设计2.1数据结构的逻辑设计每个居民区可能与其他任何一个居民区相连，也即居民区与居民区之间是一种多对多的关系。把一个城市抽象成为一个顶点，居民区之间的连线抽象为图中顶点之间的边，路程作为边的权值。那么，结构中的每个数据元素（顶点）都可能有任意多个直接前驱和直接后继，即是一种图结构。当然，从居民区0到居民区1应和从居民区1到居民区0是等价的。因此，我们把该数据的逻辑结构定义为无向图结构。图示如下：2.2数据的物理存储结构设计为了方便图的各种操作，如该算法当中需要判断某顶点间是否有边、比较边的权值、求顶点的位置等问题，而且这是个边较为稠密的图。鉴于此，我们采取邻接矩阵表示法来存储图结构。如对上图采用邻接矩阵存储可表示为：3210AB=0111101111011110用邻接矩阵创建无向图的算法：//邻接矩阵数据类型描述#defineMAX30/*最大定点数*/typedefstruct{elemtypevertex[vnum];/*存放顶点信息,若顶点除编号外无其它信息，则无需数组*/intmatrix[vnum][vnum];0123图形结构抽象描述示意图5}adjmatrix;//求顶点位置函数intLocateVertex(AdjMatrix*G,VertexDatav){intj=ERROR，k;for(k=0;kG-vexnum;k++)if(G-vexs[k]==v){j=k;break;}return(j);}//创建一个无向图#defineINFINITY9999//INFINITY代表一个无穷大的数intCreatUDN(AdjMtrix*G){inti,j,k,weight;VertexDatav1,v2;scanf(%d,%d,&G-arcnum,&G-vexnum);//输入图的顶点个数和边的条数for(i=0;iG-vexnum;i++)//初始化邻接矩阵for（j=0;jG-vexnum;j++)G-arcs[i][j].Adj=INFINITY;for(i=0;iG-vexnum;i++)scanf(%d,&G-vexs[i]);//输入图的顶点for(k=0;kG-vexnum;k++){scanf(%d,%d,%d,&i,&j,&weight);G-arcs[i][j].Adj=G-arcs[j][i]=weight;//建立边}reurn（OK）；}三、详细设计3.1普里姆算法分析3.1.1普里姆算法思想普里姆方法的思想是：在图中任取一个顶点k0作为开始点，令U={k0}，W=V-U，其中V为图中所有顶点集，然后找一个顶点在U中，另一个顶点在W中的边中最短的一条，找到后，将该边作为最小生成树的树边保存起来，并将该边顶点全部加入U集合中，并从W中删去这些顶点，然后重新调整U中顶点到W中顶点的距离,使之保持最小，再重复此过程，直到W为空集止。3.1.2该算法过程描述(1)在图G=(V,E)（V表示顶点，E表示边）中，从集合V中任取一个顶点（例如取顶点k0）放入集合U中，这时U={k0}，集合T(E)为空。6(2)从k0出发寻找与U中顶点相邻（另一顶点在V中）权值最小的边的另一顶点k1，并使k1加入U。即U={k0,k1}，同时将该边加入集合T(E)中。(3)重复(2)，直到U=V为止。(4)这时T(E)中有n-1条边，T=(U,T(E))就是一棵最小生成树。Prim算法示意图3.2各功能模块的划分根据对模型的功能分析，该管道铺设设计可以具有以下功能：①管道铺设信息的输入；②最小生成树信息的输出；下面我们给出相应的功能模块图：最小生成树问题信息的输入模块建立最小生成树并输出管道铺设设计问题73.3数据结构areanum居民区总数（顶点总数）；edgenum边的总数；date[][20]邻接矩阵存储图结构；s边的权值；short_way[i]居民区i到到目前生成树中所有点集U中某个居民区的路程最小值near_area[i]U中能使其最小的居民区3.4流程描述3.4.1信息输入模块//读入图的信息，并将邻接矩阵输出voidread（）{//输入顶点个数和边的条数printf（请输入：顶点数，边数：\n);scanf(%d,%d,&areanum,&edgenum);//初始化矩阵各元素值inti,j,k;for(i=0；iareanum;i++)for(j=0;jareanum;j++)date[i][j]=INFINITY;//读入边intfrom,to,s;printf(输入边,格式为i,j,k,表示i到j的权值是k:\n);for(i=0;iedgenum;i++){scanf(%d,%d,%d,&from,&to,&ws);date[from][to]=s;date[to][from]=st;}//输出邻接矩阵for(i=0;iareanum;i++){for(j=0;jareanum;j++){printf(%d\t,date[i][j]);}printf(\n);}}3.4.2建立最小生成树并输出结果voidprim(intdate[][MAXNODE],intareanum,intnear_area[])8{//辅助数组short_way,near_area//short_way[i]表示居民区i到到目前生成树中所有点集U中某个居民区（点）的路程最小值//near_city[i]表示U中能使其最小的居民区(点)intshort_way[areanum];intmin;inti,j,k;//0已经放入U中//初始化short_way和near_areafor(i=1;iareanum;i++){short_way[i]=date[0][i];near_area[i]=0;}short_way[i]=0;near_area[0]=0;for(i=1;iareanum;i++)//有n-1条边要加入生成树,所以只要循环n-1次即可{min=INFINITY;//求生成树外顶点到生成树内顶点具有最小权值的边j=1;k=1;while(jareanum)//确定当前具有最小权值的边及位置{if(short_way[j]!=0&&short_way[j]min){min=short_way[j];k=j;}j++;}printf(居民区序号为%d，居民区路程（边的权值）为%d,k,min);short_way[k]=0;for(j=0;jn;j++){if(date[k][j]short_way[j]){short_way[j]=date[k][j];near_area