数据结构深度与广度优先搜索：迷宫问题

1、数据结构深度与广度优先搜索：迷宫问题膻熾工摩院数据结构课程设计深度与广度优先搜索：迷宫问题数据结构课程设计一深度与广度优先搜索:迷宫问题数据结构课程设计一深度与广度优先搜索:迷宫问题 #Xxxxxxxxxxx专业学生姓名班级学号数据结构课程设计数据结构课程设计6设计小结127参考文献6设计小结127参考文献目录优先搜索：迷宫问题1设计题目TOC o 1-5 h z2设计分析1 HYPERLINK l bookmark6 o Current Document 3设计实现34测试方法341测试目的842测试输入843正确输岀944实际输出9 HYPERLINK l bookmark4 o Curr

2、ent Document 45错误原因115分析与探讨1151测试结果分析1152探讨与改进11数据结构课程设计一深度与广度优先搜索:迷宫问题数据结构课程设计一深度与广度优先搜索:迷宫问题 1设计题目a）迷宫问题求解的目标：寻找一条从入口点到出口点的通路。（迷宫可表示为一个二维平面图形，将迷宫的左上角作入口，右下角作出口。）例如，可以设计一个8*8矩阵maze88来表示迷宫，如下所示：0100001100010010101010111010110101111110100110001010001110110100左下角maze00为起点，右下角maze77为终点；设“0”为通路，“1”为墙，既无

3、法穿越。假设一只老鼠从起点出发，目的为右下角终点，可向“上、下、左、右、左上、左下、右上、右下”8个方向行走。b）设计程序要求：能自动生成或者手动生成这样一个8*8矩阵；针对这个矩阵,程序判断是否能从起点经过迷宫走到终点。如果不能，请指出；如果能，请用图形界面标出走出迷宫的路径。2设计分析a）首先明确题目中的已知条件：迷宫是一个8*8大小的矩阵。从迷宫的左上角进入，右下角为迷宫的终点。mazeij=0代表第i+1行第j+1列的点是通路；mazeij=1代表该点是墙，无法通行。迷宫有两种生成方式：手工设定和自动生成。当老鼠处于迷宫中某一点的位置上，它可以向8个方向前进，分别是：“上、下、左、右、

4、左上、左下、右上、右下”8个方向。要实现这个程序，首先要考虑如何表示这个迷宫。在实例程序中使用二维数组mzeN+2N+2来表示这个迷宫，其中N为迷宫的行、列数。当值为“0”时表示该点是通路，当值为“1”时表示该点是墙。老鼠在迷宫中的位置在任何时候都可以用行号row和列号col表示。b）为什么指定mazeN+2N+2表示迷宫，而不是使用mazeNN来表示迷宫？原因是当老鼠跑到迷宫的边界点时就有可能跳出迷宫;而使用mazeN+2N+2就可以把迷宫的外面再包一层“1”，这样就能阻止老鼠走出格。c）老鼠再每一点都有8种方向可以走，分别是：North，NorthEast9East,SoutbEast9E

5、ast9South,SouthWest,West9NorthWest.可以用数组move8来表示在每一个方向上的横纵坐标的偏移量，见表21。根据这个数组，就很容易计算出沿某个方向行走后的下一点的坐标。NamedirMovedir.vertMovedir.horizN0-10NE1-11E201SE311S410SW51-1W60-1NW60-1表218种方向move的偏移量d）迷宫问题可以用深度优先搜索方法实现。当老鼠当老鼠在迷宫中移动的时候，可能会有多种移动选择方向。程序需要记录并用栈来保存当前点的坐标，然后任意选取一个方向进行移动。由于应用栈保存了当前通道上各点的坐标，所以当前各方向上都走

6、不通时可以返回上一个点，然后选择另一个方向前进。可定义element结构用于存储每一步的横纵坐标和方向。typedefstructshortintrow;shortintcol;shortintdir;element;ElementstackMAX_STACK_SIZE;根据表21可推算出每次移动后的坐标。设当前的坐标是（row,col）,移动的方向是dir，移动后的点是nextj则有next_row=row+movedir.vert;next_col=col+movedir.horiz;可用另一个二维数组markN+2来记录哪些点已经被访问过。当经过点mazerowcol时，相应地将mark

7、rowcol的值从0置为1。本程序支持自动生成迷宫。利用random(2)函数可随机产生0或1,来支持迷宫的自动生成。注意mazeNN和maze11定要等于0,因为他们分别是起点和终点。如果找到了一条走出迷宫的路径，则需要在屏幕中打印出走出迷宫的信息。这里要用到graphics.h。为画出效果图，可使用circle。函数画圆，outtexttxy()函数标记文字，并用line()函数来划线。程序的主要函数如下：.函数voidadd(int*top,elementitem)，将当前步的信息item压入到作为全局变量的栈stack(栈顶为top)中。函数elementdelete(int*top)

8、，返回stack中栈顶的元素。函数voidpath(void)，采用深度优先搜索算法，首先取出栈顶元素作为当前点选择一个方向前进到下一个点(如果能走得话)；然后，将下一个点压入栈，并将二维数组mark中对应的值改为1，表示该点已经走到了。反复执行上面两步，当走到一个点不能再走下去了(已经尝试了各个方向并失败)，并且这个点不是终点，则这个点的上一个点会从栈中被跑抛出，从而“回朔”到上一点；当遇到终点时，程序结束，找到一条路径；当在程序循环过程中遇到栈为空，则说明该迷宫根本无法走到终点。3设计实现/*ThisprogramcanbecompiledunderVC6.0*/#include#incl

9、ude8N*N/*最大栈容量*/10#include#include#include#defineN#defineMAX_STACK_SIZE#defineTRUE#defineFALSE#defineLEN(300/N)/*结构体记录每一步的横坐标，纵坐标和方向*/typedefstructshortintrow;shortintcol;数据结构课程设计一深度与广度优先搜索:迷宫问题数据结构课程设计一深度与广度优先搜索:迷宫问题 #shortintdir;element;elementstackMAX_STACK_SIZE;/*结构体记录水平和垂直的偏移量*/typedefstructshortintvert;shortinthoriz;offsets;offsetsmove8;intmazeN+2N+2;intmarkN+2N+2;/*8个方向的move*/*二维数组记录迷宫*/*记录迷宫中每点是否可到达*/intEXIT_ROW=N,EXIT_COL=N;/*在栈中加入一个元素*/voidadd(int*top,elementitem)if(*top=MAX_STACK_SIZE-1)printf(Thestackisfull!n);return;stack+*top=item;/*返回栈中顶部的元素*/elementdelete_top(int*top)if(*top