《迷宫问题非递归求解.doc》由会员分享，可在线阅读，更多相关《迷宫问题非递归求解.doc（9页珍藏版）》请在金锄头文库上搜索。
1、东华理工大学迷宫问题非递归求解 题目： 迷宫问题非递归求解 一、需求分析迷宫问题非递归求解，要求实现以下任务：（1）、可以输入一个任意大小的迷宫数据；（2）、用非递归的方法求出一条走出迷宫的路径；（3）、将路径输出；二、总体设计对于迷宫问题的非递归求解，我采用二维指针即指向指针的指针来保存迷宫，采用顺序栈来探寻迷宫路径，最后将路径输出。寻找一条走出迷宫的路径时，当下一方向可以走时（为0时），就入栈，若下一方向不可走时就退栈，再次试探另一方向是否可以走，可走再入栈，到达新的一点时依此反复。最后就可以得到迷宫的路径。将路径输出时则采用退栈方式，依次输出路径。三、详细设计创建迷宫Create（）寻找
2、路径find（）选择1选择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 *
3、maze,int a,int 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
4、:again(int *maze,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.empt
5、y()temp=st.top();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对不起，
6、无法找到出口.;return; 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; cout
7、ijcd;find(maze,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) thro
8、w 下溢; x=datatop-; 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重新输
9、入入口出口图1.3 选2重新建立迷宫图1.4 选3退出程序运行结构无误，符合程序设计要求。需要改进的地方是在寻找的路径上，发现并不是最短的路径，可以引入队列算法加以改进，保证最后求得的路径是最短的。七、总结通过这一周的程序设计，加深了我对数据结构面向对象程序设计的理解以及使用，对栈以及二维指针的使用都有了更深一层的了解，同时使用的也更加熟练了，我的课程设计题目是迷宫问题的非递归求解。在系统分析和设计的部分仍然花了比较多的时间。模块设计部分因为涉及功能的实现，要从抽象的设计转化成实际的代码。加上在开发系统之前，我阅读很多与本系统有相关内容的书籍以做参考，使得此次系统编写能顺利进行。经过对迷宫问题的非递归求解的分析与编写，我得到了很大的收获。自主学习的必要性更是解决问题的基础。这次设计使我重温了以前学过的C+语言的知识，让我对C编程有了更深刻的认识。 这次C课程设计，提升了我分析问题的能力和思考问题的逻辑能力，更明白实际调研的重要性。从这次设计学到的东西，相信会对我日后的学习工作起到很大的指导作用。 最后谢谢高永平老师对我的细心指导，正是因为有了老师您的细心指导才使得我对数据结构程序设计更加感兴趣，使得这一个学期的学习那么的愉快而且深刻，使得这次的课程设计进行的如此顺利。- 9 -
