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

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

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

3、ivate: int top; /棧頂指針 Type *elements; /棧元素?cái)?shù)組 int maxSize; /棧最大容量 public: Stack ( int sz = 10 ); /構(gòu)造函數(shù) Stack ( ) delete elements; void Push ( Type /進(jìn)棧 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 程序中定義多個(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棧2 10 (2)共享進(jìn)棧算法共享進(jìn)棧算法 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ǔn)綏?棧的鏈接表示 鏈?zhǔn)綏o棧滿問題，空間可擴(kuò)充 插入與刪除僅在棧頂處執(zhí)行

7、 鏈?zhǔn)綏５臈ｍ斣阪滎^ 適合于多棧操作 top 13 template class Stack; template class StackNode friend class Stack; private: Type data; /結(jié)點(diǎn)數(shù)據(jù) StackNode *link; /結(jié)點(diǎn)鏈指針 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 /進(jìn)棧 int Pop ( ); /退棧 Type *GetTop ( ); /讀取棧頂元素 void MakeEmpty ( ); /實(shí)現(xiàn)與Stack( )同 int IsEmpty ( ) return top = NULL; template Stack : Stack ( ) StackNode *p; while ( top != NULL ) /逐結(jié)點(diǎn)回收 p = top; top = top-link; delete p; template void Stack : Push ( const T

9、ype /新結(jié)點(diǎn)鏈入*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; 棧的應(yīng)用舉例棧的應(yīng)用舉例 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換 行編輯程序行編輯程序 迷宮求解迷宮求解 表達(dá)式求值表達(dá)式求值 18 數(shù)制轉(zhuǎn)換 十進(jìn)制數(shù)轉(zhuǎn)換為八進(jìn)制數(shù)。采用

10、對(duì)十進(jìn)制 數(shù)除8取余的方法，可得到八進(jìn)制數(shù)的倒序。 N = (N div d)d + N mod d 例如：（1348)10 = (2504)8 ，其運(yùn)算過程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 計(jì)算順序計(jì)算順序 輸出順序輸出順序 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 行編輯程序行編輯程序 在用戶輸入一行的過程中，允許在用戶輸入一行的過程中，允許 用戶輸入用戶輸入 出差錯(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#ilr#e（s#*s) outchaputchar(*s=#+); 實(shí)際有效行為：實(shí)際有效行為： 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(); / 從終端接收下一個(gè)字符從終端接收下一個(gè)字符 /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迷宮路徑算法的基本思想 若當(dāng)前位置“可通”，則納入路徑，繼續(xù)前 進(jìn); 若當(dāng)前位置“不可通”，則后退，換方向繼 續(xù)探索; 若四周“均無通路”，則將當(dāng)前位置從路徑 中刪除出去。 25 設(shè)定當(dāng)前位置的初值為入口位置；設(shè)定當(dāng)前位置的初值為入口位置； do 若當(dāng)前位置可通，若當(dāng)前位置可通， 則將當(dāng)前位置插入棧頂；則將當(dāng)前

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

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

16、過標(biāo)記 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); /記不能通過標(biāo)記 /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 限于二元運(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í)符 | 無符號(hào)整數(shù)無符號(hào)整數(shù) Exp = S1 + OP + S2 前綴表示法前綴表示法OP + S1 + S2 中綴表示法中綴表示法 S1 + OP + S2 后綴表示法后綴表示法 S1 + S2 + OP 表達(dá)式求值表達(dá)式求值 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 + 表達(dá)式標(biāo)識(shí)方法表達(dá)式標(biāo)識(shí)方法 b - c a / * de f * + 32 rst1 rst2 rst3 rst4 rst5 rst6 rst1 rst2 rst3 rst4 rst5 rst6 n順序掃描表達(dá)式的每一項(xiàng)，根據(jù)它的類 型做如下相應(yīng)操作： u若該項(xiàng)是操作數(shù)，則將其壓棧； u若該項(xiàng)是操作符，則連續(xù)從棧中 退出兩個(gè)操作數(shù)Y和X，形成運(yùn)算指令 XY，并將計(jì)算結(jié)果重新壓棧。 n當(dāng)表達(dá)式的所有項(xiàng)都掃描并處理完后， 棧頂存放的就是最后的計(jì)算結(jié)果。 步步 輸入輸入類類 型型

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

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

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

22、給后綴 式式;(后綴與前綴式操作數(shù)的順序是相同的后綴與前綴式操作數(shù)的順序是相同的) 4) 若若當(dāng)前當(dāng)前運(yùn)算符的運(yùn)算符的優(yōu)先數(shù)高優(yōu)先數(shù)高于棧頂運(yùn)算符，于棧頂運(yùn)算符， 則則進(jìn)棧進(jìn)棧; 5) 否則，退出棧頂運(yùn)算符發(fā)送給后綴式否則，退出棧頂運(yùn)算符發(fā)送給后綴式; 6) “(” 對(duì)它之前后的運(yùn)算符對(duì)它之前后的運(yùn)算符起隔離作用起隔離作用， “)”為自左括弧開始的表達(dá)式的結(jié)束符。為自左括弧開始的表達(dá)式的結(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 ); 為實(shí)現(xiàn)算符優(yōu)先算法，在這里用了兩個(gè)工作棧。一個(gè)存 放算符OPTR，另一個(gè)存放數(shù)據(jù)OPND。算法思想是： （1）首先置數(shù)據(jù)棧為空棧，表達(dá)式起始符“”為算符 棧的棧底元素 （2）自左向右掃描表達(dá)式，讀到操作數(shù)進(jìn)OPND棧，讀到 運(yùn)算符，則和OPTR棧頂元素比較（棧頂

24、元素為c1，讀 到的算符為c2); 若c1c2,則將c1出棧，并在操作數(shù)棧取出兩個(gè)元素a和b 按c1做運(yùn)算，運(yùn)算結(jié)果進(jìn)OPND. 重復(fù)直到表達(dá)式求值完畢。 46 例如：表達(dá)式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)消消 去括號(hào)去括號(hào) 9 15 # operate(3,*,5) 10 15 # PUSH(OPTR,*) 47 為使兩個(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-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 :/退棧并計(jì)算 Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND, Operate(a,theta,b); break; /switch /while return GetTop(OPND); /EvaluateExpression 52 隊(duì)列 定義:只允許在表的一端進(jìn)行插入，而在另 一端刪除元素的線性表。 在隊(duì)列中，允許插入的一端叫隊(duì)尾（rear） ，允許刪除的一端稱為對(duì)頭(front)。 特點(diǎn)：先進(jìn)先出 (FIFO) a1 ，a2， a3，an 出隊(duì)列出隊(duì)列入隊(duì)列入隊(duì)列

29、隊(duì)隊(duì) 頭頭 隊(duì)隊(duì) 尾尾 53 鏈隊(duì)列：隊(duì)列的鏈?zhǔn)奖硎?鏈隊(duì)列中，有兩個(gè)分別指示隊(duì)頭和隊(duì)尾的 指針。 鏈?zhǔn)疥?duì)列在進(jìn)隊(duì)時(shí)無隊(duì)滿問題，但有隊(duì)空 問題。 data next front rear data next front rear 54 front rear x 元素元素x入隊(duì)入隊(duì) front rear xy 元素元素y入隊(duì)入隊(duì) front rear xy 元素元素x出隊(duì)出隊(duì) front rear 空隊(duì)列空隊(duì)列 front rear NULL 空隊(duì)列空隊(duì)列 55 template class Queue; template class QueueNode friend class Queue;

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

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

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

33、nt和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ì)列 61 隊(duì)列的進(jìn)隊(duì)和出隊(duì) front rear 空隊(duì)列空隊(duì)列frontrear A,B,C, D進(jìn)隊(duì)進(jìn)隊(duì) A B C D frontrear A,B出隊(duì)出隊(duì) C D front rear E,F,G進(jìn)隊(duì)進(jìn)隊(duì) C D E F G C D E F

34、 G front rear H進(jìn)隊(duì)進(jìn)隊(duì),溢出溢出 62 循環(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; 0 1 23 4 5 67 循環(huán)隊(duì)列循環(huán)隊(duì)列 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 隊(duì)滿隊(duì)滿(錯(cuò)誤錯(cuò)誤) front rear D E F G A B C H 0 1 23 4 5 67rear 空隊(duì)列空隊(duì)列 front C 0 1 23 4 5 6 7 隊(duì)滿隊(duì)滿(正確正確) front rear D E F G A B C 64 #include template class Queue private: int rear, front;/隊(duì)尾, 隊(duì)頭指針 Type *elements; /隊(duì)列元素?cái)?shù)組 int maxSize; /最大元素個(gè)數(shù) public: Queue ( ); Queue ( ) delete ele

36、ments; void EnQueue ( const Type /進(jìn)隊(duì) int DeQueue ( ); /退隊(duì) Type *GetFront ( ); /取隊(duì)頭元素 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; 隊(duì)列應(yīng)用舉例隊(duì)列應(yīng)用舉例 打印二項(xiàng)展開式打印二項(xià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 69 分析第分析第 i 行元素與第行元素與第 i+1行元素的關(guān)系行元素的關(guān)系 目的是從前一行的數(shù)據(jù)可以計(jì)算下一行的數(shù)據(jù)目的是從前一行的數(shù)據(jù)可

39、以計(jì)算下一行的數(shù)據(jù) 70 從第從第 i 行數(shù)據(jù)計(jì)算并存放第行數(shù)據(jù)計(jì)算并存放第 i+1 行數(shù)據(jù)行數(shù)據(jù) 71 void 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行的行的i+2個(gè)系數(shù)個(gè)系數(shù) int t =

40、 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 72 任任務(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)越高，設(shè)不存在同優(yōu)數(shù)字越小

41、，優(yōu)先權(quán)越高，設(shè)不存在同優(yōu) 先級(jí)元素先級(jí)元素 73 #include #include #include const int maxPQSize = 50; /缺省元素個(gè)數(shù)缺省元素個(gè)數(shù) template class PQueue public: PQueue ( ); PQueue ( ) delete pqelements; void PQInsert ( const Type Type PQRemove ( ); 優(yōu)先隊(duì)列的類定義優(yōu)先隊(duì)列的類定義 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)先級(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ù) 75 template PQueue:PQueue ( ) : count (- -1) pqelements = new TypemaxPQSize; assert ( pqelements != 0 ); /分配斷言分配斷

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

44、最小元素尋找最小元素 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í)最高）元素 77 離散事件模擬離散事件模擬 日常生活中排隊(duì)活動(dòng)的模擬程序需要用到隊(duì)列和日常生活中排隊(duì)活動(dòng)的模擬程序需要用到隊(duì)列和 線

45、性表的數(shù)據(jù)結(jié)構(gòu)，是隊(duì)列的典型應(yīng)用。線性表的數(shù)據(jù)結(jié)構(gòu)，是隊(duì)列的典型應(yīng)用。 設(shè)銀行有四個(gè)窗口，從開門起每個(gè)窗口一個(gè)時(shí)刻設(shè)銀行有四個(gè)窗口，從開門起每個(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í)間。 78 思路：思路： 1. 為求平均時(shí)間要知道每個(gè)客戶到達(dá)和離為求平均時(shí)間

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

47、留的平均時(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; /處理客戶離開處理客戶離開 事件事件 default: Invalid; /switch /while CloseForDay; /計(jì)算平均逗留時(shí)間計(jì)算平均逗留時(shí)間 /Bank_Simulation 80 具

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

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

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

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

52、擬程序處理的第一 個(gè)事件，之后每個(gè)客戶到達(dá)的時(shí)刻在前一個(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è)新的客

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

54、ev;/事件表事件表 Eventen;/事件事件 LinkQueueq4;/4個(gè)客戶隊(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或或1 void OpenForDay() /初始化操作初始化操作 TotalTime=0; CustomerNum=0; /初始化累計(jì)時(shí)間和客戶數(shù)為初始化累計(jì)時(shí)間和客戶數(shù)為0 InitL

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

56、rTime+intertime; /下一客戶到達(dá)時(shí)刻下一客戶到達(dá)時(shí)刻 if (t0 i=en.NType; DelQueue(qi, customer); /刪除第刪除第i隊(duì)列的排頭客戶隊(duì)列的排頭客戶 TotalTime+=en.OccurTime customer.ArrivalTime; /累計(jì)客戶逗留時(shí)間累計(jì)客戶逗留時(shí)間 if (!QueueEmpty(qi) /設(shè)定第設(shè)定第i隊(duì)列的一個(gè)離隊(duì)列的一個(gè)離 開事件并插入事件表開事件并插入事件表 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; /處理客戶到達(dá)事件處理客戶到達(dá)事件 else CustomerDeparture; /處理客戶離開事件處理客戶離開事件 /計(jì)算并輸出平均逗留時(shí)間計(jì)算并輸出平均逗留時(shí)間 printf(“The Averag

58、e Time is %f n”, TotalTime / CustomerNum); /Bank_Simulation 88 遞 歸 定義定義若一個(gè)對(duì)象部分地包含它自己若一個(gè)對(duì)象部分地包含它自己, 或用它或用它 自己給自己定義自己給自己定義, 則稱這個(gè)對(duì)象是遞歸的；則稱這個(gè)對(duì)象是遞歸的； 若一個(gè)過程直接地或間接地調(diào)用自己若一個(gè)過程直接地或間接地調(diào)用自己, 則稱這則稱這 個(gè)過程是遞歸的過程。個(gè)過程是遞歸的過程。 三種遞歸情況三種遞歸情況 定義是遞歸的定義是遞歸的 數(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ù) 時(shí)時(shí)當(dāng)當(dāng) 時(shí)時(shí)當(dāng)當(dāng) 1 ,)!1( 0 , 1 ! n n nn n 90 求解階乘求解階乘 n! 的過程的過程 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

60、 直接定值直接定值 = 1 返回返回 1 參參 數(shù)數(shù) 傳傳 遞遞 結(jié)結(jié) 果果 返返 回回 91 例例2.計(jì)算斐波那契數(shù)列函數(shù)計(jì)算斐波那契數(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é)點(diǎn)的單鏈表有若干結(jié)點(diǎn)的單鏈表 例如單