迷宫问题实验报告(c++编写-附源代码)(共19页)

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

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

3、1) 为了实现上述程序功能，需要定义迷宫的抽象数据类型：typedef struct/定义迷宫结构体int maze_arraymaxsizemaxsize;/二维数组存放迷宫每个点是通畅或阻隔的信息int max_x,max_y; /迷宫的行数和和列数2) 定义迷宫中点的指针的结构体typedef struct point int vex_x,vex_y; /结点的横纵坐标（横坐标为行号,纵坐标为列号）struct point *ahead;/在链栈中，指向前一个结点的指针int direction; /从当前结点走至下一个结点的方向;基本操作： A. Maze creat_manual()

4、初始条件：无 操作结果：手动创建一个迷宫。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个函数：主函数main()手动创建一个迷宫 Maz

5、e creat_manual();自动创建一个迷宫 Maze creat_automatic();查找栈中是否有head指针内所含的坐标 int found(int x,int y,Point *head);迷宫寻路函数 Point * find_road(Maze a);显示迷宫信息函数 void display(Point *po,Maze a);各函数间关系如下：主函数创建迷宫迷宫求解函数改变条件输出路径初始化符和条件？进栈找到出口？4详细设计1) 定义迷宫结构体typedef struct int maze_arraymaxsizemaxsize;/二维数组存放迷宫每个点是通畅或阻隔的

6、信息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()/手动创建迷宫输入迷宫的行数和列数；依次输入各点的值；4) Maze creat_automatic()/自动创建迷宫 输入迷宫的行数和列数； 随机产生各点的值； 入口结

7、点和出口结点赋值为0；打印迷宫；5) int found(int x,int y,Point *head) 查找栈中是否有head指针内所含的坐标 若含，则返回1；否则返回06) Point * find_road(Maze a)/迷宫寻路函数，返回一条通路或者NULL int j,find,x,y;do while(方向j<4) find=0； switch(j)/1234分别表示东南西北 case 1:if(纵坐标加1后在迷宫内，且当前结点为0，且当前结点没有在栈中出现) 当前结点进栈； 把方向j赋予当前结点方向； find=1;break; case 2: if(横坐标加1后在迷宫

8、内，且当前结点为0，且当前结点没有在栈中出现) 当前结点进栈； 把方向j赋予当前结点方向； find=1;break；case 3: if(纵坐标减1后在迷宫内，且当前结点为0，且当前结点没有在栈中出现) 当前结点进栈； 把方向j赋予当前结点方向； find=1;break；case 4: if(横标减1后在迷宫内，且当前结点为0，且当前结点没有在栈中出现) 当前结点进栈； 把方向j赋予当前结点方向； find=1;break;if(find=1) j+;break;else 方向加1，即换方向;if(j>4) if(栈顶前一个结点不为空) 当前结点出栈且方向加1else return

9、NULL;while(当前结点不是出口) return top;7) void display(Point *po,Maze a)/输出结果int i,j,top=0;Point *stackmaxsize;if(指针=NULL)cout<<"没有找到迷宫通路！"<<endl;elsewhile(指针!=NULL)/通过一个栈将链栈逆序stacktop+=指针;po指针指向前一个结点;cout<<"迷宫通道如下："<<endl;while(top>1)将栈中的通路所含结点的方向值加10top-;a.m

10、aze_array当前新栈中所存的行坐标当前新栈中所存的列坐标=新栈中当前结点到下一个结点的方向+10;/11、12、13、14分别为东、南、西、北 for(i=1;i<=行最大值;i+)/打印迷宫 for(j=1;j<=列最大值;j+)if(结点值<=1)cout<<结点值<<" "else/根据结点内所存储的方向值，对应输出四个方向的箭头之一，指示从该结点到下一个结点的方向switch(结点值)case 东:输出->； break; case 南: 输出；break; case 西: 输出<- ；break; cas

11、e 北: 输出；break; 5调试分析通过本试验我对链栈有了更深入的了解。在编写程序的过程中，我们更容易发现问题所在，对算法有更深会的理解。判断方向的转变使其不会重复走过的路经，这个比较麻烦，当时也不知道如何不让迷宫走“回头路”，只能是查资料，和同学讨论，最终找到了解决办法。6使用说明程序名为：迷宫.exe，运行环境为DOS。程序执行后显示请选择手动或自动生成迷宫1.手动生成迷宫2.自动生成迷宫输入数字选择执行不同的功能。输入1，使用手动生成迷宫功能；输入2，使用自动生成迷宫功能；输入其他数字，则提示输入错误，需要重新输入数字选择功能，直至输入的数字为1或2为止。输入其他数字后，输出的画面如

12、下：您输入的数值有误，请重新输入请选择手动或自动生成迷宫1.手动生成迷宫2.自动生成迷宫输入1后，接着输入迷宫的行数和列数，最后出现如下画面此时请依次输入每个结点的值，其中入口和出口必须输入0：接着程序会输出迷宫通路或者是没有通路的信息使用自动创建迷宫功能时，只需输入行数和列数，接着程序会输出迷宫通路或者是没有通路的信息7测试结果1) 5X5迷宫，没路的情况，输入和输出如下所示：2) 5X5迷宫，有通路情况，输入和输出如下所示：3) 4X3迷宫，没路情况，输入和输出如下所示： 4) 4X3迷宫，有路情况，输入和输出如下所示：源代码如下：# include <iostream>usi

13、ng namespace std;#include<time.h>#include<stdlib.h># define maxsize 20typedef struct/定义迷宫结构体int maze_arraymaxsizemaxsize;/二维数组存放迷宫每个点是通畅或阻隔的信息int max_x,max_y; /迷宫的行数和和列数Maze;typedef struct point/定义迷宫中点的指针的结构体int vex_x,vex_y; /结点的横纵坐标（横坐标为行号,纵坐标为列号）struct point *ahead;/在链栈中，指向前一个结点的指针int

14、direction; /从当前结点走至下一个结点的方向Point;Maze creat_manual()/手动创建迷宫int i,j;Maze temp;cout<<"请输入迷宫的行数: "cin>>temp.max_x;cout<<"请输入迷宫的列数: "cin>>temp.max_y; cout<<"迷宫的入口和出口已经指定；"<<endl;cout<<"迷宫的入口结点坐标为（1,1），输入该结点的值时，请输入0。"<&l

15、t;endl;cout<<"迷宫的出口结点坐标为"<<"（"<<temp.max_x<<","<<temp.max_y<<"）"<<"，输入该结点的值时，请输入0。"<<endl;cout<<"结点值为0表示通畅，值为1表示阻隔"<<endl<<endl;for(i=1;i<=temp.max_x;i+)cout<<"

16、请输入迷宫第"<<i<<"行各点的值："for(j=1;j<=temp.max_y;j+)cin>>temp.maze_arrayij;cout<<endl;return temp;Maze creat_automatic()/自动创建迷宫int i,j;Maze temp;cout<<"请输入迷宫的行数: "cin>>temp.max_x;cout<<"请输入迷宫的列数: "cin>>temp.max_y;unsigned

17、 int t;t=time(NULL)%1000;srand(t);/产生随机数种子for(i=1;i<=temp.max_x;i+)for(j=1;j<=temp.max_y;j+)temp.maze_arrayij=rand()%2;temp.maze_array11=0;/迷宫入口置值为0temp.maze_arraytemp.max_xtemp.max_x=0;/迷宫出口置值为0，否则程序不能正常运行for(i=1;i<=temp.max_x;i+)/打印迷宫for(j=1;j<=temp.max_y;j+)cout<<temp.maze_array

18、ij<<" "cout<<endl;cout<<endl;return temp;int found(int x,int y,Point *head)/查找栈中是否有head指针内所含的坐标；若含，则返回1，否则返回0Point *p=head;while(p!=NULL)if(x=p->vex_x&&y=p->vex_y)return 1;p=p->ahead;return 0;Point * find_road(Maze a)/迷宫寻路函数，返回一条通路或者NULLPoint *top,*p;/top

19、为栈的栈顶指针int j,find,x,y;p=(Point *)malloc(sizeof(Point);p->ahead=NULL;p->vex_x=1;p->vex_y=1;top=p;j=1;/j为方向，1、2、3、4分别为东、南、西、北dowhile(j<=4)find=0;/find判断是否为符合条件的结点，若有为1，没有为0 x=p->vex_x;y=p->vex_y;switch(j) case 1: if(y+1<=a.max_x&&!a.maze_arrayxy+1&&!found(x,y+1,top

20、) /若纵坐标加1后，在迷宫范围内；且该结点为0；且该结点没有在链栈中出现，则当前结点加入链栈 p=(Point *)malloc(sizeof(Point); p->vex_x=x; p->vex_y=y+1; p->ahead=top; top->direction=j;/从上一结点至该结点的方向，存放在上一结点的结点指针内 top=p; find=1; break; case 2: if(x+1<=a.max_x&&!a.maze_arrayx+1y&&!found(x+1,y,top) p=(Point *)malloc(s

21、izeof(Point); p->vex_x=x+1; p->vex_y=y; p->ahead=top; top->direction=j; top=p; find=1; break; case 3: if(y-1>=1&&!a.maze_arrayxy-1&&!found(x,y-1,top) p=(Point *)malloc(sizeof(Point); p->vex_x=x; p->vex_y=y-1; p->ahead=top; top->direction=j; top=p; find=1; b

22、reak; case 4: if(x-1<=1&&!a.maze_arrayx-1y&&!found(x-1,y,top) p=(Point *)malloc(sizeof(Point); p->vex_x=x-1;p->vex_y=y;p->ahead=top; top->direction=j; top=p; find=1; break; if(find=1)/若找到符合条件的结点，则j赋值为1，然后退出内层while循环 j=1;break; else j+; /若没有，j加1if(j>4)/4个方向都找不到符合条件的结

23、点时 if(top->ahead!=NULL)/若top不为空，则出栈，上一个结点的方向j加1p=p->ahead;top=p;/使栈顶结点指向前一个节点，原节点删除j=top->direction+1;top->direction=j;else return NULL;/若top为空，则返回NULLwhile(top->vex_x!=a.max_x | top->vex_y!=a.max_y);/若果当前结点不是出口，则继续进行do-while循环return top;void display(Point *po,Maze a)/输出结果int i,j,t

24、op=0;Point *stackmaxsize;if(po=NULL)cout<<"没有找到迷宫通路！"<<endl;elsewhile(po!=NULL)/通过一个栈将链栈逆序stacktop+=po;po=po->ahead;cout<<"迷宫通道如下："<<endl;while(top>1)/出口结点值为0，无方向，不需要把方向赋值给该结点top-;a.maze_arraystacktop->vex_xstacktop->vex_y=stacktop->direction+10;/把迷宫通路走的方向赋值给迷宫中相应的结点/11、12、13、14分别为东、南、西、北 for(i=1;i<=a.max_x;i+)/打印迷宫 for(j=1;j<=a.max_y;j+)if(a.maze_arrayij<=1)cout<<a.maze_arrayij<<" "else/根据结点内所存储的方向值，对应输出四个方向的箭头之一，指示从该结点到下一个结点的方向switch(a.m