迷宫游戏数据结构课程设计大学论文.doc

《迷宫游戏数据结构课程设计大学论文.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、计算机解迷宫问题通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。迷宫的入口点的下标为（1，1），出口点的下标为（m，n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫的任一位置，均可约定有东、南、西、北四个方向可通。有一种简单走出迷宫的方法，把手放在右边的墙上开始前进，始终不要把手从墙上移开。如果迷宫向右拐，你也顺着墙向右拐。只要不把手从墙上移开，最终就会

2、到达迷宫的出口。当然这样得到的路径可能不是一个最短的路径，但它可以最终得到结果，换句话说，这种方法走不出迷宫的风险是最小的。本设计是为了实现一个可视化迷宫，以及利用最短路径算法寻找迷宫的出路以及将最短路径打印在屏幕上，并且限制小老鼠不能穿越墙，只能在路径上移动。而且可以根据自己的需要设计迷宫地图。关键词迷宫；栈；VC++6.0目录1课设题目11.1课设题目………………………………………………………………………………….11.2基本要求：……………………………………………………………………………….11.3需求分析…………………………

3、………………………………………………………12程序总体设计22.1流程图：………………………………………………………………………………….22.2概要设计………………………………………………………………………………….62.3运行结果及分析…………………………………………………………………………7总结9源程序10参考文献201课设题目1.1课设题目编写一个程序求解迷宫问题。迷宫由m行n列的二维数组设置，0表示无障碍，1表示有障碍。设入口为（1，1），出口为（m，n），每次只能从一个无障碍单元移到周围四个方向上任一无障碍单元。编程实现

4、对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。算法输入：代表迷宫入口的坐标算法输出：穿过迷宫的结果。算法要点：创建迷宫，试探法查找路径，输出解1.2基本要求：1.求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一个坐标的方向。2.输出迷宫示意图1.3需求分析1、本程序实现迷宫的探索过程.以用户和计算机对话的方式，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，然后程序就探索路径并输出路径。2、本演示程序中，输入形式以“回车符”为结束

5、标志，且允许出现重复字符。3、利用二维指针实现迷宫位置的存储，并用栈存贮探索路径，每个结点含三个整形变量。输入的形式以回车结束。4、本程序中，用户可以读去文件里的迷宫，也可自己重新输入迷宫，而且用户可以输入任意大小的迷宫，然后程序自动探索路径，并输出迷宫的路径。202程序总体设计2.1流程图：1.功能结构图Main主函数模块输出路径模块printpath（）获取迷宫模块探索路径模块Findpath（）存储探索路径模块stack类读文件Readfile（）写文件Writefile（）Stack类数据模块操作模块盘空函数isempty（

6、）清空函数clear（）取栈顶函数getpop（）进栈与出栈函数push（）Pop（）构造与析构函数stack（）~stack（）结点模块Node*top结点数据类型模块datatype类202.画出主要数据结构的类图class类名DataType//定义描述迷宫中当前位置的类型数据成员访问控制权限数据类型变量名;public:intx;//x代表当前位置的行坐标inty;//y代表当前位置的列坐标intdir;//dir表示移动到下一步的方向class类名Move//定义下一个位置的方向数据成员访问控制权限数据类型变量名;publ

7、ic:intx;inty;class类名Node//结点数据成员访问控制权限数据类型变量名;public:DataTypedata;Node*next;class类名stack数据成员访问控制权限数据类型变量名;private:Node*top;//指向第一个结点的栈顶指针成员函数访问控制权限返回值类型函数名(参数列表)public:stack();//构造函数，置空栈~stack();//析构函数voidPush(DataTypedata);//把元素data压入栈中DataTypePop();//使栈顶元素出栈DataTypeG

8、etPop();//取出栈顶元素voidClear();//把栈清空boolIsEmpty();//判断栈是否为空，如果为空则返回1，否则返回020开始3.main函数流程图显示系统信息选择获取迷宫的方式chCh==’b’Ch==’a