图论编程题3参考构成可以使n个城市连接的最小生成树

目录一需求分析211设计的任务212程序所能达到的功能213程序执行命令2二概要设计321抽象数据类型结构体数组的定义322程序模块423流程图4三详细设计531数据类型定义532程序主要模块5四调试分析和测试结果841调试分析842测试结果9五总结10六参考文献10七致谢11八附录111构造可以使N个城市连接的最小生成树一需求分析11设计的任务给定一个地区的N个城市间的距离网，用PRIM算法或KRUSKAL算法建立最小生成树，并计算得到的最小生成树的代价。12程序所能达到的功能121城市间的道路网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。122显示出城市间道路网的邻接矩阵。123最小生成树中包括的边及其权值，并显示得到的最小生成树的总代价。13程序执行命令输入城市数、道路数输入城市名输入道路信息执行KRUSKAL算法执行PRIM算法输出最小生成树2二概要设计21抽象数据类型结构体数组的定义IFNDEFADJACENCYMATRIXED/防止该头文件被重复引用DEFINEADJACENCYMATRIXED/而引起的数据重复定义DEFINEINFINITY32767/最大值DEFINEMAX_VERTEX_NUM20/最大顶点个数TYPEDEFINTVRTYPE/权值，即边的值TYPEDEFCHARINFOTYPE/附加信息的类型，后面使用时会定义成一个指针TYPEDEFCHARVERTEXTYPEMAX_VERTEX_NUM/顶点类型TYPEDEFENUMDG1,DN,UDG,UDNGRAPHKIND/有向图，有向网，无向图，无向网TYPEDEFSTRUCTARCCELLVRTYPEADJ/VRTYPE是顶点关系类型。对无权图，用1或0表示相邻否；对带权图，则为权值类型。INFOTYPEINFO/该弧关系信息的指针ARCCELL,ADJMATRIXMAX_VERTEX_NUMMAX_VERTEX_NUMTYPEDEFSTRUCTVERTEXTYPEVEXSMAX_VERTEX_NUM/顶点向量ADJMATRIXARCS/邻接矩阵INTVEXNUM,ARCNUM/图的当前顶点数和弧数GRAPHKINDKIND/图的种类标志MGRAPHTYPEDEFSTRUCT/普里姆算法辅助数组的定义VERTEXTYPEADJVEXVRTYPELOWCOSTCLOSEDGEMAX_VERTEX_NUMENDIF/结束IF322程序模块MGRAPHG/网G，唯一的全局变量INTMAININTARGC,CHARARGV/主函数STATUSLOCATEVEXMGRAPHG,VERTEXTYPEV/判断城市V在网G中的位置STATUSCREATEUDNMGRAPH/创建网G的邻接矩阵VOIDDISPLAYNETMGRAPHG/以邻接矩阵的形式显示网GVOIDMINISPANTREE_KRUSKALMGRAPHG/最小生成树的KRUSKAL算法VOIDMINISPANTREE_PRIMMGRAPHG,VERTEXTYPEU/最小生成树的PRIM算法STATUSMINIMUMCLOSEDGECLOSEEDGE,INTN/PRIM算法中求下一个城市的函数VOIDDELETEINFOMGRAPH/释放堆内存上动态申请的空间23流程图创建用邻接矩阵表示的城市道路网输入城市数GVEXNUM、道路数GARCNUM输入城市名GVEXSI输入表示道路的两个城市及道路值GARCSIJADJ返回OK231创建邻接矩阵的流程图NS图4PRIM算法化辅助数组CLOSEEDGEFORI1ICLOSEEDGEILOWCOST返回该城市在G中的位置四调试分析和测试结果41调试分析411邻接矩阵初始化本函数的主要功能是对无向网进行邻接矩阵的初始化。构造这种具有N个顶点和E条边的无向网时，关键需要考虑其时间复杂度O（NEN）,其中对邻接矩阵GARCS的初始化花费了O（N）的时间。412PRIM算法PRIM算法的思路是逐步将城市纳入生成树中，这里面的关键步骤是要找到下一个城市。于是通过讨教别人，写了STATUSMINIMUMCLOSEDGECLOSEEDGE,INTN函数，这样就可以在辅助数组中找到道路值最小的道路的两点城市了。742测试结果图421邻接矩阵初始化运行显示界面图422PRIM算法运行显示界面8五总结通过本周的课程设计，我们小组终于圆满完成了课程设计的任务，我也有不少收获。既巩固和加深了对数据结构的理解，认识到数据结构是计算机专业一门重要的专业技术基础课程，还提高了我综合运用本课程所学知识的能力。而且，并不是单纯的看看教材就能解决我们的实际问题，所以还要去查找各种我们所需要的资料，所以这次课程设计也培养了我选用参考书，查阅手册及文献资料的能力。要完成一个课程设计的课题并不是一次就能编译成功的，中间会出现很多的大问题小问题，改错是个很繁琐的问题。通过这次课程设计培养了我独立思考，深入研究，分析问题，解决问题的能力。在以后的学习过程中我将要注意以下几点1、认真上好专业实验课，多在实践中锻炼自己。2、写程序的过程要考虑周到，严密。3、在做设计的时候要有信心，有耐心，切勿浮躁。4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。六参考文献1严蔚敏，吴伟民数据结构（C语言版）清华大学出版社，20072谭浩强，张基温C语言程序设计教程（第三版）北京高等教育出版社，20063陈维新，林小茶C面向对象程序设计教程北京清华大学出版社，20044苏仕华等数据结构课程设计北京机械工业出版社，20059七致谢感谢梁英老师对我们数据结构课程及其实验的悉心指导，正是因为老师在实验课上的指导，让我能够把书本上的知识化成自己的知识，并运用在编程的过程中。感谢同学在我的设计过程中提出的宝贵意见，如果没有他们的帮助，我在设计过程中出现的一些错误可能无法迅速查出解决，你们的帮助为我节省了宝贵的时间。衷心感谢八附录/MAININCLUDEINCLUDEINCLUDEINCLUDEINCLUDE“TYPEDEFINEH“INCLUDE“ADJACENCYMATRIXH“INCLUDE“INITIALIZEFUNCTIONH“INCLUDE“MINISPANTREE_KRUSKALH“INCLUDE“MINISPANTREE_PRIMH“INCLUDE“DISPLAYNETH“INCLUDE“DELETEINFOH“MGRAPHG/全局变量G10INTMAININTARGC,CHARARGV/主函数STATUSLOCATEVEXMGRAPHG,VERTEXTYPEV/判断城市V在网G中的位置STATUSCREATEUDNMGRAPH/创建网G的邻接矩阵VOIDDISPLAYNETMGRAPHG/以邻接矩阵的形式显示网GVOIDMINISPANTREE_KRUSKALMGRAPHG/最小生成树的KRUSKAL算法VOIDMINISPANTREE_PRIMMGRAPHG,VERTEXTYPEU/最小生成树的PRIM算法STATUSMINIMUMCLOSEDGECLOSEEDGE,INTN/PRIM算法中求下一个城市的函数VOIDDELETEINFOMGRAPH/释放堆内存上动态申请的空间INTMAININTARGC,CHARARGVCREATEGRAPHGDISPLAYNETGMINISPANTREE_KRUSKALGMINISPANTREE_PRIMG,GVEXS0DELETEINFOGCOUTGVEXNUMGARCNUMFORI0IGVEXSIFORI0IV1V2W/输入一条边依附的顶点及权值13ILOCATEVEXG,V1/确定V1、V2在G中的位置JLOCATEVEXG,V2GARCSIJADJW/弧的权值GARCSJIGARCSIJ/置的对称弧RETURNOK/CREATEUDN/MINISPANTREEPRIMHSTATUSMINIMUMCLOSEDGECLOSEEDGE,INTNINTI,FLAG,MINTEMPINFINITYFORI0ICLOSEEDGEILOWCOSTMINTEMPCLOSEEDGEILOWCOSTFLAGIRETURNFLAGVOIDMINISPANTREE_PRIMMGRAPHG,VERTEXTYPEU/用普里姆算法从第U个顶点出发构造网G的最小生成树T，输出T的各条边。14/记录从顶点集U到VU的代价最小的边的辅助数组定义见“ADJACENCYMATRIXH“INTI,J,K,TOTALCOST0CLOSEDGECLOSEEDGEKLOCATEVEXG,UFORJ0J0,VIVUCOUT/输出生成树的边TOTALCOSTCLOSEEDGEK