第3章栈和队列第7讲-队列的应用-求解迷宫问题

栈和队列都是存放多个数据的容器。通常用于存放临时数据：如果先放入的数据先处理，则使用队列。如果后放入的数据先处理，则使用栈。3.2.4用队列求解迷宫问题1/12使用一个队列qu记录走过的方块，该队列的结构如下:typedefstruct{inti,j;//方块的位置intpre//本路径中上一方块在队列中的下标}Box;//方块类型typedefstruct{Boxdata[MaxSize];intfront,rear;//队头指针和队尾指针}QuType;//定义顺序队类型这里使用的队列qu不是环形队列（因为要利用出队的元素找路径），因此在出队时，不会将出队元素真正从队列中删除，因为要利用它输出路径。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,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/12用队列求一条迷宫路径的算法：（xi，yi）（xe，ye）6/127/128/12对于图3.7的迷宫，求解(1,1)(8,8)时队列qu中结果如下：下标ijpre011-1112022103221431253236414733585169347105281161812249135310147111下标ijpre151412162512176313181515192616206417211618226520235522247522254523265623278524284625295726下标ijpre308627318427324728335829346729358730368331373732384832396833408835408835358730308627278524221024752222652020641717631313531010528851664144312011-19/12对于图3.11的迷宫，求解结果如下：显然，这个解是最优解，即是最短路径。10/1211/12━━本讲完━━12/12