迷宫游戏数据结构课程设计.doc

计算机解迷宫问题通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。迷宫的入口点的下标为（1，1），出口点的下标为（m，n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫的任一位置，均可约定有东、南、西、北四个方向可通。有一种简单走出迷宫的方法，把手放在右边的墙上开始前进，始终不要把手从墙上移开。如果迷宫向右拐，你也顺着墙向右拐。只要不把手从墙上移开，最终就会到达迷宫的出口。当然这样得到的路径可能不是一个最短的路径，但它可以最终得到结果，换句话说，这种方法走不出迷宫的风险是最小的。本设计是为了实现一个可视化迷宫，以及利用最短路径算法寻找迷宫的出路以及将最短路径打印在屏幕上，并且限制小老鼠不能穿越墙，只能在路径上移动。而且可以根据自己的需要设计迷宫地图。关键词 迷宫；栈；VC+ 6.0 目录1 课设题目11.1课设题目.11.2基本要求：.11.3 需求分析12 程序总体设计22.1流程图：.22.2概要设计.62.3 运行结果及分析7总结9源程序10参考文献201 课设题目1.1课设题目编写一个程序求解迷宫问题。迷宫由m行n列的二维数组设置，0表示无障碍，1表示有障碍。设入口为（1，1），出口为（m，n），每次只能从一个无障碍单元移到周围四个方向上任一无障碍单元。编程实现对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。算法输入：代表迷宫入口的坐标算法输出：穿过迷宫的结果。算法要点：创建迷宫，试探法查找路径，输出解1.2基本要求：1.求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一个坐标的方向。2.输出迷宫示意图1.3 需求分析1、本程序实现迷宫的探索过程. 以用户和计算机对话的方式，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，然后程序就探索路径并输出路径。 2、本演示程序中，输入形式以“回车符”为结束标志，且允许出现重复字符。3、利用二维指针实现迷宫位置的存储，并用栈存贮探索路径，每个结点含三个整形变量。输入的形式以回车结束。4、本程序中，用户可以读去文件里的迷宫，也可自己重新输入迷宫，而且用户可以输入任意大小的迷宫，然后程序自动探索路径，并输出迷宫的路径。2 程序总体设计2.1流程图：1.功能结构图Main主函数模块输出路径模块printpath（）获取迷宫模块探索路径模块Findpath（）存储探索路径模块stack类读文件Readfile（）写文件Writefile（）Stack类数据模块操作模块盘空函数isempty（）清空函数clear（）取栈顶函数getpop（）进栈与出栈函数push（）Pop（）构造与析构函数stack（）stack（）结点模块Node*top结点数据类型模块datatype类2.画出主要数据结构的类图class 类名DataType /定义描述迷宫中当前位置的类型数据成员访问控制权限 数据类型 变量名; public:int x; /x代表当前位置的行坐标 int y; /y代表当前位置的列坐标 int dir; /dir表示移动到下一步的方向 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开始 3.main函数流程图 显示系统信息选择获取迷宫的方式chCh= bCh=aReadfile()文件读取自行输入Writefile（）探索迷宫路径是否存在输出迷宫路径是否继续游戏退出开始2.探索路径函数findpath（）Temp1.x=1Temp1.y=1入口进栈p.pushq.push是否非空temp2=q.getpop（）P q栈顶是否相等探索上下左右四个方位是否有路径到达新位置是否到达出口最后一个元素进栈输出路径回复以改变的迷宫结束开始3.自行输入迷宫函数writefile（）输入长宽m，n动态申请空间二位数组空间i<=m是否保存迷宫J<=ni+ ；j+输入迷宫输入保存迷宫的文件名保存迷宫结束2.2概要设计1.构建一个二维数组mazeM+2N+2用于存储迷宫矩阵自动或手动生成迷宫，即为二维数组mazeM+2N+2赋值构建一个队列用于存储迷宫路径建立迷宫节点struct point,用于存储迷宫中每个节点的访问情况实现搜索算法屏幕上显示操作菜单 2.本程序包含10个函数： (1)主函数 main()(2)手动生成迷宫函数 shoudong_maze()(3)打印迷宫路径 (若存在路径) result_maze()(4)入队 enqueue()(5)出队 dequeue()(6)判断队列是否为空 is_empty()(7)访问节点 visit()(8)搜索迷宫路径 mgpath()2.3 运行结果及分析 总结通过这段时间的数据结构课程设计，本人对计算机的应用，数据结构的作用以及C语言的使用都有了更深的了解。尤其是C语言的进步让我深刻的感受到任何所学的知识都需要实践，没有实践就无法真正理解这些知识以及掌握它们，使其成为自己的财富。在理论学习和上机实践的各个环节中，通过自主学习和认真听老师讲课分析，我收获了不少。当然也遇到不少的问题，也正是因为这些问题引发的思考给我带了收获。从当初不喜欢上机写程序到现在能主动写程序，从当初拿着程序不只如何下手到现在知道如何分析问题，如何用专业知识解决实际问题的转变，我发现无论是专业知识还是动手能力，自己都有很大程度的提高。在这段时间里，我对for、while等的循环函数用法更加熟悉，逐渐形成了较好的编程习惯。在老师的指导帮助下，同学们课余时间的讨论中，这些问题都一一得到了解决。在程序的调试能力上，无形中得到了许多的提高。例如：头文件的使用，变量和数组的范围问题，定义变量时出现的问题等等。在实际的上机操作过程中，不仅是让我们了解数据结构的理论知识，更重要的是培养解决实际问题的能力，所以相信通过此次实习可以提高我们分析设计能力和编程能力，为后续课程的学习及实践打下良好的基础。时间过得真快，大学生活不知不觉就走过了一学期，这一学期的大学学习和课程实践阶段的提高，使我们本身知识得到提高的同时，也增强了我们对未来工作的信心，我们相信自己未来两年半的学习更使我们有能力胜任将来的工作。源程序#include<iostream>using namespace std; class T/定义描述迷宫中当前位置的结构类型public:int x;/x代表当前位置的行坐标int y;/y代表当前位置的列坐标int dir;/0:无效,1:东,2:南,3:西,4:北; class LinkNode/链表结点friend class Stack;public:T data;LinkNode *next; class Stackprivate:LinkNode *top;/指向第一个结点的栈顶指针public:Stack();/构造函数，置空栈Stack()/析构函数void Push(T e);/元素data入栈中T Pop();/栈顶元素出栈T GetPop();/取出栈顶元素void Clear();/把栈清空bool empty();/判断栈是否为空，如果为空则返回1，否则返回0; Stack:Stack()/构造函数，置空栈top=NULL; void Stack:Push(T e)/元素x入栈中LinkNode *P;P=new LinkNode;P->data=e;P->next=top;top=P; T Stack:Pop()/栈顶元素出栈T Temp;LinkNode *P;P=top;top=top->next;Temp=P->data;delete P;return Temp; T Stack:GetPop()/取出栈顶元素return top->data; void Stack:Clear()/把栈清空top=NULL; bool Stack:empty()/判断栈是否为空，如果为空则返回1，否则返回0if(top=NULL) return 1;else return 0; int move42=0,1,1,0,0,-1,-1,0;/定义当前位置移动的4个方向 void PrintPath(Stack p)/输出路径cout<<"迷宫的路径为n"cout<<"括号内的内容分别表示为(行坐标,列坐标,数字化方向,方向)n"Stack t;/定义一个栈，按从入口到出口存取路径int a,b;T data;LinkNode *temp;temp=new LinkNode;/获取空间temp->data=p.Pop();/取栈p的顶点元素，即第一个位置t.Push(temp->data);/第一个位置入栈tdelete temp;/释放空间while(!p.empty()/如果栈p非空，则反复转移temp=new LinkNode;temp->data=p.Pop();/获取下一个位置/得到行走方向a=t.GetPop().x-temp->data.x;/行坐标方向b=t.GetPop().y-temp->data.y;/列坐标方向if(a=1) temp->data.dir=1;/方向向下，用1表示else if(b=1) temp->data.dir=2;/方向向右，用2表示else if(a=-1) temp->data.dir=3;/方向向上，用3表示else if(b=-1) temp->data.dir=4;/方向向左，用4表示t.Push(temp->data);/把新位置入栈delete temp;/输出路径，包括行坐标，列坐标，下一个位置方向while(!t.empty()/栈非空，继续输出data=t.Pop();cout<<'('<<data.x<<','<<data.y<<','<<data.dir<<","/输出行坐标，列坐标switch(data.dir)/输出相应的方向 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 Restore(int *maze,int m,int n)/恢复迷宫int i,j;for(i=0;i<m+2;i+)/遍历指针for(j=0;j<n+2;j+) if(mazeij=-1)/恢复探索过位置，即把-1恢复为0mazeij=0; int* GetMaze(int &m,int &n)/返回存取迷宫的二维指针int *maze;/定义二维指针存取迷宫int i=0,j=0;cout<<"请输入迷宫的长和宽:"int a,b;cin>>a>>b;/输入迷宫的长和宽cout<<"请输入迷宫内容:(0为通路，1为墙)n"m=a;n=b;/m,n分别代表迷宫的行数和列数maze=new int *m+2;/获取长度等于行数加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;for(i=0;i<m+2;i+)mazei0=mazein+1=1;for(i=0;i<n+2;i+)maze0i=mazem+1i=1;return maze;/返回存贮迷宫的二维指针maze; bool Mazepath(int *maze,int m,int n)/寻找迷宫maze中从（0，0）到（m,n）的路径Stack q,p;/定义栈p、q,分别存探索迷宫的过程和存储路径T Temp1,Temp2; int x,y,loop;Temp1.x=1;Temp1.y=1;q.Push(Temp1);/将入口位置入栈p.Push(Temp1);maze11=-1;/标志入口位置已到达过while(!q.empty()/栈q非空，则反复探索Temp2=q.GetPop();/获取栈顶元素if(!(p.GetPop().x)=(q.GetPop().x)&&(p.GetPop().y)=(q.GetPop().y) p.Push(Temp2); /如果有新位置入栈，则把上一个探索的位置存入栈pfor(loop=0;loop<4;loop+)/探索当前位置的4个相邻位置x=Temp2.x+moveloop0;/计算出新位置x位置值y=Temp2.y+moveloop1;/计算出新位置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.dir=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;/表示查找失败，即迷宫无路经 int main()int m=0,n=0;/定义迷宫的长和宽int *maze;/定义二维指针存取迷宫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;参考文献1 严蔚敏吴伟民数据结构（C语言版）清华大学出版社，20002 文益民周学毛李健数据结构与程序设计人民邮电出版社 20083 谭浩强 C程序设计（第三版）清华大学出版设 20084 林锐韩永泉高质量程序设计指南C+/C语言第3版 200720