第3章 鏈棧及棧的應用.ppt

1、第3章 鏈棧及棧的應用,棧的鏈接存儲結構及實現,鏈棧：棧的鏈接存儲結構,特殊線性表棧,鏈棧需要加頭結點嗎？,如何改造鏈表實現棧的鏈接存儲？,將哪一端作為棧頂？,將鏈頭作為棧頂，方便操作。,鏈棧不需要附設頭結點。,棧的鏈接存儲結構及實現,棧頂,棧底,鏈棧：棧的鏈接存儲結構,特殊線性表棧,兩種示意圖在內存中對應同一種狀態(tài),棧頂,棧底,3 鏈棧 棧的鏈式存儲結構稱為鏈棧，它是運算受限的單鏈表，其插入和刪除操作僅限制在表頭位置上進行. 由于只能在鏈表頭部進行操作，故鏈表沒有必要像單鏈表那樣附加頭結點。棧頂指針就是鏈表的頭指針。 其類型說明為： 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 棧的應用舉例 1 數制轉換 十進制N和其它進制數的轉換是計算機實現計算的基本問題,其解決方法很多,其中一個簡單算法基于下列原理: N=(n div d)*d+n mod d ( 其中:div為整除運算,mod為求余運算) 例如 (1348)10=(2504)8，其運算過程如下：,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( ) /輸入任意一個非負十進制整數,打印輸出與其等值的八進制數 InitStack(S); /初始化棧 scanf (“%d”,N); /輸入一個非負十進制數 while(N) / 非零時,循環(huán) push(S,N%8);/余數入棧 N=N/8; while(! StackEmpty(S) Pop(S,e);/余數出棧 printf(“%d”,e); /conversion,2 行編輯程序 接受用戶輸入的一行字符，然后逐行存入用戶數據區(qū)。允許用戶輸入錯誤，并在發(fā)現有誤時可以及時更正。 例如:用戶發(fā)現輸入錯誤時,輸入”#”(退格符),以表示前一個字符無效; 輸入”(退行

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

7、(ch!=EOF) ch=getchar( ); DestroyStack(S); /LindeEdit,表達式的計算,在計算機中進行算術表達式的計算是通過棧來實現的。 (1) 算術表達式的三種表示： 中綴：雙目運算符出現在兩個操作數中間, 例：a+b 前綴：雙目運算符出現在兩個操作數前面, 例：+ab 后綴：雙目運算符出現在兩個操作數后面, 例：ab+,(2) 三種表達式之間的轉換： 按運算的優(yōu)先次序全部加上括號，逐個括號寫成另一種表示式 （ 括號 * ，/ +，- ） 注意：操作數出現的順序不變,3 表達式求值,三種表達式之間的轉換： 例 將中綴表達式： 轉換成后綴表達式 （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+,把表達式翻譯成正確的機器執(zhí)行指令,要正確地解釋表達式. 算符優(yōu)先法是根據算術四則運算的規(guī)定來編譯或解釋表達式的. 表達式由操作數,運算符,界限符組成.操作數可以是變量或常量;此處考慮的運算符僅為+-*/,界限符有左右括號和結束符”#”. 為實現算符優(yōu)先法,可以使用兩個工作棧.OPTR:存放運算符, OPND:存放操作數或運算結果.,算法的基本思想: (1)置操

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

10、=#) if (!In(c,OP)Push(OPND,c);c=getchar();/操作數進操作數棧 else switch(Precede(GetTop(OPTR),c) case : /棧頂元素優(yōu)先權低,進運算符棧 Push(OPTR,c);c=getchar(); break; case =:/脫括號并接收下一個字符,左右括號或兩”#”相遇 Pop(OPTR,x);c=getchar(); break;,case : /棧頂元素優(yōu)先權高, 運算符退棧,操作數退棧, /并將運算結果入棧 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 棧與遞歸,若在一個函數、過程或者數據結構定義的內部，直接或間接出現定義本身的應用，則稱它們是遞歸的，或者是遞歸定義的。 遞歸是一種強有力的數學工具，它可使問題的描述和求解變得簡潔和清晰。 遞歸算法常常比非遞歸算法更易設計，尤其是當問題本身或所涉及的數據結構是遞歸定義的時候，使用遞歸算法特別合適。,例: 斐波那契數列為：0、1、1、2、3、，即： fib(0)=0; fib(1)=1;

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

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