内容发布更新时间 : 2024/12/26 10:06:41星期一 下面是文章的全部内容请认真阅读。

石家庄铁道大学实习报告

实习报告

实验名称：数据结构基本算法演示程序 日期：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={|ai,ai+1 ∈D} ADT LinkList{

数据对象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0} 数据关系：R={|ai,ai+1 ∈D} 基本操作： a) Prim算法 ok(Tree &t,int k)

初始条件：树结构已存在

操作结果：作为判断函数的条件

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