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

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