数据结构迷宫最短路径实验报告

《数据结构迷宫最短路径实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验报告课程名：数据结构（C语言版）实验名：迷宫问题II姓名：班级：学号：撰写时间：2014/10/10一实验目的与要求1.了解栈的应用2.利用栈在迷宫中找到一条路二实验内容•一个迷宫如图1所示,是由若干个方格构成的一个矩形,其中有唯一的一个入口(用⃝标示),有唯一的一个出口(用△标示).图中深色的方格无法到达,浅色的方格都是可以到达的.每一次只能从当前方格前进到与当前方格有公共边的方格中(因此前进方向最多有四个).•本次实验的迷宫问题要求找到从入口到出口的最短的路.图1：迷宫三实验结果与分析程序：#include#include

2、b.h>intMaze(intox,intoy,intex,intey,intrnum,intcnum,inta[rnum][cnum]){intb[rnum][cnum];inti,j,Znum=0;for(i=0;i

3、-10;}/*intdx[4]={0,1,0,-1};intdy[4]={-1,0,1,0};intneighbor_num=4;*/intdx[8]={-1,0,1,1,1,0,-1,-1};intdy[8]={-1,-1,-1,0,1,1,1,0};intneighbor_num=8;if(ox==ex&&oy==ey){printf("(%d,%d)",ox,oy);}else{Qx[tail]=ox;Qy[tail]=oy;P[tail]=-1;++tail;b[ox][oy]=2;}intbrand=-1;while(tail>head){for(i

4、=0;i=0){printf("(%d,%d),",Qx[t],Qy[t]);t=P[t];}head=tail;brand=1;break;}else{Qx[tail]=tx;Qy[tail]=ty;P[tail]=head;++tail;b[tx][ty]=2;}}}++head;

5、}return(brand);}intmain(intargc,char*argv[]){intrnum=10;intcnum=10;inta[10][10]={{1,1,1,1,1,1,1,1,1,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,0,0,1,1,0,0,1},{1,0,1,1,1,0,0,0,0,1},{1,0,0,0,1,0,0,0,0,1},{1,0,1,0,0,0,1,0,0,1},{1,0,1,1,1,0,1,1,0,1},{1,1,0,0,0,0,0,0,0,1},{1,1

6、,1,1,1,1,1,1,1,1}};//假设外面有一层不可到达的方块，故迷宫成了10乘10型intox=1,oy=1,ex=rnum-2,ey=cnum-2;intbrand=Maze(ox,oy,ex,ey,rnum,cnum,a);if(brand<0){printf("Thereisnoway");}return0;}图1：实验结果截图