DS04線性結(jié)構(gòu)b陳越主編數(shù)據(jù)結(jié)構(gòu)

第3章線性結(jié)構(gòu)§3.3堆棧[例3.4]對于算術(shù)表達式來說，其基本規(guī)則是：先乘除，后加減；先括號內(nèi)，再括號外；相同優(yōu)先級情況下從左到右。比如，5+6/2-3*4就是一個算術(shù)表達式，它的正確理解應(yīng)該是：

5+6/2-3*4=5+3-3*4

=8-3*4=8-12=-4。可以看到這類表達式主要由兩類對象構(gòu)成的，即運算數(shù)（如2、3、4等）和運算符號（如+、-、*、/等）。不同運算符號優(yōu)先級是不一樣的，而且運算符號均位于兩個運算數(shù)中間。堆棧要實現(xiàn)表達式求值，首先需要正確理解一個表達式，主要是運算的先后順序。計算機編譯程序是如何自動地理解表達式的？1/23〖例〗62342=?8對象:6(運算數(shù))6對象:2(運算數(shù))2對象:(運算符)26=3toptop3top對象:3(運算數(shù))3top對象:(運算符)3toptop3=00top對象:4(運算數(shù))top4對象:2(運算數(shù))top2對象:(運算符)top2top4=88top對象:(運算符)top8top0=88topPop:8topT(N)=O(N)。不需要知道運算符的優(yōu)先規(guī)則。第3章線性結(jié)構(gòu)§3.3堆棧中綴表達式：運算符號位于兩個運算數(shù)之間。如，a

bcde后綴表達式：運算符號位于兩個運算數(shù)之后。如，

abc

de

后綴表達式toptoptop2/23第3章線性結(jié)構(gòu)§3.3堆棧

把數(shù)據(jù)插入稱為壓入棧（Push）；

而數(shù)據(jù)刪除可看作從堆棧中取出數(shù)據(jù)，叫做彈出棧（Pop）。

最后入棧的數(shù)據(jù)將被最先彈出，所以堆棧也被稱為“后入先出”表（LastInFirstOut，簡稱LIFO）。堆棧的定義“堆棧（Stack）”可以認為是具有一定操作約束的線性表，插入和刪除操作都作用在一個稱為棧頂(Top)的端點位置。類型名稱:堆棧（Stack）數(shù)據(jù)對象集：一個有0個或多個元素的有窮線性表。操作集：對于一個具體的長度為正整數(shù)MaxSize的堆棧SStack，記堆棧中的任一元素item

ElementType。1、StackCreateStack(int

MaxSize)：生成空堆棧，其最大長度為MaxSize；2、int

IsFull(StackS,int

MaxSize)：判斷堆棧S是否已滿。若S中元素個數(shù)等于MaxSize時返回1(TRUE)；否則返回0(FALSE)；3、voidPush(StackS,ElementTypeitem)：將元素item壓入堆棧。若堆棧已滿，返回堆棧為滿信息；否則將數(shù)據(jù)元素item插入到堆棧S棧頂處；4、int

IsEmpty(StackS)：判斷堆棧S是否為空，若是返回1(TRUE)；否則返回0(FALSE)；5、ElementTypePop(StackS)：刪除并返回棧頂元素。若堆棧為空，返回堆棧為空信息；否則將棧頂數(shù)據(jù)元素從堆棧中刪除并返回。6、

ElementType

Top(StackS)：……3/23第3章線性結(jié)構(gòu)§3.3堆棧TopTopTopTopAABABCABCDTopTopTopTopDABCCBAABACreatStack();Push(S,A);Push(S,B);Push(S,C);x=Pop(S);x=Pop(S);x=Pop(S);IsEmpty(S)12345665654/23Push和Pop可以任意穿插交替進行；求后綴表達式562/+34*-時：

Push和Pop的序列是：

Push(S,5);Push(S,6);Push(S,2);/*S:562*/x=Pop(S);/*x=2*/y=Pop(S);/*y=6*/Push(S,y/x);/*y/x=3,S:53*/x=Pop(S);/*x=3*/y=Pop(S);/*y=5*/Push(S,x+y);/*y+x=8,S:8*/Push(S,3);Push(S,4);/*S:834*/x=Pop(S);/*x=4*/y=Pop(S);/*y=3*/Push(S,x*y);/*y*x=12,S:812*/x=Pop(S);/*x=12*/y=Pop(S);/*y=8*/Push(S,y-x);/*S:-4*/x=Pop(S);/*x=-4*/第3章線性結(jié)構(gòu)§3.3堆棧5/23第3章線性結(jié)構(gòu)§3.3堆棧【分析】1只有一個字符出入棧時，顯然只有一種可能，即A入棧也只有A出棧。有兩個字符AB出入棧時，如果進棧順序為AB，那么出棧的系列AB、BA都有可能：即可以A進棧、A出棧、B進棧、B出棧，產(chǎn)生輸出序列AB；也可以A進棧、B進棧、B出棧、A出棧，產(chǎn)生輸出序列BA。

這兩個可能的序列也是正好是兩個字符的全排列。[例3.5]如果將ABCD四個字符按順序壓入堆棧，是不是ABCD的所有排列都可能是出棧的序列？可以產(chǎn)生CABD這樣的序列嗎？如果有三個字符ABC出入棧時，全排列有3！=6種可能。其中的CAB是沒法生成的。因為先輸出C，需要C進棧再出棧，而要求按照ABC這樣的順序進棧，所以C出棧時AB必然還在棧里，而且A還壓在B下面。其它5種排列都可以生成。如果有四個字符ABCD出入棧時，排列有4!=24種可能。不是所有排列都有可能是出棧的序列，象CABD這樣的序列是產(chǎn)生不了的。四個字符出棧的所有可能序列有幾種？（14種）6/23第3章線性結(jié)構(gòu)棧的順序存儲結(jié)構(gòu)通常由一個一維數(shù)組和一個記錄棧頂元素位置的變量組成。#define

MaxSize<儲存數(shù)據(jù)元素的最大個數(shù)>typedef

struct{

ElementType

Data[MaxSize];

intTop;}Stack;§3.3堆棧的實現(xiàn)1．棧的順序存儲實現(xiàn)voidPush(Stack*PtrS,ElementTypeitem){

if(PtrS->Top==MaxSize-1){

printf(“堆棧滿”);return;}else{

PtrS->Data[++(PtrS->Top)]=item;

return;}}TopAB(1)入棧PtrS7/23第3章線性結(jié)構(gòu)§3.3堆棧的實現(xiàn)ElementTypePop(Stack*PtrS){

if(PtrS->Top==-1){

printf(“堆?？铡?;

returnERROR;/*ERROR是ElementType的特殊值，標志錯誤*/}else

return(PtrS->Data[(PtrS->Top)--]);}TopAB(2)出棧PtrS8/23[例３.６]請用一個數(shù)組實現(xiàn)兩個堆棧，要求最大地利用數(shù)組空間，使數(shù)組只要有空間入棧操作就可以成功。寫出相應(yīng)的入棧和出棧操作函數(shù)?！痉治觥恳环N比較聰明的方法是使這兩個棧分別從數(shù)組的兩頭開始向中間生長；當兩個棧的棧頂指針相遇時，表示兩個棧都滿了。此時，最大化地利用了數(shù)組空間。第3章線性結(jié)構(gòu)§3.3堆棧#defineMaxSize<存儲數(shù)據(jù)元素的最大個數(shù)>struct

DStack{

ElementType

Data[MaxSize];

intTop1;/*堆棧１的棧頂指針*/

intTop2;/*堆棧２的棧頂指針*/}S;S.Top1=-1;S.Top2=MaxSize;9/23第3章線性結(jié)構(gòu)§3.3堆棧voidPush(struct

DStack*PtrS,ElementTypeitem,intTag){/*Tag作為區(qū)分兩個堆棧的標志，取值為1和2*/

if(PtrS->Top2–PtrS->Top1==1){/*堆棧滿*/printf(“堆棧滿”);return;}

if(Tag==1)/*對第一個堆棧操作*/

PtrS->Data[++(PtrS->Top1)]=item;

else

/*對第二個堆棧操作*/

PtrS->Data[--(PtrS->Top2)]=item;}ElementTypePop(struct

DStack*PtrS,intTag){/*Tag作為區(qū)分兩個堆棧的標志，取值為1和2*/

if(Tag==1){/*對第一個堆棧操作*/

if(PtrS->Top1==-1){/*堆棧1空*/

printf(“堆棧1空”);returnNULL;}else

return

PtrS->Data[(PtrS->Top1)--];}else{/*對第二個堆棧操作*/

if(PtrS->Top2==MaxSize){/*堆棧2空*/

printf(“堆棧2空”);returnNULL;}else

return

PtrS->Data[(PtrS->Top2)++];}}10/23第3章線性結(jié)構(gòu)棧的鏈式存儲結(jié)構(gòu)實際上就是一個單鏈表，叫做鏈棧。插入和刪除操作只能在鏈棧的棧頂進行；棧頂指針Top就是鏈表的頭指針?！?.3堆棧的實現(xiàn)2．堆棧的鏈式存儲實現(xiàn)LinkStack*CreateStack(){/*構(gòu)建一個堆棧的頭結(jié)點，返回指針*/

LinkStack*S;S=malloc(sizeof(structNode));S->Next=NULL;

returnS;}int

IsEmpty(LinkStack*S){/*判斷堆棧S是否為空，若為空函數(shù)返回整數(shù)1，否則返回0*/

return(S->Next==NULL);}(1)堆棧初始化（建立空棧）(2)判斷堆棧S是否為空typedef

struct

Node{

ElementTypeData;

structNode*Next;}LinkStack;LinkStack*Top;S11/23第3章線性結(jié)構(gòu)§3.3堆棧的實現(xiàn)voidPush(ElementTypeitem,LinkStack*S){/*將元素item壓入堆棧S*/structNode*TmpCell;TmpCell=malloc(sizeof(structNode));TmpCell->Element=item;TmpCell->Next=S->Next;S->Next=TmpCell;}ElementTypePop(LinkStack*S){/*刪除并返回堆棧S的棧頂元素*/

structNode*FirstCell;ElementType

TopElem;if(IsEmpty(S)){printf(“堆?？铡?;returnNULL;}else{FirstCell=S->Next;S->Next=FirstCell->Next;TopElem=FirstCell->Element;free(FirstCell);return

TopElem;}}12/23堆棧應(yīng)用：表達式求值第3章線性結(jié)構(gòu)§3.3堆棧應(yīng)用堆棧實現(xiàn)后綴表達式求值的基本過程：.從左到右讀入后綴表達式的各項（運算符或運算數(shù)）；.根據(jù)讀入的對象（運算符或運算數(shù)）判斷執(zhí)行操作；.操作分下列3種情況：當讀入的是一個運算數(shù)時，把它被壓入棧中；當讀入的是一個運算符時，就從堆棧中彈出適當數(shù)量的運算數(shù)，對該運算進行計算，計算結(jié)果再壓回到棧中；處理完整個后綴表達式之后，堆棧頂上的元素就是表達式的結(jié)果值。對象序列的后綴表達式結(jié)果值字符序列的后綴表達式求值利用堆棧對象分割GetOp1.21.3+24.2*-1.2

1.3+2

4.2*--5.913/23中綴表達式求值第3章線性結(jié)構(gòu)§3.3堆棧對象序列的中綴表達式字符序列的中綴表達式對象分割GetOp(1.2+1.3–2)*4.2(1.2+1.3–2)*4.22.1對象序列的后綴表達式結(jié)果值求值利用堆棧1.2

1.3+2-4.2*對象分割GetOp求值利用堆棧利用堆棧轉(zhuǎn)換利用堆棧轉(zhuǎn)換14/23中綴表達式轉(zhuǎn)換為后綴表達式第3章線性結(jié)構(gòu)§3.3堆棧從頭到尾讀取中綴表達式的每個對象，對不同對象按不同的情況處理。對象分下列6種情況：①如果遇到空格則認為是分隔符，不需處理；②若遇到運算數(shù)，則直接輸出；③若是左括號，則將其壓入堆棧中；④若遇到的是右括號，表明括號內(nèi)的中綴表達式已經(jīng)掃描完畢，將棧頂?shù)倪\算符彈出并輸出，直到遇到左括號（左括號也出棧，但不輸出）；⑤若遇到的是運算符，若該運算符的優(yōu)先級大于棧頂運算符的優(yōu)先級時，則把它壓棧；若該運算符的優(yōu)先級小于等于棧頂運算符時，將棧頂運算符彈出并輸出，再比較新的棧頂運算符，按同樣處理方法，直到該運算符大于棧頂運算符優(yōu)先級為止，然后將該運算符壓棧；⑥若中綴表達式中的各對象處理完畢，則把堆棧中存留的運算符一并輸出。15/23第3章線性結(jié)構(gòu)§3.3堆棧(?〖例〗a

(

b

c

)

d

=?

abc

d

top輸出:

輸入對象:a(操作數(shù))a輸入對象:(乘法)top輸入對象:((左括號)

(?top(輸入對象:b(操作數(shù))b輸入對象:(加法)NO?!top+輸入對象:c(操作數(shù))c輸入對象:)(右括號)toptop輸入對象:(除法)

?toptop輸入對象:d(操作數(shù))dtopT(N)=O(N)16/23中綴轉(zhuǎn)換為后綴示例：（

2*（9+6/3-5）+4）第3章線性結(jié)構(gòu)§3.3堆棧步驟待處理表達式堆棧狀態(tài)（底頂）輸出狀態(tài)12*（9+6/3-5）+42*（9+6/3-5）+423（9+6/3-5）+4*249+6/3-5）+4*（25+6/3-5）+4*（2966/3-5）+4*（

+297/3-5）+4*（

+29683-5）+4*（

+/2969-5）+4*（

+/2963105）+4*（

-2963/+11）+4*（

-2963/+512+4*2963/+5-134+2963/+5-*14+2963/+5-*4152963/+5-*4+17/23第3章線性結(jié)構(gòu)把數(shù)據(jù)插入稱為入隊列（AddQ）；

而數(shù)據(jù)刪除可看作從隊列中取出數(shù)據(jù)，叫做出隊列（DeleteQ）。

最先入隊列的數(shù)據(jù)將被最先彈出，即先來先服務(wù);所以隊列也被稱為“先進先出”表（FistInFirstOut，簡稱FIFO）。隊列的定義“隊列(Queue)”是具有一定操作約束的線性表，插入和刪除操作有一定要求：只能在一端插入，而在另一端刪除?！?.4隊列類型名稱：隊列(Queue)數(shù)據(jù)對象集：一個有0個或多個元素的有窮線性表。操作集：對于一個長度為正整數(shù)MaxSize的隊列QQueue，記隊列中的任一元素item

ElementType。1、QueueCreatQueue(int

MaxSize)：生成長度為MaxSize的空隊列。2、int

IsFullQ(QueueQ,int

MaxSize)：判斷隊列Q是否已滿，若是返回1(TRUE)；否則返回0(FALSE)。3、voidAddQ(QueueQ,ElementTypeitem)：若隊列已經(jīng)滿了，返回已滿信息；否則將數(shù)據(jù)元素item插入到隊列Q中去。4、int

IsEmptyQ(QueueQ)：判斷隊列Q是否為空，若是返回1(TRUE)；否則返回0(FALSE)。5、ElementType

DeleteQ(QueueQ)：若隊列為空信息，返回隊列空信息；否則將隊頭數(shù)據(jù)元素從隊列中刪除并返回。6、

ElementType

FrontQ(QueueQ)：……18/23第3章線性結(jié)構(gòu)隊列的順序存儲結(jié)構(gòu)通常由一個一維數(shù)組和一個記錄隊列頭元素位置的變量front以及一個記錄隊列尾元素位置的變量rear組成。#define

MaxSize<儲存數(shù)據(jù)元素的最大個數(shù)>typedef

struct{

ElementTypeData[MaxSize];

intrear;

intfront;}Queue;1．隊列的順序存儲實現(xiàn)§3.4隊列的實現(xiàn)Job3〖例〗

一個工作隊列AddQJob1AddQJob2AddQJob3DeleteQJob1AddQJob4AddQJob5AddQJob6DeleteQJob2AddQJob7AddQJob8Job1Job2RearJob4Job5Job6FrontRearJob70123456RearRearFrontRear19/23[0][1][2][3][4][5]AddQJob1AddQJob2AddQJob3DeleteQJob1AddQJob4AddQJob5AddQJob6AddQJob7Job1Job2Job3Job4Job5Job6隊列滿！順環(huán)隊列:RearRearFrontRearFrontRearRearRear注:

如果數(shù)據(jù)結(jié)構(gòu)中增加一個

Size

域，用來區(qū)分隊列“空”和“滿”的話，

可以“節(jié)省”一個數(shù)據(jù)元素的存儲單元。但是會帶來算法描述的復(fù)雜性。Rear第3章線性結(jié)構(gòu)§3.4隊列的實現(xiàn)20/23第3章線性結(jié)構(gòu)void

AddQ(Queue*PtrQ,ElementTypeitem){if((PtrQ->rear+1)%MaxSize==PtrQ->front){

printf(“隊列滿”);

return;}

PtrQ->rear=(PtrQ->rear+1)%MaxSize;

PtrQ->Data[PtrQ->rear]=item;}§3.4隊列ElementType

DeleteQ(Queue*PtrQ){

if(PtrQ->front==PtrQ->rear){

printf(“隊列空”);

returnERROR;}else{

PtrQ->front=(PtrQ->front+1)%MaxSize;

return

PtrQ->Data[PtrQ->front];}}(1)入隊列(2)