數(shù)據(jù)結(jié)構(gòu)03棧與隊(duì)列ppt課件

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 1. 第三章 棧棧和隊(duì)隊(duì)列主要內(nèi)容主要內(nèi)容棧的定義及其根本操作棧的定義及其根本操作1順序棧及鏈棧的實(shí)現(xiàn)順序棧及鏈棧的實(shí)現(xiàn)2隊(duì)列的定義及其根本操作隊(duì)列的定義及其根本操作3循環(huán)隊(duì)列及鏈隊(duì)列的實(shí)現(xiàn)循環(huán)隊(duì)列及鏈隊(duì)列的實(shí)現(xiàn)4棧和隊(duì)列的運(yùn)用棧和隊(duì)列的運(yùn)用5教學(xué)要求教學(xué)要求教學(xué)重點(diǎn)教學(xué)難點(diǎn)難點(diǎn)目的和要求1.了解棧的定義、特征及其所定義的根本操作2. 掌握在兩種存儲(chǔ)構(gòu)造上對(duì)棧的根本操作的實(shí)現(xiàn)3.了解隊(duì)列的定義、特征及其所定義的根本操作4. 掌握在兩種存儲(chǔ)構(gòu)造上對(duì)隊(duì)列的根本操作的實(shí)現(xiàn)1.棧的定義及邏輯特點(diǎn)2. 順序棧和鏈棧的存儲(chǔ)構(gòu)造及操作實(shí)現(xiàn)3.入棧、出棧等操作在順序棧和鏈棧上的操作4. 隊(duì)列

2、棧的定義及邏輯特點(diǎn)5. 順序隊(duì)列、循環(huán)隊(duì)列和鏈隊(duì)列的存儲(chǔ)構(gòu)造及操作實(shí)現(xiàn)6.入隊(duì),出隊(duì)等操作在循環(huán)隊(duì)列和鏈隊(duì)列上的操作1.順序棧的溢出判別條件2.棧的運(yùn)用3.循環(huán)隊(duì)列的隊(duì)空、隊(duì)滿判別條件4.循環(huán)隊(duì)列上的插入、刪除操作3.1.1棧的定義及其根本操作棧的定義及其根本操作棧：限定結(jié)點(diǎn)插入和刪除只能在同一端進(jìn)展的線性表?xiàng)＃合薅ńY(jié)點(diǎn)插入和刪除只能在同一端進(jìn)展的線性表 anan-1.a2a1進(jìn)棧進(jìn)棧 出棧出棧 棧頂指針棧頂指針(top) 棧底指針棧底指針(bottom) 棧頂元素棧頂元素 棧底元素棧底元素 一個(gè)重要特點(diǎn)：最后壓入的結(jié)點(diǎn)最先彈出，最先壓入的結(jié)點(diǎn)只能最后彈出LIFO表表(Last In Firs

3、t Out )棧頂指針棧頂指針 (top) 棧底指針棧底指針(bottom)空?？諚?.1.棧的定義棧的定義棧頂指針和棧底指針都等于0時(shí)，棧為空1u 創(chuàng)建棧創(chuàng)建棧2u 判?？张袟？?u 壓棧壓棧4u 彈棧彈棧5u 讀棧讀棧6u 置?？?u 求棧長(zhǎng)度2.2.棧的根本操作棧的根本操作3.1.2順序棧及其操作順序棧及其操作1.1.棧的順序存儲(chǔ)構(gòu)造棧的順序存儲(chǔ)構(gòu)造順序存儲(chǔ)構(gòu)造存儲(chǔ)的棧稱為順序棧，用一個(gè)一維數(shù)組存儲(chǔ) 棧頂指針不是指針類型，而是一個(gè)整數(shù)C言語(yǔ)描畫(huà)順序棧言語(yǔ)描畫(huà)順序棧 #define DT char #define M 100 typedef struct DT dataM; int top

4、; SEQSTACK;指示棧頂元素在順序棧中的位置順序棧上的操作順序棧上的操作創(chuàng)建棧創(chuàng)建棧SEQSTACK INISTACK() SEQSTACK S;S =0;return(S);首先根據(jù)棧的數(shù)據(jù)類型闡明一個(gè)棧S，再置棧頂指針為0棧頂棧頂(top)=0順序棧上的操作順序棧上的操作判?？眨涸O(shè)判?？眨涸O(shè)S S是是SEQSTACKSEQSTACK類型的變量，棧底位置在向量的低端，類型的變量，棧底位置在向量的低端，stop=0stop=0表示空棧表示空棧top=0M1棧空?？諚ｍ斨羔榯op,指向?qū)嵺`棧底后的空位置，初值為0topM1壓棧壓棧.BCDEFtoptoptoptoptop棧滿234M1AB

5、CD彈棧彈棧toptoptoptoptop棧空設(shè)數(shù)組大小為Mtop=0,?？眨藭r(shí)出棧，那么下溢underflow)留意：彈棧留意：彈棧算法并未闡算法并未闡明對(duì)刪除了明對(duì)刪除了的結(jié)點(diǎn)的處的結(jié)點(diǎn)的處置置設(shè)數(shù)組大小為Mtop=M,棧滿，此時(shí)入棧，那么上溢overflow)壓棧：壓棧：stopstop是正向添加的，即進(jìn)棧時(shí)需將是正向添加的，即進(jìn)棧時(shí)需將stopstop加加1 1彈棧：退棧時(shí)需將彈棧：退棧時(shí)需將stop stop 減減1 1順序棧上的操作順序棧上的操作讀棧讀棧把棧S的棧頂結(jié)點(diǎn)數(shù)據(jù)讀出作為函數(shù)的前往值12340ABCDEtop前往值讀棧讀棧char GETSTACK(SEQSTACK S

6、) if (S=0) printf(empty!); return 0; else returnS.dataS;S.dataS留意：該算法并未改動(dòng)棧的形狀，即已讀出的結(jié)點(diǎn)仍保管在原處不變3.1.3鏈棧及其操作鏈棧及其操作1.1.棧的鏈存儲(chǔ)構(gòu)造棧的鏈存儲(chǔ)構(gòu)造鏈存儲(chǔ)構(gòu)造存儲(chǔ)的棧稱為鏈棧，鏈棧的結(jié)點(diǎn)由結(jié)點(diǎn)數(shù)據(jù)和next指針構(gòu)成。鏈棧的結(jié)點(diǎn)類型： #define DT char typedef struct snode DT data; struct snode *next; STACKNODE;結(jié)點(diǎn)經(jīng)過(guò)next指針鏈接起來(lái)鏈棧的結(jié)點(diǎn)數(shù)據(jù)結(jié)點(diǎn)數(shù)據(jù)結(jié)點(diǎn)數(shù)據(jù)指針指針datanext插入和刪除總是在鏈的頭部

7、進(jìn)展，所以頭指針也是棧頂指針插入和刪除總是在鏈的頭部進(jìn)展，所以頭指針也是棧頂指針留意留意: : 鏈棧鏈棧中指針的方向中指針的方向top為棧頂指針，一直指向當(dāng)前棧頂元素前面的頭結(jié)點(diǎn)棧名、鏈頭指針、棧頂指針定義一個(gè)鏈棧 STACKNODE *top 棧頂結(jié)點(diǎn)棧頂結(jié)點(diǎn)top 棧底結(jié)點(diǎn)棧底結(jié)點(diǎn)DCBA.非空棧底非空棧底top非空棧底非空棧底3.1.3鏈棧及其操作鏈棧及其操作1.1.鏈棧上的操作鏈棧上的操作LS 棧頂結(jié)點(diǎn)棧頂結(jié)點(diǎn)棧底結(jié)點(diǎn)棧底結(jié)點(diǎn).Xq新結(jié)點(diǎn)新結(jié)點(diǎn)LS STACKNODE *PUSLSTACK(STACKNODE *LS,char x)STACKNODE *q;q=(STACKNODE *

8、)malloc(sizeof(STACKNODE); q-data=x; q-next=LS;LS =q;return(LS);壓棧壓棧鏈棧無(wú)棧滿問(wèn)題，空間可擴(kuò)展。插入與刪除僅在棧頂處執(zhí)行3.1.3鏈棧及其操作鏈棧及其操作彈棧彈棧棧頂結(jié)點(diǎn)棧頂結(jié)點(diǎn)棧底結(jié)點(diǎn)棧底結(jié)點(diǎn).LS pSTACKNODE *POPLSTACK(STACKNODE *LS)STACKNODE *q;if(LS = NULL)printf(Empty!); else q=LS; LS = q-next; free(q);return(LS);LSq=NULL,前往前往n3.1.3鏈棧及其操作鏈棧及其操作求棧長(zhǎng)度求棧長(zhǎng)度int S

9、IZELSTACK(STACKNODE *LS)int n=0; STACKNODE *q;for(q=LS;q!=NULL;q=q-next) n+;return(n); 統(tǒng)計(jì)鏈棧LS中當(dāng)前所含結(jié)點(diǎn)個(gè)數(shù) 棧頂結(jié)點(diǎn)棧頂結(jié)點(diǎn)棧底結(jié)點(diǎn)棧底結(jié)點(diǎn).LS qn=1qn=2qn=3qn=?3.1.4棧構(gòu)造的運(yùn)用棧構(gòu)造的運(yùn)用數(shù)值轉(zhuǎn)換的運(yùn)用數(shù)值轉(zhuǎn)換的運(yùn)用一個(gè)簡(jiǎn)單算法是逐次除以基數(shù) d 取余法。如10進(jìn)制數(shù)到2進(jìn)制數(shù)的轉(zhuǎn)換d2。例：例： (67)10=(100011)2，其運(yùn)算過(guò)程如下：，其運(yùn)算過(guò)程如下： 輸 出 順 序 NN div 2N mod 267331331611680840420210101計(jì) 算

10、順 序 商為 0 時(shí)得到的余數(shù)是 Bn 的最高位3.1.4棧構(gòu)造的運(yùn)用棧構(gòu)造的運(yùn)用topvoid DTOB(int n)SEQSTACK NS;int x=0;NS = INISTACK();if(n=0)NS = PUSSTACK(NS,0);while(n)NS = PUSSTACK(NS,n%2); n=(n-n%2)/2;printf(Conversed to Binary number = );while(!EMPSTACK(NS) x=GETSTACK(NS); NS=POPSTACK(NS);printf(%d ,x);printf(n);67111033top16top8top

11、40top20top10top0Push(S, N%2) 1000011數(shù)值轉(zhuǎn)換的運(yùn)用數(shù)值轉(zhuǎn)換的運(yùn)用3.1.4棧構(gòu)造的運(yùn)用棧構(gòu)造的運(yùn)用計(jì)算算術(shù)表達(dá)式的運(yùn)用計(jì)算算術(shù)表達(dá)式的運(yùn)用這是棧運(yùn)用的典型例子這是棧運(yùn)用的典型例子無(wú)括號(hào)算術(shù)表達(dá)式求值中綴表達(dá)式直接求值 (1)規(guī)定優(yōu)先級(jí)表；(2) 設(shè)置兩個(gè)棧：DNS(運(yùn)算數(shù)棧)和OPS(運(yùn)算符棧)；(3) 自左向右掃描，遇操作符那么與OPS棧頂優(yōu)先級(jí)比較：當(dāng)前操作符OPS棧頂那么進(jìn)OPS棧；當(dāng)前操作符 OPS棧頂，DNS棧頂、次頂和OPS棧頂，退棧構(gòu)成運(yùn)算， 運(yùn)算結(jié)果進(jìn)DNS棧。例：實(shí)現(xiàn)例：實(shí)現(xiàn)5+4*78/2#的運(yùn)算過(guò)程時(shí)棧區(qū)變化情況的運(yùn)算過(guò)程時(shí)棧區(qū)變化情況

12、5 + 4 7 8 / 2 #5+47288操作數(shù)或結(jié)果操作數(shù)或結(jié)果 33/2429運(yùn)算符運(yùn)算符3.2隊(duì)列隊(duì)列3.2.1 3.2.1 隊(duì)列的定義及其根本操作隊(duì)列的定義及其根本操作隊(duì)列的定義隊(duì)列的定義限定在表的一端插入、另一端刪除。限定在表的一端插入、另一端刪除。 先進(jìn)先出先進(jìn)先出 (FIFO (FIFO構(gòu)造構(gòu)造) )。 隊(duì)頭隊(duì)頭 以下圖是隊(duì)列的表示圖： a1a2an 出隊(duì)方向 入隊(duì)方向隊(duì)頭指針隊(duì)頭指針 隊(duì)尾指針隊(duì)尾指針 刪除端刪除端插入端插入端1u 建立隊(duì)列建立隊(duì)列2u 判隊(duì)空判隊(duì)空3u 插入結(jié)點(diǎn)插入結(jié)點(diǎn)4u 刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)5u 讀隊(duì)頭結(jié)點(diǎn)讀隊(duì)頭結(jié)點(diǎn)6u 隊(duì)列置空7u 求隊(duì)列長(zhǎng)度2.2.隊(duì)列

13、的根本操作隊(duì)列的根本操作3.2.2順序隊(duì)列及其操作順序隊(duì)列及其操作1.1.隊(duì)列的順序存儲(chǔ)構(gòu)造隊(duì)列的順序存儲(chǔ)構(gòu)造順序存儲(chǔ)構(gòu)造存儲(chǔ)的隊(duì)列稱為順序隊(duì)列，用一個(gè)一維數(shù)組存儲(chǔ) #define DT char#define M 100typedef struct DT dataM； int front，rear； SEQUEUE;C言語(yǔ)描畫(huà)順序棧言語(yǔ)描畫(huà)順序棧 隊(duì)頭、隊(duì)尾指針不是指針類型，而是數(shù)組元素下標(biāo)隊(duì)頭指針一直指向隊(duì)頭結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)位置隊(duì)尾指針總是指向隊(duì)尾結(jié)點(diǎn)位置隊(duì)頭、隊(duì)尾指隊(duì)頭、隊(duì)尾指針初始值為針初始值為0順序隊(duì)列上的操作順序隊(duì)列上的操作頭尾頭尾 指針指針 初始化時(shí)的初始值均應(yīng)置為初始化時(shí)的初始

14、值均應(yīng)置為 0 0。 入隊(duì)，尾指針增入隊(duì)，尾指針增 1 1 出隊(duì)，頭指針增出隊(duì)，頭指針增 1 1 front= 0rear= 0234561隊(duì)空隊(duì)空234561fronta,b,c插入插入abcrearrear234561a,b,c入隊(duì)入隊(duì)abcfront設(shè)兩個(gè)指針設(shè)兩個(gè)指針front,rear,商定：商定：rear指示隊(duì)尾元素；指示隊(duì)尾元素；front指示隊(duì)頭元素前一位置指示隊(duì)頭元素前一位置初值初值front = rear = 0空隊(duì)列條件：空隊(duì)列條件：front=rear入隊(duì)列：入隊(duì)列：sq+rear=x;出隊(duì)列：出隊(duì)列：x=sq+front;rearrearfrontrear234561

15、a,b,c刪除刪除abcfrontfrontfront存在問(wèn)題存在問(wèn)題設(shè)數(shù)組維數(shù)為設(shè)數(shù)組維數(shù)為M，那么：，那么：當(dāng)當(dāng)front=0,rear=M時(shí)，再有元素入隊(duì)發(fā)生溢出時(shí)，再有元素入隊(duì)發(fā)生溢出真溢出真溢出當(dāng)當(dāng)front 0,rear=M時(shí)，再有元素入隊(duì)發(fā)生溢出時(shí)，再有元素入隊(duì)發(fā)生溢出假溢出假溢出rear234561真溢出真溢出abcfrontrear234561假溢出假溢出abcfront“假溢出假溢出隊(duì)列的存儲(chǔ)空間未滿，卻發(fā)生了溢出隊(duì)列的存儲(chǔ)空間未滿，卻發(fā)生了溢出處理處理“假溢出的問(wèn)題有兩種可行的方法：假溢出的問(wèn)題有兩種可行的方法： (1) 平移元素：把元素平移到隊(duì)列的首部。 效率低 (2)

16、 將新元素插入到第一個(gè)位置上，構(gòu)成循環(huán)隊(duì)列，入隊(duì)和出隊(duì)仍按“先進(jìn)先出的原那么進(jìn)展。 操作效率、空間利用率高def3.2.3循環(huán)隊(duì)列及其操作循環(huán)隊(duì)列及其操作循環(huán)隊(duì)列是把順序隊(duì)列的頭尾相接構(gòu)成一個(gè)圓環(huán)；邏輯上把1號(hào)結(jié)點(diǎn)作為M號(hào)結(jié)點(diǎn)的后繼結(jié)點(diǎn)處置 根本思想：把隊(duì)列想象成環(huán)形，讓根本思想：把隊(duì)列想象成環(huán)形，讓LQ0LQ0接在接在LQM-1LQM-1之后，假設(shè)之后，假設(shè)rear+1=M,rear+1=M,那么令那么令rear=0;rear=0;實(shí)現(xiàn)：利用實(shí)現(xiàn)：利用“模運(yùn)算模運(yùn)算入隊(duì)：入隊(duì)： rear=(rear+1)%M; LQrear=x; rear=(rear+1)%M; LQrear=x;出隊(duì)：出

17、隊(duì)： front=(front+1)%M; x=LQfront; front=(front+1)%M; x=LQfront;初始形狀frontrear0 01 12 23 34 45 5ABCABC出隊(duì)出隊(duì)frontrear0 01 12 23 34 45 5DEFDEF入隊(duì)入隊(duì)front0 01 12 23 34 45 5rear隊(duì)滿、隊(duì)空斷定條件隊(duì)滿、隊(duì)空斷定條件僅憑 front = rear 不能斷定隊(duì)列是空還是滿 處理方案：1.另外設(shè)一個(gè)標(biāo)志以區(qū)別隊(duì)空、隊(duì)滿2.少用一個(gè)元素空間： 隊(duì)空：front=rear 隊(duì)滿：(rear+1)%M=front循環(huán)隊(duì)列初始條件： 隊(duì)頭指針 = 隊(duì)尾指

18、針 = 0循環(huán)隊(duì)列滿條件： MOD隊(duì)尾指針+1,M = 隊(duì)頭指針循環(huán)隊(duì)列空條件： 隊(duì)頭指針 = 隊(duì)尾指針隊(duì)頭指針推進(jìn)計(jì)算： 隊(duì)頭指針 = MOD隊(duì)頭指針+1，M隊(duì)尾指針推進(jìn)計(jì)算： 隊(duì)尾指針 MOD隊(duì)尾指針+1，M循環(huán)隊(duì)列上的操作循環(huán)隊(duì)列上的操作插入插入1檢查隊(duì)列能否已滿，假設(shè)隊(duì)滿，那么進(jìn)展溢出錯(cuò)誤處置；2將隊(duì)尾指針后移一個(gè)位置即加1，指向下一單元；3將新元素賦給存入以rear值為下標(biāo)的數(shù)組元素中 ；SEQUEUE INCQUEUE(SEQUEUE CQ,DT x) if(CQ.rear+1)%M = CQ.front) printf(CQ is full!); elseCQ.rear=(CQ.

19、rear+1)%M; CQ.dataCQ.rear=x; returnCQ;循環(huán)隊(duì)列上的操作循環(huán)隊(duì)列上的操作刪除刪除1檢查隊(duì)列能否為空，假設(shè)隊(duì)空，那么進(jìn)展下溢錯(cuò)誤處置；2將隊(duì)首指針后移一個(gè)位置即加1；OUTCQUEUE(SeQueue CQ) if(CQ.front=CQ.rear) printf(CQ is empty!); else CQ.front=(CQ.front+1)%M; returnCQ; 3.2.4鏈隊(duì)列及其操作鏈隊(duì)列及其操作鏈存儲(chǔ)構(gòu)造存儲(chǔ)的隊(duì)列稱為鏈隊(duì)列，鏈棧的結(jié)點(diǎn)由結(jié)點(diǎn)數(shù)據(jù)和next指針構(gòu)成。1，隊(duì)列的鏈存儲(chǔ)構(gòu)造，隊(duì)列的鏈存儲(chǔ)構(gòu)造 結(jié)點(diǎn)數(shù)據(jù)結(jié)點(diǎn)數(shù)據(jù)指針指針datanext

20、鏈隊(duì)列的結(jié)點(diǎn)類型： #define DT char； typedef struct qnode DT data； struct qnode *next； LINKNODE； 頭結(jié)點(diǎn)頭結(jié)點(diǎn)隊(duì)尾結(jié)點(diǎn)隊(duì)尾結(jié)點(diǎn)ABC.非空鏈隊(duì)非空鏈隊(duì)隊(duì)首結(jié)點(diǎn)隊(duì)首結(jié)點(diǎn)隊(duì)首指針隊(duì)首指針隊(duì)尾指針隊(duì)尾指針為了操作方便，也給鏈隊(duì)列添加一個(gè)頭結(jié)點(diǎn)為了操作方便，也給鏈隊(duì)列添加一個(gè)頭結(jié)點(diǎn)typedef struct LINKNODE *front，*rear ； LINKQUEUE；定義一個(gè)鏈隊(duì)列定義一個(gè)鏈隊(duì)列一個(gè)鏈隊(duì)列由一個(gè)頭指針和一個(gè)尾指針獨(dú)一確定把結(jié)點(diǎn)鏈接起來(lái)構(gòu)成一個(gè)單鏈表 鏈?zhǔn)疥?duì)列在進(jìn)隊(duì)時(shí)無(wú)隊(duì)滿問(wèn)題，但有隊(duì)空問(wèn)題空隊(duì)列的斷定

21、條件是：頭指針和尾指針都指向頭結(jié)點(diǎn)空隊(duì)列的斷定條件是：頭指針和尾指針都指向頭結(jié)點(diǎn) 隊(duì)首指針隊(duì)首指針隊(duì)尾指針隊(duì)尾指針頭結(jié)點(diǎn)頭結(jié)點(diǎn)隊(duì)空的條件隊(duì)空的條件fornt= =NULL?front-next= =NULL? 空鏈隊(duì)列空鏈隊(duì)列 隊(duì)首指針隊(duì)首指針 隊(duì)尾指針隊(duì)尾指針生成空鏈隊(duì)列：生成空鏈隊(duì)列：LINKQUEUE *INILQUEUE(LINKQUEUE * LQ) LQ-front=(LINKNODE *) malloc(sizeof(LINKNODE); LQ-front-data=#; LQ-front-next=NULL; LQ-rear=LQ-front; return(LQ);#3.2.4鏈隊(duì)列及其操作鏈隊(duì)列及其操作2鏈隊(duì)列上的操作鏈隊(duì)列上的操作 rearfrontxyp p 插入插入 INLQUEUE *(LINKQUEUE * LQ,DT x) LINKNODE *p; p=(LINKNODE *) malloc(sizeof(LINKNODE); p-data=x; p-next=NULL; LQ-rear-next=p; LQ-rear=p;return(LQ);3.2.4鏈隊(duì)列及其操作鏈隊(duì)列及其操作2鏈