第3章 數(shù)據(jù)結(jié)構(gòu)-棧和隊列(天津大學)

1、棧 隊列 遞歸 第三章棧和隊列第三章棧和隊列 1 棧 ( Stack ) 定義:是限定僅在表尾進行插入或刪除操作 的線性表。 允許插入和刪除的一端 稱為棧頂(top)，另一端 稱為棧底(bottom) 特點：后進先出 (LIFO) a1 top bottom an . . . . 進棧進棧 出棧出棧 2 template class Stack public: Stack ( int sz = 10 ); /構(gòu)造函數(shù) void Push ( Type /進棧 Type Pop ( ); /出棧 Type GetTop ( ); /取棧頂元素 void MakeEmpty ( ); /置空棧 i

2、nt IsEmpty ( ) const; /判?？辗?int IsFull ( ) const; /判棧滿否 棧的表示和實現(xiàn) 順序棧：棧的順序存儲結(jié)構(gòu)，利用一組地址連續(xù) 的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素， 指針top指向棧頂元素在順序棧中的下一個位置， base為棧底指針，指向棧底的位置。 base 空棧a 進棧b 進棧 aa b top base top base top 4 toptop a b c d e e 進棧 a b c d e f 進棧溢出 a b d e 出出棧 c basebasebase top 5 #include template class Stack pr

3、ivate: int top; /棧頂指針 Type *elements; /棧元素數(shù)組 int maxSize; /棧最大容量 public: Stack ( int sz = 10 ); /構(gòu)造函數(shù) Stack ( ) delete elements; void Push ( Type /進棧 Type Pop ( ); /出棧 Type GetTop ( ); /取棧頂 void MakeEmpty ( ) top = -1; /置空棧 int IsEmpty ( ) const return top = -1; int IsFull ( ) const return top = max

4、Size-1; template Stack : Stack ( int s ) : top (-1), maxSize (s) elements = new TypemaxSize; assert ( elements != NULL ); /斷言 template void Stack : Push ( Type /先決條件斷言 elements+top = item; /加入新元素 template int stack : Pop ( ) if ( IsEmpty ( ) ) return 0; /?？詹煌藯?top-; return 1; /退出棧頂元素 template Type s

5、tack: GetTop ( ) assert ( !IsEmpty ( ) ); /先決條件斷言 return elementstop; /取出棧頂元素 b0 t0 t1 b1 0 maxSize-1 V 程序中定義多個棧程序中定義多個棧 （1）定義共享棧數(shù)據(jù)結(jié)構(gòu)）定義共享棧數(shù)據(jù)結(jié)構(gòu) #define MAX 100 int stackMAX,top1=0,top2=MAX-1; 棧1top1top2棧2 10 (2)共享進棧算法共享進棧算法 void push1(int x) if (top1top2) printf(“overflow”); else stacktop1=x;top1+;

6、void push2(int x) if(top1top2) printf(“overflow”); else stacktop2=x;top2-; 11 (3)共享出棧算法共享出棧算法 int pop1() if top1=0)printf(“underflow”);return(NULL); top1-;return(stacktop1); int pop2() if(top2=MAX-1) printf(“underflow”);return(NULL): top2+;return(stacktop2); 12 鏈式棧:棧的鏈接表示 鏈式棧無棧滿問題，空間可擴充 插入與刪除僅在棧頂處執(zhí)行

7、 鏈式棧的棧頂在鏈頭 適合于多棧操作 top 13 template class Stack; template class StackNode friend class Stack; private: Type data; /結(jié)點數(shù)據(jù) StackNode *link; /結(jié)點鏈指針 public: StackNode ( Type d = 0, StackNode *l = NULL ) : data ( d ), link ( l ) ; template class Stack private: StackNode *top; /棧頂指針 public: Stack ( ) : top

8、( NULL ) Stack ( ); void Push ( const Type /進棧 int Pop ( ); /退棧 Type *GetTop ( ); /讀取棧頂元素 void MakeEmpty ( ); /實現(xiàn)與Stack( )同 int IsEmpty ( ) return top = NULL; template Stack : Stack ( ) StackNode *p; while ( top != NULL ) /逐結(jié)點回收 p = top; top = top-link; delete p; template void Stack : Push ( const T

9、ype /新結(jié)點鏈入*top之前, 并成為新棧頂 template int Stack : Pop ( ) if ( IsEmpty ( ) ) return 0; StackNode *p = top; top = top-link; /修改棧頂指針 delete p; return 1; /釋放 template Type Stack: GetTop ( ) assert ( !IsEmpty ( ) ); return top-data; 棧的應用舉例棧的應用舉例 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換 行編輯程序行編輯程序 迷宮求解迷宮求解 表達式求值表達式求值 18 數(shù)制轉(zhuǎn)換 十進制數(shù)轉(zhuǎn)換為八進制數(shù)。采用

10、對十進制 數(shù)除8取余的方法，可得到八進制數(shù)的倒序。 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 計算順序計算順序 輸出順序輸出順序 19 void conversion () InitStack(S); scanf (%d,N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion

11、20 行編輯程序行編輯程序 在用戶輸入一行的過程中，允許在用戶輸入一行的過程中，允許 用戶輸入用戶輸入 出差錯，并在發(fā)現(xiàn)有誤時可以及時更正。出差錯，并在發(fā)現(xiàn)有誤時可以及時更正。 設立一個輸入緩沖區(qū)，用以接受用戶輸入設立一個輸入緩沖區(qū)，用以接受用戶輸入 的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū); 并假設并假設 “#”為退格符，為退格符，“”為退行符。為退行符。 假設從終端接受兩行字符：假設從終端接受兩行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+); 實際有效行為：實際有效行為： while (*s) putchar(*s+); 2

12、1 Void LineEdit() InitStack(s); ch=getchar(); while (ch != EOF) /EOF為全文結(jié)束符為全文結(jié)束符 while (ch != EOF break; case : ClearStack(S); break; / 重置重置S為空棧為空棧 default : Push(S, ch); break; ch = getchar(); / 從終端接收下一個字符從終端接收下一個字符 /while 22 將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的 數(shù)據(jù)區(qū)；數(shù)據(jù)區(qū)； ClearStack(S); / 重置重置S為空棧為空

13、棧 if (ch != EOF) ch = getchar(); /while DestroyStack(s); 23 v迷宮求解迷宮求解 通常用的是通常用的是“窮舉求解窮舉求解”的方法的方法 # # #$# # #$# # $ $# # # # # # # # # # # # 24 v迷宮路徑算法的基本思想 若當前位置“可通”，則納入路徑，繼續(xù)前 進; 若當前位置“不可通”，則后退，換方向繼 續(xù)探索; 若四周“均無通路”，則將當前位置從路徑 中刪除出去。 25 設定當前位置的初值為入口位置；設定當前位置的初值為入口位置； do 若當前位置可通，若當前位置可通， 則將當前位置插入棧頂；則將當前

14、位置插入棧頂； 若該位置是出口位置，則算法結(jié)束；若該位置是出口位置，則算法結(jié)束； 否則切換當前位置的東鄰方塊為新的否則切換當前位置的東鄰方塊為新的 當前位置；當前位置； . 26 否則否則 若棧不空且棧頂位置尚有其他方向未被探索，若棧不空且棧頂位置尚有其他方向未被探索， 則設定新的當前位置為則設定新的當前位置為: 沿順時針方向旋轉(zhuǎn)沿順時針方向旋轉(zhuǎn) 找到的棧頂位置的下一相鄰塊；找到的棧頂位置的下一相鄰塊； 若棧不空但棧頂位置的四周均不可通，若棧不空但棧頂位置的四周均不可通， 則則 刪去棧頂位置；刪去棧頂位置；/ 從路徑中刪去該通道塊從路徑中刪去該通道塊 若棧不空，則重新測試新的棧頂位置，若棧不空

15、，則重新測試新的棧頂位置， 直至找到一個可通的相鄰塊或出棧至?？罩敝琳业揭粋€可通的相鄰塊或出棧至?？? while (棧不空）；棧不空）； 27 typedef struct int ord;/序號 PosTypeseat;/坐標 int di;/方向 SElemType;/棧元素 Status MazePath (MazeType maze, PosType start, PosType end) InitStack(S); curpos=start;/當前位置 curstep=1; 28 do if (Pass(curpos) /可通過且未走過 FootPrint(curpos);/記已通

16、過標記 e=(curstep, curpos, 1); Push (S, e); if (curpos = end) return (TRUE); curpos = NextPos ( curpos, 1); curstep+; /if 29 else if (!StackEmpty(S) Pop(S, e); while (e.di=4 Pop(S,e); /記不能通過標記 /while if(e.di4) e.di+; Push(S, e); curpos = NextPos(e.seat, e.di); /if /if /else while (!StackEmpty(S); retur

17、n (FALSE); /MazePath 30 限于二元運算符的表達式定義限于二元運算符的表達式定義: 表達式表達式 := (操作數(shù)操作數(shù)) + (運算符運算符) + (操作數(shù)操作數(shù)) 操作數(shù)操作數(shù) := 簡單變量簡單變量 | 表達式表達式 簡單變量簡單變量 : = 標識符標識符 | 無符號整數(shù)無符號整數(shù) Exp = S1 + OP + S2 前綴表示法前綴表示法OP + S1 + S2 中綴表示法中綴表示法 S1 + OP + S2 后綴表示法后綴表示法 S1 + S2 + OP 表達式求值表達式求值 31 例如例如: Exp = a b + (c d / e) f 前綴式前綴式: + a

18、b c / d e f 中綴式中綴式: a b + c d / e f 后綴式后綴式: a b c d e / f + 表達式標識方法表達式標識方法 b - c a / * de f * + 32 rst1 rst2 rst3 rst4 rst5 rst6 rst1 rst2 rst3 rst4 rst5 rst6 n順序掃描表達式的每一項，根據(jù)它的類 型做如下相應操作： u若該項是操作數(shù)，則將其壓棧； u若該項是操作符，則連續(xù)從棧中 退出兩個操作數(shù)Y和X，形成運算指令 XY，并將計算結(jié)果重新壓棧。 n當表達式的所有項都掃描并處理完后， 棧頂存放的就是最后的計算結(jié)果。 步步 輸入輸入類類 型型

19、動動 作作棧內(nèi)容棧內(nèi)容 1置空棧置空?？湛?2A操作數(shù)操作數(shù) 進棧進棧A 3B操作數(shù)操作數(shù) 進棧進棧AB 4C操作數(shù)操作數(shù) 進棧進棧ABC 5D操作數(shù)操作數(shù) 進棧進棧ABCD 6- -操作符操作符 D、C 退棧退棧, 計算計算 C- -D, 結(jié)果結(jié)果 r1 進棧進棧 ABr1 7*操作符操作符 r1、B 退棧退棧, 計算計算 B*r1, 結(jié)果結(jié)果 r2 進棧進棧 Ar2 8+操作符操作符 r2、A 退棧退棧, 計算計算 A+r2, 結(jié)果結(jié)果 r3 進棧進棧 r3 步步 輸入輸入類類 型型動動 作作棧內(nèi)容棧內(nèi)容 9E操作數(shù)操作數(shù) 進棧進棧r3E 10F操作數(shù)操作數(shù) 進棧進棧r3EF 11操作符操

20、作符 F、E 退棧退棧, 計算計算 EF, 結(jié)果結(jié)果 r4 進棧進棧 r3r4 12G操作數(shù)操作數(shù) 進棧進棧r3r4G 13/操作符操作符 G、r4 退棧退棧, 計算計算 r4/E, 結(jié)果結(jié)果 r5 進棧進棧 r3r5 14+ +操作符操作符 r5、r3 退棧退棧, 計算計算 r3+r5, 結(jié)果結(jié)果 r6 進棧進棧 r6 void Calculator : Run ( ) char ch; double newoperand; while ( cin ch, ch != = ) switch ( ch ) case + : case - - : case * * : case / / : Do

21、Operator ( ch ); break; /計算計算 default : cin.putback ( ch ); /將字符放回輸入流將字符放回輸入流 cin newoperand; /讀操作數(shù)讀操作數(shù) AddOperand ( newoperand ); 算符間優(yōu)先級 / ( ) # （ ） # = c2棧外 c1棧內(nèi) 42 從中綴式求得后綴式方法從中綴式求得后綴式方法 1) 設立暫存設立暫存運算符運算符的的棧棧; 2) 設表達式的結(jié)束符為設表達式的結(jié)束符為“#”, 予設予設運算符棧運算符棧 的的棧底為棧底為“#” 3) 若若當前字符當前字符是操作數(shù)是操作數(shù)，則，則直接發(fā)送給后綴直接發(fā)送

22、給后綴 式式;(后綴與前綴式操作數(shù)的順序是相同的后綴與前綴式操作數(shù)的順序是相同的) 4) 若若當前當前運算符的運算符的優(yōu)先數(shù)高優(yōu)先數(shù)高于棧頂運算符，于棧頂運算符， 則則進棧進棧; 5) 否則，退出棧頂運算符發(fā)送給后綴式否則，退出棧頂運算符發(fā)送給后綴式; 6) “(” 對它之前后的運算符對它之前后的運算符起隔離作用起隔離作用， “)”為自左括弧開始的表達式的結(jié)束符。為自左括弧開始的表達式的結(jié)束符。 44 void postfix ( expression e ) stack s; char ch, op; s.Push ( # ); cin.Get ( ch ); while ( ! s.IsE

23、mpty( ) cin.Get ( ch ); else if ( isp ( s.GetTop( ) ) icp ( ch ) ) op = s.GetTop ( ); s.Pop( ); cout op; else op = s.GetTop ( ); s.Pop( ); if ( op = ( ) cin.Get ( ch ); 為實現(xiàn)算符優(yōu)先算法，在這里用了兩個工作棧。一個存 放算符OPTR，另一個存放數(shù)據(jù)OPND。算法思想是： （1）首先置數(shù)據(jù)棧為空棧，表達式起始符“”為算符 棧的棧底元素 （2）自左向右掃描表達式，讀到操作數(shù)進OPND棧，讀到 運算符，則和OPTR棧頂元素比較（棧頂

24、元素為c1，讀 到的算符為c2); 若c1c2,則將c1出棧，并在操作數(shù)棧取出兩個元素a和b 按c1做運算，運算結(jié)果進OPND. 重復直到表達式求值完畢。 46 例如：表達式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 （3 7 2)#

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

26、se -:c_temp1=2;break; case (:c_temp1=0;break; case ):c_temp1=5;break; case #:c_temp1=-1; 49 switch(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 *: ca

27、se /:c_temp1=4;break; case +: case -:c_temp1=2;break; case (:c_temp1=0;break; case ):c_temp1=5;break; case #:c_temp1=-1; 50 OperandType EvaluateExpression() InitStack (OPTR); Push ( OPTR,#); InitStack (OPND); c=getchar(); while (c!=#| GetTop(OPTR)!=#) if(!In(c,OP)Push(OPND,c); c=getchar(); else swit

28、ch(Precede(GetTop(OPTR),c) case :/退棧并計算 Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND, Operate(a,theta,b); break; /switch /while return GetTop(OPND); /EvaluateExpression 52 隊列 定義:只允許在表的一端進行插入，而在另 一端刪除元素的線性表。 在隊列中，允許插入的一端叫隊尾（rear） ，允許刪除的一端稱為對頭(front)。 特點：先進先出 (FIFO) a1 ，a2， a3，an 出隊列出隊列入隊列入隊列

29、隊隊 頭頭 隊隊 尾尾 53 鏈隊列：隊列的鏈式表示 鏈隊列中，有兩個分別指示隊頭和隊尾的 指針。 鏈式隊列在進隊時無隊滿問題，但有隊空 問題。 data next front rear data next front rear 54 front rear x 元素元素x入隊入隊 front rear xy 元素元素y入隊入隊 front rear xy 元素元素x出隊出隊 front rear 空隊列空隊列 front rear NULL 空隊列空隊列 55 template class Queue; template class QueueNode friend class Queue;

30、private: Type data; /隊列結(jié)點數(shù)據(jù) QueueNode *link; /結(jié)點鏈指針 public: QueueNode ( Type d=0, QueueNode *l = NULL ) : data (d), link (l) ; template class Queue private: QueueNode *front, *rear; /隊頭、隊尾指針指針 public: Queue ( ) : rear ( NULL ), front ( NULL ) Queue ( ); void EnQueue ( const Type int DeQueue ( ); Typ

31、e *GetFront ( ); void MakeEmpty ( ); /實現(xiàn)與Queue( )同 int IsEmpty ( ) const return front = NULL; ; template Queue : Queue ( ) /隊列的析構(gòu)函數(shù) QueueNode *p; while ( front != NULL ) /逐個結(jié)點釋放 p = front; front = front-link; delete p; template void Queue : EnQueue ( const Type else /隊列不空, 插入 rear = rear-link = new

32、QueueNode ( item, NULL ); template int Queue : DeQueue ( ) if ( IsEmpty ( ) ) return 0; /判隊空 QueueNode *p = front; front = front-link; delete p; return 1; template Type *Queue : GetFront ( ) if ( IsEmpty( ) ) return NULL; return 循環(huán)隊列 (Circular Queue) 順序隊列隊列的順序存儲表示。用一組地 址連續(xù)的存儲單元依次存放從隊列頭到隊列尾 的元素，指針fro

33、nt和rear分別指示隊頭元素和隊 尾元素的位置。 插入新的隊尾元素，尾指針增1，rear = rear + 1， 刪除隊頭元素，頭指針增1， front = front + 1， 因此，在非空隊列中，頭指針始終指向隊列頭元 素，而尾指針始終指向隊列尾元素的下一個位 置。 隊滿時再進隊將溢出 解決辦法：將順序隊列臆造為一個環(huán)狀的空間， 形成循環(huán)(環(huán)形)隊列 61 隊列的進隊和出隊 front rear 空隊列空隊列frontrear A,B,C, D進隊進隊 A B C D frontrear A,B出隊出隊 C D front rear E,F,G進隊進隊 C D E F G C D E F

34、 G front rear H進隊進隊,溢出溢出 62 循環(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; 0 1 23 4 5 67 循環(huán)隊列循環(huán)隊列 front rear Maxsize-1 63 0 1 2 3 4 5 67 front B CD rear 一

35、般情況一般情況 A C 0 1 23 4 5 67 隊滿隊滿(錯誤錯誤) front rear D E F G A B C H 0 1 23 4 5 67rear 空隊列空隊列 front C 0 1 23 4 5 6 7 隊滿隊滿(正確正確) front rear D E F G A B C 64 #include template class Queue private: int rear, front;/隊尾, 隊頭指針 Type *elements; /隊列元素數(shù)組 int maxSize; /最大元素個數(shù) public: Queue ( ); Queue ( ) delete ele

36、ments; void EnQueue ( const Type /進隊 int DeQueue ( ); /退隊 Type *GetFront ( ); /取隊頭元素 void MakeEmpty ( ) front = rear = 0; int IsEmpty ( ) const return front = rear; int IsFull ( ) const return (rear+1) % maxSize = front; int Length ( ) const return (rear-front+maxSize) % maxSize; template Queue: Que

37、ue ( int sz ) : front (0), rear (0), maxSize (sz) elements = new TypemaxSize; assert ( elements != NULL ); template void Queue: EnQueue ( const Type elementsrear = item; rear = (rear+1) % MaxSize; template int Queue : DeQueue ( ) if ( IsEmpty ( ) ) return 0; front = ( front+1) % MaxSize; return 1; t

38、emplate Type Queue : GetFront ( ) assert ( !IsEmpty ( ) ); return elementsfront; 隊列應用舉例隊列應用舉例 打印二項展開式打印二項展開式 (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 69 分析第分析第 i 行元素與第行元素與第 i+1行元素的關(guān)系行元素的關(guān)系 目的是從前一行的數(shù)據(jù)可以計算下一行的數(shù)據(jù)目的是從前一行的數(shù)據(jù)可

39、以計算下一行的數(shù)據(jù) 70 從第從第 i 行數(shù)據(jù)計算并存放第行數(shù)據(jù)計算并存放第 i+1 行數(shù)據(jù)行數(shù)據(jù) 71 void YANGHUI ( int n ) Queue q; /隊列初始化隊列初始化 q.MakeEmpty ( ); q.EnQueue (1); q.EnQueue (1);/預放入第一行的兩個系數(shù)預放入第一行的兩個系數(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行的行的i+2個系數(shù)個系數(shù) int t =

40、 q.DeQueue ( );/讀取系數(shù)讀取系數(shù) q.EnQueue ( s+t );/計算下一行系數(shù)，并進隊列計算下一行系數(shù)，并進隊列 s = t; if ( j != i+2 ) cout s ;/打印一個系數(shù)，第打印一個系數(shù)，第 i+2個個 為為0 72 任任務務編編號號 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)的元素 例如下表：任務的優(yōu)先權(quán)及執(zhí)行順序的關(guān)系 數(shù)字越小，優(yōu)先權(quán)越高，設不存在同優(yōu)數(shù)字越小

41、，優(yōu)先權(quán)越高，設不存在同優(yōu) 先級元素先級元素 73 #include #include #include const int maxPQSize = 50; /缺省元素個數(shù)缺省元素個數(shù) template class PQueue public: PQueue ( ); PQueue ( ) delete pqelements; void PQInsert ( const Type Type PQRemove ( ); 優(yōu)先隊列的類定義優(yōu)先隊列的類定義 74 void makeEmpty ( ) count = -1; int IsEmpty ( ) const return count = -

42、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ù) 75 template PQueue:PQueue ( ) : count (- -1) pqelements = new TypemaxPQSize; assert ( pqelements != 0 ); /分配斷言分配斷

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

44、最小元素尋找最小元素 if ( pqelementsi min ) /存于存于min min = pqelementsi; minindex = i; pqelementsminindex = pqelementscount- -1; /用最后一個元素填補要取走的最小值元素用最后一個元素填補要取走的最小值元素 count- - ;/優(yōu)先級隊列中元素個數(shù)減一優(yōu)先級隊列中元素個數(shù)減一 return min; /從隊中刪除最小值（優(yōu)先級最高）元素從隊中刪除最小值（優(yōu)先級最高）元素 77 離散事件模擬離散事件模擬 日常生活中排隊活動的模擬程序需要用到隊列和日常生活中排隊活動的模擬程序需要用到隊列和 線

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

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

47、留的平均時間。 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_Simulation 80 具

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

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

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

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

52、擬程序處理的第一 個事件，之后每個客戶到達的時刻在前一個客戶到達個事件，之后每個客戶到達的時刻在前一個客戶到達 時設定。因此在客戶到達事件發(fā)生時須先產(chǎn)生兩個隨時設定。因此在客戶到達事件發(fā)生時須先產(chǎn)生兩個隨 機數(shù)：其一為此時刻到達的客戶辦理事務所需時間機數(shù)：其一為此時刻到達的客戶辦理事務所需時間 durtime;其二為下一客戶將到達的時間間隔其二為下一客戶將到達的時間間隔intertime, 假設當前事件發(fā)生的時刻為假設當前事件發(fā)生的時刻為occurtime，則下一個客戶，則下一個客戶 到達事件發(fā)生的時刻為到達事件發(fā)生的時刻為occurtime+intertime。由此應。由此應 產(chǎn)生一個新的客

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

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

55、ist(ev); /初始化事件鏈表為空表初始化事件鏈表為空表 en.OccurTime=0; en.NType=0; /設定第一個客戶到達事件設定第一個客戶到達事件 OrderInsert(ev, en, (* cmp)(); /插入事件表插入事件表 for (i=0; i4; +i) InitQueue(qi); /置空隊列置空隊列 /OpenForDay 85 void CustomerArrived() /處理客戶到達事件，處理客戶到達事件，en.NType=0 +CustomerNum; Random(durtime, intertime); /生成隨機數(shù)生成隨機數(shù) t=en.Occu

56、rTime+intertime; /下一客戶到達時刻下一客戶到達時刻 if (t0 i=en.NType; DelQueue(qi, customer); /刪除第刪除第i隊列的排頭客戶隊列的排頭客戶 TotalTime+=en.OccurTime customer.ArrivalTime; /累計客戶逗留時間累計客戶逗留時間 if (!QueueEmpty(qi) /設定第設定第i隊列的一個離隊列的一個離 開事件并插入事件表開事件并插入事件表 GetHead(qi, customer); OrderInsert (ev, (en.OccurTime+customer.Duration, i)

57、, (* cmp(); /if /CustomerDeparture 87 void Bank_Simulation(int CloseTime) OpenForDay; /初始化初始化 while (!EmptyEventList(ev) DelFirst( GetHead(ev),p); en=GetCurElem(p); if (en.NType=0) CustomerArrived; /處理客戶到達事件處理客戶到達事件 else CustomerDeparture; /處理客戶離開事件處理客戶離開事件 /計算并輸出平均逗留時間計算并輸出平均逗留時間 printf(“The Averag

58、e Time is %f n”, TotalTime / CustomerNum); /Bank_Simulation 88 遞 歸 定義定義若一個對象部分地包含它自己若一個對象部分地包含它自己, 或用它或用它 自己給自己定義自己給自己定義, 則稱這個對象是遞歸的；則稱這個對象是遞歸的； 若一個過程直接地或間接地調(diào)用自己若一個過程直接地或間接地調(diào)用自己, 則稱這則稱這 個過程是遞歸的過程。個過程是遞歸的過程。 三種遞歸情況三種遞歸情況 定義是遞歸的定義是遞歸的 數(shù)據(jù)結(jié)構(gòu)是遞歸的數(shù)據(jù)結(jié)構(gòu)是遞歸的 問題的解法是遞歸的問題的解法是遞歸的 89 定義是遞歸的定義是遞歸的 求解階乘函數(shù)的遞歸算法求解階乘

59、函數(shù)的遞歸算法 long Factorial ( long n ) if ( n = 0 ) return 1; else return n * Factorial (n- -1); 例例1.階乘函數(shù)階乘函數(shù) 時時當當 時時當當 1 ,)!1( 0 , 1 ! n n nn n 90 求解階乘求解階乘 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

60、 直接定值直接定值 = 1 返回返回 1 參參 數(shù)數(shù) 傳傳 遞遞 結(jié)結(jié) 果果 返返 回回 91 例例2.計算斐波那契數(shù)列函數(shù)計算斐波那契數(shù)列函數(shù)Fib(n)的定義的定義 遞歸算法遞歸算法 long Fib ( long n ) if ( n = 1 ) return n; else return Fib (n- -1) + Fib (n- -2); 1n2),Fib(n1)Fib(n 0,1nn, )Fib(n 如如 F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5 92 數(shù)據(jù)結(jié)構(gòu)是遞歸的數(shù)據(jù)結(jié)構(gòu)是遞歸的 有若干結(jié)點的單鏈表有若干結(jié)點的單鏈表 例如單