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

hhhhhh课程设计说明书（数据结构课程设计）专业:课程名称:数据结构课程设计班级:设计题目:走迷宫游戏设计时间:2013-2-25至2013-3-8评语:_____________________________________________________________________________________________________________________________________________________________________________________________________评阅成绩:＿＿＿＿评阅教师:＿＿hhhhhh一、问题描述与需求分析1、问题描述程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。要求：老鼠形象可辨认，可用键盘操纵老鼠上下左右移动；迷宫的墙足够结实，老鼠不能穿墙而过；正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败；添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙；找出走出迷宫的所有路径，以及最短路径；6）利用序列化功能实现迷宫地图文件的存盘和读出等功能。功能需求分析老鼠形象设计，使用图形化编程，绘制椭圆，填充颜色，绘制线。设置游戏者在探索过程中遇到迷宫边界和墙时，不可继续前行，定义好迷宫边界。使用time函数获取系统时间，处理游戏所用时间，限定操作时间，对游戏者的位置有准确的判断，当到达出口时，可以识别，返回提示信息。对于迷宫的所有路径的求解，比较最短路径，最小生成树算法。5.对迷宫的地图可将其存储到二进制文件中，在下次使用时直接调用，读取文件。二、概要设计1、总体设计思路在程序中，采用二维数组存储迷宫地图（0：墙1：路），在探索迷宫过程中采用栈的数据结构存储探索迷宫时的全部路径和有效路径，因栈的“后进先出”结构非常适合探索过程中的退步，即可以保证在任何位置都可沿原路退回。在探索迷宫过程中采用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向在继续探索，直到所有可能的通路都探索到为止。hhhhhh2、模块简介程序由以下几个模块组成：迷宫地图随机生成模块：入口：int**Maze()出口：returnmaze;实现功能：该函数使用new函数为指向二维数组的指针maze申请存储空间，分两步实现，先申请长度等于行数加2的二级指针，然后为每个二维指针申请存储空间。调用包含在头文件stdlib.h中的库函数，随机数生成器srand(),rand(),及包含在头文件time.h中的系统时间函数time(),srand((unsigned)time(NULL))使用系统时间，传入空指针NULL，作为初始化种子，使得在后面调用的rand()%2函数产生不同的随机数，取余之后为(0和1)，从而实现了迷宫地图的随机生成，但使用该方法产生的迷宫地图中不一定存在一条从入口到出口的路径。最后使用for循环嵌套给迷宫的上、下、左、右边界赋值0（为墙壁）；指定迷宫的入口与出口位置同时赋值为1（为通道）。因定义了二维指针类型函数，故在其它函数调用该函数时返回指向迷宫地图的二维指针，使得调用迷宫地图极为方便。栈操作实现模块：该模块共包含：①初始化栈，②元素入栈，③元素出栈，④删除栈顶元素，⑤栈的遍历5个函数。①初始化栈入口：intStackTraverse(SqStack*s)出口：exit(OVERFLOW);returnTRUE;实现功能：初始化一个栈，并为其分配存储空间初始量。形参为栈类型指针，调用时传递实参全局变量realPathPath地址，调用包含在头文件malloc.h中的库函数malloc根据栈的存储空间初始量及SqStack所占字节为其动态分配内存，最后，将内存地址赋给栈底指针，同时使栈顶指针也指向该内存，栈的大小为存储空间初始量；当分配失败时，返回空指针NULL，退出该函数同时输出错误提醒语句，以便调试；分配成功，返回TRUE，表明该函数已执行。hhhhhh这样做的优点是节省了内存，根据存储使用量动态分配，在使用结束后可及时释放该内存。②元素入栈入口：intPush(SqStack*s,SElemTypee)出口：exit(OVERFLOW);returnTRUE;实现功能：向栈中添加新元素。形参为栈类型指针，栈元素类型e，调用时传递实参地址及入栈元素；但需注意的是：在入栈之前要判断栈是否还有空间容纳新元素，如栈满（s->top-s->base>=s->stackSize）则应使用realloc函数为栈分配存储空间增量（STACKINCREMENT），在栈底指针base之后追加增量，同时将新的地址赋给base，此时应重新定位栈顶指针（s->top=s->base+s->stacksize;），因重新分配了空间base值已改变，所以top值也就相应的改变，才能指向新的元素；如存储分配失败，则输出提醒语句，退出函数；否则，新元素e入栈，栈顶指针top++，返回TRUE，函数正常退出。③元素出栈入口：SElemTypeGetTop(SqStack*s)出口：exit(ERROR);return*(s->top-1);实现功能：若栈非空，获取栈顶元素，并返回其值。因函数类型为栈元素类型，故可直接返回栈顶元素，需注意的是：在出栈之前要判断栈是否非空（s->top==s->base），若base值等于top值，则表明栈空，输出错误提醒语句，强制退出函数；否则，top值减1，返回栈顶元素，此时函数正常退出。④删除栈顶元素入口：intPop(SqStack*s)出口：exit(ERROR);returnTRUE;实现功能：若栈非空，则删除栈顶元素。同样，在删除元素之前需判断栈是否非空，是，则栈顶指针top--返回TRUE，函数正常退出；否（s->top==s->base），则输出错误提醒语句，强制退出函数。hhhhhh⑤栈的遍历入口：intStackTraverse(SqStack*s) 出口：returnTRUE;实现功能：逆序遍历栈，先指向栈底元素，以后依次向上增1，输出迷宫从入口到出口的路径。当base值小于top-1时执行while循环，由栈底依次向上输出栈中元素，s->base++，不满足条件时跳出while循环，此时栈底指针指向栈顶元素，输出栈中最后一个元素，即迷宫通道中的出口位置。探索迷宫操作模块：该模块共包含：①判断当前位置是否走过，②获取东面相邻位置，③获取南面相邻位置，④获取西面相邻位置，⑤获取北面相邻位置，⑥获取下一可通行位置，以及⑦获取迷宫路径函数7个函数，其中获取迷宫路径函数为主要函数，调用其他函数以实现获取迷宫路径，并将其存储到栈中。①判断当前位置是否走过入口：intUnPass(SqStackpath,SElemTypee);出口：returnflag;实现功能：在探索迷宫时，调用该函数，判断当前位置是否走过。形参为栈类型path，栈元素类型e，在调用时传递全局变量Path，即存储探索迷宫时走过的所有路径的栈，当前位置的栈元素类型；在该函数中，定义整型数flag=1作为标记，当栈Path非空时执行while循环，比较当前位置对应坐标是否与出栈元素的坐标相等，即判断当前位置是否在Path的路径中出现过，若满足条件，标记flag=0，Path.top--，即每执行一次循环，头指针下移一个位置，直到不满足条件时跳出循环，即将Path中所有元素都与当前位置作了比较；若有符合要求的，返回标记flag=0，表明该位置走过；否则，返回标记flag=1，该位置未曾走过。②获取东面相邻位置入口：SElemTypegetEast(int**m,SElemTypee)出口：returne;实现功能：获取东面相邻位置信息，返回栈元素类型，包含位置坐标，方向。形参为二维指针m，栈元素类型e，调用时传递指向迷宫地图的二维指针，及当前位置；hhhhhh注：以屏幕左上角为坐标原点，水平向右为y轴正方向，竖直向下为x轴正方向。判断当前位置未到迷宫右（东）边界时，当前位置y坐标加1（e.curpos.y+=1;），将东面相邻位置在迷宫地图中的值赋给当前位置（e.curpos.val=m[e.curpos.x][e.curpos.y];），返回e，从而实现了获取当前位置的东面相邻位置信息。③获取南面相邻位置入口：SElemTypegetSouth(int**m,SElemTypee)出口：returne;实现功能：获取南面相邻位置信息。需判断当前位置是否已到迷宫下（南）边界。x位置坐标加1（e.curpos.x+=1;）④获取西面相邻位置入口：SElemTypegetWest(int**m,SElemTypee)出口：returne;实现功能：获取西面相邻位置信息。需判断当前位置是否已到迷宫左（西）边界。y位置坐标加1（e.curpos.y+=1;）⑤获取北面相邻位置入口：SElemTypegetNorth(int**m,SElemTypee)出口：returne;实现功能：获取北面相邻位置信息。需判断当前位置是否已到迷宫上（北）边界。x位置坐标减1（e.curpos.x-=1;）⑥获取下一可通行位置入口：SElemTypeNextPos(SElemTypee)出口：returnnext;实现功能：在当前位置，向四个方向（东、南、西、北）探索，调用②、③、④、⑤函数，若相邻位置可行走，且未曾走过，则返回该位置信息，将当前位置切换到下一位置。⑦获取迷宫路径函数hhhhhh入口：intMazePath(Positionstart,Positionend);出口：returnTRUE;returnFALSE;实现功能：若迷宫Maze中存在从入口start到出口end的通道，则求得一条存放在栈中realPath(从栈底到栈顶)，并返回TRUE；否则返回FALSE。辅助函数模块：①输出迷宫地图入口：intPrintMap(int**temp);出口：returnTRUE;实现功能：在主函数中调用，传递实参指向迷宫地图的二维指针，使用for循环嵌套输出迷宫地图。②错误消息提示入口：interrormessage() 出口：returnTRUE;实现功能：错误消息提示主函数模块：入口：intmain()出口：return0;实现功能：程序执行的入口，在主函数中调用各个模块，实现程序的运行。初始化栈，Path用于存放探索迷宫时的全部路径，realPath用于存放迷宫入口到出口的有效路径；初始化游戏参数，对全局变量map入口、出口位置坐标、对应地图值（为1）进行赋值；调用迷宫地图输出函数，输出迷宫；调用获取迷宫路径函数，若存在一条路径，则存放到栈realPath；调用遍历栈函数，逆序输出栈中元素（从栈底到栈顶），即从入口位置到出口位置的一条路径。return0;主函数结束，程序运行结束。三、详细设计1、数据结构设计（1）程序中定义了迷宫的位置坐标，结构体类型Position，包含整型数x,y存储迷宫地图二维数组对应的行和列坐标，整型数val用于存储迷宫地图的值，如0和1。hhhhhh特别说明：val值是作为迷宫探索时的重要判断标记，若当前位置的四面为墙（0）或已走过，则在切换下一位置的函数NextPos中所返回val的值为-1。详细定义如下：typedefstruct{ intx;//二维数组maze下标 inty; intval;//maze[x][y]的值}Position;//游戏中的位置坐标程序中定义了结构体类型MapCfg,及对应该结构体类型全局变量map，包含上一结构体类型Position变量start,end,即迷宫的起始位置与结束位置，在调用探索迷宫函数时，传递实参起始位置，结束位置为全局变量直接调用，从而使得在判断结束位置时更加方便，但需注意的一点是：在调用之前要给起始、结束位置坐标变量赋初值。详细定义如下：typedefstruct{ Positionstart;//起始位置 Positionend;//结束位置}MapCfg;MapCfgmap;程序中定义了迷宫中路径（单独每一通道块）所存储的结构体类型，包含当前位置坐标，及从该通道块走向下一通道块的“方向”，如：1：东，2：南，3：西，4：北。注：为存储迷宫路径的数据结构栈的元素类型。详细定义如下：typedefstruct{ Positioncurpos;//通道块在迷宫中的位置坐标 intdi;//从此通道块走向下一通道块的"方向"}SElemType;程序中定义了探索迷宫、和从入口start到出口end的通道,所存储的数据结构栈，为全局变量Path,realPath,其存储方式为顺序栈，包含指向栈元素类型的栈底base和栈顶top指针，及栈的存储空间stacksize，需注意的是：在初始化栈时要分配给存储空间初始量，在后续使用过程中可为其分配增量，以满足存储要求。hhhhhh详细定义如下：typedefstruct{ SElemType*base;//栈底指针 SElemType*top;//栈顶指针 intstacksize;//栈的大小}SqStack;SqStackrealPath;//存放路径SqStackPath; //探索迷宫2、算法分析与实现主要功能模块的算法设计分析。intMazePath(Positionstart,Positionend){ int**temp=Maze(); SElemTypee; e.curpos.x=map.start.x; //设定"当前位置"为"入口位置" e.curpos.y=map.start.y; e.curpos.val=temp[map.start.x][map.start.y]; do { if(UnPass(Path,e))//当前位置可以通过,即是未曾走过的通道块 { Push(&realPath,e);Push(&Path,e); e=NextPos(e); if(e.curpos.x==map.end.x&&e.curpos.y==map.end.y) { //到达终点(出口) Push(&realPath,e);hhhhhh Push(&Path,e); StackTraverse(&Path); returnTRUE; } elseif(e.curpos.val==-1) { //当前位置的四面或为墙或已走过Pop(&realPath); //删除真实路径的栈顶元素e=GetTop(&realPath); //令e指向栈顶元素} }else {//如果当前位置已经走过,说明原来测试的方向不对,现在尝试其它方向e=NextPos(e);if(e.curpos.val==-1) { //仍不通,删除真实路径的栈顶元素 Pop(&realPath); e=GetTop(&realPath); //令cur指向栈顶元素} }}while(e.curpos.x!=end.x||e.curpos.y!=end.y);returnFALSE;}四、运行结果和调试分析程序运行结果图：1.计算机“穷举求解法”，输出迷宫入口到出口路径。hhhhhh2.用二维数组表示迷宫地图，0为墙，1为道路。在程序调试过程中遇到变量不能被赋值的问题，后来经过按F5进行断点调试，根据错误提醒，发现了问题所在，得到了及时的修改。在本程序中对于迷宫当前位置是否走过的判断，需要对存储所有路径的realPath一一访问，对比当前位置是否被访问过，追其原因，是由于探索过程中并没有做好该位置已被访问的标记，导致每一位置都需重新定位，进行判断，浪费了时间与存储空间。改进：在栈元素类型，即迷宫中每一位置，增加flag标记，若已访问则标记-1，下次获得该位置坐标后便可得知该位置是否被访