《數(shù)據(jù)結(jié)構(gòu)與算法》課件-第3章

第三章棧和隊(duì)列§3.1?！瞫tack〕一、棧的定義和運(yùn)算定義：限定僅在表尾進(jìn)行插入或刪除操作的線性表，表尾—棧頂，表頭—棧底，不含元素的空表稱空棧。棧s=(a1,a2,……,an)入棧出棧anan-1a1…棧頂棧底后進(jìn)先出3.棧的表示和實(shí)現(xiàn)1〕順序?！獥５捻樞虼鎯?chǔ)結(jié)構(gòu)2〕鏈棧——棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1〕順序?！獥５捻樞虼鎯?chǔ)結(jié)構(gòu)限定在表尾進(jìn)行插入和刪除操作的順序表類型定義：

typedef

struct

{ElemType

data[MAXSIZE];

inttop;}SeqStack;0123……n-1maxsize-1a1a2a3a4andatatop根本操作的實(shí)現(xiàn)

棧的初始化操作SeqStack

SeqStackInit(){SeqStacks;s.top=-1;returns;}

判斷棧是否為空

int

SeqStackEmpty(SeqStacks)

{if(s.top==-1)return1;

elsereturn0;

}取棧頂元素

ElemType

SeqStackGetTop(SeqStacks){ if(s.top!=-1)returns.data[s.top--];

}注意:(1)取棧頂元素的條件(非空)(2)如何取棧頂元素(top指針的移動(dòng))

stacksize進(jìn)棧操作棧滿條件：s.top==MAXSIZE-1

進(jìn)棧操作：s.data[++s->top]=x;當(dāng)棧滿時(shí)再做進(jìn)棧運(yùn)算必定產(chǎn)生空間溢出，簡(jiǎn)稱“上溢”;算法描述如下：voidSeqStackPush(SeqStacks,ElemTypex){if(s.top==MAXSIZE-1) {printf(“overflow!”);exit(0);}s.top++; s.data[s.top]=x;}退棧操作例如棧空條件：此時(shí)不能出棧

退棧操作：x=s.data[s.top--]；

當(dāng)棧空時(shí)再做退棧運(yùn)算也將產(chǎn)生溢出，簡(jiǎn)稱“下溢”。ElemTypeSeqStackPop(SeqStacks){ if(s.top==-1〕 ｛printf(“empty!”);exit(0);} x=s->data[s->top]; s.top--; returnx;}不帶頭結(jié)點(diǎn)的單鏈表，其插入和刪除操作僅限制在表頭位置上進(jìn)行。鏈表的頭指針即棧頂指針。鏈棧示意圖如下：s2〕鏈?！獥５逆?zhǔn)酱鎯?chǔ)結(jié)構(gòu)棧空條件：s=NULLtop為頭指針typedefstructStackNode{ ElemTypedata; strcutStackNode*next;}StackNode,*LinkStack;初始化LinkStackLinkStackInit(){top=NULL;returntop;}思考一下判空怎樣實(shí)現(xiàn)？

入棧voidLinkStackPush(LinkStacktop,ElemTypex){s=(StackNode*)malloc(sizeof(StackNode));s->data=x;s->next=top;top=s;returntop;}出棧ElemTypeLinkStackPop(LinkStacktop){if(top!=NULL){x=top->data;p=top;top=top->next;free(p);returnx;}例2：將單鏈表逆向存儲(chǔ)，即a1變?yōu)閍n,an變?yōu)閍1分析：具體操作過(guò)程如下：判斷棧L1是否為空;L1中的元素出棧；將出棧的元素入棧到L2中。③

ai-1aia1…puaiai＋1an…L②

④

①

uvoidreverse(node*L){node*p=NULL;

while(L!=NULL)

{node*u=L;

L=L->next;

u->next=p;

p=u;

}

L=p;

}

3.表達(dá)式求值算符間的優(yōu)先級(jí)關(guān)系

運(yùn)算符號(hào)#（+-*/)^優(yōu)先級(jí)別-10112123為實(shí)現(xiàn)算符優(yōu)先算法，可使用兩個(gè)工作棧：

number棧：存數(shù)據(jù)或運(yùn)算結(jié)果

operation棧：存運(yùn)算符例：12+5*〔3+2〕*6/2-4掃描基本符號(hào)是否操作數(shù)？Y棧頂運(yùn)算符低于當(dāng)前運(yùn)算符？操作數(shù)入棧NYN運(yùn)算符入棧取出S棧頂運(yùn)算符和O棧頂?shù)膬蓚€(gè)操作數(shù)運(yùn)算，結(jié)果入棧O定義運(yùn)算符棧S和操作數(shù)棧O棧S為空？Y結(jié)束Y算法思想：1.初態(tài)：置number棧為空；將“#”作為operation棧的棧底元素2.依次讀入表達(dá)式中的每個(gè)字符1〕假設(shè)是操作數(shù)，那么進(jìn)入number棧；2〕假設(shè)是運(yùn)算符，那么與operation棧的棧頂運(yùn)算符進(jìn)行優(yōu)先權(quán)〔級(jí)〕的比較：假設(shè)讀入運(yùn)算符的優(yōu)先權(quán)高，那么進(jìn)入operation棧；假設(shè)讀入運(yùn)算符的優(yōu)先權(quán)低，那么operation退?！餐顺鲈械臈ｍ斣亍?，number棧退出兩個(gè)元素先退出b，再退出a〕，中間結(jié)果再進(jìn)入number棧；假設(shè)讀入“〕”，operation棧的原有棧的棧頂元素假設(shè)為“〔”，那么operation退出“〔”；假設(shè)讀入“#”，operation棧棧頂元素也為“#”，那么operation棧退出“#”，結(jié)束。數(shù)制轉(zhuǎn)換1357÷8所得的余數(shù)1357÷8所得的商按此次序連接各位余數(shù)便得到最后的轉(zhuǎn)換結(jié)果為25150

288881357

51691

21

52

十進(jìn)制N和其它進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的根本問(wèn)題應(yīng)用：1、將N除以d,取其商和余數(shù)2、判斷商是否為0；假設(shè)商不為零，那么將商賦值給N,并轉(zhuǎn)向1;假設(shè)商為零,那么轉(zhuǎn)換結(jié)束.作業(yè)2：能否借助一個(gè)空棧tmp,將一個(gè)非空棧s中的值等于value的元素全部刪除？如能，寫出算法作業(yè)3：利用棧作為輔助的存儲(chǔ)系統(tǒng)，實(shí)現(xiàn)回文的判斷?！岔樞驐：玩湕６伎梢浴乘惴枋觯簐oidD_to_O(intN){LinkStackstacks;intmod;

LinkStackInit(s);while(N!=0){mod=N%8;LinkStackPush(s,mod);

N=N/8;

}while(!(LinkStackEmpty(s)){x=LinkStackPop(s); cout<<x;

}}§3.3隊(duì)列1.定義2.順序隊(duì)列----隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)3.鏈隊(duì)列----隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1.定義限定在表的一端進(jìn)行刪除，在表的另一端進(jìn)行插入操作的線性表。允許刪除的一端叫做隊(duì)頭(front)，允許插入的一端叫做隊(duì)尾(rear)。特性：FIFO(FirstInFirstOut)圖示如下：a1

a2

a3……an出隊(duì)入隊(duì)隊(duì)頭（刪除元素）隊(duì)尾（插入元素）2.順序隊(duì)列#defineMAXSIZE100typedefstruct{ElemTypedata[MAXSIZE];intfront,rear;}SeQueue;隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)定義：0123maxsize-1a1a2……andatafrontrear循環(huán)隊(duì)列順序隊(duì)列會(huì)產(chǎn)生“假溢出”將數(shù)組元素data[0]看做是data[MAXSIZE-1]的下一個(gè)儲(chǔ)存位置，就形成了循環(huán)隊(duì)列frontrear210maxsize-1循環(huán)隊(duì)列a2a3123a1465frontrear初始狀態(tài)123465frontrear隊(duì)列為空a4a2a3123a1465frontreara5a6隊(duì)列為滿空：front=rear滿：front=rear思考：如何分清何時(shí)為滿何時(shí)為空？front循環(huán)隊(duì)列---運(yùn)算〔1〕初始化隊(duì)列：

SeQueue

SeQueueInit() {SeQueueQ;

Q.front=0;Q.rear=0; returnQ;}判斷隊(duì)列是否為空：

int

SeQueueEmpty(SeQueueQ) {if(Q.front==Q.rear)return1; elsereturn0;}循環(huán)隊(duì)列---運(yùn)算〔2〕判斷隊(duì)列是否為滿：

BOOLSeQueueFull(SeQueueQ) {if((1+Q.rear)%maxsize==Q.front)return1; elsereturn0;}入隊(duì)

voidSeQueueIn(SeQueue

Q,ElemTypex) {if(SeQueueFull(Q))error(“溢出”); else{Q.rear=(1+Q.rear)%maxsize;

Q.data［Q.rear］=x；}}出隊(duì)

ElemType

SeQueueOut(SeQueueQ) {if(SeQueueEmpty(Q))error(“隊(duì)空，不能出隊(duì)”); else{Q.front=(Q.front+1)%maxsize; returnQ.data[Q->front];}}循環(huán)隊(duì)列---運(yùn)算〔3〕3.鏈隊(duì)列——隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)頭指針始終指向表頭，尾指針始終指向表尾；采用帶頭節(jié)點(diǎn)的鏈表形式。a1a2anfrontrearlinkqueuetypedefstructLQNode{ ElemTypedata;structLQNode*next；}LQNode,*LinkedQNode；typedefstruct{ structLQNode*front,*rear；}LQueue,*LinkedQueue；2〕根本操作與實(shí)現(xiàn)

1.鏈隊(duì)列初始化LinkedQueueLinkedQueueInit(){Q=(LinkedQueue)malloc(sizeof(LQueue)); P=(LinkedQNode)malloc(sizeof(LQnode));P->next=NULL;Q->front=Q->rear=P; returnQ;}LinkedQueueEmpty(LinkedQueueQ){ if(Q->front==Q->rear)return1; elsereturn0;}2.判斷鏈隊(duì)列是否為空a1∧anQ.frontQ.rear∧es…鏈隊(duì)列的入隊(duì)操作:voidLinkedQueueIn(LinkedQueueQ,ElemTypex){p=(LinkedQNode)malloc(sizeof(LQNode)); p->data=x; p->next=NULL;Q->rear->next=p;Q->rear=p;}4.入隊(duì)a1a2an…Q.frontQ.rear∧anQ.frontQ.rear∧∧pp鏈隊(duì)列的出隊(duì)操作:當(dāng)隊(duì)列中只有一個(gè)元素時(shí):Q.rearElemTypeLinkedQueueOut(LinkedQueueQ){if(empty(*Q))error(“隊(duì)空”); else{

p=Q->front->next; Q->front->next=p->next; x=p->data;

free(p); if(Q->front->next==NULL)

Q->rear=Q->front; returnx;

}}5.出隊(duì)作業(yè)循環(huán)隊(duì)列Q，請(qǐng)?jiān)O(shè)置一個(gè)判斷隊(duì)列狀態(tài)為空和為滿的標(biāo)志tag。請(qǐng)?jiān)O(shè)計(jì)該隊(duì)列的入隊(duì)和出隊(duì)算法。四.隊(duì)列的應(yīng)用例：用隊(duì)列計(jì)算并打印楊輝三角的前8行分析：

s1s20151010511615201561解決方法：用隊(duì)列保存上一行的內(nèi)容，每當(dāng)由上一行的兩個(gè)數(shù)求出下一行的一個(gè)數(shù)時(shí)，刪除前一個(gè)數(shù)，新求出的數(shù)入隊(duì)。111121133114641151010511615201561172135352171

voidOut_Number(intn){init_Queue(Q);cout<<1<<endl;enqueue(Q,s1+s2);for(i=2;i<=n;i++) {s1=0; for(j=1;j<=i-1;j++) {s2=outqueue(Q); cout<<s1+s2; enqueue(Q,s1+s2); s1=s2;} cout<<1<<endl;enqueue(Q,1);}}例1：對(duì)于一個(gè)棧，給出輸入項(xiàng)A、B、C，如果輸入項(xiàng)序列由ABC組成，試給出所有可能的輸出序列。(能否產(chǎn)生CAB序列?)A進(jìn)A出B進(jìn)B出C進(jìn)C出ABCA進(jìn)A出B進(jìn)C進(jìn)C出B出ACBA進(jìn)B進(jìn)B出A出C進(jìn)C出BACA進(jìn)B進(jìn)B出C進(jìn)C出A出BCAA進(jìn)B進(jìn)C進(jìn)C出B出A出CBA不可能產(chǎn)生輸出序列CAB例：計(jì)算機(jī)系2001年考研題〔程序設(shè)計(jì)根底〕設(shè)依次進(jìn)入一個(gè)棧的元素序列為c，a，b，d，那么可得到出棧的元素序列是：Ａ〕a，b，c，dＢ〕c，d，a，bＣ〕b，c，d，aＤ〕a，c，d，bA、D可以（B、C不行）。答：一、定義二、遞歸的分類三、使用遞歸的幾種情況1、定義是遞歸的§3.3棧的應(yīng)用——遞歸例1：fact(n)=1n×

fact(n-1)

n=1，0n>1分析：n=0,2、數(shù)據(jù)結(jié)構(gòu)是遞歸的3、問(wèn)題的解法是遞歸的intfact(intn){if(n<0)printf(“n<0,dataerror!\n”);elseif(n==0||n==1)return1;elsereturnfact(n-1)*n;}練習(xí)：用遞歸程序求解1+2+3+……+100。作業(yè)：編一遞歸函數(shù)求xn二、遞歸程序的閱讀例:對(duì)下面的遞歸程序，寫出調(diào)用p(3)的運(yùn)行結(jié)果

voidp(intn)

{if(n>0)

{p(n-1);

cout<<n;

p(n-2);

}}輸出：P(4)w=4p(3)w=3p(2)w=2p(1)w=1p(0)w=0{{{{{……………

p(3);p(2);p(1);p(0);……………cout<<4cout<<3cout<<2cout<<1p(2)(調(diào)用)p(1)(調(diào)用)p(0)p(-1)}}}}1231412三、將遞歸程序轉(zhuǎn)為非遞歸程序?qū)崿F(xiàn)是借助于棧的使用例：將下面的程序轉(zhuǎn)化為非遞歸的程序

voidp(intw)

{if(w>0)

{p(w-1);cout<<w;

}}voidp(intw){init_stack(s);while(w>0)

{push_stack