资源描述：
《数据结构实验报告 迷宫.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、数据结构实验报告实验三迷宫姓名：xxx学号：xxx专业：信息安全实验日期：第十二.三周周日实验三迷宫一、实验目的1、了解回溯法在求解迷宫问题中的应用2、进一步掌握栈的使用二、实验内容用回溯法求解迷宫问题，可以用一个栈保存探索的序列。并且在该迷宫的行走中，站在一点可以有八个方向选择。比如如下的迷宫Enter->01110000000001000100010110010001001011000100101100111010100000100010110010001011011010100000001011
2、00-->EXIT下面是可能的路径（注意：从入口到出口可能有多条路径，优先选择的方向不同，路径可能也不一样！）Path:(maze[0][0],maze[1][0],maze[1][1],maze[1][2],maze[2][2],maze[3][2],maze[3][3],maze[4][3],maze[5][3],maze[6][3],maze[6][4],maze[6][5],maze[5][5],maze[4][5],maze[3][5],maze[2][5],maze[2][6],maze[
3、1][6],maze[0][6],maze[0][7],maze[0][8],maze[1][8],maze[2][8],maze[3][8],maze[4][8],maze[5][8],maze[5][7],maze[6][7],maze[7][7],maze[8][7],maze[8][8],maze[8][9],maze[9][9])Enter->X11100X---X---X0X---X---X100X1X001X11X---X1X001X---X1X11X0010X1X11X0111X1X1
4、X---X0001X---X---X1X110010001X110110101X--X--X000010110X-->EXIT1、提示：（1）数据结构：²用二维数组MAZE[m+2][n+2]表示迷宫的结构，数组中的值为1表示是墙，为0表示可以走通。（用MAZE[m+2][n+2]而不用MAZE[m][n]的原因在于想表示和编写代码的时候简单些，而且让迷宫周围都是墙，防止错误的走出去）²用二维数组MARK[m+2][n+2]表示迷宫是否被走过，主要是为了回溯时已经证明走不通的路线就不要再去走了。（用M
5、ARK[m+2][n+2]而不用MARK[m][n]的原因在于想表示和编写代码的时候简单些）²二维数据MOVE[8][2]是为了更方便的移动到下一步，改变坐标。这个二维数组是为了更好的转换坐标（八个方向，从0到7），而且也能避免重复走路²用栈保存走过的路径（2）输出：²迷宫布局，用0表示可以走通的地方，用1表示墙²如果能走通，则输出路径和路径的长度；若不能走通，则输出提示不能走通²带有路径的迷宫布局头文件部分#ifndefMIG_H#defineMIG_Hstructzhan{intMAX;intn;
6、int*s;};typedefstructzhan*seqstack;seqstackvoidzhan(intm);intisnullzhan(seqstackpastack);voidyazhan(seqstackpastack,intk);voidchuzhan(seqstackpastack);voidnizhan(seqstackpastack);inttopzhan(seqstackpastack);voidprintzhan(seqstackpastack);voidmigonglujin
7、(intmaze[8][11],intdirection[4][2],intx1,inty1,intx2,inty2,intm);#endif函数算法实现部分#include"ma.h"#include#includeseqstackvoidzhan(intm)//创建一个空栈{seqstackpastack=(seqstack)malloc(sizeof(structzhan));if(pastack!=NULL){pastack->s=(int*)malloc
8、(sizeof(int)*m);if(pastack->s){pastack->MAX=m;pastack->n=-1;returnpastack;}elsefree(pastack);}printf("over");returnNULL;}intisnullzhan(seqstackpastack)//判断栈是否为空{return(pastack->n==0);}voidyazhan(seqstackpastack,intk)//压栈{if(pasta
