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

数据结构课程设计报告设计题目：走迷宫游戏专业：计算机科技院系：计算机学院姓名：xxxxxxxx学号：xxxxxxxxx时间：2013年10月10日目录一、课程设计的目的 (2)二、需求分析 (2)三、课程设计报告内容 (3)1.概要设计 (3)2.详细设计 (4)3.调试分析 (9)4.用户手册 (9)5.测试结果 (10)6.程序清单 (11)四、小结 (16)五、参考文献 (16)一、课程设计的目的(1) 熟练使用 C 语言编写程序，解决实际问题;(2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;(3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;(4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力;二、需求分析程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。

游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。

要求：①老鼠形象可辨认，可用键盘操纵老鼠上下左右移动；②迷宫的墙足够结实，老鼠不能穿墙而过；③正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败；④添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙；⑤找出走出迷宫的所有路径，以及最短路径。

利用序列化功能实现迷宫地图文件的存盘和读出等功能三、实验报告内容1 概要设计（1）具体要求①构建一个二维数组maze[M+2][N+2]用于存储迷宫矩阵②自动或手动生成迷宫，即为二维数组maze[M+2][N+2]赋值③构建一个队列用于存储迷宫路径④建立迷宫节点struct point,用于存储迷宫中每个节点的访问情况⑤实现搜索算法⑥屏幕上显示操作菜单（2）本程序包含10个函数：①主函数 main()②手动生成迷宫函数 shoudong_maze()③自动生成迷宫函数 zidong_maze()④将迷宫打印成图形 print_maze()⑤打印迷宫路径 (若存在路径) result_maze()⑥入队 enqueue()⑦出队 dequeue()⑧判断队列是否为空 is_empty()⑨访问节点 visit()⑩搜索迷宫路径 mgpath()2 详细设计实现概要设计中定义的所有数据类型及操作的伪代码算法节点类型和指针类型迷宫矩阵类型：int maze[M+2][N+2];为方便操作使其为全局变量迷宫中节点类型及队列类型：struct point{introw,col,predecessor} que[512]迷宫的操作(1)手动生成迷宫void shoudong_maze(int m,int n){定义i,j为循环变量for(i<=m)for(j<=n)输入maze[i][j]的值}(2)自动生成迷宫void zidong_maze(int m,int n){定义i,j为循环变量for(i<=m)for(j<=n)maze[i][j]=rand()%2 //由于rand()产生的随机数是从0到RAND_MAX,RAND_MAX是定义在stdlib.h中的,其值至少为32767),要产生从X到Y的数,只需要这样写：k=rand()%(Y-X+1)+X;}(3)打印迷宫图形void print_maze(int m,int n){用i,j循环变量，将maze[i][j]输出□、■}(4)打印迷宫路径void result_maze(int m,int n){用i,j循环变量，将maze[i][j]输出□、■、☆}搜索迷宫路径①迷宫中队列入队操作void enqueue(struct point p){将p放入队尾，tail++}②迷宫中队列出队操作struct point dequeue(struct point p){head++,返回que[head-1]}③判断队列是否为空int is_empty(){返回head==tail的值，当队列为空时，返回0}④访问迷宫矩阵中节点void visit(int row,int col,int maze[41][41]){建立新的队列节点visit_point,将其值分别赋为row,col,head-1,maze[row][col]=2,表示该节点以被访问过;调用enqueue(visit_point),将该节点入队}⑤路径求解void mgpath(int maze[41][41],int m,int n){先定义入口节点为struct point p={0,0,-1},从maze[0][0]开始访问。

如果入口处即为障碍，则此迷宫无解，返回0 ，程序结束。

否则访问入口节点，将入口节点标记为访问过maze[p.row][p.col]=2,调用函数enqueue(p)将该节点入队。

判断队列是否为空，当队列不为空时，则运行以下操作：{ 调用dequeue()函数，将队头元素返回给p，如果p.row==m-1且p.col==n-1,即到达出口节点，即找到了路径，结束如果p.col+1<n且maze[p.row][p.col+1]==0,说明未到迷宫右边界，且其右方有通路,则visit(p.row,p.col+1,maze),将右边节点入队标记已访问如果p.row+1<m且maze[p.row+1][p.col]==0,说明未到迷宫下边界，且其下方有通路,则visit(p.row+1,p.col,maze),将下方节点入队标记已访问如果p.col-1>0且maze[p.row][p.col-1]==0,说明未到迷宫左边界，且其左方有通路,则visit(p.row,p.col-1,maze),将左方节点入队标记已访问如果p.row-1>0且maze[p.row-1][p.col]==0,说明未到迷宫上边界，且其上方有通路,则visit(p.row,p.col+1,maze),将上方节点入队标记已访问}访问到出口(找到路径)即p.row==m-1且p.col==n-1,则逆序将路径标记为3即maze[p.row][p.col]==3;while(p.predecessor!=-1){p=queue[p.predecessor]; maze[p.row][p.col]==3;}最后将路径图形打印出来。

菜单选择while(cycle!=(-1)){printf("╔═══════════════════════════╗\n");printf("║欢迎进入走迷宫游戏演示系统║\n");printf("║ ---------------------------------------------- ║\n");printf("║ -1. 手动生成迷宫║\n");printf("║ -2.系统自动生成迷宫║\n");printf("║ -3.退出系统║\n");printf("╚═══════════════════════════╝\n");printf(">>>>>>>\n");printf("请选择你的操作 [ ]\b\b");scanf("%d",&i);switch(i){case 1:printf("\n请输入行数 [ ]\b\b");scanf("%d",&m);printf("\n");printf("请输入列数 [ ]\b\b");scanf("%d",&n);while((m<=0||m>39)||(n<=0||n>39)){printf("\n抱歉，你输入的行列数超出预设范围(0-39,0-39),请重新输入：\n\n");printf("请输入行数 [ ]\b\b");scanf("%d",&m);printf("\n");printf("请输入列数 [ ]\b\b");scanf("%d",&n);}shoudong_maze(m,n);print_maze(m,n);mgpath(maze,m,n);if(X!=0)result_maze(m,n);printf("\n\nPress Enter Contiue!\n");getchar();while(getchar()!='\n');break;case 2:printf("\n请输入行数 [ ]\b\b");scanf("%d",&m);printf("\n");printf("请输入列数 [ ]\b\b");scanf("%d",&n);while((m<=0||m>39)||(n<=0||n>39)){printf("\n抱歉，你输入的行列数超出预设范围(0-39,0-39),请重新输入!\n\n");printf("请输入行数 [ ]\b\b");scanf("%d",&m);printf("\n");printf("请输入列数 [ ]\b\b");scanf("%d",&n);}zidong_maze(m,n);print_maze(m,n);mgpath(maze,m,n);if(X!=0) result_maze(m,n);printf("\n\nPress Enter Contiue!\n");getchar();while(getchar()!='\n');break;case 3: cycle=(-1);break;default:printf("\n");printf("你的输入有误!\n");printf("\nPress EnterContiue!\n");getchar();while(getchar()!='\n');break;}}注：具体源代码见附录3．调试分析在调试过程中，首先使用的是栈进行存储，但是产生的路径是多条或不是最短路径，所以通过算法比较，改用此算法4.用户手册①本程序的运行环境为windows7 64位操作系统②进入演示程序后即显示文本方式的用户界面5.测试结果图1 手动生成迷宫图2 系统自动生成迷宫6．程序清单#include<stdlib.h>#include<stdio.h>#define N 39#define M 39int X;int maze[N+2][M+2];struct point{int row,col,predecessor;}queue[512];int head=0,tail=0;void shoudong_maze(int m,int n){int i,j;printf("\n\n");printf("请按行输入迷宫，0表示通路，1表示障碍:\n\n");for(i=0;i<m;i++)for(j=0;j<n;j++)scanf("%d",&maze[i][j]);}void zidong_maze(int m,int n){int i,j;printf("\n迷宫生成中……\n\n");system("pause");for(i=0;i<m;i++)for(j=0;j<n;j++)maze[i][j]=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迷宫生成结果如下:\n\n");printf("迷宫入口\n");printf("↓");for(i=0;i<m;i++){printf("\n");for(j=0;j<n;j++){if(maze[i][j]==0) printf("□");if(maze[i][j]==1) printf("■");}}printf("→迷宫出口\n");}void result_maze(int m,int n){int i,j;printf("迷宫通路(用'鼠'表示)如下所示：\n\t");for(i=0;i<m;i++){printf("\n");for(j=0;j<n;j++){if(maze[i][j]==0||maze[i][j]==2) printf("□");if(maze[i][j]==1) printf("■");if(maze[i][j]==3) printf("鼠");}}}void enqueue(struct point p){queue[tail]=p;tail++;}struct point dequeue(){head++;return queue[head-1];}int is_empty(){return head==tail;}void visit(int row,int col,int maze[41][41]){struct point visit_point={row,col,head-1};maze[row][col]=2;enqueue(visit_point);}int mgpath(int maze[41][41],int m,int n){X=1;struct point p={0,0,-1};if(maze[p.row][p.col]==1){printf("\n--------------------------------------------------\n");printf("此迷宫无解\n\n");X=0;return 0;}maze[p.row][p.col]=2;enqueue(p);while(!is_empty()){p=dequeue();if((p.row==m-1)&&(p.col==n-1)) break;if((p.col+1<n)&&(maze[p.row][p.col+1]==0)) visit(p.row,p.col+1,maze);if((p.row+1<m)&&(maze[p.row+1][p.col]==0)) visit(p.row+1,p.col,maze);if((p.col-1>=0)&&(maze[p.row][p.col-1]==0)) visit(p.row,p.col-1,maze);if((p.row-1>=0)&&(maze[p.row-1][p.col]==0)) visit(p.row-1,p.col,maze);}if(p.row==m-1&&p.col==n-1){printf("\n--------------------------------------------------\n");printf("迷宫路径为：\n");printf("(%d,%d)\n",p.row,p.col);maze[p.row][p.col]=3;while(p.predecessor!=-1){p=queue[p.predecessor];printf("(%d,%d)\n",p.row,p.col);maze[p.row][p.col]=3;}}else {printf("\n--------------------------------------------------\n");printf("此迷宫无解！\n\n");X=0;}return 0;}int main(){int i,m,n,cycle=0;system("cls");system("color 1f");printf(" ┏━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");printf(" ┃㊣必做题：走迷宫游戏㊣┃\n");printf(" ┃姓名：xxxx ┃\n");printf(" ┃学号：xxxxxxxxx ┃\n");printf(" ┗━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");while(cycle!=(-1)){printf("╔══════════════════════════════════╗\n");printf("║欢迎进入走迷宫游戏演示系统║\n");printf("║ ------------------------------------------- ║\n");printf("║ 1.手动生成迷宫║\n");printf("║ 2.系统自动生成迷宫║\n");printf("║ 3.退出系统║\n");printf("╚══════════════════════════════════╝\n");printf(">>>>>>>\n");printf("请选择你的操作 [ ]\b\b");scanf("%d",&i);switch(i){case 1:printf("\n请输入行数 [ ]\b\b");scanf("%d",&m);printf("\n");printf("请输入列数 [ ]\b\b");scanf("%d",&n);while((m<=0||m>39)||(n<=0||n>39)){printf("\n抱歉，你输入的行列数超出预设范围(0-39,0-39),请重新输入：\n\n");printf("请输入行数 [ ]\b\b");scanf("%d",&m);printf("\n");printf("请输入列数 [ ]\b\b");scanf("%d",&n);}shoudong_maze(m,n);print_maze(m,n);mgpath(maze,m,n);if(X!=0)result_maze(m,n);printf("\n\nPress Enter Contiue!\n");getchar();while(getchar()!='\n');break;case 2:printf("\n请输入行数 [ ]\b\b");scanf("%d",&m);printf("\n");printf("请输入列数 [ ]\b\b");scanf("%d",&n);while((m<=0||m>39)||(n<=0||n>39)){printf("\n抱歉，你输入的行列数超出预设范围(0-39,0-39),请重新输入!\n\n");printf("请输入行数 [ ]\b\b");scanf("%d",&m);printf("\n");printf("请输入列数 [ ]\b\b");scanf("%d",&n);}zidong_maze(m,n);print_maze(m,n);mgpath(maze,m,n);if(X!=0) result_maze(m,n);printf("\n\nPress Enter Contiue!\n");getchar();while(getchar()!='\n');break;case 3: cycle=(-1);break;default:printf("\n");printf("你的输入有误!\n");printf("\nPress Enter Contiue!\n");getchar();while(getchar()!='\n');break;}}}四、小结通过这段时间的课程设计，我对计算机的应用，数据结构的作用以及C语言的使用都有了更深的了解。