第3章鏈棧

及棧的應用棧的鏈接存儲結構及實現(xiàn)鏈棧：棧的鏈接存儲結構特殊線性表——棧firsta1a2an∧ai鏈棧需要加頭結點嗎？如何改造鏈表實現(xiàn)棧的鏈接存儲？將哪一端作為棧頂？將鏈頭作為棧頂，方便操作。鏈棧不需要附設頭結點。棧的鏈接存儲結構及實現(xiàn)棧頂棧底鏈棧：棧的鏈接存儲結構特殊線性表——棧topanan-1a1∧firsta1a2an∧ai兩種示意圖在內(nèi)存中對應同一種狀態(tài)topa1an-1an∧棧頂棧底3鏈棧

棧的鏈式存儲結構稱為鏈棧，它是運算受限的單鏈表，其插入和刪除操作僅限制在表頭位置上進行.由于只能在鏈表頭部進行操作，故鏈表沒有必要像單鏈表那樣附加頭結點。棧頂指針就是鏈表的頭指針。其類型說明為：typedefstructStackNode{DataTypedatastructStackNode*next}; StackNode*top;(1)初始化棧voidInitStack(StackNode*top){ top=NULL;}(2)判斷空棧intStackEmpty(StackNode*top){

returntop==NULL;}(3)取棧頂DataTypeGetTop(StackNode*top){if(StackEmpty(p))error(“stackisempty.”);

returntop–>data;}算法描述：voidPush(StackNode*top,DataTypex){ s=(StackNode*)malloc(sizeof(StackNode));

s->data=x;s->next=top;top=s;}topanan-1a1∧(4)入棧xstop操作接口：voidPush(StackNode*top,DataTypex){為什么沒有判斷棧滿？算法描述：DataTypePop(StackNode*top){if(StackEmpty(top)error(“stackunderflow.”);x=top->data;p=top;top=top->next;deletep;returnx;}(5)出棧操作接口：DataTypePop(StackNode*top)topanan-1a1∧topp

top++可以嗎？

3.2棧的應用舉例1數(shù)制轉換

十進制N和其它進制數(shù)的轉換是計算機實現(xiàn)計算的基本問題,其解決方法很多,其中一個簡單算法基于下列原理:N=(ndivd)*d+nmodd(其中:div為整除運算,mod為求余運算)例如(1348)10=(2504)8，其運算過程如下：

NNdiv8Nmod8134816841682102125202先入棧,再出棧入棧順序:4,0,5,2.出棧順序:2,5,0,4所以1348=(2504)ovoidconversion(){//輸入任意一個非負十進制整數(shù),打印輸出與其等值的八進制數(shù)InitStack(S);//初始化棧scanf(“%d”,N);//輸入一個非負十進制數(shù)while(N){//非零時,循環(huán)push(S,N%8);//余數(shù)入棧N=N/8;}while(!StackEmpty(S)){Pop(S,e);//余數(shù)出棧printf(“%d”,e);}}//conversion2行編輯程序接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)。允許用戶輸入錯誤，并在發(fā)現(xiàn)有誤時可以及時更正。

例如:用戶發(fā)現(xiàn)輸入錯誤時,輸入”#”(退格符),以表示前一個字符無效;輸入”@”(退行符),表示當前輸入的一行無效;設一個棧接受輸入,每輸入一個字符,做如下判斷:是無效符,刪除前一個入棧的符號是退行符,刪除前一行入棧的符號其它,入棧行編輯程序算法如下:

voidLineEdit(){//利用字符棧S,從終端接收一行并傳送至數(shù)據(jù)區(qū)InitStack(S);//構造空棧ch=getcher();//從終端接收第一個字符while(ch!=EOF){//EOF為全文結束符while(ch!=EOF&&ch!=‘\n’){switch(ch){case‘#’:Pop(S,c);//無效符,出棧case‘@’:ClearStack(S);//退行符,清空棧default:Push(S,ch);//其它,入棧}

ch=getchar();//從終端接收下一個字符}//while//將從棧底到棧頂?shù)臈?nèi)字符傳送至調(diào)用過程的數(shù)據(jù)區(qū)ClearStack(S);if(ch!=EOF)ch=getchar();}DestroyStack(S);}//LindeEdit表達式的計算在計算機中進行算術表達式的計算是通過棧來實現(xiàn)的。

(1)算術表達式的三種表示：中綴：——雙目運算符出現(xiàn)在兩個操作數(shù)中間,例：a+b前綴：——雙目運算符出現(xiàn)在兩個操作數(shù)前面,例：+ab后綴：——雙目運算符出現(xiàn)在兩個操作數(shù)后面,例：ab+(2)三種表達式之間的轉換：按運算的優(yōu)先次序全部加上括號，逐個括號寫成另一種表示式（括號——*，/——+，-）注意：操作數(shù)出現(xiàn)的順序不變3表達式求值三種表達式之間的轉換：例將中綴表達式：——轉換成后綴表達式（A+B）*D–E/（F+A*D）+CAB+FAD*+AB+D*EFAD*+/AB+D*EFAD*+/-AB+D*EFAD*+/-C+例：A+B*D–E/F+A*D+CABD*+EF/-AD*+C+把表達式翻譯成正確的機器執(zhí)行指令,要正確地解釋表達式.算符優(yōu)先法是根據(jù)算術四則運算的規(guī)定來編譯或解釋表達式的.表達式由操作數(shù),運算符,界限符組成.操作數(shù)可以是變量或常量;此處考慮的運算符僅為+-*/,界限符有左右括號和結束符”#”.為實現(xiàn)算符優(yōu)先法,可以使用兩個工作棧.OPTR:存放運算符,OPND:存放操作數(shù)或運算結果.

算法的基本思想:(1)置操作數(shù)棧為空,表達式起始符”#”,作為運算符棧的棧底.(2)依次讀入表達式中每個字符,若是操作數(shù)進OPND棧,若是運算符,則和OPTR棧的棧頂運算符比較優(yōu)先權后作相應操作,直至整個表達式求值完畢(即OPTR棧的棧頂元素和當前讀入的字符均為”#”).算法OperandTypeEvaluateExpression(){//算術表達式求值的算符優(yōu)先算法,設OPTR和OPND分別為運算符棧和操作數(shù)棧;OP為算符(運算符和界限符)集合InitStack(OPTR;)Push(OPTR,’#’);InitStack(OPND);c=getchar();while(c!=‘#’||GetTop(OPTR)!=‘#’){if(!In(c,OP)){Push((OPND,c);c=getchar();}//操作數(shù)進操作數(shù)棧elseswitch(Precede(GetTop(OPTR),c){case‘<’://棧頂元素優(yōu)先權低,進運算符棧

Push(OPTR,c);c=getchar();break;case‘=’://脫括號并接收下一個字符,左右括號或兩”#”相遇

Pop(OPTR,x);c=getchar();break;case‘>’://棧頂元素優(yōu)先權高,運算符退棧,操作數(shù)退棧,//并將運算結果入棧

Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}//switch}//whilereturnGetTop(OPND);}//EvaluateExpression步驟OPTR棧OPND棧輸入字符主要操作1#3*(7–2)#PUSH(OPND,’3’)2#3*(7–2)#PUSH(OPTR,’*’)3#*3

(7–2)#PUSH(OPTR,’(’)4#*(3

7

–2)#PUSH(OPND,’7’)5#*(37

–2)#PUSH(OPTR,’-’)6#*(-372)#PUSH(OPND,’2’)7#*(-372)

#operate(‘7’,’-’,’2’)8#*(35)#POP(OPTR){消去括號}9#*35#operate(‘3,’,’*’,’5’)10#15#return(GetTop(OPND)“-”大于”)”“(”等于”)”3.3棧與遞歸

若在一個函數(shù)、過程或者數(shù)據(jù)結構定義的內(nèi)部，直接或間接出現(xiàn)定義本身的應用，則稱它們是遞歸的，或者是遞歸定義的。

遞歸是一種強有力的數(shù)學工具，它可使問題的描述和求解變得簡潔和清晰。

遞歸算法常常比非遞歸算法更易設計，尤其是當問題本身或所涉及的數(shù)據(jù)結構是遞歸定義的時候，使用遞歸算法特別合適。例:斐波那契數(shù)列為：0、1、1、2、3、……，即：

fib(0)=0;

fib(1)=1;

fib(n)=fib(n-1)+fib(n-2)（當n>1時）。

寫成遞歸函數(shù)有：

intfib(intn)

{if(n==0)return0;

if(n==1)return1;

if(n>1)returnfib(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)，分別能立即得到結果1和0。在遞推階段，必須要有終止遞歸的情況。例如在函數(shù)fib中，當n為1和0的情況。

在回歸階段，當獲得最簡單情況的解后，逐級返回，依次得到稍復雜問題的解，例如得到fib(1)和fib(0)后，返回得到fib(2)的結果，……，在得到了fib(n-1)和fib(n-2)的結果后，返回得到fib(n)的結果。

通常,一個函數(shù)調(diào)用另一個函數(shù)之前,要作如下工作:a)將實在參數(shù),返回地址等信息傳遞給被調(diào)用函數(shù)保存;b)為被調(diào)用函數(shù)的局部變量分配存儲區(qū);c)將控制轉移到被調(diào)函數(shù)的入口.從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前,也要做三件事情:a)保存被調(diào)函數(shù)的計算結果;b)釋放被調(diào)用函數(shù)的數(shù)據(jù)區(qū);c)依照被調(diào)函數(shù)保存的返回地址將控制轉移到調(diào)用函數(shù).變量和地址等數(shù)據(jù)都是保存在系統(tǒng)所分配的棧中的.為了保證遞歸函數(shù)正確執(zhí)行,系統(tǒng)需設立一個”遞歸工作?！?作為數(shù)據(jù)存儲區(qū).用來存儲所有的實在參數(shù),所有