《迷宫问题——数据结构课程设计迷宫问题完整版(含源代码)》由会员分享，可在线阅读，更多相关《迷宫问题——数据结构课程设计迷宫问题完整版(含源代码)（26页珍藏版）》请在金锄头文库上搜索。
1、Ki Ki Ki Ki Ki Ki Ki Ki彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、实践教学Kl Kl Kl Kl Kl Kl Kl Kl Kl Kl Kl Kl Kl Kl Kl Kl Kl Kl Kl彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、兰州理工大学计算机与通信学院2012 年春季学期算法与数据结构 课程设计专业班级 名 学号 指导教师 成绩题 目： 迷宫问题计算机科学与技术一班vl* k1* k1* k1* k1* k1* k1* k1*T *T* *T* *T *T *T *T* *T*目录摘要 3、八、.前言
2、 4正文 5一、采用C+语言定义相关的数据类型5二、各模块的伪码算法6三、函数的调用关系图10四、调试分析 11五、测试结果 121、开始界面 122、自动生成迷宫运行情况123、键盘输入迷宫运行情况14总结 16致谢 17参考文献 18附录 19源程序（带注释）19摘要本程序主要是对任意给定的迷宫，求出一条从入口到出口的通路，或得出没 有通路的结论。使我们基本掌握线性表及栈上基本运算的实现，进一步理解和熟 练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题， 培养我们的动手能力。1、生成迷宫：根据提示输入数据，然后生成一个 8 行8 列的迷宫。2、探索迷宫路径：由输入的入口
3、位置开始，对相邻的（上，下，左，右）四 个方向的方块进行探索，若可通则“纳入路径”，否则顺着“来向”退到“前一通 道块”，朝着“来向”之外的其它方向继续探索。3、保存迷宫路径：若探索到出口则把探索到的路径压入另一个栈中，并最后 弹出路径坐标，输出在屏幕上。关键字：栈，栈的存储结构，出栈与入栈前言求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机 解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探 索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至 所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需 要用一个后进先出的结
4、构来保存从入口到当前位置的路径。因此，在求迷宫通路 的算法中应用“栈”也就是自然而然的事。迷宫问题要求，所求路径必须是简单 路径，即在求得路径上不能同时重复出现同一通道。在迷宫中用 1 和 0 分别表示 迷宫中的通路和障碍。首先，输入迷宫数据，在计算机的屏幕上显示一个8 行8 列的矩阵表示迷宫。 矩阵中的每个数据或为通路（以 0 表示），或为墙（以 1 表示），所求路径必须是 简单路径，即在求得的路径上不能重复出现同一道块。其次，假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块 位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置“可通”，则“纳 入当前路径”，并继续朝“下一个
5、位置”探索，即切换“下一位置”为“当前位置”， 如此重复直到到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一 通道块”，然后朝着除“来向”，之外的其它方向继续探索，若该通道块的四周四 个方块均“不可通”，则应该从“当前路径”上删除该通道块，所谓“下一个位置” 指的是“当前位置”四周四个方向（上，下，左，右）上相邻的方块。假设以栈s 记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳 入路径”的操作为“当前位置入栈”；从当前路径删除前一通道块的操作为“出栈”。最后，若找到出口，则从栈中弹出数据，在屏幕上显示从入口到出口的路径 坐标。最后希望通过对该课题的设计，
6、理解和掌握所学到的各种数据结构，学会 把学到的知识应用于解决实际的问题当中，培养自己的动手能力。正文、采用C+语言定义相关的数据类型1、定义坐标(X, Y):#include #include using namespace std; struct Coorint row;int column;int direction;2、定义方向： struct Moveint row;int column;3、定义/链表结点： struct LinkNodeCoor data; LinkNode *next;4、定义栈：class stackprivate: LinkNode *top;public:
7、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(); /判断栈是否为空 bo
8、ol 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+) /申请每
9、个二维指针的空间mazei=new intn+2;for(i=1;i=m;i+) for(j=1;jmazeij;coutvv是否保存新迷宫？ n;coutvv用Y或y表示保存、N或n表示不保存n; char choose;cinchoose;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+)
10、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=1)coutvv ”；coutendl；return maze；/返回存贮迷宫的二维指针 maze2、探索路径函数： bool Mazepath(int *maze,int m,int n)寻找迷宫maze中从(0, 0)至到 (m,n)的路径 到则返回true，否则返回falsestack q,p;Coor Temp1,Temp2； int row,column,loop； Temp1.row=1； Temp1.colu
11、mn=1； q.Push(Temp1)； p.Push(Temp1)； maze11=8； while(!q.IsEmpty()Temp2=q.GetPop()；定义栈p、q,分别存探索迷宫的存储和路径过程/将入口位置入栈/标志入口位置已至达过/栈 q 非空,则反复探索/获取栈顶元素if(!(p.GetPop().row=q.GetPop().row&p.GetPop().column=q.GetPop().column)p.Push(Temp2)；如果有新位置入栈，则把上一个探索的位置存入栈pfor(loop=0；loopchoose;if(choose=1)PrintPath(p);/坐标
12、显示输出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().colu mn)/如果没有新位置入栈,则返回到上一个位置 p.Pop();q.Pop();/表示查找失败,即迷宫无路经return 0;3、输出迷宫void PrintPath(stack p)/输出路径coutvv迷宫的路径为n;coutvv括号内的内容分别表示为(行坐标,列坐标，数字化方向，方向)n; stack t;/定义一个栈，按从入口到出口存取路径int a,b;Coor data;LinkNode *temp;temp=new LinkNode;/申请空间temp-data=p.Pop();/取栈 p 的顶点元素，即第一个位置t.Push(temp-data); /第一个位置入栈 t delete temp;/释放空间while(!p.IsEmpty() /栈 p 非空，则反复转移
