数据结构课程设计报告--PRIM算法求最小生成树

《数据结构课程设计报告--PRIM算法求最小生成树》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、沈阳航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：PRIM算法求最小生成树院（系）：计算机学院专业：计算机科学与技术班级：学号：姓名：指导教师：沈阳航空航天大学课程设计报告目录1需求分析11.1题目内容及要求11.2题目分析12系统设计22.1数据结构设计22.2函数设计32.3关键流程42.3.1系统流程42.3.2PRIM函数流程42.3.3Huitu函数流程52.3.4GraphicVer函数输出邻接矩阵63调试分析73.1调试初期73.2调试中期73.3调试后期74测试及运行结果94.1欢迎界面94.2获取输入，绘制无向图1

2、04.3输出邻接矩阵134.4PRIM算法生成最小生成树144.5用户退出15参考文献16附录（关键部分程序清单）1722沈阳航空航天大学课程设计报告22沈阳航空航天大学课程设计报告1需求分析1.1题目内容及要求本次课程设计的题目是用PRIM算法实现最小生成树的演示过程。内容要求以合适的方式输入一个边带权值的无向图，要求输入无向图的方式尽量简单方便。采用合适的存储结构存储该无向图，然后根据PRIM算法求该无向图的最小生成树，并且能够形象地演示PRIM算法求最小生成树的过程。1.2题目分析本次课程设计共有三点要求，分别是以合适方便的方式输入一个边带权值的无

3、向图，采用合适的存储结构存储该无向图，用PRIM算法求该无向图的最小生成树。在无向图的输入上要求能够形象演示，该功能的实现还要求输入方式尽量简单方便，即通过图象来演示，此功能的实现只能使用TC环境来实现。存储该无向图时要使用正确的存储结构，因为课程设计的目的在于演示，并不是用于实际，所以从稳定性方面考虑，我选择了邻接矩阵作为此次无向图的存储结构，最后是PRIM算法求最小生成树，此功能的实现比较简单，只要有前两者很好的铺垫，此功能的实现就变的比较轻松。以上即为本人对此次课程设计题目的分析。22沈阳航空航天大学课程设计报告2系统设计2.1数据结构设计任何一个

4、程序都是由算法和数据结构组成的，算法是程序的灵魂，但没有数据结构这个载体，灵魂也实现不了自己的价值。所以数据结构设计也是程序设计环节中很重要的部分。图主要有邻接矩阵和邻接表两种存储结构。邻接表以一个一维数组作表头节点存储图的顶点，然后利用表头引出所有以该点为箭尾的邻接边的信息；而邻接矩阵则是单独建立一个一维数组来存储顶点的信息，并以顶点的个数来建立一个相应的N阶对称矩阵，以二维数组存储单元来存储相应边的权值。由于PRIM算法需要多次修改closeedge[]中的adjvex和lowcost值，且此次数据规模较小，只需达到演示部分数据即可，所以统一采用数组

5、的存储结构，即亦采用邻接矩阵的存储结构来存储无向带权图更利于实现及操作。邻接矩阵的抽象数据结构定义：#defineINFINITYINT_MAX//最大值#defineMAX_ERTEX_NUM20//最大顶点数typedefenum{DG,DN,UDG,UDN}GraphKind;//{有向图，有向网，无向网，无向图}typedefstructArcCell{VRTypeadj;//VRType是顶点关系的类型。对无权图，用1和0//表示相邻否；对带权图则为权值类型InfoType*info;//该弧相关信息的指针}ArcCell，AdjMatrix[

6、MAX_VERTEX_NUM][MAX_VERTEX_NUM]；22沈阳航空航天大学课程设计报告Typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数GraphKindkind;//图的种类标志}Mgraph;2.2函数设计本系统所使用的函数见表2.1表2.1本系统所使用的函数函数名称函数原型功能描述main()intmain(void)系统调用主函数Huitu()VoidHuitu()绘制无向图Graphic

7、Ver()voidGraphicVer(Graph*G)输出邻接矩阵prim()voidprim(Graph*G)PRIM算法演示本系统所调用函数调用的关系见图2.2图2.2本系统的函数调用关系22沈阳航空航天大学课程设计报告2.3关键流程流程图能直观和系统地把主函数的各个执行步骤和调用的子函数以及调用先后表示出来，子函数中也有调用其他子函数的情况，画出子函数的流程图能清楚地看出子函数中各步语句的执行，下面是关于主函数流程和关键的子函数流程图的直观表示。2.3.1系统流程图2.3系统函数流程2.3.2PRIM函数流程图2.4PRIM函数流程22沈阳航空航

8、天大学课程设计报告2.3.3Huitu函数流程图2.5Huitu函数流程22沈阳