数据结构实验报告 迷宫.doc

《数据结构实验报告 迷宫.doc》由会员分享，可在线阅读，更多相关《数据结构实验报告 迷宫.doc（12页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构实验报告实验三 迷宫姓名：xxx学号：xxx专业：信息安全实验日期：第十二.三周周日实验三 迷宫一、实验目的1、了解回溯法在求解迷宫问题中的应用2、进一步掌握栈的使用二、实验内容用回溯法求解迷宫问题，可以用一个栈保存探索的序列。并且在该迷宫的行走中，站在一点可以有八个方向选择。比如如下的迷宫Enter- 0 1 1 1 0 0 0 0 0 00 0 0 1 0 0 0 1 0 00 1 0 1 1 0 0 1 0 00 1 0 0 1 0 1 1 0 00 1 0 0 1 0 1 1 0 01 1 1 0 1 0 1 0 0 00 0 1 0 0 0 1 0 1 10 0 1 0 0

2、0 1 0 1 10 1 1 0 1 0 1 0 0 00 0 0 0 1 0 1 1 0 0 - EXIT下面是可能的路径（注意：从入口到出口可能有多条路径，优先选择的方向不同，路径可能也不一样！） Path: ( maze00, maze10, maze11, maze12, maze22, maze32, maze33, maze43, maze53, maze63, maze64, maze65, maze55, maze45, maze35, maze25, maze26, maze16, maze06, maze07, maze08, maze18, maze28, maze38,

3、 maze48, maze58, maze57, maze67, maze77, maze87, maze88, maze89, maze99)Enter- X 1 1 1 0 0 X-X-X 0X-X-X 1 0 0 X 1 X 00 1 X 1 1 X-X 1 X 00 1 X-X 1 X 1 1 X 00 1 0 X 1 X 1 1 X 01 1 1 X 1 X 1 X-X 00 0 1 X-X-X 1 X 1 10 0 1 0 0 0 1 X 1 10 1 1 0 1 0 1 X- X- X0 0 0 0 1 0 1 1 0 X - EXIT1、提示：（1）数据结构： 用二维数组MAZ

4、Em+2n+2表示迷宫的结构，数组中的值为1表示是墙，为0表示可以走通。（用MAZEm+2n+2而不用MAZEmn的原因在于想表示和编写代码的时候简单些，而且让迷宫周围都是墙，防止错误的走出去） 用二维数组MARKm+2n+2表示迷宫是否被走过，主要是为了回溯时已经证明走不通的路线就不要再去走了。（用MARKm+2n+2而不用MARKmn的原因在于想表示和编写代码的时候简单些） 二维数据MOVE82是为了更方便的移动到下一步，改变坐标。这个二维数组是为了更好的转换坐标（八个方向，从0到7），而且也能避免重复走路 用栈保存走过的路径（2）输出： 迷宫布局，用0表示可以走通的地方，用1表示墙 如果

5、能走通，则输出路径和路径的长度；若不能走通，则输出提示不能走通 带有路径的迷宫布局头文件部分#ifndef MIG_H#define MIG_Hstruct zhan int MAX; int n; int*s;typedef struct zhan*seqstack;seqstack voidzhan(int m);int isnullzhan(seqstack pastack);void yazhan(seqstack pastack,int k);void chuzhan(seqstack pastack);void nizhan(seqstack pastack);int topzha

6、n(seqstack pastack);void printzhan(seqstack pastack);void migonglujin(int maze811,int direction42,int x1,int y1,int x2,int y2,int m);#endif函数算法实现部分#includema.h#include#includeseqstack voidzhan(int m)/创建一个空栈 seqstack pastack=(seqstack)malloc(sizeof(struct zhan); if(pastack!=NULL) pastack-s=(int*)mall

7、oc(sizeof(int)*m); if(pastack-s ) pastack-MAX=m; pastack-n=-1; return pastack; else free(pastack); printf(over);return NULL;int isnullzhan(seqstack pastack)/判断栈是否为空 return(pastack-n=0);void yazhan(seqstack pastack,int k)/压栈 if(pastack-n=pastack-MAX-1) printf(不好意思，这站满人了，等下一站吧，亲！); else pastack-n+; pa

8、stack-spastack-n=k; void chuzhan(seqstack pastack)/出栈 if(pastack-n=0) printf(我都空了); else pastack-n=pastack-n-1;int topzhan(seqstack pastack)/取栈顶元素 if(pastack-n=-1) printf(木有东西哦！无顶！); else return(pastack-spastack-n); void printzhan(seqstack pastack)/打印栈 int b; b=pastack-n; while(b-1) printf(%d,pastac

9、k-sb); printf( );b-; void nizhan(seqstack pastack)/将栈倒置，即：逆栈 int i; for(i=0;in ;i+) printf(%d,pastack-si); printf( );void migonglujin(int maze811,int direction42,int x1,int y1,int x2,int y2,int m) int i,j,k; int g,h,x,y,d; seqstack c; c=voidzhan(m); mazex1y1=2; x=x1; y=y1; d=-1; yazhan(c,x); yazhan(

10、c,y); while(!isnullzhan(c) y=topzhan(c); chuzhan(c);x=topzhan(c);chuzhan(c);i=x;j=y;k=d+1; while(k=3) g=i+directionk0; h=j+directionk1;if(g=x2&h=y2&mazegh=0) printf(打印路径上的每一点(以-为开始端哦！且按这个方向走！); /nizhan(c); while(!isnullzhan(c) y=topzhan(c); /printf(这是Y点); /printf(%d,y); chuzhan(c); x=topzhan(c); chu

11、zhan(c); /printf(这是X点); /printf(%d,x); /chuzhan(c); /printf(); printf(%d%d,x,y);printf(-); return;if(mazegh=0) mazegh=2; x=i;y=j;d=k; yazhan(c,x); yazhan(c,y); i=g;j=h; k=-1;k=k+1; printf(the path has not been found.n);主函数部分#includema.h#includestdlib.h#includestdio.hvoid main()int maze811=1,1,1,1,1,1,1,1,1,1,1, 1,0,1,0,0,1,1,1,0,0,1, 1,0,1,0,0,0,1,0,0,1,1, 1,0,1,1,1,0,0,0,1,1,1, 1,0,0,0,1,1,1,1,0,1,1, 1,1,0,0,1,0,1,1,1,1,1, 1,1,1,0,0,0,0,0,0,0,1, 1,1,1,1,1,1,1,1,1,1,1 ;int direction42=0,1,1,0,0,-1,-1,0;printf(求迷宫路径：);migonglujin(maze,direction,1,1,6,9,200);