1、1,棧與隊列上機題講解,一、 表達式的后綴式計算（9較難）,二、 回文游戲,三、 地圖四染色（8，選做）,四、 n皇后問題（6）,五、 k階斐波那契序列（5）,2,表達式 := (操作數(shù)) + (運算符) + (操作數(shù)) 操作數(shù) := 簡單變量 | 表達式 簡單變量 :=標識符 | 無符號整數(shù),二元運算符的表達式的三種標識方法,3,表達式的三種標識方法：,設 Exp = S1 + OP + S2,則稱 OP + S1 + S2 為前綴表示法,S1 + OP + S2 為中綴表示法,S1 + S2 + OP 為后綴表示法,4,例如: Exp = a b + (c d / e) f 前綴式: 中綴

2、式: 后綴式:,結論:,1）操作數(shù)之間的相對次序不變;,2）運算符的相對次序不同;,3）中綴式丟失了括弧信息， 致使運算的次序不確定;,+ a b c / d e f a b + c d / e f a b c d e / f +,5,5)后綴式的運算規(guī)則為: 每個運算符和在它之前出現(xiàn) 且緊靠它 的兩個操作數(shù)構成一個最小表達式; 運算符在表達式中出現(xiàn)的順序恰為表達式的運算順序。,4)前綴式的運算規(guī)則為: 連續(xù)出現(xiàn)的兩個操作數(shù)和在它們之前且緊靠它們的運算符構成一個最小表達式;,6,如何從后綴式求值？,先找運算符， 再找操作數(shù),例如： a b c d e / f +,ab,d/e,c-d/e,(c

3、-d/e)f,7,如何從原表達式求得后綴式？,每個運算符的運算次序要由它之后的一個運算符來定，在后綴式中，優(yōu)先數(shù)高的運算符領先于優(yōu)先數(shù)低的運算符。,分析 “原表達式” 和 “后綴式”中的運算符: 原表達式: a + b c d / e f 后綴式: a b c + d e / f ,8,從原表達式求得后綴式的規(guī)律為：,1) 設立運算符棧；,2) 設表達式的結束符為“#”， 預設運算符棧的棧底為“#”；,3) 若當前字符是操作數(shù)， 則直接發(fā)送給后綴式。,9,4) 若當前運算符的優(yōu)先數(shù)高于棧頂運算符，則進棧；,5) 否則，退出棧頂運算符發(fā)送給后綴式；,6) “(” 對它之前后的運算符起隔離作用，“

4、)”可視為自相應左括弧開始的表達式的結束符。,從原表達式求得后綴式的規(guī)律為：,10,例如: Exp = a b + (c d / e) f#,后綴式: Suffix =,a,d,c,f,+,b,+,（,-,e,/,/,11,void transform(char suffix , char exp ) /從原表達式求得后綴式 /s是運算符棧，s棧底預設 #，OP是運算符集合 / CrtExptree,InitStack(S); Push(S, #); p = exp; ch = *p; while (!StackEmpty(S) if (!IN(ch, OP) / 若ch是操作數(shù) Pass(

5、Suffix, ch); else A: / 若ch是運算符 if ( ch!= # ) p+; ch = *p; else Pop(S, ch); Pass(Suffix, ch); / while, ,12,A: switch (ch) case ( : Push(S, ch); break; case ) : Pop(S, c); while (c!= ( ) Pass( Suffix, c); Pop(S, c) break; defult : while(Gettop(S, c) / switch,若ch的優(yōu)先級比c低，為真,13,1) 設立操作數(shù)棧S；,2) 設表達式的結束符為“#

6、”；,3)讀入表達式一個字符,若當前字符是操作數(shù)，則壓入棧中,轉(zhuǎn)4)。,求后綴式的值：,14,若當前字符是運算符optr，從棧中彈出2個數(shù),將運算結果再壓入棧,即: x2=POP(S)； x1=POP(S)； PUSH(S,(x1 optr x2);,讀下一字符，重復3）和4）直至讀到結束符#；,棧頂,x=POP(S)即后綴式相應的表達式的值。,15,int cal(char suffix-exp ) /求后綴式表達式的值 /s是運算數(shù)棧，OP是運算符集合 /cal,InitStack(S); i = 0; ch = suffix-exp0; while (ch#) if (!IN(ch, O

7、P) / 若ch是操作數(shù) Push( S, ch); else / 若ch是運算符 x2=POP(S)； x1=POP(S)；/取出兩個操作數(shù) PUSH(S,(x1 ch x2); i+; ch= suffix-expi; / while,16,算法思路： 1.讀入字符串 2.去掉空格（原串） 3.壓入棧 4.原串字符與出棧字符依次比較 若不等，非回文 若直到?？斩枷嗟龋匚?字符串：“madam im adam”,回文游戲： 順讀與逆讀字符串一樣（不含空格）,17,int IsHuiwen( char *S), SeqStack T; int i , n; char t1; InitStac

8、k( / 比較完畢均相等則返回 1 ,18,地圖四染色問題,“四染色”定理是計算機科學中著名的定理之一。 使地圖中相鄰的國家或行政區(qū)域不重色，最少可用四種顏色對地圖著色。 證明此定理的結論，利用棧采用回溯法對地圖著色。 思想：對每個行政區(qū)編號：1-7 對顏色編號；a、b、c、d； 從第一號行政區(qū)開始逐一染色，每一個區(qū)域逐次用四種顏色進行試探，若所取顏色與周圍不重，則用棧記下來該區(qū)域的色數(shù)，否則依次用下一色數(shù)進行試探。若出現(xiàn)a-d均與周圍發(fā)生重色，則需退?；厮荩薷漠斍皸ｍ?shù)纳珨?shù)。,19,1,2,2,3,4,1,4,3,3,4,2,3,1# 紫色 2# 黃色 3# 紅色 4# 藍色,地圖四染色舉

9、例,SK,20,Void mapcolor(int R,int n,int s), s1=1; / 1號區(qū)域染1色 a=2; J=1; / a為區(qū)域號，J為染色號 while ( a4) a=a-1; J=sa+1 /回溯，修改顏色 ,21,設n皇后問題的解為 (x1, x2, x3, ,xn), 約束條件為：其中任意兩個xi 和xj不能位于棋盤的同行、同列及同對角線。,如何表示棋盤中放置的棋子？ 由于每行、列及對角線上只能有一個棋子，因而對每列來說，只需記錄該列中棋子所在的行號，故用一維數(shù)組即可。,皇后問題求解,22,設四皇后問題的解為 (x1, x2, x3, x4), 其中： xi (i

10、=1,2,3,4) Si=1, 2, 3, 4 約束條件為：其中任意兩個xi 和xj不能位于棋盤的同行、同列及同對角線。,按回溯法的定義，皇后問題求解過程為： 解的初始值為空；首先添加 x1=1, 之后添加滿足條件的 x2=3，由于對所有的 x31,2, 3, 4都不能找到滿足約束條件的部分解(x1, x2, x3), 則回溯到部分解(x1), 重新添加滿足約束條件的x2=4, 依次類推(按行存列號)。,按四皇后問題求解舉例,23,24,void queen(int i, int n) / 進入本函數(shù)時，在nn棋盤前i-1行已放置了互不攻 / 擊的i-1個棋子?，F(xiàn)從第 i 行起繼續(xù)為后續(xù)棋子選

11、擇 / 滿足約束條件的位置。當求得(in)的一個合法布局 / 時，輸出之。 if (in) 輸出棋盤的當前布局; else for (j=1; j=n; +j) 在第 i 行第 j 列放置一個棋子; if (當前布局合法) queen(i+1, n); 移去第 i 行第 j 列的棋子; / trial,25,#include #define n 8 / n為皇后個數(shù)，m為擺法計數(shù) int m=0,an; / ai存放第i個皇后放置的行號, int ok(int i, int j) /檢查(i,j)上能否放棋子 j1=j; i1=i; ok1=1; /1. 檢查第i行上能否放棋子 while(

12、(j11) return ok1 ,26,Void queen(int j) /從第j列開始逐個試探 if (jn) m+; printf(m=%d ,m); for (i=1;i=n;i+) printf( %d,ai); printf(“n”); else for( i=1; i=n;i+) if(ok(i,j) /檢查(i,j)上能否放棋子 aj=i; /在(i,j)上放一個棋子 queen(j+1) ; main() queen(1);,27,k階斐波那契序列,試利用循環(huán)隊列編寫求k階斐波那契序列中前n+1項（f0, f1 , f2 , fn )的算法，要求滿足fn max而fn+1 max ，其中max為某個約定的常數(shù)。（注意本題所用循環(huán)隊列的容量僅為k,則在算法執(zhí)行結束時，留在循環(huán)隊列中的元素應是k階斐波那契序列中的最后k項fn-k+1 , fn ) 。,28,f0=0 , f1=0 , , fk-2=0 , fk-1=1, fn = fn-1 + fn-2 + fn-k (n=k,k+1,),fi = fi-1 + fi-2 + fi-k fi+1 = fi + fi-1 + fi-2 + fi-k+1 兩式相減得： fi+1 = 2*fi - fi-k,k階斐波那契序列,29,void fb(int k,int max)