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

计算机软件技术基础实验报告I数据结构实验三管道铺设施工的最佳方案问题一、问题描述1实验题目需要在某个城市N个居民小区之间铺设煤气管道，则在这N个居民小区之间只需要铺设N1条管道即可。假设任意两个小区之间都可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。2基本要求在可能假设的M条管道中，选取N1条管道，使得既能连通N个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的存储采用邻接表的结构。3测试数据使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。右侧是给出的参考解。图1小区煤气管道铺设网及其参考解4输入输出从键盘或文件读入上图中的无向网，以顶点对（I,J）的形式输出最小生成树的边。2、需求分析1本程序所能达到的基本可能本程序用无向网表示各小区之间的管道铺设情况，结点表示小区位置，边表示铺设的管道，边的权值表示各段的费用。采用邻接表存储,输入无向网数据创建邻接表，通过普利姆算法求出最小生成树，即是最佳铺设方案。2输入输出形式及输入值范围根据提示输入总的边数，结点数。再根据提示输入各结点的信息即结点的名称，输入边的信息，即边的两个端点和该边的权值。输入后成功创建邻接表，自动输出所建立的邻接表和普利姆算法求出的最小生成树。3测试数据要求使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。右侧是给出的参考解。输入结点数和边数915根据提示分别输入九个结点的名称ABCDEFGHI输入边的信息，即两个端点的名称及该边的权值（AB328）；（BC59）CD213DE673AC446AH121AI182HI87HG525CG564CE411EF856DF987IF792EG105输入完毕直接输出“建立的图邻接表表示为08721202460313542465235834642776808570”直接输出应用PRIME算法，得到的最小生成树的结果，用结点字母表示三、概要设计为了实现上述功能，该程序以邻接表存储的无向图模拟居民住宅的分布和住宅之间的管道，通过普利姆算法求最小生成树来求解管道最小花费。因此需要邻接表这一抽象数据类型来表示无向图。还需要普利姆算法求最小生成树。1邻接表抽象数据类型定义ADTALGRAPH数据对象DAI,BI,CI|AIADJLIST,BIINT,CIINT,I1,2,N,N0数据关系R基本操作CREATEALGRAPHG/建立无向图的邻接表存储VOIDPRIMEALGRAPHG,INTFROM/用普利姆算法求最小生成树ADTALGRAPH2ADT的C语言形式说明TYPEDEFSTRUCTADJLISTADJLIST/邻接表INTN,E/顶点数和边数ALGRAPH/ALGRAPH是以邻接表方式存储的图类型VOIDCREATEALGRAPHG/建立无向图的邻接表存储VOIDPRIMEALGRAPHG,INTFROM/用普利姆算法求最小生成树3本程序保护模块主函数模块图模块4普利姆算法分析（1）普利姆算法思想普利姆算法的思想是在图中人去一个定点K0作为开始点，令UK0，WVU，其中V为图中所有顶点集，然后找一个顶点在U中，另一个顶点在W中的边中最短的一条，找到后，将该边作为最小生成树的树边保存起来，并将该边顶点全部加入U集合中，并从W中删除这些顶点，然后重新调整U中顶点到W中顶点的距离，使之保持最小，再重复此过程，直到W为空集。（2）算法过程描述在图G（V，E）（V是顶点，E是边）中，从集合V中任取一个顶点，如K0放入集合U中，这时，UK0，集合T（E）为空。从K0出发寻找与U中顶点相邻权值最小的边的另一顶点K1，并使K1加入U。即UK0，K1，同时将该边加入集合T（E）中。重复（2），直到UV为止。这时T（E）中有N1条边，T（U，T（E）就是一一颗最小生成树。5主程序流程及其模块调用关系1主程序流程先提示用户输入相关数据节点数，边数，各结点名称，各边两端名称和边的权值。创建邻接表存储无向图并输出这一邻接表。用普利姆算法求最小生成树访问各节点，从已经访问过的节点和未访问过的节点组成的所有边中挑出权重最小的一条边放入邻接表EDGENODEMINEDGE中。输出这个最小权重的表。（2）模块调用关系（3）功能模块图主函数模块邻接表存储模块CREATEALGRAPHG普利姆算法求最小生成树模块PRIMEALGRAPHG,INTFROM管道铺设设计问题最小生成树问题信息输入模块建立最小生成树问题题判断是否访问过ISEXISTSINTVISITED,INTN,INTVEX6主要算法流程图CREATEALGRAPHG读入节点数和边数INI0读入顶点信息II1K0KE读入边两个对应顶点名及权值将新边表结点插入到VI和VJ邻接表头部KK1结束开始四、详细设计1、元素类型、结点类型、结点指针类型TYPEDEFSTRUCTNODE/边表节点INTSRC/边端的序号CHARSRCNAME/边端的名称INTADJVEX/邻接点域NODENEXT/指向下一个邻接点的指针域CHARADJNAMEFLOATCOST/边的权值EDGENODETYPEDEFSTRUCT/顶点表节点CHARVERTEX/顶点域EDGENODEFIRSTEDGE/边表头指针VERTEXNODETYPEDEFVERTEXNODEADJLISTMAXVERTEXNUM/ADJLIST是邻接表类型TYPEDEFSTRUCTADJLISTADJLIST/邻接表INTN,E/顶点数和边数ALGRAPH/ALGRAPH是以邻接表方式存储的图类型2创建邻接表VOIDCREATEALGRAPHG/建立无向图的邻接表存储INTK,W,VEDGENODESCOUTGNGE/读入顶点数和边数FORINTI0INI/建立有N个顶点的顶点表COUTC/读入顶点信息GADJLISTIVERTEXCGADJLISTIFIRSTEDGENULL/顶点表的边表头指针设为空PRINTF“建立边表N“FORK0KEK/建立边表FLOATCOSTCOUTCICJCOST/读入边/将输入的节点名A,B,C转化成内部的下标ICIAJCJA/将输入的VIVJ这条边插入到邻接表头部SEDGENODEMALLOCSIZEOFEDGENODESSRCISSRCNAMEGADJLISTIVERTEXSADJVEXJSADJNAMEGADJLISTJVERTEXSCOSTCOSTSNEXTGADJLISTIFIRSTEDGE/插入表头GADJLISTIFIRSTEDGESSEDGENODEMALLOCSIZEOFEDGENODESSRCJSSRCNAMEGADJLISTJVERTEXSADJVEXISADJNAMEGADJLISTIVERTEXSCOSTCOSTSNEXTGADJLISTJFIRSTEDGEGADJLISTJFIRSTEDGES3用普利姆算法生成最小生成树INTISEXISTSINTVISITED,INTN,INTVEX/判断VEX是否在VISITED数组里INTEXISTS0FORINTI0IN/当访问到所有的点，就表示整个过程结束EDGENODEMINEDGENULLFLOATMINCOST9999FORINTI0IADJLISTVISITEDNODESIFIRSTEDGEWHILEPNULLIFISEXISTSVISITEDNODES,VISITEDINDEX,PADJVEX0MINEDGEPPPNEXTTOTALMINCOSTMINCOSTCHOSENEDGEINDEXMINEDGECOUTSRCNAME“ADJNAMEADJVEX4主函数INTMAINPRINTF“试验名称管道铺设施工的最佳方案问题N“PRINTF“学号031350103N“PRINTF“姓名N“PRINTF“N“TIME_TRAWTIME1STRUCTTMTIMEINFO1TIMETIMEINFO1LOCALTIME/时间函数；PRINTF“程序运行开始,当前日期和时间S“,ASCTIMETIMEINFO1ALGRAPHGALGRAPHMALLOCSIZEOFALGRAPHCREATEGCOUTNIEDGENODEPGADJLISTIFIRSTEDGEPRINTF“D“,I/输出建立的邻接表WHILEPNULLPRINTF“D“,PADJVEXPPNEXTPRINTF“N“PRINTF“应用PRIM算法，得到的最小生成树是“PRIMEG,0CHARKONGCINKONG/输出最小生成树RETURN0TIME_TRAWTIME2STRUCTTMTIMEINFO2TIMETIMEINFO2LOCALTIMEPRINTF“程序运行结束,当前日期和时间S“,ASCTIMETIMEINFO2五、调试分析1、程序将小区的相关信息输入存储在图的邻接表结构中，每个节点与小区一一对应，权值与小区之间的距离一一对应，只需要输入节点符号，以及相应的权值，程序会自动输出相应的最小生成树即相应的管道铺设线路。2、算法的时空分析1由于CREATEALGRAPHG程序中读入顶点的操作执行了N次，读入边的操作执行了E次，故其时间复杂度为O（N2E）（2）PRIMEALGRAPHG,INTFROM的时间复杂度为O（N2），N是顶点个数；（3）所有算法的空间复杂度都是O1六、使用说明用户首先根据提示输入节点数N和边数E，应输入整数，用空格隔开，如915；再根据提示输入N个结点的名称，分N次输入；再根据提示输入边的信息，即两个端点的名称及该边的权值，名称为字符，权值为实数，用空格隔开，如AB328，分E次输入输入完成后不需操作，自动输出所建立的邻接表及最小生成树的结果七、调试结果输入节点数边数915输入九个结点的名称ABCDEFGHI输入边的信息，即两个端点的名称及该边的权值（AB328）；（BC59）CD213DE673AC446AH121AI182HI87HG525CG564CE411EF856DF987IF792EG105输入完毕直接输出“建立的图邻接表表示为08721202460313542465235834642776808570”输出“应用PRIM算法，得到的最小生成树是AHHIABBCCDCEEGIF”初始界面为输入数据时的界面输出界面八、遇到的问题和解决方法1最初拿到这个题目时还不会普利姆算法的具体内容，只知道求最小生成树的两个方法叫普利姆算法和克里斯卡尔算法，但不理解也不会写代码。于是我上网查阅了相关资料，还请教了上机时给我们辅导的研究生学长，学会了PRIM算法。2开始建立邻接表的时候我是照着软件技术基础教程课本上给的邻接表存储有向图的代码修改的，想让它存储无向图，但开始只是在创建边表结点时设置了两个CHAR型变量存放两个名称和两个INT型变量存储序号，后面不知道怎么改，后经助教学长指点知CREATEALGRAPHG中对应改动，将新表结点插入到VI的边表头部这里的操作是双向的才能保证图是无向的，即，插入到VI后一次，插入到VJ后一次，如这段代码所示SSRCISNEXTGADJLISTIFIRSTEDGE/插入表头GADJLISTIFIRSTEDGESSSRCJSNEXTGADJLISTJFIRSTEDGEGADJLISTJFIRSTEDGES3输入所有的结点和边的信息后程序运行出错，如图后经排查调试发现错误原因是在输出图G的时候，直接用GADJLISTIFIRSTEDGE这个指针，并在输出的过程中，不断的修改GADJLISTIFIRSTEDGE，导致FIRSTEDGE最后被修改成了NULL，在后面的PRIME算法中出现了空指针异常。修改办法是，用指针P代替GADJLISTIFIRSTEDGE做遍历，防止了GADJLISTIFIRSTEDGE被随意修改。经再测试发现运行正常，错误得到解决。9、实验收获和感想这次的计算机实践题目是要求用邻接表存储无向图再求出最小生成树，完成以后感觉这一次的程序是本学期计算机实践数据结构部分相对较难的一个题目。我们在课本上给出的程序语句样例是建立有向图，建立无向图时只需要做以修改，在边表结点中设置两组变量分别存储两端的节点。这个程序只需要求最小生成树，而且题目说明了要用邻接表存储，即需求明确且不复杂，所以设计程序成思路明确，先建立邻接表再求最小生成树。再求最小生成树时，有普里姆算法和克里斯卡尔算法两种选择，我选择了自己更为理解的普里姆算法。这也是第一次运用这些只理解理论的算法来写实际的程序。写过调试过才对算法的精髓有了深入的理解。完成整个程序设计使得对数据结构、算法的使用更加熟练。同时通过直接对图的操作，加深了对数据结构的理解和认识。感觉自己编写程序的能力在一次次实践中有着显著的进步，要想真正理解并记住一个算法，亲自的编写程序比其他任何方法都更加有效果。比如本次编程前我对于普里姆算法完全不懂，只知道它是用来求解最小生成树的，却没有想过它的逻辑思路，知道这次要用到才去查找资料学习普里姆算法，最终在运用中实现了从不会到熟练运用的转型。感觉收获非常大。以后即使这门实践课结束了，我也要经常联系编写程序，在实践运用中学习算法。十、源程序INCLUDEINCLUDEINCLUDEINCLUDEINCLUDEDEFINEMAXVERTEXNUM50DEFINEMAXEDGENUM1000/边的最大值TYPEDEFSTRUCTNODE/边表节点INTSRC/边端的序号CHARSRCNAME/边端的名称INTADJVEX/邻接点域NODENEXT/指向下一个邻接点的指针域CHARADJNAMEFLOATCOST/边的权值EDGENODETYPEDEFSTRUCT/顶点表节点CHARVERTEX/顶点域EDGENODEFIRSTEDGE/边表头指针VERTEXNODETYPEDEFVERTEXNODEADJLISTMAXVERTEXNUM/ADJLIST是邻接表类型TYPEDEFSTRUCTADJLISTADJLIST/邻接表INTN,E/顶点数和边数ALGRAPH/ALGRAPH是以邻接表方式存储的图类型VOIDCREATEALGRAPHG/建立无向图的邻接表存储INTK,W,VEDGENODESCOUTGNGE/读入顶点数和边数FORINTI0INI/建立有N个顶点的顶点表COUTC/读入顶点信息GADJLISTIVERTEXCGADJLISTIFIRSTEDGENULL/顶点表的边表头指针设为空PRINTF“建立边表N“FORK0KEK/建立边表FLOATCOSTCOUTCICJCOST/读入边ICIA/将输入的节点名A,B,C转化成内部的下标JCJASEDGENODEMALLOCSIZEOFEDGENODE/将输入的VIVJ这条边插入到邻接表头部SSRCISSRCNAMEGADJLISTIVERTEXSADJVEXJSADJNAMEGADJLISTJVERTEXSCOSTCOSTSNEXTGADJLISTIFIRSTEDGE/插入表头GADJLISTIFIRSTEDGESSEDGENODEMALLOCSIZEOFEDGENODESSRCJSSRCNAMEGADJLISTJVERTEXSADJVEXISADJNAMEGADJLISTIVERTEXSCOSTCOSTSNEXTGADJLISTJFIRSTEDGEGADJLISTJFIRSTEDGESINTISEXISTSINTVISITED,INTN,INTVEX/判断VEX是否