第3章栈和队列第7讲-队列的应用-求解迷宫问题ppt课件.pptx

《第3章栈和队列第7讲-队列的应用-求解迷宫问题ppt课件.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、栈和队列都是存放多个数据的容器。通常用于存放临时数据：如果先放入的数据先处理，则使用队列。如果后放入的数据先处理，则使用栈。3.2.4用队列求解迷宫问题1/12使用一个队列qu记录走过的方块，该队列的结构如下:typedefstruct{inti,j;//方块的位置intpre//本路径中上一方块在队列中的下标}Box;//方块类型typedefstruct{Boxdata[MaxSize];intfront,rear;//队头指针和队尾指针}QuType;//定义顺序队类型这里使用的队列qu不是环形队列（因为要利用

2、出队的元素找路径），因此在出队时，不会将出队元素真正从队列中删除，因为要利用它输出路径。数据组织2/12当前方块front：当前方块在队列中的下标相邻方块1i相邻方块2i+1Qu[i].pre=frontQu[i+1].pre=front算法设计首先将入口进队。出队一个方块，考察如下：考察所有相邻可走方块3/12入口0方块方块方块方块……方块方块方块出口所有搜索过的方块都在队列中。最后通过队列找出从出口入口的一条迷宫路径。4/12012345012345intmg[M+2][N+2]=//M=4,N=4{{1,

3、1,1,1,1,1},{1,0,0,0,1,1},{1,0,1,0,0,1},{1,0,0,0,1,1},{1,1,0,0,0,1},{1,1,1,1,1,1}};0:(1,1)-1入口2:(2,1)01:(1,2)03:(1,3)15:(2,3)34:(3,1)26:(3,2)47:(2,4)58:(3,3)59:(4,2)610:(4,3)811:(4,4)10出口迷宫路径:(4,4)(4,3)(3,3)(2,3)(1,3)(1,2)(1,1)5/12boolmgpath1(intxi,intyi,intxe,i

4、ntye)//搜索路径为:(xi,yi)->(xe,ye){Boxe;inti,j,di,i1,j1;QuType*qu;//定义顺序队指针quInitQueue(qu);//初始化队列que.i=xi;e.j=yi;e.pre=-1;enQueue(qu,e);//(xi,yi)进队mg[xi][yi]=-1;//将其赋值-1,以避免回过来重复搜索用队列求一条迷宫路径的算法：（xi，yi）（xe，ye）6/12while(!QueueEmpty(qu))//队不空循环{deQueue(qu,e);//出队方块ei

5、=e.i;j=e.j;if(i==xe&&j==ye)//找到了出口,输出路径{print(qu,qu->front);//调用print函数输出路径DestroyQueue(qu);//销毁队列returntrue;//找到一条路径时返回真}7/12for(di=0;di<4;di++)//循环扫描每个方位{switch(di){case0:i1=i-1;j1=j;break;case1:i1=i;j1=j+1;break;case2:i1=i+1;j1=j;break;case3:i1=i;j1=j-1;brea

6、k;}if(mg[i1][j1]==0){e.i=i1;e.j=j1;e.pre=qu->front;enQueue(qu,e);//(i1，j1)方块进队mg[i1][j1]=-1;//将其赋值-1}}}DestroyQueue(qu);//销毁队列returnfalse;}把每个可走的方块插入队列中8/12对于图3.7的迷宫，求解(1,1)(8,8)时队列qu中结果如下：下标ijpre011-111202210322143125323641473358516934710528116181224913531014

7、7111下标ijpre151412162512176313181515192616206417211618226520235522247522254523265623278524284625295726下标ijpre308627318427324728335829346729358730368331373732384832396833408835408835358730308627278524221024752222652020641717631313531010528851664144312011-19/12迷宫路

8、径如下:(1,1)(2,1)(3,1)(4,1)(5,1)(5,2)(5,3)(6,3)(6,4)(6,5)(7,5)(8,5)(8,6)(8,7)(8,8)运行结果对于图3.11的迷宫，求解结果如下：显然，这个解是最优解，即是最短路径。10/12思考题：用队列和用栈求解迷宫问题有什么不同？11/12━━本讲完━━12/12