数据结构课程设计—迷宫求解.doc

《数据结构课程设计—迷宫求解.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计—迷宫求解.doc（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date数据结构课程设计迷宫求解数据结构课程设计迷宫求解 湖南工业大学课 程 设 计资 料 袋 计算机与通信 学院（系、部） 2009 2010 学年第 二 学期 课程名称 数据结构 指导教师 邓彬 职称 学生姓名 柏云 专业班级 软件工程 学号 09408300134 题 目 编制一个求解迷宫通路的程序 成 绩 起止日期 2010年 6 月 28日 2010年 7 月 4

2、日目 录 清 单序号材 料 名 称资料数量备 注1课程设计任务书12课程设计说明书13课程设计图纸1张456 湖南工业大学课程设计任务书2009 2010 学年第 二 学期 计算机与通信 学院（系、部） 软件工程 专业 091 班级课程名称： 数据结构 设计题目： 编制一个求解迷宫通路的程序 完成期限：自 2010 年 6 月 28日至 2010 年 7 月 4 日共 1 周内容及任务一、设计的主要技术参数使用栈机制模拟迷宫的寻路过程, 图的DFS 自动生成随机迷宫地图.二、设计任务使用C语言实现各个模块的功能.三、设计工作量 汪婷负责实现迷宫的寻路算法以及栈机制等的实现, 柏云负责迷宫地图自

3、生成算法,以及游戏功能,友好界面等的实现.进度安排起止日期工作内容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数据测试、形成文档主要参考资料指导教师（签字）： 年 月 日系（教研室）主任（签字）： 年 月 日-数据结构设计说明书数据结构课程设计编制一个求解迷宫通路的程序起止日期： 2010 年 6 月 28日 至 2010年 7 月 4 日学生姓名柏云班级软件091班学号09408300134成绩指导教师

4、(签字)计算机与通信学院（部）年 月 日湖南工业大学课程设计情况分析表课程设计名称数据结构设计周数17周学院（部）计算机与通信学院系（教研室）软件工程系指导教师邓彬学生专业、班级软件工程0901选题设计一个迷宫生成算法成绩分布优良中及格不及格学生数百分比学生课程设计存在的主要问题改进措施及建议指导教师（签字）： 年 月 日系（教研室）主任（签字）： 年 月 日备注：本表在课程设计完成后由指导教师填写，与课程设计资料一起存档。 目录1. 题目及需求分析 VI2. 概要设计 VII3. 详细设计 X4. 调试分析 XIX5. 用户手册 XXI6. 测试结果 XXIII7. 附录 程序清单 XXV题

5、目:编制一个求解迷宫通路的程序.扩展:增加迷宫地图的随机生成;增加人工操作游戏功能;可显示迷宫通路.一 . 需求分析( 1 ) 以二维数组的形式存储迷宫地图, 0 代表通路 , 1 代表墙壁 , 2 代表已走过的足迹 , 3 代表 死路 ,以上 用宏定义如下:( 2 ) 设计交互界面 , 用户只需输入选择就可做想做的事情.( 3 ) 用户可以自己输入迷宫的大小 , 然后由程序自动生成随机迷宫.( 4 ) 求出迷宫通路并且打印在屏幕上.( 5 ) 用户可以通过方向键控制小人自己走出迷宫.( 6 ) 使用文件存储迷宫的 矩阵表示 以及 图形表示.二 . 概要设计1. 设定栈的抽象数据类型定义 :A

6、DT 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 以存在操作结果 : 获取栈顶元素Push(SqStack &s,SElemType &e)初始条件 : 栈 s 以存在操作结果 : 在栈顶插入新元素Pop(SqStack &s,SElemType &e)初始条件 : 栈 s 以存在操作结果 : 删除栈顶元素,并删除e值St

7、ackEmpty(SqStack s)初始条件 : 栈 s 以存在操作结果 : 判断栈是否为空ClearStack(SqStack &s)初始条件 : 栈 s 以存在操作结果 : 将栈置为空栈 ADT SqStack;2. 设定迷宫的抽象数据类型ADT MazeType数据对象 : D=ai,j|ai,j ,#、*，0=i=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

8、,int a,int row,int col)初始条件: 数组a 中存放了迷宫的矩阵表示,row 和 col 为迷宫的大小操作结果: 将数组 a 复制到迷宫类型的 数组 arr 中,并保存迷宫的行和列Status Pass(MazeType &maze,PosType curpos)初始条件: maze 存在迷宫, curpos 保存了当前位置的坐标操作结果: 如果可通,返回真,否则为假Status FootPrint(MazeType &maze,PosType curpos)初始条件: maze 存在迷宫, curpos 保存了当前位置的坐标操作结果: 将当前坐标curpos处的arr值记

9、为 足迹Status MarkPrint(MazeType &maze,PosType curpos)初始条件: maze 存在迷宫, curpos 保存了当前位置的坐标操作结果: 将当前坐标curpos处的arr值记为 死路SElemType CreateSElem(int step,PosType pos,DirectiveType di)初始条件: 各参数值都已经定义操作结果: 为要走的当前位置生成一个栈元素类型PosType &NextPos(PosType curpos,DirectiveType di)初始条件: 各参数值已经定义操作结果: 求得以当前位置为栈顶的下一个方向的元素的

10、坐标Status PosEquare(PosType pos1,PosType pos2)初始条件: 个参数值已经定义操作结果: 判断是否为同一位置,是则返回真, 否则为假.void PrintMaze(MazeType maze)初始条件: maze 存在迷宫地图操作结果: 在屏幕上打印出迷宫的可用路径Status MazePath(MazeType &maze,PosType start,PosType end) 初始条件: maze 存在迷宫地图操作结果: 为建立的迷宫找到一条路径ADT MazeType;3. 本程序包含6个模块1) 主程序模块:int main()主菜单函数, 实现时

11、间循环.return 0;/主函数2) 栈模块-实现栈抽象数据类型3) 迷宫模块-实现迷宫抽象数据类型4) 迷宫随机地图生成模块-用户自定义迷宫地图的生成5) 菜单模块-实现与用户交互菜单6) 游戏模块-实现游戏功能各模块之间的调用如下:主程序模块 菜单模块游戏模块迷宫模块迷宫生成模块 栈模块4. 求解迷宫通路的伪码算法:设定当前位置的初值为入口位置;Do若当前位置可通,则将当前位置插入栈顶;/纳入路径若该位置为出口位置,则结束;/求的路径存放在栈中否则切换当前位置的东邻方块为新的当前位置;否则若栈不空且栈顶位置还有其他位置没有被探索,则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相

12、邻块.若栈不空但栈顶位置的四周均不可通,则删去栈顶位置;/后退一步,从路径中删去该通道快若栈不空,则重新测试新的栈顶位置,直到找到一个可通的相邻块或出栈至空栈;while ( 栈不空 ); 栈空说明没有路径存在 三. 详细设计工程文件视图: 类视图:-头文件设计-1. my_Stack.h 文件 #ifndef MY_STACK_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_

13、SIZE 100#define STACKINCREMENT 10typedef int Status;typedef int DirectiveType; typedef struct int row;int col;PosType;typedef struct /栈中的数据元素类型int step;PosType seat;DirectiveType di;SElemType;typedef struct /栈结构SElemType *base;SElemType *top;int stacksize;SqStack; /-栈的基本操作-/初始化Status InitStack(SqSta

14、ck &s);/得到栈顶元素Status GetTop(SqStack s,SElemType &e);/入栈Status Push(SqStack &s,SElemType &e);/出栈Status Pop(SqStack &s,SElemType &e);/判断栈是否为空int StackEmpty(SqStack s);/清空栈Status ClearStack(SqStack &s);#endif2. my_Maze_Create.h 文件#ifndef MY_MAZE_CREATE_H#define MY_MAZE_CREATE_H#define MAZE_MAX 155/路径查找

15、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 * 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 RA

16、NGE 300 /迷宫最大限制#define ROAR 0/迷宫中点可通点#define WALL 1/墙#define ETR 2/已走过的足迹#define JAM 3/死路typedef struct int x,y; /迷宫的实际行、列int arrRANGERANGE; /迷宫最多的行列，限定作用MazeType;/-迷宫的基本操作-/初始化迷宫Status InitMaze(MazeType &maze,int aMAZE_MAX * 2MAZE_MAX * 2,int row,int col);/判断当前位置是否可通Status Pass(MazeType &maze,PosTy

17、pe curpos);/可通标记 Status FootPrint(MazeType &maze,PosType curpos);/不可通标记 Status MarkPrint(MazeType &maze,PosType curpos);/为要走的当前位置生成一个栈元素类型SElemType CreateSElem(int step,PosType pos,DirectiveType di);/求得以当前位置为栈顶的下一个方向的元素的坐标PosType &NextPos(PosType curpos,DirectiveType di);/判断是否为同一位置Status PosEquare(P

18、osType pos1,PosType pos2);/打印迷宫void PrintMaze(MazeType maze);/为建立的迷宫找到一条路径Status MazePath(MazeType &maze,PosType start,PosType end) ;#endif4. MazePlay.h 文件#ifndef MAZEPLAY_H#define MAZEPLAY_H/获取 方向键 响应事件int getPos();/移动 小人 的位置Status MovePos ( MazeType &maze, int pos );/判断按键方向是否可以移动bool isMoveable (

19、MazeType &maze ,PosType pos);/显示 当前位置的状态1void disPlay ( MazeType &maze, PosType pos );/显示 当前位置的状态2void disPlay_2 ( MazeType &maze, PosType pos );/游戏主事件int playMain ( MazeType &maze );#endif5. Main_Menu.h 文件#ifndef MAIN_MENU_H#define MAIN_MENU_Htypedef struct PosType start;PosType end;EtrANdOutPos;/菜

20、单显示1void displayMenu_1 ();/菜单显示2void displayMenu_2 ();/菜单调节void displayMenu_3 ();/自定义迷宫EtrANdOutPos creatPsnMaze (int mazeMapMAZE_MAX * 2MAZE_MAX * 2 , MazeType &maze );/主选择菜单int MainChoiceMenu();/光标移动void gotoxy(int x, int y);#endif6. myHeader.h 主包含头文件#include #include #include #include #include #i

21、nclude #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;-实现文件(部分)-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 d4

22、2=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*dnext1=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; f

23、or(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,rand()%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 )生成随机迷宫地图文件

24、并读取;2. my_Maze.cpp文件/打印迷宫void PrintMaze(MazeType maze)打印迷宫路径地图;/为建立的迷宫找到一条路径Status MazePath(MazeType &maze,PosType start,PosType end)SqStack s;SElemType e;InitStack(s);PosType curpos=start;curstep = 1;doif(Pass(maze,curpos)FootPrint(maze,curpos);e=CreateSElem(curstep,curpos,1);Push(s,e);if(PosEquare

25、(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( 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 isMoveable ( MazeType &maze ,PosType