老鼠迷宫.doc

(完整word版)老鼠迷宫 数 据 结 构 课 程 设 计3.8 老鼠迷宫姓 名: XXX院系: 计算机学院专 业: 计算机科学与技术年 级: 13级学 号: E11314XXX指导教师:XXX2015年 10月 5 日目录1.课程设计的目的32.需求分析33走迷宫游戏的设计33.1概要设计33.1.1主界面设计33.1.2存储结构33.1.3系统功能设计43.2详细设计43.2.1系统子程序及功能设计43.2.2数据类型定义53.2.3系统主要子程序详细设计63.3调试分析153.4用户手册164总结165、程序清单:(见附录)167、程序运行结果16附录122 37 / 371.课程设计的目的(1) 熟练使用 C 语言编写程序，解决实际问题;(2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;(3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;(4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力。2.需求分析(1) 程序运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。(2) 按动键盘上的方向操作杆控制老鼠在规定的时间内走到粮仓。(3) 老鼠形象可辨认，迷宫的墙足够结实，老鼠不能穿墙。(4) 若老鼠在规定时间走到粮仓处则提示成功，否则提示失败。(5) 添加编辑迷宫功能，可使迷宫墙变路，路变墙。(6) 找出走出迷宫的所有路径，以及最短路径。3走迷宫游戏的设计3.1概要设计3.1.1主界面设计图 1主界面，如图1所示，包含六个菜单项，分别是开始游戏、编辑迷宫、读入迷宫、生成随机迷宫、最短路径、退出系统。输入数字选择对应菜单，进入子项。3.1.2存储结构本系统用结构体Maze存储迷宫，该结构体由roomMN，statusMN组成。room是int型数组，存储迷宫具体内容；status是int型数组，用来存放迷宫求解时通堵状态，迷宫大小M，N固定。本系统用结构体pos存储迷宫求解时每一步的信息，该结构体由x,y,parent,self,next4组成。x,y是整型变量，存储坐标，parent是上一步在队列数组中的位置，self是本步在队列数组中的位置,next4存储四个方向下一步在队列数组中的位置。本系统用结构体Queue形成队列，该结构体由pM*N,front，rear组成。p是pos型变量，存储队列中的内容。本系统用数组实现队列操作，是为了求最短路径时，用BFS算法后，还能找到出队列的数据。3.1.3系统功能设计本系统主菜单包含四个选项，功能描述如下：菜单1：开始游戏。在菜单1中开始走迷宫游戏，老鼠用笑脸表示，初始状态老鼠在迷宫中间；通过键盘操纵老鼠上下左右移动，游戏分为6关，同一张地图，在规定时间到达粮仓可升级，否则提示失败，返回主菜单，随着级别增高最大时间逐渐减少。菜单2：编辑迷宫。在菜单2中编辑迷宫，按上下左右操作光标。可输入1，控制光标走过的地方为通路，输入0控制光标走过的地方为障碍。输入非法字符退出编辑。光标默认在迷宫中间，默认情况下光标走过的地方都为通路。菜单3：读入迷宫。在菜单3中读入已存在的迷宫文件，并输出读入的迷宫。菜单4：随机迷宫。在菜单4中以系统时间作为种子，随机生成地图，并输出地图，询问是否保存到文件。菜单5：最短路径。在菜单5中进行迷宫求解，若存在走出迷宫的路径，则找出最小路径，并用图形化界面输出，同时输出所有可走出迷宫的路径数目；否则，提示未找到最短路径，即该迷宫无解。菜单0：退出系统。3.2详细设计3.2.1系统子程序及功能设计本系统设置19个子程序，各程序的函数名及功能说明如下：int maincourse()/主菜单int inputselection(int n)/输入菜单选择，返回值为输入的选项void initqueue(Queue &Q)/初始化队列void enqueue(Queue &Q,pos p)/进队void dequeue(Queue &Q,pos &p)/出队int emptyqueue(Queue Q)/判队空void display(Elemtype roomMN,int degree,int t,int flag)/输出迷宫void countdown()/倒计时进入迷宫游戏void play(Elemtype roomMN)/迷宫游戏void filesave(Maze maze)/保存地图到文件void fileread(Maze &maze)/读入地图void modify(Maze &maze)/编辑迷宫void mazerand(Maze &maze)/随机生成迷宫int pass(Maze maze,pos p)/是否可通过void markprint(Maze &maze,pos p)/留下足迹void stepsdisplay(Queue Q,pos p,Maze maze)/输出最短路径void minroad(Maze maze)/最短路径void findallroad(Maze &maze,pos p,int &num)/找所有路径void allroad(Maze maze)/所有路径各个函数间的调用关系如下:主主菜单countdown();display();开始迷宫游戏play(roomMN)display();filesave(maze);修改迷宫modify(maze)display();从文件读入地址信息fileread(maze)display();filesave(maze);随机生成迷宫mazerand(maze)markprint();pass();stepsdiplay();minroad(maze)最短路径及所有路径数目统计allroad(maze) (maze)markprint();pass();findallroad;图33.2.2数据类型定义struct MazeElemtype roomMN;/迷宫Elemtype statusMN;/迷宫求解记录;struct posint x,y,parent,self;/x,y是当前坐标,parent是上一步在队列中的位置int next4;/self是本步在队列中的位置,next是下四步在队列中的位置;struct Queuepos pM*N;/队列中元素int front;/队首int rear;/队尾;3.2.3系统主要子程序详细设计输出迷宫：void display(Elemtype roomMN,int degree,int t,int flag)/输出迷宫int i,j; /flag为0为游戏模式,flag为1或2为编辑模式,大于2为输出模式printf(nn);for(i=0;iM;i+)putchar(t);for(j=0;j=3)/其他模式putchar(n);continue;switch(i)case 0:printf( -);break;case 1:if(flag)printf( 编辑迷宫! );/编辑模式elseprintf( 欢迎进入迷宫游戏!);/游戏模式break;case 2:printf( -);break;case 3:printf( -);break;case 4:printf( 按操纵 );break;case 5:printf( -);break;case 6:printf( -);break;case 7:if(flag)printf( 0,路边墙;1,墙变路);/编辑模式elseprintf( 当前等级:%d ,degree);/游戏模式break;case 8:printf( -);break;case 9:printf( -);break;case 10:if(flag=2)printf( 此时墙变路 );/编辑模式else if(flag=1)printf( 此时路变墙 );elseprintf( 剩余时间:%dt,t);/游戏模式break;case 11:printf( -);break;putchar(n);走出迷宫游戏：void play(Elemtype roomMN)/迷宫游戏countdown();system(cls);clock_t start,start2;start=clock();int x=M/2,y=N/2,x1=1,y1=1;int degree=1,lefted_t=30,all_t=30;while(1)start2=clock();while(lefted_t=(start2-start)/second)all_t&!kbhit()/计时及判断是否有输入system(cls);display(room,degree,all_t-lefted_t,0);while(clock()-start2second&!kbhit();start2=clock();lefted_t=all_t-lefted_t;if(lefted_t=0)/时间用完system(cls);printf(ttt*n);printf(ttt 游戏结束!挑战失败! n);printf(ttt*n);roomxy=1;roomM/2N/2=2;return;getch();switch(getch()/操纵case 72: x1=x-1;y1=y;break; / 向上case 80: x1=x+1;y1=y;break; / 向下case 75:x1=x; y1=y-1;break; / 向左case 77: x1=x; y1=y+1;/ 向右break;default:continue;if(x1=0|x1=M-1|y1=0|y1=N-1)/撞边墙了continue;else if(roomx1y1=0)/撞墙了continue;elseroomxy=1;x=x1;y=y1;if(x=N-2&y=N-2)/找到出口system(cls);degree+;all_t-=5;if(all_t=0)/随着升级，时间减少system(cls);printf(ttt*n);printf(ttt 你赢了!n);printf(ttt*n);roomxy=3;roomM/2N/2=2;return;printf(ttt*n);printf(ttt 升级了!等级%d!n,degree);printf(ttt*n);system(pause);start=clock();/下一关重新计时x=M/2;y=N/2;roomxy=2;/更新坐标elseroomxy=2;/更新坐标编辑迷宫：void modify(Maze &maze)/编辑迷宫int flag=1;int laststep;int x1=M/2,y1=N/2,x=M/2,y=N/2;char c;while(1)system(cls);display(maze.room,0,0,flag+1);while(!kbhit();c=getch();if(c=-32)c=getch();switch(c)case 72: x1=x-1;y1=y;break; / 向上case 80: x1=x+1;y1=y;break; / 向下case 75:x1=x; y1=y-1;break; / 向左case 77: x1=x; y1=y+1;/ 向右break;case 48:flag=0;/变墙break;case 49:flag=1;/变路break;default:system(cls);printf(ttt*n);printf(ttt 退出编辑!n);printf(ttt*n);maze.statusxy=maze.roomxy=laststep;maze.statusM/2N/2=maze.roomM/2N/2=2;filesave(maze);system(pause);return;if(x1=0|x1=M-1|y1=0|y1=N-1)/撞墙了continue;else if(x1=M-2&y1=M-2)continue;elseif(flag)/变路maze.statusxy=maze.roomxy=1;else/变墙maze.statusxy=maze.roomxy=0;laststep=maze.roomx1y1;x=x1;y=y1;maze.statusxy=maze.roomxy=2;/定位最短路径：void minroad(Maze maze)/最短路径system(cls);printf(-nt 最 短 路 径 n);printf(-n);Queue Q;initqueue(Q);pos p1,p2;/进队用p1，出队用p2int next42=1,0,0,1,0,-1,-1,0;p1.x=M/2;p1.y=N/2;p1.parent=-1;p1.self=0;enqueue(Q,p1);dodequeue(Q,p2);for(int i=0;i4;i+)/四个方向p1.x=p2.x+nexti0;/下一方向的坐标p1.y=p2.y+nexti1;p1.parent=Q.front-1;p1.self=Q.rear;if(pass(maze,p1)/判断是否可通过markprint(maze,p1);/留下足迹enqueue(Q,p1);Q.pp1.parent.nexti=Q.rear-1; /父结点指向进队的子结点if(p2.x=M-2&p2.y=N-2)printf(输出最短路径:);stepsdisplay(Q,p2,maze); /输出最短路径return;while(!emptyqueue(Q);printf(未找到最短路径!n);统计所有路径数目：void findallroad(Maze &maze,pos p,int &num)/找从p开始的所有路径 int next42=1,0,0,1,0,-1,-1,0;/移动方向pos p1;Elemtype temp;for(int i=0;i4;i+)/四个方向p1.x=p.x+nexti0;/下一方向的坐标p1.y=p.y+nexti1;if(pass(maze,p1)temp=maze.statusp1.xp1.y;/保留状态markprint(maze,p1);/留下足迹if(p1.x=M-2&p1.y=N-2)num+;elsefindallroad(maze,p1,num);/递归调用maze.statusp1.xp1.y=temp;/恢复状态void allroad(Maze maze)/所有路径int num=0;pos p;p.x=M/2;p.y=N/2;markprint(maze,p);/留下足迹findallroad(maze,p,num);/寻找从p开始的所有通路if(num)printf(共有%d条路径n,num);3.3调试分析测试数据及测试结果在7中有详细给出，这里省略。时间复杂度分析：play函数为走出迷宫游戏，其时间复杂度也不确定，与通路的块数以及通路的布局有关。display函数为显示迷宫，被多次调用，因为要将迷宫一个一个地输出，所以时间复杂度为modify函数为修改迷宫的函数，其时间复杂度不确定，与要修改的块相关。fileread和filesave函数保存一个Maze型数据，时间复杂度为。mazerand函数用rand()生成个伪随机数，所以时间复杂度为minroad函数对可走块四个方向都要判断是否可通，若可走块的数目为，则最多需要判断次，时间复杂度为allroad函数对可走块四个方向都要判断是否可通，时间复杂度同样为。调试思考：1 注意菜单选择函数的设计，它们的功能和菜单之间的联系。注意各个菜单函数中迷宫是否要初始化。2 为了让迷宫边界更加明显，默认设置边界部分全部为障碍。3 用键盘操作老鼠的移动方向，可用switch函数，根据输入的按键，进入不同分支，按照不同方式修改当前老鼠坐标。4 迷宫游戏需通过计时，判断是否在规定时间内完成迷宫。计时可通过不断获取系统时间实现。同时，需在动画界面不断更新计时，每隔一段时间刷新屏幕。5 迷宫游戏要用动画界面实现，在按动键盘或计时更新时都要刷新屏幕，可用一个while循环实现，当时间间隔足够或者键盘有操作时退出while循环并刷新屏幕。6 迷宫编辑函数modify中为实现图形化的界面，让修改更加的直观，设置每按下一个按键就根据所按下按键修改地图，并刷新屏幕，重新输出迷宫，从而实现可直观编辑迷宫的目的。7 求最短路径要用BFS的方法，从起点即树的根节点按层遍历，第一次到达终点也就是遍历层数最少时到达终点，求得最短路径。8 求所有可通路径，让方向有优先级，先沿着优先级高的方向走，当走到终点或者没有通路可走时，尝试下一个方向，直至所有可走块的方向都尝试完后即可得到所有可通路径的数目。3.4用户手册1 本程序执行文件为maze.exe。2 用户进入系统后根据提示，输入数字进入相应的子菜单，实现相应功能。3 本系统可实现走出迷宫游戏、编辑迷宫、保存迷宫到文件、从文件读入迷宫、随机生成迷宫、迷宫最短路径求解、统计迷宫所有可通路径数目的功能。4总结本次实验的内容比较难，几乎综合了迷宫求解和动画输出界面，还好我有迷宫求解的题目，先做了迷宫求解，稍微适应一下使用堆栈求解后，再做的这个题目。事实上，这个题目的最短路径求解和迷宫求解不同，比迷宫求解要难，用BFS求最短路径很难想到，看了网上的一些代码才有思路。求所有路径也非常难，也是看了网上的提示才做的。不过这也让我意识到了从了解BFS，DFS到应用它们之间的差距。的确需要较多的练习才能用好BFS和DFS。除此之外，我也意识到要多看一些算法，如果脑子里全是自己想的不规整的方法，解决问题时会比较吃力，遇到问题不能得心应手。5、程序清单:(见附录)7、程序运行结果主界面菜单1 开始迷宫游戏倒计时游戏界面超时提示失败升级提示菜单2 编辑迷宫编辑前：编辑中:编辑后：菜单3 读入迷宫菜单4 随机生成迷宫菜单5 最短路径无路径时：只有一条路径时：只有两条路径时：有很多条路径时：菜单0附录1程序清单#include #include #include #include #include #define N 20#define M 20#define Elemtype int#define second 1000struct MazeElemtype roomMN;/迷宫Elemtype statusMN;/迷宫求解记录;struct posint x,y,parent,self;/x,y是当前坐标,parent是上一步在队列中的位置int next4;/self是本步在队列中的位置,next是下四步在队列中的位置;struct Queuepos pM*N;/队列中元素int front;/队首int rear;/队尾;void initqueue(Queue &Q)/初始化队列Q.front=0;Q.rear=0;void enqueue(Queue &Q,pos p)/进队if(Q.rearM*N)return;/队列满了Q.pQ.rear=p;Q.rear+;void dequeue(Queue &Q,pos &p)/出队if(Q.frontQ.rear)return;/队列空了p=Q.pQ.front;Q.front+;int emptyqueue(Queue Q)/判队空if(Q.front=Q.rear)return 1;return 0;void display(Elemtype roomMN,int degree,int t,int flag)/输出迷宫int i,j; /flag为0为游戏模式,flag为1或2为编辑模式,大于2为输出模式printf(nn);for(i=0;iM;i+)putchar(t);for(j=0;j=3)/其他模式putchar(n);continue;switch(i)case 0:printf( -);break;case 1:if(flag)printf( 编辑迷宫! );/编辑模式elseprintf( 欢迎进入迷宫游戏!);/游戏模式break;case 2:printf( -);break;case 3:printf( -);break;case 4:printf( 按操纵 );break;case 5:printf( -);break;case 6:printf( -);break;case 7:if(flag)printf( 0,路边墙;1,墙变路);/编辑模式elseprintf( 当前等级:%d ,degree);/游戏模式break;case 8:printf( -);break;case 9:printf( -);break;case 10:if(flag=2)printf( 此时墙变路 );/编辑模式else if(flag=1)printf( 此时路变墙 );elseprintf( 剩余时间:%dt,t);/游戏模式break;case 11:printf( -);break;putchar(n);int inputselection(int n)/输入菜单选择，返回值为输入的选项int flag=0;char s100;doif(flag)printf(t 输入非法,请重新输入:);elseprintf(t 输入数字0-%d选择:,n);flag=1;scanf(%s,s);while(strlen(s)1|s0-0n);getchar();return s0-0;int maincourse()/主菜单printf(tt -n);printf(ttt 1. 开始游戏 2. 编辑迷宫n);printf(ttt 3. 读入迷宫 4. 随机迷宫n);printf(ttt 5. 最短路径 0. 退出系统n);printf(tt -nn);return inputselection(5);void countdown()/倒计时进入迷宫游戏int i;clock_t start;system(cls);for(i=3;i=0;i-)start=clock();system(cls);printf(ttt*n);printf(ttt 即将进入迷宫游戏，倒计时:%d n,i);printf(ttt*n);while(clock()-startsecond);void play(Elemtype roomMN)/迷宫游戏countdown();system(cls);clock_t start,start2;start=clock();int x=M/2,y=N/2,x1=1,y1=1;int degree=1,lefted_t=30,all_t=30;while(1)start2=clock();while(lefted_t=(start2-start)/second)all_t&!kbhit()/计时及判断是否有输入system(cls);display(room,degree,all_t-lefted_t,0);while(clock()-start2second&!kbhit();start2=clock();lefted_t=all_t-lefted_t;if(lefted_t=0)/时间用完system(cls);printf(ttt*n);printf(ttt 游戏结束!挑战失败! n);printf(ttt*n);roomxy=1;roomM/2