迷宫问题非递归求解

1、 题目： 迷宫问题非递归求解 一、需求分析迷宫问题非递归求解，要求实现以下任务：（1）、可以输入一个任意大小的迷宫数据；（2）、用非递归的方法求出一条走出迷宫的路径；（3）、将路径输出；二、总体设计对于迷宫问题的非递归求解，我采用二维指针即指向指针的指针来保存迷宫，采用顺序栈来探寻迷宫路径，最后将路径输出。寻找一条走出迷宫的路径时，当下一方向可以走时（为0时），就入栈，若下一方向不可走时就退栈，再次试探另一方向是否可以走，可走再入栈，到达新的一点时依此反复。最后就可以得到迷宫的路径。将路径输出时则采用退栈方式，依次输出路径。三、详细设计创建迷宫Create（）寻找路径find（）选择1选择2选

2、择3重新输入入口出口重新创建迷宫恢复迷宫结束恢复迷宫开始四、实现部分/maze.h头文件#include#include#include#includeusing namespace std;typedef structint x,y,d;Datetype;typedef structint x,y; int pre; SqType; typedef stack stack_int;class mazepublic:void print(SqType sq,int);void again(int *maze,int m,int n);void find(int *maze,int a,int

3、b,int m,int n);void create();private:int front,rear; ;class Stackpublic: void Push(); int Pop(); Stack(); Stack(); private:int top;int data1000;/maze.cpp成员函数#include maze.h#includeiostreamvoid maze:print(SqType sq,int)int i;i=rear; docout（sqi.x,sqi.y）;i=sqi.pre; while(i!=-1);void maze:again(int *maz

4、e,int m,int n)for(int i=1;i=m;i+)for(int j=1;j=n;j+)if(mazeij=-1)mazeij=0;void maze:find(int *maze,int a,int b,int m,int n)Datetype move4=0,1,1,0,0,-1,-1,0;stack_int st;Datetype temp;int x,y,d,i,j;if(mazeab=1)cout进口输入有误。;return;temp.x=a;temp.y=b;temp.d=-1; st.push(temp);while(!st.empty()temp=st.top(

5、);x=temp.x;y=temp.y;d=temp.d+1;while(d4)i=x+moved.x;j=y+moved.y;if(mazeij=0) temp.x=x;temp.y=y;temp.d=d; st.push(temp); x=i;y=j;mazexy=-1;if(x=m & y=n)cout 迷宫路径为:endl;cout(m,n);Datetype t;while(!st.empty()t=st.top();cout(t.x,t.y);st.pop(); coutendl;return ; else d=0; else d+; cout对不起，无法找到出口.;return;

6、 void maze:create() int m,n,i,j,l,c,d;cout 请输入迷宫的行数列数:mn;int *maze=new int*m;for(i=0;i=m+1;i+)mazei=new intn;cout请输入迷宫：m行n列(0/1)；endl;for(i=1;i=m;i+) for(j=1;jmazeij; A:if(mazeij!=0 & mazeij!=1)coutmazeij;goto A; cout迷宫如下：endl; for(i=1;i=m;i+)for(j=1;j=n;j+) coutmazeij; coutendl; coutijcd;find(maze,

7、i,j,c,d); coutendl; cout-endl;cout1、重新输入入口与出口；endl;cout2、重新建立迷宫；endl;cout3、退出；endl;cout-l; if(l=1)again(maze,m,n); coutijcd;find(maze,i,j,c,d); else if (l=2)create();else return; void Stack:Push()int x=-1; if (top=999) throw 上溢; top+; datatop=x;int Stack:Pop( ) int x; if (top=-1) throw 下溢; x=datatop

8、-; return x;Stack:Stack() top=NULL;Stack:Stack() /main函数#include using namespace std;#includemaze.h void main()string s=Y;do cout-欢迎进入迷宫世界-n;maze M;M.create();coutendl;coutn 是否继续？Y 或Ns;while (s=Y|s=y);system(pause);五、程序测试创建一个5行5列的迷宫，入口为（1，1），出口为（5，4），寻找到的一条路径如下：图1.1 输入迷宫找到路径图1.2 选1重新输入入口出口图1.3 选2重新建

9、立迷宫图1.4 选3退出程序运行结构无误，符合程序设计要求。需要改进的地方是在寻找的路径上，发现并不是最短的路径，可以引入队列算法加以改进，保证最后求得的路径是最短的。七、总结通过这一周的程序设计，加深了我对数据结构面向对象程序设计的理解以及使用，对栈以及二维指针的使用都有了更深一层的了解，同时使用的也更加熟练了，我的课程设计题目是迷宫问题的非递归求解。在系统分析和设计的部分仍然花了比较多的时间。模块设计部分因为涉及功能的实现，要从抽象的设计转化成实际的代码。加上在开发系统之前，我阅读很多与本系统有相关内容的书籍以做参考，使得此次系统编写能顺利进行。经过对迷宫问题的非递归求解的分析与编写，我得到了很大的收获。自主学习的必要性更是解决问题的基础。这次设计使我重温了以前学过的C+语言的知识，让我对C编程有了更深刻的认识。 这次C课程设计，提升了我分析问题的