數(shù)據(jù)結(jié)構(gòu)第三部分棧和隊(duì)列ppt課件

1、 數(shù)據(jù)結(jié)構(gòu)課程本章內(nèi)容3.1 棧3.2 棧的運(yùn)用舉例3.3 隊(duì)列中國(guó)科大數(shù)據(jù)結(jié)構(gòu)3.1 棧3.1.1 3.1.1 棧的定義棧的定義棧棧stackstack：是限定僅在表尾進(jìn)展插入和刪除操作的線(xiàn)性表。又稱(chēng)為：是限定僅在表尾進(jìn)展插入和刪除操作的線(xiàn)性表。又稱(chēng)為后進(jìn)先出后進(jìn)先出last in first outlast in first out的線(xiàn)性表簡(jiǎn)稱(chēng)的線(xiàn)性表簡(jiǎn)稱(chēng)LIFOLIFO構(gòu)造。構(gòu)造。棧頂棧頂toptop：棧表尾端。：棧表尾端。棧底棧底bottombottom：棧表頭端。：棧表頭端。例：假設(shè)棧例：假設(shè)棧 S=(a1,a2,an) S=(a1,a2,an) ，那么，那么 a1 a1 稱(chēng)稱(chēng)為棧底

2、元素，為棧底元素，an an 為棧頂元素。棧中元素按為棧頂元素。棧中元素按a1,a2,an a1,a2,an 的次序進(jìn)棧，退棧的第一個(gè)元的次序進(jìn)棧，退棧的第一個(gè)元素應(yīng)為棧頂元素。如右圖所示。素應(yīng)為棧頂元素。如右圖所示。 出棧出棧 進(jìn)棧進(jìn)棧 棧頂棧頂 an . . . a2 棧底棧底 a1 棧的表示圖棧的表示圖中國(guó)科大數(shù)據(jù)結(jié)構(gòu)3.1 棧3.1.2 3.1.2 棧的順序存儲(chǔ)構(gòu)造棧的順序存儲(chǔ)構(gòu)造定義：順序棧即棧的順序存儲(chǔ)構(gòu)造：是利用一組地址延續(xù)的存儲(chǔ)定義：順序棧即棧的順序存儲(chǔ)構(gòu)造：是利用一組地址延續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)附設(shè)指針單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)附設(shè)指針

3、toptop指示棧指示棧頂元素在順序棧中的位置。頂元素在順序棧中的位置。C C言語(yǔ)描畫(huà)言語(yǔ)描畫(huà)typedef struct stack_tag typedef struct stack_tag elemtype elemtype * *elem; /elem; /指向存放數(shù)據(jù)元素的內(nèi)存塊指向存放數(shù)據(jù)元素的內(nèi)存塊 int top; /int top; /棧頂標(biāo)識(shí)，棧頂標(biāo)識(shí)，elemtopelemtop是棧頂元素是棧頂元素 int size; /int size; /棧的容量棧的容量 SQSTACK;SQSTACK;圖形表示圖形表示topbottomtopbottomtopbottomAABCDE

4、棧的順序存儲(chǔ)構(gòu)造表示圖棧的順序存儲(chǔ)構(gòu)造表示圖 中國(guó)科大數(shù)據(jù)結(jié)構(gòu)3.1 棧p初始化棧初始化棧pint InitSqstack(SQSTACK *S, int n)p /初始化順序棧，棧的容量是初始化順序棧，棧的容量是n。勝利那么前往。勝利那么前往1，否那么前往，否那么前往0p S-elem=(elemtype *)malloc(n*sizeof(elemtype); /為數(shù)據(jù)元素分配內(nèi)存為數(shù)據(jù)元素分配內(nèi)存p if (S-elem=NULL) return 0; /初始化失敗初始化失敗p S-size=n; /設(shè)置棧的容量設(shè)置棧的容量p S-top=-1; /設(shè)置棧為空棧設(shè)置棧為空棧p retur

5、n 1;p p銷(xiāo)毀棧銷(xiāo)毀棧pvoid DestroySqstack(SQSTACK *S)p /釋放棧所占有的內(nèi)存釋放棧所占有的內(nèi)存p free(S-elem); /釋放內(nèi)存，并設(shè)置為釋放內(nèi)存，并設(shè)置為NULLp S-elem=NULL;p S-top=-1; /將其他成員設(shè)置成平安值將其他成員設(shè)置成平安值p S-size=0;p中國(guó)科大數(shù)據(jù)結(jié)構(gòu)3.1 棧p入棧入棧pint Push(SQSTACK *S,elemtype e)p /在棧頂一端插入數(shù)據(jù)元素在棧頂一端插入數(shù)據(jù)元素e，操作勝利，那么前往，操作勝利，那么前往1，否那么前往，否那么前往0p if (IsSqstackFull(*S)r

6、eturn 0; /棧滿(mǎn)，操作失敗棧滿(mǎn)，操作失敗p S-top+; /top增增1p S-elemS-top=e; /將將e賦值成新的棧頂賦值成新的棧頂p return 1;pp出棧出棧pint Pop(SQSTACK *S,elemtype *e)p /獲取棧頂數(shù)據(jù)元素，并刪除棧頂。操作勝利，那么前往獲取棧頂數(shù)據(jù)元素，并刪除棧頂。操作勝利，那么前往1，否那么前往，否那么前往0p if (IsSqstackEmpty(*S) return 0; /假設(shè)棧空，操作失敗假設(shè)棧空，操作失敗p *e=S-elemS-top; /獲取棧頂元素獲取棧頂元素p S-top-; /刪除棧頂刪除棧頂p retu

7、rn 1;p中國(guó)科大數(shù)據(jù)結(jié)構(gòu)3.1 棧p判別?？铡M(mǎn)判別?？铡M(mǎn)pint IsSqstackEmpty(SQSTACK S)p /假設(shè)?？?，那么前往假設(shè)棧空，那么前往1，否那么前往，否那么前往0p return S=-1; /top是棧頂標(biāo)識(shí)，是是棧頂標(biāo)識(shí)，是-1時(shí)表示空棧時(shí)表示空棧ppint IsSqstackFull(SQSTACK S)p /假設(shè)棧滿(mǎn)，那么前往假設(shè)棧滿(mǎn)，那么前往1，否那么前往，否那么前往0p return S=S.size-1; /top作為作為elem的下標(biāo)，其最大值是的下標(biāo)，其最大值是size-1 p中國(guó)科大數(shù)據(jù)結(jié)構(gòu)3.1 棧3.1.3 棧的鏈?zhǔn)酱鎯?chǔ)構(gòu)造棧的鏈?zhǔn)酱?/p>

8、儲(chǔ)構(gòu)造 data next S 棧頂棧頂 棧底棧底 鏈棧表示圖鏈棧表示圖 中國(guó)科大數(shù)據(jù)結(jié)構(gòu)3.2 棧的運(yùn)用舉例3.2.1 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換十進(jìn)制數(shù)十進(jìn)制數(shù)N和其他和其他d進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的根本問(wèn)進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的根本問(wèn)題，其處理方法很多，其中一個(gè)是輾轉(zhuǎn)相除法：題，其處理方法很多，其中一個(gè)是輾轉(zhuǎn)相除法： N = ( N div d ) d + N mod d 其中：其中：div為整除運(yùn)算，為整除運(yùn)算，mod為為求余運(yùn)算求余運(yùn)算由于計(jì)算過(guò)程是從低位到高位順序產(chǎn)生八進(jìn)制數(shù)的各個(gè)數(shù)由于計(jì)算過(guò)程是從低位到高位順序產(chǎn)生八進(jìn)制數(shù)的各個(gè)數(shù)位，而輸出應(yīng)從高位到低位進(jìn)展，恰好和計(jì)算過(guò)程相反

9、。因此，假位，而輸出應(yīng)從高位到低位進(jìn)展，恰好和計(jì)算過(guò)程相反。因此，假設(shè)計(jì)算過(guò)程中得到八進(jìn)制數(shù)的各位順序進(jìn)棧，那么按出棧序列打印設(shè)計(jì)算過(guò)程中得到八進(jìn)制數(shù)的各位順序進(jìn)棧，那么按出棧序列打印輸出的即為與輸入對(duì)應(yīng)的八進(jìn)制數(shù)。輸出的即為與輸入對(duì)應(yīng)的八進(jìn)制數(shù)。 例如：例如：(1348)10(2504)8，其運(yùn)算過(guò)程如下：，其運(yùn)算過(guò)程如下：NN div 8 N mod 8 1348 / 168 余余 4 168 / 21 余 0 21 / 2 余 5 2 / 0 余 2中國(guó)科大數(shù)據(jù)結(jié)構(gòu)3.2 棧的運(yùn)用舉例p算法算法3.1如下：如下：p void conversion ( ) /輸入一個(gè)非負(fù)十進(jìn)制整數(shù)，轉(zhuǎn)換成

10、八進(jìn)輸入一個(gè)非負(fù)十進(jìn)制整數(shù)，轉(zhuǎn)換成八進(jìn)制數(shù)。制數(shù)。pInitStack (S); /構(gòu)造空棧構(gòu)造空棧pscanf (“%d, N);pwhile (N) pPush (S, N%8);pN = N / 8;ppwhile (!StackEmpty(s) pPop (S, e);pprintf (“%d, e);pp /conversion中國(guó)科大數(shù)據(jù)結(jié)構(gòu)3.2 棧的運(yùn)用舉例3.2.2 迷宮途徑求解迷宮途徑求解【義務(wù)描畫(huà)】給定某個(gè)迷宮的規(guī)劃及其入口和出口的坐標(biāo)如圖【義務(wù)描畫(huà)】給定某個(gè)迷宮的規(guī)劃及其入口和出口的坐標(biāo)如圖3_9所示，留所示，留意橫坐標(biāo)是從左向右的，但是縱坐標(biāo)是從上向下的，迷宮中空白的

11、地方意橫坐標(biāo)是從左向右的，但是縱坐標(biāo)是從上向下的，迷宮中空白的地方可以走，陰影的部分表示墻壁，走不通。設(shè)計(jì)算法找出從入口到出口的一可以走，陰影的部分表示墻壁，走不通。設(shè)計(jì)算法找出從入口到出口的一切途徑。需求處理切途徑。需求處理2個(gè)問(wèn)題：個(gè)問(wèn)題：迷宮在計(jì)算機(jī)中如何表示。迷宮在計(jì)算機(jī)中如何表示。 int maze 12= 1,1,1,1,1,1,1,1,1,1,1,1, 1,0,0,0,0,0,1,0,0,1,1,1, 1,0,1,0,1,0,1,0,1,1,1,1, 1,0,1,0,0,0,1,0,1,1,1,1, 1,0,1,1,1,1,1,0,1,1,1,1, 1,0,0,0,0,0,0,0

12、,0,0,0,1, 1,1,1,1,1,1,1,1,1,1,1,1 ;如何探求從入口到達(dá)出口的一切途徑。如何探求從入口到達(dá)出口的一切途徑。 深度優(yōu)先探求深度優(yōu)先探求+回溯：從當(dāng)前位置出發(fā)，向四個(gè)方向探求，假設(shè)發(fā)現(xiàn)某方回溯：從當(dāng)前位置出發(fā)，向四個(gè)方向探求，假設(shè)發(fā)現(xiàn)某方向的相鄰位置可走，那么走過(guò)去，將那個(gè)位置當(dāng)作當(dāng)前位置繼續(xù)探求。這向的相鄰位置可走，那么走過(guò)去，將那個(gè)位置當(dāng)作當(dāng)前位置繼續(xù)探求。這時(shí)需求將原當(dāng)前位置保管在棧中。假設(shè)四個(gè)方向都走不通，那么退回到出時(shí)需求將原當(dāng)前位置保管在棧中。假設(shè)四個(gè)方向都走不通，那么退回到出發(fā)點(diǎn)棧頂中的位置。走過(guò)的地方要打上發(fā)點(diǎn)棧頂中的位置。走過(guò)的地方要打上“已走標(biāo)志

13、，回退時(shí)要將已走標(biāo)志，回退時(shí)要將“已已走標(biāo)志去除。走標(biāo)志去除。0 1 2 3 4 5 6 7 8 901234入口(1,5)(8,1)出口10 1165中國(guó)科大數(shù)據(jù)結(jié)構(gòu)3.2 棧的運(yùn)用舉例typedef struct int x,y; /位置坐標(biāo) int v; /探求方向 elemtype;int movex5=0,0,1,0,-1;int movey5=0,-1,0,1,0;#define M 27#define N 25#define MAXSIZE 200算法：void go(int mazeMN ,int x0,int y0 ,int xx ,int yy) /找出maze中從入口(x

14、,y)到出口(xx,yy)的一切途徑 int x,y,x1,y1,v; SQSTACK s; /存放探求途徑的棧 elemtype e; InitSqstack(&s,MAXSIZE); /初始化棧初始化棧將入口位置信息(x,y,0)入棧v0) /這次出棧是回退操作，去除原探求位置的已走標(biāo)志 mazey+moveye.vx+movexe.v=0; while(v=4) /*按照順時(shí)針順序探求4個(gè)方向*/ x1=x+movexv; y1=y+moveyv; /獲取當(dāng)前位置(x,y)v方向的相鄰位置坐標(biāo)(x1,y1) if (x1=xx&y1=yy) /遇到出口 輸出存放在s中的途

15、徑 /*這條指令不是C語(yǔ)句*/ V+; /換一個(gè)方向繼續(xù)探求 while(v0&x10&y1elem=(elemtype q-elem=(elemtype * *)malloc(n+1)malloc(n+1)* *sizeof(elemtype);sizeof(elemtype);p if(q-elem=NULL)return 0; / if(q-elem=NULL)return 0; /操作失敗操作失敗p q-front=q-rear=0; /q-front=q-rear=0; /隊(duì)首指針、隊(duì)尾指針都?xì)w零隊(duì)首指針、隊(duì)尾指針都?xì)w零p q-size=n+1; /q-size=n+

16、1; /設(shè)置容量設(shè)置容量p return 1; return 1; 中國(guó)科大數(shù)據(jù)結(jié)構(gòu)3.3 隊(duì)列p銷(xiāo)毀隊(duì)列銷(xiāo)毀隊(duì)列pvoid DestroySqqueue(SQQUEUE *q)p /銷(xiāo)毀隊(duì)列銷(xiāo)毀隊(duì)列p free(q-elem); /釋放隊(duì)列所占內(nèi)存釋放隊(duì)列所占內(nèi)存p q-elem=NULL; /將其他成員設(shè)置成平安值將其他成員設(shè)置成平安值p q-front=q-rear=0;p q-size=0;p p判別隊(duì)空判別隊(duì)空pint IsSqqueueEmpty(SQQUEUE q)p /假設(shè)隊(duì)空，那么前往假設(shè)隊(duì)空，那么前往1，否那么前往，否那么前往0p return q.front=q.rear

17、;p 中國(guó)科大數(shù)據(jù)結(jié)構(gòu)3.3 隊(duì)列p入隊(duì)入隊(duì)pint EnSqqueue(SQQUEUE *q, elemtype e)p /將數(shù)據(jù)元素將數(shù)據(jù)元素e入隊(duì)，操作勝利前往入隊(duì)，操作勝利前往1，否那么前往，否那么前往0p if(IsSqqueueFull(*q)return 0;p q-elemq-rear=e; /將將e放置在隊(duì)列中放置在隊(duì)列中p q-rear=(q-rear+1)%q-size; /隊(duì)尾指針向后挪動(dòng)隊(duì)尾指針向后挪動(dòng)p return 1;p p判別隊(duì)滿(mǎn)判別隊(duì)滿(mǎn)pint IsSqqueueFull(SQQUEUE q)p /假設(shè)隊(duì)滿(mǎn)，那么前往假設(shè)隊(duì)滿(mǎn)，那么前往1，否那么前往，否那么前

18、往0p return q.front=(q.rear+1)%q.size;p 中國(guó)科大數(shù)據(jù)結(jié)構(gòu)3.3 隊(duì)列p出隊(duì)出隊(duì)pint DeSqqueue(SQQUEUE *q, elemtype *e)p /將隊(duì)首元素復(fù)制給將隊(duì)首元素復(fù)制給*e,操作勝利前往操作勝利前往1，否那么前往，否那么前往0p if(IsSqqueueEmpty(*q)return 0; /假設(shè)隊(duì)空，操作失敗假設(shè)隊(duì)空，操作失敗p *e=q-elemq-front; /復(fù)制隊(duì)首元素復(fù)制隊(duì)首元素p q-front=(q-front+1)%q-size; /隊(duì)首指針向后挪動(dòng)隊(duì)首指針向后挪動(dòng)p return 1;p p獲得隊(duì)列長(zhǎng)度獲得隊(duì)

19、列長(zhǎng)度pint SqqueueLen(SQQUEUE q)p /前往隊(duì)列長(zhǎng)度前往隊(duì)列長(zhǎng)度p return (q.size+q.rear-q.front)%q.size; p中國(guó)科大數(shù)據(jù)結(jié)構(gòu)3.3 隊(duì)列3.3.3 鏈?zhǔn)疥?duì)列鏈?zhǔn)疥?duì)列數(shù)據(jù)類(lèi)型定義：數(shù)據(jù)類(lèi)型定義：typedef struct node_tag elemtype data; struct node_tag *next; NODE, *NODEPTR; /*定義單鏈表結(jié)點(diǎn)和指針類(lèi)型定義單鏈表結(jié)點(diǎn)和指針類(lèi)型*/typedef struct NODEPTR front,rear;/*隊(duì)首隊(duì)尾指針隊(duì)首隊(duì)尾指針*/ LKQUEUE;根本操作：根本

20、操作：1初始化空隊(duì)初始化空隊(duì)void InitLkqueue(LKQUEUE *Q) Q-front=Q-rear=NULL; 中國(guó)科大數(shù)據(jù)結(jié)構(gòu)3.3 隊(duì)列p銷(xiāo)毀隊(duì)列銷(xiāo)毀隊(duì)列pvoid DestroyLkqueue(LKQUEUE *Q)p NODEPTR p;p while(Q-front!=NULL)p p=Q-front;p Q-front=p-next; /*摘除隊(duì)首結(jié)點(diǎn)摘除隊(duì)首結(jié)點(diǎn)*/p free(p);p p Q-rear=NULL;p 中國(guó)科大數(shù)據(jù)結(jié)構(gòu)3.3 隊(duì)列p入隊(duì)入隊(duì)pint EnLkqueue(LKQUEUE int EnLkqueue(LKQUEUE * *Q,elem

21、type e)Q,elemtype e)p NODEPTR p; NODEPTR p;p p=(NODEPTR)malloc(sizeof(NODE); p=(NODEPTR)malloc(sizeof(NODE);p if(p=NULL)return 0; if(p=NULL)return 0;p p-data=e; p-data=e;p p-next=NULL; p-next=NULL;p if(Q-front=NULL) / if(Q-front=NULL) /假設(shè)隊(duì)空，那么將隊(duì)首隊(duì)尾指針都指向結(jié)點(diǎn)假設(shè)隊(duì)空，那么將隊(duì)首隊(duì)尾指針都指向結(jié)點(diǎn)p pp Q-front=Q-rear=p; Q-f

22、ront=Q-rear=p;p else elsep / /否那么將結(jié)點(diǎn)否那么將結(jié)點(diǎn)p p插入到隊(duì)尾結(jié)點(diǎn)后面插入到隊(duì)尾結(jié)點(diǎn)后面p Q-rear-next=p;Q-rear-next=p;p Q-rear=p; Q-rear=p;p p return 1; return 1;p 中國(guó)科大數(shù)據(jù)結(jié)構(gòu)3.3 隊(duì)列p出隊(duì)出隊(duì)pint DeLkqueue(LKQUEUE *Q,elemtype *e)p NODEPTR p;p if(Q-front=NULL)return 0;p p=Q-front;p Q-front=p-next;p if(Q-front=NULL)Q-rear=NULL; /假設(shè)隊(duì)空

23、，那么將隊(duì)尾指針置假設(shè)隊(duì)空，那么將隊(duì)尾指針置NULLp *e=p-data;p free(p);p return 1;p 中國(guó)科大數(shù)據(jù)結(jié)構(gòu)3.3 隊(duì)列p隊(duì)列的運(yùn)用舉例隊(duì)列的運(yùn)用舉例p【舉例【舉例1 1】汽車(chē)加油站?！科?chē)加油站。p 隨著城市里汽車(chē)數(shù)量的急速增長(zhǎng)，汽車(chē)加油站也漸隨著城市里汽車(chē)數(shù)量的急速增長(zhǎng)，汽車(chē)加油站也漸漸多了起來(lái)。通常汽車(chē)加油站的構(gòu)造根本上是：入口和出口為單行漸多了起來(lái)。通常汽車(chē)加油站的構(gòu)造根本上是：入口和出口為單行道，加油車(chē)道能夠有假設(shè)干條。每輛車(chē)加油都要經(jīng)過(guò)三段路程，第道，加油車(chē)道能夠有假設(shè)干條。每輛車(chē)加油都要經(jīng)過(guò)三段路程，第一段是在入口處排隊(duì)等候進(jìn)入加油車(chē)道；第二段是在加

24、油車(chē)道排隊(duì)一段是在入口處排隊(duì)等候進(jìn)入加油車(chē)道；第二段是在加油車(chē)道排隊(duì)等候加油；第三段是進(jìn)入出口處排隊(duì)等候分開(kāi)。實(shí)踐上，這三段都等候加油；第三段是進(jìn)入出口處排隊(duì)等候分開(kāi)。實(shí)踐上，這三段都是隊(duì)列構(gòu)造。假設(shè)用算法模擬這個(gè)過(guò)程，就需求設(shè)置加油車(chē)道數(shù)加是隊(duì)列構(gòu)造。假設(shè)用算法模擬這個(gè)過(guò)程，就需求設(shè)置加油車(chē)道數(shù)加2 2個(gè)隊(duì)列。個(gè)隊(duì)列。中國(guó)科大數(shù)據(jù)結(jié)構(gòu)3.3 隊(duì)列n【舉例【舉例2 2】模擬打印機(jī)緩沖區(qū)?！磕M打印機(jī)緩沖區(qū)。n 在主機(jī)將數(shù)據(jù)輸出到打印機(jī)時(shí)，會(huì)出現(xiàn)主機(jī)速度在主機(jī)將數(shù)據(jù)輸出到打印機(jī)時(shí)，會(huì)出現(xiàn)主機(jī)速度與打印機(jī)的打印速度不匹配的問(wèn)題。這時(shí)主機(jī)就要停下來(lái)等待與打印機(jī)的打印速度不匹配的問(wèn)題。這時(shí)主機(jī)就要停下來(lái)等待打印機(jī)。顯然，這樣會(huì)降低主機(jī)的運(yùn)用效率。為此人們想象了打印機(jī)