數(shù)據(jù)結(jié)構(gòu)-第三章

第3章限定性線性表——棧和隊列3.1棧3.2隊列返回主目錄.3.1棧3.1.1棧的定義3.1.2棧的表示和實現(xiàn)3.1.3棧的應用舉例3.1.4棧與遞歸的實現(xiàn)返回主目錄.棧的定義：

棧作為一種限定性線性表，是將線性表的插入和刪除運算限制為僅在表的一端進行。通常將表中允許進行插入、刪除操作的一端稱為棧頂

(Top)，表的另一端被稱為棧底

(Bottom)。當棧中沒有元素時稱為空棧。棧的插入操作被形象地稱為進?；蛉霔?，刪除操作稱為出?；蛲藯?。返回主目錄.根據(jù)棧定義，每次進棧的元素都被放在原棧頂元素之上而成為新的棧頂，而每次出棧的總是當前棧中“最新”的元素，即最后進棧的元素。因此，棧又稱為后進先出的線性表。簡稱為LIFO表。如下圖所示：

進棧、出棧圖例進棧出棧進棧出棧棧頂棧底ana2a1返回主目錄.棧的抽象數(shù)據(jù)類型定義關(guān)系：棧中數(shù)據(jù)元素之間是線性關(guān)系數(shù)據(jù)元素：可以是任意類型的數(shù)據(jù)，但必須屬于同一個數(shù)據(jù)對象?；静僮鳎篒nitStack（S）2.ClearStack（S）3.IsEmpty（S）

4.IsFull（S）

5.Push（S，x）6.Pop（S，x）7.GetTop（S，x）返回主目錄.3.1.2棧的表示和實現(xiàn)棧在計算機中主要有兩種基本的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。順序存儲的棧為順序棧；鏈式存儲的棧為鏈棧。返回主目錄.1.順序棧順序棧是用順序存儲結(jié)構(gòu)實現(xiàn)的棧，即利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時由于棧的操作的特殊性，還必須附設一個位置指針top（棧頂指針）來動態(tài)地指示棧頂元素在順序棧中的位置。通常以top=-1表示空棧。返回主目錄.用C語言定義棧的順序存儲結(jié)構(gòu)#defineTRUE1#defineFALSE0#defineStack_Size50

typedefstruct{StackElementTypeelem[Stack_Size];/*用來存放棧中元素的一維數(shù)組*/inttop;/*用來存放棧頂元素的下標*/}SeqStack;返回主目錄.順序棧中的進棧和出棧圖例AEDCBABAtop

top

top

top返回主目錄.順序棧基本操作的實現(xiàn)1）初始化voidInitStack(SeqStack*S){/*構(gòu)造一個空棧S*/S->top=-1;}返回主目錄.2）判?？読ntIsEmpty(SeqStack*S)/*判棧S為空棧時返回值為真，反之為假*/{return(S->top==-1?TRUE:FALSE);}返回主目錄.3）判棧滿intIsFull(SeqStack*S)/*判棧S為滿時返回真，否則返回假*/{return(S->top==Stack_Size?TRUE:FALSE);}返回主目錄.4）進棧intPush(SeqStack*S,StackElementTypex){if(S->top==Stack_Size)return(FALSE);/*棧已滿*/S->top++;S->elem[S->top]=x;return(TRUE);}返回主目錄.5）出棧intPop(SeqStack*S,StackElementType*x){if(S->top==-1)/*棧為空*/return(FALSE);else{*x=S->elem[S->top];S->top--;/*修改棧頂指針*/return(TRUE);}}返回主目錄.6）取棧頂元素intGetTop（SeqStackS,StackElementType*x）{/*將棧S的棧頂元素彈出，放到x所指的存儲空間中，但棧頂指針保持不變*/ if(S->top==-1)/*棧為空*/return(FALSE); else{*x=S->elem[S->top];return(TRUE);} }返回主目錄.兩棧共享技術(shù)：主要利用了?！皸５孜恢貌蛔?，而棧頂位置動態(tài)變化”的特性。首先為兩個棧申請一個共享的一維數(shù)組空間S[M]，將兩個棧的棧底分別放在一維數(shù)組的兩端，分別是0，M-1。共享棧的空間示意為：top[0]和top[1]分別為兩個棧頂指示器。top[0]top[1]Stack：0M-1返回主目錄.兩棧共享的數(shù)據(jù)結(jié)構(gòu)定義#defineM100typedefstruct{StackElementTypeStack[M];StackElementTypetop[2];/*top[0]和top[1]分別為兩個棧頂指示器*/}DqStack;返回主目錄.1）兩棧共享的初始化操作算法voidInitStack(DqStack*S){ S->top[0]=-1; S->top[1]=M;}返回主目錄.2）兩棧共享的進棧操作算法intPush(DqStack*S,StackElementTypex,inti){ if(S->top[0]+1==S->top[1])/*棧已滿*/return(FALSE); switch(i) {case0:S->top[0]++;S->Stack[S->top[0]]=x;break; case1:S->top[1]--;S->Stack[S->top[1]]=x;break; default:return(FALSE) } return(TRUE);}返回主目錄.3）兩棧共享的出棧操作算法intPop(DqStack*S,StackElementType*x,inti){switch(i){case0:if(S->top[0]==-1)return(FALSE);*x=S->Stack[S->top[0]];S->top[0]--;break;case1:if(S->top[1]==M)return(FALSE); *x=S->Stack[S->top[1]];S->top[1]++;break; default:return(FALSE); } return(TRUE);}返回主目錄.2.鏈棧鏈棧是采用鏈表作為存儲結(jié)構(gòu)實現(xiàn)的棧。為便于操作，采用帶頭結(jié)點的單鏈表實現(xiàn)棧。因為棧的插入和刪除操作僅限制在表頭位置進行，所以鏈表的表頭指針就作為棧頂指針。鏈棧的示意圖為：anan-1…a1∧toptop為棧頂指針，始終指向當前棧頂元素前面的頭結(jié)點。若top->next=NULL，則代表空棧。注意：鏈棧在使用完畢時，應該釋放其空間。返回主目錄.用C語言定義的鏈棧結(jié)構(gòu)typedefstructnode{StackElementTypedata;structnode*next;}LinkStackNode;typedefLinkStackNode*LinkStack;返回主目錄.鏈棧的進棧操作intPush(LinkStacktop,StackElementTypex)/*將數(shù)據(jù)元素x壓入棧top中*/{LinkStackNode*temp;temp=(LinkStackNode*)malloc(sizeof(LinkStackNode));if(temp==NULL)return(FALSE);/*申請空間失敗*/ temp->data=x;temp->next=top->next; top->next=temp;/*修改當前棧頂指針*/return(TRUE);}返回主目錄.鏈棧的出棧操作intPop(LinkStacktop,StackElementType*x){/*將棧top的棧頂元素彈出，放到x所指的存儲空間中*/LinkStackNode*temp;temp=top->next;if(temp==NULL)/*棧為空*/ return(FALSE);top->next=temp->next;*x=temp->data;free(temp);/*釋放存儲空間*/return(TRUE);}返回主目錄.3.1.3棧的應用舉例數(shù)制轉(zhuǎn)換voidConversion(intN)/*對于任意的一個非負十進制數(shù)N，打印出與其等值的二進制數(shù)*/{StackS;intx;/*S為順序棧或鏈棧*/

InitStack(&S); while(N>0) {x=N%2;Push(&S,x);N=N/2;} while(！IsEmpty(S)) {Pop(&S,&x);printf(“%d”,x);} }返回主目錄.2.

括號匹配問題思想：在檢驗算法中設置一個棧，若讀入的是左括號，則直接入棧，等待相匹配的同類右括號；若讀入的是右括號，且與當前棧頂?shù)淖罄ㄌ柾愋停瑒t二者匹配，將棧頂?shù)淖罄ㄌ柍鰲＃駝t屬于不合法的情況。另外，如果輸入序列已讀盡，而棧中仍有等待匹配的左括號，或者讀入了一個右括號，而棧中已無等待匹配的左括號，均屬不合法的情況。當輸入序列和棧同時變?yōu)榭諘r，說明所有括號完全匹配。返回主目錄.算法:voidBracketMatch(char*str){StackS;inti;charch;InitStack(&S);For(i=0;str[i]!='\0';i++){switch(str[i]){case'(':case'[':case'{':Push(&S,str[i]);break;case')':case']':case'}':if(IsEmpty(S)) {printf("\n右括號多余!");return;}else{GetTop(&S,&ch);if(Match(ch,str[i]))Pop(&S,&ch);else{printf("\n對應的左右括號不同類!");return;}}}/*switch*/}/*for*/if(IsEmpty(S)) printf("\n括號匹配!");else printf("\n左括號多余!");}返回主目錄.3.表達式求值1)無括號算術(shù)表達式求值表達式運算及運算符優(yōu)先級3+4*5#+-*/**①0123②置空棧OVS、OPTR進OVS讀字符W退OVS頂、次頂，OPTR頂將T(i)=>OVS新頂進OPTR棧W是操作符N結(jié)束NYNYYYW=‘#’’OPTRZ?？誝W優(yōu)先級≤OPTR棧頂優(yōu)先級N無括號算術(shù)表達式的處理過程如右圖返回主目錄.2)算術(shù)表達式處理規(guī)則規(guī)定優(yōu)先級表；(2)設置兩個棧：OVS(運算數(shù)棧)和OPTR(運算符棧)；(3)自左向右掃描，遇操作符則與OPTR棧頂優(yōu)先級比較：當前操作符>OPTR棧頂則進OPTR棧；當前操作符≤OPTR棧頂，OVS棧頂、次頂和OPTR棧頂，退棧形成運算T（i），T（i）進OVS棧。返回主目錄.例：實現(xiàn)A/B↑C+D*E#的運算過程時棧區(qū)變化情況返回主目錄.3)帶括號算術(shù)表達式實現(xiàn)算符優(yōu)先算法時需要使用兩個工作棧：一個稱作運算符棧operator；另一個稱作操作數(shù)棧operand。算法的基本過程如下：A.初始化操作數(shù)棧operand