數(shù)據(jù)結(jié)構(gòu)課件(c語言)(4)(編輯修改稿)
2024-11-15 19:48 本頁面
【文章內(nèi)容簡介】 原棧頂元素所占存儲(chǔ)空間 */ return item。 ? } ? } 第 3章 棧和隊(duì)列 18 (4)取棧頂元素 GetTop(*S) : ? elemtype StackTop(LinkStack *S) { if(Stop= =NULL) /*?？?，無棧頂元素可取 */ printf (Stack is empty.) 。 return (Stopdata)。 } 第 3章 棧和隊(duì)列 棧的典型應(yīng)用 ? ? ? ? 第 3章 棧和隊(duì)列 [例 1]數(shù)制轉(zhuǎn)換問題：將十進(jìn)制 N轉(zhuǎn)換為 r進(jìn)制的數(shù)。 例 把十進(jìn)制數(shù) 159轉(zhuǎn)換成八進(jìn)制數(shù) (159)10=(237)8 159 8 19 8 2 8 0 2 3 7 余 7 余 3 余 2 top top 7 top 7 3 top 7 3 2 算法思想： while(N0) {將 N%r結(jié)果進(jìn)棧 。 N=N/r。} while(棧非空 ) 出棧并輸出原棧頂元素 。 第 3章 棧和隊(duì)列 [例 2]利用棧實(shí)現(xiàn)迷宮求解： 問題描述 ： 心理學(xué)家把一只老鼠從一個(gè)無頂蓋的大盒子的入口處趕進(jìn)迷宮。迷宮中設(shè)置很多墻壁，對(duì)前進(jìn)方向形成了多處障礙，心理學(xué)家在迷宮的唯一出口放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達(dá)出口。 算法基本思想描述 ： 利用回溯法，從入口處出發(fā)，按某一方向不斷試探，若能走通，則到達(dá)新點(diǎn)，否則試探另一未試探過的方向。若所有的方向均沒有通路，則沿原路返回前一點(diǎn)，換一個(gè)未試探過的通路繼續(xù)試探，直到找到出口，或所有的通路都試探過，未找到一條通路回到出口點(diǎn)。 在試探過程中，為保證在到達(dá)某一點(diǎn)無路時(shí)，能正確返回前一點(diǎn)，需要用一個(gè)棧來保存到達(dá)的每一點(diǎn)的位置及試探方向。 第 3章 棧和隊(duì)列 設(shè)計(jì) ： 1）數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì) （ 1）迷宮的表示 設(shè)迷宮為 m行 n列，利用二維數(shù)組 maze[m][n]來表示一個(gè)迷宮，其中 (1， 1)為入口， (m， n)為出口， maze[m][n]=0或 1，其中 0表示通路， 1表示不通。 0 1 1 1 0 1 1 1 1 0 1 0 1 1 1 1 0 1 0 0 0 0 0 1 0 1 1 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 入口 出口 第 3章 棧和隊(duì)列 0 1 1 1 0 1 1 1 1 0 1 0 1 1 1 1 0 1 0 0 0 0 0 1 0 1 1 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 0 迷宮定義 define m 6 define n 8 int maze[m+2][n+2] 當(dāng)從某點(diǎn)向試探時(shí)，之間點(diǎn)有 8個(gè)方向可以試探，而四個(gè)角點(diǎn)有 3個(gè)方向，其他邊緣點(diǎn)有 5個(gè)方向，為使問題簡單化 ,在迷宮的四周加了一層，表示墻壁，這樣每個(gè)點(diǎn)的試探方向?yàn)?8。 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 0 第 3章 棧和隊(duì)列 （ 2）試探方向的表示 在上述表示迷宮的情況下，每個(gè)點(diǎn)有 8個(gè)方向可以試探，設(shè)當(dāng)前點(diǎn)的坐標(biāo)為（ x， y），與其相鄰的 8個(gè)點(diǎn)的坐標(biāo)可根據(jù)與該點(diǎn)的相鄰方位得到。為了方便求出新點(diǎn)的坐標(biāo)，將從正東開始沿順時(shí)針進(jìn)行的這 8個(gè)方向的坐標(biāo)增量放在一個(gè)結(jié)構(gòu)數(shù)組 move[8]中，其中 x表示橫坐標(biāo)增量， y表示縱坐標(biāo)增量。 （ x， y+1） （ x， y1） （ x1， y） （ x+1， y） （ x+1， y+1） （ x1， y+1） （ x1， y1） （ x+1， y1） （ x， y） 試探方向的表示 typedef struct {int x,y。}item。 item move[8]= {{0,1}, {1,1}, {1,0},{1,1}, {0,
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1