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

122839855 贡献于2018-06-08

作者 Administrators  创建于2018-06-07 07:43:00   修改者陈  修改于2018-06-07 07:43:00字数6186

文档摘要:计算机解迷宫问题通常用的是“穷举求解”方法,即从入口出发,顺着某一个方向进行探索,若能走通,则继续往前进;否则沿着原路退回,换一个方向继续探索,直至出口位置,求得一条通路。
关键词:

 计算机解迷宫问题通常用的是“穷举求解”方法,即从入口出发,顺着某一个方向进行探索,若能走通,则继续往前进;否则沿着原路退回,换一个方向继续探索,直至出口位置,求得一条通路。假如所有可能的通路都探索到而未能到达出口,则所设定的迷宫没有通路。迷宫的入口点的下标为(1,1),出口点的下标为(m,n)。为处理方便起见,可在迷宫的四周加一圈障碍。对于迷宫的任一位置,均可约定有东、南、西、北四个方向可通。有一种简单走出迷宫的方法,把手放在右边的墙上开始前进,始终不要把手从墙上移开。如果迷宫向右拐,你也顺着墙向右拐。只要不把手从墙上移开,最终就会到达迷宫的出口。当然这样得到的路径可能不是一个最短的路径,但它可以最终得到结果,换句话说,这种方法走不出迷宫的风险是最小的。 本设计是为了实现一个可视化迷宫,以及利用最短路径算法寻找迷宫的出路以及将最短路径打印在屏幕上,并且限制小老鼠不能穿越墙,只能在路径上移动。而且可以根据自己的需要设计迷宫地图。 关键词 迷宫;栈;VC++ 6.0 目录 1 课设题目 1 1.1课设题目………………………………………………………………………………….1 1.2基本要求:……………………………………………………………………………….1 1.3 需求分析…………………………………………………………………………………1 2 程序总体设计 2 2.1流程图:………………………………………………………………………………….2 2.2概要设计………………………………………………………………………………….6 2.3 运行结果及分析…………………………………………………………………………7 总结 9 源程序 10 参考文献 20 1 课设题目 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函数流程图 显示系统信息 选择获取迷宫的方式ch Ch==’ b’ Ch==’a’ Readfile()文件读取 自行输入 Writefile() 探索迷宫路径是否存在 输出迷宫路径 是否继续游戏 退出 开始 2.探索路径函数findpath() Temp1.x=1 Temp1.y=1 入口进栈p.push q.push 是否非空 temp2=q.getpop() P q栈顶是否相等 探索上下左右四个方位是否有路径 到达新位置 是否到达出口 最后一个元素进栈输出路径 回复以改变的迷宫 结束 开始 3.自行输入迷宫函数writefile() 输入长宽m,n 动态申请空间二位数组空间 i<=m 是否保存迷宫 J<=n i++ ;j++ 输入迷宫 输入保存迷宫的文件名 保存迷宫 结束 2.2概要设计 1.①构建一个二维数组maze[M+2][N+2]用于存储迷宫矩阵 ②自动或手动生成迷宫,即为二维数组maze[M+2][N+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 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 Stack { private: 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,否则返回0 { if(top==NULL) return 1; else return 0; } int move[4][2]={{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);//第一个位置入栈t delete 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<<'('<>a>>b;//输入迷宫的长和宽 cout<<"请输入迷宫内容:(0为通路,1为墙)\n"; m=a; n=b;//m,n分别代表迷宫的行数和列数 maze=new int *[m+2];//获取长度等于行数加2的二级指针 for(i= 0;i>maze[i][j]; for(i=0;i

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 10 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档