资源描述：
《迷宫问题实验报告(c++编写,附源代码)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、迷宫问题实验报告级班年月日姓名学号_1．实验题目 以一个mXn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。2．需求分析本程序使用VC编写，实现设定迷宫或自动生成迷宫长方阵表的功能，并且求出一条从指定入口到指定出口的通路，或得出没有通路的结论。①输入的形式和输入值的范围：A.输入指定的数字，以此选择迷宫的创建方式，分为手动创建迷宫和自动创建迷宫B.输入迷宫阵表的行数和列数，行数和列数不超过40行C.手动创建迷宫时，需要输
2、入迷宫结点的通畅和障碍情况，0和1分别表示迷宫中的通路和障碍。②输出的形式：输出没有通路的结论，或者输出一个长方阵表，其中路径的每个结点都输出→、↓、←、↑之一，表示从当前结点到下一个结点的方向。③程序所能达到的功能：实现设定迷宫或自动生成迷宫长方阵表的功能，并且求出一条从指定入口到指定出口的通路（迷宫的入口指定为坐标为（1,1）的结点，迷宫的出口指定为坐标为（迷宫最大行,迷宫最大列）的结点），或得出没有通路的结论。④测试数据：输入数据：A．出现选择生成迷宫方式的菜单时，输入1（即手动输入数据，生成迷宫）；B
3、．输入迷宫的行数和列数，行数输入3，列数输入3；C．输入每个迷宫结点的信息：001100100输出结果：→↓11→↓1003．概要设计1)为了实现上述程序功能，需要定义迷宫的抽象数据类型： typedefstruct//定义迷宫结构体{intmaze_array[maxsize][maxsize];//二维数组存放迷宫每个点是通畅或阻隔的信息intmax_x,max_y;//迷宫的行数和和列数第19页，共19页}1)定义迷宫中点的指针的结构体typedefstructpoint{intvex_x,vex_y;
4、//结点的横纵坐标（横坐标为行号,纵坐标为列号）structpoint*ahead;//在链栈中，指向前一个结点的指针intdirection;//从当前结点走至下一个结点的方向}; 基本操作： A.Mazecreat_manual()初始条件：无 操作结果：手动创建一个迷宫。B.Mazecreat_automatic()初始条件：无操作结果：自动创建一个迷宫。 C.intfound(intx,inty,Point*head)初始条件：存在一个存放结点的链栈 操作结果：查找栈中是否有head指针内所含的坐
5、标；若含，则返回1，否则返回0。D.Point*find_road(Mazea)初始条件：存在一个迷宫操作结果：返回一条通路或者NULL E.voiddisplay(Point*po,Mazea)初始条件：存在一个迷宫操作结果：输出结果。程序包含6个函数： 主函数main() 手动创建一个迷宫Mazecreat_manual();自动创建一个迷宫Mazecreat_automatic();查找栈中是否有head指针内所含的坐标intfound(intx,inty,Point*head);迷宫寻路函数Poi
6、nt*find_road(Mazea);显示迷宫信息函数voiddisplay(Point*po,Mazea);各函数间关系如下：第19页，共19页主函数创建迷宫迷宫求解函数改变条件输出路径初始化符和条件？进栈找到出口？4．详细设计1)定义迷宫结构体typedefstruct{intmaze_array[maxsize][maxsize];//二维数组存放迷宫每个点是通畅或阻隔的信息intmax_x,max_y;//迷宫的行数和和列数}Maze;2)定义迷宫中点的指针的结构体typedefstructpoin
7、t{intvex_x,vex_y;//结点的横纵坐标（横坐标为行号,纵坐标为列号）structpoint*ahead;//在链栈中，指向前一个结点的指针intdirection;//从当前结点走至下一个结点的方向}Point;迷宫的基本操作如下3)Mazecreat_manual()//手动创建迷宫{第19页，共19页输入迷宫的行数和列数；依次输入各点的值；}1)Mazecreat_automatic()//自动创建迷宫{输入迷宫的行数和列数；随机产生各点的值；入口结点和出口结点赋值为0；打印迷宫；}2)in
8、tfound(intx,inty,Point*head){查找栈中是否有head指针内所含的坐标若含，则返回1；否则返回0}3)Point*find_road(Mazea)//迷宫寻路函数，返回一条通路或者NULL{intj,find,x,y;do{while(方向j<4){find=0；switch(j)//1234分别表示东南西北{case1:if(纵坐标加1后在迷宫内，且当前结点为0，且当前结
