数据结构课程设计-走迷宫讲解

1、数据结构课程设计报告设计题目：走迷宫游戏专 业：计算机科技院系：计算机学院姓名：xxxxxxxx学号：xxxxxxxxx时间： 2013年 10月 10日数据结构课程设计 走迷宫游戏目录一、课程设计的目的 2二、需求分析 三、课程设计报告内容 1. 概要设计 32. 详细设计. 43. 调试分析 . 94. 用户手册 5. 测试结果 106. 程序清单 11四、小结 16 五、参考文献 161 / 17数据结构课程设计 走迷宫游戏、课程设计的目的(1) 熟练使用 C 语言编写程序，解决实际问题 ;(2) 了解并掌握数据结构与算法的设计方法， 具备初步的独立分析和 设计能力 ;(3) 初步掌握软

2、件开发过程的问题分析、系统设计、程序编码、测试 等基本方法和技能 ;(4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能 力;二、需求分析程序开始运行时显示一个迷宫地图， 迷宫中央有一只老鼠， 迷宫的右 下方有一个粮仓。 游戏的任务是使用键盘上的方向键操纵老鼠在规定 的时间内走到粮仓处。要求： 老鼠形象可辨认，可用键盘操纵老鼠上下左右移动； 迷宫的墙足够结实，老鼠不能穿墙而过； 正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则 提示失败； 添加编辑迷宫功能， 可修改当前迷宫， 修改内容：墙变路、路变墙； 找出走出迷宫的所有路径，以及最短路径。利用序列化功能实现迷宫地图文件的

3、存盘和读出等功能2 / 17数据结构课程设计 走迷宫游戏三、实验报告内容1 概要设计( 1)具体要求 构建一个二维数组 mazeM+2N+2 用于存储迷宫矩阵 自动或手动生成迷宫，即为二维数组 mazeM+2N+2 赋值 构建一个队列用于存储迷宫路径建立迷宫节点 struct point, 用于存储迷宫中每个节点的访问 情况 实现搜索算法 屏幕上显示操作菜单(2) 本程序包含 10 个函数：主函数 main()手动生成迷宫函数 shoudong_maze() 自动生成迷宫函数 zidong_maze() 将迷宫打印成图形 print_maze() 打印迷宫路径 ( 若存在路径 ) result

4、_maze() 入队 enqueue() 出队 dequeue() 判断队列是否为空 is_empty() 访问节点 visit() 搜索迷宫路径 mgpath()3 / 17数据结构课程设计 走迷宫游戏2 详细设计实现概要设计中定义的所有数据类型及操作的伪代码算法 节点类型和指针类型迷宫矩阵类型： int mazeM+2N+2; 为方便操作使其为全局变量 迷宫中节点类型及队列类型： struct pointint row,col,predecessor que512迷宫的操作(1) 手动生成迷宫void shoudong_maze(int m,int n) 定义 i,j 为循环变量for(i

5、=m)for(j=n)输入 mazeij 的值(2) 自动生成迷宫void zidong_maze(int m,int n) 定义 i,j 为循环变量for(i=m)for(j=n)4 / 17数据结构课程设计 走迷宫游戏mazeij=rand()%2 / 由于 rand() 产生的随机数是从 0 到 RAND_MAX,RAND_M是A定X义在 stdlib.h 中的,其值至少为 32767), 要 产生从 X到 Y的数, 只需要这样写： k=rand()%(Y-X+1)+X;(3) 打印迷宫图形void print_maze(int m,int n) 用 i,j 循环变量，将 mazeij

6、输出 、 (4) 打印迷宫路径void result_maze(int m,int n) 用 i,j 循环变量，将 mazeij 输出 、 搜索迷宫路径迷宫中队列入队操作void enqueue(struct point p) 将p放入队尾， tail+ 迷宫中队列出队操作 struct point dequeue(struct point p) head+, 返回 quehead-1 判断队列是否为空 int is_empty() 返回 head=tail 的值，当队列为空时，返回 0访问迷宫矩阵中节点5 / 17数据结构课程设计 走迷宫游戏void visit(int row,int co

7、l,int maze4141) 建立新的队列节点 visit_point, 将其值分别赋为 row,col,head-1,mazerowcol=2, 表示该节点以被访问过 ; 调用 enqueue(visit_point), 将该节点入队 路径求解void mgpath(int maze4141,int m,int n) 先定义入口节点为 struct point p=0,0,-1, 从 maze00 开始访 问。如果入口处即为障碍，则此迷宫无解，返回 0 ，程序结束。否 则访问入口节点，将入口节点标记为访问过 mazep.rowp.col=2, 调用函数 enqueue(p) 将该节点入队。

8、判断队列是否为空，当队列不为空时，则运行以下操作： 调用 dequeue() 函数，将队头元素返回给 p，如果 p.row=m-1 且 p.col=n-1, 即到达出口节点，即找到了路径， 结束如果 p.col+1n 且 mazep.rowp.col+1=0,说明未到迷宫右边界，且其右方有通路 , 则 visit(p.row,p.col+1,maze),将右边节点入队标记已访问如果 p.row+10 且 mazep.rowp.col-1=0, 说明未到迷宫左边界， 且其左方有通路 , 则 visit(p.row,p.col-1,maze), 将左方节点入队标 记已访问如果 p.row-10 且

9、 mazep.row-1p.col=0, 说明未到迷宫上边界， 且其上方有通路 , 则 visit(p.row,p.col+1,maze), 将上方节点入队标 记已访问访问到出口 (找到路径)即 p.row=m-1且p.col=n-1, 则逆序将路径 标记为 3 即 mazep.rowp.col=3;while(p.predecessor!=-1) p=queuep.predecessor; mazep.rowp.col=3;最后将路径图形打印出来。printf( n);printf( 欢迎进入走迷宫游戏演示系统n);printf( n);printf( -1.手动生成迷宫n);printf(

10、 -2.系统自动生成迷宫n);printf( -3.退出系统n);printf( 菜单选择while(cycle!=(-1) n);printf(n);7 / 17数据结构课程设计 走迷宫游戏printf( 请选择你的操作 bb);scanf(%d,&i);switch(i)case 1:printf(n 请输入行数 bb);scanf(%d,&m); printf(n);printf( 请输入列数 bb);scanf(%d,&n); while(m39)|(n39)printf(n 抱歉，你输入的行列数超出预设范围 请重新输入： nn);printf( 请输入行数 bb);scanf(%d,

11、&m);printf(n);printf( 请输入列数 bb);scanf(%d,&n);shoudong_maze(m,n); print_maze(m,n); mgpath(maze,m,n);if(X!=0)result_maze(m,n);printf(nnPress Enter Contiue!n);getchar();while(getchar()!=n);break;case 2:printf(n 请输入行数 bb);scanf(%d,&m); printf(n);printf( 请输入列数 bb);scanf(%d,&n); while(m39)|(n39) printf(n

12、抱歉，你输入的行列数超出预设范围 请重新输入 !nn);printf( 请输入行数 bb);scanf(%d,&m);printf(n);printf( 请输入列数 bb);scanf(%d,&n);zidong_maze(m,n); print_maze(m,n); mgpath(maze,m,n);if(X!=0) result_maze(m,n); printf(nnPress Enter Contiue!n); getchar();(0-39,0-39),(0-39,0-39),8 / 17数据结构课程设计 走迷宫游戏while(getchar()!=n);break;case 3:

13、cycle=(-1);break;default: printf(n);printf( 你的输入有误 !n); printf(nPress Enter Contiue!n);getchar();while(getchar()!=n);break; 注：具体源代码见附录3调试分析在调试过程中，首先使用的是栈进行存储，但是产生的路径是多条或不是最短路径，所以通过算法比较，改用此算法4. 用户手册本程序的运行环境为 windows7 64 位操作系统进入演示程序后即显示文本方式的用户界面9 / 17数据结构课程设计 走迷宫游戏5. 测试结果图1 手动生成迷宫10 / 17数据结构课程设计 走迷宫游戏

14、图 2 系统自动生成迷宫6程序清单#include#include#define N 39#define M 39int X;int mazeN+2M+2;struct pointint row,col,predecessor;queue512;int head=0,tail=0;void shoudong_maze(int m,int n)int i,j;printf(nn);printf( 请按行输入迷宫， 0 表示通路， 1 表示障碍 :nn);11 / 17数据结构课程设计 走迷宫游戏for(i=0;im;i+)for(j=0;jn;j+) scanf(%d,&mazeij);void

15、 zidong_maze(int m,int n)int i,j;printf(n 迷宫生成中 nn);system(pause);for(i=0;im;i+) for(j=0;jn;j+) mazeij=rand()%2;/ 由于 rand() 产生的随机数是从 0 到 RAND_MAX /RAND_MAX是定义在 stdlib.h 中的 , 其值至少为 32767) / 要产生从 X到 Y的数, 只需要这样写： k=rand()%(Y-X+1)+X; void print_maze(int m,int n)int i,j;printf(n 迷宫生成结果如下 :nn); printf( 迷宫

16、入口 n);printf( );for(i=0;im;i+)printf(n);for(j=0;jn;j+)if(mazeij=0) printf( );if(mazeij=1) printf( ); printf( 迷宫出口 n);void result_maze(int m,int n)int i,j;printf( 迷宫通路 ( 用“鼠”表示 ) 如下所示： nt); for(i=0;im;i+)printf(n);for(j=0;jn;j+)if(mazeij=0|mazeif(mazeij=1) printf(if(mazeij=3) printf( ij=2) printf();鼠

17、);12 / 17数据结构课程设计 走迷宫游戏void enqueue(struct point p)queuetail=p;tail+;struct point dequeue()head+;return queuehead-1;int is_empty()return head=tail;void visit(int row,int col,int maze4141)struct point visit_point=row,col,head-1;mazerowcol=2;enqueue(visit_point);int mgpath(int maze4141,int m,int n)X=1

18、;struct point p=0,0,-1;if(mazep.rowp.col=1)printf(nn);printf( 此迷宫无解 nn);X=0;return 0;mazep.rowp.col=2;enqueue(p);while(!is_empty()p=dequeue();if(p.row=m-1)&(p.col=n-1) break;if(p.col+1n)&(mazep.rowp.col+1=0) visit(p.row,p.col+1,maze); if(p.row+1=0)&(mazep.rowp.col-1=0) visit(p.row,p.col-1,maze); if(

19、p.row-1=0)&(mazep.row-1p.col=0) visit(p.row-1,p.col,maze);if(p.row=m-1&p.col=n-1)printf(nn);printf( 迷宫路径为： n);printf(%d,%d)n,p.row,p.col);mazep.rowp.col=3;13 / 17数据结构课程设计 走迷宫游戏while(p.predecessor!=-1)p=queuep.predecessor;printf(%d,%d)n,p.row,p.col);mazep.rowp.col=3;else printf(nn);printf( 此迷宫无解！ nn)

20、;X=0;return 0;void main()int i,m,n,cycle=0;system(cls);system(color 1f);printf( n); printf( 必做题：走迷宫游戏 n); printf(姓名： xxxxn);printf(学号： xxxxxxxxx n);printf( n); while(cycle!=(-1)printf( n);printf( 欢迎进入走迷宫游戏演示系统 n);printf( n);printf( 1.手动生成迷宫 n);printf( 2.系统自动生成迷宫 n);printf( printf( 3.退出系统 n); n);prin

21、tf(n); printf( 请选择你的操作 bb); scanf(%d,&i);switch(i)case 1:printf(n 请输入行数 bb);scanf(%d,&m); printf(n);printf( 请输入列数 bb);scanf(%d,&n); while(m39)|(n39)14 / 17数据结构课程设计 走迷宫游戏printf(n 抱歉，你输入的行列数超出预设范围 (0-39,0-39), 入： nn);printf( 请输入行数 bb);scanf(%d,&m); printf(n);printf( 请输入列数 bb);scanf(%d,&n); shoudong_ma

22、ze(m,n); print_maze(m,n); mgpath(maze,m,n);if(X!=0) result_maze(m,n); printf(nnPress Enter Contiue!n); getchar();while(getchar()!=n);break;case 2: printf(n 请输入行数 bb);scanf(%d,&m); printf(n);printf( 请输入列数 bb);scanf(%d,&n); while(m39)|(n39)printf(n 抱歉，你输入的行列数超出预设范围 (0-39,0-39), 入!nn);printf( 请输入行数 bb);scanf(%d,&m); printf(n);printf( 请输入列数 bb);scanf(%d,&n); zidong_maze(m,n); print_maze(m,n); mgpath(maze,m,n); if(X!=0) resu