第3章棧和隊列第7講-隊列的應用-求解迷宮問題課件

棧和隊列都是存放多個數(shù)據(jù)的容器。通常用于存放臨時數(shù)據(jù)：如果先放入的數(shù)據(jù)先處理，則使用隊列。如果后放入的數(shù)據(jù)先處理，則使用棧。3.2.4用隊列求解迷宮問題1/12棧和隊列都是存放多個數(shù)據(jù)的容器。通常用于存放臨時數(shù)據(jù)使用一個隊列qu記錄走過的方塊，該隊列的結(jié)構(gòu)如下:typedefstruct{inti,j;

//方塊的位置

intpre //本路徑中上一方塊在隊列中的下標}

Box; //方塊類型typedefstruct{Boxdata[MaxSize];

intfront,rear; //隊頭指針和隊尾指針}

QuType; //定義順序隊類型

這里使用的隊列qu不是環(huán)形隊列（因為要利用出隊的元素找路徑），因此在出隊時，不會將出隊元素真正從隊列中刪除，因為要利用它輸出路徑。數(shù)據(jù)組織

2/12使用一個隊列qu記錄走過的方塊，該隊列的結(jié)構(gòu)如下:當前方塊front：當前方塊在隊列中的下標相鄰方塊1i相鄰方塊2i+1Qu[i].pre=frontQu[i+1].pre=front

算法設計

首先將入口進隊。出隊一個方塊，考察如下：考察所有相鄰可走方塊3/12當前方塊front：當前方塊在隊列中的下標相鄰方塊1i相鄰方入口0方塊方塊方塊方塊……方塊方塊方塊出口所有搜索過的方塊都在隊列中。最后通過隊列找出從出口入口的一條迷宮路徑。4/12入口0方塊方塊方塊方塊……方塊方塊方塊出口所有搜索過的方塊都012345012345intmg[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/12012345012345intmg[M+2][N+2]boolmgpath1(intxi,intyi,intxe,intye) //搜索路徑為:(xi,yi)->(xe,ye){Boxe;inti,j,di,i1,j1;QuType*qu; //定義順序隊指針qu

InitQueue(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/12boolmgpath1(intxi,intyi,int

while(!QueueEmpty(qu)) //隊不空循環(huán){ deQueue(qu,e); //出隊方塊e i=e.i;j=e.j; if(i==xe&&j==ye) //找到了出口,輸出路徑 {print(qu,qu->front); //調(diào)用print函數(shù)輸出路徑

DestroyQueue(qu); //銷毀隊列 returntrue; //找到一條路徑時返回真 }7/12while(!QueueEmpty(qu))for(di=0;di<4;di++) //循環(huán)掃描每個方位{ 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;break; } 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/12for(di=0;di<4;di++) 對于圖3.7的迷宮，求解(1,1)(8,8)時隊列qu中結(jié)果如下：下標ijpre011-1112022103221431253236414733585169347105281161812249135310147111下標ijpre151412162512176313181515192616206417211618226520235522247522254523265623278524284625295726下標ijpre308627318427324728335829346729358730368331373732384832396833408835408835358730308627278524221024752222652020641717631313531010528851664144312011-19/12對于圖3.7的迷宮，求解(1,1)(8,8)時隊列qu中結(jié)迷宮路徑如下:

(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)