數(shù)據(jù)結(jié)構(gòu)課件2009級chapter

1、第3章 棧和隊(duì)列棧棧與遞歸 隊(duì)列 優(yōu)先級隊(duì)列 3.1 棧 ( Stack )只允許在一端插入和刪除的線性表。a0an-1an-2topbottom允許插入和刪除的一端稱為棧頂(top)，另一端稱為棧底(bottom)特點(diǎn) 后進(jìn)先出 (LIFO)template class Stack public: Stack ( int sz = 10 ); /構(gòu)造函數(shù) void Push (Type x); /進(jìn)棧 int Pop (Type& x); /出棧 int GetTop (Type& x); /取棧頂元素 void MakeEmpty ( ); /置空棧 int IsEmpty ( ) con

2、st; /判?？辗?int IsFull ( ) const; /判棧滿否棧的抽象數(shù)據(jù)類型template class Stack private: int top; /棧頂指針 Type *elements; /棧元素?cái)?shù)組 int maxSize; /棧最大容量 void overflowProcess( ); /棧的溢出處理0 1 2 3 4 5 6 7 8 9 maxSize-1top (?？?elements棧的數(shù)組存儲表示 順序棧top (棧滿) public: Stack (int sz = 10); /構(gòu)造函數(shù) Stack ( ) delete elements; void Pu

3、sh (Type x); /進(jìn)棧 int Pop (Type& x); /出棧 Type GetTop ( ); /取棧頂 void MakeEmpty ( ) top = -1; /置空棧 int IsEmpty ( ) const return top = -1; int IsFull ( ) const return top = maxSize-1; top空棧toptoptoptoptopa 進(jìn)棧b 進(jìn)棧aababcdee 進(jìn)棧abcdef 進(jìn)棧溢出abdee 退棧ctopc 退棧b 退棧abaa 退?？諚opabdd 退棧ctopabctoptoptemplate void Seq

4、Stack:overflowProcess( ) /私有函數(shù)：當(dāng)棧滿則執(zhí)行擴(kuò)充棧存儲空間處理 T *newArray = new E2*maxSize;/創(chuàng)建更大的存儲數(shù)組 for (int i = 0; i = top; i+) newArrayi = elementsi; maxSize += maxSize; delete elements; elements = newArray; /改變elements指針; template void SeqStack:Push(T x) /若棧不滿, 則將元素x插入該棧棧頂, 否則溢出處理 if (IsFull() = true) overflo

5、wProcess; /棧滿 elements+top = x; template bool SeqStack:Pop(T& x) /函數(shù)退出棧頂元素并返回棧頂元素的值 if (IsEmpty() = true) return false; x = elementstop-; return true; /退棧成功; template bool Seqstack:getTop(T& x) /若棧不空則函數(shù)返回該棧棧頂元素的地址 if (IsEmpty() = true) return false; x = elementstop; return true;算法分析：GetTop( ) / 取棧頂元

6、素Push( ) /入棧操作Pop( ) /出棧操作O(1)雙棧共享一個?？臻gb0 t0 t1 b10 maxSize-1V初始 t0 = b0 = -1 t1 = b1 = ？ 棧滿條件：maxSizet0+1 = t1t0 = b0或t1 = b1 ?？諚l件： if ( DS.t0+1 = DS.t1 ) return 0; if ( i = 0 ) DS.t0+; else DS.t1-; DS.VDS.ti = x; return 1; if ( DS.ti = DS.bi ) return 0; x = DS.VDS.ti; if ( i = 0 ) DS.t0-; else DS.

7、t1+; return 1; int push ( DualStack& DS, Type x, int i)int Pop (DualStack& DS, Type& x, int i)例：多進(jìn)制輸出（將十進(jìn)制轉(zhuǎn)換成其它進(jìn)制）算法：以B進(jìn)制形式輸出1.nB,結(jié)果壓入棧S中；2.n的剩余部分為n/B,用n/B代替n;3.重復(fù)上述過程1和2直到n=0;4.從棧中彈出并打印所有數(shù)字。5310125124023122021棧的鏈接存儲表示 鏈?zhǔn)綏ｆ準(zhǔn)綏５臈ｍ斣阪滎^；插入與刪除僅在棧頂處執(zhí)行;鏈?zhǔn)綏o棧滿問題，空間可擴(kuò)充；適合于多棧操作。toptemplate class Stack;template

8、 class StackNode friend class Stack;private: Type data; /結(jié)點(diǎn)數(shù)據(jù) StackNode *link; /結(jié)點(diǎn)鏈指針public: StackNode ( T d = 0, StackNode * next = NULL ) : data (d), link (next) ; 鏈?zhǔn)綏?(LinkedStack)類的定義template class LinkedStack : public Stack /鏈?zhǔn)綏ｎ惗x private: StackNode *top; /棧頂指針 void output(ostream& os, StackNo

9、de *ptr, int& i); /遞歸輸出棧的所有元素public: LinkedStack() : top(NULL) /構(gòu)造函數(shù) LinkedStack() makeEmpty(); /析構(gòu)函數(shù) void Push(E x); /進(jìn)棧 bool Pop(E& x); /退棧 bool getTop(E& x) const;/取棧頂 bool IsEmpty() const return top = NULL; void makeEmpty();/清空棧的內(nèi)容 int k = 1; friend ostream& operator (ostream& os, LinkedStack& s

10、) output(os, s.top, k); /輸出棧元素的重載操作 ;棧的應(yīng)用(一) : 括號匹配字符串: (a*(b+c)-d)目的: 輸入字符串,輸出匹配的括號和沒有匹配的括號算法基本思想:從左到右掃描,把遇到的左括號存放在棧中;每當(dāng)在后續(xù)的掃描過程中遇到一個右括號時,就將它與棧頂?shù)淖罄ㄌ栂嗥ヅ?并在棧頂刪除該左括號。#include #include #include #include “stack.h”const int maxLength = 100;void PrintMatchedPairs(char * expression) stack s(maxLength); int

11、 j, length = strlen(expression); for (int i = 1;ilength; i+) if (expressioni-1=() s.Push(i); /左括號, 位置進(jìn)棧 else if (expressioni-1=) /右括號 if (s.Pop(j) = true) /棧不空,退棧成功 coutj“與”i“匹配”endl; else cout“沒有與第”i”個右括號匹配的左括號!”endl; while (s.IsEmpty( ) = false) s.Pop(j); cout.endl; ?/棧中還有左括號沒有與第”j“個左括號相匹配的右括號!”棧的

12、應(yīng)用 (二)：表達(dá)式計(jì)算一個表達(dá)式由操作數(shù)(亦稱運(yùn)算對象)、操作符 (亦稱運(yùn)算符) 和分界符組成。算術(shù)表達(dá)式有三種表示：中綴(infix)表示 ，如 A+B；前綴(prefix)表示 ，如 +AB；后綴(postfix)表示 ，如 AB+；一般表達(dá)式的操作符有4種類型：算術(shù)操作符 如雙目操作符（+、-、*、/ 和%）以及單目操作符（-）; 關(guān)系操作符 包括、=、。這些操作符主要用于比較; 邏輯操作符 如與(&)、或(|)、非(!); 括號(和) 它們的作用是改變運(yùn)算順序。 表達(dá)式中相鄰兩個操作符的計(jì)算次序?yàn)椋?優(yōu)先級高的先計(jì)算； 優(yōu)先級相同的自左向右計(jì)算； 當(dāng)使用括號時從最內(nèi)層括號開始計(jì)算;如

13、：中綴表達(dá)式 a + b * ( c - d ) - e / f后綴表達(dá)式 a b c d - * + e f / -從左向右順序地掃描表達(dá)式，并用一個棧暫存掃描到的操作數(shù)或計(jì)算結(jié)果。在后綴表達(dá)式的計(jì)算順序中已隱含了加括號的優(yōu)先次序，括號在后綴表達(dá)式中不出現(xiàn)。應(yīng)用后綴表示計(jì)算表達(dá)式的值rst1rst2rst3rst4rst5rst6計(jì)算例 a b c d - * + e f g / -通過后綴表示計(jì)算表達(dá)式值的過程順序掃描表達(dá)式的每一項(xiàng)，根據(jù)它的類型做如下相應(yīng)操作：若該項(xiàng)是操作數(shù)，則將其壓棧；若該項(xiàng)是操作符，則連續(xù)從棧中退出兩個操作數(shù)Y和X，形成運(yùn)算指令XY，并將計(jì)算結(jié)果重新壓棧。當(dāng)表達(dá)式的所

14、有項(xiàng)都掃描并處理完后，棧頂存放的就是最后的計(jì)算結(jié)果。后綴表達(dá)式：ABCD - * + EF G / -void Calculator : Run ( ) char ch; double newoperand; while ( cin ch&ch != ; ) switch ( ch ) case + : case - : case * : case / : DoOperator ( ch ); break; /計(jì)算 default : cin.putback ( ch ); /將字符放回輸入流 cin newoperand; /讀操作數(shù) S.Push( newoperand ); void D

15、oOperator ( char op ) /從棧S中取兩個操作數(shù)，形成運(yùn)算指令并計(jì)算進(jìn)棧 double left, right; int succ = S.GetTop( right ); S.Pop( ); if ( succ ) succ = S.GetTop( left ); S.Pop( ); if ( !succ ) return; /退出兩個操作數(shù) switch ( op ) case +: S.Push ( left + right); break; /加 case -: S.Push ( left - right); break; /減 case *: S.Push ( le

16、ft * right); break; /乘 case /: if ( right != 0.0 ) S.Push ( left / right); /除 else cout “除數(shù)為0!n” ); exit(1); 中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式 中綴表達(dá)式 a + b * ( c - d ) - e / f后綴表達(dá)式 a b c d - * + e f / -C+中操作符的優(yōu)先級 優(yōu)先級 操作符 1 單目-、！ 2 *、/、% 3 +、- 4 、= 5 =、!= 6 & 7 | 中綴表達(dá)式 a + b * ( c - d ) - e / f后綴表達(dá)式 a b c d - * + e f / -

17、過程：利用棧各個算術(shù)操作符的優(yōu)先級isp叫做棧內(nèi)(in stack priority)優(yōu)先數(shù)。icp叫做棧外(in coming priority)優(yōu)先數(shù)。* +icp(*)isp(+)icp(+) isp(棧頂?shù)牟僮鞣?,掃描到的操作符進(jìn)棧； icp(掃描到的操作符) isp (op)，令ch進(jìn)棧，讀入下一個字符ch。 若 icp (ch) isp (op)，退棧并輸出。 若 icp (ch) = isp (op)，退棧但不輸出，若退出的是“(”號, 讀入下一個字符ch。 算法結(jié)束，輸出序列即為所需的后綴表達(dá)式。如：A + B * ( C - D ) - E /Fvoid postfix (

18、 expression e ) stack s; char ch, op; s.Push ( # ); cin.Get ( ch ); while ( ! s.IsEmpty( ) & ch != # ) if ( isdigit ( ch ) ) cout ch; 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 ); 算法分析：

19、設(shè)表達(dá)式中符號的總數(shù)為nO(n)3.2 棧與遞歸3.2.1 遞歸的概念冪函數(shù)：xnS(n)=i=1+2+3+n如果已經(jīng)求得xn或S(n), 計(jì)算xn+1或S(n+1)時？定義是遞歸的求解階乘函數(shù)的遞歸算法long Factorial ( long n ) if ( n = 0 ) return 1; else return n * Factorial (n-1);例如，階乘函數(shù)主程序 main : fact(4)參數(shù) 4 計(jì)算 4*fact(3)參數(shù) 3 計(jì)算 3*fact(2)參數(shù) 2 計(jì)算 2*fact(1)參數(shù) 1 計(jì)算 1*fact(0)參數(shù) 0 直接定值 = 1參數(shù)傳遞結(jié)果返回遞歸調(diào)

20、用回歸求值112624求解階乘 n! 的過程遞歸的定義: 若一個對象部分地包含它自己, 或用它自己給自己定義, 則稱這個對象是遞歸的； 若一個過程直接地或間接地調(diào)用自己, 則稱這個過程是遞歸的過程。以下三種情況常常用到遞歸方法:定義是遞歸的 數(shù)據(jù)結(jié)構(gòu)是遞歸的 問題的解法是遞歸的 數(shù)據(jù)結(jié)構(gòu)是遞歸的 一個結(jié)點(diǎn)，它的指針域?yàn)镹ULL，是一個單鏈表; 一個結(jié)點(diǎn)，它的指針域指向單鏈表，仍是一個單鏈表。 例如，單鏈表結(jié)構(gòu)f f 例1：搜索鏈表最后一個結(jié)點(diǎn)并打印其數(shù)值f f f f f a0a1a2a3a4遞歸找鏈尾template void Print ( ListNode *f ) if ( f -li

21、nk = NULL ) cout data link );f f f f 遞歸找含x值的結(jié)點(diǎn)xtemplate void Print ( ListNode *f, Type& x ) if ( f != NULL ) if ( f - data = x ) cout data link, x );例2:在鏈表中尋找等于給定值的結(jié)點(diǎn)并打印其數(shù)值遞歸定義是遞歸的 數(shù)據(jù)結(jié)構(gòu)是遞歸的 問題的解法是遞歸的 問題的解法是遞歸的漢諾塔(Tower of Hanoi)問題：設(shè)A柱上最初的盤子總數(shù)為n,hanoi(n,A,B,C)如果 n = 1，則將這一個盤子直接從 A 柱移到 C 柱上。 將 A 柱上最后一

22、個盤子直接移到 C 柱上； 用 A 柱做過渡，將 B 柱上的 (n-1) 個盤子移到 C 柱上。否則，執(zhí)行以下三步： 用 C 柱做過渡，將 A 柱上的 (n-1) 個盤子移到 B 柱上； #include #include strclass.h”void Hanoi (int n, String A, String B, String C) /解決漢諾塔問題的算法 if ( n = 1 ) cout move A to C endl; else Hanoi ( n-1, A, C, B ); cout move A to C endl; Hanoi ( n-1, B, A, C ); 構(gòu)成遞歸

23、的條件不能無限制地調(diào)用本身，必須有一個出口，化簡為非遞歸狀況直接處理。 Procedure ( ) if ( ) return ( initial value ); else return ( ( parameter exchange ); 3.2.2 遞歸過程與遞歸工作棧遞歸過程在實(shí)現(xiàn)時，需要自己調(diào)用自己。如：n!long Factorial ( long n ) if ( n = 0 ) return 1; else return n * Factorial (n-1);求解階乘 n! 的過程主程序 main : fact(4)參數(shù) 4 計(jì)算 4*fact(3)參數(shù) 3 計(jì)算 3*fact

24、(2)參數(shù) 2 計(jì)算 2*fact(1)參數(shù) 1 計(jì)算 1*fact(0)參數(shù) 0 直接定值 = 1參數(shù)傳遞結(jié)果返回遞歸調(diào)用回歸求值112624主程序第一次調(diào)用遞歸過程為外部調(diào)用；遞歸過程每次遞歸調(diào)用自己為內(nèi)部調(diào)用。必須解決：調(diào)用時的參數(shù)傳遞和返回地址問題調(diào)用結(jié)束時返回的方式不同遞歸工作棧每層遞歸調(diào)用：需保存的信息.遞歸工作記錄局部變量返回地址參數(shù)的副本空間遞歸工作記錄 按后進(jìn)先出的棧組織活動記錄框架函數(shù)遞歸時的活動記錄.Function() .調(diào)用塊函數(shù)塊 參數(shù) 返回地址(下一條指令) 返回值 void main ( ) int n; n = Factorial (4);RetLoc1 lo

25、ng Factorial ( long n ) int temp; if ( n = 0 ) return 1; else temp = n * Factorial (n-1); RetLoc2 return temp; 以 Factorial(n) 為例：計(jì)算Fact時活動記錄的內(nèi)容遞歸調(diào)用序列0 1 RetLoc21 1 RetLoc22 2 RetLoc23 6 RetLoc24 24 RetLoc1參數(shù) 返回值 返回地址 返回時的指令return 4*6 /返回 24 return 3*2 /返回 6 return 1 /返回 1 return 1*1 /返回 1 return 2*1

26、 /返回 2 但是，遞歸并不是一種高效的方法如：計(jì)算斐波那契數(shù)列的函數(shù)Fib(n)long Fib ( long n ) if ( n = 1 ) return n; else return Fib (n-1) + Fib (n-2); 調(diào)用次數(shù) NumCall(k) =？斐波那契數(shù)列的遞歸調(diào)用樹Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)2*Fib(k+1) - 1算法的時間復(fù)雜度：O(2n)用循環(huán)實(shí)現(xiàn)斐波那契數(shù)列l(wèi)ong FibIter ( long n

27、) if ( n = 1 ) return n; long twoback = 0, oneback = 1, Current; for ( int i = 2; i = n; i+ ) Current = twoback + oneback; twoback = oneback; oneback = Current; return Current;算法的時間復(fù)雜度：O(n)遞歸過程改為非遞歸過程遞歸過程簡潔、易編、易懂；效率低，重復(fù)計(jì)算多；非遞歸過程方法：單向遞歸和尾遞歸：直接用迭代實(shí)現(xiàn) 其他情形：借助棧 實(shí)現(xiàn)單向遞歸和尾遞歸：用迭代法實(shí)現(xiàn)單向遞歸：斐波那契數(shù)列l(wèi)ong Fib ( long

28、 n ) if ( n = 1 ) return n; else return Fib (n-1) + Fib (n-2); long FibIter ( long n ) if ( n = 1 ) return n; long twoback = 0, oneback = 1, Current; for ( int i = 2; i = 0 ) cout An = 0 ) cout value An endl; n-; 3.2.3 用回溯法求解迷宮問題迷宮的表示：mazem+2p+2 001000110001111111 .入口出口mazeij=1 墻壁mazeij=0 通路所走過的路徑信息

29、：struct itemsint x,y,dir; /位置和前進(jìn)方向;前進(jìn)方向表：qmoveq.amoveq.bN-10NE-11E01SE11S10SW1-1W0-1NW-1-1enum direction N,NE,E,SE,S,SW,NWstruct offsetint a,b;/a-y /bx;offset move8;迷宮問題非遞歸解法用到的數(shù)據(jù)結(jié)構(gòu)mazeij:迷宮描述數(shù)據(jù)items:當(dāng)前位置的坐標(biāo)和來向stack st(m*p) markij：標(biāo)識，是否走過（=0，未走過）offset move8:各個方向的偏移表迷宮問題非遞歸解法讀入迷宮數(shù)據(jù)mazeij 初始化工作棧，迷宮入口

30、坐標(biāo)和前進(jìn)方向，并進(jìn)棧； 初始化mark數(shù)組為0 while (棧非空) pop( ) = (i,j,dir);/從棧頂退出的坐標(biāo)和方向； while (還有其他方向可移動) g=i+movedir.a;h=j+movedir.b;/(g,h):下一坐標(biāo)； if (g=m&h=p) 迷宮搜索成功；/出口在mazemp if (!mazegh&!markgh) markgh=1; dir=dir+1;/下一次將要移動的方向； (i,j,dir) 進(jìn)棧； i=g;j=h;dir=N;/當(dāng)前位置：gh,方向初始為N else dir+; / 回到外循環(huán) 3.3 隊(duì)列a0 a1 a2 an-1fron

31、trear定義隊(duì)列是只允許在一端刪除，在另一端插入的線性表。允許刪除的一端叫做隊(duì)頭(front)，允許插入的一端叫做隊(duì)尾(rear)。特性 先進(jìn)先出(FIFO, First In First Out)template class Queue public: Queue (int = 10); /構(gòu)造函數(shù) void EnQueue (Type x); /進(jìn)隊(duì) int DeQueue (Type& x); /出隊(duì)列 int GetFront (Type& x); /取隊(duì)頭元素值 void MakeEmpty ( ); /置空隊(duì)列 int IsEmpty ( ) const ; /判隊(duì)列空否 int

32、 IsFull ( ) const; /判隊(duì)列滿否隊(duì)列的抽象數(shù)據(jù)類型隊(duì)列的順序存儲表示#include template class Queue private: int rear, front;/隊(duì)尾, 隊(duì)頭指針 Type *elements; /隊(duì)列元素?cái)?shù)組 int maxSize; /最大元素個數(shù)public: Queue (int sz = 10); Queue ( ) delete elements; void EnQueue (Type x); /進(jìn)隊(duì)隊(duì)列的進(jìn)隊(duì)和出隊(duì) frontrear空隊(duì)列frontrearA進(jìn)隊(duì)AfrontrearB進(jìn)隊(duì)A BfrontrearC, D進(jìn)隊(duì)A

33、B C DfrontrearA退隊(duì)B C DfrontrearB退隊(duì)C DfrontrearE,F,G進(jìn)隊(duì)C D E F GC D E F GfrontrearH進(jìn)隊(duì),溢出frontrearB進(jìn)隊(duì)A BfrontrearC, D進(jìn)隊(duì)A B C DfrontrearA退隊(duì)B C DfrontrearB退隊(duì)C DfrontrearE,F,G進(jìn)隊(duì)C D E F GC D E F GfrontrearH進(jìn)隊(duì),溢出隊(duì)列的進(jìn)隊(duì)和出隊(duì) 初始化： front=rear= -1 進(jìn)隊(duì)時： rear = rear + 1，再將新元素按 rear 指示位置加入；隊(duì)尾指針指示實(shí)際隊(duì)尾位置。出隊(duì)時：front = fr

34、ont + 1，隊(duì)頭指針指示實(shí)際隊(duì)頭的前一位置，再將下標(biāo)為 front 的元素取。 隊(duì)滿時：rear = maxsize 1;再進(jìn)隊(duì)將溢出（假溢出） ； 隊(duì)空時:front = rear;再出隊(duì)將隊(duì)空處理。 隊(duì)列的順序存儲表示循環(huán)隊(duì)列（ Circular Queue）01234567front01234567front01234567frontrearAABCrearrear空隊(duì)列A進(jìn)隊(duì)B, C進(jìn)隊(duì)0123456701234567A退隊(duì)B退隊(duì)01234567D,E,F,G,H,I 進(jìn)隊(duì)frontBCrearAfrontBCrearfrontCrearDEFGHI隊(duì)列存放數(shù)組被當(dāng)作首尾相接的表處

35、理。當(dāng)隊(duì)頭、隊(duì)尾指針加1進(jìn)到maxsize 1 后，再前進(jìn)一個位置就自動到0，可用取模(余數(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 循環(huán)隊(duì)列 (Circular Queue)01234567frontCrearDEFGH(rear+1) % maxSize = front 01234567frontCrearDEFGHI如果是： rea

36、r= front ？01234567frontrearAA int DeQueue (Type& x); /退隊(duì) int GetFront (Type& x); /取隊(duì)頭元素 void MakeEmpty ( ) front = rear = 0; int IsEmpty ( ) const return front = rear; int IsFull ( ) const return (rear+1) % maxSize = front; int Length ( ) const return ;循環(huán)隊(duì)列其他操作的定義(rear-front+maxSize) % maxSizetempla

37、te int Queue : DeQueue (Type& x) if ( IsEmpty ( ) ) return 0; front = (front+1) % maxSize; x = elementsfront; return 1;template int Queue : GetFront (Type& x) if ( IsEmpty ( ) ) return 0; x = elements( front+1) % maxSize; return 1;隊(duì)列的鏈接存儲表示 鏈?zhǔn)疥?duì)列隊(duì)頭在鏈頭，隊(duì)尾在鏈尾。鏈?zhǔn)疥?duì)列在進(jìn)隊(duì)時無隊(duì)滿問題，但有隊(duì)空問題。隊(duì)空條件為 front = NULL 。fr

38、ontreartemplate class Queue;template class QueueNode friend class Queue;private: Type data; /隊(duì)列結(jié)點(diǎn)數(shù)據(jù) QueueNode *link; /結(jié)點(diǎn)鏈指針public: QueueNode ( Type d = 0, QueueNode *next = NULL ) : data (d), link (next) ; 鏈?zhǔn)疥?duì)列類的定義template class Queue private: QueueNode *front, *rear; /隊(duì)頭、隊(duì)尾指針指針public: Queue ( ) : r

39、ear ( NULL ), front ( NULL ) Queue ( ); void EnQueue (Type x); int DeQueue (Type& x); int GetFront (Type& x); void MakeEmpty ( ); /實(shí)現(xiàn)與Queue( )同 int IsEmpty ( ) const return front = NULL; ; template Queue : Queue ( ) /隊(duì)列的析構(gòu)函數(shù) QueueNode *p; while ( front != NULL ) /逐個結(jié)點(diǎn)釋放 p = front; front = front-link

40、; delete p; template void Queue : EnQueue (Type item) /將新元素item插入到隊(duì)列的隊(duì)尾 if ( front = NULL ) /創(chuàng)建第一個結(jié)點(diǎn)front = rear = new QueueNode (item, NULL); else /隊(duì)列不空, 插入 rear-link = new QueueNode (item, NULL); rear = rear-link;template Type Queue : DeQueue ( ) if ( IsEmpty ( ) ) return 0; /判隊(duì)空 QueueNode *p = fr

41、ont; Type x = front-data; front = front-link; delete p; return x;template Type Queue : GetFront ( ) if ( IsEmpty ( ) ) return 0; Type x = front-data; return x; 算法分析：入隊(duì)：出隊(duì)：O(1)O(1)隊(duì)列的應(yīng)用舉例 逐行打印 二項(xiàng)展開式 (a + b)i 的系數(shù)楊輝三角形 (Pascals triangle)分析第 i 行元素與第 i+1行元素的關(guān)系i = 2i = 3i = 4從前一行的數(shù)據(jù)可以計(jì)算下一行的數(shù)據(jù)0 1 3 3 1 01 4 6 4 10 1 2 1 00 1 1 0sts+t從第 i 行數(shù)據(jù)計(jì)算并存放第 i+1 行數(shù)據(jù)1 2 1 0 1 3 3 1 0 1 4 6s=0 t=1 t=2 t=1 t=0 t=1 t=3 t=3 t=1 t=0 t=1s+t s=t s=t s=t s=t s=t s=t s=t s=ts+t s+t s+t s+t s+t s+t s+t s+t利用隊(duì)列實(shí)現(xiàn)打印二項(xiàng)