迷宫系统课程设计报告.doc

设计题目：迷宫系统专业班级：计科一班小组成员: 赵大江（41012009） 赵春鹏（41012015） 沙娇（41012030） 李静（41012041） 2012-5-28 1、 问题描述：把一只老鼠从一个无顶盖的大盒子（迷宫）的入口处赶进迷宫。迷宫中设置了很多墙壁，对前进方向形成了多处障碍。在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以达到出口。如果从迷宫的入口到达出口，途中不出现行进方向错误，则得到一条最佳路线。我们利用非递归方法获得迷宫从入口到出口的最佳路线。二、需求分析： 【基本需求】（） 设置可选择的入口及出口，具有良好的界面以便用户操作。（） 自动生成迷宫，迷宫中用不同的符号标志代表墙壁和通路。（） 利用非递归算法实现，并输出有无通路两种情况下的迷宫路径，便于用户查看。 【简单分析】（1）本程序中定义了三个二维数组。一个迷宫数组，两个标记数组。对它们进行相同的初始化。int rowint colstruct point *nextstruct point（2）程序使用create()函数，系统自动创建一个大小确定的迷宫，该迷宫有a、b、c、d四个门。任何两个门之间是否存在路径不能确定，系统自动分配。 入口截图:（3） 输出的形式： 在有无通路时使用两种不同的标记路径方式，有通路时采用图形输出，无通路时则采用标记数组maze表示。 有通路的路径截图： 无通路的路径截图：三、概要设计：1、数据结构的设计首先，在寻找迷宫路径的时候,当走到某一位置而不能再前进时,就需要后退。因此，我们需要用“栈”的思想来满足这一要求。 其次，当成功找到路径时，我们需要用图形输出迷宫。在输出路径时每个点之间必须要有联系，所以我们又用了“链表”的思想。 最后, 结合以上两点,在本程序中,我们应用了“链式栈”的思想，用以解决存放迷宫路径以及输出路径的问题。2、算法的设计（） 创建迷宫： 用二维数组mazem+2n+2来表示迷宫矩阵，当数组元素mazeij=1时，表示该位置是墙壁, 不能通行；当数组元素mazeij=0时，表示该位置是通路。（1im）(1jn)数组的第行、第m+1行、第列、第n+1列是迷宫的围墙。 建立过程中调用库函数 rand()，产生随机数，从而自动生成迷宫。（） 路径查找：使用链式栈来存储在试探的过程中所走过的路径。一旦需要回退，可以从栈中取得刚才走过位置的坐标和前进方向。如果某个前进方向走不通，则将位于栈顶的活动记录退栈，使得在前进路径上回退一步，再尝试其他的允许方向，直至找到出口为止（有通路）。如果栈空则表示已经退回到开始位置（无通路）。（） 路径输出：有路径时，用标记数组mark输出。mark数组中各元素的值与迷宫数组maze完全相同,此时我们采用图形输出。具体算法如下所示： 假定p、q为指向point的指针，p指向当前位置，q指向下一位置。当 p-row q-row 时，输出；当 p-row row 时，输出；当 p-col q-col 时， 输出；当 p-col col 时， 输出；没有路径时，用标记数组maze输出。由于当没有找到通路时，栈内元素退栈并删除内存空间。因此，我们用maze数组来存放所有走过的点用以输出。（4） 主函数： 在该函数中，我们用了一个while循环贯穿整个函数。用于能够多次进行寻找迷宫路径。v 迷宫系统功能模块图 迷宫系统出 栈，释放空间无通路有通路无通路有通路调用库函数：rand()函数产生随机数输出模块：print 函数主函数：while 函数创建模块：create 函数路径查找：mazepath 函数调用create()mazepath()print()函数您是否还要再试一次系统自动创建生成四个门入栈k+，标记已访问再闯请输0否则请输1输 出，图形表示输 出，标记数组maze4、 详细设计：（1） 定义三元组结构：typedef struct pointint row ;int col;struct point *next;point;int markm+2n+2;int mazem+2n+2;（2） 成员函数流程图：1 创建迷宫：create()2 路径查找：mazepath()3 路径输出：print2()是创建迷宫：create()其中有四个for 嵌套循环，此处以第一个for循环为例 exit是否 i +; j+;mazeij=1;（迷宫数组）markij=1;（标记数组1）mazeij=1;（标记数组2）（对它们进行相同的初始化） j=n+1？ j=0;（maze 的列） inext =null？否入栈k+是出栈，释放空间已退到入口，释放空间出栈，结束循环 stackrow = =x2& stackcol = =y2?否return 0;是 return 1;是下一个标记数组用“ ”表示有两个路径输出函数，此流程图是有通路时的，流程图中的内容表示的是注释说明。否是路径输出：print2()下一个标记数组用“”表示下一个标记数组用 “ ”表示是是是否进入for 循环下一个标记数组用“ ”表示否否 p = pnext;pcol pnextcol?prow nextrow?prow pnextrow? pnext ! =null? point *p;p=stack; 开始（3）主函数流程图：开始进入while循环输出菜单输入相应命令否输入是否正确？是完成相应操作是是否再来？否结束五、实现与测试1.调试过程中遇到的问题(1)输出问题 问题解决前： 如上图所示，有图可发现迷宫中的通路不易查找；走过的路径标记不明显，而且也没有标记清楚走的过程。因此，在迷宫及路径输出时，我们通过图形输出，以达到标记走路径的过程。如下图所示： 问题解决后： (2)查找路径问题 问题解决前： 如上图所示，选定入口为a，出口为d。由图可以发现，在走的过程中，走法太过死板。因此，当选定入口和出口后，我们规定了判断上下左右四个方向的先后判断顺序。以减少走的步骤。如下图所示：问题解决后： 2.测试数据及输出结果 (1) 输入正确数据及输出的结果 有路径的情况 选择入口为a，出口为d。则结果如下图所示： 没有路径的情况 选择入口为c，出口为b。则结果如下图如所示： (2) 输入错误数据及输出的结果 3. 算法的时空分析及改进设想 时间复杂度：o（m*n）空间复杂度：不确定4. 源代码及运行结果#include #include #include #include #include time.h#define m 10#define n 10typedef struct point /定义三元组结构类 int row; /行int col; /列struct point *next; /前进方向 point;point* stack; /定义一个存储三元组的链式栈int markm+2n+2; int mazem+2n+2; /标记数组void create(int mazen+2)/建立迷宫int i,j;srand( (unsigned)time( null ) ); /产生随机种子for(i = 0;i = m+1;i+)for(j = 0;j = n+1;j+) mazeij = 1;markij = 1;mazeij = 1; for(i = 1;i = m;i+)for(j = 1;j = n;j+) mazeij = 0;markij = 0;mazeij = 0; int c,i1,j1;for(c = 1;c = m*n;c+) i1 = (int)(rand()%m)+1;j1 = (int)(rand()%n)+1; mazei1j1 = int(rand()%2);/随机矩阵,这样可以产生更多的0即通路 for(i = 1;i = m;i+)for(j = 1;j = n;j+)mazeij = markij = mazeij;maze11 = maze1n = mazem1 = mazemn = 0; maze10 = 10; maze1n+1 = 11;mazem0 = 12;mazemn+1 = 13; void print(int mazen+2) /打印迷宫 int i,j;coutn 迷宫endl;coutn (黑色为路，绿色为墙)endl;cout ;for(i = 0;i = m+1;i+)coutendl;cout ;for(j = 0;j = n+1;j+)if(mazeij = 0) cout ;if(mazeij = 1) cout;if(mazeij = 10) couta ;if(mazeij = 11) cout b;if(mazeij = 12) coutc ;if(mazeij = 13) coutrow = x1;p-col = y1;p-next = null;stack = p; /将入口放入链式栈mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标志入口已访问while(!(stack-row = null & stack-col = null) & (!(stack-row = x2 & stack-col = y2)/未找到出口并且栈不空if(mazestack-row+1stack-col = 0)/下面可通 p = new (point);p-row = stack-row+1;p-col=stack-col;p-next = stack; /入栈stack = p;mazestack-rowstack-col=mazestack-rowstack-col = k; k+;/标记已访问else if(mazestack-rowstack-col-1 = 0)/左面可通 p = new (point);p-row = stack-row;p-col = stack-col-1;p-next = stack; /入栈stack = p; mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标记已访问else if(mazestack-rowstack-col+1 = 0)/右面位置可通p = new (point);p-row = stack-row;p-col = stack-col+1;p-next = stack; /入栈stack = p; mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标记已访问else if(mazestack-row-1stack-col = 0)/上面可通p = new (point);p-row = stack-row-1;p-col = stack-col;p-next = stack; /入栈stack = p;mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标记已访问else /不可通 返回上一点if (stack-next != null)/栈里不止一个顶点则出栈并返回循环p = stack;stack = stack-next; /出栈delete p; /释放空间else /堆栈里只有一个顶点即入口，释放空间出堆栈结束循环 stack-row = null;stack-col = null;stack-next = null;if (stack-row = x2 & stack-col = y2) return 1;else return 0;else return 0; /a、celse if( x1 = 1 & y1 = 1 & x2 = 1 & y2 = n )point *p;int k = 2;if(mazex1y1 = 0)p = new (point);p-row = x1;p-col = y1;p-next = null;stack = p; /将入口放入链式栈mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标志入口已访问while(!(stack-row = null & stack-col = null) & (!(stack-row = x2 & stack-col = y2)/未找到出口并且栈不空if(mazestack-rowstack-col+1 = 0)/右面可通p = new (point);p-row = stack-row;p-col = stack-col+1;p-next = stack; /入栈stack = p;mazestack-rowstack-col= mazestack-rowstack-col = k; k+;/标记已访问else if(mazestack-row-1stack-col = 0)/上面可通p = new (point);p-row = stack-row-1;p-col = stack-col;p-next = stack; /入栈stack = p; mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标记已访问else if(mazestack-row+1stack-col = 0)/下面可通 p = new (point);p-row = stack-row+1;p-col = stack-col;p-next = stack; /入栈stack = p; mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标记已访问 else if(mazestack-rowstack-col-1 = 0)/左面可通p = new (point);p-row = stack-row;p-col = stack-col-1;p-next = stack; /入栈stack = p;mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标记已访问else /不可通 返回上一点if (stack-next != null)/栈里不止一个顶点则出栈并返回循环p = stack;stack = stack-next; /出栈delete p; /释放空间else /堆栈里只有一个顶点即入口，释放空间出堆栈结束循环 stack-row = null;stack-col = null;stack-next = null;if (stack-row = x2 & stack-col = y2) return 1;else return 0;else return 0; /a、belse if( x1 = 1 & y1 = 1 & x2 = m & y2 = n)point *p;int k = 2;if(mazex1y1 = 0)p = new (point);p-row = x1;p-col = y1;p-next = null;stack = p; /将入口放入链式栈mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标志入口已访问while(!(stack-row = null & stack-col = null) & (!(stack-row = x2 & stack-col = y2)/未找到出口并且栈不空if(mazestack-row+1stack-col = 0)/下面可通p = new (point);p-row = stack-row+1;p-col = stack-col;p-next = stack; /入栈stack = p;mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标记已访问else if(mazestack-rowstack-col+1 = 0)/右面可通p = new (point);p-row = stack-row;p-col = stack-col+1;p-next = stack; /入栈stack = p; mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标记已访问else if(mazestack-rowstack-col-1 = 0)/左面可通p = new (point);p-row = stack-row;p-col = stack-col-1;p-next = stack; /入栈stack = p; mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标记已访问else if(mazestack-row-1stack-col = 0)/上面可通p = new (point);p-row = stack-row-1;p-col = stack-col;p-next = stack; /入栈stack = p;mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标记已访问else /不可通 返回上一点if (stack-next != null)/栈里不止一个顶点则出栈并返回循环p = stack;stack = stack-next; /出栈delete p; /释放空间else /堆栈里只有一个顶点即入口，释放空间出堆栈结束循环 stack-row = null;stack-col = null;stack-next = null;if (stack-row = x2 & stack-col = y2) return 1;else return 0;else return 0; /a、delse if( x1 = 1 & y1 = n & x2 = m & y2 = 1)point *p;int k = 2;if(mazex1y1 = 0)p = new (point);p-row = x1;p-col = y1;p-next = null;stack = p; /将入口放入链式栈mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标志入口已访问while(!(stack-row = null & stack-col = null) & (!(stack-row = x2 & stack-col = y2)/未找到出口并且栈不空if(mazestack-rowstack-col-1 = 0)/左面可通p = new (point);p-row = stack-row;p-col = stack-col-1;p-next = stack; /入栈stack = p;mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标记已访问else if(mazestack-row+1stack-col = 0)/下面可通p = new (point);p-row = stack-row+1;p-col = stack-col;p-next = stack; /入栈stack = p; mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标记已访问else if(mazestack-rowstack-col+1 = 0)/右面可通p = new (point);p-row = stack-row;p-col = stack-col+1;p-next = stack; /入栈stack = p; mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标记已访问else if(mazestack-row-1stack-col = 0)/上面可通p = new (point);p-row = stack-row-1;p-col = stack-col;p-next = stack; /入栈stack = p;mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标记已访问else /不可通 返回上一点if (stack-next != null)/栈里不止一个顶点则出栈并返回循环p = stack;stack = stack-next; /出栈delete p; /释放空间else /堆栈里只有一个顶点即入口，释放空间出堆栈结束循环 stack-row = null;stack-col = null;stack-next = null;if (stack-row = x2 & stack-col = y2) return 1;else return 0;else return 0; /b、celse if( x1 = 1 & y1 = n & x2 = m & y2 = n)point *p;int k = 2;if(mazex1y1 = 0)p = new (point);p-row = x1;p-col = y1;p-next = null;stack = p; /将入口放入链式栈mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标志入口已访问while(!(stack-row = null & stack-col = null) & (!(stack-row = x2 & stack-col = y2)/未找到出口并且栈不空if(mazestack-row+1stack-col = 0)/下面可通p = new (point);p-row = stack-row+1;p-col = stack-col;p-next = stack; /入栈stack = p;mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标记已访问else if(mazestack-rowstack-col+1 = 0)/右面可通p = new (point);p-row = stack-row;p-col = stack-col+1;p-next = stack; /入栈stack = p;mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标记已访问else if(mazestack-rowstack-col-1 = 0)/左面可通p = new (point);p-row = stack-row;p-col = stack-col-1;p-next = stack; /入栈stack = p; mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标记已访问else if(mazestack-row-1stack-col = 0)/上面可通p = new (point);p-row = stack-row-1;p-col = stack-col;p-next = stack; /入栈stack = p;mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标记已访问else /不可通 返回上一点if (stack-next != null)/栈里不止一个顶点则出栈并返回循环p = stack;stack = stack-next; /出栈delete p; /释放空间else /堆栈里只有一个顶点即入口，释放空间出堆栈结束循环 stack-row = null;stack-col = null;stack-next = null;if (stack-row = x2 & stack-col = y2) return 1;else return 0;else return 0; /b、delse if(x1 = m & y1 = 1 & x2 = m & y2 = n)point *p;int k = 2;if(mazex1y1 = 0)p = new (point);p-row = x1;p-col = y1;p-next = null;stack = p; /将入口放入链式栈mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标志入口已访问while(!(stack-row = null & stack-col = null) & (!(stack-row = x2 & stack-col = y2)/未找到出口并且栈不空if(mazestack-rowstack-col+1 = 0)/右面可通p = new (point);p-row = stack-row;p-col = stack-col+1;p-next = stack; /入栈stack = p;mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标记已访问else if(mazestack-row+1stack-col = 0)/下面可通p = new (point);p-row = stack-row+1;p-col = stack-col;p-next = stack; /入栈stack = p; mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标记已访问else if(mazestack-row-1stack-col = 0)/上面可通p = new (point);p-row = stack-row-1;p-col = stack-col;p-next = stack; /入栈stack = p; mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标记已访问else if(mazestack-rowstack-col-1 = 0)/左面可通p = new (point);p-row = stack-row;p-col = stack-col-1;p-next = stack; /入栈stack = p;mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标记已访问else /不可通 返回上一点if (stack-next != null)/栈里不止一个顶点则出栈并返回循环p = stack;stack = stack-next; /出栈delete p; /释放空间else /堆栈里只有一个顶点即入口，释放空间出堆栈结束循环 stack-row = null;stack-col = null;stack-next = null;if (stack-row = x2 & stack-col = y2) return 1;else return 0;else return 0; /c、delse if( x1 = 1 & y1 = n & x2 = 1 & y2 = 1 )point *p;int k = 2;if(mazex1y1 = 0) p = new (point);p-row = x1;p-col = y1;p-next = null;stack = p; /将入口放入链式栈mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标志入口已访问while(!(stack-row = null & stack-col = null) & (!(stack-row = x2 & stack-col = y2)/未找到出口并且栈不空if(mazestack-rowstack-col-1 = 0)/左面可通p = new (point);p-row = stack-row;p-col = stack-col-1;p-next = stack; /入栈stack = p;mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标记已访问else if(mazestack-row-1stack-col = 0)/上面可通p = new (point);p-row = stack-row-1;p-col = stack-col;p-next = stack; /入栈stack = p; mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标记已访问else if(mazestack-row+1stack-col = 0)/下面可通p = new (point);p-row = stack-row+1;p-col = stack-col;p-next = stack; /入栈stack = p; mazestack-rowstack-col = mazestack-rowstack-col = k; k+;/标记已访问else if(mazestack-rowstack-col+1 = 0)/右面可通p = new (point);p-row