数据结构实验报告四

1、甘肃政法学院本科生实验报告（）姓名:学院:专业:班级:13级实验课程名称:数据结构实验日期:2014年5月30日指导教师及职称:实验成绩:开课时间： 2013-2014学年 第二学期甘肃政法学院实验管理中心印制实验题目树形结构小组合作否姓名班级学 号一、实验目的8.1实现图的邻接矩阵和邻接表储存8.2实现图的遍历算法8.3求所有深度优先遍历序列8.4用图搜索方法求解迷宫问题8.5求有向图的简单路径8.6求无向图的深度优先生成树和广度优先生成树8.7用普利姆算法求最小生成树8.8采用克鲁斯卡尔算法求最小生成树8.9采用狄克斯特拉算法求有向带权图的最短路径8.10采用弗洛伊德算法求有向带权图的最短

2、路径二实验环境安装了Windows7操作系统，并且安装了Microsoft Visual C+ 6.0。三、实验内容与步骤1、安装Microsoft Visual C+ 6.0。2打开Microsoft Visual C+ 6.0四实验过程：8.1实现图的邻接矩阵和邻接表储存编写一个程序algo8-1，实现不带权图和带权图的邻接矩阵与邻接表的相互转化算法、输出邻接矩阵与邻接表的运算并在此基础上设计一个主程序完成如下功能：（1） 建立如图所示的有向G邻接矩阵，并输出之；（2） 由有向图G的邻接矩阵产生邻接表，并输出之；（3） 再由（2）的邻接表产生相应的邻接矩阵，并输出之新建工程选择“Hello

3、，world！程序”选择Fileview复制algo8-1和Graph到工程文件中。把主文件大开，用exp8-1的内容覆盖到主文件由于main（）函数被重复定义所以需要备注，把algo8-1中主函数备注掉，并且手动引入#include“algo8-1.cpp”。运行程序，如下图：输入代码如下：8.2实现图的遍历算法编写一个程序algo8-2，实现实现图的遍历算法并在此基础上设计一个exp8-2.cpp程序完成如下功能：（1） 输出有向图G从丁丁点0开始的深度优先遍历序列(递归算法)（2） 输出有向图G从丁丁点0开始的深度优先遍历序列(非递归算法)（3） 输出有向图G从丁丁点0开始的广度优先遍历

4、序列（4） 新建工程选择“Hello，world！程序”选择Fileview复制algo8-1和algo8-2和Graph到工程文件中。把主文件大开，用exp8-2的内容覆盖到主文件由于main（）函数被重复定义所以需要备注，把algo8-1中主函数备注掉，并且手动引入#include“algo8-1.cpp” 和#include“algo8-2.cpp”。运行程序，如下图：输入代码如下：8.3求所有深度优先遍历序列编写一个程序algo8-3，采用邻接表存储图。新建工程选择“Hello，world！程序”选择Fileview复制algo8-1和Graph到工程文件中。把主文件大开，用exp8-

5、3的内容覆盖到主文件由于main（）函数被重复定义所以需要备注，把algo8-1中主函数备注掉，并且手动引入#include“algo8-1.cpp” 。运行程序，如下图：输入程序如下：8.4用图搜索方法求解迷宫问题设计一个程序，实现如下功能：（1）建立教程所示迷宫对应的邻接表表示。（2）采用深度优先遍历输出所有迷宫的路径。 新建工程选择“Hello，world！程序”选择Fileview复制algo8-1和Graph到工程文件中。把主文件大开，用exp8-4的内容覆盖到主文件由于main（）函数被重复定义所以需要备注，把algo8-1中主函数备注掉，并且手动引入#include“algo8-

6、1.cpp”运行程序，如下图：输入程序如下：8.5求有向图的简单路径编写一个程序exp8-5，实现如下功能： （1）输出所示的有线图G从顶点5到顶点2的所有路径： （2）输出所示的有线图G从顶点5到顶点2的所有长度为3的路径： （3）输出所示的有线图G从顶点5到顶点2的最短路径： 新建工程选择“Hello，world！程序”选择Fileview复制algo8-1和Graph到工程文件中。把主文件大开，用exp8-5的内容覆盖到主文件由于main（）函数被重复定义所以需要备注，把algo8-1中主函数备注掉，并且手动引入#include“algo8-1.cpp” 运行程序，如下图：输入代码如下：

7、8.6求无向图的深度优先生成树和广度优先生成树编写一个程序algo8-2，输出所示的有线图G从顶点3出发深度优先生成树和广度优先生成树。新建工程选择“Hello，world！程序”选择Fileview复制algo8-1和 Graph到工程文件中。把主文件大开，用exp8-6的内容覆盖到主文件由于main（）函数被重复定义所以需要备注，把algo8-1中主函数备注掉，并且手动引入#include“algo8-1.cpp” 程运行序，如下图：输入程序如下：8.7用普利姆算法求最小生成树编写一个程序设计一个算法对所示无限带权图G,采用普利姆算法输出从顶点0出发的最小生成树新建工程选择“Hello，w

8、orld！程序”选择Fileview复制algo8-1和Graph到工程文件中。把主文件大开，用exp8-7的内容覆盖到主文件由于main（）函数被重复定义所以需要备注，把algo8-1中主函数备注掉，并且手动引入#include“algo8-1.cpp” 。运行程序，如下图：输入程序如下：8.8采用克鲁斯卡尔算法求最小生成树编写一个程序所示无限带权图G,采用克鲁斯卡尔算法输出从顶点0出发的最小生成树新建工程选择“Hello，world！程序”选择Fileview复制algo8-1和Graph到工程文件中。把主文件大开，用exp8-8的内容覆盖到主文件由于main（）函数被重复定义所以需要备注

9、，把algo8-1中主函数备注掉，并且手动引入#include“algo8-1.cpp”运行程序，如下图：输入程序如下：8.9采用狄克斯特拉算法求有向带权图的最短路径编写一个程对所示无限带权图G,采用克鲁斯卡尔算法输出从顶点0的最短路径的长度和最短路径。新建工程选择“Hello，world！程序”选择Fileview复制algo8-1和Graph到工程文件中。把主文件大开，用exp8-9的内容覆盖到主文件由于main（）函数被重复定义所以需要备注，把algo8-1中主函数备注掉，并且手动引入#include“algo8-1.cpp” 运行程序，如下图：输入程序如下：8.10采用弗洛伊德算法求有向带权图的最短路径编写一个程序对所示无限带权图G,采用弗洛伊德算法输出从顶点0的最短路径的长度和最短路径。新建工程选择“Hello，world！程序”选择Fileview复制algo8-1和Graph到工程文件中。把主文件大开，用exp8-10的内容覆盖到主文件。由于main（）函数被重复定义所以需要备注，把algo8-1中主函数备注掉，并且手动引入#include“algo8-1.cpp” 运行程序，如下图：输入程序如下：五、实验故障在实验一中就出现了问题，始终调试不出来。显示错误为：后来经过反反复复的调试才发现是我没把graph添加到