鏈棧及棧的應用第1頁，課件共26頁，創作于2023年2月棧的鏈接存儲結構及實現鏈棧：棧的鏈接存儲結構特殊線性表——棧firsta1a2an∧ai鏈棧需要加頭結點嗎？如何改造鏈表實現棧的鏈接存儲？將哪一端作為棧頂？將鏈頭作為棧頂，方便操作。鏈棧不需要附設頭結點。第2頁，課件共26頁，創作于2023年2月棧的鏈接存儲結構及實現棧頂棧底鏈棧：棧的鏈接存儲結構特殊線性表——棧topanan-1a1∧firsta1a2an∧ai兩種示意圖在內存中對應同一種狀態topa1an-1an∧棧頂棧底第3頁，課件共26頁，創作于2023年2月3鏈棧

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

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

typedefstructStackNode{DataTypedatastructStackNode*next}; StackNode*top;第4頁，課件共26頁，創作于2023年2月(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頁，創作于2023年2月算法描述：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頁，創作于2023年2月算法描述：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頁，創作于2023年2月

3.2棧的應用舉例1數制轉換

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

例如(1348)10=(2504)8，其運算過程如下：第8頁，課件共26頁，創作于2023年2月

NNdiv8Nmod8134816841682102125202

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

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

所以1348=(2504)o第9頁，課件共26頁，創作于2023年2月

voidconversion(){//輸入任意一個非負十進制整數,打印輸出與其等值的八進制數

InitStack(S);//初始化棧

scanf(“%d”,N);//輸入一個非負十進制數

while(N){//非零時,循環

push(S,N%8);//余數入棧

N=N/8;}while(!StackEmpty(S)){Pop(S,e);//余數出棧

printf(“%d”,e);}}//conversion第10頁，課件共26頁，創作于2023年2月2行編輯程序接受用戶輸入的一行字符，然后逐行存入用戶數據區。允許用戶輸入錯誤，并在發現有誤時可以及時更正。

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

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

是無效符,刪除前一個入棧的符號是退行符,刪除前一行入棧的符號其它,入棧第11頁，課件共26頁，創作于2023年2月行編輯程序算法如下:

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

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);//其它,入棧

}

第12頁，課件共26頁，創作于2023年2月

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

}//while//將從棧底到棧頂的棧內字符傳送至調用過程的數據區ClearStack(S);if(ch!=EOF)ch=getchar();}DestroyStack(S);}//LindeEdit第13頁，課件共26頁，創作于2023年2月表達式的計算在計算機中進行算術表達式的計算是通過棧來實現的。

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

算符優先法是根據算術四則運算的規定來編譯或解釋表達式的.

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

為實現算符優先法,可以使用兩個工作棧.OPTR:存放運算符,OPND:存放操作數或運算結果.

第16頁，課件共26頁，創作于2023年2月算法的基本思想:(1)置操作數棧為空,表達式起始符”#”,作為運算符棧的棧底.(2)依次讀入表達式中每個字符,若是操作數進OPND棧,若是運算符,則和OPTR棧的棧頂運算符比較優先權后作相應操作,直至整個表達式求值完畢(即OPTR棧的棧頂元素和當前讀入的字符均為”#”).第17頁，課件共26頁，創作于2023年2月算法OperandTypeEvaluateExpression(){//算術表達式求值的算符優先算法,設OPTR和OPND分別為運算符棧和操作數棧;OP為算符(運算符和界限符)集合

InitStack(OPTR;)Push(OPTR,’#’);InitStack(OPND);c=getchar();while(c!=‘#’||GetTop(OPTR)!=‘#’){if(!In(c,OP)){Push((OPND,c);c=getchar();}//操作數進操作數棧

elseswitch(Precede(GetTop(OPTR),c){case‘<’://棧頂元素優先權低,進運算符棧

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

Pop(OPTR,x);c=getchar();break;第18頁，課件共26頁，創作于2023年2月

case‘>’://棧頂元素優先權高,運算符退棧,操作數退棧,//并將運算結果入棧

Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}//switch}//whilereturnGetTop(OPND);}//EvaluateExpression第19頁，課件共26頁，創作于2023年2月步驟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頁，創作于2023年2月3.3棧與遞歸

若在一個函數、過程或者數據結構定義的內部，直接或間接出現定義本身的應用，則稱它們是遞歸的，或者是遞歸定義的。

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

遞歸算法常常比非遞歸算法更易設計，尤其是當問題本身或所涉及的數據結構是遞歸定義的時候，使用遞歸算法特別合適。第21頁，課件共26頁，創作于2023年2月例:斐波那契數列為：0、1、1、2、3、……，即：

fib(0)=0;

fib(1)=1;

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

寫成遞歸函數有：

intfib(intn)

{if(n==0)return0;

if(n==1)return1;

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

}

第22頁，課件共26頁，創作于2023年2月

遞歸執行分遞推和回歸兩個階段。在遞推階段，把較復雜的問題（規模為n）的求解推到比原問題簡單一些的問題（規模小于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。在遞推階段，必須要有終止遞歸的情況。例如在函數fib中，當n為1和0的情況。

在回歸階段，當獲得最簡單情況的解后，逐級返回，依次得到稍復雜問題的解，例如得到fib(1)和fib(0)后，返回得到fib(2)的結果，……，在得到了fib(n-1)和fib(n-2)的結果后，返回得到fib(n)的結果。第23頁，課件共26頁，創作于2023年2月

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

從被調用函數返回調用函數之前,也要做三件事情:a)保存被調函數的計算結果;b)釋放被調用函數的數據區;c)依照被調函數保存的返回地址將控制轉移到調用函數.

變量和地址等數據都是保存在系統所分配的棧中的.為了保證遞歸函數正確執行,系統需設立一個”遞歸工作棧”,作為