数据结构程序设计(迷宫问题).doc

合肥工业大学数据结构课程设计报告 课程设计名称：迷宫问题的数据结构C+描述班 级：信息与计算科学1班姓 名：刘石清 20106583 张任重 20106607指 导 老 师：王青山 王琦1.实验目的及要求1）、设计目标（问题描述）迷宫问题：编写一个程序求解迷宫问题。迷宫以m行n列的长方阵表示，0和1分别表示迷宫中通路和障碍。设计一个程序，对任意设定的迷宫，求出一条入口到出口的通路，或得出没有通路的结论。 算法要点：创建迷宫，试探查找路径，输出解2）、需求分析 1、本程序实现迷宫的探索过程. 以用户和计算机对话的方式，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，然后程序就探索路径并输出路径。 2、本演示程序中，输入形式以“回车符”为结束标志，且允许出现重复字符。 3、利用二维指针实现迷宫位置的存储，并用栈存贮探索路径，每个结点含三个整形变量。输入的形式以回车结束。 4、本程序中，用户可以读去文件里的迷宫，也可自己重新输入迷宫，而且用户可以输入任意大小的迷宫，然后程序自动探索路径，并输出迷宫的路径 2. 实验内容1）、设计概述(a) 开发平台：Visual C+ 6.0(b) 参考书籍： 1.数据结构C+描述 熊岳山 陈怀义 编著 2、数据结构与算法黄定 黄煜廉编著3、数据结构辅导与提高徐孝凯 编著2）、处理流程(a)画出功能结构图(b)画出主要数据结构的类图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，否则返回03）、源程序#include#include#includeusing namespace std;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;stack:stack() /构造函数，置空栈top=NULL;stack:stack() /析构函数void stack:Push(DataType x) /进栈Node *TempNode; TempNode=new Node; TempNode-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() /判断栈是否为空，如果为空则返回1，否则返回0if(top=NULL) return true; else return false;/* Description: 外部函数的声明部分*/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);/* Description: main.cpp*/ void main() coutendl; 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 从文件中读取endl; cout 直接自行输入endl; coutch; 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; coutc; if(c=n) flag1=1; else flag=0; cout 谢谢,您已经退出迷宫系统 endl; coutendl;/* Description: 获取迷宫函数*/int* readFile (int &m,int &n) /读出文件int *maze; int i=0,j=0; cout 您选择的是直接从文件中读取迷宫!endl; coutendl; cout 文件中的迷宫如下： endl; char ch; /定义一个字符，读取文件中的内容 ifstream open(maze.txt); /定义一个文件对象，并打开文件maze.txt /读取内容记录行数和列数 while(open.get(ch) /从读取文件中内容（一旦个字符形式） if(ch=0|ch=1) j+; /是0或1字符宽就加1 if(ch=n) i+; /如果是换行符，就行加1 n=j; /得列数 j=0; open.close(); /读取文件结束 m=i; maze=new int *m+2; /申请长度等于行数加2的二维指针(为后面的回复迷宫打下基础) for(i= 0;im+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; /把数字字符转化为数字，并存到指针里 coutmazeij ; /在屏幕中显示迷宫 j+; if(ch=n) /遇到换行，指针也相应换行 coutendl; i+; j=1; open1.close(); /读取结束 return maze; int* writeFile (int &m,int &n) /将自定义迷宫写入文件int a,b; int i,j;int*maze; cout 您选择的是自行输入迷宫!endl; coutb; /输入迷宫的长和宽 couta; cout 请输入迷宫内容(0代表可通，1代表不通):n; m=a; n=b; /m,n分别代表迷宫的行数和列数 maze=new int *m+2; for(i= 0;im+2;i+) mazei=new intn+2; for(i=1;i=m;i+) /输入迷宫的内容，0代表可通，1代表不通 for(j=1;jmazeij; coutchoose; if(choose=Y|choose=y) char ch; string str; coutstr; ofstream open(str.c_str(); for(i=1;i=m;i+) for(j=1;j=n;j+) ch=0+mazeij; opench; openendl; flush(cout); open.close(); for(i=0;im+2;i+) mazei0=mazein+1=1; for(i=0;in+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&p.GetPop().y=q.GetPop().y) p.Push(Temp2); /如果有新位置入栈，则把上一个探索的位置存入栈p for(loop=0;loop4;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; 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; /表示查找失败，即迷宫无路经/* Description: 输出路径函数*/void PrintPath(stack p) /输出路径coutendl; cout 迷宫的路径为endl; coutdata=p.Pop(); t.Push(temp-data); /第一个位置入栈 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-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(dat