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

#大学数据结构课程设计报告题目：走迷宫游戏 院（系）：计算机工程学院 学生姓名: 班级： 学号: 起迄日期: 2011-6-21 至 2011-6-30指导教师: 20102011年度 第 2 学期 一、需求分析1 问题描述走迷宫游戏程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。2 基本功能1) 老鼠形象可辨认，可用键盘操纵老鼠上下左右移动；2) 迷宫的墙足够结实，老鼠不能穿墙而过；3) 正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败；4) 添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙；5) 找出走出迷宫的所有路径，以及最短路径。利用序列化功能实现迷宫地图文件的存盘和读出等功能3 输入输出输入为字符型： 1， 2， 3 分别实现功能选择 w(上),s(下),a(左),d(右)控制迷宫的走向 y表示确定 n表示否定二、 概要设计1. 设计思路： 2.数据结构设计： 采用的是栈来存储数据，进栈实际是在栈中插入三元组，出栈则只数组的个数进行操作抽象数据类型线性表的定义如下：ADT SqStack数据对象：D=ai| ai SElemType,i=1,2,3，n,n0数据关系：R1=| ai-1,ai D,i=1,2,3,，n基本操作：SqStack *InitStack()操作结果：创建一个空栈 void Push(SqStack *S,SElemType data)初始条件：栈S已存在操作结果：插入一个元素，并且使数据个数加一(top+)void Pop(SqStack *S)初始条件：栈S已存在。操作结果：栈中元素个数减一（top-） 2. 软件结构设计：game（）模块函数原型：void game(int map1hw)/游戏函数 #define killtime 15 clock_t start, finish; double duration;int x=1,y=1,m=0,n=0,M,N,MAP100100;/x-colom y-rowchar cCtrl=0; cout 游戏规则:endl w向上,s向下,a向左,d向右,q退出endl 按任意键开始，方向键开始计时endl;for(M=0;M=h-1;M+)for(N=0;N=w-1;N+)MAPMN=map1MN; start = clock();/开始计时while(cCtrl=getch()!=q) switch(cCtrl) case w:/向上 cout0&!MAPy-1x)y-;break; case s:/下 couta;if(!MAPy+1x)y+;break; case a:/左 cout0&!MAPyx-1)x-;break; case d:/右 couta;if(!MAPyx+1)x+;break; system(cls);/刷屏 for(m=0;mh;m+) for(n=0;nw;n+) if(m=y&n=x) system(color 6); cout;/现实老鼠所在位置 else if(MAPmn) cout;/打印墙壁 else if(m=9&n=8)cout;/显示粮仓 else cout;/显示可行路径 if(x=8&y=9) finish = clock();/停止计时 duration = (double)(finish - start) / CLOCKS_PER_SEC;/compute the time coutendl你耗费的时间是:endlduration秒killtime)/losecout 你输了，完蛋了，小老鼠要饿死了 囧rz!endl;else/wincoutendl (o) 小老鼠总算找到粮仓了，谢谢啊！ endl 这是你赢得的金币，小老鼠奉上:endl;cout ;for(int i=0;i20-duration;i+)cout;coutendl; exit(0); coutendl; Mazepath（）模块：void MazePath(int mazew,int x,int y)/找到全部路径的函数int i;SElemType data;if(x=h-2&y=w-2)/到达出口print(S);return;for(i=0;i4;i+)/进行四个方向的判断data.seat.r=x;data.seat.c=y;data.d=i;mazexy=-1; x=x+movei.r;/对下一个方向处理y=y+movei.c;if(mazexy=0)/如果下一方向可通，把此元素入栈Push(S,data);MazePath(maze,x,y);/求下一元素为开始的路径Pop(S);x=x-movei.r;/若下一方向不通，回到此坐标y=y-movei.c;mazexy=0; 三、 详细设计 1. 定义程序中所有用到的数据及其数据结构，及其基本操作的实现typedef structint r,c;PosType;/坐标 r表示行，c表示列typedef structPosType seat;int d;SElemType;/seat表示当前坐标，d表示当前要转的方向序号typedef structSElemType data1000;int top;SqStack;/栈元素类型，含有一个三元组，top表示该数组的元素个数SqStack *S;PosType move4=0,1,1,0,0,-1,-1,0;/move 表示移动，分别是右、下、左、上int count=1;/用来统计路径条数2主函数和其他函数的伪码算法void MazePath(int mazew,int x,int y)/找到全部路径的函数int i;SElemType data;/定义三元组类型变量if(x=h-2&y=w-2)/到达出口 打印路径；for(i=0;i4;i+)/进行四个方向的判断把x,y赋给datadata.d=i;/方向记录mazexy=-1; 对下一个方向进行探索；if(mazexy=0)/如果下一方向可通 把此元素入栈MazePath(maze,x,y);/求下一元素为开始的路径Pop(S);若下一方向不通，返回到此坐标；mazexy=0; void print(SqStack *s) /显示一条路径/freopen(THEMAP.txt,a,stdout);int maphw=/给出迷宫的矩阵for(i=0;itop;i+) 输出每一个坐标位置和探索的方向maps-datai.seat .rs-datai.seat.c=2;/把坐标位置重新标记count+;/路径记录加一 输出字符模式的地图；void game(int map1hw)/游戏函数 #define killtime 15 clock_t start, finish; double duration;int x=1,y=1,m=0,n=0,M,N,MAP100100;/x-colom y-rowchar cCtrl=0; 初始化地图（赋值）； start = clock();/开始计时while(cCtrl=getch()!=q) switch(cCtrl) case w:/向上 if(y0&!MAPy-1x)y-;break; case s:/下 if(!MAPy+1x)y+;break; case a:/左 if(x0&!MAPyx-1)x-;break; case d:/右 if(!MAPyx+1)x+;break; system(cls);/刷屏 打印出老鼠，墙壁，粮仓； if(x=8&y=9) finish = clock();/停止计时 duration = (double)(finish - start) / CLOCKS_PER_SEC;/compute the time胜利和失败的处理； exit(0); coutendl; void savemap(int maphw)/保存地图以追加的方式打开一个文件；将地图以字符形式写入文件；将地图以数组形式写入文件；void change(int maphw)/墙变路，路变墙 先以字符形式显示地图；输入你想改变的坐标； 路变墙，墙变路；显示改变后的地图 选择保存与否； 继续游戏；void edit(int game)int a100000;FILE *fp;fp=fopen(ok.txt,r);/打开地图数组文件int t=0;while(fscanf(fp,%d,&at)!=EOF)/没有到文件结尾gamet=at;/把读出的赋值到新的数组里面t=t+1;fclose(fp);3.主要函数的程序流程图4.函数之间的调用关系图。输入操作选择选择gameA左W上选择mazepathD右S下输出所有路径main（）选择change输入坐标保存与否四、 调试分析 1 实际完成情况： 实现了老鼠走迷宫：老鼠形象可辨认，墙足够厚 实现了迷宫编辑功能：墙变路，路变墙 能对游戏结果和时间进行判断 能够找出迷宫所有路径和最段路径（其中第一条默认为最短路径） 能够实现存功能2 程序的性能分析：程序的运行效率不是很高，因为在game（）函数中采用的是刷屏显示老鼠的走动，所以每移动一次都要把所有的字符打印一遍，这对于时间的耗费是相当大的。对于mazepath（）函数，空间浪费一般，因为采用的栈存储，数组中的个数做多也就是h*w个，而且每一次退栈之后只是对上一个坐标四个方向判断后压栈，但是采用递归方法，对于时间的耗费相当大。其他函数时间和空间复杂度均和h、w有关，可以理解为为复杂度为h*w。3 上机过程出现的问题以及解决方案： 1）的移动无法实现，最后采用坐标改变后刷屏实现 2）个程序只能找出一条路径，经过重新修改，利用递归实现的了找出所有路径，其中采用了栈来存储可行路径 3）栈基本元素的定义感到模糊，最后确定用三元组形式实现 4）文件的存盘和读出功能功过直接对数组操作实现4 程序可以进行改进的地方 程序若实现将文件中地图数组读出并转化为整形数组进行操作，则可实现地图改变后保存更新的功能5 程序中可以扩充的功能及设计实现假想 实现电脑自己走迷宫的功能 同样应用刷屏实现，这个功能应当建立在mazepath函数之上，电脑每找出一条路径，则在出栈的时候自动演示五、测试结果六、用户手册 进入用户界面之后选择1，2，3选择你要进行的功能选项 选择1 进入游戏界面，通过w、s、a、d实现上下左右的行走 走到终点系统自动提示你的成绩和运行结果。 选择2 进入游戏自动寻路，自动显示出游戏所以路径 选择3 进入修改地图界面，输入一组坐标，数字之间用空格隔开，若选择y则保存，n则不保存，系统自动进入新的游戏界面，你将面对新的地图进行游戏七、体会与自我评价 关于走迷宫小游戏的总结 虽然走迷宫小游戏实现了要求的基本功能，但是我也看到了自己在编程方面的极大欠缺。针对迷宫小游戏，基本的难点是：1）如何实现老鼠的移动，2）如何创建函数实现电脑自动找出迷宫所有路径，3）如何实现地图数组的存盘功能。 对于第一个问题，其实我感觉还是很简单的，用数组创建地图，其中1表示墙壁，0表示可通路径，重点问题在于如何实现老鼠的移动，最终我决定利用刷屏实现，每移动一下则从新打印一下地图，基本实现了行走功能。 对于第二个问题，本来自己按照课本版的做了一个，利用栈来实现，但是结果只能实现找出一条路径，这与问题要求差的太远，通过和学长的交流以及查阅资料，最终敲定一个函数。采用递归调用的思想，先右函数一直向右走，判断之后找出一条路径，让后逐步退栈，使每一个坐标四个方位都被判断，最终搜素出一条新路径并打印出来。这个函数的最大特点是，退栈的时候并不是退出栈中的元素，而是把栈中三元组的top减一，然后对坐标重新下一方向的搜索，若可通，入栈，若不可通，继续退栈，对上一个坐标进行一次的操作。 第三个问题最后让我头疼不已。不过最后的讨论之后，我采用把数组存入文件中后，单个以int型读出，赋值到新的数组中（当作的地图数组），再创建一个保存地图数组的新函数edit函数，从而实现了文件的读出。这个小问题是我对文件操作加深了了解。对于c语言的复习进一步加深。 走迷宫虽然是一个小游戏，但是内部所展现的数据结构的思想却很精湛。尤其此处对于栈的应用，非常的概括和经典。通过这样一个小游戏的实现，我对于编程语言的学习更加有信心，说实在的，自己实现一个小游戏带来的喜悦确实很好。 希望这次的课设是我学习的一个新的起点。源代码#include#include#include#include#include#include#define ERROR 0#define FALSE 0#define OVERFLOW -1#define TRUE 1 #define OK 1#define RANGE 10#define h 11#define w 10typedef structint r,c;PosType;/坐标 r表示行，c表示列typedef structPosType seat;int d;SElemType;/seat表示当前坐标，d表示当前要转的方向序号typedef structSElemType data1000;int top;SqStack;/栈元素类型，含有一个三元组，top表示该数组的元素个数SqStack *S;PosType move4=0,1,1,0,0,-1,-1,0;/move 表示移动，分别是右、下、左、上int count=1;/用来统计路径条数SqStack *InitStack() /构造栈 SqStack *S;S=(SqStack *)malloc(sizeof(SqStack);S-top=-1;return S;void Push(SqStack *S,SElemType data)/入栈S-top+;S-dataS-top=data;void Pop(SqStack *S)/出栈S-top-;void print(SqStack *s) /显示一条路径/freopen(THEMAP.txt,a,stdout);int maphw=/形成迷宫的矩阵1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,0,0,1,1,1,0,1,1,1,0,0,1,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,1,1,1,0,1,1,1,1,0,0,1,1,1,1,1,0,0,0,1,0,1,1,1,1,1,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1;int i;printf(第%d条路径为:n,count);for(i=0;itop;i+)printf(%d,%d,%d) ,s-datai.seat .r,s-datai.seat.c,s-datai.d);maps-datai.seat .rs-datai.seat.c=2;if(i+1)%5=0)coutendl;coutendlendl;count+;int m,n;for(m=0;mh;m+)coutendl;for(n=0;nw;n+)if(mapmn=2) cout;if(mapmn=0)cout; if(mapmn=1)cout;coutendlendl;void MazePath(int mazew,int x,int y)/找到全部路径的函数int i;SElemType data;if(x=h-2&y=w-2)/到达出口print(S);return;for(i=0;icolom y-rowchar cCtrl=0; cout 游戏规则:endl w向上,s向下,a向左,d向右,q退出endl 按任意键开始，方向键开始计时endl;for(M=0;M=h-1;M+)for(N=0;N=w-1;N+)MAPMN=map1MN; start = clock();/开始计时while(cCtrl=getch()!=q) switch(cCtrl) case w:/向上 cout0&!MAPy-1x)y-;break; case s:/下 couta;if(!MAPy+1x)y+;break; case a:/左 cout0&!MAPyx-1)x-;break; case d:/右 couta;if(!MAPyx+1)x+;break; system(cls);/刷屏 for(m=0;mh;m+) for(n=0;nw;n+) if(m=y&n=x) system(color 6); cout;/现实老鼠所在位置 else if(MAPmn) cout;/打印墙壁 else if(m=9&n=8)cout;/显示粮仓 else cout;/显示可行路径 if(x=8&y=9) finish = clock();/停止计时 duration = (double)(finish - start) / CLOCKS_PER_SEC;/compute the time coutendl你耗费的时间是:endlduration秒killtime)/losecout 你输了，完蛋了，小老鼠要饿死了 囧rz!endl;else/wincoutendl (o) 小老鼠总算找到粮仓了，谢谢啊！ endl 这是你赢得的金币，小老鼠奉上:endl;cout ;for(int i=0;i20-duration;i+)cout;coutendl; exit(0); coutendl; void savemap(int maphw)/保存地图int i,j;FILE *fp;if(fp=fopen(mapshow.txt,a)=NULL)/以追加的方式打开一个文件coutCant open fileendl; exit(0);else fprintf(fp,n); fprintf(fp,new map:); for( i=0;ih;i+)fprintf(fp,n);for( j=0;jw;j+)if(mapij=1)fprintf(fp,);else fprintf(fp,);fclose(fp);fp=fopen(ok.txt,w);for(i=0;i11;i+)for(j=0;j10;j+)fprintf(fp, %d ,mapij);fclose(fp);void edit(int game)int a100000;FILE *fp;fp=fopen(ok.txt,r);int t=0;while(fscanf(fp,%d,&a