1棧與隊列數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第1頁。2棧隊列棧的應用：表達式求值棧的應用：遞歸隊列的應用：打印楊輝三角形優(yōu)先級隊列棧與隊列數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第2頁。3只允許在一端插入和刪除的線性表允許插入和刪除 的一端稱為棧頂

(top)，另一端稱 為棧底(bottom)特點 后進先出(LIFO)棧(Stack)退棧進棧a0an-1an-2topbottom數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第3頁。4template<classE>classStack{

//棧的類定義public:Stack(){}; //構造函數(shù)

virtualvoidPush(Ex)=0;//進棧

virtualboolPop(E&x)=0; //出棧

virtualboolGetTop(E&x)=0; //取棧頂

virtualboolIsEmpty()=0; //判棧空

virtualboolIsFull()=0; //判棧滿}；棧的抽象數(shù)據(jù)類型數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第4頁。5棧的數(shù)組存儲表示—

順序棧0123456789maxSize-1top(棧空)elements數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第5頁。6

top空棧toptoptoptoptopa進棧b進棧aababcdee進棧abcdef進棧溢出abdee退棧c數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第6頁。7topc退棧b退棧abaa退棧空棧topabdd退棧ctopabctoptop數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第7頁。8棧的鏈接存儲表示—

鏈式棧鏈式棧無棧滿問題，空間可擴充插入與刪除僅在棧頂處執(zhí)行鏈式棧的棧頂在鏈頭適合于多棧操作top數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第8頁。9隊列(

Queue)定義隊列是只允許在一端刪除，在另一端插入的線性表允許刪除的一端叫做隊頭(front)，允許插入的一端叫做隊尾(rear)。特性先進先出(FIFO,

FirstInFirstOut)a0

a1

a2

an-1frontrear數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第9頁。10隊列的進隊和出隊

frontrear空隊列frontrearA進隊AfrontrearB進隊ABfrontrearC,D進隊ABCDfrontrearA退隊BCDfrontrearB退隊CDfrontrearE,F,G進隊CDEFGCDEFGfrontrearH進隊,溢出數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第10頁。11隊列的進隊和出隊原則進隊時先將新元素按rear指示位置加入，再將隊尾指針加一rear=rear+1。隊尾指針指示實際隊尾的后一位置。出隊時按隊頭指針指示位置取出元素，再將隊頭指針進一front=front+1，隊頭指針指示實際隊頭位置。隊滿時再進隊將溢出出錯（假溢出）；隊空時再出隊將隊空處理。解決假溢出的辦法之一：將隊列元素存放數(shù)組首尾相接，形成循環(huán)（環(huán)形）隊列。數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第11頁。12隊列存放數(shù)組被當作首尾相接的表處理。隊頭、隊尾指針加1時從maxSize-1直接進到0，可用語言的取模(余數(shù))運算實現(xiàn)。隊頭指針進1:front=(front+1)%maxSize;隊尾指針進1:

rear=(rear+1)%maxSize;隊列初始化：front=rear

=0;隊空條件：front

==

rear;隊滿條件：(rear+1)%maxSize==front

循環(huán)隊列(CircularQueue)數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第12頁。1301234567front01234567front01234567frontrearAABCrearrear空隊列A進隊B,C進隊0123456701234567A退隊B退隊01234567D,E,F,G,H,I進隊frontBCrearAfrontBCrearfrontCrearDEFGHI數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第13頁。14隊列的鏈接存儲表示—

鏈式隊列隊頭在鏈頭，隊尾在鏈尾。鏈式隊列在進隊時無隊滿問題，但有隊空問題。隊空條件為

front==NULLfrontrear數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第14頁。15棧的應用：表達式求值一個表達式由操作數(shù)（亦稱運算對象）、操作符（亦稱運算符）和分界符組成。算術表達式有三種表示：中綴(infix)表示

<操作數(shù)><操作符><操作數(shù)>，如A+B；前綴(prefix)表示

<操作符><操作數(shù)><操作數(shù)>，如+AB；后綴(postfix)表示

<操作數(shù)><操作數(shù)><操作符>，如AB+；數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第15頁。16中綴表達式

a+b*(c-d)-e/f后綴表達式abcd-*+ef/-前綴表達式

-+a*b–cd/ef表達式中相鄰兩個操作符的計算次序為：優(yōu)先級高的先計算；優(yōu)先級相同的自左向右計算；當使用括號時從最內(nèi)層括號開始計算。表達式事例數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第16頁。17應用后綴表示計算表達式的值從左向右順序地掃描表達式，并用一個棧暫存掃描到的操作數(shù)或計算結果。在后綴表達式的計算順序中已隱含了加括號的優(yōu)先次序，括號在后綴表達式中不出現(xiàn)。計算例abcd-*+ef/-rst1rst2rst3rst4rst5數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第17頁。18一般表達式的操作符有4種類型：

算術操作符

如雙目操作符（+、-、*、/和%）以及單目操作符（-）。

關系操作符

包括<、<=、==、!=、>=、>。這些操作符主要用于比較。

邏輯操作符

如與(&&)、或(||)、非(!)。

括號‘(’和‘)’

它們的作用是改變運算順序。數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第18頁。19中綴表示→轉(zhuǎn)后綴表示先對中綴表達式按運算優(yōu)先次序加上括號，再把操作符后移到右括號的后面并以就近移動為原則，最后將所有括號消去。如中綴表示(A+B)*D-E/(F+A*D)+C，其轉(zhuǎn)換為后綴表達式的過程如下：

(

(

((A+B)*D)

–(E/(F+(A*D)

)

)

)+C)后綴表示

AB+D*EFAD*+/-C+數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第19頁。20中綴表示→轉(zhuǎn)前綴表示先對中綴表達式按運算優(yōu)先次序通統(tǒng)加上括號，再把操作符前移到左括號前并以就近移動為原則，最后將所有括號消去。

如中綴表示(A+B)*D-E/(F+A*D)+C，其轉(zhuǎn)換為前綴表達式的過程如下：

(

(

((A+B)*D)

–(E/(F+(A*D)

)

)

)+C)前綴表示

+-*+ABD/E+F*ADC數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第20頁。21利用棧將中綴表示轉(zhuǎn)換為后綴表示使用棧可將表達式的中綴表示轉(zhuǎn)換成它的前綴表示和后綴表示。為了實現(xiàn)這種轉(zhuǎn)換， 需要考慮各操作符 的優(yōu)先級。

優(yōu)先級

操作符

1 單目-、！

2 *、/、% 3 +、-

4 <、<=、>、>=5==、!= 6 && 7 || 數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第21頁。22各個算術操作符的優(yōu)先級isp叫做棧內(nèi)(instackpriority)優(yōu)先數(shù)icp叫做棧外(incomingpriority)優(yōu)先數(shù)。操作符優(yōu)先數(shù)相等的情況只出現(xiàn)在括號配對或棧底的“;”號與輸入流最后的“;”號配對時。數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第22頁。23中綴表達式轉(zhuǎn)換為后綴表達式的算法操作符棧初始化，將結束符‘;’進棧。然后讀入中綴表達式字符流的首字符ch。重復執(zhí)行以下步驟，直到ch=‘;’，同時棧頂?shù)牟僮鞣彩恰?’，停止循環(huán)。若ch是操作數(shù)直接輸出，讀入下一個字符ch。若ch是操作符，判斷ch的優(yōu)先級icp和位于棧頂?shù)牟僮鞣鹢p的優(yōu)先級isp：數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第23頁。24若icp(ch)>isp(op)，令ch進棧，讀入下一個字符ch。若icp(ch)<isp(op)，退棧并輸出。若icp(ch)==isp(op)，退棧但不輸出，若退出的是“(”號讀入下一個字符ch。算法結束，輸出序列即為所需的后綴表達式。數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第24頁。25數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第25頁。26數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第26頁。27應用中綴表示計算表達式的值使用兩個棧，操作符棧OPTR(operator)，操作數(shù)棧OPND(operand)為了實現(xiàn)這種計算，需要考慮各操作符的優(yōu)先級rst1rst2rst3rst4rst5a+b*

(c-d)-e/f數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第27頁。28各個算術操作符的優(yōu)先級isp叫做棧內(nèi)(instackpriority)優(yōu)先數(shù)icp叫做棧外(incomingpriority)優(yōu)先數(shù)。操作符優(yōu)先數(shù)相等的情況只出現(xiàn)在括號配對或棧底的“#”號與輸入流最后的“#”號配對時。數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第28頁。29中綴算術表達式求值對中綴表達式求值的一般規(guī)則：建立并初始化OPTR棧和OPND棧，然后在OPTR棧中壓入一個“#”掃描中綴表達式，取一字符送入ch。當ch!=‘#’

或OPTR棧的棧頂!=‘#’時,執(zhí)行以下工作,否則結束算法。在OPND棧的棧頂?shù)玫竭\算結果。若ch是操作數(shù)，進OPND棧，從中綴表達式取下一字符送入ch；

數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第29頁。30若ch是操作符，比較icp(ch)的優(yōu)先級和isp(OPTR)的優(yōu)先級：若icp(ch)>isp(OPTR)，則ch進OPTR棧，從中綴表達式取下一字符送入ch；若icp(ch)<isp(OPTR)，則從OPND棧退出a2和a1，從OPTR棧退出θ,形成運算指令(a1)θ(a2)，結果進OPND棧；若icp(ch)==isp(OPTR)

且ch==

')'，則從OPTR棧退出'('，對消括號，然后從中綴表達式取下一字符送入ch；數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第30頁。31voidInFixRun(){stack<char>OPTR,OPND;charch,op;OPTR.makeEmpty();OPND.makeEmpty();OPTR.Push(‘#’);//兩個棧初始化

getchar(ch);//讀入一個字符

op=

'#';while(ch!='#'||op!='#'){if(isdigit(ch))//是操作數(shù),進棧

{

OPND.Push(ch);getchar(ch);}

else{//是操作符,比較優(yōu)先級

OPTR.GetTop(op);

//讀一個操作符

數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第31頁。32

if

(icp(ch)>isp(op))//棧頂優(yōu)先級低

{OPTR.Push(ch);

getchar(ch);}

else

if(icp(ch)<isp(op)){

OPTR.Pop(op);//棧頂優(yōu)先級高

OPND.DoOperator(op);} elseif(ch

==‘)’)

//優(yōu)先級相等

{

OPTR.Pop(op);getchar(ch);}}

OPTR.GetTop(op);}/*endofwhile*/}數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第32頁。33數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第33頁。34數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第34頁。35數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第35頁。36棧的應用：遞歸遞歸的定義

若一個對象部分地包含它自己，或用它自己給自己定義,則稱這個對象是遞歸的；若一個過程直接地或間接地調(diào)用自己,則稱這個過程是遞歸的過程。以下三種情況常常用到遞歸方法。定義是遞歸的數(shù)據(jù)結構是遞歸的問題的解法是遞歸的數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第36頁。37定義是遞歸的求解階乘函數(shù)的遞歸算法longFactorial(longn){if(n==0)return1;

elsereturnn*Factorial(n-1);}例如，階乘函數(shù)數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第37頁。38求解階乘n!的過程主程序

main:fact(4)參數(shù)4計算4*fact(3)

返回24參數(shù)3計算3*fact(2)

返回6參數(shù)2計算2*fact(1)

返回2參數(shù)1計算1*fact(0)

返回1參數(shù)0直接定值=1

返回1參數(shù)傳遞結果返回遞歸調(diào)用回歸求值數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第38頁。39搜索鏈表最后一個結點并打印其數(shù)值template<classE>

voidPrint(ListNode<E>*f){if(f->link==NULL)

cout<<f->data<<

endl;elsePrint(f->link);}fffffa0a1a2a3a4遞歸找鏈尾數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第39頁。40在鏈表中尋找等于給定值的結點并打印其數(shù)值

template<classE>

voidPrint(ListNode<E>*f,Evalue){

if(f!=NULL)

if(f->data==value)

cout<<f->

data<<endl;

elsePrint(f->link,value);

}ffff遞歸找含x值的結點x數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第40頁。41問題的解法是遞歸的例，漢諾塔(TowerofHanoi)問題的解法： 如果n=1，則將這一個盤子直接從A柱移到C柱上。否則，執(zhí)行以下三步：用C柱做過渡，將A柱上的(n-1)個盤子移到B柱上：將A柱上最后一個盤子直接移到C柱上；用A柱做過渡，將B柱上的(n-1)個盤子移到C柱上。數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第41頁。42f(n,A,B,C)=(f(n-1,A,C,B),f(1,A,_,C),f(n-1,B,A,C))數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第42頁。43#include<iostream.h>void

Hanoi(intn,

charA,

charB,

charC){//解決漢諾塔問題的算法

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);

}}數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第43頁。44(3,A,B,C)(2,A,C,B)A->CA,B,C(1,A,C,B)A,B,CA->CA->C(1,B,A,C)A,B,CA->CA->BA->BA->CB->CC->BA->C(2,B,A,C)A,B,C(1,A,C,B)A,B,CA->CA->C(1,B,A,C)A,B,CA->CB->CA->BB->AB->CA->C數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第44頁。45自頂向下、逐步分解的策略子問題應與原問題做同樣事情，且規(guī)模變小；解決遞歸問題的策略是把一個規(guī)模比較大的問題分解為一個或若干規(guī)模比較小的問題，分別對這些比較小的問題求解，再綜合它們的結果，從而得到原問題的解。

—分而治之策略（分治法）這些比較小的問題的求解方法與原來問題的求解方法一樣。數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第45頁。46構成遞歸的條件不能無限制地調(diào)用本身，必須有一個出口，化簡為非遞歸狀況直接處理。

Procedure<name>(<parameterlist>){if(<initialcondition>)//遞歸結束條件

return(initialvalue);else//遞歸

return(<name>(parameterexchange));}數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第46頁。47遞歸過程在實現(xiàn)時，需要自己調(diào)用自己。層層向下遞歸，退出時的次序正好相反：

遞歸調(diào)用

n!(n-1)!(n-2)!1!0!=1

返回次序主程序第一次調(diào)用遞歸過程為外部調(diào)用；遞歸過程每次遞歸調(diào)用自己為內(nèi)部調(diào)用。它們返回調(diào)用它的過程的地址不同。遞歸過程與遞歸工作棧數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第47頁。48

longFactorial(longn){inttemp;if(n==0)return1;elsetemp=n*Factorial(n-1);

returntemp; }

voidmain(){ intn;

n=Factorial(4);

}RetLoc1RetLoc2數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第48頁。49遞歸工作棧每一次遞歸調(diào)用時，需要為過程中使用的參數(shù)、局部變量等另外分配存儲空間。每層遞歸調(diào)用需分配的空間形成遞歸工作記錄，按后進先出的棧組織。

局部變量返回地址參數(shù)活動記錄框架遞歸工作記錄數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第49頁。50函數(shù)遞歸時的活動記錄……………….<下一條指令>Function(<參數(shù)表>)……………….<return>調(diào)用塊函數(shù)塊返回地址(下一條指令)局部變量參數(shù)數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第50頁。51計算Fact時活動記錄的內(nèi)容遞歸調(diào)用序列01RetLoc211RetLoc222RetLoc236RetLoc2424RetLoc1參數(shù)返回值返回地址返回時的指令return4*6//返回

24

return3*2//返回

6

return

1//返回

1

return1*1//返回

1

return2*1//返回

2

數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第51頁。52遞歸過程改為非遞歸過程遞歸過程簡潔、易編、易懂遞歸過程效率低，重復計算多改為非遞歸過程的目的是提高效率單向遞歸和尾遞歸可直接用迭代實現(xiàn)其非遞歸過程其他情形必須借助棧實現(xiàn)非遞歸過程數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第52頁。53計算斐波那契數(shù)列的函數(shù)Fib(n)的定義

求解斐波那契數(shù)列的遞歸算法

longFib(longn){

if(n<=1)returnn;

elsereturnFib(n-1)+Fib(n-2);}如F0=0,F1=1,F2=1,F3=2,F4=3,F5=5

數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第53頁。54調(diào)用次數(shù)

NumCall(k)=2*Fib(k+1)-1斐波那契數(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)數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第54頁。55單向遞歸用迭代法實現(xiàn)longFibIter(longn){if(n<=1)returnn;

longtwoback=0,oneback=1,Current;

for(inti=2;i<=n;i++){Current=twoback+oneback;twoback=oneback;oneback=Current;

}

returnCurrent;}數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第55頁。56voidrecfunc(intA[],intn){if(n>=0){

cout

<<A[n]<<“”;n--;recfunc(A,n);}}

2536721899495463

尾遞歸用迭代法實現(xiàn)數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第56頁。57voidsterfunc(intA[],intn){//消除了尾遞歸的非遞歸函數(shù)

while(n>=0){cout

<<"value"<<A[n]<<endl;n--;

}}

數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第57頁。58遞歸與回溯對一個包含有許多結點，且每個結點有多個分支的問題，可以先選擇一個分支進行搜索。當搜索到某一結點，發(fā)現(xiàn)無法再繼續(xù)搜索下去時，可以沿搜索路徑回退到前一結點，沿另一分支繼續(xù)搜索。如果回退之后沒有其他選擇，再沿搜索路徑回退到更前結點，…。依次執(zhí)行，直到搜索到問題的解，或搜索完全部可搜索的分支沒有解存在為止。回溯法與分治法本質(zhì)相同，可用遞歸求解。數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第58頁。59在n行n列的國際象棋棋盤上，若兩個皇后位于同一行、同一列、同一對角線上，則稱為它們?yōu)榛ハ喙簟皇后問題是指找到這

n個皇后的互不攻擊的布局。n皇后問題數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第59頁。601#主對角線3#主對角線5#主對角線0#次對角線2#次對角線4#次對角線6#次對角線1#次對角線3#次對角線5#次對角線0#主對角線2#主對角線4#主對角線6#主對角線01230123k=i+jk=n+i-j-1數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第60頁。61解題思路安放第i行皇后時，需要在列的方向從0到n-1試探(j=0,…,n-1)在第

j列安放一個皇后：如果在列、主對角線、次對角線方向有其它皇后，則出現(xiàn)攻擊，撤消在第j列安放的皇后。如果沒有出現(xiàn)攻擊，在第j列安放的皇后不動，遞歸安放第i+1行皇后。數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第61頁。62設置4個數(shù)組

col[n]

：col[i]標識第i列是否安放了皇后

md[2n-1]:md[k]標識第k條主對角線是否安放了皇后

sd[2n-1]:sd[k]標識第k條次對角線是否安放了皇后

q[n]:q[i]記錄第i行皇后在第幾列數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第62頁。63voidQueen(inti){for(intj=0;j<n;j++){if(第i行第j列沒有攻擊){

在第i行第j列安放皇后；

if(i==n-1)

輸出一個布局；

elseQueen(i+1);

撤消第i行第j列的皇后；

}}}數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第63頁。64算法求精voidQueen(inti){for(intj=0;j<n;j++){if(!col[j]&&!md[n+i-j-1]&&!sd[i+j]){

/*第i行第j列沒有攻擊*/

col[j]=md[n+i-j-1]=sd[i+j]=1;

q[i]=j;

/*在第i行第j列安放皇后*/

數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第64頁。65

if(i==n-1){/*輸出一個布局*/

for(intk=0;k<n;k++)

cout<<k<<q[k]<<‘,’;cout<<endl;}elseQueen(i+1);

col[j]=md[n+i-j-1]=sd[i+j]=0;

q[i]=0;/*撤消第i行第j列的皇后*/}}}數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第65頁。66迷宮問題小型迷宮

路口動作 結果

1

(入口)正向走進到2

2

左拐彎進到3

3

右拐彎進到4

4

(堵死)回溯 退到3

3

(堵死)回溯 退到2

2

正向走進到5

5

(堵死)回溯 退到2

2

右拐彎進到6

6

左拐彎進到7(出口)

4352176

6

左0 直2右0

行3行5行60 040 000 00700

7小型迷宮的數(shù)據(jù)數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第66頁。67迷宮的類定義#include<iostream.h>#include<fstream.h>#include<stdlib.h>classMaze{private:intMazeSize; intEXIT;

Intersection*intsec; public:Maze(char*filename);

intTraverseMaze(intCurrentPos);}交通路口結構定義structIntersection{

intleft;

intforward;

intright;}數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第67頁。68Maze::Maze(char*filename){

//構造函數(shù)：從文件

filename

中讀取各路口

//和出口的數(shù)據(jù)

ifstreamfin;

fin.open(filename,ios::in|ios::nocreate);

//為輸入打開文件,文件不存在則打開失敗

if(!fin){

cerr<<“迷宮數(shù)據(jù)文件”<<filename

<<“打不開”<<endl;

exit(1);

}

fin>>MazeSize;

//輸入迷宮路口數(shù)數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第68頁。69

intsec=newIntersection[MazeSize+1];

//創(chuàng)建迷宮路口數(shù)組

for(inti=1;i<=MazeSize;i++)

fin>>intsec[i].left>>intsec[i].forward

>>intsec[i].right;

fin>>EXIT;//輸入迷宮出口

fin.close();}迷宮漫游與求解算法

intMaze::TraverseMaze(intCurrentPos){

if(CurrentPos>0){

//路口從1開始數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第69頁。70

if(CurrentPos==EXIT){

//出口處理

cout<<CurrentPos<<"";

return1;}

else//遞歸向左搜尋可行

if(TraverseMaze(intsec[CurrentPos].left))

{cout<<CurrentPos<<“”;

return1;}

else//遞歸向前搜尋可行

if(TraverseMaze(intsec[CurrentPos].forward))

{cout<<CurrentPos<<“”;

return1;}

else//遞歸向右搜尋可行

if(TraverseMaze(intsec[CurrentPos].right))

{cout<<CurrentPos<<"";

return1;}

}

return

0;

}數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第70頁。71隊列的應用：打印楊輝三角形算法逐行打印二項展開式

(a+b)i的系數(shù)：楊輝三角形(Pascal’striangle)數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第71頁。72分析第i行元素與第i+1行元素的關系從前一行的數(shù)據(jù)可以計算下一行的數(shù)據(jù)i=2i=3i=401331014641012100110sts+t數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第72頁。73從第i行數(shù)據(jù)計算并存放第i+1行數(shù)據(jù)121013310

146s=0t=1t=2t=1t=0t=1t=3t=3t=1t=0t=1s+ts=ts=ts=ts=ts=ts=ts=ts=ts+t

s+t

s+t

s+t

s+t

s+ts+ts+t數(shù)據(jù)結構中的棧與隊列課件全文共82頁，當前為第73頁。74利用隊列打印二項展開式系數(shù)的算法#include

<stdio.h>#include

<iostream.h>#include"queue.h"voidYANGHVI(intn){Queueq(n+3);

//隊列初始化

q.MakeEmpty();q.EnQueue(1);q.EnQueue(1);

ints