嚴(yán)蔚敏版數(shù)據(jù)結(jié)構(gòu)第三章.

《嚴(yán)蔚敏版數(shù)據(jù)結(jié)構(gòu)第三章.》由會(huì)員分享，可在線閱讀，更多相關(guān)《嚴(yán)蔚敏版數(shù)據(jù)結(jié)構(gòu)第三章.（62頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,,?#?,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),,,*,1,數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容,,,,,,,2,3.1,棧（,Stack,）,,第三章 棧和隊(duì)列,3.2,隊(duì)列,（,Queue,）,1.,定義,2.,邏輯結(jié)構(gòu),3.,存儲(chǔ)結(jié)構(gòu),4.,運(yùn)算規(guī)則,5.,實(shí)現(xiàn)方式,1.,定義,2.,邏輯結(jié)構(gòu),3.,存儲(chǔ)結(jié)構(gòu),

2、4.,運(yùn)算規(guī)則,5.,實(shí)現(xiàn)方式,,3,1.,定義,3.1,棧,與同線性表相同，仍為一對(duì)一關(guān)系。,用順序?；蜴湕４鎯?chǔ)均可，但以順序棧更常見(jiàn),只能在棧頂運(yùn)算，且訪問(wèn)結(jié)點(diǎn)時(shí)依照后進(jìn)先出（,LIFO,）或先進(jìn)后出（,FILO,）的原則。,關(guān)鍵是編寫(xiě)入棧和出棧函數(shù)，具體實(shí)現(xiàn)依順序?；蜴湕５牟煌煌?。,基本操作有入棧、出棧、讀棧頂元素值、建棧、或判斷棧滿、?？盏?。,3.,存儲(chǔ)結(jié)構(gòu),4.,運(yùn)算規(guī)則,5.,實(shí)現(xiàn)方式,,2.,邏輯結(jié)構(gòu),限定只能在表的一端進(jìn)行插入和刪除運(yùn)算的線性表（只能在棧頂操作）,,4,問(wèn)：堆棧是什么？它與一般線性表有什么不同？,3.1,棧,答：,堆棧是一種特殊的線性表，它只能在表的一端（即

3、棧頂）進(jìn)行插入和刪除運(yùn)算。,與一般線性表的區(qū)別：僅在于運(yùn)算規(guī)則不同。,一般線性表 堆棧,邏輯結(jié)構(gòu)：一對(duì)一 邏輯結(jié)構(gòu)：一對(duì)一,存儲(chǔ)結(jié)構(gòu)：順序表、鏈表 存儲(chǔ)結(jié)構(gòu)：順序棧、鏈棧,運(yùn)算規(guī)則：隨機(jī)存取 運(yùn)算規(guī)則：后進(jìn)先出,(LIFO),,“,進(jìn)” ＝壓入,=PUSH,（,x),“,出” ＝彈出,=POP ( y ),5,棧 是僅在,表尾,進(jìn)行插入、刪除操作的線性表。,表尾,(,即,a,n,端,),稱為,棧頂,,top ;,表頭,(

4、,即,a,1,端,),稱為,棧底,base,例如： 棧,s= (a,1,, a,2 ,,a,3 , ……….,,a,n-1 ,,a,n,),,a,1,稱為 棧底元素,,a,n,,稱為 棧頂元素,插入元素到,棧頂,（即表尾）的操作，稱為,入棧,。,從,棧頂,（即表尾）刪除最后一個(gè)元素的操作，稱為,出棧。,教材,P44,對(duì),棧,有更詳細(xì)定義：,強(qiáng)調(diào)：,插入和刪除都只能在表的一端（棧頂）進(jìn)行！,,6,棧的表示和實(shí)現(xiàn),順序棧：棧的順序存儲(chǔ)結(jié)構(gòu)，利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，指針,top,指向棧頂元素在順序棧中的下一個(gè)位置，,,base,為棧底指針，指向棧底的位置。,

5、base,空棧,a,進(jìn)棧,b,進(jìn)棧,,,,a,a,b,top,base,top,base,top,順序棧示意圖,s,,,a,1,a,2,a,3,data,,,(,棧底,),(,棧頂,),99,.,.,.,3,2,1,0,top,,,,,8,順序棧的類型表示,:,#define STACK_INIT_SIZE 100,；,#define STACKINCREMENT 10,；,,typedef char StackData;,,typedef struct {,//,順序棧定義,,StackData *base;,//,棧底指針,,,StackData *top;,//,棧頂指針,,,int

6、 stacksize,；,//,當(dāng)前已分配的存儲(chǔ)空間,} SeqStack,；,9,判棧空,int StackEmpty (SeqStack *S) {,if( S->top == S->base ) return 1 //,空則返回,1,else return 0; //,否則返回,0,},判棧滿,int StackFull (SeqStack *S) {,if( S->top- S->base >= S-> StackSize )  return 1,//,判棧滿,,,滿則返回,1,else return 0;,//,否則返回,0,},順序棧的基本運(yùn)算,:,,10,初始化,voi

7、d InitStack ( SeqStack *S) {,//,置空棧,S,->base,=( StackData *)malloc(STACK_INIT_SIZE * sizeof(StackData));if (!S->base) exit(OVERFLOW);,S,->,top = S,->base,;,S,->stacksize= S,TACK_INIT_SIZE ;,Return ok;,},11,a,1,a,2,……,a,n,順序棧,S,a,i,……,,表和棧的操作區(qū)別,——,對(duì)線性表,,s= (a,1,, a,2 , …. ,,a,n-1 ,,a,n,),表頭,表尾,棧

8、底,base,棧頂,top,低地址,高地址,寫(xiě)入：,v[i]=,a,i,讀出：,x= v[i],壓入：,PUSH (an+1),彈出：,POP (x),前提：一定要預(yù)設(shè)棧頂指針,top,！,低地址,高地址,v[i],a,1,a,2,a,i,a,n,……,順序表,V[n],……,,a,n+1,12,入棧操作,——,例如用堆棧存放（,A,，,B,，,C,，,D,）,,（注意要遵循,“,后進(jìn)先出,”,原則）,A,,,,,,A,,,C,B,A,,,,B,A,top,核心語(yǔ)句：,top,=L;,,順序棧中的,PUSH,函數(shù),status Push(ElemType x),{ if(top>M){,上溢

9、,},else v[,top++,]=x;,},Push (B);,Push (C);,Push (D);,,,top,top,top,top,低地址,L,Push (A);,高地址,M,B,C,D,13,入棧,int Push (SeqStack *S, StackData x) {,//,插入元素,x,為新的棧頂元素,,,if ( StackFull (S) ){,S->base =( StackData *)malloc(S->base ,,(S->stacksize+ STACKINCREMENT) * sizeof(StackData));,if(! S->base)exit(

10、overflow);,S->top= S->base + S->stacksize;,S->stacksize+= STACKINCREMENT;,//,追加存儲(chǔ)空間,},*(S->top)=x;,,（,S->top,）,++;,Return ok,},14,,出棧操作,——,例如從棧中取出,‘,B,’,,,（注意要遵循,“,后進(jìn)先出,”,原則）,D,C,B,A,,top,top,,D,C,,A,B,,D,C,B,A,top,,,D,C,B,A,top,低地址,L,高地址,M,D,核心語(yǔ)句：,Pop ( );,Pop ( );,Printf(,Pop (),);,,順序棧中的,POP,函數(shù),s

11、tatus Pop( ),{ if(top=L) {,下溢,},else { y=v[,--top,]; return(y);},},,15,出棧,,int pop (SeqStack *S, StackData &x) {,//,若?？辗祷?,,,否則棧頂元素退出到,x,并返回,1,,if ( StackEmpty(S) ) return 0;,--(S->top);,x = *(S->top);,return 1;,},16,例,1,：,一個(gè)棧的輸入序列是,12345,，若在入棧的過(guò)程中允許出棧,，,則棧的輸出序列,43512,可能實(shí)現(xiàn)嗎？,12345,的輸出呢？,43512,不可

12、能實(shí)現(xiàn)，主要是其中的,12,順序不能實(shí)現(xiàn)；,,12345,的輸出可以實(shí)現(xiàn)，只需壓入一個(gè)立即彈出一個(gè)即可。,,,435612,中到了,12,順序不能實(shí)現(xiàn)；,,135426,可以實(shí)現(xiàn)。,例,2,：,如果一個(gè)棧的輸入序列為,123456,，能否得到,435612,和,135426,的出棧序列？,,答：,答：,17,例,3,（嚴(yán)題集,3.1,）,一個(gè)棧的輸入序列為,123,，若在入棧的過(guò)程中允許出棧，則可能得到的出棧序列是什么？,答：,可以通過(guò)窮舉所有可能性來(lái)求解：,①,1,入,1,出，,2,入,2,出，,3,入,3,出， 即,123,；,②,1,入,1,出，,2,、,3,入,3,、,2,出， 即

13、,132,；,③,1,、,2,入，,2,出，,3,入,3,出， 即,231,；,④,1,、,2,入，,2,、,1,出，,3,入,3,出， 即,213,；,⑤,1,、,2,、,3,入，,3,、,2,、,1,出， 即,321,；,合計(jì)有,5,種可能性。,,18,例,4,：,計(jì)算機(jī)系,2001,年考研題（程序設(shè)計(jì)基礎(chǔ)）,設(shè)依次進(jìn)入一個(gè)棧的元素序列為,c,，,a,，,b,，,d,，,則可得到出棧的元素序列是：,,Ａ）,a,，,b,，,c,，,d,Ｂ）,c,，,d,，,a,，,b,Ｃ）,b,，,c,，,d,，,a,Ｄ）,a,，,c,，,d,，,b,A,、,D,可以,（,B,、,C,不行）。

14、,討論：有無(wú)通用的判別原則？,有。在可能的輸出序列中，不存在這樣的輸入序列,i,，,j,，,k,，能同時(shí)滿足,i

15、acksize;,20,補(bǔ)充,3,：鏈棧 鏈棧示意圖,s,,,,(,棧底,),(,棧頂,),top,,,,,a3,a2,a4,a1,^,21,,鏈棧的入棧函數(shù)、出棧函數(shù),（以頭指針為棧頂，在頭指針處插入或刪除?。?公共說(shuō)明部分：,,typedef struct snode{,SElemType data;,struct snode *link;,},NODE,;,NODE,*st(,棧頂指針,), *p(,新節(jié)點(diǎn),);,int m=sizeof(NODE);,,22,Push (SElemType x),{ p=(NODE*)malloc(m

16、);,if(!p){,上溢,},else{ p->data=x; p->link=st; st=p;},},,S,tatus,pop( ),,{ if(st==NULL){,下溢,},else{y=st->data;p=st;st=st->link;,free(p); return(y);},},,鏈棧,入棧函數(shù),鏈棧,出棧函數(shù),插入表頭,從表頭刪除,23,說(shuō) 明,,鏈?zhǔn)綏o(wú)棧滿問(wèn)題，空間可擴(kuò)充,插入與刪除僅在棧頂處執(zhí)行,鏈?zhǔn)綏５臈ｍ斣阪滎^,適合于多棧操作,24,,數(shù)制轉(zhuǎn)換（十轉(zhuǎn),N,）,——P48,,設(shè)計(jì)思路：用棧暫存低位值,,例,2,：括號(hào)匹配的檢驗(yàn),————P49,,設(shè)計(jì)思路：用棧暫

17、存左括號(hào),,例,3,,：,表達(dá)式求值,—-————P52,,設(shè)計(jì)思路：用棧暫存運(yùn)算符,,,例,1,：,棧的應(yīng)用舉例,25,1.,數(shù)制轉(zhuǎn)換,,N = (N div d)×d + N mod d,,例如：（,1348),10,= (2504),8,,，其運(yùn)算過(guò)程如下：,,,N N div 8 N mod 8,,1348 168 4 168 21 0 21 2 5 2 0 2,輸出順序,計(jì)算順序,26,void conversion () {,InitS

18、tack(S);,scanf ("%d",N);,while (N) {,Push(S, N % 8);,N = N/8;,},while (!StackEmpty(S)) {,Pop(S,e);,printf ( "%d", e );,},} // conversion,27,2.,行編輯程序,在用戶輸入一行的過(guò)程中，允許用戶輸入出差錯(cuò)，并在發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正。,設(shè)立一個(gè)輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū),;,并假設(shè)“,#”,為退格符，“,@”,為退行符。,假設(shè)從終端接受兩行字符：,,whli##ilr#e,（,s#*s),outcha@putchar(*s=

19、#++);,實(shí)際有效行為：,,while (*s),putchar(*s++);,28,Void LineEdit(){,InitStack(s);,ch=getchar();,while (ch != EOF) {,//EOF,為全文結(jié)束符,,while (ch != EOF && ch != '\n'),,{,switch (ch),{,case '#' : Pop(S, c); break;,case '@': ClearStack(S); break;,,//,重置,S,為空棧,,default : Push(S, ch); break;,},ch = getchar();,//,從

20、終端接收下一個(gè)字符,,},29,將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過(guò)程的數(shù)據(jù)區(qū),；,ClearStack(S);,//,重置,S,為空棧,if (ch != EOF) ch = getchar();,},DestroyStack(s);,},30,例,3,,表達(dá)式求值,(,這是棧應(yīng)用的典型例子,),,這里，,表達(dá)式求值的算法是,“,算符優(yōu)先法,”,。,例如：,3*,（,7 – 2,）,（,1,）要正確求值，首先了解算術(shù)四則運(yùn)算的規(guī)則：,,a.,,從左算到右,,b.,,先乘除，后加減,,c.,,先括號(hào)內(nèi)，后括號(hào)外,例：,4+2*3-10/5=4+6-10/5=10-10/5=10-2=8,,由此，

21、此表達(dá)式的計(jì)算順序?yàn)椋?,3*,（,7 – 2,）,= 3 * 5 = 15,,31,（,2,）根據(jù)上述三條運(yùn)算規(guī)則，在運(yùn)算的每一步中，對(duì)任意相繼出現(xiàn)的算符,?,1,和,?,2,,，都要比較優(yōu)先權(quán)關(guān)系。,算符優(yōu)先法所依據(jù)的算符間的優(yōu)先關(guān)系,見(jiàn)教材,P53,表,3.1,,（是提供給計(jì)算機(jī)用的表?。?由表可看出，右括號(hào),),,和井號(hào),,#,,作為,?,2,時(shí),級(jí)別最低；,,由,c,規(guī)則,得出： * ，,/,，,+,，,-,為,?,1,時(shí)的優(yōu)先權(quán)低于‘（’，高于‘）’,由,a,規(guī)則,得出：‘,（,’,=‘,）,’ 表明括號(hào)內(nèi)運(yùn)算，已算完。,‘,#,’=‘,#,’,表明表達(dá)式求值完畢。,棧的應(yīng)用（表

22、達(dá)式求值）,,32,（,3,）算法思想：,設(shè)定兩棧：,操作符棧,OPTR,，操作數(shù)棧,OPND,棧初始化,：設(shè)操作數(shù)棧,OPND,為空；操作符棧,OPTR,的棧底元素為表達(dá)式起始符 ‘,#’,；,依次讀入字符,：是操作數(shù)則入,OPND,棧，是操作符則要判斷：,,if,,操作符,<,棧頂元素,，則退棧、計(jì)算，結(jié)果壓入,OPND,棧；,,操作符,=,棧頂元素且不為‘,#’,，脫括號(hào)（彈出左括號(hào)）；,,操作符,>,棧頂元素,，壓入,OPTR,棧。,棧的應(yīng)用（表達(dá)式求值）,,33,棧的應(yīng)用（表達(dá)式求值）,OPTR,OPND,INPUT,OPERATE,3*(7-2)#,Push(opnd,’3’),,

23、#,*(7-2)#,3,#,Push(optr,’*’),#,*,3,(7-2)#,Push(optr,’(’),#,*,(,3,7-2)#,Push(opnd,’7’),#,*,(,3,7,-2)#,Push(optr,’-’),#,*,(,,－,3,7,2)#,Push(opnd,’2’),#,*,(,,－,3,7,2,),#,Operate(7-2),#,*,(,3,5,)#,Pop(optr),#,*,3,5,#,Operate(3*5),#,15,#,GetTop(opnd),,34,Status EvaluateExpression( OperandType &result

24、) {,InitStack(OPND); InitStack(OPTR);Push(OPTR ,’#’);c=getchar();,while((c!=‘#’)//(GetTop(OPTR)!=‘#’)),{ if (!In(c,OP) { Push(OPND,c); c=getchar();},else switch(,compare(c,GetTop(OPTR),)),{case ‘>’ : Push(OPTR , c); c=getchar();break;,case ‘=’: Pop(OPTR);c=getchar();break;,,case ‘<’

25、: temat=Pop(OPTR); b=Pop();a=Pop();,,result= Operate(a,temat,b);Push(OPND,result);,c=getchar();break;,} //switch }//while,result=GetTop(OPND);}//EvaluateExpression,,此函數(shù)在哪里？,35,,定 義,3.2,隊(duì)列,與線性表相同，仍為一對(duì)一關(guān)系。,順序隊(duì),或,鏈隊(duì),，以循環(huán)順序隊(duì)更常見(jiàn)。,只能在隊(duì)首和隊(duì)尾運(yùn)算，且訪問(wèn)結(jié)點(diǎn)時(shí)依照,先進(jìn)先出,（,FIFO,）,的原則。,關(guān)鍵是掌握,入隊(duì),和,出隊(duì),操作，具體實(shí)現(xiàn)依順序隊(duì)或鏈隊(duì)的不同而

26、不同。,基本操作有入隊(duì)或出隊(duì)，建空隊(duì)列，判隊(duì)空或隊(duì)滿等操作。,3.,存儲(chǔ)結(jié)構(gòu),4.,運(yùn)算規(guī)則,5.,實(shí)現(xiàn)方式,,2.,邏輯結(jié)構(gòu),只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表 （,頭刪尾插,）,,36,隊(duì)列 （,Queue,）,是僅在,表尾,進(jìn)行插入操作，在,表頭,進(jìn)行刪除操作的線性表。,表尾即,a,n,端，稱為,隊(duì)尾,,； 表頭即,a,1,端，稱為,隊(duì)頭,。,它是一種先進(jìn)先出（,ＦＩＦＯ,）的線性表。,例如：隊(duì)列,Q= (a,1,, a,2 ,,a,3 , ……….,,a,n-1 ,,a,n,),插入元素稱為,入隊(duì),；刪除元素稱為,出隊(duì),。,隊(duì)頭,隊(duì)尾,教材,P59,對(duì)

27、隊(duì)列有更詳細(xì)定義：,,隊(duì)列的抽象數(shù)據(jù)類型定義見(jiàn)教材Ｐ,59,－,60,隊(duì)列的存儲(chǔ)結(jié)構(gòu)為,鏈隊(duì),或,順序隊(duì),,（常用循環(huán)順序隊(duì)）,37,鏈隊(duì)列示意圖,,討論：,空隊(duì)列的特征？,Q,,(,隊(duì)尾,),(,隊(duì)首,),front,,,,,a1,a2,,a3,^,rear,,,p,front,,,,^,rear,,,③,怎樣實(shí)現(xiàn)入隊(duì)和出隊(duì)操作？,入隊(duì)（尾部插入）：,rear->next=S; rear=S;,出隊(duì)（頭部刪除）：,front->next=p->next;,,②,隊(duì)列會(huì)滿嗎？,front=rear,一般不會(huì)，因?yàn)閯h除時(shí)有,free,動(dòng)作。除非內(nèi)存不足！,38,,,front,rear,x,^,

28、元素,x,入隊(duì),,front,,,rear,x,,y,^,元素,y,入隊(duì),,front,,,rear,x,^,^,y,元素,x,出隊(duì),,front,rear,^,空隊(duì)列,^,39,鏈?zhǔn)疥?duì)列的定義,,typedef int QueueData;,,typedef struct node {,QueueData data; //,隊(duì)列結(jié)點(diǎn)數(shù)據(jù),,struct node *link; //,結(jié)點(diǎn)鏈指針,} QueueNode;,,typedef struct {,QueueNode *rear, *front;,} LinkQueue;,40,基本操作,Sta

29、tus InitQueue(LinkQueue &Q),{,//,構(gòu)造一個(gè)空隊(duì)列,Q,if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)))),exit(OVERFLOW);,Q.front->next=NULL;,return OK;,},41,Status QueueEmpty(LinkQueue Q),{ //,若,Q,為空隊(duì)列,,,則返回,TRUE,,否則返回,FALSE,if(Q.front==Q.rear),return TRUE;,else,return FALSE;,},42,int QueueLength(LinkQueue

30、Q),{,//,求隊(duì)列的長(zhǎng)度,,int i=0;,QueuePtr p;,p=Q.front;,while(Q.rear!=p),{,i++;,p=p->next;,},return i;,},43,Status EnQueue(LinkQueue &Q,QElemType e),{,//,插入元素,e,為,Q,的新的隊(duì)尾元素,,QueuePtr p;,if(!(p=(QueuePtr)malloc(sizeof(QNode)))),//,存儲(chǔ)分配失敗,,exit(OVERFLOW);,p->data=e;,p->next=NULL;,Q.rear->next=p;,Q.rear=p;,ret

31、urn OK;,},44,Status DeQueue(LinkQueue &Q,QElemType &e),{,//,若隊(duì)列不空,,,刪除,Q,的隊(duì)頭元素,,,用,e,返回其值,,,并返回,OK,,否則返回,ERROR,QueuePtr p;,if(Q.front==Q.rear),return ERROR;,p=Q.front->next;,e=p->data;,Q.front->next=p->next;,if(Q.rear==p),Q.rear=Q.front;,free(p);,return OK;,},45,順序隊(duì)示意圖,Q,,,(,隊(duì)尾,),(,隊(duì)首,),,front,,,,a,

32、1,a,2,a,3,data,a,4,,0,.,.,.,.,.,.,.,99,rear,,,②,隊(duì)列會(huì)滿嗎？,很可能會(huì)，因?yàn)閿?shù)組前端空間無(wú)法釋放。因此數(shù)組應(yīng)當(dāng)有長(zhǎng)度限制。,①,空隊(duì)列的特征？,約定：,front=rear,隊(duì)尾后地址,入隊(duì),(,尾部插入,),：,v[rear]=e; rear++;,出隊(duì),(,頭部刪除,),：,x=v[front]; front++;,討論：,假溢出,,有缺陷,③,怎樣實(shí)現(xiàn)入隊(duì)和出隊(duì)操作？,3.2,隊(duì)列,46,問(wèn)：什么叫“假溢出” ？如何解決？,答：,在順序隊(duì)中，當(dāng)尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊(duì)操作，但其實(shí)數(shù)組中還有空位置，這就叫,“,假溢出,”,。

33、,3.2,隊(duì)列,,解決假溢出的途徑,———,采用循環(huán)隊(duì)列,47,,a3,a2,a1,,,0,1,2,3,N-1,rear,front,循環(huán)隊(duì)列（臆造）,順序隊(duì)列,,,a3,a2,a1,,,front,rear,0,1,2,3,.,.,N-1,新問(wèn)題：,在循環(huán)隊(duì)列中，空隊(duì)特征是,front=rear,；,隊(duì)滿時(shí)也會(huì)有,front=rear,；,判決條件將出現(xiàn)二義性！,解決方案有三：,① 加設(shè)標(biāo)志位，讓刪除動(dòng)作使其為,1,,插入動(dòng)作使其為,0,,則可識(shí)別當(dāng)前,front=rear,②,使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)（即隊(duì)列長(zhǎng)度）；,③ 人為浪費(fèi)一個(gè)單元，令,隊(duì)滿特征為,front=(rear+1

34、)%N,；,,48,隊(duì)空條件,:,front = rear,(,初始化時(shí)：,front = rear ),隊(duì)滿條件,：,front = (rear+1) % N,(N=maxsize),隊(duì)列長(zhǎng)度：,L=,（,N,＋,rear,－,front,）,% N,,J2 J3,J1 J4,,J5,front,rear,,選用,空閑單元法：,即,front,和,rear,之一指向?qū)嵲?，另一指向空閑元素。,,問(wèn),2,：,在具有,n,個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有多少個(gè)元素？,n-1,個(gè),5,,,問(wèn),1,：左圖中隊(duì)列長(zhǎng)度,L=,？,,49

35、,J6 J5,J7,J8 J9,例,1,：,一循環(huán)隊(duì)列如下圖所示，若先刪除,4,個(gè)元素，接著再插入,4,個(gè)元素，請(qǐng)問(wèn)隊(duì)頭和隊(duì)尾指針?lè)謩e指向哪個(gè)位置,?,J2 J3,J1 J4,,J5,front,rear,解：,由圖可知，隊(duì)頭和隊(duì)尾指針的初態(tài)分別為,front=1,和,rear=6,。,front,rear,,刪除,4,個(gè)元素后,front=5,；再插入,4,個(gè)元素后，,r=(6+4),%,6=4,front,front,front,front,front,50,例,2,：,數(shù)組Ｑ,[n],用來(lái)

36、表示一個(gè)循環(huán)隊(duì)列，,f,為當(dāng)前隊(duì)列頭元素的,前一,位置，,r,為隊(duì)尾元素的位置。假定隊(duì)列中元素的個(gè)數(shù)小于,n,，計(jì)算隊(duì)列中元素的公式為,:,（Ａ）,r,－,f,（Ｂ）（,n,＋,f,－,r,）,% n,（Ｃ）,n,＋,r,－,f,（Ｄ） （,n,＋,r,－,f,）,% n,4,種公式哪種合理？,當(dāng),r ≥f,時(shí)（,A,）合理；,當(dāng),r < f,時(shí)（,C,）合理；,分析 ：,,,綜合,2,種情況，以（,D,）的表達(dá)最為合理,例,3,：,在一個(gè)循環(huán)隊(duì)列中，若約定隊(duì)首指針指向隊(duì)首元素的,前一個(gè),位置。那么，從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是 先,,，后,,。,,移動(dòng)隊(duì)首指針,取出元素,√,51,問(wèn)

37、：為什么要設(shè)計(jì)隊(duì)列？它有什么獨(dú)特用途？,離散事件的模擬（模擬事件發(fā)生的先后順序）；,操作系統(tǒng)中多道作業(yè)的處理（一個(gè),CPU,執(zhí)行多個(gè)作業(yè)）；,3.,簡(jiǎn)化程序設(shè)計(jì)。,答：,循環(huán)隊(duì)列的操作實(shí)現(xiàn),見(jiàn)教材,P64,,52,循環(huán)隊(duì)列的操作實(shí)現(xiàn),1,）,初始化一空隊(duì)列,算法要求：生成一空隊(duì)列,算法操作：為隊(duì)列分配基本容量空間,設(shè)置隊(duì)列為,空隊(duì)列,，,即,front=rear=0,（也可為任意單元，如,2,，或,4,）,;,,53,算法：,Status InitQueue ( SqQueue &q ),{//,初始化空循環(huán)隊(duì)列,q,q . base=(QElemType *)malloc,(,

38、sizeof(QElemType,）,* QUEUE_MAXSIZE,);,//,分配空間,if (,!q.base,) exit(OVERFLOW);//,失敗，退出程序,q.front =q.rear=0;//,置空隊(duì)列,return OK;,}//InitQueue;,,新開(kāi)單元的地址為,0,則表示內(nèi)存不足,54,算法說(shuō)明：向循環(huán)隊(duì)列的隊(duì)尾插入一個(gè)元素,分 析,：,(1),插入前應(yīng)當(dāng)先判斷隊(duì)列是否滿,,if (( q . rear + 1 ) %,,QUEUE_MAXSIZE,)==q.front),return ERROR;,(2,）插入動(dòng)作,,q.base [q.re

39、ar] = e;,q.rear = ( q . rear + 1 ) %,QUEUE_MAXSIZE,;,,2,） 入隊(duì)操作,,55,Status,EnQueue,(SqQueue &q, QElemType e),{,//,向循環(huán)隊(duì)列,q,的隊(duì)尾加入一個(gè)元素,e,if ( (q.rear+1) %,QUEUE_MAXSIZE,= = q.front ),return ERROR ;,q.base [ q.rear ] = e;,//,存儲(chǔ),,q.rear = ( q . rear + 1 ) %,QUEUE_MAXSIZE,;,//,指針后移,return OK;,},/

40、/,EnQueue,;,,2,） 入隊(duì)操作（完整函數(shù)）,56,3,）出隊(duì)操作,算法說(shuō)明：刪除隊(duì)頭元素，返回其值,e,分 析：,（,1,）,在刪除前應(yīng)當(dāng)判斷隊(duì)列是否空；,,if (q.front = q.rear ) return ERROR;,,（,2,）,插入動(dòng)作分析；,因?yàn)殛?duì)頭指針,front,指向隊(duì)頭元素的位置，所以：,,e = q.base [ q.front ] ;,q.front = ( q . front + 1 ) %,QUEUE_MAXSIZE,;,,,57,Status,DeQueue,,( SqQueue &q, QElemType &e),{,/

41、/,若隊(duì)列不空，刪除循環(huán)隊(duì)列,q,的隊(duì)頭元素，,,//,由,e,返回其值，并返回,OK,if ( q.front = = q.rear ) return ERROR;,//,隊(duì)列空,e = q.base [ q.front ] ;,q.front=(q.front+1) %,QUEUE_MAXSIZE,;,return OK;,},// DeQueue,算法：,,58,討論（代本章小結(jié)）,線性表、棧與隊(duì)的異同點(diǎn),相同點(diǎn)：,邏輯結(jié)構(gòu)相同，都是線性的；都可以用順序存儲(chǔ)或鏈表存儲(chǔ)；棧和隊(duì)列是兩種特殊的線性表，即,受限的線性表,（只是對(duì)插入、刪除運(yùn)算加以限制）。,不同點(diǎn)：,① 運(yùn)算規(guī)則不同，線性表

42、為隨機(jī)存取，而棧是只允許在一端進(jìn)行插入和刪除運(yùn)算，因而是后進(jìn)先出表,LIFO,；隊(duì)列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算，因而是先進(jìn)先出表,FIFO,。,② 用途不同，線性表比較通用；堆棧用于函數(shù)調(diào)用、遞歸和簡(jiǎn)化設(shè)計(jì)等；隊(duì)列用于離散事件模擬、多道作業(yè)處理和簡(jiǎn)化設(shè)計(jì)等。,,59,一 選擇題,1.,對(duì)于棧操作數(shù)據(jù)的原則是（ ）。,先進(jìn)先出,B.,后進(jìn)先出,C.,后進(jìn)后出,D.,不分順序,2.,一個(gè)棧的輸入序列為,123…n,，若輸出序列的第一個(gè)元素是,n,，輸出第,i,（,1<=i<=n,）個(gè)元素是（ ）。,A.,不確定,B. n-i+1 C. i D.

43、n-i,3.,若一個(gè)棧的輸入序列為,1,2,3,…,n,，輸出序列的第一個(gè)元素是,i,，則第,j,個(gè)輸出元素是（ ）。,,A. i-j-1 B. i-j C. j-i+1 D.,不確定的,4.,棧在（ ）中應(yīng)用。,【,中山大學(xué),1998,二、,3,（,2,分）,】,遞歸調(diào)用,B.,子程序調(diào)用,C.,表達(dá)式求值,D. A,，Ｂ，Ｃ,5.,有六個(gè)元素,6,，,5,，,4,，,3,，,2,，,1,的順序進(jìn)棧，問(wèn)下列哪,一個(gè)不是合法的出棧序列？（ ）,5 4 3 6 1 2 B. 4 5 3 1 2 6,C. 3 4 6 5

44、 2 1 D. 2 3 4 1 5 6,60,6.,在作進(jìn)棧運(yùn)算時(shí),,,應(yīng)先判別棧是否,( ① ),,在作退棧運(yùn)算時(shí)應(yīng)先判別棧是否,( ② ),。當(dāng)棧中元素為,n,個(gè),,,作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢,,,則說(shuō)明該棧的最大容量為,( ③ ),。,為了增加內(nèi)存空間的利用率和減少溢出的可能性,,,由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí),,,應(yīng)將兩棧的,( ④ ),分別設(shè)在這片內(nèi)存空間的兩端,,,這樣,,,當(dāng),( ⑤ ),時(shí)，才產(chǎn)生上溢。,,①,, ②: A.,空,B.,滿,C.,上溢,D.,下溢,③,: A. n-1 B. n C. n+1 D.

45、n/2,④: A.,長(zhǎng)度,B.,深度,C.,棧頂,D.,棧底,⑤,: A.,兩個(gè)棧的棧頂同時(shí)到達(dá)棧空間的中心點(diǎn),.,B.,其中一個(gè)棧的棧頂?shù)竭_(dá)?？臻g的中心點(diǎn),.,C.,兩個(gè)棧的棧頂在?？臻g的某一位置相遇,.,D.,兩個(gè)棧均不空,,,且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底,.,61,7.,輸入序列為,ABC,，可以變?yōu)?CBA,時(shí)，經(jīng)過(guò)的棧操作為（ ）,【,中山大學(xué),1999,一、,8(1,分,)】,A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop,C. push,push,pop,pop,push,pop

46、 D. push,pop,push,push,pop,pop,8.,若一個(gè)棧以向量,V[1..n],存儲(chǔ)，初始棧頂指針,top,為,n+1,，則下面,x,進(jìn)棧的正確操作是,( ),。,A,．,top:=top+1; V [top]:=x B. V [top]:=x; top:=top+1,C. top:=top-1; V [top]:=x D. V [top]:=x; top:=top-1,9.,設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（ ）數(shù)據(jù)結(jié)構(gòu)最佳。,A,．線性表的順序存儲(chǔ)結(jié)構(gòu),B.,隊(duì)列,C.

47、,線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),D.,棧,62,10.,用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí),,,其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn),,,其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí),( ),。,【,北京理工大學(xué),2001,六、,3,（,2,分）,】,A,．僅修改隊(duì)頭指針,B.,僅修改隊(duì)尾指針,C.,隊(duì)頭、隊(duì)尾指針都要修改,D.,隊(duì)頭,,,隊(duì)尾指針都可能要修改,11.,假設(shè)以數(shù)組,A[m],存放循環(huán)隊(duì)列的元素,,,其頭尾指針?lè)謩e為,front,和,rear,，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（ ）。,A,．,(rear-front+m)%m B,．,rear-front+1,C,．,(front-rear+m)%m D,．,(rear-front)%m,12,棧和隊(duì)都是（ ）,A,．順序存儲(chǔ)的線性結(jié)構(gòu),B.,鏈?zhǔn)酱鎯?chǔ)的非線性結(jié)構(gòu),C.,限制存取點(diǎn)的線性結(jié)構(gòu),D.,限制存取點(diǎn)的非線性結(jié)構(gòu),