数据结构课程设计-迷宫求解

《数据结构课程设计-迷宫求解》由会员分享，可在线阅读，更多相关《数据结构课程设计-迷宫求解（25页珍藏版）》请在装配图网上搜索。

1、 湖南工业大学课 程 设 计资 料 袋 计算机与通信 学院（系、部） 2009 2010 学年第 二 学期 课程名称 数据结构 指导教师 邓彬 职称 学生姓名 柏云 专业班级 软件工程 学号 题 目 编制一个求解迷宫通路的程序 成 绩 起止日期 2010年 6 月 28日 2010年 7 月 4 日目 录 清 单序号材 料 名 称资料数量备 注1课程设计任务书12课程设计说明书13课程设计图纸1张456 湖南工业大学课程设计任务书2009 2010 学年第 二 学期 计算机与通信 学院（系、部） 软件工程 专业 091 班级课程名称： 数据结构 设计题目： 编制一个求解迷宫通路的程序 完成期限

2、：自 2010 年 6 月 28日至 2010 年 7 月 4 日共 1 周内容及任务一、设计的主要技术参数使用栈机制模拟迷宫的寻路过程, 图的DFS 自动生成随机迷宫地图.二、设计任务使用C语言实现各个模块的功能.三、设计工作量 汪婷负责实现迷宫的寻路算法以及栈机制等的实现, 柏云负责迷宫地图自生成算法,以及游戏功能,友好界面等的实现.进度安排起止日期工作内容2010-6-28-2010-6-29设计本程序思路2010-6-29-2010-7-1实现子程序模块函数2010-7-1 -2010-7-2将子程序和主程序构建成完整的C源程序，并且进行相关编译调试2010-7-2 -2010-7-4

3、数据测试、形成文档主要参考资料指导教师（签字）： 年 月 日系（教研室）主任（签字）： 年 月 日数据结构设计说明书数据结构课程设计编制一个求解迷宫通路的程序起止日期： 2010 年 6 月 28日 至 2010年 7 月 4 日学生姓名柏云班级软件091班学号成绩指导教师(签字)计算机与通信学院（部）年 月 日湖南工业大学课程设计情况分析表课程设计名称数据结构设计周数17周学院（部）计算机与通信学院系（教研室）软件工程系指导教师邓彬学生专业、班级软件工程0901选题设计一个迷宫生成算法成绩分布优良中及格不及格学生数百分比学生课程设计存在的主要问题改进措施及建议指导教师（签字）： 年 月 日系

4、（教研室）主任（签字）： 年 月 日备注：本表在课程设计完成后由指导教师填写，与课程设计资料一起存档。 目录1. 题目及需求分析 VI2. 概要设计 VII3. 详细设计 X4. 调试分析 XIX5. 用户手册 XXI6. 测试结果 XXIII7. 附录 程序清单 XXV题目:编制一个求解迷宫通路的程序.扩展:增加迷宫地图的随机生成;增加人工操作游戏功能;可显示迷宫通路.一 . 需求分析( 1 ) 以二维数组的形式存储迷宫地图, 0 代表通路 , 1 代表墙壁 , 2 代表已走过的足迹 , 3 代表 死路 ,以上 用宏定义如下:( 2 ) 设计交互界面 , 用户只需输入选择就可做想做的事情.(

5、 3 ) 用户可以自己输入迷宫的大小 , 然后由程序自动生成随机迷宫.( 4 ) 求出迷宫通路并且打印在屏幕上.( 5 ) 用户可以通过方向键控制小人自己走出迷宫.( 6 ) 使用文件存储迷宫的 矩阵表示 以及 图形表示.二 . 概要设计1. 设定栈的抽象数据类型定义 :ADT Stack 数据对象 : D=ai|aiADT MazeType , i = 0,1,2n , n0数据关系 : R1= | ai-1,ai D,i=2,n 基本操作 :InitStack(SqStack &s)操作结果 : 构造一个空栈GetTop(SqStack s,SElemType &e)初始条件 : 栈 s

6、以存在操作结果 : 获取栈顶元素Push(SqStack &s,SElemType &e)初始条件 : 栈 s 以存在操作结果 : 在栈顶插入新元素Pop(SqStack &s,SElemType &e)初始条件 : 栈 s 以存在操作结果 : 删除栈顶元素,并删除e值StackEmpty(SqStack s)初始条件 : 栈 s 以存在操作结果 : 判断栈是否为空ClearStack(SqStack &s)初始条件 : 栈 s 以存在操作结果 : 将栈置为空栈 ADT SqStack;2. 设定迷宫的抽象数据类型ADT MazeType数据对象 : D=ai,j|ai,j ,#、*，0=i=

7、m+1, 0=j=n+1,m,n=10数据关系 : R=ROW,COLROW=|ai-1,j,ai,jD,i=1,m+1,j=0,n+1COW=|ai-1,j,ai,jD,i=1,m+1,j=0,n+1基本操作 :Status InitMaze(MazeType &maze,int a,int row,int col)初始条件: 数组a 中存放了迷宫的矩阵表示,row 和 col 为迷宫的大小操作结果: 将数组 a 复制到迷宫类型的 数组 arr 中,并保存迷宫的行和列Status Pass(MazeType &maze,PosType curpos)初始条件: maze 存在迷宫, curp

8、os 保存了当前位置的坐标操作结果: 如果可通,返回真,否则为假Status FootPrint(MazeType &maze,PosType curpos)初始条件: maze 存在迷宫, curpos 保存了当前位置的坐标操作结果: 将当前坐标curpos处的arr值记为 足迹Status MarkPrint(MazeType &maze,PosType curpos)初始条件: maze 存在迷宫, curpos 保存了当前位置的坐标操作结果: 将当前坐标curpos处的arr值记为 死路SElemType CreateSElem(int step,PosType pos,Directi

9、veType di)初始条件: 各参数值都已经定义操作结果: 为要走的当前位置生成一个栈元素类型PosType &NextPos(PosType curpos,DirectiveType di)初始条件: 各参数值已经定义操作结果: 求得以当前位置为栈顶的下一个方向的元素的坐标Status PosEquare(PosType pos1,PosType pos2)初始条件: 个参数值已经定义操作结果: 判断是否为同一位置,是则返回真, 否则为假.void PrintMaze(MazeType maze)初始条件: maze 存在迷宫地图操作结果: 在屏幕上打印出迷宫的可用路径Status Maz

10、ePath(MazeType &maze,PosType start,PosType end) 初始条件: maze 存在迷宫地图操作结果: 为建立的迷宫找到一条路径ADT MazeType;3. 本程序包含6个模块1) 主程序模块:int main()主菜单函数, 实现时间循环.return 0;/主函数2) 栈模块-实现栈抽象数据类型3) 迷宫模块-实现迷宫抽象数据类型4) 迷宫随机地图生成模块-用户自定义迷宫地图的生成5) 菜单模块-实现与用户交互菜单6) 游戏模块-实现游戏功能各模块之间的调用如下:主程序模块 菜单模块游戏模块迷宫模块迷宫生成模块 栈模块4. 求解迷宫通路的伪码算法:设

11、定当前位置的初值为入口位置;Do若当前位置可通,则将当前位置插入栈顶;/纳入路径若该位置为出口位置,则结束;/求的路径存放在栈中否则切换当前位置的东邻方块为新的当前位置;否则若栈不空且栈顶位置还有其他位置没有被探索,则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块.若栈不空但栈顶位置的四周均不可通,则删去栈顶位置;/后退一步,从路径中删去该通道快若栈不空,则重新测试新的栈顶位置,直到找到一个可通的相邻块或出栈至空栈;while ( 栈不空 ); 栈空说明没有路径存在 三. 详细设计工程文件视图: 类视图:-头文件设计-1. my_Stack.h 文件 #ifndef MY_STA

12、CK_H#define MY_STACK_H#define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int Status;typedef int DirectiveType; typedef struct int row;int col;PosType;typedef struct /栈中的数据元素类型int step;PosType sea

13、t;DirectiveType di;SElemType;typedef struct /栈结构SElemType *base;SElemType *top;int stacksize;SqStack; /-栈的基本操作-/初始化Status InitStack(SqStack &s);/得到栈顶元素Status GetTop(SqStack s,SElemType &e);/入栈Status Push(SqStack &s,SElemType &e);/出栈Status Pop(SqStack &s,SElemType &e);/判断栈是否为空int StackEmpty(SqStack s

14、);/清空栈Status ClearStack(SqStack &s);#endif2. my_Maze_Create.h 文件#ifndef MY_MAZE_CREATE_H#define MY_MAZE_CREATE_H#define MAZE_MAX 155/路径查找int search(int mapMAZE_MAX+2MAZE_MAX+2,int x,int y);/迷宫生成void Make_Maze(int mapMAZE_MAX+2MAZE_MAX+2,int x,int y);/生成迷宫文件void Maze_File_Make (int mazeMapMAZE_MAX *

15、2MAZE_MAX * 2,int x,int y );#endif3. my_Maze.h 文件#ifndef MY_MAZE_H#define MY_MAZE_H#include my_Stack.h#include my_Maze_Create.h#define RANGE 300 /迷宫最大限制#define ROAR 0/迷宫中点可通点#define WALL 1/墙#define ETR 2/已走过的足迹#define JAM 3/死路typedef struct int x,y; /迷宫的实际行、列int arrRANGERANGE; /迷宫最多的行列，限定作用MazeType;

16、/-迷宫的基本操作-/初始化迷宫Status InitMaze(MazeType &maze,int aMAZE_MAX * 2MAZE_MAX * 2,int row,int col);/判断当前位置是否可通Status Pass(MazeType &maze,PosType curpos);/可通标记 Status FootPrint(MazeType &maze,PosType curpos);/不可通标记 Status MarkPrint(MazeType &maze,PosType curpos);/为要走的当前位置生成一个栈元素类型SElemType CreateSElem(int

17、 step,PosType pos,DirectiveType di);/求得以当前位置为栈顶的下一个方向的元素的坐标PosType &NextPos(PosType curpos,DirectiveType di);/判断是否为同一位置Status PosEquare(PosType pos1,PosType pos2);/打印迷宫void PrintMaze(MazeType maze);/为建立的迷宫找到一条路径Status MazePath(MazeType &maze,PosType start,PosType end) ;#endif4. MazePlay.h 文件#ifndef

18、MAZEPLAY_H#define MAZEPLAY_H/获取 方向键 响应事件int getPos();/移动 小人 的位置Status MovePos ( MazeType &maze, int pos );/判断按键方向是否可以移动bool isMoveable ( MazeType &maze ,PosType pos);/显示 当前位置的状态1void disPlay ( MazeType &maze, PosType pos );/显示 当前位置的状态2void disPlay_2 ( MazeType &maze, PosType pos );/游戏主事件int playMain

19、 ( MazeType &maze );#endif5. Main_Menu.h 文件#ifndef MAIN_MENU_H#define MAIN_MENU_Htypedef struct PosType start;PosType end;EtrANdOutPos;/菜单显示1void displayMenu_1 ();/菜单显示2void displayMenu_2 ();/菜单调节void displayMenu_3 ();/自定义迷宫EtrANdOutPos creatPsnMaze (int mazeMapMAZE_MAX * 2MAZE_MAX * 2 , MazeType &m

20、aze );/主选择菜单int MainChoiceMenu();/光标移动void gotoxy(int x, int y);#endif6. myHeader.h 主包含头文件#include #include #include #include #include #include #include #include my_Stack.h#include my_Maze.h#include my_Maze_Create.h#include Main_Menu.h#include MazePlay.h#include #include using namespace std;-实现文件(部分

21、)-1. my_Maze_Create.cpp 文件#include myHeader.hint mapMAZE_MAX+2MAZE_MAX+2;int search(int mapMAZE_MAX+2MAZE_MAX+2,int x,int y)static int d42=0,1,1,0,0,-1,-1,0; int zx=x*2,zy=y*2,next,turn,i; mapzxzy=1;turn = rand()%2 ? 1 : 3; for(i=0,next=rand()%4; i4; i+,next=(next+turn)%4) if(mapzx+2*dnext0zy+2*dnex

22、t1=0) mapzx+dnext0zy+dnext1=1;search(map,x+dnext0,y+dnext1);return 0;void Make_Maze(int mapMAZE_MAX+2MAZE_MAX+2,int x,int y) int z1,z2; for(z1=0,z2=2*y+2;z1=2*x+2;z1+)mapz10=1,mapz1z2=1; for(z1=0,z2=2*x+2;z1=2*y+2;z1+)map0z1=1,mapz2z1=1; map12=1;map2*x+12*y=1;srand(unsigned)time(NULL); search(map,ra

23、nd()%x+1,rand()%y+1);map10 = 1;mapx-2y-1 = 1;/生成迷宫文件 C 实现void Maze_File_Make (int mazeMapMAZE_MAX * 2MAZE_MAX * 2,int x,int y )生成随机迷宫地图文件并读取;2. my_Maze.cpp文件/打印迷宫void PrintMaze(MazeType maze)打印迷宫路径地图;/为建立的迷宫找到一条路径Status MazePath(MazeType &maze,PosType start,PosType end)SqStack s;SElemType e;InitStac

24、k(s);PosType curpos=start;curstep = 1;doif(Pass(maze,curpos)FootPrint(maze,curpos);e=CreateSElem(curstep,curpos,1);Push(s,e);if(PosEquare(curpos,end)return TURE;curpos=NextPos(curpos,1);curstep+;elseif(!StackEmpty(s)Pop(s,e);while(e.di = 4 & !StackEmpty(s)MarkPrint(maze,e.seat);Pop(s,e);curstep-;if(

25、 e.di 4 )e.di +;Push(s,e);curpos=NextPos(e.seat,e.di);while(!StackEmpty(s);return FALSE;3. MazePlay.cpp文件#include myHeader.hPosType start;PosType end;PosType curPos;PosType prePos;int getPos()pos = 键位标识符;return pos;Status MovePos ( MazeType &maze, int pos )switch(pos)case : 向pos方向移动;return 0;bool is

26、Moveable ( MazeType &maze ,PosType pos)if ( maze.arrpos.rowpos.col = 1 )return false;return true;void disPlay ( MazeType &maze, PosType pos )显示迷宫; void disPlay_2 ( MazeType &maze, PosType pos )显示小人的当前位置;4. main.cpp 主函数#include myHeader.hint main()/主菜单MainChoiceMenu();return 0;/主函数函数调用关系图如下:四: 调试分析1.

27、 本次作业比较简单 , 只是后期在原来的程序上做了许多扩展, 如实现随机迷宫地图的自动生成 和 游戏模式. 初期的调试总是输出 “没有找到路径”, 但是迷宫的路径确实是存在的,后来发现是由于迷宫的自生成算法与输入有些不一致, 更正了行列顺序后,程序能正常运行.2. 在设计迷宫初始化函数的时候,参数的传递出现错误,主要是对指针和引用的理解出现混淆,通过查阅相关资料, 弄清楚了两者之间的区别,指针是用于指向一个变量的地址,而引用只是对一个已存在变量的一个重命名.3. 在调试过程中使用printf函数输出标志信息跟踪函数调用,收到了显著的效果,大大提高了调试效率,有利于以后的代码调试.4. 使用了小

28、部分的win32 API,发现使用局部句柄时,调用的winAPI不能正常运行,改成全局后问题解决.5. 程序源代码中仍有部分重复代码,可以模块化,实现代码重用.6. 在实现游戏功能时发现,每次调用disPlay 函数时都进行清屏操作,屏幕的闪动幅度非常大,眼睛很容易疲劳, 第一次改进后, 去除了清屏操作,而采用覆盖式的输出 ,即在原来已有的画面上再次打印.经过这次改进, 界面趋向与稳定,但是,在进行高频率按键时,仍然可以发现有较小的闪动现象.经过思考,发现迷宫地图是不变的,只要重画改变部分就可以了,再次改进后,游戏时已经没有闪屏现象出现.代码中的主要算法 : Make_Maze的时间复杂度为

29、O( n * logn ), MazePath 的时间复杂度为O( n * m ).7. 经验体会: 使用模块化操作易于代码的调试和修改,而且易于阅读.在设计实现过程中虽然遇到了很多问题,但是在解决这些问题的过程中,巩固和加深了我们对已学知识的理解,对团队合作有了一个比较基础的认识,为以后的工作实践打下了基础.五.用户手册1.本程序的运行环境为 DOS 操作系统, 执行文件为MazeProgramming.exe.2.进入演示程序后 , 即显示文本方式的用户界面:操作提示信息操作命令清单键入选择3. 进入”建立自定义迷宫” 命令后, 根据提示输入 迷宫的行和列,回车后即可得到”迷宫建立完成”的

30、提示信息.数据不合要求,如( 0 , 0 ),则会提示: 本程序设置的数据范围为行列 均在 1 49 之间.4. 进入 “输出迷宫路径” 命令后, 程序 立即会显示先前生成迷宫的可通路径,如果迷宫还未生成,则会提示用户”迷宫未生成”.5. 进入 “试玩当前迷宫” 命令后, 用户只需控制方向键就可移动小人玩此游戏, 游戏中途可按 ESC建 随时退出.成功完成迷宫后,会输出用户的游戏时间和所走步数.此为出口6. 输入 “0” 即可退出此演示程序.六. 测试结果1. 根据提示输入4,10. 生成迷宫如下 :1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0

31、 0 1 1 0 1 0 1 1 1 0 1 1 1 0 1 1 0 1 0 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 0 0 1 0 1 0 1 0 0 0 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 0 1 0 0 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 1 0 1 0 1 1 0 1 0 1 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1求解后的路径如下:2. 输入第二组测试数据 7,8:求解后路径如下 :七. 附录 程序清单: