资源描述：
《数据结构小学期-算法演示程序实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、实习报告实验名称：数据结构基本算法演示程序日期：2017年7月1日姓名：于博学号：20153236班级：信1501-2指导教师：陈娜1.实验题目1）Prim算法输入：无向图（顶点序列，边序列）功能要求：输出最小生成树的各组成边及最小生成树的权值2）Kruskal算法输入：无向图（顶点序列，边序列）功能要求：输出最小生成树的各组成边及最小生成树的权值3）Floyd算法输入：有向图（顶点序列，有向边序列）功能要求：输出各顶点对间最短路径和路径长度4）Dijkstra算法输入：有向图（顶点序列，有向边序列），起始顶点功能要求：输出起始顶点到其它各顶点的最短路径和路径长度
2、2.需求分析本演示程序用C++编写，完成四个算法的实现，Prim算法，Kruskal算法，Floyd算法，Dijkstra算法①输入的形式和输入值的范围：整数，菜单项是1至5,其他输入根据图的实际情况。②输出的形式：输出最小生成树，树的各组成边，所有路径及源点到其他点的所有最短路径。③程序所能达到的功能：四个算法Prim算法，Kruskal算法，Floyd算法，Dijkstra算法的实现。④测试数据：A.输入3个点，3条边。B.输入135012202310三组点及权值。3.概要设计1）为了实现上述程序功能，需要定义树、线性表的抽象数据类型：ADTTree{数据对象
3、：D={ai
4、aiIntegerSet,i=0,1,2,•••,n,n0}数据关系：R={
5、ai,ai+lWD}ADTLinkList{数据对象:D={ai
6、aiWIntegerSet,i=0,1,2,•••,n,n>0}数据关系：R={
7、ai,ai+lWD}基本操作：a）Prim算法ok（Treek）初始条件：树结构已存在操作结果：作为判断函数的条件judge(Tree&t)初始条件：树结构已存在操作结果：判断树是否包含所有图的结点show_prim()初始条件：树结构已存在，prim算法运行成功操作结果：展示prim算法，输
8、出最小生成树b)Kruskal算法Find(intx)初始条件：图己存在操作结果：查寻父节点Union(intx,inty)初始条件：图已存在操作结果：合并结点boolCom(Nodex,Nodey)初始条件：图已存在操作结果：判断结点权值show_kruskal()初始条件：图已存在，kruskal算法运行成功操作结果：展示kruskal算法，输出各组成边c)Floyd算法F_Creategraph(F_MGraph*F_MGraph)操作结果：创建图Floyd(F_MGraph*F_MGraph,int**iArrPath)初始条件：图己存在操作结果：运行弗洛
9、伊德算法PrintResult(F_MGraph*F_MGraph,int**iArrPath)初始条件：图已存在操作结果：打印图的信息show_floyd()初始条件：图已存在，弗洛伊德算法运行成功操作结果：展示弗洛伊德算法d)Dijkstra算法createGraph(HeadNode*G,intnodeNum,intarcNum)操作结果：创建图printGraph(HeadNode*GintnodeNum)初始条件：图已存在操作结果：打印图getWeight(HeadNode*G,intbegin,intend)初始条件：图已存在操作结果：得到ns发点到终
10、点权重Dijkstra(HeadNode*GintnodeNum,intbegin)初始条件：图已存在，出发点已知操作结果：运行迪杰斯特拉算法printPath(HeadNode*Gintend)初始条件：图已存，迪杰斯特拉算法运行成功操作结果：打印路径show_Dijkstra()初始条件：图已存，迪杰斯特拉算法运行成功操作结果：展示迪杰斯特拉算法menu()操作结果：在屏幕上显示操作菜单2)本程序包含17个函数：主函数main()菜单函数menuOPrim算法判断函数ok()判断树是否包含所有图的结点judge()展示prim算法函数show_prim()Kr
11、uskal算法查寻父节点函数Find()合并结点函数Union。判断节点权值函数boolCom()展示kruskal算法函数show_kruskal()Floyd算法弗洛伊德创建图F_Creategraph()弗洛伊德算法函数Floyd()打印图信息函数PrintResult()展示弗洛伊德函数show_floyd()Dijistra算法创建图createGraph()迪杰斯特拉算法函数Dijkstra()打印路径函数printPath()展示迪杰斯特拉函数show_Dijkstra()各函数间关系如下：okamainMnenujudgesFin"Union卜1b
12、oolCo
