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

设计题目：迷宫系统专业班级：计科一班小组成员: 赵大江（41012009） 赵春鹏（41012015） 沙娇（41012030） 李静（41012041） 2012-5-28 一、 问题描述：把一只老鼠从一个无顶盖的大盒子（迷宫）的入口处赶进迷宫。迷宫中设置了很多墙壁，对前进方向形成了多处障碍。在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以达到出口。如果从迷宫的入口到达出口，途中不出现行进方向错误，则得到一条最佳路线。我们利用非递归方法获得迷宫从入口到出口的最佳路线。二、需求分析：Ø 【基本需求】（） 设置可选择的入口及出口，具有良好的界面以便用户操作。（） 自动生成迷宫，迷宫中用不同的符号标志代表墙壁和通路。（） 利用非递归算法实现，并输出有无通路两种情况下的迷宫路径，便于用户查看。Ø 【简单分析】（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 < q->row 时，输出；当 p->col > q->col 时， 输出；当 p->col < q->col 时， 输出；没有路径时，用标记数组maze输出。由于当没有找到通路时，栈内元素退栈并删除内存空间。因此，我们用maze数组来存放所有走过的点用以输出。（4） 主函数： 在该函数中，我们用了一个while循环贯穿整个函数。用于能够多次进行寻找迷宫路径。v 迷宫系统功能模块图 迷宫系统出 栈，释放空间无通路有通路无通路有通路调用库函数：rand()函数产生随机数输出模块：print 函数主函数：while 函数创建模块：create 函数路径查找：Mazepath 函数调用create()Mazepath()print()函数您是否还要再试一次系统自动创建生成四个门入栈K+，标记已访问再闯请输0否则请输1输 出，图形表示输 出，标记数组maze四、 详细设计：（1） 定义三元组结构：Typedef struct Pointint row ;int col;struct Point *next;Point;int markM+2N+2;int mazeM+2N+2;（2） 成员函数流程图： 创建迷宫：create() 路径查找：Mazepath() 路径输出：print2()是创建迷宫：create()其中有四个for 嵌套循环，此处以第一个for循环为例 exit是否 i +; j+;Mazeij=1;（迷宫数组）markij=1;（标记数组1）mazeij=1;（标记数组2）（对它们进行相同的初始化） j<=N+1？ j=0;（Maze 的列） i<=M+1? i=0;（Maze 的行） 开始否 开始查找路径：Mazepath()此流程图以A为入口，D为出口为例。里的内容表示的是注释说明。 Point *p;int K=2;Mazex1y1= = 0?否是 将入口放入链式栈Y否未找到出口并且栈不空？ 左面位置可通？是是否 下面位置可通？是是否 右面位置可通？否是 上面位置可通？ 退回到上一结点否stack>next =NULL？否入栈K+是出栈，释放空间已退到入口，释放空间出栈，结束循环 stack>row = =x2&& stack>col = =y2?否return 0;是 return 1;是下一个标记数组用“ ”表示有两个路径输出函数，此流程图是有通路时的，流程图中的内容表示的是注释说明。否是路径输出：print2()下一个标记数组用“”表示下一个标记数组用 “ ”表示是是是否进入for 循环下一个标记数组用“ ”表示否否 p = p>next;p>col > p>next>col?p>row < p>next>row?p>row > p>next>row? p>next ! =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 <iostream.h>#include <Windows.h>#include <stdio.h>#include <iomanip.h>#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;cout<<"n 迷宫"<<endl;cout<<"n (黑色为路，绿色为墙)"<<endl;cout<<" "for(i = 0;i <= M+1;i+)cout<<endl;cout<<" "for(j = 0;j <= N+1;j+)if(Mazeij = 0) cout<<" "if(Mazeij = 1) cout<<""if(Mazeij = 10) cout<<"A "if(Mazeij = 11) cout<<" B"if(Mazeij = 12) cout<<"C "if(Mazeij = 13) cout<<" D"int Mazepath(int MazeN+2,int x1,int y1,int x2,int y2)if( x1 = 1 && y1 = 1 && 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->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)