棧操作及應(yīng)用

1、棧操作及應(yīng)用2008/03/182KMP算法asdf abcabcpehkabdkdjfk abcabcakkabcabcakkabcabcakkabcabcakkabcabcakkabcabcakk if (i=-1|p-ci = t-cj) i+; j+; else i = nexti;while (k=0 & p-ci!=p-ck) k = nextk;i+; k+; nexti = k;while (k=0 & p-ci!=p-ck) k = nextk; i+; k+; if (p-ci = p-ck) nexti=nextk; elsenexti = k;3關(guān)于詩(shī)歌

2、系統(tǒng)：n上學(xué)期的成果可以繼承n也可以單獨(dú)發(fā)起新的題目n鼓勵(lì)深層探索n完成示例（側(cè)重思路與算法、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)）4關(guān)于大作業(yè)n詩(shī)歌相似性計(jì)算n詩(shī)歌風(fēng)格的定位（詩(shī)歌與類(lèi)）n詩(shī)人風(fēng)格的相似性（類(lèi)與類(lèi)）包括：q問(wèn)題定義（合理性）q基本思路q所需數(shù)據(jù)資源q算法q算法實(shí)現(xiàn)q1-2人組，21號(hào)前報(bào)名，20天完成q設(shè)計(jì)文檔 ：2分。實(shí)現(xiàn)：2分，創(chuàng)意：1分。n未來(lái)還有三個(gè)方向的大作業(yè)可選： 有關(guān)詩(shī)歌情景的網(wǎng)頁(yè)表現(xiàn)。（用到CSS，少量JavaScrip） 簡(jiǎn)單功能的詩(shī)歌網(wǎng)站系統(tǒng)的開(kāi)發(fā)（ASP.net, C#)。 一個(gè)有關(guān)最優(yōu)化的的題目（動(dòng)態(tài)規(guī)劃算法）。原來(lái)網(wǎng)站設(shè)計(jì)的小組可以大概按幾個(gè)方向分工。一般一個(gè)方向1-2人組

3、。既要分工，又要有統(tǒng)一的數(shù)據(jù)規(guī)范與接口標(biāo)準(zhǔn)?？梢詥为?dú)列出一個(gè)人員負(fù)責(zé)設(shè)計(jì)與文檔。對(duì)于有特殊數(shù)據(jù)基礎(chǔ)要求的也可以單獨(dú)有人做數(shù)據(jù)加工與整理以及數(shù)據(jù)規(guī)范的制定。5棧的應(yīng)用 數(shù)制轉(zhuǎn)換與遞歸n問(wèn)題：對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù)。 n算法：N = (N div d) * d + N mod d 512 = (514 / 8) * 8 + 514 mod 8 2 (64 / 8) * 8 + 64 mod 8 0 (8 / 8) * 8 + 8 mod 8 0 (1 / 8) * 8 + 1 mod 8 1 while(n != 0) /in stackpush(S,n%8)

4、;n=n/8;6棧的應(yīng)用 數(shù)制轉(zhuǎn)換與遞歸（續(xù)）7遞歸算法與數(shù)制轉(zhuǎn)換8棧的應(yīng)用 函數(shù)調(diào)用機(jī)制9棧的應(yīng)用 棧與遞歸q遞歸功能最終是由棧實(shí)現(xiàn)的，如果程序設(shè)計(jì)語(yǔ)言（如 C語(yǔ)言）提供了遞歸功能，那么，該功能最終由編譯器用棧實(shí)現(xiàn)。q如果程序設(shè)計(jì)語(yǔ)言不具備遞歸功能，如何用棧實(shí)現(xiàn)遞歸？10遞歸的基本概念n自身的簡(jiǎn)單情況來(lái)定義自己的方式，稱(chēng)為遞歸定義遞歸定義。n例：1 n=0n!= n*(n-1)! N0q在n階乘的定義中，當(dāng)n為0時(shí)定義為1，它不再用遞歸來(lái)定義，稱(chēng)為遞歸定義的出口，簡(jiǎn)稱(chēng)為遞歸出口。遞歸出口。11階乘的遞歸計(jì)算階乘的遞歸計(jì)算int fact( int n ) if ( n = 0 )return

5、 1; elsereturn ( n * fact( n 1 ) );函數(shù)fact( n )中又調(diào)用了函數(shù)fact，這種函數(shù)自己調(diào)用自己的作法稱(chēng)為遞歸調(diào)用遞歸調(diào)用。 包含直接還是間接遞歸調(diào)用的函數(shù)都稱(chēng)為遞歸函數(shù)遞歸函數(shù)。12用棧將遞歸轉(zhuǎn)為非遞歸int nfact( int n ) int res; PSeqStack st; /* 使用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧 */ st = createEmptyStack_seq( ); while (n0) push_seq(st, n); n = n 1; res = 1; while (! isEmptyStack_seq(st) res = res *

6、 top_seq(st); pop_seq(st); free(st); return ( res );13表達(dá)式計(jì)算表達(dá)式的構(gòu)成表達(dá)式的構(gòu)成： 操作數(shù) | 運(yùn)算符 | 界符（如括號(hào)）表達(dá)式的求值：表達(dá)式的求值： 例 5+6 (1+2)- 4 按照四則運(yùn)算法則，上述表達(dá)式的計(jì)算過(guò)程為： 5+6 (1+2)- 4=5+6 3- 4 = 5+18-4= 23-4=19 表達(dá)式中運(yùn)算符的運(yùn)算順序?yàn)椋?+ ， ， +， - ，如何確定運(yùn)算符的運(yùn)算順序？1234123414表達(dá)式的遞歸定義n二元運(yùn)算符的表達(dá)式定義: 表達(dá)式 := (算子) + (算符) + (算子) 算子 := 操作數(shù) | 表達(dá)式 操作

7、數(shù) := 標(biāo)識(shí)符 | 無(wú)符號(hào)整數(shù) 操作數(shù)、算符、界符 + 優(yōu)先級(jí) 15棧的應(yīng)用 表達(dá)式求值（續(xù)）n 表達(dá)式的三種標(biāo)識(shí)方法:q Exp = a b + (c d / e) fq前綴式: + a b c / d e fq中綴式: a b + c d / e fq后綴式: a b c d e / f +中綴式丟失了括弧信息，致使運(yùn)算的次序不確定。16后綴式的運(yùn)算n后綴式的運(yùn)算規(guī)則為: 運(yùn)算符在式中出現(xiàn)的順序恰為 表達(dá)式的運(yùn)算順序; 每個(gè)運(yùn)算符和在它之前出現(xiàn)，且緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小表達(dá)式（算子）。例：31 * ( 5 22 ) + 7031 5 22 - * 70 + -22531*22-1

8、73117后綴表達(dá)式的求值過(guò)程。n使用一個(gè)存放算子（運(yùn)算分量）的棧。n求值過(guò)程順序掃描后綴表達(dá)式，每次遇到算子便將它推入棧中；n遇到運(yùn)算符時(shí)，就從棧中彈出兩個(gè)整數(shù)(算子)進(jìn)行計(jì)算，而后再把結(jié)果推入棧中。n到掃描結(jié)束時(shí)，留在棧頂?shù)恼麛?shù)就是所求表達(dá)式的值。4123+ 3 5 * / -18從中綴表達(dá)式求得后綴式的規(guī)則1) 設(shè)立操作符棧棧2)設(shè)表達(dá)式的結(jié)束符為“#”, 設(shè)運(yùn)算符棧的棧底為“#”；3)若當(dāng)前字符串是個(gè)操作數(shù) 則直接發(fā)送給后綴式。 否則：若當(dāng)前運(yùn)算符的優(yōu)先數(shù)高于棧頂運(yùn)算符，則進(jìn)棧； 否則：退出棧頂運(yùn)算符發(fā)送給后綴式； goto step3; 4) “(” 對(duì)它之前后的運(yùn)算符起隔離作用，“)”可視為自相應(yīng)左括弧開(kāi)始的表達(dá)式的結(jié)束符。相遇則自動(dòng)取消。1921+ 運(yùn)算符優(yōu)先關(guān)系表20中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式 $ 3 * ( 7 + 3 * 6 / 2 5 ) $算符 棧頂棧外 棧頂棧外$3*(7+3*6*/2 / +-5 -*數(shù)21作業(yè)：n實(shí)現(xiàn)一個(gè)將包含四則運(yùn)算、括號(hào)的正整數(shù)表達(dá)式轉(zhuǎn)換為后綴形式的程序。該程序的輸入為一個(gè)字符串。輸出為轉(zhuǎn)換后