【正文】 ack。 鏈棧為空的條件： top = NULL 鏈棧為滿的條件 : t = NULL t 為申請的結(jié)點 ,為 NULL表示失敗。 操作步驟 : step1 申請一個鏈棧結(jié)點 ,若 t=NULL,則表示鏈滿 。 step2 在 top所指結(jié)點之前插入新結(jié)點 ,并將 top指向新申請的結(jié)點 t。top, ElemType x) { SNode *p=new SNode。 pnext=top。 } } 下一頁 上一頁 停止放映 [第 20頁 /68頁 ] （ 2） 出棧操作 若棧不空 ， 則刪除棧頂元素 ， 用 e返回其值 。 step2 刪除 top所指結(jié)點 ， 并使 top 指向被刪除結(jié)點的后繼結(jié)點 。 下一頁 上一頁 停止放映 [第 21頁 /68頁 ] 出棧操作程序 void Pop (LinkStack amp。e) { SNode *p。 p=top。 delete p。 例如， 3*（ 72） ； – 實際處理表達式是用兩個棧結(jié)構(gòu) OPTR（算符）和 OPND（操作數(shù)）加運算規(guī)則組成； 四則運算 下一頁 上一頁 停止放映 [第 24頁 /68頁 ] 計算表達式算法步驟 Step1 初始化，清空 OPTR和 OPND，將左定界符壓 OPTR棧； Step2 循環(huán)輸入表達式中的每個字符 – 若輸入操作數(shù)，則進 OPND棧 – 若是算符，則和 OPTR棧頂元素進行比較，按規(guī)則進行相應(yīng)操作 – 操作服從優(yōu)先關(guān)系表（ Q1是棧中算符， Q2是當前算符） ? Q1Q2 Q2入 OPTR棧，再讀入下一個元素 ? Q1=Q2 Q1出 OPTR棧，脫括號，再讀一個元素 ? Q1Q2 Q1出 OPTR棧，從 OPND中取兩個數(shù)運算 Step3 直到出現(xiàn)右定界符為止。最簡單的表達式為下列形式： (操作數(shù) S1)(運算符 OP)(操作數(shù) S2) 三種不同的表示方法： 前綴表示法 OPS1S2 例如 6+3寫成 +63 中綴表示法 OPS1S2 例如 6+3寫成 63+ 后綴表示法 S1S2OP 例如 6+3寫成 63+ 下一頁 上一頁 停止放映 [第 27頁 /68頁 ] 同時，任何表達式都可分解為下列形式： (子表達式 E1)(運算符 OP)(子表達式 E2) 它的后綴表示法應(yīng)寫成： (E1的后綴表示 )(E2的后綴表示 )OP 只要不斷對子表達式進一步分解，總能將子表達式分解為最簡單形式，因此任何四則運算表達式都可寫成前綴式或后綴式。 (注意：轉(zhuǎn)化為后綴式后括號去掉 ) 下一頁 上一頁 停止放映 [第 28頁 /68頁 ] 用后綴式求值的算法為： 首先設(shè)立一個堆棧，依此讀取后綴式中的字符，若字符是數(shù)字，則進棧并繼續(xù)讀取，若字符是運算符，則連續(xù)出棧兩次得到數(shù)字 S1和 S2，計算表達式 S1OPS2并將結(jié)果入棧，繼續(xù)讀取后綴式。 下一頁 上一頁 停止放映 [第 29頁 /68頁 ] 例如，后綴式 263+*的計算過程為 3依次入棧，讀 +號則令 3和 6依次出棧，計算 6+3后將結(jié)果 9入棧，讀 *號則令 9和 2依次出棧，計算 2*9后將結(jié)果 18入棧。 【 例 23】 假定表達式是由不超過四個實數(shù)進行四則運算構(gòu)成的算式，要編寫一個程序來求解該算式的結(jié)果。 else return ( n * fac(n1))。在 A塔上插有 n個直徑大小不同、以小到大編號為 … 、 n的圓盤。移動圓盤的規(guī)則為： 1）每次只能移動一個圓盤； 2）圓盤可以插在 A、 B、 C的任意一個上； 3）任何時刻都不能將較大的圓盤壓在較小的圓盤之上。 下一頁 上一頁 停止放映 [第 33頁 /68頁 ] 算法分析 ? 將 n個盤子從 A軸移到 C軸可分為以下三個步驟 : ① 將 A上 n1個盤子移到 B上 (借助 C)； ② 把 A上剩下的一個盤子移到 C上； ③ 將 n1個盤子從 B移到 C上 (借助 A)。 ② 將一個盤子從一處移到另一處。 例程序 下一頁 上一頁 停止放映 [第 34頁 /68頁 ] n=1的 Hanoi塔問題 A B C A C 下一頁 上一頁 停止放映 [第 35頁 /68頁 ] n=2的 Hanoi塔問題 A B C A B A C B C 下一頁 上一頁 停止放映 [第 36頁 /68頁 ] n=3的 Hanoi塔問題 A B C 變?yōu)?n1問題 A C A B C B A C B A B C A C 下一頁 上一頁 停止放映 [第 37頁 /68頁 ] 隊列定義 隊列是一種特殊的線性表，它只允許在表的前端（ front）進行刪除操作，而在表的后端（ rear）進行插入操作。 隊列中沒有元素時，稱為空隊列。 隊列空的條件： front = rear 隊列滿的條件： rear = MAXSIZE a b c front rear 入隊 出隊 隊列示意圖 maxsize 下一頁 上一頁 停止放映 [第 38頁 /68頁 ] 關(guān)于隊列表示的約定 約定： 隊頭指針 front總是指向隊頭元素的前一個位置； 隊尾指針 rear總是指向隊尾元素的位置。 判別隊列為空的條件也將復雜化。顯然，這是邏輯設(shè)計上的問題。 用表達式描述 : if （ rear MAXSIZE ） rear = 1 。 這就是循環(huán)隊列的處理思想。 else rear＝ rear + 1。 下一頁 上一頁 停止放映 [第 44頁 /68頁 ] 循環(huán)隊列的指針移動 （ 1） 隊頭指針 front = front% MAXSIZE + 1； 等價于： if（ front MAXSIZE ） front = 1 。 （ 2）隊尾指針 rear = rear % MAXSIZE +1 ； 等價于： if （ rear MAXSIZE ） rear = 1。 循環(huán)隊列在指針移動處理時與一般隊列不同： 下一頁 上一頁 停止放映 [第 45頁 /68頁 ] 隊空條件為 front=rear 隊滿條件為 (rear