迷宫求解细节.doc

《迷宫求解细节.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、需求分析1.选题理由本次课设我选择了迷宫问题，迷宫求解是数据结构课程的一个经典问题，迷宫问题要求寻找一条从入口到出口的路径。通常用的是“穷举求解”的方法。为了保证在任何位置上都能原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求解迷宫通路的算法中要应用“栈”的思想。对于栈的内容在整个学期的学习中我也有了一定的了解，所以选择了迷宫这一经典问题作为本次课设的内容。2.基本原理分析迷宫问题通常是用“穷举求解”方法解决，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前走；否则沿着

2、原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。栈是一个后进先出的结构，可以用来保存从入口到当前位置的路径。以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，在迷宫的四周加一圈障碍。对于迷宫任何一个位置，均约定东、南、西、北四个方向可通。3.功能要求（1）以一个二维数组Maze[m+2][n+2]表示迷宫，其中：Maze[0][j]和Maze[m+1][j](0<=j<=n+1)及Maze

3、[i][0]和Maze[i][n+1](0<=i<=m+1)为做外层的一圈障碍。数组中以0表示通路，1表示障碍，限定迷宫的大小为：m,n<=10。（2）用户需用文件的形式输入迷宫的数据：文件中第一行的数据为迷宫的行数m和列数n；从第2行至第m+1行（每行n个数）为迷宫值，用0，1输入，同行中的两个数字之间用空白字符相隔。（3）迷宫的入口位置和出口位置可由用户随时设定。（4）若设定的迷宫存在通路，则以长方阵形式将迷宫及其通路输出到标准输出文件上，其中字符“#”表示障碍，“*”表示路径，“@”表示曾途经该位置但不能到

4、达出口，其余位置用空格符表示。若设定迷宫不存在通路则报告相应信息（5）本程序只求出一条成功的通路。（6）程序执行的命令为：1，创建迷宫；2，求解迷宫；3，输出迷宫的解。一、详细设计源程序:#include#include#include#defineMAXLEN10//迷宫包括外墙最大行列数目#defineTRUE1#defineFALSE0#defineOK1#defineERROR0 typedefintStatus;//坐标位置类型 typedefs

5、truct{   intr,c;}PosType;//迷宫中r行c列的位置//迷宫类型 typedefstruct{    intr;    intc;    chararr[MAXLEN][MAXLEN];//可取'','*','@','#'}MazeType;   typedefstruct{//intstep;//当前位置在路径上的“序号”  PosTypeseat;//当前的坐标位置  intdi;//往下一坐标位置的方向}SElemType; //结点类型typedefstructNodeType{  

6、SElemTypedata;  NodeType*next;}NodeType,*LinkType;//栈类型 typedefstruct{  LinkTypetop;  intstacksize;}SqStack; PosTypestart;PosTypeend;MazeTypemaze;boolfound; //创建栈StatusInitStack(SqStack&S){  S.top=(LinkType)malloc(sizeof(NodeType));  S.top->next=NULL;  S.stac

7、ksize=0;  returnOK;} //进栈StatusPush(SqStack&S,SElemType&e){  LinkTypep;  p=(NodeType*)malloc(sizeof(NodeType));  p->data=e;  p->next=S.top;  S.top=p;  S.stacksize++;  returnOK;} //判断是否为栈空StatusStackEmpty(SqStackS){  if(S.top->next==NULL)returnOK;  returnERROR

8、;} //出栈StatusPop(SqStack&S,SElemType&e){  LinkTypep;  if(StackEmpty(S))returnERROR;  p=S.top;  e=p->data;  S.top=S.top->next;  S.stacksize--;  free(p);  returnOK;} //销毁栈StatusDestroyStack