迷宫问题——数据结构课程设计迷宫问题.doc

*实践教学* 兰州理工大学计算机与通信学院2012年春季学期 算法与数据结构 课程设计题 目： 迷宫问题 专业班级：计算机科学与技术一班 姓 名： 程文鑫 学 号： 10240127 指导教师： 张永 成 绩： 目 录摘 要3前 言4正 文5一、采用c+语言定义相关的数据类型5二、各模块的伪码算法6三、函数的调用关系图10四、调试分析11五、测试结果111、开始界面122、自动生成迷宫运行情况123、键盘输入迷宫运行情况14总 结16致 谢17参考文献18附 录19源程序（带注释）19摘 要本程序主要是对任意给定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。使我们基本掌握线性表及栈上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养我们的动手能力。1、生成迷宫：根据提示输入数据，然后生成一个8行8列的迷宫。2、探索迷宫路径：由输入的入口位置开始，对相邻的（上，下，左，右）四个方向的方块进行探索，若可通则“纳入路径”，否则顺着“来向”退到“前一通道块”，朝着“来向”之外的其它方向继续探索。3、保存迷宫路径：若探索到出口则把探索到的路径压入另一个栈中，并最后弹出路径坐标，输出在屏幕上。 关键字：栈，栈的存储结构，出栈与入栈前 言 求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事。迷宫问题要求，所求路径必须是简单路径，即在求得路径上不能同时重复出现同一通道。在迷宫中用1和0分别表示迷宫中的通路和障碍。 首先，输入迷宫数据，在计算机的屏幕上显示一个8行8列的矩阵表示迷宫。矩阵中的每个数据或为通路（以0表示），或为墙（以1表示），所求路径必须是简单路径，即在求得的路径上不能重复出现同一道块。 其次，假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置“可通”，则“纳入当前路径”，并继续朝“下一个位置”探索，即切换“下一位置”为“当前位置”，如此重复直到到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”，之外的其它方向继续探索，若该通道块的四周四个方块均“不可通”，则应该从“当前路径”上删除该通道块，所谓“下一个位置”指的是“当前位置”四周四个方向（上，下，左，右）上相邻的方块。假设以栈s记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作为“当前位置入栈”；从当前路径删除前一通道块的操作为“出栈”。 最后，若找到出口，则从栈中弹出数据，在屏幕上显示从入口到出口的路径坐标。最后希望通过对该课题的设计，理解和掌握所学到的各种数据结构，学会把学到的知识应用于解决实际的问题当中，培养自己的动手能力。正 文一、采用c+语言定义相关的数据类型1、定义坐标（x，y）:#include#includeusing namespace std;struct coor int row; int column; int direction; ; 2、定义方向：struct move int row;int column;3、定义/链表结点：struct linknode coor data;linknode *next;4、定义栈：class stackprivate:linknode *top; public:stack(); stack(); void push(coor data); coor pop(); coor getpop(); void clear(); bool isempty(); ;5、定义迷宫定义移动的4个方向：move move4=0,1,1,0,0,-1,-1,0;6、几个函数功能的描述: stack(); /构造函数，置空栈 stack(); /析构函数void push(coor data); /把元素data压入栈中coor pop(); /使栈顶元素出栈coor getpop(); /取出栈顶元素void clear(); /把栈清空bool isempty(); /判断栈是否为空bool mazepath(int *maze,int m,int n); /寻找迷宫maze中从（0，0）到（m,n）的路径 /到则返回true,否则返回falsevoid printpath(stack p); /输出迷宫的路径void printpath2(int m,int n,stack p,int *maze); /输出路径void restore(int *maze,int m,int n); /恢复迷宫二、各模块的伪码算法1、根据输入产生一个8*8的迷宫：m=a; n=b; maze=new int *m+2; /申请长度等于行数加2的二级指针 for(i= 0;im+2;i+) /申请每个二维指针的空间 mazei=new intn+2;for(i=1;i=m;i+) for(j=1;jmazeij;cout是否保存新迷宫？n;coutchoose;if(choose=y|choose=y)char ch;ofstream fop(newtest.txt); for(i=1;i=m;i+)for(j=1;j=n;j+)ch=0+mazeij;fopch;fopendl;flush(cout);fop.close(); /给迷宫的四周加一堵墙，即把迷宫四周定义为1for(i=0;im+2;i+) mazei0=mazein+1=1;for(i=0;in+2;i+) maze0i=mazem+1i=1;for(int p=0;pm+2;+p)for(int q=0;q=n+2;+q)if(mazepq=0)cout=1)cout;coutendl;return maze; /返回存贮迷宫的二维指针maze2、探索路径函数：bool mazepath(int *maze,int m,int n) /寻找迷宫maze中从（0，0）到（m,n）的路径 /到则返回true,否则返回falsestack q,p; /定义栈p、q,分别存探索迷宫的存储和路径过程coor temp1,temp2; int row,column,loop;temp1.row=1;temp1.column=1;q.push(temp1); /将入口位置入栈p.push(temp1);maze11=8; /标志入口位置已到达过while(!q.isempty() /栈q非空，则反复探索temp2=q.getpop(); /获取栈顶元素if(!(p.getpop().row=q.getpop().row&p.getpop().column=q.getpop().column) p.push(temp2); /如果有新位置入栈，则把上一个探索的位置存入栈pfor(loop=0;loop4;loop+) /探索当前位置的4个相邻位置row=temp2.row+moveloop.row; /计算出新位置x位置值column=temp2.column+moveloop.column; /计算出新位置y位置值if(mazerowcolumn=0) /判断新位置是否可达temp1.row=row;temp1.column=column;mazerowcolumn=8; /标志新位置已到达过q.push(temp1); /新位置入栈if(row=(m)&(column=(n) /成功到达出口temp1.row=m;temp1.column=n;temp1.direction=0;p.push(temp1); /把最后一个位置入栈char choose;coutchoose; if(choose=1) printpath(p); /坐标显示输出 restore(maze,m,n); elseprintpath2(m,n,p,maze); /矩阵显示输出 restore(maze,m,n); return 1; /表示成功找到路径if(p.getpop().row=q.getpop().row&p.getpop().column=q.getpop().column) /如果没有新位置入栈，则返回到上一个位置p.pop();q.pop();return 0; /表示查找失败，即迷宫无路经3、输出迷宫void printpath(stack p) /输出路径cout迷宫的路径为n;coutdata=p.pop(); /取栈p的顶点元素，即第一个位置t.push(temp-data); /第一个位置入栈tdelete temp; /释放空间while(!p.isempty() /栈p非空，则反复转移temp=new linknode;temp-data=p.pop(); /获取下一个位置 /得到行走方向a=t.getpop().row-temp-data.row; /行坐标方向b=t.getpop().column-temp-data.column; /列坐标方向if(a=1) temp-data.direction=1; /方向向下，用1表示else if(b=1) temp-data.direction=2; /方向向右，用2表示else if(a=-1) temp-data.direction=3; /方向向上，用3表示else if(b=-1) temp-data.direction=4; /方向向左，用4表示t.push(temp-data); /把新位置入栈delete temp;cout坐标（row,column,direction）中x在指向当前位置所在的行数，y指向当前位置所在的列数，;coutdirection表示下一位置走向。endl; /输出路径，包括行坐标，列坐标，下一个位置方向while(!t.isempty() /栈非空，继续输出data=t.pop();cout(data.row,data.column,data.direction,; /输出行坐标，列坐标switch(data.direction) /输出相应的方向 case 1:cout)n;break;case 2:cout)n;break;case 3:cout)n;break;case 4:cout)n;break;case 0:cout)n;break;void printpath2(int m,int n,stack p,int *maze) /输出路径cout迷宫的路径为n;for (int i = 0; i m+2; +i )for (int j = 0; j n+2; +j)cout mazeij ;cout =0&ch=9都可以执行，但是在执行过程中显示迷宫时有“吃墙”现象，如图： 经过反复调试程序，最后发现在定义 出错，后来改为后，吃图现象在没有发生，如图；2、算法的时间复杂度和空间复杂度空间复杂度：o（1）；时间复杂度随机生成迷宫：o（n*n）；探寻出口：o（n*n）；输出迷宫：o（n*n）；判断当前位置可通：o（1）。五、测试结果 1、开始界面 2、自动生成迷宫运行情况（1） 选择生成迷宫输入1如下图所示 （2） 选择以坐标形式输出迷宫：输入1如下图所示（3） 选择以方阵形式输出迷宫：输入2如下图所示（其中8代表路径，1代表墙） 3、键盘输入迷宫运行情况（1） 选择键盘输入输入2如下图所示（2） 键盘输入10*10的迷宫，运行结果及通路结果如下图所示总 结 我的课设题目为迷宫问题，通过该题目的设计过程,我加深了对栈的逻辑结构,存储结构及入栈出栈过程的理解,对栈的基本运算的实现有所掌握,对课本中所学的各种数据结构进一步理解和掌握,学会了如何把学到的知识用于解决实际问题,锻炼了自己动手的能力。 本次课程设计，使我对数据结构线性表的设计方法、步骤、思路，有一定的了解和认识，它相当于实际设计工作的模拟。在课程设计过程中，基本能按照规定的程序进行，先针对表达式算法为背景，建立系统模型：收集、调查有关资料，共同与老师和同学进行几次讨论、修改、再讨论、再修改，最后确定方案。 通过此次课程设计，我了解了编写应用软件的一般步骤，获得了很多宝贵的经验，特别是怎么样通过理论与实践相结合，把书本上的内容应用到我们做的程序上去。怎样使各个子模块实施其的详细功能，特别是各个子模块之间的接口，一定要相当清晰，达到相互协调的作用。其次，我熟悉了数据结构知识，学会了很多关于程序设计的经验和技巧，明白了程序的使用性和通用性是程序生存周期长短的关键。学会了调试程序的一般方法，知道了如何在困难重重中一步一步发现问题，解决问题。 一个人要完成所有的工作是非常困难和耗时的。在以后的学习中我会更加注意各个方面的能力的协调发展。在课程设计时遇到了很多的问题，在老师的帮助，和对各种资料的查阅中，将问题解决，培养了我自主动手，独立研究的能力，为今后在学习工作中能更好的发展打下了坚实的基础。 三周的课程设计很短暂，但其间的内容是很充实的，在其中我学习到了很多平时书本中无法学到的东西，积累了经验，锻炼了自己分析问题，解决问题的能力，并学会了如何将所学的各课知识融会，组织，来配合学习，三周中我收益很大，学到很多。致 谢 在此次课程设计的撰写过程中，我得到了许多人的帮助和支持。 首先，我要感谢张永老师在课程设计上给予我的指导、提供给我的支持和帮助，这是我能顺利完成这次报告的主要原因，更重要的是张老师的帮助使我解决了许多技术上的难题，让我能把系统做得更加完善。在此期间，我不仅学到了许多新的知识，而且也开阔了视野，提高了自己的设计能力和实践能力。其次，我要感谢本班同学和帮助过我的同学，是他们的帮助和支持使我顺利的完成了本次课程设计，他们也为我解决了不少我不太明白的设计上的难题。同时也感谢学院为我提供良好的做课程设计的环境。最后，再一次感谢所有在课程设计中曾经帮助过我的良师益友和同学。参考文献1 严蔚敏，吴伟民.数据结构（c语言版）.清华大学出版社.2 严蔚敏，吴伟民.数据结构题集（c语言版）.清华大学出版社.3 data structure with c+. william ford,william topp .清华大学出版社（影印版）. 4 谭浩强.c语言程序设计. 清华大学出版社. 5 数据结构与算法分析（java版） , a practical introduction to data structures and algorithm analysis java edition clifford a. shaffer , 张铭,刘晓丹译电子工业出版社 2001 年1月附 录源程序（带注释） #include#includeusing namespace std;struct coor /定义描当前位置的结构类型int row; int column; int direction; ;struct move /定义下一个位置的方向int row;int column;struct linknode /链表结点coor data;linknode *next;/定义栈class stackprivate:linknode *top; public:stack(); /构造函数，置空栈 stack(); /析构函数void push(coor data); /把元素data压入栈中coor pop(); /使栈顶元素出栈coor getpop(); /取出栈顶元素void clear(); /把栈清空bool isempty(); /判断栈是否为空;stack:stack() /构造函数，置空栈top=null;stack:stack() /析构函数void stack:push(coor x) /把元素data压入栈中linknode *tempnode;tempnode=new linknode;tempnode-data=x;tempnode-next=top;top=tempnode;coor stack:pop() /使栈顶元素出栈coor temp; linknode *tempnode;tempnode=top;top=top-next;temp=tempnode-data;delete tempnode;return temp;coor stack:getpop() /取出栈顶元素return top-data;void stack:clear() /把栈清空top=null;bool stack:isempty() if(top=null) return true;else return false;move move4=0,1,1,0,0,-1,-1,0; /定义移动的4个方向bool mazepath(int *maze,int m,int n); /寻找迷宫maze中从（0，0）到（m,n）的路径 /到则返回true,否则返回falsevoid printpath(stack p); /输出迷宫的路径void printpath2(int m,int n,stack p,int *maze); /输出路径void restore(int *maze,int m,int n); /恢复迷宫int* getmaze(int &m,int &n); /获取迷宫（可从文件中读取，也可输入） /返回存取迷宫的二维指针int main()system(color f5);int m=0,n=0; int *maze; /定义二维指针存取迷宫cout ntt*欢迎使用迷宫模拟程序* endl;cout tt 10级计算机一班 endl;cout tt 程文鑫 endl;cout tt 学号：10240127 endl;maze=getmaze(m,n); /调用getmaze(int &m,int &n)函数，得到迷宫if(mazepath(maze,m,n) /调用mazepath(int *maze,int m,int n)函数获取路径cout迷宫路径探索成功!n;else cout路径不存在!n;return 0;int* getmaze(int &m,int &n) /获取迷宫（可从文件中读取，也可输入） /返回存取迷宫的二维指针int *maze; int i=0,j=0;char choose; /定义一个标志，选择读取文件或直接输入，获取迷宫coutchoose; if(choose=1) /当标志choose为1时，读取文件cout=0&ch=9) /获取文件中的数字字符j+; /如果是字符，列就加1if(ch=n) i+; /如果是换行，就行加1 n=j; /得到宽，即列数j=0; fip.close(); /读取文件结束m=i; /得到长即行数maze=new int *m+2; /申请长度等于行数加2的二级指针for(i= 0;i=0&ch=9)mazeij=ch-0; /把数字字符转化为数字，并存到指针里coutmazeij ; /在屏幕中显示迷宫j+;if(ch=n) /遇到换行，指针也相应换行coutendl;i+;j=1;fip2.close(); /读取结束coutendl; else /choose=2 ,输入迷宫 coutab; cout请输入迷宫内容:(0表示通路,1表示不连通。中间用空格键分开)n;m=a; n=b; maze=new int *m+2; /申请长度等于行数加2的二级指针 for(i= 0;im+2;i+) /申请每个二维指针的空间 mazei=new intn+2;for(i=1;i=m;i+) for(j=1;jmazeij;cout是否保存新迷宫？n;coutchoose;if(choose=y|choose=y)char ch;ofstream fop(newtest.txt); for(i=1;i=m;i+)for(j=1;j=n;j+)ch=0+mazeij;fopch;fopendl;flush(cout);fop.close(); /给迷宫的四周加一堵墙，即把迷宫四周定义为1for(i=0;im+2;i+) mazei0=mazein+1=1;for(i=0;in+2;i+) maze0i=mazem+1i=1;for(int p=0;pm+2;+p)for(int q=0;q=n+2;+q)if(mazepq=0)cout=1)cout;coutendl;return maze; /返回存贮迷宫的二维指针mazebool mazepath(int *maze,int m,int n) /寻找迷宫maze中从（0，0）到（m,n）的路径 /到则返回true,否则返回falsestack q,p; /定义栈p、q,分别存探索迷宫的存储和路径过程coor temp1,temp2; int row,column,loop;temp1.row=1;temp1.column=1;q.push(temp1); /将入口位置入栈p.push(temp1);maze11=8; /标志入口位置已到达过while(!q.isempty() /栈q非空，则反复探索temp2=q.getpop(); /获取栈顶元素if(!(p.getpop().row=q.getpop().row&p.getpop().column=q.getpop().column) p.push(temp2); /如果有新位置入栈，则把上一个探索的位置存入栈pfor(loop=0;loop4;loop+) /探索当前位置的4个相邻位置row=temp2.row+moveloop.row; /计算出新位置x位置值column=temp2.column+moveloop.column; /计算出新位置y位置值if(mazerowcolumn=0) /判断新位置是否可达temp1.row=row;temp1.column=column;mazerowcolumn=8; /标志新位置已到达过q.push(temp1); /新位置入栈if(row=(m)&(column=(n) /成功到达出口temp1.row=m;temp1.column=n;temp1.direction=0;p.push(temp1); /把最后一个位置入栈char choose;coutchoose; if(choose=1) printpath(p); /坐标显示输出 restore(maze,m,n); elseprintpath2(m,n,p,maze); /矩阵显示输出 restore(maze,m,n); return 1; /表示成功找到路径if(p.getpop().row=q.getpop().row&p.getpop().column=q.getpop().column) /如果没有新位置入栈，则返回到上一个位置p.pop();q.pop();return 0; /表示查找失败，即迷宫无路经void printpath(stack p