《迷宫游戏数据结构课程设计.doc》由会员分享，可在线阅读，更多相关《迷宫游戏数据结构课程设计.doc（23页珍藏版）》请在金锄头文库上搜索。
1、计算机解迷宫问题通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。迷宫的入口点的下标为（1，1），出口点的下标为（m，n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫的任一位置，均可约定有东、南、西、北四个方向可通。有一种简单走出迷宫的方法，把手放在右边的墙上开始前进，始终不要把手从墙上移开。如果迷宫向右拐，你也顺着墙向右拐。只要不把手从墙上移开，最终就会到达迷宫的出口。当然这样得到的路径可能不是一个最短的路径，但它
2、可以最终得到结果，换句话说，这种方法走不出迷宫的风险是最小的。本设计是为了实现一个可视化迷宫，以及利用最短路径算法寻找迷宫的出路以及将最短路径打印在屏幕上，并且限制小老鼠不能穿越墙，只能在路径上移动。而且可以根据自己的需要设计迷宫地图。关键词 迷宫；栈；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），每
3、次只能从一个无障碍单元移到周围四个方向上任一无障碍单元。编程实现对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。算法输入：代表迷宫入口的坐标算法输出：穿过迷宫的结果。算法要点：创建迷宫，试探法查找路径，输出解1.2基本要求：1.求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一个坐标的方向。2.输出迷宫示意图1.3 需求分析1、本程序实现迷宫的探索过程. 以用户和计算机对话的方式，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，然后程序就探索路径并输出路径。 2、本演示程序中，输入形式以“回车符
4、”为结束标志，且允许出现重复字符。3、利用二维指针实现迷宫位置的存储，并用栈存贮探索路径，每个结点含三个整形变量。输入的形式以回车结束。4、本程序中，用户可以读去文件里的迷宫，也可自己重新输入迷宫，而且用户可以输入任意大小的迷宫，然后程序自动探索路径，并输出迷宫的路径。2 程序总体设计2.1流程图：1.功能结构图Main主函数模块输出路径模块printpath（）获取迷宫模块探索路径模块Findpath（）存储探索路径模块stack类读文件Readfile（）写文件Writefile（）Stack类数据模块操作模块盘空函数isempty（）清空函数clear（）取栈顶函数getpop（）进栈与
5、出栈函数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 /结点数据成员访问控制权限 数据类型
6、变量名; 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();
7、 /判断栈是否为空，如果为空则返回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是否保存迷宫
8、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)访问节
9、点 visit()(8)搜索迷宫路径 mgpath()2.3 运行结果及分析 总结通过这段时间的数据结构课程设计，本人对计算机的应用，数据结构的作用以及C语言的使用都有了更深的了解。尤其是C语言的进步让我深刻的感受到任何所学的知识都需要实践，没有实践就无法真正理解这些知识以及掌握它们，使其成为自己的财富。在理论学习和上机实践的各个环节中，通过自主学习和认真听老师讲课分析，我收获了不少。当然也遇到不少的问题，也正是因为这些问题引发的思考给我带了收获。从当初不喜欢上机写程序到现在能主动写程序，从当初拿着程序不只如何下手到现在知道如何分析问题，如何用专业知识解决实际问题的转变，我发现无论是专业知识还
10、是动手能力，自己都有很大程度的提高。在这段时间里，我对for、while等的循环函数用法更加熟悉，逐渐形成了较好的编程习惯。在老师的指导帮助下，同学们课余时间的讨论中，这些问题都一一得到了解决。在程序的调试能力上，无形中得到了许多的提高。例如：头文件的使用，变量和数组的范围问题，定义变量时出现的问题等等。在实际的上机操作过程中，不仅是让我们了解数据结构的理论知识，更重要的是培养解决实际问题的能力，所以相信通过此次实习可以提高我们分析设计能力和编程能力，为后续课程的学习及实践打下良好的基础。时间过得真快，大学生活不知不觉就走过了一学期，这一学期的大学学习和课程实践阶段的提高，使我们本身知识得到提
11、高的同时，也增强了我们对未来工作的信心，我们相信自己未来两年半的学习更使我们有能力胜任将来的工作。源程序#includeusing 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:
12、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
