[理學(xué)]第四章棧和隊列(編輯修改稿)
2024-11-12 21:31 本頁面
【文章內(nèi)容簡介】 徑?？商剿鲿r，記錄分支信息，便于退回時繼續(xù)其它分支探索。 mazeFrame() { 創(chuàng)建一個（保存探索過程）的空棧 把入口位置壓入棧 while（棧不空時） { 取棧頂位置并設(shè)置為當(dāng)前位置 while（當(dāng)前位置存在試探可能：未試探的方向） { 按照試探方向，計算試探位置 if（試探位置為出口） 打印結(jié)果，返回 if（試探位置為通道） 當(dāng)前位置進棧并將試探位置設(shè)為當(dāng)前位置 } } } E(0) S(1) W(2) N(3) Direction[4][2] 0 1 2 3 0 1 1 0 0 1 1 0 （ 3） 程序設(shè)計 A. 為避免走回到已進入的點（包括已在當(dāng)前路徑上的點和曾經(jīng)在當(dāng)前路徑上的點），凡是進入過的點都應(yīng)做上特殊標記（原來只有 0、 1，可以 2區(qū)分）。 B. 為記錄當(dāng)前位置及在該位置上所選的方向，設(shè)置一個棧，棧中每個元素包括三項，分別記錄當(dāng)前位置的行、列坐標及在該位置上所選的方向。如下： struct NodeMaze { int x, y, d。 } DataType。 C. 回溯用順序棧實現(xiàn) 5. 表達式計算 中綴表達式 ：運算符在操作數(shù)之間 31*（ 522） +70 后綴表達式 ：運算符在操作數(shù)后 31 5 22 * 70 + 后綴表達式的求值 ：需要一個存放操作數(shù)的棧 過程 ：從左往右掃描表達式， ? 遇到操作數(shù)進棧； ? 遇到運算符時從棧中彈出兩個操作數(shù)計算，并將計算的結(jié)果再壓入棧。 ?掃描結(jié)束時，棧頂元素就是最后的結(jié)果。 31 5 22 * 70 + 22 5 31 17 31 527 70 527 457 遇到 前，遇到 遇到 * 70入棧 遇到 + 中綴表達式到后綴表達式的轉(zhuǎn)換 ：需要一個存放運算符的棧 過程 ：從左往右掃描表達式， ? 遇到操作數(shù)：輸出； ? 遇到運算符： 【 兩個操作數(shù)輸出后才輸出 】 判斷與棧頂運算符的優(yōu)先關(guān)系，高于 ：入棧； 低于 ：彈棧輸出棧頂運算符，壓入當(dāng)前運算符。 【 運算符優(yōu)先級：四則運算 】 注意 ： ( )特殊處理。 碰到 “（” ，壓棧；碰到 “）” ，彈出 “（” 上面的所有運算符 【 含 “（” 】 。如： 5*(27+3*7)+22 輸出： 5 27 3 7 *+* 22+ 棧變化： （ * + （ * * + （ * * + （ * + 掃描： *優(yōu)先級 碰到 ) 高于 + 輸出 *+(， +優(yōu)先級低于 * 當(dāng)掃描到左括號時立即推入棧，繼續(xù)掃描直到出現(xiàn)右括號時才將留在棧中的這對左右括號之間的運算符逐一彈出輸出 。 十進制到 m進制的轉(zhuǎn)換 1： void main() { int v, m, i, j, result[1024]。 //輸入 printf(輸入進制 :)。 scanf(%d, amp。m)。 printf(輸入十進制數(shù) :)。 scanf(%d, amp。v)。 i = 0。 while (v) //轉(zhuǎn)換 { result[i++] = v%m。 v /= m。 } i。 printf(輸出結(jié)果 :)。 //輸出 for (j = i。 j = 0。 j) printf(%d , result[j])。 printf(\n)。 } 十進制到 m進制的轉(zhuǎn)換 2： void main() { int v, m。 pSeqStack *s = CreatStack()。 //輸入 printf(輸入進制 :)。 scanf(%d, amp。m)。 printf(輸入十進制數(shù) :)。 scanf(%d, amp。v)。 while (v) //轉(zhuǎn)換 { push(s, v%m)。 v /= m。 } printf(輸出結(jié)果 :)。 //輸出 while (!EmptyStack(s)) { v = pop(s)。 printf(%d , v)。 } printf(\n)。 DestroyStack(s)。 } : 是一種 先進先出 的線性表（ First In First Out, FIFO)，只允許在表的一端 (隊尾）進行插入，另一端（隊頭）進行刪除。 隊列 a0 a1 a2 … a n1 入隊列 出隊列 隊頭 隊尾 隊頭 隊尾 a0先入隊列，接著 a1 a2 … a n1依次進入隊列； a0先出隊列，后面的元素才能按照 先進先出 順序出隊列 . 應(yīng)用廣泛 ：作業(yè)、進程管理等 2. 隊列的基本運算 創(chuàng)建一個空隊列或?qū)㈥犃兄贸煽贞犃校? 判隊列是否為空隊列； 往隊列中插入一個元素； 從隊列中刪除一個元素； 求隊列頭部元素的值。 struct QNode /* 結(jié)點結(jié)構(gòu) */ { ElemType info。 struct QNode *link。 }。 typedef struct QNode *PNode。 struct LinkQueue /* 隊列結(jié)構(gòu) */ { P
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1