第三章+棧和隊(duì)列

1、棧 隊(duì)列 遞歸第三章棧和隊(duì)列第三章棧和隊(duì)列1棧 ( Stack )定義:是限定僅在表尾進(jìn)行插入或刪除操作的線性表。允許插入和刪除的一端稱為棧頂(top)，另一端稱為棧底(bottom)特點(diǎn)：后進(jìn)先出 (LIFO)a1topbottoman.進(jìn)棧進(jìn)棧 出棧出棧2棧的主要操作ADT Stack /對(duì)象由數(shù)據(jù)類型為StackData的元素構(gòu)成 int Push (stack *S, StackData x); /進(jìn)棧 int Pop (stack *S, StackData &x); /出棧 int GetTop (stack *S, StackData &x); /取棧頂 void

2、 InitStack (stack *S); /置空棧 int StackEmpty (stack *S); /判?？辗?int StackFull (stack *S); /判棧滿否3棧的表示和實(shí)現(xiàn)順序棧：棧的順序存儲(chǔ)結(jié)構(gòu)，利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，指針top指向棧頂元素在順序棧中的下一個(gè)位置，base為棧底指針，指向棧底的位置。base空棧a 進(jìn)棧b 進(jìn)棧aabtopbasetopbasetop4toptopabcdee 進(jìn)棧abcdef 進(jìn)棧溢出abde 出出棧cbasebasebasetop5順序棧的類型表示:#define STACK_INIT_SIZ

3、E 100；#define STACKINCREMENT 10；typedef char StackData;typedef struct /順序棧定義 StackData *base; /棧底指針 StackData *top; /棧頂指針int stacksize；/當(dāng)前已分配的全部存儲(chǔ)空間 SeqStack；6判?？読nt StackEmpty (SeqStack *S) if( S-top = S-base ) return 1 /判?？?空則返回1 else return 0; /否則返回0判棧滿int StackFull (SeqStack *S) if( S-top- S-bas

4、e = S- StackSize ) return 1 /判棧滿,滿則返回1else return 0; /否則返回0順序棧的基本運(yùn)算順序棧的基本運(yùn)算:7初始化初始化void InitStack ( SeqStack *S) /置空棧置空棧S-base-base =( StackData *)malloc(STACK_INIT_SIZE * sizeof(StackData);if (!S-base) exit(OVERFLOW);S-top = S-base-base ; S-stacksize= S-stacksize= STACK_INIT_SIZE ;Return ok; 8入棧int

5、 Push (SeqStack *S, StackData x) /插入元素x為新的棧頂元素 if ( StackFull (S) ) S-base =( StackData *)realloc(S-base ,(S-stacksize+ STACKINCREMENT) * sizeof(StackData);if(! S-base)exit(overflow); S-top= S-base + S-stacksize;S-stacksize+= STACKINCREMENT; /追加存儲(chǔ)空間 *(S-top)=x; （S-top）+;Return ok9取棧頂元素int GetTop (Se

6、qStack *S, StackData &x) /若棧空返回0, 否則棧頂元素讀到x并返回1 if ( StackEmpty(S) ) return 0; x = *(S-top-1); return 1;10出棧int Pop (SeqStack *S, StackData &x) /若?？辗祷?, 否則棧頂元素退出到x并返回1 if ( StackEmpty(S) ) return 0; -(S-top);x = *(S-top); return 1;11鏈?zhǔn)綏?棧的鏈接表示 鏈?zhǔn)綏o(wú)棧滿問(wèn)題，空間可擴(kuò)充插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏５臈ｍ斣阪滎^top12鏈?zhǔn)綏?(Lin

7、kStack)的定義typedef int StackData;typedef struct node StackData data; /結(jié)點(diǎn) struct node *link; /鏈指針 StackNode;typedef struct StackNode *top; /棧頂指針 LinkStack;13鏈?zhǔn)綏２僮鲗?shí)現(xiàn)初始化void InitStack ( LinkStack *S ) S-top = NULL;入棧int Push ( LinkStack *S, StackData x ) StackNode *p = ( StackNode * ) malloc ( sizeof (

8、StackNode ) ); p-data = x; p-link = S-top; S-top = p; return 1;14判?？読nt StackEmpty (LinkStack *S) return S-top = NULL;出棧int Pop ( LinkStack *S, StackData &x ) if ( StackEmpty (S) ) return 0; StackNode * p = S-top; S-top = p-link; x = p-data; free (p); return 1; 15取棧頂int GetTop ( LinkStack *S, St

9、ackData &x ) if ( StackEmpty (S) ) return 0; x = S-top-data; return 1;置?？読nt MakeEmpty ( LinkStack *S) While(S-top!=NULL)StackNode * p = S-top; S-top = S-top -link;free(p);16程序中定義多個(gè)棧程序中定義多個(gè)棧（1）定義共享?xiàng)?shù)據(jù)結(jié)構(gòu)）定義共享?xiàng)?shù)據(jù)結(jié)構(gòu)#define MAX 100 int stackMAX,top1=0,top2=MAX-1;棧1top1top2棧217(2)共享進(jìn)棧算法共享進(jìn)棧算法 void pu

10、sh1(int x) if (top1top2) printf(“overflow”); else stacktop1=x;top1+; void push2(int x) if(top1top2) printf(“overflow”); else stacktop2=x;top2-;18(3)共享出棧算法共享出棧算法 int pop1()if top1=0)printf(“underflow”);return(NULL);top1-;return(stacktop1);int pop2()if(top2=MAX-1)printf(“underflow”);return(NULL): top2

11、+;return(stacktop2);19棧的應(yīng)用舉例棧的應(yīng)用舉例數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換行編輯程序行編輯程序迷宮求解迷宮求解表達(dá)式求值表達(dá)式求值20采用對(duì)十進(jìn)制數(shù)除8取余的方法，可得到八進(jìn)制數(shù)的倒序。 N = (N div d)d + N mod d 例如：（1348)10 = (2504)8 ，其運(yùn)算過(guò)程如下：N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2計(jì)算順序計(jì)算順序輸出順序輸出順序21數(shù)制轉(zhuǎn)換十進(jìn)制數(shù)轉(zhuǎn)換為八進(jìn)制數(shù)。void conversion () InitStack(S); scanf (%d,N); while (N) Push(

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

13、ilr#e（s#*s) outchaputchar(*s=#+);實(shí)際有效行為：實(shí)際有效行為： while (*s) putchar(*s+);23Void LineEdit()InitStack(s);ch=getchar();while (ch != EOF) /EOF為全文結(jié)束符為全文結(jié)束符while (ch != EOF & ch != n) switch (ch) case # : Pop(S, ch); break; case : ClearStack(S); break;/ 重置重置S為空棧為空棧 default : Push(S, ch); break; ch = ge

14、tchar(); / 從終端接收下一個(gè)字符從終端接收下一個(gè)字符 /while24將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過(guò)程的將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過(guò)程的數(shù)據(jù)區(qū)；數(shù)據(jù)區(qū)；ClearStack(S); / 重置重置S為空棧為空棧if (ch != EOF) ch = getchar(); /whileDestroyStack(s);25v迷宮求解迷宮求解通常用的是通常用的是“窮舉求解窮舉求解”的方法的方法# #$# #$# $# # # # # #26v迷宮路徑算法的基本思想若當(dāng)前位置“可通”，則納入路徑，繼續(xù)前進(jìn);若當(dāng)前位置“不可通”，則后退，換方向繼續(xù)探索;若四周“均無(wú)通路”，則將當(dāng)前位置從路

15、徑中刪除出去。27設(shè)定當(dāng)前位置的初值為入口位置；設(shè)定當(dāng)前位置的初值為入口位置； do 若當(dāng)前位置可通，若當(dāng)前位置可通， 則將當(dāng)前位置插入棧頂；則將當(dāng)前位置插入棧頂； 若該位置是出口位置，則算法結(jié)束；若該位置是出口位置，則算法結(jié)束； 否則切換當(dāng)前位置的東鄰方塊為新的否則切換當(dāng)前位置的東鄰方塊為新的 當(dāng)前位置；當(dāng)前位置； . 28否則否則 若棧不空且棧頂位置尚有其他方向未被探索，若棧不空且棧頂位置尚有其他方向未被探索，則設(shè)定新的當(dāng)前位置為則設(shè)定新的當(dāng)前位置為: 沿順時(shí)針?lè)较蛐D(zhuǎn)沿順時(shí)針?lè)较蛐D(zhuǎn) 找到的棧頂位置的下一相鄰塊；找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，若棧不空但棧頂

16、位置的四周均不可通，則則刪去棧頂位置；刪去棧頂位置；/ 從路徑中刪去該通道塊從路徑中刪去該通道塊 若棧不空，則重新測(cè)試新的棧頂位置，若棧不空，則重新測(cè)試新的棧頂位置， 直至找到一個(gè)可通的相鄰塊或出棧至?？罩敝琳业揭粋€(gè)可通的相鄰塊或出棧至棧空;while (棧不空）；棧不空）；29typedef struct int ord;/序號(hào)PosType seat;/坐標(biāo)int di;/方向SElemType;/棧元素Status MazePath (MazeType maze, PosType start, PosType end) InitStack(S); curpos=start;/當(dāng)前位置cu

17、rstep=1;30do if (Pass(curpos) /可通過(guò)且未走過(guò)FootPrint(curpos);/記已通過(guò)標(biāo)記e=(curstep, curpos, 1);Push (S, e);if (curpos = end) return (TRUE);curpos = NextPos ( curpos, 1);curstep+;/if31else if (!StackEmpty(S) Pop(S, e);while (e.di=4 & !StackEmpty(S) MarkPrint(e.seat); Pop(S,e);/記不能通過(guò)標(biāo)記/whileif(e.di4) e.di+

18、; Push(S, e);curpos = NextPos(e.seat, e.di);/if/if/elsewhile (!StackEmpty(S);return (FALSE);/MazePath32限于二元運(yùn)算符的表達(dá)式定義限于二元運(yùn)算符的表達(dá)式定義: 表達(dá)式表達(dá)式 := (操作數(shù)操作數(shù)) + (運(yùn)算符運(yùn)算符) + (操作數(shù)操作數(shù)) 操作數(shù)操作數(shù) := 簡(jiǎn)單變量簡(jiǎn)單變量 | 表達(dá)式表達(dá)式 簡(jiǎn)單變量簡(jiǎn)單變量 : = 標(biāo)識(shí)符標(biāo)識(shí)符 | 無(wú)符號(hào)整數(shù)無(wú)符號(hào)整數(shù)Exp = S1 + OP + S2前綴表示法前綴表示法OP + S1 + S2中綴表示法中綴表示法 S1 + OP + S2后綴表示法

19、后綴表示法 S1 + S2 + OP表達(dá)式求值表達(dá)式求值33例如例如: Exp = a b + (c d / e) f前綴式前綴式: + a b c / d e f中綴式中綴式: a b + c d / e f后綴式后綴式: a b c d e / f + 表達(dá)式標(biāo)識(shí)方法表達(dá)式標(biāo)識(shí)方法b-ca/*def*+34后綴表達(dá)式求值先找運(yùn)算符，再找操作數(shù)例如：例如： a b c d e / f +a bd/ec-d/e(c-d/e) f35從原表達(dá)式求得后綴式方法從原表達(dá)式求得后綴式方法設(shè)立暫存設(shè)立暫存運(yùn)算符運(yùn)算符的的棧棧;設(shè)表達(dá)式的結(jié)束符為設(shè)表達(dá)式的結(jié)束符為“#”, 予設(shè)予設(shè)運(yùn)算符棧運(yùn)算符棧的的棧底

20、為棧底為“#”若若當(dāng)前字符當(dāng)前字符是操作數(shù)是操作數(shù)，則，則直接發(fā)送給后綴直接發(fā)送給后綴式式;(后綴與前綴式操作數(shù)的順序是相同的后綴與前綴式操作數(shù)的順序是相同的)若若當(dāng)前當(dāng)前運(yùn)算符的運(yùn)算符的優(yōu)先數(shù)高優(yōu)先數(shù)高于棧頂運(yùn)算符，于棧頂運(yùn)算符，則則進(jìn)棧進(jìn)棧;否則，退出棧頂運(yùn)算符發(fā)送給后綴式否則，退出棧頂運(yùn)算符發(fā)送給后綴式;“(” 對(duì)它之前后的運(yùn)算符對(duì)它之前后的運(yùn)算符起隔離作用起隔離作用，“)”為自左括弧開(kāi)始的表達(dá)式的結(jié)束符。為自左括弧開(kāi)始的表達(dá)式的結(jié)束符。36表達(dá)式求值的算法采用“算符優(yōu)先法”，在表達(dá)式中,優(yōu)先級(jí)的順序是:（1）括號(hào)的優(yōu)先級(jí)最高,對(duì)括號(hào)內(nèi)的各種運(yùn)算符有:先乘除、再加堿，同級(jí)運(yùn)算從左至右。（

21、2）先括號(hào)內(nèi)，后括號(hào)外，多層括號(hào)，由內(nèi)向外。任何表達(dá)式都是由操作數(shù)、運(yùn)算符和界符組成。操作數(shù)可以是常量、變量、常數(shù)運(yùn)算符有算術(shù)運(yùn)算符、關(guān)系運(yùn)算符、邏輯運(yùn)算符界符包括左右括號(hào)算式結(jié)束符。運(yùn)算符和界符統(tǒng)稱為“算符”。37在算符集中，在每一個(gè)運(yùn)算步，相鄰的算符c1 和c2之間的關(guān)系是如下三種情況（c1出現(xiàn)在c2之前）：c1c2,c1的優(yōu)先級(jí)大于c27*(5-3)38算符間優(yōu)先級(jí) / ( ) （） =c2c139為實(shí)現(xiàn)算符優(yōu)先算法，在這里用了兩個(gè)工作棧。一個(gè)存放算符OPTR，另一個(gè)存放數(shù)據(jù)OPND。算法思想是：（1）首先置數(shù)據(jù)棧為空棧，表達(dá)式起始符“”為算符棧的棧底元素（2）自左向右掃描表達(dá)式，讀到操

22、作數(shù)進(jìn)OPND棧，讀到運(yùn)算符，則和OPTR棧頂元素比較（棧頂元素為c1，讀到的算符為c2);若c1c2,則將c1出棧，并在操作數(shù)棧取出兩個(gè)元素a和b按c1做運(yùn)算，運(yùn)算結(jié)果進(jìn)OPND.重復(fù)直到表達(dá)式求值完畢。40例如：表達(dá)式3*(7-2),求值過(guò)程如下表：步驟步驟OPTROPTR棧棧OPNDOPND棧棧輸入字符輸入字符主要操作主要操作13*(7-2)#PUSH(OPND,3)23*(7-2)#PUSH(OPTR,*)3 3(7-2)#PUSH(OPTR,()4 （37-2)#PUSH(OPND,7)5 （3 7-2)#PUSH(OPTR,-)6 （ - 3 72)#PUSH(OPND,2)7 （

23、3 7 2)#operate(7,-,2)8 （3 5)#POP(OPTR)消消去括號(hào)去括號(hào)9 15 #operate(3,*,5)41為使兩個(gè)算符比較方便,給算符設(shè)置優(yōu)先級(jí),如下表,其中c1為棧內(nèi)元素,c2為棧外元素算算符符棧內(nèi)優(yōu)先級(jí)棧內(nèi)優(yōu)先級(jí)棧外優(yōu)先級(jí)棧外優(yōu)先級(jí)* /43+ -21(05)50#-1-142算符比較算法算符比較算法char Precede(char c1,char c2)int c_temp1,c_temp2; switch(c1) case *: case /:c_temp1=4;break;case +: case -:c_temp1=2;break; case (:c

24、_temp1=0;break; case ):c_temp1=5;break; case #:c_temp1=-1;43switch(c2) case *: case /:c_temp2=3;break; case +: case -:c_temp2=1;break; case (:c_temp2=5;break; case ):c_temp2=0;break; case #:c_temp2=-1;if(c_temp1c_temp2) return(c_temp2) return();switch(c1) case *: case /:c_temp1=4;break;case +: case

25、-:c_temp1=2;break; case (:c_temp1=0;break; case ):c_temp1=5;break; case #:c_temp1=-1;44int express()Initstack(OPTR);Push(OPTR,#);InitStack(OPND);w=getchar();while(w!=#|GetTop(OPTR)!=#) if(!In(w,OP)Push(OPND,w);w=getchar();else/OP是操作符集合switch(Precede(GetTop(OPTR),w)case : op=Pop(OPTR);b=Pop(OPND);a=P

26、op(OPND);push(OPND,Operate(a,op,b);break;return(Getop(OPND);45OperandType EvaluateExpression() InitStack (OPTR); Push ( OPTR,#);InitStack (OPND); c=getchar();while (c!=#| GetTop(OPTR)!=#) if(!In(c,OP)Push(OPND,c);c=getchar();elseswitch(Precede(GetTop(OPTR),c)case :/退棧并計(jì)算Pop(OPTR,theta);Pop(OPND,b);

27、Pop(OPND,a);Push(OPND, Operate(a,theta,b);break;/switch/whilereturn GetTop(OPND);/EvaluateExpression47隊(duì)列定義:只允許在表的一端進(jìn)行插入，而在另一端刪除元素的線性表。在隊(duì)列中，允許插入的一端叫隊(duì)尾（rear），允許刪除的一端稱為對(duì)頭(front)。特點(diǎn)：先進(jìn)先出 (FIFO) a1 ，a2， a3，an出隊(duì)列出隊(duì)列入隊(duì)列入隊(duì)列隊(duì)隊(duì)頭頭隊(duì)隊(duì)尾尾48鏈隊(duì)列：隊(duì)列的鏈?zhǔn)奖硎炬滉?duì)列中，有兩個(gè)分別指示隊(duì)頭和隊(duì)尾的指針。鏈?zhǔn)疥?duì)列在進(jìn)隊(duì)時(shí)無(wú)隊(duì)滿問(wèn)題，但有隊(duì)空問(wèn)題。data nextfrontreardata

28、 nextfrontrear49frontrearx元素元素x入隊(duì)入隊(duì)frontrearxy元素元素y入隊(duì)入隊(duì)frontrearxy元素元素x出隊(duì)出隊(duì)frontrear空隊(duì)列空隊(duì)列frontrearNULL空隊(duì)列空隊(duì)列50鏈?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;51鏈隊(duì)列的主要操作初始化void InitQueue (

29、LinkQueue *Q ) Q-rear = Q-front = NULL;隊(duì)空int QueueEmpty ( LinkQueue *Q ) return Q-front = NULL;取隊(duì)頭元素int GetFront ( LinkQueue *Q, QueueData &x ) if ( QueueEmpty (Q) ) return 0; x = Q-front-data; return 1;52入隊(duì)int EnQueue ( LinkQueue *Q, QueueData x ) QueueNode *p = ( QueueNode * ) malloc ( sizeof

30、( QueueNode ) ); p-data = x; p-link = NULL; if ( Q-front = NULL ) /空,創(chuàng)建第一個(gè)結(jié)點(diǎn) Q-front = Q-rear = p; else Q-rear-link = p; /入隊(duì) Q-rear =p; return 1;53出隊(duì)int DeQueue ( LinkQueue *Q, QueueData &x) /刪去隊(duì)頭結(jié)點(diǎn)，并返回隊(duì)頭元素的值 if ( QueueEmpty (Q) ) return 0;/判隊(duì)空 QueueNode *p = Q-front; x = p-data;/保存隊(duì)頭的值 Q-front=

31、 Q-front-link; /新隊(duì)頭free (p); return 1;54循環(huán)隊(duì)列 (Circular Queue)順序隊(duì)列隊(duì)列的順序存儲(chǔ)表示。用一組地址連續(xù)的存儲(chǔ)單元依次存放從隊(duì)列頭到隊(duì)列尾的元素，指針front和rear分別指示隊(duì)頭元素和隊(duì)尾元素的位置。插入新的隊(duì)尾元素，尾指針增1，rear = rear + 1，刪除隊(duì)頭元素，頭指針增1， front = front + 1，因此，在非空隊(duì)列中，頭指針始終指向隊(duì)列頭元素，而尾指針始終指向隊(duì)列尾元素的下一個(gè)位置。 隊(duì)滿時(shí)再進(jìn)隊(duì)將溢出 解決辦法：將順序隊(duì)列臆造為一個(gè)環(huán)狀的空間，形成循環(huán)(環(huán)形)隊(duì)列55隊(duì)列的進(jìn)隊(duì)和出隊(duì)frontrear空

32、隊(duì)列空隊(duì)列frontrearA,B,C, D進(jìn)隊(duì)進(jìn)隊(duì)A B C DfrontrearA,B出隊(duì)出隊(duì)C DfrontrearE,F,G進(jìn)隊(duì)進(jìn)隊(duì)C D E F GC D E F GfrontrearH進(jìn)隊(duì)進(jìn)隊(duì),溢出溢出56循環(huán)隊(duì)列 (Circular Queue)隊(duì)頭、隊(duì)尾指針加1，可用取模(余數(shù))運(yùn)算實(shí)現(xiàn)。隊(duì)頭指針進(jìn)1: front = (front+1) %maxsize;隊(duì)尾指針進(jìn)1: rear = (rear+1) % maxsize;隊(duì)列初始化：front = rear = 0;隊(duì)空條件：front = rear;隊(duì)滿條件：(rear+1) % maxsize = front;01234

33、567循環(huán)隊(duì)列循環(huán)隊(duì)列frontrearMaxsizerontBCDrear一般情況一般情況AC01234567隊(duì)滿隊(duì)滿(錯(cuò)誤錯(cuò)誤)frontrearDEFGABCH01234567rear空隊(duì)列空隊(duì)列frontC01234567隊(duì)滿隊(duì)滿(正確正確)frontrearDEFGABC58#define MAXSIZE 100Typedef structQueueData *data;int front;int rear; SeqQueue循環(huán)隊(duì)列的類型定義59循環(huán)隊(duì)列操作的實(shí)現(xiàn)初始化隊(duì)列void InitQueue ( SeqQueue *Q ) /構(gòu)造空隊(duì)列Q-dat

34、a=(QueueData *)malloc(MAXSIZE *sizeof(QueueData);If(! Q-data)exit(OVERFLOW); Q-rear = Q-front = 0;Return ok60判隊(duì)空int QueueEmpty ( SeqQueue *Q ) return Q-rear = Q-front;判隊(duì)滿int QueueFull ( SeqQueue *Q ) return (Q-rear+1) % QueueSize = Q-front;入隊(duì)int EnQueue ( SeqQueue *Q, QueueData x ) if ( QueueFull (Q

35、) ) return 0; Q-dataQ-rear = x; Q-rear = ( Q-rear+1) % MAXSIZE;return 1;61出隊(duì)int DeQueue ( SeqQueue *Q, QueueData &x ) if ( QueueEmpty (Q) ) return 0; x = Q-dataQ-front; Q-front = ( Q-front+1) % MAXSIZE;return 1;取隊(duì)頭int GetFront ( SeqQueue *Q, QueueData &x ) if ( QueueEmpty (Q) ) return 0; x =

36、 Q-dataQ-front; return 1;求隊(duì)列長(zhǎng)度int QueueLength (SeqQueue *Q) return (Q-rear Q-front + MAXSIZE) % MAXSIZE;62隊(duì)列應(yīng)用舉例隊(duì)列應(yīng)用舉例 打印二項(xiàng)展開(kāi)式打印二項(xiàng)展開(kāi)式 (a + b)i 的系數(shù)的系數(shù)楊輝三角形楊輝三角形 (Pascals triangle) 1 1 i = 1 1 2 1 2 1 3 3 1 3 1 4 6 4 1 4 1 5 10 10 5 1 5 1 6 15 20 15 6 1 6 63分析第分析第 i 行元素與第行元素與第 i+1行元素的關(guān)系行元素的關(guān)系目的是從前一行的數(shù)

37、據(jù)可以計(jì)算下一行的數(shù)據(jù)目的是從前一行的數(shù)據(jù)可以計(jì)算下一行的數(shù)據(jù)64從第從第 i 行數(shù)據(jù)計(jì)算并存放第行數(shù)據(jù)計(jì)算并存放第 i+1 行數(shù)據(jù)行數(shù)據(jù)65void YANGHUI ( int n ) Queue q; /隊(duì)列初始化隊(duì)列初始化 q.MakeEmpty ( ); q.EnQueue (1); q.EnQueue (1);/預(yù)放入第一行的兩個(gè)系數(shù)預(yù)放入第一行的兩個(gè)系數(shù) int s = 0;for ( int i=1; i=n; i+ ) /逐行處理逐行處理 cout endl;/換行換行 q.EnQueue (0); for ( int j=1; j=i+2; j+ ) /處理第處理第i行的行的

38、i+2個(gè)系數(shù)個(gè)系數(shù) int t = q.DeQueue ( );/讀取系數(shù)讀取系數(shù) q.EnQueue ( s+t );/計(jì)算下一行系數(shù)，并進(jìn)隊(duì)列計(jì)算下一行系數(shù)，并進(jìn)隊(duì)列 s = t; if ( j != i+2 ) cout s ;/打印一個(gè)系數(shù)，第打印一個(gè)系數(shù)，第 i+2個(gè)個(gè)為為0 66 任任務(wù)務(wù)編編號(hào)號(hào) 1 2 3 4 5 優(yōu)優(yōu)先先權(quán)權(quán) 20 0 40 30 10 執(zhí)執(zhí)行行順順序序 3 1 5 4 2優(yōu)先級(jí)隊(duì)列 (Priority Queue)優(yōu)先級(jí)隊(duì)列 是不同于先進(jìn)先出隊(duì)列的另一種隊(duì)列。每次從隊(duì)列中取出的是具有最高優(yōu)先權(quán)的元素例如下表：任務(wù)的優(yōu)先權(quán)及執(zhí)行順序的關(guān)系數(shù)字越小，優(yōu)先權(quán)越高，

39、設(shè)不存在同優(yōu)數(shù)字越小，優(yōu)先權(quán)越高，設(shè)不存在同優(yōu)先級(jí)元素先級(jí)元素67#include #include $include const int maxPQSize = 50; /缺省元素個(gè)數(shù)缺省元素個(gè)數(shù)template class PQueue public: PQueue ( ); PQueue ( ) delete pqelements; void PQInsert ( const Type & item ); Type PQRemove ( ); 優(yōu)先隊(duì)列的類定義優(yōu)先隊(duì)列的類定義68 void makeEmpty ( ) count = -1; int IsEmpty ( ) con

40、st return count = -1; int IsFull ( ) const return count = maxPQSize; int Length ( ) const return count; / /優(yōu)先級(jí)隊(duì)列元優(yōu)先級(jí)隊(duì)列元素個(gè)數(shù)素個(gè)數(shù)private: Type *pqelements;/存放數(shù)組（優(yōu)先級(jí)隊(duì)列數(shù)組）存放數(shù)組（優(yōu)先級(jí)隊(duì)列數(shù)組） int count; /隊(duì)列元素計(jì)數(shù)隊(duì)列元素計(jì)數(shù) 69template PQueue:PQueue ( ) : count (- -1) pqelements = new TypemaxPQSize; assert ( pqelements

41、!= 0 ); /分配斷言分配斷言/創(chuàng)建優(yōu)先級(jí)隊(duì)列創(chuàng)建優(yōu)先級(jí)隊(duì)列template void PQueue :PQInsert ( const Type & item ) assert ( !IsFull ( ) ); /判隊(duì)滿斷言判隊(duì)滿斷言 count +； pqelementscount = item;/插入元素到隊(duì)尾插入元素到隊(duì)尾優(yōu)先級(jí)隊(duì)列部分成員函數(shù)的實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列部分成員函數(shù)的實(shí)現(xiàn)70template Type PQueue:PQRemove ( ) assert ( !IsEmpty ( ) ); /判隊(duì)空斷言判隊(duì)空斷言 Type min = pqelements0; int

42、 minindex = 0; for ( int i=1; icount; i+ ) /尋找最小元素尋找最小元素 if ( pqelementsi min ) /存于存于min min = pqelementsi; minindex = i; pqelementsminindex = pqelementscount- -1; /用最后一個(gè)元素填補(bǔ)要取走的最小值元素用最后一個(gè)元素填補(bǔ)要取走的最小值元素 count- - ;/優(yōu)先級(jí)隊(duì)列中元素個(gè)數(shù)減一優(yōu)先級(jí)隊(duì)列中元素個(gè)數(shù)減一 return min;/從隊(duì)中刪除最小值（優(yōu)先級(jí)最高）元素從隊(duì)中刪除最小值（優(yōu)先級(jí)最高）元素71離散事件模擬離散事件模擬日常

43、生活中排隊(duì)活動(dòng)的模擬程序需要用到隊(duì)列和日常生活中排隊(duì)活動(dòng)的模擬程序需要用到隊(duì)列和線性表的數(shù)據(jù)結(jié)構(gòu)，是隊(duì)列的典型應(yīng)用。線性表的數(shù)據(jù)結(jié)構(gòu)，是隊(duì)列的典型應(yīng)用。設(shè)銀行有四個(gè)窗口，從開(kāi)門(mén)起每個(gè)窗口一個(gè)時(shí)刻設(shè)銀行有四個(gè)窗口，從開(kāi)門(mén)起每個(gè)窗口一個(gè)時(shí)刻只能接待一個(gè)客戶，人多時(shí)客戶需排隊(duì)。當(dāng)客只能接待一個(gè)客戶，人多時(shí)客戶需排隊(duì)。當(dāng)客戶進(jìn)入銀行時(shí)，如有窗口空閑則直接辦理業(yè)務(wù)，戶進(jìn)入銀行時(shí)，如有窗口空閑則直接辦理業(yè)務(wù)，否則會(huì)排在人數(shù)最少的隊(duì)伍后面。先要求編程否則會(huì)排在人數(shù)最少的隊(duì)伍后面。先要求編程序模擬銀行的業(yè)務(wù)活動(dòng)并計(jì)算一天中客戶在銀序模擬銀行的業(yè)務(wù)活動(dòng)并計(jì)算一天中客戶在銀行的平均逗留時(shí)間。行的平均逗留時(shí)間。72

44、思路：思路： 為求平均時(shí)間要知道每個(gè)客戶到達(dá)和離為求平均時(shí)間要知道每個(gè)客戶到達(dá)和離開(kāi)銀行的兩個(gè)時(shí)刻，所有客戶逗留時(shí)間開(kāi)銀行的兩個(gè)時(shí)刻，所有客戶逗留時(shí)間總和除以客戶數(shù)便是平均時(shí)間?？偤统钥蛻魯?shù)便是平均時(shí)間。1. 客戶到達(dá)和離開(kāi)銀行兩個(gè)時(shí)刻發(fā)生的事客戶到達(dá)和離開(kāi)銀行兩個(gè)時(shí)刻發(fā)生的事情成為情成為“事件事件”，整個(gè)程序按事件發(fā)生，整個(gè)程序按事件發(fā)生的先后順序進(jìn)行處理，即事件驅(qū)動(dòng)模擬。的先后順序進(jìn)行處理，即事件驅(qū)動(dòng)模擬。73銀行客戶的離散事件驅(qū)動(dòng)模擬程序：銀行客戶的離散事件驅(qū)動(dòng)模擬程序：void Bank_Simulation(int CloseTime) /銀行業(yè)務(wù)模擬，統(tǒng)計(jì)一天內(nèi)客戶在銀行逗留的平

45、均時(shí)間。銀行業(yè)務(wù)模擬，統(tǒng)計(jì)一天內(nèi)客戶在銀行逗留的平均時(shí)間。OpenForDay; /初始化初始化while(MoreEvent) do EventDrived( OccurTime, EventType); /事件驅(qū)動(dòng)事件驅(qū)動(dòng)switch (EventType) case A:CustomerArrived; break; /處理客戶到達(dá)事處理客戶到達(dá)事件件case D:CustomerDeparture; break; /處理客戶離開(kāi)處理客戶離開(kāi)事件事件default: Invalid; /switch /while CloseForDay; /計(jì)算平均逗留時(shí)間計(jì)算平均逗留時(shí)間 /Bank_

46、Simulation74具體實(shí)現(xiàn)：具體實(shí)現(xiàn)：1.算法中處理的主要對(duì)象為算法中處理的主要對(duì)象為“事件事件”，事件的主要信息是，事件的主要信息是事件類型和發(fā)生時(shí)刻。事件有兩類：客戶到達(dá)事件，事件類型和發(fā)生時(shí)刻。事件有兩類：客戶到達(dá)事件，其發(fā)生時(shí)刻隨客戶到來(lái)自然形成；客戶離開(kāi)事件，其其發(fā)生時(shí)刻隨客戶到來(lái)自然形成；客戶離開(kāi)事件，其發(fā)生時(shí)刻由客戶事物所需時(shí)間和等待時(shí)間決定。由于發(fā)生時(shí)刻由客戶事物所需時(shí)間和等待時(shí)間決定。由于事件驅(qū)動(dòng)是按事件發(fā)生時(shí)刻的先后順序進(jìn)行，則事件驅(qū)動(dòng)是按事件發(fā)生時(shí)刻的先后順序進(jìn)行，則事件事件表表是有序表，其主要操作是插入和刪除事件。是有序表，其主要操作是插入和刪除事件。類型定義如下

47、：類型定義如下：typedef struct int OccurTime; /事件發(fā)生時(shí)刻事件發(fā)生時(shí)刻int NType; /事件類型，事件類型，0表示到達(dá)事件，表示到達(dá)事件，1至至4表示四表示四個(gè)窗口的離開(kāi)事件個(gè)窗口的離開(kāi)事件Event, ElemType; /事件類型，有序鏈表事件類型，有序鏈表LinkList的數(shù)據(jù)的數(shù)據(jù)元素類型元素類型typedef LinkList EventList /事件鏈表類型，定義為有序事件鏈表類型，定義為有序鏈表鏈表752.模擬程序的另一種數(shù)據(jù)結(jié)構(gòu)是表示客戶模擬程序的另一種數(shù)據(jù)結(jié)構(gòu)是表示客戶排隊(duì)的隊(duì)列，銀行的四個(gè)窗口對(duì)應(yīng)四個(gè)排隊(duì)的隊(duì)列，銀行的四個(gè)窗口對(duì)應(yīng)四個(gè)

48、隊(duì)列，隊(duì)列中客戶的信息是其到達(dá)的時(shí)隊(duì)列，隊(duì)列中客戶的信息是其到達(dá)的時(shí)刻和辦理事物所需時(shí)間。刻和辦理事物所需時(shí)間。typedef struct int ArrivalTime; /到達(dá)時(shí)刻到達(dá)時(shí)刻int Duration; /辦理事物所需時(shí)間辦理事物所需時(shí)間QElemType; /隊(duì)列的數(shù)據(jù)元素類型隊(duì)列的數(shù)據(jù)元素類型763.每個(gè)隊(duì)列的隊(duì)頭是正在辦理事物的客戶，每個(gè)隊(duì)列的隊(duì)頭是正在辦理事物的客戶，他辦完事物離開(kāi)隊(duì)列的時(shí)刻就是即將發(fā)他辦完事物離開(kāi)隊(duì)列的時(shí)刻就是即將發(fā)生的客戶離開(kāi)事件的時(shí)刻，即對(duì)每個(gè)隊(duì)生的客戶離開(kāi)事件的時(shí)刻，即對(duì)每個(gè)隊(duì)頭客戶都存在一個(gè)將要驅(qū)動(dòng)的客戶離開(kāi)頭客戶都存在一個(gè)將要驅(qū)動(dòng)的客戶離開(kāi)

49、事件。因此在任何時(shí)刻即將發(fā)生的事件事件。因此在任何時(shí)刻即將發(fā)生的事件只有五種可能只有五種可能：（：（1）新客戶到達(dá)；（）新客戶到達(dá)；（2）1號(hào)窗口客戶離開(kāi)；（號(hào)窗口客戶離開(kāi)；（3）2號(hào)窗口客戶離號(hào)窗口客戶離開(kāi)；（開(kāi)；（4）3號(hào)窗口客戶離開(kāi)；（號(hào)窗口客戶離開(kāi)；（5）4號(hào)號(hào)窗口客戶離開(kāi)。窗口客戶離開(kāi)。由以上分析可見(jiàn)，在這個(gè)模擬程序中只需由以上分析可見(jiàn)，在這個(gè)模擬程序中只需要兩種數(shù)據(jù)類型：有序鏈表和隊(duì)列。要兩種數(shù)據(jù)類型：有序鏈表和隊(duì)列。77主要操作的實(shí)現(xiàn)：主要操作的實(shí)現(xiàn)：設(shè)第一個(gè)客戶進(jìn)門(mén)的時(shí)刻為設(shè)第一個(gè)客戶進(jìn)門(mén)的時(shí)刻為0，即是模擬程序處理的第一，即是模擬程序處理的第一個(gè)事件，之后每個(gè)客戶到達(dá)的時(shí)刻在

50、前一個(gè)客戶到達(dá)個(gè)事件，之后每個(gè)客戶到達(dá)的時(shí)刻在前一個(gè)客戶到達(dá)時(shí)設(shè)定。因此在客戶到達(dá)事件發(fā)生時(shí)須先產(chǎn)生兩個(gè)隨時(shí)設(shè)定。因此在客戶到達(dá)事件發(fā)生時(shí)須先產(chǎn)生兩個(gè)隨機(jī)數(shù)：其一為此時(shí)刻到達(dá)的客戶辦理事務(wù)所需時(shí)間機(jī)數(shù)：其一為此時(shí)刻到達(dá)的客戶辦理事務(wù)所需時(shí)間durtime;其二為下一客戶將到達(dá)的時(shí)間間隔其二為下一客戶將到達(dá)的時(shí)間間隔intertime,假設(shè)當(dāng)前事件發(fā)生的時(shí)刻為假設(shè)當(dāng)前事件發(fā)生的時(shí)刻為occurtime，則下一個(gè)客戶，則下一個(gè)客戶到達(dá)事件發(fā)生的時(shí)刻為到達(dá)事件發(fā)生的時(shí)刻為occurtime+intertime。由此應(yīng)。由此應(yīng)產(chǎn)生一個(gè)新的客戶到達(dá)事件插入事件表；剛到達(dá)的客產(chǎn)生一個(gè)新的客戶到達(dá)事件插入事

51、件表；剛到達(dá)的客戶則應(yīng)插入到當(dāng)前所含元素最少的隊(duì)列中；若該隊(duì)列戶則應(yīng)插入到當(dāng)前所含元素最少的隊(duì)列中；若該隊(duì)列在插入前為空，則還應(yīng)產(chǎn)生一個(gè)客戶離開(kāi)事件插入事在插入前為空，則還應(yīng)產(chǎn)生一個(gè)客戶離開(kāi)事件插入事件表。件表。客戶離開(kāi)事件先計(jì)算該客戶在銀行逗留的時(shí)間客戶離開(kāi)事件先計(jì)算該客戶在銀行逗留的時(shí)間,然后從隊(duì)然后從隊(duì)列中刪除該客戶后查看隊(duì)列是否空列中刪除該客戶后查看隊(duì)列是否空,若不空則設(shè)定一個(gè)若不空則設(shè)定一個(gè)新的隊(duì)頭客戶離開(kāi)事件新的隊(duì)頭客戶離開(kāi)事件.78銀行事件驅(qū)動(dòng)模擬程序算法銀行事件驅(qū)動(dòng)模擬程序算法:EventList ev;/事件表事件表Eventen;/事件事件LinkQueueq4;/4個(gè)客戶

52、隊(duì)列個(gè)客戶隊(duì)列QElemTypecustomer;/客戶記錄客戶記錄int TotalTime, CustomerNum;/累計(jì)客戶逗留時(shí)間，客戶數(shù)累計(jì)客戶逗留時(shí)間，客戶數(shù)int cmp (Event a, Event b); /依事件依事件a的發(fā)生時(shí)刻的發(fā)生時(shí)刻事件事件b的發(fā)的發(fā)生時(shí)刻分別返回生時(shí)刻分別返回-1或或0或或1void OpenForDay() /初始化操作初始化操作TotalTime=0; CustomerNum=0; /初始化累計(jì)時(shí)間和客戶數(shù)為初始化累計(jì)時(shí)間和客戶數(shù)為0InitList(ev); /初始化事件鏈表為空表初始化事件鏈表為空表en.OccurTime=0; en.

53、NType=0; /設(shè)定第一個(gè)客戶到達(dá)事件設(shè)定第一個(gè)客戶到達(dá)事件OrderInsert(ev, en, (* cmp)(); /插入事件表插入事件表for (i=0; i4; +i) InitQueue(qi); /置空隊(duì)列置空隊(duì)列 /OpenForDay79void CustomerArrived() /處理客戶到達(dá)事件，處理客戶到達(dá)事件，en.NType=0+CustomerNum;Random(durtime, intertime); /生成隨機(jī)數(shù)生成隨機(jī)數(shù)t=en.OccurTime+intertime; /下一客戶到達(dá)時(shí)刻下一客戶到達(dá)時(shí)刻if (t0i=en.NType; DelQu

54、eue(qi, customer); /刪除第刪除第i隊(duì)列的排頭客戶隊(duì)列的排頭客戶TotalTime+=en.OccurTime customer.ArrivalTime; /累計(jì)客戶逗留時(shí)間累計(jì)客戶逗留時(shí)間if (!QueueEmpty(qi) /設(shè)定第設(shè)定第i隊(duì)列的一個(gè)離隊(duì)列的一個(gè)離開(kāi)事件并插入事件表開(kāi)事件并插入事件表GetHead(qi, customer);OrderInsert (ev, (en.OccurTime+customer.Duration, i), (* cmp(); /if /CustomerDeparture81void Bank_Simulation(int Clo

55、seTime)OpenForDay; /初始化初始化while (!EmptyEventList(ev)DelFirst( GetHead(ev),p); en=GetCurElem(p);if (en.NType=0)CustomerArrived; /處理客戶到達(dá)事件處理客戶到達(dá)事件else CustomerDeparture; /處理客戶離開(kāi)事件處理客戶離開(kāi)事件/計(jì)算并輸出平均逗留時(shí)間計(jì)算并輸出平均逗留時(shí)間printf(“The Average Time is %f n”, TotalTime / CustomerNum); /Bank_Simulation82遞 歸定義定義若一個(gè)對(duì)象部

56、分地包含它自己若一個(gè)對(duì)象部分地包含它自己, 或用它或用它自己給自己定義自己給自己定義, 則稱這個(gè)對(duì)象是遞歸的；則稱這個(gè)對(duì)象是遞歸的； 若一個(gè)過(guò)程直接地或間接地調(diào)用自己若一個(gè)過(guò)程直接地或間接地調(diào)用自己, 則稱這則稱這個(gè)過(guò)程是遞歸的過(guò)程。個(gè)過(guò)程是遞歸的過(guò)程。三種遞歸情況三種遞歸情況定義是遞歸的定義是遞歸的 數(shù)據(jù)結(jié)構(gòu)是遞歸的數(shù)據(jù)結(jié)構(gòu)是遞歸的 問(wèn)題的解法是遞歸的問(wèn)題的解法是遞歸的83定義是遞歸的定義是遞歸的求解階乘函數(shù)的遞歸算法求解階乘函數(shù)的遞歸算法long Factorial ( long n ) if ( n = 0 ) return 1; else return n * Factorial (n

57、- -1);例例1.階乘函數(shù)階乘函數(shù)時(shí)時(shí)當(dāng)當(dāng)時(shí)時(shí)當(dāng)當(dāng) 1 ,)!1( 0 , 1!nnnnn84求解階乘求解階乘 n! 的過(guò)程的過(guò)程 main : fact(4)參數(shù)參數(shù) 4 計(jì)算計(jì)算 4*fact(3) 返回返回 24參數(shù)參數(shù) 3 計(jì)算計(jì)算 3*fact(2) 返回返回 6參數(shù)參數(shù) 2 計(jì)算計(jì)算 2*fact(1) 返回返回 2參數(shù)參數(shù) 1 計(jì)算計(jì)算 1*fact(0) 返回返回 1參數(shù)參數(shù) 0 直接定值直接定值 = 1 返回返回 1參參數(shù)數(shù)傳傳遞遞結(jié)結(jié)果果返返回回85例例2.計(jì)算斐波那契數(shù)列函數(shù)計(jì)算斐波那契數(shù)列函數(shù)Fib(n)的定義的定義遞歸算法遞歸算法 long Fib ( long n

58、 ) if ( n =0) return 1; if(n=1 & m=0) return 2; if(m=0 & n=2) return n+2; return ackerman(ackerman(n-1,m),m-1);88 A(nA(n，m)m)的自變量的自變量m m的每一個(gè)值都定義了一個(gè)單變量的每一個(gè)值都定義了一個(gè)單變量函數(shù)：函數(shù)： M=0M=0時(shí)，時(shí)，A(n,0)=n+2A(n,0)=n+2 M=1M=1時(shí)，時(shí)，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和，和A(1,1)=2A(1,1)

59、=2故故A(n,1)=2A(n,1)=2* *n n M=2M=2時(shí)，時(shí)，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和，和A(1,2)=A(A(0,2),1)=A(1,1)=2A(1,2)=A(A(0,2),1)=A(1,1)=2，故，故A(n,2)= 2n A(n,2)= 2n 。( (小于小于n!)n!) M=3M=3時(shí)，類似的可以推出時(shí)，類似的可以推出 ( (大于大于n n！) ) M=4M=4時(shí)，時(shí)，A(n,4)A(n,4)的增長(zhǎng)速度非?？欤灾劣跊](méi)有適當(dāng)?shù)脑鲩L(zhǎng)速度非?？欤灾劣跊](méi)有適當(dāng)?shù)臄?shù)學(xué)式子來(lái)表示這一

60、函數(shù)。的數(shù)學(xué)式子來(lái)表示這一函數(shù)。( (遠(yuǎn)遠(yuǎn)大于遠(yuǎn)遠(yuǎn)大于n n！) )n222289 定義單變量的定義單變量的AckermanAckerman函數(shù)函數(shù)A(n)A(n)為，為，A(n)=A(nA(n)=A(n，n)n)。 定義其擬逆函數(shù)定義其擬逆函數(shù)B(n)B(n)為：為：B(n)=minkB(n)=minkA(k)nA(k)n。即。即B(n)B(n)是使是使nA(k)nA(k)成立的最小的成立的最小的k k值。值。 但在理論上但在理論上B(n)B(n)沒(méi)有上界，隨著沒(méi)有上界，隨著n n的增加，它以難以想象的增加，它以難以想象的慢速度趨向正無(wú)窮大。的慢速度趨向正無(wú)窮大。 由A(0)=1,A(1)=2,A(2)=4,A(3)=16推知B(1)=0,B(2)=1,B(3)=B(4)=2和B(5)=B(16)=3。由此可以看