鏈棧及棧的應(yīng)用

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

棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)為鏈棧，它是運(yùn)算受限的單鏈表，其插入和刪除操作僅限制在表頭位置上進(jìn)行.

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

typedefstructStackNode{DataTypedatastructStackNode*next}; StackNode*top;第4頁(yè),共26頁(yè)，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頁(yè),共26頁(yè)，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){為什么沒(méi)有判斷棧滿(mǎn)？第6頁(yè),共26頁(yè)，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頁(yè),共26頁(yè)，2024年2月25日，星期天

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

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

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

NNdiv8Nmod8134816841682102125202

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

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

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

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

例如:用戶(hù)發(fā)現(xiàn)輸入錯(cuò)誤時(shí),輸入”#”(退格符),以表示前一個(gè)字符無(wú)效;輸入”@”(退行符),表示當(dāng)前輸入的一行無(wú)效;

設(shè)一個(gè)棧接受輸入,每輸入一個(gè)字符,做如下判斷:

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

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

InitStack(S);//構(gòu)造空棧

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

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

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

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

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

}

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

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

}//while//將從棧底到棧頂?shù)臈?nèi)字符傳送至調(diào)用過(guò)程的數(shù)據(jù)區(qū)ClearStack(S);if(ch!=EOF)ch=getchar();}DestroyStack(S);}//LindeEdit第13頁(yè),共26頁(yè)，2024年2月25日，星期天表達(dá)式的計(jì)算在計(jì)算機(jī)中進(jìn)行算術(shù)表達(dá)式的計(jì)算是通過(guò)棧來(lái)實(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)先次序全部加上括號(hào)，逐個(gè)括號(hào)寫(xiě)成另一種表示式（括號(hào)——*，/——+，-）注意：操作數(shù)出現(xiàn)的順序不變3表達(dá)式求值第14頁(yè),共26頁(yè)，2024年2月25日，星期天三種表達(dá)式之間的轉(zhuǎn)換：例將中綴表達(dá)式：——轉(zhuǎn)換成后綴表達(dá)式（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頁(yè),共26頁(yè)，2024年2月25日，星期天把表達(dá)式翻譯成正確的機(jī)器執(zhí)行指令,要正確地解釋表達(dá)式.

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

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

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

第16頁(yè),共26頁(yè)，2024年2月25日，星期天算法的基本思想:(1)置操作數(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)前讀入的字符均為”#”).第17頁(yè),共26頁(yè)，2024年2月25日，星期天算法OperandTypeEvaluateExpression(){//算術(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)!=‘#’){if(!In(c,OP)){Push((OPND,c);c=getchar();}//操作數(shù)進(jìn)操作數(shù)棧

elseswitch(Precede(GetTop(OPTR),c){case‘<’://棧頂元素優(yōu)先權(quán)低,進(jìn)運(yùn)算符棧

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

Pop(OPTR,x);c=getchar();break;第18頁(yè),共26頁(yè)，2024年2月25日，星期天

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

Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}//switch}//whilereturnGetTop(OPND);}//EvaluateExpression第19頁(yè),共26頁(yè)，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){消去括號(hào)}9#*35#

operate(‘3,’,’*’,’5’)10#15#

return(GetTop(OPND)“-”大于”)”“(”等于”)”第20頁(yè),共26頁(yè)，2024年2月25日，星期天3.3棧與遞歸

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

遞歸是一種強(qiáng)有力的數(shù)學(xué)工具，它可使問(wèn)題的描述和求解變得簡(jiǎn)潔和清晰。

遞歸算法常常比非遞歸算法更易設(shè)計(jì)，尤其是當(dāng)問(wèn)題本身或所涉及的數(shù)據(jù)結(jié)構(gòu)是遞歸定義的時(shí)候，使用遞歸算法特別合適。第21頁(yè),共26頁(yè)，2024年2月25日，星期天例:斐波那契數(shù)列為：0、1、1、2、3、……，即：

fib(0)=0;

fib(1)=1;

fib(n)=fib(n-1)+fib(n-2)（當(dāng)n>1時(shí)）。

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

intfib(intn)

{if(n==0)return0;

if(n==1)return1;

if(n>1)returnfib(n-1)+fib(n-2);

}

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

遞歸執(zhí)行分遞推和回歸兩個(gè)階段。在遞推階段，把較復(fù)雜的問(wèn)題（規(guī)模為n）的求解推到比原問(wèn)題簡(jiǎn)單一些的問(wè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)。依次類(lèi)推，直至計(jì)算fib(1)和fib(0)，分別能立即得到結(jié)果1和0。在遞推階段，必須要有終止遞歸的情況。例如在函數(shù)fib中，當(dāng)n為1和0的情況。

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

通常,一個(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)所分配的棧中的.為了保證遞歸函數(shù)正確執(zhí)行,系統(tǒng)需設(shè)立一個(gè)”遞歸工作?！?作為數(shù)據(jù)存儲(chǔ)區(qū).用