堆棧堆棧的應(yīng)用隊列隊列的應(yīng)用教學(xué)內(nèi)容

堆棧堆棧的應(yīng)用隊列隊列的應(yīng)用第三章堆棧和隊列9/26/202413.1棧(Stack)只允許在一端插入和刪除的順序表允許插入和刪除的一端稱為棧頂

(top)，另一端稱為棧底(bottom)特點后進(jìn)先出(LIFO)退棧進(jìn)棧9/26/20242進(jìn)棧示例

9/26/20243退棧示例9/26/20244棧的順序存儲結(jié)構(gòu)順序棧的定義typedefintdatatype;#definemaxsize64typedefstruct{datatypedata[maxsize];inttop;}seqstack;

9/26/20246棧的基本運算置空棧SETNULL(seqstack*s){s->top＝-1;}

判?？読ntEMPTY(seqstack*s){if(s->top>=0)returnFALSE;elsereturnTRUE;}9/26/20247進(jìn)棧seqstack*PUSH(seqstack*s,datatypex){if(s->top==maxsize-1){printf(“overflow\n”);returnNULL;}else{s->top++;s->data[s->top]＝x;}returns;}9/26/20248退棧datatypePOP(seqstack*s){if(EMPTY(s)){printf(“underflow\n”);returnNULL;}else{s->top--;return(s->data[s->top+1]);}}9/26/20249取棧頂datatypeTOP(seqstack*s){if(EMPTY(s)){printf(“underflow\n”);returnNULL;}elsereturn(s->data[s->top]);}9/26/202410兩個堆棧共享空間0maxsize-1lefttoprighttop9/26/202411棧的鏈接表示—鏈?zhǔn)綏ｆ準(zhǔn)綏o棧滿問題，空間可擴(kuò)充插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏５臈ｍ斣阪滎^適合于多棧操作9/26/202412棧的鏈接存儲結(jié)構(gòu)鏈棧的結(jié)點定義typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}linkstack;

9/26/202413鏈棧的進(jìn)棧算法linkstack*PUSHLSTACK(linkstack*top,datatypex){linkstack*p;p＝malloc(sizeof(linkstack));p->data＝x;p->next＝top;returnp;}9/26/202414鏈棧的出棧算法linkstack*POPLSTACK(linkstack*top,datatype*datap){linkstack*p;if(top==NULL){printf(“underflow\n”);returnNULL;}else{*datap＝top->data;p＝top;top＝top->next;free(p);returntop;}}9/26/202415例：對于一個棧，給出輸入項A、B、C，如果輸入項序列由ABC組成，試給出所有可能的輸出序列。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)生輸出序列CAB9/26/202416棧的應(yīng)用舉例－－文字編輯器seqstacks;EDIT(){charc;SETNULL(&s);c＝getchar();while(c!=‘*’){if(c==‘#’)POP(&s);elseif(c==‘@’)SETNULL(&s);elsePUSH(&s,c);c＝getchar();}}9/26/202417棧的應(yīng)用－－遞歸函數(shù)intFACT(intn){if(n==1)return(1);elsereturn(n*FACT(n-1));}

9/26/202418棧的應(yīng)用－－表達(dá)式計算中綴表達(dá)式：A+(B–C/D)×E后綴表達(dá)式：ABCD/－E×+（逆波蘭表達(dá)式）后綴表達(dá)式特點1、與相應(yīng)的中綴表達(dá)式中的操作數(shù)次序相同2、沒有括號9/26/202419后綴表達(dá)式的處理過程操作順序后綴表達(dá)式ABCD/－E×+T1←C/DABT1－E×+T2←B–T1AT2E×+T3←T2×EAT3+T4←A+T3T49/26/202420ABCDE＋×－／ABCT1＋×－ABT2＋×AT3＋9/26/202421中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式＋－×／()#＋>><<<>>－>><<<>>×>>>><>>／>>>><>>(<<<<<=)>>>>>>#<<<<<=當(dāng)前運算符棧頂運算符9/26/202422中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的處理規(guī)則1、如為操作數(shù)，直接輸出到隊列；2、若當(dāng)前運算符為“（”，則直接入棧；2、如當(dāng)前運算符高于棧頂運算符，入棧；3、如當(dāng)前運算符低于棧頂運算符，棧頂運算符退棧，并輸出到隊列，當(dāng)前運算符再與棧頂運算符比較；4、如當(dāng)前運算符為“）”，則將棧中“（”以后的字符依次彈出存入輸出到隊列，然后將“）”彈出退棧。繼續(xù)讀下一符號；5、如當(dāng)前運算符等于棧頂運算符，且棧頂運算符為“#”，當(dāng)前運算符也為“#”，則棧頂運算符退棧，處理結(jié)束；9/26/202423步驟中綴表達(dá)式STACK輸出1A＋(B－C／D)×E##2＋(B－C／D)×E##A3(B－C／D)×E##＋A4B－C／D)×E##＋(A5－C／D)×E##＋(AB6C／D)×E##＋(－AB7／D)×E##＋(－ABC8D)×E##＋(－/ABC9)×E##＋(－/ABCD9/26/202424步驟中綴表達(dá)式STACK輸出10×E##＋(－ABCD/11×E##＋(ABCD/－12×E##＋ABCD/－13E##＋×ABCD/－14##＋×ABCD/－E15##＋ABCD/－E×16##ABCD/－E×＋9/26/202425隊列(

Queue)定義隊列是只允許在一端刪除，在另一端插入的順序表允許刪除的一端叫做隊頭(front)，允許插入的一端叫做隊尾(rear)。特性先進(jìn)先出(FIFO,FirstInFirstOut)9/26/202426隊列的進(jìn)隊和出隊

進(jìn)隊時隊尾指針先進(jìn)一rear=rear+1，再將新元素按

rear

指示位置加入。出隊時隊頭指針先進(jìn)一front=front+1，再將下標(biāo)為front的元素取出。

隊滿時再進(jìn)隊將溢出出錯；隊空時再出隊將隊空處理。9/26/202427順序隊列的指針說明typedefstruc{datatypedata[maxsize];intfront,rear;}sequeue;9/26/202428隊列的基本操作1、置空隊列2、判定隊列是否為空3、取隊列頭元素4、將新元素插入隊尾5、隊列頭元素出隊9/26/202429順序隊列置隊空SETNULL(sequeue*sq){sq->front＝maxsize-1;sq->rear＝maxsize-1;}9/26/202430順序隊列判隊空intEMPTY(sequeue*sq){if(sq->rear==sq->front)return(TRUE);elsereturn(FALSE);}

9/26/202431順序隊列取隊頭元素datatypeFRONT(sequeue*sq){if(EMPTY(sq)){printf(“queueisempty\n”);returnNULL;}elsereturn((sq->front+1)%maxsize);}9/26/202432順序隊列入隊intENQUEUE(sequeue*sq,datatypex){if(sq->front==(sq->rear+1)%maxsize){printf(“sequeueisfull\n”;returnNULL);}else{sq->rear＝(sq->rear+1)%maxsize;sq->data[sq->rear]＝x;return(TRUE);}}9/26/202433順序隊列出隊datetypeDEQUEUE(sequeue*sq){if(EMPTY(sq)){printf(“queueisempty\n”);returnNULL;}else{sq->front＝(sq->front+1)%maxsize;return(sq->data[sq->front]);}}9/26/202434存儲隊列的數(shù)組被當(dāng)作首尾相接的表處理。隊頭、隊尾指針加1時從maxSize

-1直接進(jìn)到0，可用語言的取模(余數(shù))運算實現(xiàn)。隊頭指針進(jìn)1:

front=(front+1)%maxSize;

隊尾指針進(jìn)1:rear=(rear+1)%maxSize;隊列初始化：front=rear=0;隊空條件：front==rear;隊滿條件：(rear+1)%maxSize==front

循環(huán)隊列(CircularQueue)9/26/202435循環(huán)隊列的進(jìn)隊和出隊9/26/202436隊列的鏈接表示—鏈?zhǔn)疥犃嘘狀^在鏈頭，隊尾在鏈尾。鏈?zhǔn)疥犃性谶M(jìn)隊時無隊滿問題，但有隊空問題。隊空條件為front==NULL9/26/202437鏈隊列結(jié)點類型定義typedefstructnode{datatypedata;structnode*next;}linklist;typedefstruct{linklist*front,*rear;}linkqueue;9/26/202438鏈隊列置隊空SETNULL(linkqueue*q){q->front＝malloc(sizeof(linklist));q->front->next＝NULL;q->rear＝q->front;}

9/26/202439鏈隊列判隊空intEMPTY(linkqueue*q){ifq->front==q->rear)return(TRUE);elsereturn(FALSE);}

9/26/202440鏈隊列取隊頭結(jié)點datatypeFRONT(linkqueue*q){if(EMPTY(q)){printf(“queueisempty\n”);returnNULL;}elsereturn(q->front->next->data);}

9/26/202441鏈隊列入隊ENQUEUE(linkqueue*q,datatypex){q->rear->next＝(linklist*)malloc(sizeof(linklist));q->rear＝q->rear->next;q->rear->data＝x;q->rear->next＝NULL;}

9/26/202442鏈隊列出隊datatypeDEQUEUE(linkqueue*q){linklist*s;if(EMPTY(q)){printf(“queueisempty\n”);returnNULL;}else{s＝q->front;q->front＝q->front->next;free(s);return(q->front->data);}}

9/26/20244301110111101010100100111101110011100110000110011012345678123456隊列的應(yīng)用舉例－－求迷宮的最短路徑9/26/202444zxzy1-102-1+130+14+1+15+106+1-170-18-1-1需要解決的問題1：如何從某一坐標(biāo)點出發(fā)搜索其四周的鄰點9/26/202445需要解決的問題2：如何存儲搜索路徑需要解決的問題3：如何防止重復(fù)到達(dá)某坐標(biāo)點步xypre1110222133324343…………9/26/202446需要解決的問題4：如何輸出搜索路徑1…121314151617181920x1…525656656…y1…663175488…pre0…8910101112141616…隊列9/26/202447#definem10#definen15

typedefstruct{intx,y;intpre;}sqtype;sqtypesq[400];

intmg[m+1][n+1];intzx[8],z