1、 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES第第3 3章章 棧和隊(duì)列棧和隊(duì)列 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES3.1 棧棧 ( Stack )a0an-1an-2topbottom Department of Computer Science & Technology, Nanjing University fal

2、lDATA STRUCTUREStemplate class Stack public: Stack ( int sz = 10 ); /構(gòu)造函數(shù)構(gòu)造函數(shù) void Push (Type x); /進(jìn)棧進(jìn)棧 int Pop (Type& x); /出棧出棧 int GetTop (Type& x); /取棧頂元素取棧頂元素 void MakeEmpty ( ); /置空棧置空棧 int IsEmpty ( ) const; /判棧空否判棧空否 int IsFull ( ) const; /判棧滿(mǎn)否判棧滿(mǎn)否 Department of Computer Science &

3、 Technology, Nanjing University fallDATA STRUCTUREStemplate class Stack private: int top; /棧頂指針棧頂指針 Type *elements; /棧元素?cái)?shù)組棧元素?cái)?shù)組 int maxSize; /棧最大容量棧最大容量 void overflowProcess( ); /棧的溢出處理?xiàng)５囊绯鎏幚? 1 2 3 4 5 6 7 8 9 maxSize-1top (棧空棧空)elements棧的數(shù)組存儲(chǔ)表示棧的數(shù)組存儲(chǔ)表示 順序棧順序棧top (棧滿(mǎn)棧滿(mǎn)) Department of Computer Scien

4、ce & Technology, Nanjing University fallDATA STRUCTURES public: Stack (int sz = 10); /構(gòu)造函數(shù)構(gòu)造函數(shù) Stack ( ) delete elements; void Push (Type x); /進(jìn)棧進(jìn)棧 int Pop (Type& x); /出棧出棧 Type GetTop ( ); /取棧頂取棧頂 void MakeEmpty ( ) top = -1; /置空棧置空棧 int IsEmpty ( ) const return top = -1; int IsFull ( ) con

5、st return top = maxSize-1; Department of Computer Science & Technology, Nanjing University fallDATA STRUCTUREStop空棧toptoptoptoptopa 進(jìn)棧進(jìn)棧b 進(jìn)棧進(jìn)棧aababcdee 進(jìn)棧進(jìn)棧abcdef 進(jìn)棧溢出進(jìn)棧溢出abdee 退棧退棧c Department of Computer Science & Technology, Nanjing University fallDATA STRUCTUREStopc 退棧退棧b 退棧退棧abaa 退棧退棧空棧

6、空棧topabdd 退棧退棧ctopabctoptop Department of Computer Science & Technology, Nanjing University fallDATA STRUCTUREStemplate void SeqStack:overflowProcess( ) /私有函數(shù)：當(dāng)棧滿(mǎn)則執(zhí)行擴(kuò)充棧存儲(chǔ)空間處理 T *newArray = new E2*maxSize;/創(chuàng)建更大的存儲(chǔ)數(shù)組 for (int i = 0; i = top; i+) newArrayi = elementsi; maxSize += maxSize; delete el

7、ements; elements = newArray; /改變elements指針; template void SeqStack:Push(T x) /若棧不滿(mǎn)若棧不滿(mǎn), 則將元素則將元素x插入該棧棧頂插入該棧棧頂, 否則溢出處理否則溢出處理 if (IsFull() = true) overflowProcess; /棧滿(mǎn)棧滿(mǎn) elements+top = x; Department of Computer Science & Technology, Nanjing University fallDATA STRUCTUREStemplate bool SeqStack:Pop(

8、T& x) /函數(shù)退出棧頂元素并返回棧頂元素的值函數(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; Department of Computer Science & Technology, N

9、anjing University fallDATA STRUCTURES算法分析：算法分析：GetTop( ) / 取棧頂元素取棧頂元素Push( ) /入棧操作入棧操作Pop( ) /出棧操作出棧操作O(1) Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESb0 t0 t1 b10 maxSize-1V Department of Computer Science & Technology, Nanjing University fallDATA STRUC

10、TURES 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.t1+; return 1; int push ( DualStack& DS, Type x, int i)int Pop (DualStack& DS, Type& x, int i) Department of Comput

11、er Science & Technology, Nanjing University fallDATA STRUCTURES例：多進(jìn)制輸出例：多進(jìn)制輸出（將十進(jìn)制轉(zhuǎn)換成其它進(jìn)制）（將十進(jìn)制轉(zhuǎn)換成其它進(jìn)制）算法：以算法：以B進(jìn)制形式輸出進(jìn)制形式輸出1.nB,結(jié)果壓入棧結(jié)果壓入棧S中；中；2.n的剩余部分為的剩余部分為n/B,用用n/B代替代替n;3.重復(fù)上述過(guò)程重復(fù)上述過(guò)程1和和2直到直到n=0;4.從棧中彈出并打印所有數(shù)字。從棧中彈出并打印所有數(shù)字。5310125124023122021 Department of Computer Science & Technology,

12、 Nanjing University fallDATA STRUCTUREStop Department of Computer Science & Technology, Nanjing University fallDATA STRUCTUREStemplate class Stack;template class StackNode friend class Stack;private: Type data; /結(jié)點(diǎn)數(shù)據(jù)結(jié)點(diǎn)數(shù)據(jù) StackNode *link; /結(jié)點(diǎn)鏈指針結(jié)點(diǎn)鏈指針public: StackNode ( T d = 0, StackNode * next =

13、 NULL ) : data (d), link (next) ; Department of Computer Science & Technology, Nanjing University fallDATA STRUCTUREStemplate class LinkedStack : public Stack /鏈?zhǔn)綏ｎ?lèi)定義 private: StackNode *top; /棧頂指針 void output(ostream& os, StackNode *ptr, int& i); /遞歸輸出棧的所有元素public: LinkedStack() : top(N

14、ULL) /構(gòu)造函數(shù) LinkedStack() makeEmpty(); /析構(gòu)函數(shù) void Push(E x); /進(jìn)棧 bool Pop(E& x); /退棧 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES bool getTop(E& x) const;/取棧頂取棧頂 bool IsEmpty() const return top = NULL; void makeEmpty();/清空棧的內(nèi)容清空棧的內(nèi)容 int k = 1; friend

15、 ostream& operator (ostream& os, LinkedStack& s) output(os, s.top, k); /輸出棧元素的重載操作輸出棧元素的重載操作 ; Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES字符串字符串: (a*(b+c)-d)目的目的: 輸入字符串輸入字符串,輸出匹配的括號(hào)和沒(méi)有匹配的括號(hào)輸出匹配的括號(hào)和沒(méi)有匹配的括號(hào)算法基本思想算法基本思想:從左到右掃描從左到右掃描,把遇到的左括號(hào)存放在棧中把遇

16、到的左括號(hào)存放在棧中;每當(dāng)在后續(xù)的掃描過(guò)程中遇到一個(gè)右括號(hào)時(shí)每當(dāng)在后續(xù)的掃描過(guò)程中遇到一個(gè)右括號(hào)時(shí),就將它與棧就將它與棧頂?shù)淖罄ㄌ?hào)相匹配頂?shù)淖罄ㄌ?hào)相匹配,并在棧頂刪除該左括號(hào)。并在棧頂刪除該左括號(hào)。 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES#include #include #include #include “stack.h”const int maxLength = 100;void PrintMatchedPairs(char * expression)

17、stack s(maxLength); int j, length = strlen(expression); for (int i = 1;ilength; i+) if (expressioni-1=() s.Push(i); /左括號(hào)左括號(hào), 位置進(jìn)棧位置進(jìn)棧 else if (expressioni-1=) /右括號(hào)右括號(hào) if (s.Pop(j) = true) /棧不空棧不空,退棧成功退棧成功 coutj“與與”i“匹配匹配”endl; else cout“沒(méi)有與第沒(méi)有與第”i”個(gè)右括號(hào)匹配的左括號(hào)個(gè)右括號(hào)匹配的左括號(hào)!”endl; while (s.IsEmpty( ) = fa

18、lse) s.Pop(j); cout.endl; ?/棧中還有左括號(hào)棧中還有左括號(hào)沒(méi)有與第沒(méi)有與第”j“個(gè)左括號(hào)相匹配的右括個(gè)左括號(hào)相匹配的右括號(hào)號(hào)!” Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES Department of Computer Science & Technolog

19、y, Nanjing University fallDATA STRUCTURES Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESrst1rst2rst3rst4rst5rst6 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESn順序掃描表達(dá)式的每一項(xiàng)，根據(jù)它的類(lèi)型做如下順序掃描表達(dá)式的每一項(xiàng)，根據(jù)它的類(lèi)型做如下相應(yīng)操作：相應(yīng)操作：n若該項(xiàng)是操

20、作數(shù)，則將其壓棧；若該項(xiàng)是操作數(shù)，則將其壓棧；n若該項(xiàng)是操作符若該項(xiàng)是操作符，則連續(xù)從棧中退出兩個(gè)操，則連續(xù)從棧中退出兩個(gè)操作數(shù)作數(shù)Y和和X，形成運(yùn)算指令，形成運(yùn)算指令XY，并將計(jì)算結(jié)，并將計(jì)算結(jié)果重新壓棧。果重新壓棧。n當(dāng)表達(dá)式的所有項(xiàng)都掃描并處理完后，棧頂存放當(dāng)表達(dá)式的所有項(xiàng)都掃描并處理完后，棧頂存放的就是最后的計(jì)算結(jié)果。的就是最后的計(jì)算結(jié)果。 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES步步 輸入輸入 類(lèi)類(lèi) 型型 動(dòng)動(dòng) 作作 棧內(nèi)容棧內(nèi)容 1 置空棧置空棧 空

21、空 2 A 操作數(shù)操作數(shù) 進(jìn)棧進(jìn)棧 A 3 B 操作數(shù)操作數(shù) 進(jìn)棧進(jìn)棧 AB 4 C 操作數(shù)操作數(shù) 進(jìn)棧進(jìn)棧 ABC 5 D 操作數(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 Department of Computer Science & Technology, Nanjing University

22、fallDATA STRUCTURES步步 輸入輸入 類(lèi)類(lèi) 型型 動(dòng)動(dòng) 作作 棧內(nèi)容棧內(nèi)容 9 E 操作數(shù)操作數(shù) 進(jìn)棧進(jìn)棧 r3E 10 F 操作數(shù)操作數(shù) 進(jìn)棧進(jìn)棧 r3EF 11 操作符操作符 F、E 退棧退棧, 計(jì)算計(jì)算 EF, 結(jié)果結(jié)果 r4 進(jìn)棧進(jìn)棧 r3r4 12 G 操作數(shù)操作數(shù) 進(jìn)棧進(jìn)棧 r3r4G 13 / 操作符操作符 G、r4 退棧退棧, 計(jì)算計(jì)算 r4/G, 結(jié)果結(jié)果 r5 進(jìn)棧進(jìn)棧 r3r5 14 - - 操作符操作符 r5、r3 退棧退棧, 計(jì)算計(jì)算 r3- -r5, 結(jié)果結(jié)果 r6 進(jìn)棧進(jìn)棧 r6 Department of Computer Science &am

23、p; Technology, Nanjing University fallDATA STRUCTURESvoid 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 );

24、Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESvoid DoOperator ( char op ) /從棧從棧S中取兩個(gè)操作數(shù)，形成運(yùn)算指令并計(jì)算進(jìn)棧中取兩個(gè)操作數(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; /退出兩個(gè)操作數(shù)退出兩個(gè)

25、操作數(shù) switch ( op ) case +: S.Push ( left + right); break; /加加 case -: S.Push ( left - right); break; /減減 case *: S.Push ( left * right); break; /乘乘 case /: if ( right != 0.0 ) S.Push ( left / right); /除除 else cout isp(+)icp(+) # 操作符操作符+進(jìn)棧進(jìn)棧, 讀字符讀字符 4 B #+ B 操作數(shù)操作數(shù)B輸出輸出, 讀字符讀字符 5 * #+ * + 操作符操作符*進(jìn)棧進(jìn)棧,

26、 讀字符讀字符 6 ( #+* ( * 操作符操作符(進(jìn)棧進(jìn)棧, 讀字符讀字符 7 C #+*( C 操作數(shù)操作數(shù)C輸出輸出, 讀字符讀字符 8 - #+*( - - ( 操作符操作符- -進(jìn)棧進(jìn)棧, 讀字符讀字符 9 D #+*(- - D 操作數(shù)操作數(shù)D進(jìn)棧進(jìn)棧, 讀字符讀字符 10 ) #+*(- - ) - - 操作符操作符- -退棧輸出退棧輸出 11 #+*( ) = ( ( 退棧退棧, 消括號(hào)消括號(hào), 讀字符讀字符 操作符 ch # ( *, /, % +, - - ) isp (棧棧內(nèi)內(nèi)) 0 1 7 5 3 8 icp (棧棧外外) 0 8 6 4 2 1 Department

27、 of Computer Science & Technology, Nanjing University fallDATA STRUCTURES步 輸入 棧內(nèi)容棧內(nèi)容 語(yǔ)義 輸出 動(dòng)作 12 - - #+* - - * * 操作符操作符*退棧輸出退棧輸出 13 #+ - - # 操作操作符符- -進(jìn)棧進(jìn)棧, 讀字符讀字符 15 E #- - E 操作數(shù)操作數(shù)E輸出輸出, 讀字符讀字符 16 / #- - / - 操作符操作符/進(jìn)棧進(jìn)棧, 讀字符讀字符 17 F #- -/ F 操作數(shù)操作數(shù)F輸出輸出, 讀字符讀字符 18 # #- -/ # / / 操作符操作符/退棧輸出退棧輸出 1

28、9 #- - # - - - - 操作符操作符- -退棧輸出退棧輸出 20 # # = # #配對(duì)配對(duì), 轉(zhuǎn)換結(jié)束轉(zhuǎn)換結(jié)束 操作符 ch # ( *, /, % +, - - ) isp (棧棧內(nèi)內(nèi)) 0 1 7 5 3 8 icp (棧棧外外) 0 8 6 4 2 1 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESvoid postfix ( expression e ) stack s; char ch, op; s.Push ( # ); cin.Get ( c

29、h ); 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 ); Department of Computer Science & Technology, Nanjing Univers

30、ity fallDATA STRUCTURES算法分析：算法分析：設(shè)表達(dá)式中符號(hào)的總數(shù)為設(shè)表達(dá)式中符號(hào)的總數(shù)為nO(n) Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES3.2 棧與遞歸棧與遞歸n3.2.1 遞歸的概念遞歸的概念冪函數(shù)：冪函數(shù)：xnS(n)=i=1+2+3+n如果已經(jīng)求得如果已經(jīng)求得xn或或S(n), 計(jì)算計(jì)算xn+1或或S(n+1)時(shí)？時(shí)？ Department of Computer Science & Technology, Nanjing

31、 University fallDATA STRUCTURES求解階乘函數(shù)的遞歸算法求解階乘函數(shù)的遞歸算法long Factorial ( long n ) if ( n = 0 ) return 1; else return n * Factorial (n-1);時(shí)時(shí)當(dāng)當(dāng)時(shí)時(shí)當(dāng)當(dāng) 1 ,)!1( 0 ,1!nnnnn Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES參數(shù)參數(shù) 4 計(jì)算計(jì)算 4*fact(3)參數(shù)參數(shù) 3 計(jì)算計(jì)算 3*fact(2)參數(shù)參數(shù) 2 計(jì)算

32、計(jì)算 2*fact(1)參數(shù)參數(shù) 1 計(jì)算計(jì)算 1*fact(0)參數(shù)參數(shù) 0 直接定值直接定值 = 1112624 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES Department of Computer Science & Technology, Nanjing Universi

33、ty fallDATA STRUCTURESf f Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESf f f f f a0a1a2a3a4遞歸找鏈尾template void Print ( ListNode *f ) if ( f -link = NULL ) cout data link ); Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURE

34、Sf 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 ); Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES遞歸遞歸 Department of Computer Science & Technology, Nanjing University fallDATA STRUC

35、TURES Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES#include #include strclass.h”void Hanoi (int n, String A, String B, String C) /解決漢諾塔問(wèn)題的算法解決漢諾塔問(wèn)題的算法 if ( n = 1 ) cout m

36、ove A to C endl; else Hanoi ( n-1, A, C, B ); cout move A to C endl; Hanoi ( n-1, B, A, C ); Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES如：如：n!long Factorial ( long n )

37、if ( n = 0 ) return 1; else return n * Factorial (n-1); Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES參數(shù)參數(shù) 4 計(jì)算計(jì)算 4*fact(3)參數(shù)參數(shù) 3 計(jì)算計(jì)算 3*fact(2)參數(shù)參數(shù) 2 計(jì)算計(jì)算 2*fact(1)參數(shù)參數(shù) 1 計(jì)算計(jì)算 1*fact(0)參數(shù)參數(shù) 0 直接定值直接定值 = 1112624 Department of Computer Science & Technology

38、, Nanjing University fallDATA STRUCTURES必須解決：必須解決：調(diào)用時(shí)的參數(shù)傳遞和返回地址問(wèn)題調(diào)用時(shí)的參數(shù)傳遞和返回地址問(wèn)題 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES局部變量局部變量返回地址返回地址參數(shù)的副本空間參數(shù)的副本空間遞歸遞歸工作記錄工作記錄 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES.F

39、unction() .調(diào)用塊函數(shù)塊 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES void main ( ) int n; n = Factorial (4);RetLoc1 long Factorial ( long n ) int temp; if ( n = 0 ) return 1; else temp = n * Factorial (n-1); RetLoc2 return temp; 以以 Factorial(n) 為例：為例： Department

40、of Computer Science & Technology, Nanjing University fallDATA STRUCTURES0 1 RetLoc21 1 RetLoc22 2 RetLoc23 6 RetLoc24 24 RetLoc1return 4*6 /返回返回 24 return 3*2 /返回返回 6 return 1 /返回返回 1 return 1*1 /返回返回 1 return 2*1 /返回返回 2 Department of Computer Science & Technology, Nanjing University fallDA

41、TA STRUCTURES但是，遞歸并不是一種高效的方法但是，遞歸并不是一種高效的方法long Fib ( long n ) if ( n = 1 ) return n; else return Fib (n-1) + Fib (n-2); 1n2),Fib(n1)Fib(n0,1nn,)Fib(n Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES斐波那契數(shù)列的遞歸調(diào)用樹(shù)斐波那契數(shù)列的遞歸調(diào)用樹(shù)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fi

42、b(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)算法的時(shí)間復(fù)雜度：算法的時(shí)間復(fù)雜度： O(2n) Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESlong FibIter ( long n ) if ( n = 1 ) return n; long twoback = 0, oneback = 1, Current; for ( int i = 2; i = n; i+ ) Current = twoback +

43、oneback; twoback = oneback; oneback = Current; return Current;算法的時(shí)間復(fù)雜度：算法的時(shí)間復(fù)雜度：O(n) Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES方法：方法：?jiǎn)蜗蜻f歸和尾遞歸：?jiǎn)蜗蜻f歸和尾遞歸：直接用迭代實(shí)現(xiàn)直接用迭代實(shí)現(xiàn) 其他情形：借助棧其他情形：借助棧 實(shí)現(xiàn)實(shí)現(xiàn) Department of Computer Science & Technology, Nanjing University

44、 fallDATA STRUCTURES單向遞歸：斐波那契數(shù)列單向遞歸：斐波那契數(shù)列l(wèi) o n g F i b ( l o n g 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-; Department of Computer

45、 Science & Technology, Nanjing University fallDATA STRUCTURES3.2.3 用回溯法求解迷宮問(wèn)題用回溯法求解迷宮問(wèn)題迷宮的表示：迷宮的表示：mazem+2p+2 001000110001111111 .入口入口出出口口mazeij=1 墻壁墻壁mazeij=0 通路通路 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES所走過(guò)的路徑信息：所走過(guò)的路徑信息：struct itemsint x,y,dir; /

46、位置和前進(jìn)方向位置和前進(jìn)方向; Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES前進(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; Department of Computer Science & Technology, Nanjing Uni

47、versity fallDATA STRUCTURES迷宮問(wèn)題非遞歸解法用到的數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題非遞歸解法用到的數(shù)據(jù)結(jié)構(gòu)mazeij:迷宮描述數(shù)據(jù)迷宮描述數(shù)據(jù)items:當(dāng)前位置的坐標(biāo)和來(lái)向當(dāng)前位置的坐標(biāo)和來(lái)向stack st(m*p) markij：標(biāo)識(shí)，是否走過(guò)（：標(biāo)識(shí)，是否走過(guò)（=0，未走過(guò)），未走過(guò)）offset move8:各個(gè)方向的偏移表各個(gè)方向的偏移表 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES迷宮問(wèn)題非遞歸解法迷宮問(wèn)題非遞歸解法讀入迷宮數(shù)據(jù)讀入迷宮數(shù)

48、據(jù)mazeij 初始化工作棧，迷宮入口坐標(biāo)和前進(jìn)方向，并進(jìn)棧；初始化工作棧，迷宮入口坐標(biāo)和前進(jìn)方向，并進(jìn)棧； 初始化初始化mark數(shù)組為數(shù)組為0 while (棧非空棧非空) pop( ) = (i,j,dir);/從棧頂退出的坐標(biāo)和方向；從棧頂退出的坐標(biāo)和方向； while (還有其他方向可移動(dòng)還有其他方向可移動(dòng)) g=i+movedir.a;h=j+movedir.b;/(g,h):下一坐標(biāo)；下一坐標(biāo)； if (g=m&h=p) 迷宮搜索成功；迷宮搜索成功；/出口在出口在mazemp if (!mazegh&!markgh) markgh=1; dir=dir+1;/下一次

49、將要移動(dòng)的方向；下一次將要移動(dòng)的方向； (i,j,dir) 進(jìn)棧；進(jìn)棧； i=g;j=h;dir=N;/當(dāng)前位置：當(dāng)前位置：gh,方向初始為方向初始為N else dir+; / 回到外循環(huán)回到外循環(huán) Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESa0 a1 a2 an-1frontrear Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESte

50、mplate class Queue public: Queue (int = 10); /構(gòu)造函數(shù)構(gòu)造函數(shù) void EnQueue (Type x); /進(jìn)隊(duì)進(jìn)隊(duì) int DeQueue (Type& x); /出隊(duì)列出隊(duì)列 int GetFront (Type& x); /取隊(duì)頭元素值取隊(duì)頭元素值 void MakeEmpty ( ); /置空隊(duì)列置空隊(duì)列 int IsEmpty ( ) const ; /判隊(duì)列空否判隊(duì)列空否 int IsFull ( ) const; /判隊(duì)列滿(mǎn)否判隊(duì)列滿(mǎn)否 Department of Computer Science & Te

51、chnology, Nanjing University fallDATA STRUCTURES隊(duì)列的順序存儲(chǔ)表示#include template class Queue private: int rear, front;/隊(duì)尾隊(duì)尾, 隊(duì)頭指針隊(duì)頭指針 Type *elements; /隊(duì)列元素?cái)?shù)組隊(duì)列元素?cái)?shù)組 int maxSize; /最大元素個(gè)數(shù)最大元素個(gè)數(shù)public: Queue (int sz = 10); Queue ( ) delete elements; void EnQueue (Type x); /進(jìn)隊(duì)進(jìn)隊(duì) Department of Computer Science

52、& Technology, Nanjing University fallDATA STRUCTURESfront rear空隊(duì)列front rearA進(jìn)隊(duì)進(jìn)隊(duì)Afront rearB進(jìn)隊(duì)進(jìn)隊(duì)A Bfront rearC, D進(jìn)隊(duì)進(jìn)隊(duì)A B C Dfront rearA退隊(duì)退隊(duì)B C Dfront rearB退隊(duì)退隊(duì)C Dfront rearE,F,G進(jìn)隊(duì)進(jìn)隊(duì)C D E F GC D E F Gfront rearH進(jìn)隊(duì)進(jìn)隊(duì),溢出溢出 Department of Computer Science & Technology, Nanjing University fallDATA

53、 STRUCTURESfront rearB進(jìn)隊(duì)進(jìn)隊(duì)A Bfront rearC, D進(jìn)隊(duì)進(jìn)隊(duì)A B C Dfront rearA退隊(duì)退隊(duì)B C Dfront rearB退隊(duì)退隊(duì)C Dfront rearE,F,G進(jìn)隊(duì)進(jìn)隊(duì)C D E F GC D E F Gfront rearH進(jìn)隊(duì)進(jìn)隊(duì),溢出溢出 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES 初始化：初始化： front=rear= -1 進(jìn)隊(duì)時(shí)：進(jìn)隊(duì)時(shí)： rear = rear + 1，再將新元素按，再將新元素按

54、 rear 指示位置加入；隊(duì)尾指針指示實(shí)際隊(duì)尾位置。指示位置加入；隊(duì)尾指針指示實(shí)際隊(duì)尾位置。出隊(duì)時(shí)：出隊(duì)時(shí)：front = front + 1，隊(duì)頭指針指示實(shí)際，隊(duì)頭指針指示實(shí)際隊(duì)頭的前一位置，再將下標(biāo)為隊(duì)頭的前一位置，再將下標(biāo)為 front 的元素取。的元素取。 隊(duì)滿(mǎn)時(shí)：隊(duì)滿(mǎn)時(shí)：rear = maxsize 1;再進(jìn)隊(duì)將溢出（假再進(jìn)隊(duì)將溢出（假溢出）溢出） ； 隊(duì)空時(shí)隊(duì)空時(shí):front = rear;再出隊(duì)將隊(duì)空處理。再出隊(duì)將隊(duì)空處理。 Department of Computer Science & Technology, Nanjing University fallDATA S

55、TRUCTURES隊(duì)列的順序存儲(chǔ)表示隊(duì)列的順序存儲(chǔ)表示循環(huán)隊(duì)列循環(huán)隊(duì)列（ Circular Queue）01234567front01234567front01234567frontrearAABCrearrear空隊(duì)列空隊(duì)列A進(jìn)隊(duì)進(jìn)隊(duì)B, C進(jìn)隊(duì)進(jìn)隊(duì)0123456701234567A退隊(duì)退隊(duì)B退隊(duì)退隊(duì)01234567D,E,F,G,H,I 進(jìn)隊(duì)進(jìn)隊(duì)frontBCrearAfrontBCrearfrontCrearDEF GHI Department of Computer Science & Technology, Nanjing University fallDATA STRUCT

56、URES Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES01234567frontCrearDEF GH01234567frontCrearDEF GHI如果是：如果是： rear= front ？01234567frontrearAA Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES int DeQueue (Type& x); /退

57、隊(duì)退隊(duì) int GetFront (Type& x); /取隊(duì)頭元素取隊(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 Department of Computer Science & Technology, Nanjing Uni

58、versity fallDATA STRUCTUREStemplate 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; Department of Computer Scie

59、nce & Technology, Nanjing University fallDATA STRUCTURESfrontrear Department of Computer Science & Technology, Nanjing University fallDATA STRUCTUREStemplate class Queue;template class QueueNode friend class Queue;private: Type data; /隊(duì)列結(jié)點(diǎn)數(shù)據(jù)隊(duì)列結(jié)點(diǎn)數(shù)據(jù) QueueNode *link; /結(jié)點(diǎn)鏈指針結(jié)點(diǎn)鏈指針public: QueueNod

60、e ( Type d = 0, QueueNode *next = NULL ) : data (d), link (next) ; Department of Computer Science & Technology, Nanjing University fallDATA STRUCTUREStemplate class Queue private: QueueNode *front, *rear; /隊(duì)頭、隊(duì)尾指針指針隊(duì)頭、隊(duì)尾指針指針public: Queue ( ) : rear ( NULL ), front ( NULL ) Queue ( ); void EnQueu

61、e (Type x); int DeQueue (Type& x); int GetFront (Type& x); void MakeEmpty ( ); /實(shí)現(xiàn)與實(shí)現(xiàn)與Queue( )同同 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES int IsEmpty ( ) const return front = NULL; ; template Queue : Queue ( ) /隊(duì)列的析構(gòu)函數(shù)隊(duì)列的析構(gòu)函數(shù) QueueNode *p; while ( front != NULL ) /逐個(gè)結(jié)點(diǎn)釋放逐個(gè)結(jié)點(diǎn)釋放 p = front; front = front-link; delete p; Department of Computer Science &