数据结构实验报告—管道铺设问题

《计算机软件技术基础》实验报告I—数据结构实验三：管道铺设施工的最佳方案问题一、问题描述1.实验题目：需要在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道即可。假设任意两个小区之间都可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。2.基本要求：在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的存储采用邻接表的结构。3.测试数据：使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。右侧是给出的参考解。图1小区煤气管道铺设网及其参考解4.输入输出:从键盘或文件读入上图中的无向网，以顶点对（i,j）的形式输出最小生成树的边。二、需求分析1.本程序所能达到的基本可能：本程序用无向网表示各小区之间的管道铺设情况，结点表示小区位置，边表示铺设的管道，边的权值表示各段的费用。采用邻接表存储,输入无向网数据创建邻接表，通过普利姆算法求出最小生成树，即是最佳铺设方案。2.输入输出形式及输入值范围：根据提示输入总的边数，结点数。再根据提示输入各结点的信息即结点的名称，输入边的信息，即边的两个端点和该边的权值。输入后成功创建邻接表，自动输出所建立的邻接表和普利姆算法求出的最小生成树。3.测试数据要求：使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。右侧是给出的参考解。输入结点数和边数：915根据提示分别输入九个结点的名称：ABCDEFGHI输入边的信息，即两个端点的名称及该边的权值：（AB32.8）；（BC5.9）;(CD21.3);(DE67.3);(AC44.6);(AH12.1);(AI18.2);(HI8.7);(HG52.5);(CG56.4);(CE41.1);(EF85.6);(DF98.7);(IF79.2);(EG10.5)输入完毕直接输出“建立的图邻接表表示为：0-8-7-2-1-2-0-2-4-6-0-3-1-3-5-4-2-4-6-5-2-3-5-8-3-4-6-4-2-7-7-6-8-0-8-5-7-0”直接输出应用prime算法，得到的最小生成树的结果，用结点字母表示三、概要设计为了实现上述功能，该程序以邻接表存储的无向图模拟居民住宅的分布和住宅之间的管道，通过普利姆算法求最小生成树来求解管道最小花费。因此需要邻接表这一抽象数据类型来表示无向图。还需要普利姆算法求最小生成树。1.邻接表抽象数据类型定义ADTALGraph{数据对象：D={ai,bi,ci|ai∈AdjList,bi∈int,ci∈int),i=1,2...,n,n≥0}:数据关系：R=∅基本操作:create(ALGraph*G)//建立无向图的邻接表存储voidprime(ALGraph*G,intfrom)//用普利姆算法求最小生成树}ADTALGraph2.ADT的c语言形式说明：typedefstruct{AdjListadjlist;//邻接表intn,e;//顶点数和边数}ALGraph;//ALGraph是以邻接表方式存储的图类型voidcreate(ALGraph*G)//建立无向图的邻接表存储voidprime(ALGraph*G,intfrom)//用普利姆算法求最小生成树3.本程序保护模块：主函数模块图模块4.普利姆算法分析（1）普利姆算法思想：普利姆算法的思想是：在图中人去一个定点k0作为开始点，令U={k0}，W=V-U，其中V为图中所有顶点集，然后找一个顶点在U中，另一个顶点在w中的边中最短的一条，找到后，将该边作为最小生成树的树边保存起来，并将该边顶点全部加入U集合中，并从W中删除这些顶点，然后重新调整U中顶点到W中顶点的距离，使之保持最小，再重复此过程，直到W为空集。（2）算法过程描述：在图G=（V，E）（V是顶点，E是边）中，从集合V中任取一个顶点，如k0放入集合U中，这时，U={k0}，集合T（E）为空。从k0出发寻找与U中顶点相邻权值最小的边的另一顶点k1，并使k1加入U。即U={k0，k1}，同时将该边加入集合T（E）中。重复（2），直到U=V为止。这时T（E）中有n-1条边，T=（U，T（E））就是一一颗最小生成树。5.主程序流程及其模块调用关系:(1)主程序流程：先提示用户输入相关数据：节点数，边数，各结点名称，各边两端名称和边的权值。创建邻接表存储无向图并输出这一邻接表。用普利姆算法求最小生成树：访问各节点，从已经访问过的节点和未访问过的节点组成的所有边中挑出权重最小的一条边放入邻接表EdgeNode*minEdge中。输出这个最小权重的表。（2）模块调用关系（3）功能模块图主函数模块邻接表存储模块create(ALGraph*G)普利姆算法求最小生成树模块prime(ALGraph*G,intfrom)管道铺设设计问题最小生成树问题信息输入模块建立最小生成树问题题判断是否访问过isExists(int*visited,intn,intvex)6.主要算法流程图create(ALGraph*G)读入节点数和边数i＜ni=0读入顶点信息i=i+1K=0K＜e读入边v1,v2两个对应顶点名及权值开始四、详细设计1、元素类型、结点类型、结点指针类型：typedefstructnode//边表节点{intsrc;//边端的序号charsrcName;//边端的名称intadjvex;//邻接点域node*next;//指向下一个邻接点的指针域charadjName;floatcost;//边的权值}EdgeNode;typedefstruct//顶点表节点{charvertex;//顶点域EdgeNode*firstedge;//边表头指针}VertexNode;typedefVertexNodeAdjList[MaxVertexNum];//AdjList是邻接表类型typedefstruct{AdjListadjlist;//邻接表intn,e;//顶点数和边数}ALGraph;//ALGraph是以邻接表方式存储的图类型2.创建邻接表voidcreate(ALGraph*G)//建立无向图的邻接表存储{intk,w,v;EdgeNode*s;cout请输入节点数和边数（用空格隔开）endl;cinG-nG-e;//读入顶点数和边数for(inti=0;iG-n;i++)//建立有n个顶点的顶点表{cout请输入顶点名称：;charc;cinc;//读入顶点信息G-adjlist[i].vertex=c;G-adjlist[i].firstedge=NULL;//顶点表的边表头指针设为空}printf(建立边表\n);for(k=0;kG-e;k++)//建立边表{floatcost;cout请输入边的信息（顶点1顶点2权值）;charci,cj;inti=-1,j=-1;cincicjcost;//读入边vi,vj的顶点对应名称//将输入的节点名(A,B,C...)转化成内部的下标i=ci-'A';j=cj-'A';//将输入的vi-vj这条边插入到邻接表头部s=(EdgeNode*)malloc(sizeof(EdgeNode));s-src=i;s-srcName=G-adjlist[i].vertex;s-adjvex=j;s-adjName=G-adjlist[j].vertex;s-cost=cost;s-next=G-adjlist[i].firstedge;//插入表头G-adjlist[i].firstedge=s;s=(EdgeNode*)malloc(sizeof(EdgeNode));s-src=j;s-srcName=G-adjlist[j].vertex;s-adjvex=i;s-adjName=G-adjlist[i].vertex;s-cost=cost;s-next=G-adjlist[j].firstedge;G-adjlist[j].firstedge=s;}}3.用普利姆算法生成最小生成树intisExists(int*visited,intn,intvex)//判断vex是否在visited数组里{intexists=0;for(inti=0;in;i++){if(visited[i]==vex){exists=1;}}returnexists;}voidprime(ALGraph*G,intfrom)//用普利姆算法求最小生成树{intvisitedNodes[MaxVertexNum];intvisitedIndex=0;visitedNodes[visitedIndex++]=from;EdgeNodechosen[MaxEdgeNum];intedgeIndex=0;floattotalMinCost=0;while(visitedIndex!=G-n)//当访问到所有的点，就表示整个过程结束{EdgeNode*minEdge=NULL;floatminCost=9999;for(inti=0;ivisitedIndex;i++)//从已经访问过的节点和未访问过的节点组成的所有边中挑出权重最小的一条边{EdgeNode*p=G-adjlist[visitedNodes[i]].firstedge;while(p!=NULL){if(isExists(visitedNodes,visitedIndex,p-adjvex)==0&&p-costminCost){minCost=p-cost;minEdge=p;}p=p-next;}}totalMinCost+=minCost;chosen[edgeIndex++]=*minEdge;coutminEdge-srcName-minEdge-adjNameendl;//输出这条最小权重的表visitedNodes[visitedIndex++]=minEdge-adjvex;}}4.主函数intmain(){printf(试验名称：管道铺设施工的最佳方案问题\n);printf(学号：031350103\n);printf(姓名：\n);printf(=========================================================\n);time_trawtime1;structtm*timeinfo1;time(&rawtime1);timeinfo1=localtime(&rawtime1);//时间函数；printf(程序运行开始,当前日期和时间:%s,asctime(timeinfo1));ALGraph*G=(ALGraph*)malloc(sizeof(ALGraph));create(G);cout建立的图邻接表表示为：endl;for(inti=0;iG-n;i++){EdgeNode*p=G-adjlist[i].firstedge;printf(%d-,i);//输出建立的邻接表while(p!=NULL){printf(%d-,p-adjvex);p=p-next;}printf(\n);}printf(应用prim算法，得到的最小生成树是：);prime(G,0);charkong;cinkong;//输出最小生成树return0;time_trawtime2;structtm*timeinfo2;time(&rawtime2);timeinfo2=localtime(&rawtime2);printf(程序运行结束,当前日期和时间:%s,asctime(timeinfo2));}五、调试分析1、程序将