2023年数据结构之迷宫求解实验报告武汉大学.docx

《2023年数据结构之迷宫求解实验报告武汉大学.docx》由会员分享，可在线阅读，更多相关《2023年数据结构之迷宫求解实验报告武汉大学.docx（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构实验报告迷宫求解问题实验上机环境：DevC+ +二、程序设计相关信息（1）实验题目：迷宫求解问题问题描述：实验题3.5改善节中的求解迷宫问题程序,规定输出如图3. 14所示的迷宫的所 有途径，并求最短途径长度及最短途径。0 1 ?.4 4 5（2）实验项目组成：本项目由一个原程序mg. c p p及mg. cxc文献组成。（3）实验项目的程序结构：函数调用关系图：mainOQtrurt舛松依monnth/X余杼两加(4 )实验项目包含的函数的功能描述:mgM+lN+l/构造迷宫二维数组，1表达墙不可走方块，0表达通道m g pa t h( i nt x i , int yi, int

2、xe, i nt ye)求解途径为：(xi, yi) (xe, y e)/采用顺序栈存储，进栈，回溯,退栈等(5)算法描述:求解迷宫从入口到出口的所有途径，从入口出发，顺某一个方向向前试探，对于可走的 方块都进栈,并将这个可走发方位保存,且t。p+ 1 ,然后试探下一个方块,若下一个方块能走通则继续，否则则回溯到前一个方块，且top-U为记录所有的途径调用Pa t h k=St ack k记录，从次方块向不同方向去试探，已经走过的方块则为不可走方块。最后比较I。P值找到一条最短途径并输出。试探途径过程的算法运用了 “广度优先搜索遍历”算法。流程图:for循环mg=0(6)实验数据:迷宫数组如下

3、:int mgM+l N+l = 1, 1, 1 , 1 , 1 , 1 J 1 , 0 , 0,0,13 , 1,0, 1 ,0,0, 1,实验结果:1, 0,0, 0, 1,1), 1, 1,0,0, 0,1), (1, 1,1,1,1,1)；路径如下：1： 4,34,42： 3： 4： 最短路径如下： 路隹最妞长度：7 最短路径路备情按任意键继续. .三、程序代码:# in c 1 ude # i ncludc# i ncludc# d e fineM6# d ef i n e #define Maxsi z e 100 i n t mg M+l N+l=U/，l,1,1,1 ， 1，0

4、.0,0, 1,1),1, 0,1,001,1,0,0,0,1 , 1), 1,1,0,0,0,11 ,1,1,1, 1, 1,1);st r uct(i nt i ；in t j;in t d i ; S ta c k Ma x s iz e ,Pa t hM a xsiz e ;in t t o p=-l ；int c o u n t = 1 ;int min=Max s iz e ;int mgpath()(int i,j,di,find,k;top+ + ;Stack t o p.i=l;Stack t o p.j= 1 ；St a cktop.di=-l;m g 1 1 =- 1 ;

5、P ri n if(迷宫所有途径如下： n )；whi 1 e (t o p 1 )i=S t ack| t op .i; j = S t a ck t op, j ; d i=Stacktop.di;i f (i=M-2& j =N-2)prinlf(%4d： , c o unl+);f or (k= 0 ； k=t o p;k+)p rin tf(%d.% d ), Sta c k k. i , S t ac k k.j);i f (k+l)%5=0)p rintf ( n )；)pr i n t f Cn);i f (top+1 m i n)(for( k =0;k=top; k +)P

6、 a th k =S t ackk;mi n =to p + 1 ;1mg S t ackftop .i S tac k top .j=0;to pi = S t ack t o p.iy= S tac k top .j;di= S t a ck t op, d i ;fin d =0；wh i le( d i 4& f i n d= 0 )(d i +;s witch(di)case O:i=S t ack to p .i- 1 ;j= S(ackftop.j;break；case 1 ： i =St a cktop .i; j = S t ac k to p.j+l:bre a k ;ca

7、 s e 2:i=S t a c kto p .i+ 1 ; j =S t a c k lop, j ; b reak;ca s e 3:i=Stackt o p.i;j=S t a ck t o p . j -1： b r e a k ;)if (mg 川j =0)f ind= 1 ;i f ( find= 1)(S t a ckt o p . d i =d i ;top+;S uc k top .i=i;Stackft o p .j=j；S t ac k to p .di= 1;mg i)else(mg StacktopJ. i JStack(o p .j=0；to p)P r i ntf(n );printf (最短途径如下:n )；print f (途径最短长度:dn , min)：printf (最短途径途径:n);fo r ( k =0;k m in;k+)P rin t f( (%d,%d)” ,P a thk . i,Pa t hk. j);print ffnn,);)i nt m a in()(mg p ath ();s y st e m(PAUSE);r e t urn 0 ;