數(shù)據(jù)結(jié)構(gòu)上機(jī)例題.ppt

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

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

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

4、)”可視為自相應(yīng)左括弧開始的表達(dá)式的結(jié)束符。,從原表達(dá)式求得后綴式的規(guī)律為：,10,例如: Exp = a b + (c d / e) f#,后綴式: Suffix =,a,d,c,f,+,b,+,（,-,e,/,/,11,void transform(char suffix , char exp ) /從原表達(dá)式求得后綴式 /s是運(yùn)算符棧，s棧底預(yù)設(shè) #，OP是運(yùn)算符集合 / 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是運(yùn)算符 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)先級(jí)比c低，為真,13,1) 設(shè)立操作數(shù)棧S；,2) 設(shè)表達(dá)式的結(jié)束符為“#

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

7、P) / 若ch是操作數(shù) Push( S, ch); else / 若ch是運(yùn)算符 x2=POP(S)； x1=POP(S)；/取出兩個(gè)操作數(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,地圖四染色問題,“四染色”定理是計(jì)算機(jī)科學(xué)中著名的定理之一。 使地圖中相鄰的國(guó)家或行政區(qū)域不重色，最少可用四種顏色對(duì)地圖著色。 證明此定理的結(jié)論，利用棧采用回溯法對(duì)地圖著色。 思想：對(duì)每個(gè)行政區(qū)編號(hào)：1-7 對(duì)顏色編號(hào)；a、b、c、d； 從第一號(hào)行政區(qū)開始逐一染色，每一個(gè)區(qū)域逐次用四種顏色進(jìn)行試探，若所取顏色與周圍不重，則用棧記下來該區(qū)域的色數(shù)，否則依次用下一色數(shù)進(jìn)行試探。若出現(xiàn)a-d均與周圍發(fā)生重色，則需退?；厮?，修改當(dāng)前棧頂?shù)纳珨?shù)。,19,1,2,2,3,4,1,4,3,3,4,2,3,1# 紫色 2# 黃色 3# 紅色 4# 藍(lán)色,地圖四染色舉

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

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

11、擇 / 滿足約束條件的位置。當(dāng)求得(in)的一個(gè)合法布局 / 時(shí)，輸出之。 if (in) 輸出棋盤的當(dāng)前布局; else for (j=1; j=n; +j) 在第 i 行第 j 列放置一個(gè)棋子; if (當(dāng)前布局合法) queen(i+1, n); 移去第 i 行第 j 列的棋子; / trial,25,#include #define n 8 / n為皇后個(gè)數(shù)，m為擺法計(jì)數(shù) int m=0,an; / ai存放第i個(gè)皇后放置的行號(hào), 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列開始逐個(gè)試探 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)上放一個(gè)棋子 queen(j+1) ; main() queen(1);,27,k階斐波那契序列,試?yán)醚h(huán)隊(duì)列編寫求k階斐波那契序列中前n+1項(xiàng)（f0, f1 , f2 , fn )的算法，要求滿足fn max而fn+1 max ，其中max為某個(gè)約定的常數(shù)。（注意本題所用循環(huán)隊(duì)列的容量?jī)H為k,則在算法執(zhí)行結(jié)束時(shí)，留在循環(huán)隊(duì)列中的元素應(yīng)是k階斐波那契序列中的最后k項(xiàng)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)