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

第1页，共19页迷宫问题实验报告级班年月日姓名学号_1．实验题目以一个mXn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。2．需求分析本程序使用VC编写，实现设定迷宫或自动生成迷宫长方阵表的功能，并且求出一条从指定入口到指定出口的通路，或得出没有通路的结论。①输入的形式和输入值的范围：A.输入指定的数字，以此选择迷宫的创建方式，分为手动创建迷宫和自动创建迷宫B.输入迷宫阵表的行数和列数，行数和列数不超过40行C.手动创建迷宫时，需要输入迷宫结点的通畅和障碍情况，0和1分别表示迷宫中的通路和障碍。②输出的形式：输出没有通路的结论，或者输出一个长方阵表，其中路径的每个结点都输出→、↓、←、↑之一，表示从当前结点到下一个结点的方向。③程序所能达到的功能：实现设定迷宫或自动生成迷宫长方阵表的功能，并且求出一条从指定入口到指定出口的通路（迷宫的入口指定为坐标为（1,1）的结点，迷宫的出口指定为坐标为（迷宫最大行,迷宫最大列）的结点），或得出没有通路的结论。④测试数据：输入数据：A．出现选择生成迷宫方式的菜单时，输入1（即手动输入数据，生成迷宫）；B．输入迷宫的行数和列数，行数输入3，列数输入3；C．输入每个迷宫结点的信息：001100100输出结果：→↓11→↓1003．概要设计1)为了实现上述程序功能，需要定义迷宫的抽象数据类型：typedefstruct//定义迷宫结构体{intmaze_array[maxsize][maxsize];//二维数组存放迷宫每个点是通畅或阻隔的信息intmax_x,max_y;//迷宫的行数和和列数第2页，共19页}2)定义迷宫中点的指针的结构体typedefstructpoint{intvex_x,vex_y;//结点的横纵坐标（横坐标为行号,纵坐标为列号）structpoint*ahead;//在链栈中，指向前一个结点的指针intdirection;//从当前结点走至下一个结点的方向};基本操作：A.Mazecreat_manual()初始条件：无操作结果：手动创建一个迷宫。B.Mazecreat_automatic()初始条件：无操作结果：自动创建一个迷宫。C.intfound(intx,inty,Point*head)初始条件：存在一个存放结点的链栈操作结果：查找栈中是否有head指针内所含的坐标；若含，则返回1，否则返回0。D.Point*find_road(Mazea)初始条件：存在一个迷宫操作结果：返回一条通路或者NULLE.voiddisplay(Point*po,Mazea)初始条件：存在一个迷宫操作结果：输出结果。程序包含6个函数：○1主函数main()○2手动创建一个迷宫Mazecreat_manual();○3自动创建一个迷宫Mazecreat_automatic();○4查找栈中是否有head指针内所含的坐标intfound(intx,inty,Point*head);○5迷宫寻路函数Point*find_road(Mazea);○6显示迷宫信息函数voiddisplay(Point*po,Mazea);各函数间关系如下：第3页，共19页4．详细设计1)定义迷宫结构体typedefstruct{intmaze_array[maxsize][maxsize];//二维数组存放迷宫每个点是通畅或阻隔的信息intmax_x,max_y;//迷宫的行数和和列数}Maze;2)定义迷宫中点的指针的结构体typedefstructpoint{intvex_x,vex_y;//结点的横纵坐标（横坐标为行号,纵坐标为列号）structpoint*ahead;//在链栈中，指向前一个结点的指针intdirection;//从当前结点走至下一个结点的方向}Point;迷宫的基本操作如下3)Mazecreat_manual()//手动创建迷宫{输入迷宫的行数和列数；主函数创建迷宫迷宫求解函数改变条件输出路径初始化符和条件？进栈找到出口？第4页，共19页依次输入各点的值；}4)Mazecreat_automatic()//自动创建迷宫{输入迷宫的行数和列数；随机产生各点的值；入口结点和出口结点赋值为0；打印迷宫；}5)intfound(intx,inty,Point*head){查找栈中是否有head指针内所含的坐标若含，则返回1；否则返回0}6)Point*find_road(Mazea)//迷宫寻路函数，返回一条通路或者NULL{intj,find,x,y;do{while(方向j4){find=0；switch(j)//1234分别表示东南西北{case1:if(纵坐标加1后在迷宫内，且当前结点为0，且当前结点没有在栈中出现){当前结点进栈；把方向j赋予当前结点方向；find=1;}break;case2:if(横坐标加1后在迷宫内，且当前结点为0，且当前结点没有在栈中出现){当前结点进栈；把方向j赋予当前结点方向；第5页，共19页find=1;}break；case3:if(纵坐标减1后在迷宫内，且当前结点为0，且当前结点没有在栈中出现){当前结点进栈；把方向j赋予当前结点方向；find=1;}break；case4:if(横标减1后在迷宫内，且当前结点为0，且当前结点没有在栈中出现){当前结点进栈；把方向j赋予当前结点方向；find=1;}break;}if(find==1){j++;break;}else方向加1，即换方向;}if(j4){if(栈顶前一个结点不为空){当前结点出栈且方向加1}elsereturnNULL;}}while(当前结点不是出口)returntop;第6页，共19页7)voiddisplay(Point*po,Mazea)//输出结果{inti,j,top=0;Point*stack[maxsize];if(指针==NULL)cout没有找到迷宫通路！endl;else{while(指针!=NULL)//通过一个栈将链栈逆序{stack[top++]=指针;po指针指向前一个结点;}cout迷宫通道如下：endl;while(top1)将栈中的通路所含结点的方向值加10{top--;a.maze_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;case北:输出↑；break;}}}}}第7页，共19页5．调试分析通过本试验我对链栈有了更深入的了解。在编写程序的过程中，我们更容易发现问题所在，对算法有更深会的理解。判断方向的转变使其不会重复走过的路经，这个比较麻烦，当时也不知道如何不让迷宫走“回头路”，只能是查资料，和同学讨论，最终找到了解决办法。6．使用说明程序名为：迷宫.exe，运行环境为DOS。程序执行后显示请选择手动或自动生成迷宫1.手动生成迷宫2.自动生成迷宫输入数字选择执行不同的功能。输入1，使用手动生成迷宫功能；输入2，使用自动生成迷宫功能；输入其他数字，则提示输入错误，需要重新输入数字选择功能，直至输入的数字为1或2为止。输入其他数字后，输出的画面如下：您输入的数值有误，请重新输入请选择手动或自动生成迷宫1.手动生成迷宫2.自动生成迷宫输入1后，接着输入迷宫的行数和列数，最后出现如下画面此时请依次输入每个结点的值，其中入口和出口必须输入0：接着程序会输出迷宫通路或者是没有通路的信息使用自动创建迷宫功能时，只需输入行数和列数，接着程序会输出迷宫通路或者是没有通路的信息第8页，共19页7．测试结果1)5X5迷宫，没路的情况，输入和输出如下所示：2)5X5迷宫，有通路情况，输入和输出如下所示：3)4X3迷宫，没路情况，输入和输出如下所示：4)4X3迷宫，有路情况，输入和输出如下所示：第9页，共19页源代码如下：#includeiostreamusingnamespacestd;#includetime.h#includestdlib.h#definemaxsize20typedefstruct//定义迷宫结构体{intmaze_array[maxsize][maxsize];//二维数组存放迷宫每个点是通畅或阻隔的信息intmax_x,max_y;//迷宫的行数和和列数}Maze;typedefstructpoint//定义迷宫中点的指针的结构体{intvex_x,vex_y;//结点的横纵坐标（横坐标为行号,纵坐标为列号）structpoint*ahead;//在链栈中，指向前一个结点的指针intdirection;//从当前结点走至下一个结点的方向}Point;Mazecreat_manual()//手动创建迷宫{inti,j;Mazetemp;cout请输入迷宫的行数:;第10页，共19页cintemp.max_x;cout请输入迷宫的列数:;cintemp.max_y;cout迷宫的入口和出口已经指定；endl;cout迷宫的入口结点坐标为（1,1），输入该结点的值时，请输入0。endl;cout迷宫的出口结点坐标为（temp.max_x,temp.max_y），输入该结点的值时，请输入0。endl;cout结点值为0表示通畅，值为1表示阻隔endlendl;for(i=1;i=temp.max_x;i++){cout请输入迷宫第i行各点的值：;for(j=1;j=temp.max_y;j++)cintemp.maze_array[i][j];}coutendl;returntemp;}Mazecreat_automatic()//自动创建迷宫{inti,j;Mazetemp;cout请输入迷宫的行数:;cintemp.max_x;第11页，共19页cout请输入迷宫的列数:;cintemp.max_y;unsignedintt;t=time(NULL)%1000;srand(t);//产生随机数种子for(i=1;i=temp.max_x;i++){for(j=1;j=temp.max_y;j++){temp.maze_array[i][j]=rand()%2;}}temp.maze_array[1][1]=0;//迷宫入口置值为0temp.maze_array[temp.max_x][temp.max_x]=0;//迷宫出口置值为0，否则程序不能正常运行for(i=1;i=temp.max_x;i++)//打印迷宫{for(j=1;j=temp.max_y;j++){couttemp.maze_array[i][j];}coutendl;}第12页，共19页coutendl;returntemp;}intfound(intx,inty,Point*head)//查找栈中是否有head指针内所含的坐标；若含，则返回1，否则返回0{Point*p=head;while(p!=NULL){if(x==p-vex_x&&y==p-vex_y)return1;p=p-ahead;}return0;}Point*find_road(Mazea)//迷宫寻路函数，返回一条通路或者NULL{Point*top,*p;//top为栈的栈顶指针intj,find,x,y;p=(Point*)malloc(sizeof(Poi