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

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

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

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

bcde后綴表達(dá)式：運(yùn)算符號(hào)位于兩個(gè)運(yùn)算數(shù)之后。如，

abc

de

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

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

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

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

ElementType。1、StackCreateStack(int

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

IsFull(StackS,int

MaxSize)：判斷堆棧S是否已滿。若S中元素個(gè)數(shù)等于MaxSize時(shí)返回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可以任意穿插交替進(jìn)行；求后綴表達(dá)式562/+34*-時(shí)：

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只有一個(gè)字符出入棧時(shí)，顯然只有一種可能，即A入棧也只有A出棧。有兩個(gè)字符AB出入棧時(shí)，如果進(jìn)棧順序?yàn)锳B，那么出棧的系列AB、BA都有可能：即可以A進(jìn)棧、A出棧、B進(jìn)棧、B出棧，產(chǎn)生輸出序列AB；也可以A進(jìn)棧、B進(jìn)棧、B出棧、A出棧，產(chǎn)生輸出序列BA。

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

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

struct{

ElementType

Data[MaxSize];

intTop;}Stack;§3.3堆棧的實(shí)現(xiàn)1．棧的順序存儲(chǔ)實(shí)現(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堆棧的實(shí)現(xiàn)ElementTypePop(Stack*PtrS){

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

printf(“堆?？铡?;

returnERROR;/*ERROR是ElementType的特殊值，標(biāo)志錯(cuò)誤*/}else

return(PtrS->Data[(PtrS->Top)--]);}TopAB(2)出棧PtrS8/23[例３.６]請(qǐng)用一個(gè)數(shù)組實(shí)現(xiàn)兩個(gè)堆棧，要求最大地利用數(shù)組空間，使數(shù)組只要有空間入棧操作就可以成功。寫出相應(yīng)的入棧和出棧操作函數(shù)。【分析】一種比較聰明的方法是使這兩個(gè)棧分別從數(shù)組的兩頭開始向中間生長(zhǎng)；當(dāng)兩個(gè)棧的棧頂指針相遇時(shí)，表示兩個(gè)棧都滿了。此時(shí)，最大化地利用了數(shù)組空間。第3章線性結(jié)構(gòu)§3.3堆棧#defineMaxSize<存儲(chǔ)數(shù)據(jù)元素的最大個(gè)數(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ū)分兩個(gè)堆棧的標(biāo)志，取值為1和2*/

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

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

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

else

/*對(duì)第二個(gè)堆棧操作*/

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

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

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

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

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

return

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

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

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

return

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

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

1.3+2

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

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

(

b

c

)

d

=?

abc

d

top輸出:

輸入對(duì)象:a(操作數(shù))a輸入對(duì)象:(乘法)top輸入對(duì)象:((左括號(hào))

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

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

2*（9+6/3-5）+4）第3章線性結(jié)構(gòu)§3.3堆棧步驟待處理表達(dá)式堆棧狀態(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ù)插入稱為入隊(duì)列（AddQ）；

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

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

ElementType。1、QueueCreatQueue(int

MaxSize)：生成長(zhǎng)度為MaxSize的空隊(duì)列。2、int

IsFullQ(QueueQ,int

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

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

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

ElementType

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

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

struct{

ElementTypeData[MaxSize];

intrear;

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

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

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

Size

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

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

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

printf(“隊(duì)列滿”);

return;}

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

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

DeleteQ(Queue*PtrQ){

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

printf(“隊(duì)列空”);

returnERROR;}else{

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

return

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