资源描述：
《数据结构--迷宫求解()》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、实验报告题目：迷宫求解一、需求分析1．本演示程序运用栈的结构求解迷宫。2．实现一个以顺序表或链表做存储结构的栈类型，编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出。3．程序执行的命令是：对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。4．迷宫的测试数据如下：左上角（1，1）为入口，右下角（3，4）为出口。二、编码实现1．存储类型typedefstruct{zuobiao*base;zuobiao*top;}Sqstack;2．部分函数的伪码算法//构造一个栈voidInitstack(
2、Sqstack&s){s.base=(zuobiao*)malloc(100*sizeof(zuobiao));s.top=s.base;}//入栈操作voidpush(Sqstack&s,zuobiaoe){(*s.top).x=e.x;(*s.top).y=e.y;s.top++;}//出栈voidpop(Sqstack&s,zuobiao&e){s.top--;e.x=(*s.top).x;e.y=(*s.top).y;}//取栈顶元素voidgettop(Sqstacks,zuobiao&e){s.top--;e.x=(*
3、s.top).x;e.y=(*s.top).y;//迷宫求解intmgqj(intmg[6][6],Sqstack&s){zi[1]=0;zj[1]=1;//东zi[2]=1;zj[2]=0;//南zi[3]=0;zj[3]=-1;//西zi[4]=-1;zj[4]=0;//北i=1;j=1;e.x=1;e.y=1;push(s,e);mg[1][1]=-1;do{for(v=1;v<=4;v++){m=i+zi[v];n=j+zj[v];if(mg[m][n]==0){mg[m][n]=-1;i=m;j=n;e.x=m;e.y=
4、n;push(s,e);break;}elsecontinue;}if(v==5&&s.top!=s.base){pop(s,e);gettop(s,e);i=e.x;j=e.y;}}while(s.top!=s.base&&(i!=4
5、
6、j!=4));if(i==4&&j==4)return1;elsereturn0;}三、调试分析1．由于忽略算法和程序的区别，首次运行存在许多错误2．本次作业题目虽然算法较长，但要求清晰，易形成思路。3．经验体会：在程序中适当加以注释，将使程序调试变得非常简便，可以加快找到程序中的疵点。编制程序
7、时应先建立大体框架，再将各部分细化，掌握从算法到程序的转换得方法四、测试结果除输出整个迷宫外，还输出：（1，1）（1，2）（2，2）（3，2）（3，3）（3，4）五、附录带注释的源程序如下#include#includetypedefstruct{intx;inty;}zuobiao;typedefstruct{zuobiao*base;zuobiao*top;}Sqstack;voidInitstack(Sqstack&s){s.base=(zuobiao*)malloc(100*sizeo
8、f(zuobiao));s.top=s.base;}voidpush(Sqstack&s,zuobiaoe){(*s.top).x=e.x;(*s.top).y=e.y;s.top++;}voidpop(Sqstack&s,zuobiao&e){s.top--;e.x=(*s.top).x;e.y=(*s.top).y;}voidgettop(Sqstacks,zuobiao&e){s.top--;e.x=(*s.top).x;e.y=(*s.top).y;}intmgqj(intmg[6][6],Sqstack&s){inti,
9、j,v,m,n,zi[5],zj[5];zuobiaoe;zi[1]=0;zj[1]=1;zi[2]=1;zj[2]=0;zi[3]=0;zj[3]=-1;zi[4]=-1;zj[4]=0;i=1;j=1;e.x=1;e.y=1;push(s,e);mg[1][1]=-1;do{for(v=1;v<=4;v++){m=i+zi[v];n=j+zj[v];if(mg[m][n]==0){mg[m][n]=-1;i=m;j=n;e.x=m;e.y=n;push(s,e);break;}elsecontinue;}if(v==5&&s.
10、top!=s.base){pop(s,e);gettop(s,e);i=e.x;j=e.y;}}while(s.top!=s.base&&(i!=4
11、
12、j!=4));if(i==4&&j==4)return1;elsereturn0;}voidma
