迷宫问题实验报告(c++编写-附源代码)13909.pdf

《迷宫问题实验报告(c++编写-附源代码)13909.pdf》由会员分享，可在线阅读，更多相关《迷宫问题实验报告(c++编写-附源代码)13909.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、迷宫问题实验报告 级 班 年 月 日 姓名 学号_ 1实验题目 以一个 mXn 的长方阵表示迷宫，0 和 1 分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。2需求分析 本程序使用 VC 编写，实现设定迷宫或自动生成迷宫长方阵表的功能，并且求出一条从指定入口到指定出口的通路，或得出没有通路的结论。输入的形式和输入值的范围：A.输入指定的数字，以此选择迷宫的创建方式，分为手动创建迷宫和自动创建迷宫 B.输入迷宫阵表的行数和列数，行数和列数不超过40 行 C.手动创建迷宫时，需要输入迷宫结点的通畅和障碍情况，0 和 1 分别表示迷宫中的

2、通路和障碍。输出的形式：输出没有通路的结论，或者输出一个长方阵表，其中路径的每个结点都输出、之一，表示从当前结点到下一个结点的方向。程序所能达到的功能：实现设定迷宫或自动生成迷宫长方阵表的功能，并且求出一条从指定入口到指定出口的通路（迷宫的入口指定为坐标为（1,1）的结点，迷宫的出口指定为坐标为（迷宫最大行,迷宫最大列）的结点），或得出没有通路的结论。测试数据：输入数据：A 出现选择生成迷宫方式的菜单时，输入1（即手动输入数据，生成迷宫）；B 输入迷宫的行数和列数，行数输入3，列数输入 3；C 输入每个迷宫结点的信息：0 0 1 1 0 0 1 0 0 输出结果：1 1 1 0 0 3概要设计

3、 为了实现上述程序功能，需要定义迷宫的抽象数据类型：typedef structMaze 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,M

4、aze 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);各函数间关系如下：主函数 创建迷宫 迷宫求解函数 改变条件 输出路径 初始化 符和条件 进栈 找到出口 4详细设计

5、 1)定义迷宫结构体 typedef struct int maze_arraymaxsizemaxsize;xe，运行环境为 DOS。程序执行后显示 请选择手动或自动生成迷宫 1.手动生成迷宫 2.自动生成迷宫 输入数字选择执行不同的功能。输入 1，使用手动生成迷宫功能；输入 2，使用自动生成迷宫功能；输入其他数字，则提示输入错误，需要重新输入数字选择功能，直至输入的数字为 1 或 2为止。输入其他数字后，输出的画面如下：您输入的数值有误，请重新输入 请选择手动或自动生成迷宫 1.手动生成迷宫 2.自动生成迷宫 输入 1 后，接着输入迷宫的行数和列数，最后出现如下画面 此时请依次输入每个结点

6、的值，其中入口和出口必须输入 0：接着程序会输出迷宫通路或者是没有通路的信息 使用自动创建迷宫功能时，只需输入行数和列数，接着程序会输出迷宫通路或者是没有通路的信息 7测试结果 1)5X5 迷宫，没路的情况，输入和输出如下所示：2)5X5 迷宫，有通路情况，输入和输出如下所示：3)4X3 迷宫，没路情况，输入和输出如下所示：4)4X3 迷宫，有路情况，输入和输出如下所示：源代码如下：#include using namespace std;#include#include#define maxsize 20 typedef struct 动生成迷宫endl;cout2.自动生成迷宫selection;while(selection!=1&selection!=2)cout您输入的数值有误，请重新输入endl;cout请选择手动或自动生成迷宫endl;cout1.手动生成迷宫endl;cout2.自动生成迷宫selection;if(selection=1)a=creat_manual();else a=creat_automatic();po=find_road(a);display(po,a);getchar();getchar();