石家庄铁道大学实习报告
实习报告
实验名称：数据结构基本算法演示程序 日期：2017年7月1 日 姓名：于博 学号：20153236 班级：信1501-2 指导教师：陈娜
1．实验题目
1) Prim 算法 输入：无向图（顶点序列，边序列）
功能要求：输出最小生成树的各组成边及最小生成树的权值 2) Kruskal 算法 输入：无向图（顶点序列，边序列） 功能要求：输出最小生成树的各组成边及最小生成树的权值 3) Floyd 算法 输入：有向图（顶点序列，有向边序列） 功能要求：输出各顶点对间最短路径和路径长度 4) Dijkstra 算法
输入：有向图（顶点序列，有向边序列），起始顶点
功能要求：输出起始顶点到其它各顶点的最短路径和路径长度
2．需求分析
本演示程序用C++编写，完成四个算法的实现, Prim 算法，Kruskal 算法，Floyd 算法，Dijkstra 算法
① 输入的形式和输入值的范围： 整数，菜单项是1至5，其他输入根据图的实际情况。 ② 输出的形式：输出最小生成树，树的各组成边，所有路径及源点到其他点的所有最短路径。
③ 程序所能达到的功能：四个算法Prim 算法，Kruskal 算法，Floyd 算法，Dijkstra 算法的实现。
④ 测试数据：
A． 输入3个点，3条边。
B． 输入1 3 50 1 2 20 2 3 10三组点及权值。
3．概要设计
1) 为了实现上述程序功能，需要定义树、线性表的抽象数据类型： ADT Tree{
数据对象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0} 数据关系：R={
数据对象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0} 数据关系：R={
初始条件：树结构已存在
操作结果：作为判断函数的条件
1 / 22
石家庄铁道大学实习报告
judge(Tree &t)
初始条件：树结构已存在
操作结果：判断树是否包含所有图的结点 show_prim()
初始条件：树结构已存在，prim算法运行成功 操作结果：展示prim算法,输出最小生成树 b) Kruskal 算法 Find(int x)
初始条件：图已存在 操作结果：查寻父节点 Union(int x,int y) 初始条件：图已存在 操作结果：合并结点 bool Com(Node x,Node y) 初始条件：图已存在 操作结果：判断结点权值 show_kruskal()
初始条件：图已存在，kruskal算法运行成功 操作结果：展示kruskal算法，输出各组成边 c) Floyd 算法
F_Creategraph(F_MGraph *F_MGraph) 操作结果：创建图
Floyd(F_MGraph *F_MGraph, int **iArrPath) 初始条件：图已存在
操作结果：运行弗洛伊德算法
PrintResult(F_MGraph *F_MGraph, int **iArrPath) 初始条件：图已存在 操作结果：打印图的信息 show_floyd()
初始条件：图已存在，弗洛伊德算法运行成功 操作结果：展示弗洛伊德算法 d) Dijkstra 算法
createGraph(HeadNode *G, int nodeNum, int arcNum) 操作结果：创建图
printGraph(HeadNode *G, int nodeNum) 初始条件：图已存在 操作结果：打印图
getWeight(HeadNode *G, int begin, int end) 初始条件：图已存在
操作结果：得到出发点到终点权重
Dijkstra(HeadNode *G, int nodeNum, int begin) 初始条件：图已存在，出发点已知 操作结果：运行迪杰斯特拉算法 printPath(HeadNode *G, int end)
2 / 22
石家庄铁道大学实习报告
初始条件：图已存，迪杰斯特拉算法运行成功 操作结果：打印路径 show_Dijkstra()
初始条件：图已存，迪杰斯特拉算法运行成功 操作结果：展示迪杰斯特拉算法 menu()
操作结果：在屏幕上显示操作菜单 2) 本程序包含 17个函数： 主函数 main() 菜单函数menu() Prim算法 判断函数ok()
判断树是否包含所有图的结点judge() 展示prim算法函数show_prim() Kruskal算法
查寻父节点函数Find() 合并结点函数Union()
判断节点权值函数bool Com()
展示kruskal算法函数show_kruskal() Floyd算法
弗洛伊德创建图F_Creategraph() 弗洛伊德算法函数Floyd() 打印图信息函数PrintResult() 展示弗洛伊德函数show_floyd() Dijistra算法
创建图createGraph()
迪杰斯特拉算法函数Dijkstra () 打印路径函数printPath()
展示迪杰斯特拉函数show_Dijkstra() 各函数间关系如下：
3 / 22