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

《嚴(yán)蔚敏版數(shù)據(jù)結(jié)構(gòu)第三章.》由會員分享，可在線閱讀，更多相關(guān)《嚴(yán)蔚敏版數(shù)據(jù)結(jié)構(gòu)第三章.（62頁珍藏版）》請在裝配圖網(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)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,,,*,1,數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容,,,,,,,2,3.1,棧（,Stack,）,,第三章 棧和隊列,3.2,隊列,（,Queue,）,1.,定義,2.,邏輯結(jié)構(gòu),3.,存儲結(jié)構(gòu),4.,運算規(guī)則,5.,實現(xiàn)方式,1.,定義,2.,邏輯結(jié)構(gòu),3.,存儲結(jié)構(gòu),

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

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

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

5、base,空棧,a,進棧,b,進棧,,,,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)前已分配的存儲空間,} 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,},順序棧的基本運算,:,,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ū)別,——,對線性表,,s= (a,1,, a,2 , …. ,,a,n-1 ,,a,n,),表頭,表尾,棧

8、底,base,棧頂,top,低地址,高地址,寫入：,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,）,,（注意要遵循,“,后進先出,”,原則）,A,,,,,,A,,,C,B,A,,,,B,A,top,核心語句：,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;,//,追加存儲空間,},*(S->top)=x;,,（,S->top,）,++;,Return ok,},14,,出棧操作,——,例如從棧中取出,‘,B,’,,,（注意要遵循,“,后進先出,”,原則）,D,C,B,A,,top,top,,D,C,,A,B,,D,C,B,A,top,,,D,C,B,A,top,低地址,L,高地址,M,D,核心語句：,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,：,一個棧的輸入序列是,12345,，若在入棧的過程中允許出棧,，,則棧的輸出序列,43512,可能實現(xiàn)嗎？,12345,的輸出呢？,43512,不可

12、能實現(xiàn)，主要是其中的,12,順序不能實現(xiàn)；,,12345,的輸出可以實現(xiàn)，只需壓入一個立即彈出一個即可。,,,435612,中到了,12,順序不能實現(xiàn)；,,135426,可以實現(xiàn)。,例,2,：,如果一個棧的輸入序列為,123456,，能否得到,435612,和,135426,的出棧序列？,,答：,答：,17,例,3,（嚴(yán)題集,3.1,）,一個棧的輸入序列為,123,，若在入棧的過程中允許出棧，則可能得到的出棧序列是什么？,答：,可以通過窮舉所有可能性來求解：,①,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,；,合計有,5,種可能性。,,18,例,4,：,計算機系,2001,年考研題（程序設(shè)計基礎(chǔ)）,設(shè)依次進入一個棧的元素序列為,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、,討論：有無通用的判別原則？,有。在可能的輸出序列中，不存在這樣的輸入序列,i,，,j,，,k,，能同時滿足,i

15、acksize;,20,補充,3,：鏈棧 鏈棧示意圖,s,,,,(,棧底,),(,棧頂,),top,,,,,a3,a2,a4,a1,^,21,,鏈棧的入棧函數(shù)、出棧函數(shù),（以頭指針為棧頂，在頭指針處插入或刪除！）,公共說明部分：,,typedef struct snode{,SElemType data;,struct snode *link;,},NODE,;,NODE,*st(,棧頂指針,), *p(,新節(jié)點,);,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,說 明,,鏈?zhǔn)綏o棧滿問題，空間可擴充,插入與刪除僅在棧頂處執(zhí)行,鏈?zhǔn)綏５臈ｍ斣阪滎^,適合于多棧操作,24,,數(shù)制轉(zhuǎn)換（十轉(zhuǎn),N,）,——P48,,設(shè)計思路：用棧暫存低位值,,例,2,：括號匹配的檢驗,————P49,,設(shè)計思路：用棧暫

17、存左括號,,例,3,,：,表達式求值,—-————P52,,設(shè)計思路：用棧暫存運算符,,,例,1,：,棧的應(yīng)用舉例,25,1.,數(shù)制轉(zhuǎn)換,,N = (N div d)×d + N mod d,,例如：（,1348),10,= (2504),8,,，其運算過程如下：,,,N N div 8 N mod 8,,1348 168 4 168 21 0 21 2 5 2 0 2,輸出順序,計算順序,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.,行編輯程序,在用戶輸入一行的過程中，允許用戶輸入出差錯，并在發(fā)現(xiàn)有誤時可以及時更正。,設(shè)立一個輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū),;,并假設(shè)“,#”,為退格符，“,@”,為退行符。,假設(shè)從終端接受兩行字符：,,whli##ilr#e,（,s#*s),outcha@putchar(*s=

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

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

22、達式求值）,,32,（,3,）算法思想：,設(shè)定兩棧：,操作符棧,OPTR,，操作數(shù)棧,OPND,棧初始化,：設(shè)操作數(shù)棧,OPND,為空；操作符棧,OPTR,的棧底元素為表達式起始符 ‘,#’,；,依次讀入字符,：是操作數(shù)則入,OPND,棧，是操作符則要判斷：,,if,,操作符,<,棧頂元素,，則退棧、計算，結(jié)果壓入,OPND,棧；,,操作符,=,棧頂元素且不為‘,#’,，脫括號（彈出左括號）；,,操作符,>,棧頂元素,，壓入,OPTR,棧。,棧的應(yīng)用（表達式求值）,,33,棧的應(yīng)用（表達式求值）,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,隊列,與線性表相同，仍為一對一關(guān)系。,順序隊,或,鏈隊,，以循環(huán)順序隊更常見。,只能在隊首和隊尾運算，且訪問結(jié)點時依照,先進先出,（,FIFO,）,的原則。,關(guān)鍵是掌握,入隊,和,出隊,操作，具體實現(xiàn)依順序隊或鏈隊的不同而

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

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

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

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

30、Q),{,//,求隊列的長度,,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,的新的隊尾元素,,QueuePtr p;,if(!(p=(QueuePtr)malloc(sizeof(QNode)))),//,存儲分配失敗,,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),{,//,若隊列不空,,,刪除,Q,的隊頭元素,,,用,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,順序隊示意圖,Q,,,(,隊尾,),(,隊首,),,front,,,,a,

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

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

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

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

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

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

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

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

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

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

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

43、n-i,3.,若一個棧的輸入序列為,1,2,3,…,n,，輸出序列的第一個元素是,i,，則第,j,個輸出元素是（ ）。,,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. A,，Ｂ，Ｃ,5.,有六個元素,6,，,5,，,4,，,3,，,2,，,1,的順序進棧，問下列哪,一個不是合法的出棧序列？（ ）,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.,在作進棧運算時,,,應(yīng)先判別棧是否,( ① ),,在作退棧運算時應(yīng)先判別棧是否,( ② ),。當(dāng)棧中元素為,n,個,,,作進棧運算時發(fā)生上溢,,,則說明該棧的最大容量為,( ③ ),。,為了增加內(nèi)存空間的利用率和減少溢出的可能性,,,由兩個棧共享一片連續(xù)的內(nèi)存空間時,,,應(yīng)將兩棧的,( ④ ),分別設(shè)在這片內(nèi)存空間的兩端,,,這樣,,,當(dāng),( ⑤ ),時，才產(chǎn)生上溢。,,①,, ②: A.,空,B.,滿,C.,上溢,D.,下溢,③,: A. n-1 B. n C. n+1 D.

45、n/2,④: A.,長度,B.,深度,C.,棧頂,D.,棧底,⑤,: A.,兩個棧的棧頂同時到達棧空間的中心點,.,B.,其中一個棧的棧頂?shù)竭_?？臻g的中心點,.,C.,兩個棧的棧頂在棧空間的某一位置相遇,.,D.,兩個棧均不空,,,且一個棧的棧頂?shù)竭_另一個棧的棧底,.,61,7.,輸入序列為,ABC,，可以變?yōu)?CBA,時，經(jīng)過的棧操作為（ ）,【,中山大學(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.,若一個棧以向量,V[1..n],存儲，初始棧頂指針,top,為,n+1,，則下面,x,進棧的正確操作是,( ),。,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è)計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用（ ）數(shù)據(jù)結(jié)構(gòu)最佳。,A,．線性表的順序存儲結(jié)構(gòu),B.,隊列,C.

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