數(shù)據(jù)結構堆棧和隊-資料下載頁
2025-09-25 22:49本頁面
【正文】 samp,scanf同步加一 隊頭元素出隊 an+1 scanf sampan+1 n+4sampan+2 an+3 an+4 scanfscanf指向隊頭 samp指向隊尾 波形向前滾動顯示 循環(huán)隊列實例 滾動顯示 待顯示波形 迷宮問題 ? n*m迷宮是一矩形區(qū)域 ， 如下表所示 （ 綠色區(qū)域是后續(xù)程序搜索路徑 ） ； ? 矩陣元素 （ 1， 1） 為入口 ， （ n， m） 為出口 ， 0表示該方格可通過 ， 1表示該方格有阻礙不能通過； ? 規(guī)則是每次只能從一個無障礙方格向其周圍 8各方向的鄰接任一無障礙方格移動一步； ? 問 ， 當迷宮有解時如何尋找一條由入口到出口的路徑并返回這個序列 ， 或者不能連通時給出無解標志 。 求 ① 提出思想； ② 給出算法 。 設定的迷宮邊界 迷宮區(qū)域 迷宮算法 — 隊列結構 ? 用 2維數(shù)組 array[n][m]表示迷宮 ， 其中 array[0][0]～ array[0][m]，array[0][0] ～ array[n][0],array[n][0] ～ array[n][m],array[0][m] ～array[n][m]， 是算法設置的邊界哨 ， 取值為 1。 ? 初始 ， 我們不知道從哪一個方格沿哪個方向走 、 并通過鄰接的方格逐步可以達到最后出口 。 但是 ， 如果把它每一步所有可能走的方向上的鄰接方格都排列起來 ， 下一步是把那些鄰接方格它們所有可能走的方向上的所有鄰接方格也繼續(xù)排列起來 ， 于是： 如一個方格任何方向上都沒有可走的鄰接方格，就不再需要它，剔除； 同樣，一個方格所有可能走的方向上的鄰接方格都已經(jīng)列出來后，我們已經(jīng)知道了后續(xù)搜索方向，也就不再需要這個方格，也可以剔除； 重復下去，會搜索到所有能走的到方格，當發(fā)現(xiàn)有一個方格已是出口后停止； 選擇數(shù)據(jù)結構。因為先搜索到的方格在排列出其后續(xù)要搜索的鄰接方格之后，先被剔除，如果把排列方格看成是按順序進入一個隊列，剔除方格就等于是隊列頭部元素的出隊操作，所以可以用隊列結構解決迷宮路徑搜索問題。 搜索方向設置。設置一個隊列 sq[]記錄搜索路徑，從數(shù)組 array[1][1]開始搜索時將每個方格下標推入隊列，以（ i,j）為中心向 8個鄰域搜索時下標變化如下表所示。 迷宮問題求解 尋找一條由入口到出口的路徑 每次從一個無障礙 (0)方格 向其周圍 8個方向的鄰接 任一無障礙方格移動一步 解題思路 把每一步所有可能走的方向上的鄰接方格都排列起來 方格 (i,j)的鄰域 i , ji , j 1i 1 , j 1i + 1 , j 1i 1 , ji + 1 , ji 1 , j + 1i + 1 , j + 1i , j + 18761 23451,1 10,1 1,15 10,15 方位 方位修正 rearfronti=1,j=1 rear一次搜索排列 f ont搜索過者出隊，開始下一步 a1,1+1 a1+1,1 a1,2+1 a1,1 front為起點繼續(xù)搜索 a1+1,2+1 a2+1,1 rear回朔路徑 frontfront為起點繼續(xù)搜索 reara1+1,3+1 front rear標記 front周圍均搜索過，沒有進隊元素 front死路，出隊，繼續(xù)搜索 fronta21,4+1 a2,4+1 rear rear frontif(frontrear)繼續(xù)搜索 if((i==N)amp。amp。(j==M)){出口 ,由回朔路徑排列搜索線路 } if(frontrear) 搜索失敗 初始化 問題 設置邊界 節(jié)點結構： struct node{ int x,y。 //方格點坐標 int pre。 //回朔 點指示 }； int seartch(int array[N+2][M+2],struct node *q,int zx[8],int zy[8]) { int x,y,i,j,v,front=1,rear=1。 struct node sq[N*M]。 sq[1].x=1。sq[1].y=1。sq[1].pre=0。*(*(array+1)+1)=1。 while(front=rear){ x=sq[front].x。y=sq[front].y。 for(v=0。v8。v++){i=x+zx[v]。j=y+zy[v]。 if(*(*(array+i)+j)==0){ rear++。sq[rear].x=i。sq[rear].y=j。 sq[rear].pre=front。*(*(array+i)+j)=1。 } if((i==N)amp。amp。(j==M)){ i=rear。j=0。 while(i){ (q+j)x=sq[i].x。(q+j)y=sq[i].y。 i=sq[i].pre。j++。 } return(j)。 } } front++。 } return(1)。 } 搜索路徑 x,y方位 原點入隊 沒有前趨 搜索標記 搜索條件 隊頭 i,j 用方位修正下標 該點沒有障礙或標記就入隊 該搜索點前趨 標記該搜索點 到達出口？ 從隊尾回朔路徑 隊頭的前趨為零 要返回的搜索路徑由當前隊尾的前趨記錄 隊尾前趨的隊列下標 返回搜索路徑的長度 未到出口，繼續(xù)搜索 搜索失敗，返回路徑長度為 1 迷宮
教學教案相關推薦
鄂ICP備17016276號-1