数据结构之迷宫求解杨磊

1、实验课名称：数据结构实验二实验名称：迷宫求解班级：20130612学号：27姓名：杨磊时间：一、问题描述 这是心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子的入口处放入，让老鼠自行找到出口出来。迷宫中设置很多障碍阻止老鼠前行，迷宫唯一的出口处放有一块奶酪，吸引老鼠找到出口。简而言之，迷宫问题是解决从布置了许多障碍的通道中寻找出路的问题。本题设置的迷宫如图1所示。迷宫四周设为墙；无填充处，为可通处。设每个点有四个可通方向，分别为东、南、西、北。左上角为入口。右下角为出口。迷宫有一个入口，一个出口。设计程序求解迷宫的一条通路。2、 数据结构设计 class 类名DataType /

2、定义描述迷宫中当前位置的类型数据成员访问控制权限 数据类型 变量名; public:int x; /x代表当前位置的行坐标 int y; /y代表当前位置的列坐标 int pre; /pre表示移动到下一步的方向 class 类名Move /定义下一个位置的方向数据成员访问控制权限 数据类型 变量名; public:int x; int y;class 类名Node /结点数据成员访问控制权限 数据类型 变量名; public: DataType data; Node *next;class 类名stack数据成员访问控制权限 数据类型 变量名; private: Node *top; /指向

3、第一个结点的栈顶指针成员函数访问控制权限 返回值类型 函数名(参数列表) public: stack(); /构造函数，置空栈 stack(); /析构函数 void Push(DataType data);/把元素data压入栈中 DataType Pop(); /使栈顶元素出栈 DataType GetPop(); /取出栈顶元素 void Clear(); /把栈清空 bool IsEmpty(); /判断栈是否为空，如果为空则返回1，否则返回0三、算法设计问题要求建立模型，确定存储结构，迷宫以m行n列的长方阵表示，0和1分别表示迷宫中通路和障碍，之后由人为控制迷宫的行数与列数。设计流程

4、图如图1.1所示。图1.1 设计流程图（1） 数据输入 （迷宫的生成） int main() cout<<""<<endl; cout<<" 欢迎进入迷宫游戏 "<<endl; int m=0,n=0; int *maze; char ch; int flag=0,flag1=0; while(flag1=0) while(flag=0)/标志是否重新选择 cout<<endl; cout<<" 请从以下选项中选择获取迷宫的方法！"<<endl; co

5、ut<<" <a>从文件中读取"<<endl; cout<<" <b>直接自行输入"<<endl; cout<<" 请选择:" cin>>ch; if(ch='a')maze=readFile(m,n);flag=1; else if(ch='b')maze=writeFile(m,n);flag=1; else cout<<" Sorry!您输入的选择代码不在范围内!请从新选择&quo

6、t;<<endl; if(findpath(maze,m,n) cout<<" Congratulations! 迷宫路径探索成功!"<<endl; /得到路径 else cout<<" Sorry! 路径不存在"<<endl; cout<<endl; cout<<" 继续玩吗？(y/n)" char c; cin>>c; if(c=n) flag1=1; else flag=0; cout<<" 谢谢,您已经退出迷宫

7、系统 "<<endl; cout<<""<<endl; return 0;（2） 探索迷宫路径 /* Description: 探索路径函数*/bool findpath(int *maze,int m,int n)stack q,p; DataType Temp1,Temp2; int x,y,loop; Temp1.x=1; Temp1.y=1; q.Push(Temp1); /将入口位置入栈 p.Push(Temp1); maze11=-1; while(!q.IsEmpty() /栈q非空，则反复探索 Temp2=q.G

8、etPop(); if(!(p.GetPop().x=q.GetPop().x&&p.GetPop().y=q.GetPop().y) p.Push(Temp2); /如果有新位置入栈，则把上一个探索的位置存入栈p for(loop=0;loop<4;loop+) /探索当前位置的4个相邻位置 x=Temp2.x+moveloop.x; y=Temp2.y+moveloop.y; if(mazexy=0) /判断新位置是否可达 Temp1.x=x; Temp1.y=y; mazexy=-1; /标志新位置已到达过 q.Push(Temp1); /新位置入栈 if(x=(m

9、)&&(y=(n) /成功到达出口 Temp1.x=m; Temp1.y=n; Temp1.pre=0; p.Push(Temp1); /把最后一个位置入栈 PrintPath(p); Restore(maze,m,n); /恢复路径（因为迷宫里面的内容已被改变 return 1; /表示成功找到路径 if(p.GetPop().x=q.GetPop().x&&p.GetPop().y=q.GetPop().y)/如果没有新位置入栈，则返回到上一个位置 p.Pop(); q.Pop(); return 0; /表示查找失败/* */ （3）输出 * Descri

10、ption: 输出路径函数*/void PrintPath(stack p) /输出路径cout<<endl; cout<<" 迷宫的路径为"<<endl; cout<<" 说明:括号内的内容分别表示为(行坐标,列坐标,方向)n" stack t; /定义一个栈，按从入口到出口存取路径 int row,column; DataType data; Node *temp; temp=new Node; /申请空间 temp->data=p.Pop(); t.Push(temp->data); /第

11、一个位置入栈 delete temp; while(!p.IsEmpty() /栈p非空，则转移 temp=new Node; temp->data=p.Pop(); /获取下一个位置 /得到行走方向 row=t.GetPop().x-temp->data.x; /行坐标方向 column=t.GetPop().y-temp->data.y; /列坐标方向 if(row=1) temp->data.pre=1; /向下，用1表示 else if(column=1) temp->data.pre=2; /向右，用2表示 else if(row=-1) temp-&g

12、t;data.pre=3; /向上，用3表示 else if(column=-1) temp->data.pre=4; /向左，用4表示 t.Push(temp->data); /把新位置入栈 delete temp; while(!t.IsEmpty() /栈非空，继续输出 data=t.Pop(); cout<<" "<<'('<<data.x<<','<<data.y<<"," switch(data.pre) /输出相应的方向 ca

13、se 0:cout<<")n"break; case 1:cout<<"向下)n"break; case 2:cout<<"向右)n"break; case 3:cout<<"向上)n"break; case 4:cout<<"向左)n"break; 四、界面设计 程序包含输入提示功能和输出提示功能。五、运行测试与分析（1）运行程序，显示提示，如图1.2所示。图1.2 启动界面（2） 按“a”从文件中读取迷宫，按“b”手动输入迷宫图1.

14、3 数据输入界面 （3）输入迷宫的长宽 并保存迷宫图1.4 迷宫生成界面（4）路径输出6、 实验收获与思考1、进一步熟悉掌握了有关栈的基本操作；2、对迷宫有了更多的认识。3、更进一步掌握有关类的操作。4、由于对栈的算法推敲不足，使程序调试时费时不少。 源代码#include<iostream>#include<string>#include<fstream>using namespace std;class DataType public:int x; int y; int pre; ; class Move public:int x; int y;clas

15、s Node public: DataType data; Node *next;class stack private: Node *top; public: stack(); stack(); void Push(DataType data); DataType Pop(); DataType GetPop(); void Clear(); bool IsEmpty(); ;stack:stack() top=NULL;stack:stack() void stack:Push(DataType x) Node *TempNode; TempNode=new Node; TempNode-

16、>data=x; TempNode->next=top; top=TempNode;DataType stack:Pop() DataType Temp; Node *TempNode=NULL; TempNode=top; top=top->next; Temp=TempNode->data; delete TempNode; return Temp;DataType stack:GetPop() return top->data;void stack:Clear() top=NULL;bool stack:IsEmpty() if(top=NULL) retu

17、rn true; else return false;/* 外部函数的声明部分*/bool findpath(int *maze,int m,int n); /寻找迷宫路径 void PrintPath(stack p); /输出路径void Restore(int *maze,int m,int n); /恢复迷宫Move move4=0,1,1,0,0,-1,-1,0; /定义当前位置移动的4个方向(上，右，下，左)int* readFile (int &m,int &n);int* writeFile(int &m,int &n); int main()

18、cout<<""<<endl; cout<<" 欢迎进入迷宫游戏 "<<endl; int m=0,n=0; int *maze; char ch; int flag=0,flag1=0; while(flag1=0) while(flag=0)/标志是否重新选择 cout<<endl; cout<<" 请从以下选项中选择获取迷宫的方法！"<<endl; cout<<" <a>从文件中读取"<<e

19、ndl; cout<<" <b>直接自行输入"<<endl; cout<<" 请选择:" cin>>ch; if(ch='a')maze=readFile(m,n);flag=1; else if(ch='b')maze=writeFile(m,n);flag=1; else cout<<" Sorry!您输入的选择代码不在范围内!请从新选择"<<endl; if(findpath(maze,m,n) cout<&

20、lt;" Congratulations! 迷宫路径探索成功!"<<endl; /得到路径 else cout<<" Sorry! 路径不存在"<<endl; cout<<endl; cout<<" 继续玩吗？(y/n)" char c; cin>>c; if(c=n) flag1=1; else flag=0; cout<<" 谢谢,您已经退出迷宫系统 "<<endl; cout<<""

21、<<endl; return 0;/* Description: 获取迷宫函数*/int* readFile (int &m,int &n) /读出文件int *maze; int i=0,j=0; cout<<" 您选择的是直接从文件中读取迷宫!"<<endl; cout<<endl; cout<<" 文件中的迷宫如下： "<<endl; char ch; ifstream open("maze.txt"); if(ch='0'|

22、ch='1') j+; if(ch='n') i+; n=j; j=0; open.close(); m=i; maze=new int *m+2; for(i= 0;i<m+2;i+) mazei=new intn+2; i=j=1; ifstream open1("maze.txt"); while(open1.get(ch) if(ch='1'|ch='0') mazeij=ch-'0' cout<<mazeij<<" " j+; if(c

23、h='n') cout<<endl; i+; j=1; open1.close(); return maze; int* writeFile (int &m,int &n) /将自定义迷宫写入文件int a,b; int i,j;int*maze; cout<<" 您选择的是自行输入迷宫!"<<endl; cout<<" 请输入迷宫的长:"cin>>b; /输入迷宫的长和宽 cout<<" 请输入迷宫的宽:"cin>>a

24、; cout<<" 请输入迷宫内容(0代表可通，1代表不通):n" m=a; n=b; maze=new int *m+2; for(i= 0;i<m+2;i+) mazei=new intn+2; for(i=1;i<=m;i+) /输入迷宫的内容，0代表可通，1代表不通 for(j=1;j<=n;j+) cin>>mazeij; cout<<" 是否保存新迷宫？(y/n): " char choose; cin>>choose; if(choose='Y'|choose

25、='y') char ch; string str; cout<<" 请输入保存迷宫的文件名(以.txt结束):" cin>>str; ofstream open(str.c_str(); for(i=1;i<=m;i+) for(j=1;j<=n;j+) ch='0'+mazeij; open<<ch; open<<endl; flush(cout); open.close(); for(i=0;i<m+2;i+) mazei0=mazein+1=1; for(i=0;i&l

26、t;n+2;i+) maze0i=mazem+1i=1; return maze; /* Description: 探索路径函数*/bool findpath(int *maze,int m,int n)stack q,p; DataType Temp1,Temp2; int x,y,loop; Temp1.x=1; Temp1.y=1; q.Push(Temp1); /将入口位置入栈 p.Push(Temp1); maze11=-1; while(!q.IsEmpty() /栈q非空，则反复探索 Temp2=q.GetPop(); if(!(p.GetPop().x=q.GetPop().x

27、&&p.GetPop().y=q.GetPop().y) p.Push(Temp2); /如果有新位置入栈，则把上一个探索的位置存入栈p for(loop=0;loop<4;loop+) /探索当前位置的4个相邻位置 x=Temp2.x+moveloop.x; y=Temp2.y+moveloop.y; if(mazexy=0) /判断新位置是否可达 Temp1.x=x; Temp1.y=y; mazexy=-1; /标志新位置已到达过 q.Push(Temp1); /新位置入栈 if(x=(m)&&(y=(n) /成功到达出口 Temp1.x=m; Te

28、mp1.y=n; Temp1.pre=0; p.Push(Temp1); /把最后一个位置入栈 PrintPath(p); Restore(maze,m,n); /恢复路径（因为迷宫里面的内容已被改变 return 1; /表示成功找到路径 if(p.GetPop().x=q.GetPop().x&&p.GetPop().y=q.GetPop().y)/如果没有新位置入栈，则返回到上一个位置 p.Pop(); q.Pop(); return 0; /表示查找失败/* Description: 输出路径函数*/void PrintPath(stack p) /输出路径cout<<endl; cout<<" 迷宫的路径为"<<endl; cout<<" 说明:括号内的内容分别表示为(行坐标,列坐标,方向)n" stack t; /定义一个栈，按从入口到出口存取路径 int row,column; DataType data; Node *temp; temp=new Node; /申请空间 temp->data=p.Pop(); t.Push(temp->data); /第一个位置入栈 delete tem