数据结构小学期-算法演示程序实验报告

石家庄铁道大学实习报告

实习报告

实验名称：数据结构基本算法演示程序 日期：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

石家庄铁道大学实习报告

4．详细设计

//------------------------------------------Prim算法--------------------------------------------------// //判断函数--是否树包含图的所有结点 void judge(Tree &t){

for(int i=1;i

for(int k=1;k<=t.v1;k++){ if(t.a[m][k]

biaoji1=t.a[m][k]; biaoji2=m; biaoji3=k; } } } }

t.v[i]=biaoji3; t.e[2*i-1]=biaoji2; t.e[2*i]=biaoji3; } }

//调用prim算法相关所有代码 void show_prim(){

cout<<\请输入图的点数和边数\输入提示 cin>>n>>m;

t.v1=n; //给树的结点总数和边的结点总数赋值 t.e1=m;

t.v=new int[n]; //结点数组 for(int i=0;i

t.e=new int[2*n-1]; //边与结点数的关系 for(int i=0;i<2*n-1;i++) //循环 初始化 t.e[i]=0; t.a=new int *[n+1]; for(int i=0;i<=n;i++) t.a[i]=new int[n+1];

cout<<\请依次输入各边的两端点及权值\ for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

t.a[i][j]=10000; //初始化为无穷大 for(int i=1;i<=m;i++){ //for循环输入

4 / 22

石家庄铁道大学实习报告

cin>>m1>>m2>>count;

t.a[m1][m2]=count; //无向网赋值 t.a[m2][m1]=count; }

judge(t); //判断是否有全部叶子节点 cout<<\最小生成树为：\ for(int i=1;i

cout<

cout<<\最小生成树的权值之和为：\}

//--------------------------------------kruskal算法------------------------------------------------------// int Find(int x){ // …… 此处隐藏：1464字，全部文档内容请下载后查看。喜欢就下载吧 ……