第三章+棧和隊列

1、棧 隊列 遞歸第三章棧和隊列第三章棧和隊列1棧 ( Stack )定義:是限定僅在表尾進行插入或刪除操作的線性表。允許插入和刪除的一端稱為棧頂(top)，另一端稱為棧底(bottom)特點：后進先出 (LIFO)a1topbottoman.進棧進棧 出棧出棧2棧的主要操作ADT Stack /對象由數(shù)據(jù)類型為StackData的元素構(gòu)成 int Push (stack *S, StackData x); /進棧 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棧的表示和實現(xiàn)順序棧：棧的順序存儲結(jié)構(gòu)，利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，指針top指向棧頂元素在順序棧中的下一個位置，base為棧底指針，指向棧底的位置。base空棧a 進棧b 進棧aabtopbasetopbasetop4toptopabcdee 進棧abcdef 進棧溢出abde 出出棧cbasebasebasetop5順序棧的類型表示:#define STACK_INIT_SIZ

3、E 100；#define STACKINCREMENT 10；typedef char StackData;typedef struct /順序棧定義 StackData *base; /棧底指針 StackData *top; /棧頂指針int stacksize；/當前已分配的全部存儲空間 SeqStack；6判棧空int 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順序棧的基本運算順序棧的基本運算: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; /追加存儲空間 *(S-top)=x; （S-top）+;Return ok9取棧頂元素int GetTop (Se

6、qStack *S, StackData &x) /若?？辗祷?, 否則棧頂元素讀到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í)行鏈式棧的棧頂在鏈頭top12鏈式棧 (Lin

7、kStack)的定義typedef int StackData;typedef struct node StackData data; /結(jié)點 struct node *link; /鏈指針 StackNode;typedef struct StackNode *top; /棧頂指針 LinkStack;13鏈式棧操作實現(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程序中定義多個棧程序中定義多個棧（1）定義共享棧數(shù)據(jù)結(jié)構(gòu)）定義共享棧數(shù)據(jù)結(jié)構(gòu)#define MAX 100 int stackMAX,top1=0,top2=MAX-1;棧1top1top2棧217(2)共享進棧算法共享進棧算法 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)換行編輯程序行編輯程序迷宮求解迷宮求解表達式求值表達式求值20采用對十進制數(shù)除8取余的方法，可得到八進制數(shù)的倒序。 N = (N div d)d + N mod d 例如：（1348)10 = (2504)8 ，其運算過程如下：N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2計算順序計算順序輸出順序輸出順序21數(shù)制轉(zhuǎn)換十進制數(shù)轉(zhuǎ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行編輯程序行編輯程序在用戶輸入一行的過程中，允許在用戶輸入一行的過程中，允許 用戶輸入用戶輸入出差錯，并在發(fā)現(xiàn)有誤時可以及時更正。出差錯，并在發(fā)現(xiàn)有誤時可以及時更正。設(shè)立一個輸入緩沖區(qū)，用以接受用戶輸入設(shè)立一個輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū); 并假設(shè)并假設(shè)“#”為退格符，為退格符，“”為退行符。為退行符。假設(shè)從終端接受兩行字符：假設(shè)從終端接受兩行字符： whli#

13、ilr#e（s#*s) outchaputchar(*s=#+);實際有效行為：實際有效行為： 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(); / 從終端接收下一個字符從終端接收下一個字符 /while24將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的數(shù)據(jù)區(qū)；數(shù)據(jù)區(qū)；ClearStack(S); / 重置重置S為空棧為空棧if (ch != EOF) ch = getchar(); /whileDestroyStack(s);25v迷宮求解迷宮求解通常用的是通常用的是“窮舉求解窮舉求解”的方法的方法# #$# #$# $# # # # # #26v迷宮路徑算法的基本思想若當前位置“可通”，則納入路徑，繼續(xù)前進;若當前位置“不可通”，則后退，換方向繼續(xù)探索;若四周“均無通路”，則將當前位置從路

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

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

17、rstep=1;30do if (Pass(curpos) /可通過且未走過FootPrint(curpos);/記已通過標記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);/記不能通過標記/whileif(e.di4) e.di+

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

19、后綴表示法 S1 + S2 + OP表達式求值表達式求值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 + 表達式標識方法表達式標識方法b-ca/*def*+34后綴表達式求值先找運算符，再找操作數(shù)例如：例如： a b c d e / f +a bd/ec-d/e(c-d/e) f35從原表達式求得后綴式方法從原表達式求得后綴式方法設(shè)立暫存設(shè)立暫存運算符運算符的的棧棧;設(shè)表達式的結(jié)束符為設(shè)表達式的結(jié)束符為“#”, 予設(shè)予設(shè)運算符棧運算符棧的的棧底

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

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

22、作數(shù)進OPND棧，讀到運算符，則和OPTR棧頂元素比較（棧頂元素為c1，讀到的算符為c2);若c1c2,則將c1出棧，并在操作數(shù)棧取出兩個元素a和b按c1做運算，運算結(jié)果進OPND.重復(fù)直到表達式求值完畢。40例如：表達式3*(7-2),求值過程如下表：步驟步驟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)消消去括號去括號9 15 #operate(3,*,5)41為使兩個算符比較方便,給算符設(shè)置優(yōu)先級,如下表,其中c1為棧內(nèi)元素,c2為棧外元素算算符符棧內(nèi)優(yōu)先級棧內(nèi)優(yōu)先級棧外優(yōu)先級棧外優(yōu)先級* /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 :/退棧并計算Pop(OPTR,theta);Pop(OPND,b);

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

28、 nextfrontrear49frontrearx元素元素x入隊入隊frontrearxy元素元素y入隊入隊frontrearxy元素元素x出隊出隊frontrear空隊列空隊列frontrearNULL空隊列空隊列50鏈式隊列的定義typedef int QueueData;typedef struct node QueueData data; /隊列結(jié)點數(shù)據(jù) struct node *link; /結(jié)點鏈指針 QueueNode;typedef struct QueueNode *rear, *front; LinkQueue;51鏈隊列的主要操作初始化void InitQueue (

29、LinkQueue *Q ) Q-rear = Q-front = NULL;隊空int QueueEmpty ( LinkQueue *Q ) return Q-front = NULL;取隊頭元素int GetFront ( LinkQueue *Q, QueueData &x ) if ( QueueEmpty (Q) ) return 0; x = Q-front-data; return 1;52入隊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)建第一個結(jié)點 Q-front = Q-rear = p; else Q-rear-link = p; /入隊 Q-rear =p; return 1;53出隊int DeQueue ( LinkQueue *Q, QueueData &x) /刪去隊頭結(jié)點，并返回隊頭元素的值 if ( QueueEmpty (Q) ) return 0;/判隊空 QueueNode *p = Q-front; x = p-data;/保存隊頭的值 Q-front=

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

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

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

34、a=(QueueData *)malloc(MAXSIZE *sizeof(QueueData);If(! Q-data)exit(OVERFLOW); Q-rear = Q-front = 0;Return ok60判隊空int QueueEmpty ( SeqQueue *Q ) return Q-rear = Q-front;判隊滿int QueueFull ( SeqQueue *Q ) return (Q-rear+1) % QueueSize = Q-front;入隊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出隊int DeQueue ( SeqQueue *Q, QueueData &x ) if ( QueueEmpty (Q) ) return 0; x = Q-dataQ-front; Q-front = ( Q-front+1) % MAXSIZE;return 1;取隊頭int GetFront ( SeqQueue *Q, QueueData &x ) if ( QueueEmpty (Q) ) return 0; x =

36、 Q-dataQ-front; return 1;求隊列長度int QueueLength (SeqQueue *Q) return (Q-rear Q-front + MAXSIZE) % MAXSIZE;62隊列應(yīng)用舉例隊列應(yīng)用舉例 打印二項展開式打印二項展開式 (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ù)可以計算下一行的數(shù)據(jù)目的是從前一行的數(shù)據(jù)可以計算下一行的數(shù)據(jù)64從第從第 i 行數(shù)據(jù)計算并存放第行數(shù)據(jù)計算并存放第 i+1 行數(shù)據(jù)行數(shù)據(jù)65void YANGHUI ( int n ) Queue q; /隊列初始化隊列初始化 q.MakeEmpty ( ); q.EnQueue (1); q.EnQueue (1);/預(yù)放入第一行的兩個系數(shù)預(yù)放入第一行的兩個系數(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個系數(shù)個系數(shù) int t = q.DeQueue ( );/讀取系數(shù)讀取系數(shù) q.EnQueue ( s+t );/計算下一行系數(shù)，并進隊列計算下一行系數(shù)，并進隊列 s = t; if ( j != i+2 ) cout s ;/打印一個系數(shù)，第打印一個系數(shù)，第 i+2個個為為0 66 任任務(wù)務(wù)編編號號 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)先級隊列 (Priority Queue)優(yōu)先級隊列 是不同于先進先出隊列的另一種隊列。每次從隊列中取出的是具有最高優(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)先級元素先級元素67#include #include $include const int maxPQSize = 50; /缺省元素個數(shù)缺省元素個數(shù)template class PQueue public: PQueue ( ); PQueue ( ) delete pqelements; void PQInsert ( const Type & item ); Type PQRemove ( ); 優(yōu)先隊列的類定義優(yōu)先隊列的類定義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)先級隊列元優(yōu)先級隊列元素個數(shù)素個數(shù)private: Type *pqelements;/存放數(shù)組（優(yōu)先級隊列數(shù)組）存放數(shù)組（優(yōu)先級隊列數(shù)組） int count; /隊列元素計數(shù)隊列元素計數(shù) 69template PQueue:PQueue ( ) : count (- -1) pqelements = new TypemaxPQSize; assert ( pqelements

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

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

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

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

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

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

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

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

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

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

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

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

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

54、eue(qi, customer); /刪除第刪除第i隊列的排頭客戶隊列的排頭客戶TotalTime+=en.OccurTime customer.ArrivalTime; /累計客戶逗留時間累計客戶逗留時間if (!QueueEmpty(qi) /設(shè)定第設(shè)定第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; /處理客戶到達事件處理客戶到達事件else CustomerDeparture; /處理客戶離開事件處理客戶離開事件/計算并輸出平均逗留時間計算并輸出平均逗留時間printf(“The Average Time is %f n”, TotalTime / CustomerNum); /Bank_Simulation82遞 歸定義定義若一個對象部

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

57、- -1);例例1.階乘函數(shù)階乘函數(shù)時時當當時時當當 1 ,)!1( 0 , 1!nnnnn84求解階乘求解階乘 n! 的過程的過程 main : fact(4)參數(shù)參數(shù) 4 計算計算 4*fact(3) 返回返回 24參數(shù)參數(shù) 3 計算計算 3*fact(2) 返回返回 6參數(shù)參數(shù) 2 計算計算 2*fact(1) 返回返回 2參數(shù)參數(shù) 1 計算計算 1*fact(0) 返回返回 1參數(shù)參數(shù) 0 直接定值直接定值 = 1 返回返回 1參參數(shù)數(shù)傳傳遞遞結(jié)結(jié)果果返返回回85例例2.計算斐波那契數(shù)列函數(shù)計算斐波那契數(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的每一個值都定義了一個單變量的每一個值都定義了一個單變量函數(shù)：函數(shù)： M=0M=0時，時，A(n,0)=n+2A(n,0)=n+2 M=1M=1時，時，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時，時，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時，類似的可以推出時，類似的可以推出 ( (大于大于n n！) ) M=4M=4時，時，A(n,4)A(n,4)的增長速度非?？欤灾劣跊]有適當?shù)脑鲩L速度非?？欤灾劣跊]有適當?shù)臄?shù)學(xué)式子來表示這一

60、函數(shù)。的數(shù)學(xué)式子來表示這一函數(shù)。( (遠遠大于遠遠大于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)沒有上界，隨著沒有上界，隨著n n的增加，它以難以想象的增加，它以難以想象的慢速度趨向正無窮大。的慢速度趨向正無窮大。 由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。由此可以看