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

沈阳航空航天大学 课 程 设 计 报 告 课程设计名称：数据结构课程设计 课程设计题目：PRIM算法求最小生成树 院（系）：计算机学院 专 业：计算机科学与技术 班 级： 学 号： 姓 名： 指导教师：  目 录 1 需求分析 1 1.1 题目内容及要求 1 1.2 题目分析 1 2 系统设计 2 2.1数据结构设计 2 2.2函数设计 3 2.3关键流程 4 2.3.1系统流程 4 2.3.2 PRIM 函数流程 4 2.3.3 Huitu函数流程 5 2.3.4 GraphicVer函数输出邻接矩阵 6 3 调试分析 7 3.1 调试初期 7 3.2调试中期 7 3.3 调试后期 7 4 测试及运行结果 9 4.1 欢迎界面 9 4.2获取输入，绘制无向图 10 4.3 输出邻接矩阵 13 4.4 PRIM算法生成最小生成树 14 4.5 用户退出 15 参考文献 16 附 录（关键部分程序清单） 17 1 需求分析 1.1 题目内容及要求 本次课程设计的题目是用PRIM算法实现最小生成树的演示过程。内容要求以合适的方式输入一个边带权值的无向图，要求输入无向图的方式尽量简单方便。采用合适的存储结构存储该无向图，然后根据PRIM算法求该无向图的最小生成树，并且能够形象地演示PRIM算法求最小生成树的过程。 1.2 题目分析 本次课程设计共有三点要求，分别是以合适方便的方式输入一个边带权值的无向图，采用合适的存储结构存储该无向图，用PRIM算法求该无向图的最小生成树。在无向图的输入上要求能够形象演示，该功能的实现还要求输入方式尽量简单方便，即通过图象来演示，此功能的实现只能使用TC环境来实现。存储该无向图时要使用正确的存储结构，因为课程设计的目的在于演示，并不是用于实际，所以从稳定性方面考虑，我选择了邻接矩阵作为此次无向图的存储结构，最后是PRIM算法求最小生成树，此功能的实现比较简单，只要有前两者很好的铺垫，此功能的实现就变的比较轻松。以上即为本人对此次课程设计题目的分析。2 系统设计 2.1数据结构设计 任何一个程序都是由算法和数据结构组成的，算法是程序的灵魂，但没有数据结构这个载体，灵魂也实现不了自己的价值。所以数据结构设计也是程序设计环节中很重要的部分。 图主要有邻接矩阵和邻接表两种存储结构。邻接表以一个一维数组作表头节点存储图的顶点，然后利用表头引出所有以该点为箭尾的邻接边的信息；而邻接矩阵则是单独建立一个一维数组来存储顶点的信息，并以顶点的个数来建立一个相应的N阶对称矩阵，以二维数组存储单元来存储相应边的权值。 由于PRIM算法需要多次修改closeedge[ ]中的adjvex和lowcost 值，且此次数据规模较小，只需达到演示部分数据即可，所以统一采用数组的存储结构，即亦采用邻接矩阵的存储结构来存储无向带权图更利于实现及操作。 邻接矩阵的抽象数据结构定义： #define INFINITY INT_MAX //最大值 #define MAX_ERTEX_NUM 20 //最大顶点数 typedef enum { DG , DN , UDG , UDN }GraphKind; //{ 有向图，有向网，无向网，无向图} typedef struct Arc Cell { VRType adj ; // VRType 是顶点关系的类型。对无权图，用1和0 //表示相邻否；对带权图则为权值类型 InfoType * info; //该弧相关信息的指针 }ArcCell ，AdjMatrix [ MAX_VERTEX_NUM][MAX_VERTEX_NUM]； Typedef struct { VertexType vexs [ MAX_VERTEX_NUM] ; //顶点向量 AdjMatrix arcs ; // 邻接矩阵 int vexnum , arcnum ; //图的当前顶点数和弧数 GraphKind kind ; // 图的种类标志 }Mgraph ; 2.2函数设计 本系统所使用的函数见表2.1 表2.1 本系统所使用的函数 函数名称 函数原型 功能描述 main() int main(void) 系统调用主函数 Huitu() Void Huitu () 绘制无向图 GraphicVer() void GraphicVer(Graph *G) 输出邻接矩阵 prim() v