数据结构之迷宫求解杨磊分析.doc

实验课名称：数据结构实验二 实验名称：迷宫求解 班级学号：27 姓名：杨磊 时间： 一、问题描述 这是心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子的入口处放入，让老鼠自行找到出口出来。迷宫中设置很多障碍阻止老鼠前行，迷宫唯一的出口处放有一块奶酪，吸引老鼠找到出口。 迷宫四周设为墙；无填充处，为可通处。设每个点有四个可通方向，分别为东、南、西、北。左上角为入口。右下角为出口。迷宫有一个入口，一个出口。设计程序求解迷宫的一条通路。 数据结构设计 class 类名DataType //定义描述迷宫中当前位置的类型 数据成员 访问控制权限 数据类型 变量名; 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; //指向第一个结点的栈顶指针 成员函数 访问控制权限 返回值类型 函数名(参数列表) public: stack(); //构造函数，置空栈 ~stack(); //析构函数 void Push(DataType data);//把元素data压入栈中 DataType Pop(); //使栈顶元素出栈 DataType GetPop(); //取出栈顶元素 void Clear(); //把栈清空 bool IsEmpty(); //判断栈是否为空，如果为空则返回1，否则返回0 三、算法设计 问题要求建立模型，确定存储结构 图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)//标志是否重新选择 {coutendl; cout ★请从以下选项中选择获取迷宫的方法！endl; cout a从文件中读取endl; cout b直接自行输入endl; cout ★请选择:; cinch; 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 ★ Congratulations! 迷宫路径探索成功!endl; //得到路径 else cout ★Sorry! 路径不存在★endl; coutendl; cout ★ 继续玩吗？(y/n); char c; cinc; if(c==n) flag1=1; else flag=0; } cout◆◆◆◆◆◆◆ 谢谢,您已经退出迷宫系统 ◆◆◆◆◆◆◆endl; cout◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆endl; return 0; } 探索迷宫路径 /* Description: 探索路径函数 */ bool findpath(int **maze,int m,int n)