鏈棧及棧的應用

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

棧的鏈式存儲結(jié)構稱為鏈棧，它是運算受限的單鏈表，其插入和刪除操作僅限制在表頭位置上進行.

由于只能在鏈表頭部進行操作，故鏈表沒有必要像單鏈表那樣附加頭結(jié)點。棧頂指針就是鏈表的頭指針。其類型說明為：

typedefstructStackNode{DataTypedatastructStackNode*next}; StackNode*top;第4頁,共26頁，2024年2月25日，星期天(1)初始化棧

voidInitStack(StackNode*top){ top=NULL;}(2)判斷空棧

intStackEmpty(StackNode*top){

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

returntop–>data;}第5頁,共26頁，2024年2月25日，星期天算法描述：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){為什么沒有判斷棧滿？第6頁,共26頁，2024年2月25日，星期天算法描述：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++可以嗎？第7頁,共26頁，2024年2月25日，星期天

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

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

例如(1348)10=(2504)8，其運算過程如下：第8頁,共26頁，2024年2月25日，星期天

NNdiv8Nmod8134816841682102125202

先入棧,再出棧入棧順序:4,0,5,2.

出棧順序:2,5,0,4

所以1348=(2504)o第9頁,共26頁，2024年2月25日，星期天

voidconversion(){//輸入任意一個非負十進制整數(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);}}//conversion第10頁,共26頁，2024年2月25日，星期天2行編輯程序接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)。允許用戶輸入錯誤，并在發(fā)現(xiàn)有誤時可以及時更正。

例如:用戶發(fā)現(xiàn)輸入錯誤時,輸入”#”(退格符),以表示前一個字符無效;輸入”@”(退行符),表示當前輸入的一行無效;

設一個棧接受輸入,每輸入一個字符,做如下判斷:

是無效符,刪除前一個入棧的符號是退行符,刪除前一行入棧的符號其它,入棧第11頁,共26頁，2024年2月25日，星期天行編輯程序算法如下:

voidLineEdit(){//利用字符棧S,從終端接收一行并傳送至數(shù)據(jù)區(qū)

InitStack(S);//構造空棧

ch=getcher();//從終端接收第一個字符

while(ch!=EOF){//EOF為全文結(jié)束符

while(ch!=EOF&&ch!=‘\n’){switch(ch){case‘#’:Pop(S,c);//無效符,出棧

case‘@’:ClearStack(S);//退行符,清空棧

default:Push(S,ch);//其它,入棧

}

第12頁,共26頁，2024年2月25日，星期天

ch=getchar();//從終端接收下一個字符

}//while//將從棧底到棧頂?shù)臈?nèi)字符傳送至調(diào)用過程的數(shù)據(jù)區(qū)ClearStack(S);if(ch!=EOF)ch=getchar();}DestroyStack(S);}//LindeEdit第13頁,共26頁，2024年2月25日，星期天表達式的計算在計算機中進行算術表達式的計算是通過棧來實現(xiàn)的。

(1)算術表達式的三種表示：中綴：——雙目運算符出現(xiàn)在兩個操作數(shù)中間,例：a+b前綴：——雙目運算符出現(xiàn)在兩個操作數(shù)前面,例：+ab后綴：——雙目運算符出現(xiàn)在兩個操作數(shù)后面,例：ab+(2)三種表達式之間的轉(zhuǎn)換：按運算的優(yōu)先次序全部加上括號，逐個括號寫成另一種表示式（括號——*，/——+，-）注意：操作數(shù)出現(xiàn)的順序不變3表達式求值第14頁,共26頁，2024年2月25日，星期天三種表達式之間的轉(zhuǎn)換：例將中綴表達式：——轉(zhuǎn)換成后綴表達式（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+第15頁,共26頁，2024年2月25日，星期天把表達式翻譯成正確的機器執(zhí)行指令,要正確地解釋表達式.

算符優(yōu)先法是根據(jù)算術四則運算的規(guī)定來編譯或解釋表達式的.

表達式由操作數(shù),運算符,界限符組成.操作數(shù)可以是變量或常量;此處考慮的運算符僅為+-*/,界限符有左右括號和結(jié)束符”#”.

為實現(xiàn)算符優(yōu)先法,可以使用兩個工作棧.OPTR:存放運算符,OPND:存放操作數(shù)或運算結(jié)果.

第16頁,共26頁，2024年2月25日，星期天算法的基本思想:(1)置操作數(shù)棧為空,表達式起始符”#”,作為運算符棧的棧底.(2)依次讀入表達式中每個字符,若是操作數(shù)進OPND棧,若是運算符,則和OPTR棧的棧頂運算符比較優(yōu)先權后作相應操作,直至整個表達式求值完畢(即OPTR棧的棧頂元素和當前讀入的字符均為”#”).第17頁,共26頁，2024年2月25日，星期天算法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;第18頁,共26頁，2024年2月25日，星期天

case‘>’://棧頂元素優(yōu)先權高,運算符退棧,操作數(shù)退棧,//并將運算結(jié)果入棧

Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}//switch}//whilereturnGetTop(OPND);}//EvaluateExpression第19頁,共26頁，2024年2月25日，星期天步驟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)“-”大于”)”“(”等于”)”第20頁,共26頁，2024年2月25日，星期天3.3棧與遞歸

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

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

遞歸算法常常比非遞歸算法更易設計，尤其是當問題本身或所涉及的數(shù)據(jù)結(jié)構是遞歸定義的時候，使用遞歸算法特別合適。第21頁,共26頁，2024年2月25日，星期天例:斐波那契數(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);

}

第22頁,共26頁，2024年2月25日，星期天

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

在回歸階段，當獲得最簡單情況的解后，逐級返回，依次得到稍復雜問題的解，例如得到fib(1)和fib(0)后，返回得到fib(2)的結(jié)果，……，在得到了fib(n-1)和fib(n-2)的結(jié)果后，返回得到fib(n)的結(jié)果。第23頁,共26頁，2024年2月25日，星期天

通常,一個函數(shù)調(diào)用另一個函數(shù)之前,要作如下工作:a)將實在參數(shù),返回地址等信息傳遞給被調(diào)用函數(shù)保存;b)為被調(diào)用函數(shù)的局部變量分配存儲區(qū);c)將控制轉(zhuǎn)移到被調(diào)函數(shù)的入口.

從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前,也要做三件事情:a)保存被調(diào)函數(shù)的計算結(jié)果;b)釋放被調(diào)用函數(shù)的數(shù)據(jù)區(qū);c)依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù).

變量和地址等數(shù)據(jù)都是保存在系統(tǒng)所分配的棧中的.為了保證遞歸函數(shù)正確執(zhí)行,系統(tǒng)需設立一個”遞歸工作棧”,作為數(shù)據(jù)存儲區(qū).用