资源描述：
《数据结构小学期-算法演示程序实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、实习报告实验名称：数据结构基本算法演示程序日期：2017年7月1日姓名：于博学号：班级：信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．输入1350122023
3、10三组点及权值。3．概要设计1)为了实现上述程序功能，需要定义树、线性表的抽象数据类型：ADTTree{数据对象：D={ai
4、ai∈IntegerSet,i=0,1,2,…,n,n≥0}数据关系：R={
5、ai,ai+1∈D}ADTLinkList{数据对象：D={ai
6、ai∈IntegerSet,i=0,1,2,…,n,n≥0}数据关系：R={
7、ai,ai+1∈D}基本操作：a)Prim算法ok(Tree&t,intk)初始条件：树结构已存在操作结果：作为判断函数的条件judge(Tree&t)
8、初始条件：树结构已存在操作结果：判断树是否包含所有图的结点show_prim()初始条件：树结构已存在，prim算法运行成功操作结果：展示prim算法,输出最小生成树a)Kruskal算法Find(intx)初始条件：图已存在操作结果：查寻父节点Union(intx,inty)初始条件：图已存在操作结果：合并结点boolCom(Nodex,Nodey)初始条件：图已存在操作结果：判断结点权值show_kruskal()初始条件：图已存在，kruskal算法运行成功操作结果：展示kruskal算法，输出各组成边b)Floyd算法F_C
9、reategraph(F_MGraph*F_MGraph)操作结果：创建图Floyd(F_MGraph*F_MGraph,int**iArrPath)初始条件：图已存在操作结果：运行弗洛伊德算法PrintResult(F_MGraph*F_MGraph,int**iArrPath)初始条件：图已存在操作结果：打印图的信息show_floyd()初始条件：图已存在，弗洛伊德算法运行成功操作结果：展示弗洛伊德算法c)Dijkstra算法createGraph(HeadNode*G,intnodeNum,intarcNum)操作结果：创建
10、图printGraph(HeadNode*G,intnodeNum)初始条件：图已存在操作结果：打印图getWeight(HeadNode*G,intbegin,intend)初始条件：图已存在操作结果：得到出发点到终点权重Dijkstra(HeadNode*G,intnodeNum,intbegin)初始条件：图已存在，出发点已知操作结果：运行迪杰斯特拉算法printPath(HeadNode*G,intend)初始条件：图已存，迪杰斯特拉算法运行成功操作结果：打印路径show_Dijkstra()初始条件：图已存，迪杰斯特拉算法
11、运行成功操作结果：展示迪杰斯特拉算法menu()操作结果：在屏幕上显示操作菜单2)本程序包含17个函数：主函数main()菜单函数menu()Prim算法判断函数ok()判断树是否包含所有图的结点judge()展示prim算法函数show_prim()Kruskal算法查寻父节点函数Find()合并结点函数Union()判断节点权值函数boolCom()展示kruskal算法函数show_kruskal()Floyd算法弗洛伊德创建图F_Creategraph()弗洛伊德算法函数Floyd()打印图信息函数PrintResult()
12、展示弗洛伊德函数show_floyd()Dijistra算法创建图createGraph()迪杰斯特拉算法函数Dijkstra()打印路径函数printPath()展示迪杰斯特拉函数show_Dijkstra()各函数间关系如下：4．
