资源描述:
《数据结构--迷宫求解()》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
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