2023年数据结构之迷宫求解实验报告武汉大学.docx
数据结构实验报告迷宫求解问题实验上机环境：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 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)实验数据:迷宫数组如下: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：<1,1><1,2><1,3><2,3><3,3> <4,3<4,42：<1,1><1,2><1,3><2,3><3,3> <3,2X4,2X4,3X4,4>3：<1,1><2,1><3,1><3,2><3,3> <4,3><4,4>4： <1,1X2,1X3,1X3,2X4,2> <4,3><4,4>最短路径如下： 路隹最妞长度：7 最短路径路备<12><1,3><2,3><3,3><4,3><4,4>情按任意键继续. .三、程序代码:# in c 1 ude <s t dio.h># i ncludc# i ncludc< s t dl i b.h># 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.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 ;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 C'n");i f (top+1 <m i n)(for( k =0;k<=top; k +)P 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 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 ;
