迷宫课程设计报告

1、目 录引 言1一设计目的2二问题描述2三需求分析3四设计3五测试分析5六完整代码10七设计体会与小结17八、成绩：21 引 言 数据结构的学习过程，是进行复杂程序设计的训练过程，是算法构造性思维方法的训练过程，技能培养的过程不亚于知识传授。数据结构课程教学的重要内容和主要难点在于让我们理解、习惯算法构造性思维方法。培养我们的数据抽象能力、算法设计能力以及创造性思维方法，才能够举一反三、触类旁通，从而达到应用知识解决复杂问题的目的。数据结构作为专业基础课程，可以对去年学习的语言知识进行总结提高，为后续专业基础课程提供基础，它承上启下，贯通始终，是计算机科学与技术人才素质框架中的脊梁，对我们能力的

2、培养至关重要。通过对数据结构的学习，我们能够以问题求解方法、程序设计方法及一些典型的数据结构算法为对象，学会分析数据对象特征，掌握数理算法，初步掌握算法的时间、空间复杂分析基础，培养良好的程序设计风格以及进行复杂程序设计的技能。一设计目的 这次课程设计，我们的题目是迷宫求解。迷宫求解是数据结构中的经典问题，我期望达到的目的有以下4个。1.巩固书本知识，对书上的知识能更透彻的了解.通过自己设计程序积累调试数据结构的经验，培养我们的编程能力。巩固我们所学的数据结构知识，消化课堂所讲解的内容。也是对所学知识的整理，将原来在我们脑中比较混乱的课程设计重新梳理。2.通过课程设计能更好的掌握迷宫求解中的设

3、计思路，为以后灵活运用奠定基础。3.能够独立的完成简单程序的设计以及完成一份较为满意的程序设计报告。4.通过课程设计达到增强巩固数据结构知识的目的，使知识全面化、系统化。 二问题描述 迷宫问题来源于古希腊的神话，而后被人们演化为一个游戏。以一个N*M的方正表示迷宫，0、1分别表示迷宫中的通路和障碍。设计一个程序对任意设定的迷宫求出一条从入口的通道，或者的出没有通路的结论。假设一个老鼠从起点0.0沿X轴的八个方向逆时针旋转，老鼠每走到一处，总让它按东，东南，南，西南，西，西北，北，东北8个方向顺序试探下一个位置，如果某方向可以通过，则前进一步，在新位置上继续进行搜索；如果8个方向都走不通或曾经到

4、达过则退回一步，都要进行判断：若前进到了出口处，则说明不存在通路。如此重复直至走到终于，即为成功。三需求分析 通过主函数调用栈和递归的算法，来创作迷宫游戏或者解决迷宫问题。1.迷宫用类型的二维数组77矩阵来表示，其中每一个格用一个MG结构体表示，包括以下元素：是否是障碍物，0表示通过，1表示障碍物，mx(横坐标),my(纵坐标)，迷宫的暂时位置为固定。2.程序的输出信息主要有：（1）.打印的迷宫模块（2）.小老鼠所走的路径（3）.汉诺塔分步搬迁表示过程。3.程序的功能包括：（1）.对迷宫加密（2）.显示主菜单函数（3）保存恢复原函数信息（4）用递归和栈显示老鼠所走路径（5）用汉诺塔是实现搬迁（

5、6）用清屏函数来清屏四设计 概要设计1. 定义栈的抽象数据类型ADT Stack数据元素：可以是任意类型的数据，但必须属于同一个 数据对象。结论关系：栈中数据元素之间是线性关系。基本操作：判断栈是否为空。若栈为空推出循环。否则让该元素入栈ADT Stack2. 定义数组抽象数据类型ADT Stack数据对象：D=a j1 j2 .jn n0.称为数组的维数，ji是数组的第i维下标，1=ji=bi,bi为数组第i维的长度，Aj1j2.jn属于ElementSet数据关系：R=R1,R2,RnRi= | 1=jk=bk,1=k=n且k!=I,1=ji+bi-1,aj1jijn,aj1ji+1jn属

6、于D，i=1,n3. 基本操作1. InitArray(A,n,boundl,boundn)：若维数n和各维的长度合法，则构造相应的数组A，并返回TRUE。2. GetValue(A,e,index1,indexn):若下标合法，则用e返回数组A中由index1,indexn所指的元素的值.程序结构可以化分成以下几个模块： 1-主函数main()主函数调用其它子函数2-指令函数void login()用来设置迷宫的密码3-菜单函数select_menu()显示菜单界面4-递归函数void digui(int mazeNM, int x,int y, int v, int xx,int yy)用

7、递归函数实现迷宫走向5-栈函数void stack(int mazeNM, int x,int y, int xx,int yy)用栈实现迷宫走向6-汉诺塔void hanio(int q, int a, int b, int c)hanio实现搬迁7-保存函数void save( int mazeM,int backupM)保存初始值8-恢复函数void load (int mazeM,int backupM)恢复程序功能，继续执行程序9-清屏函数 system(cls)清除执行过的界面各函数之间的调用关系如下：菜单函数主函数1依次调用上面的2、3、4、5、6、7、8、9，实现迷宫行走路径及

8、汉诺塔的搬迁。指令函数主函数递归函数栈函数汉诺塔函数保存函数恢复函数清屏函数图1 函数调用关系图五测试分析首先二个图是错误的运行结果，图2 登陆错误时界面的显示图3 用栈实现的结果选择2时，是系统用栈解决了迷宫问题。如图3所示。如果接着输入数字1就是下面的结果。图4 用栈和递归实现后的结果图5 用递归实现图6 汉诺塔实现的结果 清屏函数加入依次输入1、2、3，上图是输入3后的结果，按回车键控制输出汉诺塔的搬迁次数。六完整代码 #include#include #include #include#include#include#include#define N 7#define M 7#defi

9、ne Q 5int r=2;int movex9=0,1,1,0,-1,-1,-1,0,1;/用结构体表示位置int movey9=0,0,1,1,1,0,-1,-1,-1;int mazeNM=/按照用户输入的二维数组（0或1）设置迷宫maze的初值，包括加上边缘一圈的值1,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,0,1,1,1,1,0,0,1,0,1,1,1,1,1,0,1,1,1,1,0,1,0,0,1,1,1,1,1,1,1,1,1;int backup N M;void save( int mazeM,int backupM)/保存函数int i, j;for

10、(i=0;iN;i+)for(j=0;jM;j+)backupij=mazeij;void load (int mazeM,int backupM)/恢复函数int i,j;for(i=0;iN;i+)for(j=0;jM;j+)mazeij=backupij;int select_menu()/菜单函数 int i,n; for(i=1;i用递归实现 &n ); printf(nt& 2-用栈实现 &n ); printf(nt& 3- 汉诺塔 &n ); printf(nt& 4- 退出 &n ); printf(nt& &n); printf(nt& 设计者:杨瑞娇 杜春雨 赵询 黄锦

11、&n); printf(nt& (第十三组)&n); printf(nt& 团结协作 实现共赢 &n); for(i=1;i=1) hanio( q-1, a,c,b); printf( 现在是第%d 搬迁 从%c-到%cn,+step, a+64, c+64); system(pause);/起暂停作用 hanio(q-1, b,a, c);void print( int aNM)/打印设置迷宫的模块 int i, j; for(i=0; iN; i+) for(j=0; jM; j+) printf(%3d, aij); printf(n); void digui(int mazeNM,

12、int x,int y, int v, int xx,int yy)/递归函数int x1,y1; mazexy=r+;/记录路径长度 for(v=1; v=8; v+)/v为老鼠所走路径的方向，1-8表示八个方向 x1=x+movexv; y1=y+moveyv;/随v的变化，更新老鼠所处位置 if(x1=xx&y1=yy) mazex1y1=r+;/记录路径长度 print(maze);/调用print函数/ getchar(); return;/当老鼠走到出口时，打印 else if(mazex1y1=0) /如果成立，说明这是一个通路 digui(maze,x1,y1,1,xx,yy)

13、; /调用go函数 mazexy=0;/通路void stack(int mazeNM, int x,int y, int xx,int yy)/栈函数 int i;int x1,y1,x2,y2,v,top=1;structint x;int y;int v; sN*M;/定义结构体 stop.x=x; stop.y=y;/x、y入栈 stop.v=0;/路径长度附初值 mazexy=2;while(top!=0)/判断栈是否为空，若非空，则出栈 x1=stop.x; y1=stop.y; v=stop.v+1; top-; while(v=8) x2=x1+movexv; y2=y1+mo

14、veyv;/随v的变化，更新老鼠所处位置 if(x2=xx&y2=yy)/当老鼠走到出口时，输出出老鼠所走路径 for(i=1; i8时退出循环 void login()/设置秘密 char pass6; int i; for(i=1;i=3; i+)/三次机会,若三次密码都未输对,则不能进入界面 printf(nnnnntttplease input password:n); gets(pass); if(strcmp(pass,)=0) break;/若输进,则退出循环,进入主界面 if(i=3) printf(n *weclome you to here*n);/若输密码次数=3,则出现

15、括号内的字符 printf(n); else printf(ntno usen);/输出no use exit(0);/退出本层循环 void main() int x0=1, y0=1,xx=5,yy=4; int i=1,j=0; login();/调用login函数 for(;)/循环调出主菜单 switch(select_menu()/调用select_menu()函数 case 1:save(maze,backup);digui(maze,x0,y0,1,xx,yy);load(maze,backup);/调用digui函数 system(cls);/清屏函数 break; case 2: save(maze,backup); stack(