數(shù)據(jù)結(jié)構(gòu)第三章棧和隊(duì)列.ppt

1、第三章 棧和隊(duì)列,第三章 棧和隊(duì)列,本章介紹在程序設(shè)計(jì)中常用的兩種數(shù)據(jù)結(jié)構(gòu) 棧和隊(duì)列,第三章 棧和隊(duì)列 3.1 棧 3.2 棧的應(yīng)用舉例 3.4 隊(duì)列,3.1 棧 3.1 .1 棧的概念 3.1 .2 棧的順序存儲(chǔ)和實(shí)現(xiàn) 3.1 .3 棧的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn),3.1 棧,棧是限定僅能在表尾一端進(jìn)行插入、刪除操作的線性表,（a1, a2, . , ai -1, ai , ai+1, , an ）,3.1.1 棧的概念 一 什么是棧,3.1 棧,棧的示意圖,出棧,進(jìn)棧,棧的特點(diǎn) 后進(jìn)先出,第一個(gè)進(jìn)棧的元素在棧底，最后一個(gè)進(jìn)棧的元素在棧頂， 第一個(gè)出棧的元素為棧頂元素， 最后一個(gè)出棧的元素為棧底元素,3

2、.1 棧,二 棧的基本操作 1）構(gòu)造一個(gè)空棧S； 2） 進(jìn)棧操作Push3）出棧操作Pop4) 取棧頂元素top,3.1 棧,top,base,base,A,A,棧操作圖示,空棧,A進(jìn)棧,B C D E 進(jìn)棧,E D C 出棧,3.1 棧,3.1.2 棧的順序存儲(chǔ)和實(shí)現(xiàn) 一、棧的順序存儲(chǔ)結(jié)構(gòu),1 棧的順序存儲(chǔ)結(jié)構(gòu),#define MAX 50 struct sqstack elemtype stackMAX; int top; ;,3.1 棧,約定棧頂指針指向 棧頂元素的下一個(gè)位置,3. 1 棧,1 ) 進(jìn)棧操作 void Push( int x,struct sqstack *s ) if

3、(s-top=MAX) printf(“ overflow” ); else s-stacks-top=x; s-top+; ,2）出棧操作 int pop( struct sqstack *s )if (s-top=0) printf(“underflow”); return(NULL); s-top-; return s-stacks-top; ,共享?xiàng)?#define MAX 100 Int stackMAX,top1=0,top2=MAX-1;,3.1 棧,2 棧的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn) 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也稱鏈棧，如圖所示：,在前面學(xué)習(xí)了線性鏈表的 插入刪除操作算法， 不難寫出鏈?zhǔn)綏３跏蓟?/p>

4、 進(jìn)棧、出棧等操作的算法,3.1 棧,(1) 進(jìn)棧算法 NODE *top; Void push(int x) NODE *p=(NODE *)malloc(sizeof(NODE); p-data=x; p-next=top; top=p; ,3.1 棧,(2) 出棧算法 NODE *pop( ); NODE *p; if (top=NULL)return(NULL); p=top; top=p-next; return(p); ,小 結(jié) 1 棧是限定僅能在表尾一端進(jìn)行插入、 刪除操作的線性表； 2 棧的元素具有后進(jìn)先出的特點(diǎn)； 3 棧頂元素的位置由一個(gè)稱為棧頂指針的 變量指示， 進(jìn)棧、出棧

5、操作要修改棧頂指針；,3.1 棧,3.2 棧的應(yīng)用舉例,例1 數(shù)制轉(zhuǎn)換 對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制數(shù)，顯示輸出與其等值的八進(jìn)制數(shù),數(shù)制轉(zhuǎn)換方法 N = (Ndiv8)10 8+N mod 8 N：十進(jìn)制數(shù)，div：整除運(yùn)算，mod：求余運(yùn)算； (1348)10 = 283+582+08+4 = (2504)8 N 1348 168 21 2 N div 8 168 21 2 0 N mod 8 4 0 5 2,計(jì)算時(shí)從低位到高位 順序產(chǎn)生八進(jìn)制數(shù)的各個(gè)數(shù)位,結(jié)果： 2 5 0 4,顯示時(shí)按從高位到低位的 順序輸出,3.2 棧的應(yīng)用舉例,void conversion( ) InitStack

6、(s); /建空棧 scanf(“%d”, 算法3.7,3.2 棧的應(yīng)用舉例,例2 表達(dá)式求值 1）問(wèn)題的提出 設(shè)計(jì)一個(gè)小計(jì)算器: 對(duì)鍵入的表達(dá)式進(jìn)行求值。,高級(jí)語(yǔ)言中的賦值語(yǔ)句：變量=表達(dá)式；,2） 表達(dá)式的構(gòu)成 操作數(shù)+運(yùn)算符+界符（如括號(hào)） 3） 表達(dá)式的求值： 例 5+6 (1+2)- 4 按照四則運(yùn)算法則，上述表達(dá)式的計(jì)算過(guò)程為： 5+6 (1+2)- 4=5+6 3- 4 = 5+18-4= 23-4=19,3.2 棧的應(yīng)用舉例,1,2,3,4,4） 算符優(yōu)先關(guān)系表 表達(dá)式中任何相鄰運(yùn)算符c1、c2的優(yōu)先關(guān)系有： c1c2：c1的優(yōu)先級(jí)高于c2,算符間的優(yōu)先關(guān)系表,注： c1 c2

7、是相鄰算符， c1在左， c2在右,3.2 棧的應(yīng)用舉例,5 算符優(yōu)先算法,從左向右掃描表達(dá)式： 遇操作數(shù)保存； 遇運(yùn)算符號(hào)cj與前面的剛掃描過(guò)的運(yùn)算符ci比較 若cicj 則說(shuō)明ci是已掃描的運(yùn)算符中優(yōu)先級(jí)最高者，可進(jìn)行運(yùn)算； 若ci = cj 則ci為（，cj 為 ），說(shuō)明括號(hào)內(nèi)的式子已計(jì)算完，需要消去括號(hào)；,5 + 4 (1 + 2) - 6,后面也許有優(yōu)先級(jí)更高的算符,+,+,(,后保存的算符有優(yōu)先級(jí)高,用兩個(gè)棧分別保存掃描過(guò)程中遇到的操作數(shù)和運(yùn)算符,算法,算符比較算法,Char Precede( char c1, char c2) int c_temp1, c_temp2; swit

8、ch(c1) case * : case / : c_temp1=4; break; case + : case - : c_temp1=2; break; . . . . . . switch(c2) case * : case / : c_temp2=3; break; case + : case - : c_temp2=1; break; . . . . . . ,續(xù),if (c_temp1c_temp2) return( ); ,3.2 棧的應(yīng)用舉例,在算符優(yōu)先算法中，建立了兩個(gè)工作棧。一個(gè)是OPTR棧，用以保存運(yùn)算符,一個(gè)是OPND棧，用以保存操作數(shù)或運(yùn)算結(jié)果。int express

9、 ( ) /運(yùn)算數(shù)棧，OP為運(yùn)算符集合。 InitStack(OPTR); Push (OPTR, # ); InitStack(OPND); w=qetchar( ); While(w!= # | GetTop(OPTR)!=#) if(! In(w,OP)Push(OPND,w);w=getchar(); /不是運(yùn)算符則進(jìn)棧 else / In(w, OP)判斷c是否 是運(yùn)算符的函數(shù),3.2 棧的應(yīng)用舉例,續(xù) switch (Precede(GetTop(OPTR), w) case : /新輸入的算符c優(yōu)先級(jí)低，即棧頂算符優(yōu)先權(quán)高， /出棧并將運(yùn)算結(jié)果入棧OPND op=Pop(OPTR

10、); b=Pop(OPND); a= Pop(OPND); Push(OPND, Operate(a, op, b); break; return GetTop(OPND); ,表達(dá)式求值示意圖：5+6(1+2)-4,#,5,+,6,(,1,+,2,3,18,23,-,4,19,5,讀入表達(dá)式過(guò)程：,+,6,(,1,+,2,),-,4,#,=19,1+2=3,63=18,5+18=23,23-4=19,3.4 隊(duì)列 3.4 .1 隊(duì)列的概念 3.4 .2 循環(huán)隊(duì)列 隊(duì)列的順序存儲(chǔ)和實(shí)現(xiàn) 3.4 .3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn),34 隊(duì)列,3.4.1 隊(duì)列的概念 一 什么是隊(duì)列,隊(duì)列是限定僅能在表頭

11、進(jìn)行刪除，表尾進(jìn)行插入的線性表,（a1, a2, . , ai -1, ai , ai+1, , an ）,插入,刪除,34 隊(duì)列,a1 a2 a3 an,入隊(duì)列,隊(duì)頭,隊(duì)尾,出隊(duì)列,隊(duì) 列 的 示 意 圖,隊(duì)列的特點(diǎn) 先進(jìn)先出,第一個(gè)入隊(duì)的元素在隊(duì)頭，最后一個(gè)入隊(duì)的元素在隊(duì)尾， 第一個(gè)出隊(duì)的元素為隊(duì)頭元素， 最后一個(gè)出隊(duì)的元素為隊(duì)尾元素,34 隊(duì)列,二 隊(duì)列的基本操作 1）初始化操作 2）銷毀操作 3）置空操作 4）判空操作 5）取隊(duì)頭元素操作 6）入隊(duì)操作 7）出隊(duì)操作,(b)J1,J2相繼入隊(duì)列,(c)J1出隊(duì),(d)J3,J4和J5相繼入隊(duì)之后,J2出隊(duì),（a)空隊(duì)列,3. 4 隊(duì)列,

12、front,rear均為整數(shù) 用箭頭指示只是為了直觀,34 隊(duì)列,#define MAX 50 /*數(shù)據(jù)結(jié)構(gòu)定義*/ struct squeue elemtype queueMAX; int front; int rear; 初始化 Init（struct squeue *q) q-front=-1; q-rear=-1; ,int insert_queue(int x，struct squeue *q) /*入隊(duì)列*/ if(*q).rear=MAX-1) return(0); q-rear+; q-queueq-rear=x ;return(1); int del_queue(struct

13、 squeue *q) /*出隊(duì)列*/ if(q-rear=q-front) return(0); q-front+; return(q-queueq-front); ,3. 4 隊(duì)列,3 . 循環(huán)隊(duì)列,(b)隊(duì)空,(c)隊(duì)滿,隊(duì)空、隊(duì)滿 都有front=rear,J6,3. 4 隊(duì)列,有兩種方法：1）另設(shè)一個(gè)標(biāo)志位以區(qū)分隊(duì)空、隊(duì)滿。2）少用一個(gè)存儲(chǔ)單元，隊(duì)滿條件:front=rear+1;,front,（d）,3. 4 隊(duì)列,1）初始化操作 功能：建一個(gè)空隊(duì)列Q； 算法： struct squeue elemtype queueMAX; int front; int rear; ; int

14、InitQueue_Sq(struct squeue *q) /構(gòu)造一個(gè)空隊(duì)列Q q-front=q-rear=0; return (1),二 循環(huán)隊(duì)列的基本操作算法,建一個(gè)空隊(duì)列Q,3. 4 隊(duì)列,6）入隊(duì)操作 功能：將元素 x 插入隊(duì)尾,元素 x 入隊(duì)前,元素 x 入隊(duì)后,3. 4 隊(duì)列,求余運(yùn)算,3.4.2 循環(huán)隊(duì)列隊(duì)列的順序存儲(chǔ)和實(shí)現(xiàn) int insert_queue(int x,struct squeue *q) /*入隊(duì)列*/ if(q-rear+1)%MAX=q-front)return(0); q-rear=(q-rear+1)%MAX; q-queueq-rear=x; re

15、turn(1); ,3. 4 隊(duì)列,7）出隊(duì)操作 功能：刪除隊(duì)頭元素；,3. 4 隊(duì)列,int del_queue(struct squeue *q) /*出隊(duì)列*/ if(q-rear=q-front) return(0); q-front=(q-front+1)%MAX; return(q-queueq-front);,3.4.3 鏈隊(duì)列隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和實(shí)現(xiàn) 一 鏈隊(duì)列,front,rear,空鏈隊(duì)列,front,rear,鏈隊(duì)列圖示,3. 4 隊(duì)列,3. 4 隊(duì)列,二 鏈隊(duì)列的類型定義,struct node /鏈隊(duì)列結(jié)點(diǎn)的類型定義int data; struct node *nex

16、t; ;typedef struct node NODE NODE *front, *rear;,3. 4 隊(duì)列 入列運(yùn)算,Void addqlink(int x) NODE *p; p=(NODE *)malloc(sizeof(NODE); p-data=x; p-next=NULL; rear-next=p; rear=p; ,3. 4 隊(duì)列 出列運(yùn)算,NODE *deleqlink( ) NODE *p; if (front=rear) return(NULL); p=front-next; front-next=p-next; if (front-next=NULL) rear=front; return(p