迷宫问题——数据结构课程设计迷宫问题完整版(含源代码)

*******************实践教学*******************兰州理工大学计算机与通信学院2012年春季学期算法与数据结构课程设计题目：迷宫问题专业班级：计算机科学与技术一班姓名：程文鑫学号：10240127指导教师：张永成绩：目录摘要..................................................................................................................................................3前言..................................................................................................................................................4正文..................................................................................................................................................5一、采用c++语言定义相关的数据类型....................................................................................5二、各模块的伪码算法...............................................................................................................6三、函数的调用关系图.............................................................................................................10四、调试分析............................................................................................................................11五、测试结果............................................................................................................................121、开始界面..............................................................................................................................122、自动生成迷宫运行情况.......................................................................................................123、键盘输入迷宫运行情况.......................................................................................................14总结................................................................................................................................................16致谢................................................................................................................................................17参考文献............................................................................................................................................18附录................................................................................................................................................19源程序（带注释）.....................................................................................................................19摘要本程序主要是对任意给定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。使我们基本掌握线性表及栈上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养我们的动手能力。1、生成迷宫：根据提示输入数据，然后生成一个8行8列的迷宫。2、探索迷宫路径：由输入的入口位置开始，对相邻的（上，下，左，右）四个方向的方块进行探索，若可通则“纳入路径”，否则顺着“来向”退到“前一通道块”，朝着“来向”之外的其它方向继续探索。3、保存迷宫路径：若探索到出口则把探索到的路径压入另一个栈中，并最后弹出路径坐标，输出在屏幕上。关键字：栈，栈的存储结构，出栈与入栈前言求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事。迷宫问题要求，所求路径必须是简单路径，即在求得路径上不能同时重复出现同一通道。在迷宫中用1和0分别表示迷宫中的通路和障碍。首先，输入迷宫数据，在计算机的屏幕上显示一个8行8列的矩阵表示迷宫。矩阵中的每个数据或为通路（以0表示），或为墙（以1表示），所求路径必须是简单路径，即在求得的路径上不能重复出现同一道块。其次，假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置“可通”，则“纳入当前路径”，并继续朝“下一个位置”探索，即切换“下一位置”为“当前位置”，如此重复直到到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”，之外的其它方向继续探索，若该通道块的四周四个方块均“不可通”，则应该从“当前路径”上删除该通道块，所谓“下一个位置”指的是“当前位置”四周四个方向（上，下，左，右）上相邻的方块。假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作为“当前位置入栈”；从当前路径删除前一通道块的操作为“出栈”。最后，若找到出口，则从栈中弹出数据，在屏幕上显示从入口到出口的路径坐标。最后希望通过对该课题的设计，理解和掌握所学到的各种数据结构，学会把学到的知识应用于解决实际的问题当中，培养自己的动手能力。正文一、采用c++语言定义相关的数据类型1、定义坐标（X，Y）:#includeiostream#includefstreamusingnamespacestd;structCoor{introw;intcolumn;intdirection;};2、定义方向：structMove{introw;intcolumn;};3、定义/链表结点：structLinkNode{Coordata;LinkNode*next;};4、定义栈：classstack{private:LinkNode*top;public:stack();~stack();voidPush(Coordata);CoorPop();CoorGetPop();voidClear();boolIsEmpty();};5、定义迷宫定义移动的4个方向：Movemove[4]={{0,1},{1,0},{0,-1},{-1,0}};6、几个函数功能的描述:stack();//构造函数，置空栈~stack();//析构函数voidPush(Coordata);//把元素data压入栈中CoorPop();//使栈顶元素出栈CoorGetPop();//取出栈顶元素voidClear();//把栈清空boolIsEmpty();//判断栈是否为空boolMazepath(int**maze,intm,intn);//寻找迷宫maze中从（0，0）到（m,n）的路径//到则返回true,否则返回falsevoidPrintPath(stackp);//输出迷宫的路径voidPrintPath2(intm,intn,stackp,int**maze);//输出路径voidRestore(int**maze,intm,intn);//恢复迷宫二、各模块的伪码算法1、根据输入产生一个8*8的迷宫：m=a;n=b;maze=newint*[m+2];//申请长度等于行数加2的二级指针for(i=0;im+2;i++)//申请每个二维指针的空间{maze[i]=newint[n+2];}for(i=1;i=m;i++)for(j=1;j=n;j++)cinmaze[i][j];cout是否保存新迷宫？\n;cout用Y或y表示保存、N或n表示不保存\n;charchoose;cinchoose;if(choose=='Y'||choose=='y'){charch;ofstreamfop(Newtest.txt);for(i=1;i=m;i++){for(j=1;j=n;j++){ch='0'+maze[i][j];fopch;}fopendl;flush(cout);}fop.close();}}//给迷宫的四周加一堵墙，即把迷宫四周定义为1for(i=0;im+2;i++)maze[i][0]=maze[i][n+1]=1;for(i=0;in+2;i++)maze[0][i]=maze[m+1][i]=1;for(intp=0;pm+2;++p){for(intq=0;q=n+2;++q){if(maze[p][q]==0)cout■;if(maze[p][q]=1)cout□;}coutendl;}returnmaze;//返回存贮迷宫的二维指针maze2、探索路径函数：boolMazepath(int**maze,intm,intn)//寻找迷宫maze中从（0，0）到（m,n）的路径//到则返回true,否则返回false{stackq,p;//定义栈p、q,分别存探索迷宫的存储和路径过程CoorTemp1,Temp2;introw,column,loop;Temp1.row=1;Temp1.column=1;q.Push(Temp1);//将入口位置入栈p.Push(Temp1);maze[1][1]=8;//标志入口位置已到达过wh