内容发布更新时间 : 2025/1/23 0:20:23星期一 下面是文章的全部内容请认真阅读。
迷宫问题实验报告
级 班 年 月 日 姓名 学号_
1.实验题目
以一个mXn的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。 2.需求分析
本程序使用VC编写,实现设定迷宫或自动生成迷宫长方阵表的功能,并且求出一条从指定入口到指定出口的通路,或得出没有通路的结论。
① 输入的形式和输入值的范围:
A.输入指定的数字,以此选择迷宫的创建方式,分为手动创建迷宫和自动创建迷宫 B. 输入迷宫阵表的行数和列数,行数和列数不超过40行
C. 手动创建迷宫时,需要输入迷宫结点的通畅和障碍情况,0和1分别表示迷宫中的通路和障碍。
② 输出的形式:输出没有通路的结论,或者输出一个长方阵表,其中路径的每个结点都输出→、↓、←、↑之一,表示从当前结点到下一个结点的方向。
③ 程序所能达到的功能:实现设定迷宫或自动生成迷宫长方阵表的功能,并且求出一条从指定入口到指定出口的通路(迷宫的入口指定为坐标为(1,1)的结点,迷宫的出口指定为坐标为(迷宫最大行,迷宫最大列)的结点),或得出没有通路的结论。
④ 测试数据: 输入数据:
A. 出现选择生成迷宫方式的菜单时,输入1(即手动输入数据,生成迷宫); B. 输入迷宫的行数和列数,行数输入3,列数输入3; C. 输入每个迷宫结点的信息: 0 0 1 1 0 0 1 0 0 输出结果: → ↓ 1 1 → ↓ 1 0 0
3.概要设计
1) 为了实现上述程序功能,需要定义迷宫的抽象数据类型:
typedef struct//定义迷宫结构体 {
int maze_array[maxsize][maxsize];//二维数组存放迷宫每个点是通畅或阻隔的信息
int max_x,max_y; //迷宫的行数和和列数
第 1页,共19页
}
2) 定义迷宫中点的指针的结构体
typedef struct point {
int vex_x,vex_y; //结点的横纵坐标(横坐标为行号,纵坐标为列号) struct point *ahead;//在链栈中,指向前一个结点的指针 int direction; //从当前结点走至下一个结点的方向 };
基本操作:
A. Maze creat_manual()
初始条件:无
操作结果:手动创建一个迷宫。
B. Maze creat_automatic() 初始条件:无
操作结果:自动创建一个迷宫。
C. int found(int x,int y,Point *head)
初始条件:存在一个存放结点的链栈 操作结果:查找栈中是否有head指针内所含的坐标;若含,则返回1,否则返回0。 D. Point * find_road(Maze a) 初始条件:存在一个迷宫
操作结果:返回一条通路或者NULL
E. void display(Point *po,Maze a)
初始条件:存在一个迷宫 操作结果:输出结果。
程序包含6个函数:
1主函数main() ○
2手动创建一个迷宫 Maze creat_manual(); ○
3自动创建一个迷宫 Maze creat_automatic(); ○
4查找栈中是否有head指针内所含的坐标 int found(int x,int y,Point *head); ○
5迷宫寻路函数 Point * find_road(Maze a); ○
6显示迷宫信息函数 void display(Point *po,Maze a); ○
各函数间关系如下:
第 2页,共19页
主函数
创建迷宫 初始化 迷宫求解函数 改变条件 找到出口? 符和条件? 进栈 输出路径
4.详细设计
1) 定义迷宫结构体
typedef struct {
int maze_array[maxsize][maxsize];
//二维数组存放迷宫每个点是通畅或阻隔的信息
int max_x,max_y; //迷宫的行数和和列数 }Maze;
2) 定义迷宫中点的指针的结构体
typedef struct point {
int vex_x,vex_y; //结点的横纵坐标(横坐标为行号,纵坐标为列号) struct point *ahead;//在链栈中,指向前一个结点的指针 int direction; //从当前结点走至下一个结点的方向 }Point;
迷宫的基本操作如下
3) Maze creat_manual()//手动创建迷宫
{
输入迷宫的行数和列数;
第 3页,共19页