第3章 鏈棧及棧的應(yīng)用.ppt

1、第3章 鏈棧及棧的應(yīng)用,棧的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn),鏈棧：棧的鏈接存儲(chǔ)結(jié)構(gòu),特殊線性表?xiàng)?鏈棧需要加頭結(jié)點(diǎn)嗎？,如何改造鏈表實(shí)現(xiàn)棧的鏈接存儲(chǔ)？,將哪一端作為棧頂？,將鏈頭作為棧頂，方便操作。,鏈棧不需要附設(shè)頭結(jié)點(diǎn)。,棧的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn),棧頂,棧底,鏈棧：棧的鏈接存儲(chǔ)結(jié)構(gòu),特殊線性表?xiàng)?兩種示意圖在內(nèi)存中對應(yīng)同一種狀態(tài),棧頂,棧底,3 鏈棧 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈棧，它是運(yùn)算受限的單鏈表，其插入和刪除操作僅限制在表頭位置上進(jìn)行. 由于只能在鏈表頭部進(jìn)行操作，故鏈表沒有必要像單鏈表那樣附加頭結(jié)點(diǎn)。棧頂指針就是鏈表的頭指針。 其類型說明為： typedef struct StackNode Data

2、Type data struct StackNode *next ; StackNode *top;,(1) 初始化棧 void InitStack( StackNode *top) top=NULL; (2) 判斷空棧 int StackEmpty(StackNode *top) return top=NULL; (3)取棧頂 DataType GetTop(StackNode *top) if(StackEmpty(p) error(“stack is empty.”); return topdata; ,算法描述： void Push(StackNode *top,DataType x)

3、 s=(StackNode*)malloc(sizeof(StackNode); s-data=x; s-next=top; top=s; ,an,an-1,a1,(4) 入棧,操作接口： void Push( StackNode *top, DataType x),為 什 么 沒 有 判 斷 棧 滿 ？,算法描述： DataType Pop(StackNode *top) if(StackEmpty(top) error(“stack underflow.”); x=top-data; p=top; top=top-next; delete p; return x; ,(5)出棧,操作接口：

4、 DataType Pop(StackNode *top),an,an-1,a1,top+可以嗎？,3.2 棧的應(yīng)用舉例 1 數(shù)制轉(zhuǎn)換 十進(jìn)制N和其它進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問題,其解決方法很多,其中一個(gè)簡單算法基于下列原理: N=(n div d)*d+n mod d ( 其中:div為整除運(yùn)算,mod為求余運(yùn)算) 例如 (1348)10=(2504)8，其運(yùn)算過程如下：,N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 先入棧,再出棧 入棧順序:4,0,5,2. 出棧順序:2,5,0,4 所以 1348 = (2504)o,vo

5、id conversion( ) /輸入任意一個(gè)非負(fù)十進(jìn)制整數(shù),打印輸出與其等值的八進(jìn)制數(shù) InitStack(S); /初始化棧 scanf (“%d”,N); /輸入一個(gè)非負(fù)十進(jìn)制數(shù) while(N) / 非零時(shí),循環(huán) push(S,N%8);/余數(shù)入棧 N=N/8; while(! StackEmpty(S) Pop(S,e);/余數(shù)出棧 printf(“%d”,e); /conversion,2 行編輯程序 接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)。允許用戶輸入錯(cuò)誤，并在發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正。 例如:用戶發(fā)現(xiàn)輸入錯(cuò)誤時(shí),輸入”#”(退格符),以表示前一個(gè)字符無效; 輸入”(退行

6、符),表示當(dāng)前輸入的一行無效; 設(shè)一個(gè)棧接受輸入,每輸入一個(gè)字符,做如下判斷: 是無效符,刪除前一個(gè)入棧的符號 是退行符,刪除前一行入棧的符號 其它,入棧,行編輯程序算法如下: void LineEdit( ) /利用字符棧S,從終端接收一行并傳送至數(shù)據(jù)區(qū) InitStack(S); /構(gòu)造空棧 ch = getcher( ); /從終端接收第一個(gè)字符 while(ch!=EOF)/EOF為全文結(jié)束符 while(ch!=EOF /其它,入棧 ,ch=getchar( );/從終端接收下一個(gè)字符 /while /將從棧底到棧頂?shù)臈?nèi)字符傳送至調(diào)用過程的數(shù)據(jù)區(qū) ClearStack(S); if

7、(ch!=EOF) ch=getchar( ); DestroyStack(S); /LindeEdit,表達(dá)式的計(jì)算,在計(jì)算機(jī)中進(jìn)行算術(shù)表達(dá)式的計(jì)算是通過棧來實(shí)現(xiàn)的。 (1) 算術(shù)表達(dá)式的三種表示： 中綴：雙目運(yùn)算符出現(xiàn)在兩個(gè)操作數(shù)中間, 例：a+b 前綴：雙目運(yùn)算符出現(xiàn)在兩個(gè)操作數(shù)前面, 例：+ab 后綴：雙目運(yùn)算符出現(xiàn)在兩個(gè)操作數(shù)后面, 例：ab+,(2) 三種表達(dá)式之間的轉(zhuǎn)換： 按運(yùn)算的優(yōu)先次序全部加上括號，逐個(gè)括號寫成另一種表示式 （ 括號 * ，/ +，- ） 注意：操作數(shù)出現(xiàn)的順序不變,3 表達(dá)式求值,三種表達(dá)式之間的轉(zhuǎn)換： 例 將中綴表達(dá)式： 轉(zhuǎn)換成后綴表達(dá)式 （A+B）*D

8、E/（F +A*D）+C,AB+ F AD* +,AB+ D* E FAD*+ /,AB+D* EFAD*+/ -,AB+D* EFAD*+/ - C+,例：A+B*D E / F +A*D +C,ABD*+EF/ - AD* + C+,把表達(dá)式翻譯成正確的機(jī)器執(zhí)行指令,要正確地解釋表達(dá)式. 算符優(yōu)先法是根據(jù)算術(shù)四則運(yùn)算的規(guī)定來編譯或解釋表達(dá)式的. 表達(dá)式由操作數(shù),運(yùn)算符,界限符組成.操作數(shù)可以是變量或常量;此處考慮的運(yùn)算符僅為+-*/,界限符有左右括號和結(jié)束符”#”. 為實(shí)現(xiàn)算符優(yōu)先法,可以使用兩個(gè)工作棧.OPTR:存放運(yùn)算符, OPND:存放操作數(shù)或運(yùn)算結(jié)果.,算法的基本思想: (1)置操

9、作數(shù)棧為空,表達(dá)式起始符”#”,作為運(yùn)算符棧的棧底. (2)依次讀入表達(dá)式中每個(gè)字符,若是操作數(shù)進(jìn)OPND棧,若是運(yùn)算符,則和OPTR棧的棧頂運(yùn)算符比較優(yōu)先權(quán)后作相應(yīng)操作,直至整個(gè)表達(dá)式求值完畢(即OPTR棧的棧頂元素和當(dāng)前讀入的字符均為”#”).,算法 OperandType EvaluateExpression() /算術(shù)表達(dá)式求值的算符優(yōu)先算法,設(shè)OPTR和OPND分別為運(yùn)算符棧和操作數(shù)棧;OP為算符(運(yùn)算符和界限符)集合 InitStack(OPTR;) Push(OPTR,#);InitStack(OPND);c=getchar(); while(c!=#|GetTop(OPTR)!

10、=#) if (!In(c,OP)Push(OPND,c);c=getchar();/操作數(shù)進(jìn)操作數(shù)棧 else switch(Precede(GetTop(OPTR),c) case : /棧頂元素優(yōu)先權(quán)低,進(jìn)運(yùn)算符棧 Push(OPTR,c);c=getchar(); break; case =:/脫括號并接收下一個(gè)字符,左右括號或兩”#”相遇 Pop(OPTR,x);c=getchar(); break;,case : /棧頂元素優(yōu)先權(quán)高, 運(yùn)算符退棧,操作數(shù)退棧, /并將運(yùn)算結(jié)果入棧 Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPN

11、D,Operate(a,theta,b); break; /switch /while return GetTop(OPND); /EvaluateExpression,“-”大于”)”,“(”等于”)”,3.3 棧與遞歸,若在一個(gè)函數(shù)、過程或者數(shù)據(jù)結(jié)構(gòu)定義的內(nèi)部，直接或間接出現(xiàn)定義本身的應(yīng)用，則稱它們是遞歸的，或者是遞歸定義的。 遞歸是一種強(qiáng)有力的數(shù)學(xué)工具，它可使問題的描述和求解變得簡潔和清晰。 遞歸算法常常比非遞歸算法更易設(shè)計(jì)，尤其是當(dāng)問題本身或所涉及的數(shù)據(jù)結(jié)構(gòu)是遞歸定義的時(shí)候，使用遞歸算法特別合適。,例: 斐波那契數(shù)列為：0、1、1、2、3、，即： fib(0)=0; fib(1)=1;

12、 fib(n)=fib(n-1)+fib(n-2) （當(dāng)n1時(shí)）。 寫成遞歸函數(shù)有： int fib(int n) if (n=0) return 0; if (n=1) return 1; if (n1) return fib(n-1)+fib(n-2); ,遞歸執(zhí)行分遞推和回歸兩個(gè)階段。 在遞推階段，把較復(fù)雜的問題（規(guī)模為n）的求解推到比原問題簡單一些的問題（規(guī)模小于n）的求解。例如求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。而計(jì)算fib(n-1)和fib(n-2)，又必須先計(jì)算fib(n-3)和fib(n-4)。依次類推，直至計(jì)算fib(1)和fib(0)，分別能立

13、即得到結(jié)果1和0。在遞推階段，必須要有終止遞歸的情況。例如在函數(shù)fib中，當(dāng)n為1和0的情況。 在回歸階段，當(dāng)獲得最簡單情況的解后，逐級返回，依次得到稍復(fù)雜問題的解，例如得到fib(1)和fib(0)后，返回得到fib(2)的結(jié)果，在得到了fib(n-1)和fib(n-2)的結(jié)果后，返回得到fib(n)的結(jié)果。,通常,一個(gè)函數(shù)調(diào)用另一個(gè)函數(shù)之前,要作如下工作: a)將實(shí)在參數(shù),返回地址等信息傳遞給被調(diào)用函數(shù)保存; b)為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)區(qū); c)將控制轉(zhuǎn)移到被調(diào)函數(shù)的入口. 從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前,也要做三件事情: a)保存被調(diào)函數(shù)的計(jì)算結(jié)果; b)釋放被調(diào)用函數(shù)的數(shù)據(jù)區(qū); c)依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù). 變量和地址等數(shù)據(jù)都是保存在系統(tǒng)所分配的棧中的.為了