【正文】 ch=()。 while((ch!=?‘)||(!())) { if (!In(ch,OP)) { coutch。 ch=()。 } 81 else switch(pare( s. GetTop(),ch) { // s. GetTop()為 ?1 ,ch為 ?2 case ?‘ : ( ch)。 ch=()。 break。 case ?==‘: ch=()。 ch=()。 break。 case ?‘ : { op=()。 coutop。 break。 } } //switch } //while } //InPost 82 入口 出口 (4) 求迷宮問題 83 class PosType{ int x,y。 } class Block{ //通道塊 int ord。 //通道塊的序號 PosType seat。 //通道塊在迷宮中的坐標(biāo)位置 int direction。 //從此通道塊走向下一通道塊的方向 }。 class Maze { Block e。 public: bool MazePath((PosType start, PosType end)。 …… }。 84 N(北 ) [i1, j] W(西 ) [i, j1] [i, j] E(東 ) [i, j+1] S(南 ) [i+1, j] 85 bool Maze::MazePath((PosType start, PosType end){ SeqStack s。 curpos=start。 //當(dāng)前位置為入口位置 curstep=1。 //探索第一步 do{ if(Pass(curpos)){ //當(dāng)前位置可以通過且未走過 footprint(curpos)。 //留下足印 e=new Block(curstep,curpos,1)。 (e)。 //加入路徑 if(curpos==end) return(true)。 //到達(dá)終點 curpos=NextPos(curpos,1)。 //下一個位置是當(dāng)前位置的東鄰 curstep++。 } //if 迷宮求解算法 86 else{ //當(dāng)前位置不通 if(!()){ e=()。 while(==4 amp。amp。 !()){ MarkPrint()。 e=()。 //留下不能通過的標(biāo)記并后退 } // while if(4){ ++。 (e)。 //換下一個方向探索 curpos=NextPos(, )。 //新位置是舊位置的相鄰塊 } //end if } //if }// else }while(!())。 return(false)。 }。// Mazth 87 遞歸總結(jié) 1. 遞歸是重要的設(shè)計和編程工具，使許多算法變得簡單，易于設(shè)計和實現(xiàn) . －－－－優(yōu)點 2. 遞歸使算法的時間復(fù)雜度和空間復(fù)雜度同時增大，有時會導(dǎo)致效率急劇惡化，或者溢出系統(tǒng)棧。 －－－－缺點 3. 使用遞歸時應(yīng)該權(quán)衡效率和設(shè)計的關(guān)系。在有足夠的空間并且時間要求不高的情況下可以使用遞歸。 88 隊列的應(yīng)用 舞會在星期五晚舉行。舞會開始之前，參加舞會的男士和女士各自排隊進(jìn)入舞廳。舞會開始，從兩隊中按順序組成舞伴開始跳舞。一曲結(jié)束后，男士和女士分別再進(jìn)入各自隊列。如果男士和女士人數(shù)不等，則多出的人只能等到下一舞曲開始。 舞伴 用兩個隊列來表示男士和女士等待隊列，舞會開始前時，按其性別加入不同隊列，舞曲開始后，順序地同時刪除兩個隊列的元素來組成舞伴，直到某一隊列為空。 要求用算法來模擬一支舞曲開始后男士和女士組成舞伴的情況，以及多少人在等待的情況。 89 class Person{ //Person為跳舞人的類 char *name。 char sex。 //‖F(xiàn)‖為男，” M‖為女 }。 void Dance_parnter() { SeqQueue M_Dancer, F_Dancer。 // M_Dancer為男士隊列， F_Dancer為女士隊列 Person p。 //Person為跳舞人的類 Person_arrive(p,name,sex)。 //有人到達(dá)舞會 ,將其姓名和性別賦給 p //建立男士隊列和女士隊列 =name。 =sex。 隊列的應(yīng)用 90 while（ strcmp(,‖‖)0） { //將男士和女士分別入各自隊列 if (= =‘F‘) (p)。 else (p)。 Person_arrive(p,name,sex)。 } //while 91 while(!() amp。amp。 !()){ //順序地同時從兩個隊列中刪除 p=()。 cout‖ ―。 //輸出男舞伴的姓名 p=F_Dance. Leave ()。 coutendl。 //輸出女舞伴的姓名 } //while //若任一隊列中還有沒選上的，輸出人數(shù)，以及第一個人的姓名 92 if(!()){ //女士隊列為空 cout‖there are ―()‖men waiting for the next round‖endl。 cout().name‖will be the first to get a partner‖endl。 } else if(!()){ //男士隊列為空 cout‖there are ―()‖women waiting for the next round‖endl。 cout().name‖will be the first to get a partner‖endl。 } }//Dance_partner 93 本章小結(jié) ?理解 棧 和 隊列 這兩種抽象數(shù)據(jù)類型的特點及 與線性表的異同 ?熟悉 順序棧 和 鏈棧 的組織方法以及基本運算的實現(xiàn) ?掌握 鏈隊列 和 循環(huán)隊列 的組織方法、簡單算法實現(xiàn)。 ? 隊滿、隊空 的判斷條件及其描述 (難點 )。 ?掌握 遞歸 的三要素 ?能編寫一些簡單的 遞歸 算法；理解一些比較復(fù)雜的遞歸算法。 ?棧的應(yīng)用 94 書面作業(yè) P87: 31, 32， 35 31(2)換為 void main( ) { Queue Q。 char x=?e‘。 y=?c‘。 (‘h‘)。 (‘r‘)。 (y)。 x=()。 (x)。 x=()。 (‘a(chǎn)‘)。 while(!()) { y=()。 couty。 } coutx。 } 結(jié)果： char 95 35: 如果希望循環(huán)隊列中的數(shù)組元素都能得到利用，需設(shè)置一個標(biāo)志域 tag，以 tag為 0或 1來區(qū)分隊列空和滿的情況。實現(xiàn)此結(jié)構(gòu)下的入隊和出隊操作。 void Enter(Type amp。item ) { //入隊 if (tag==1amp。amp。front==rear) return。 //隊滿 QueueList[rear]=item。 rear=(rear+1) % MaxQSize。 if(front==rear) tag=1。 } 96 35: DataType Leave( ) { //出隊 if (tag==0 amp。amp。 fornd==rear) return。 // 隊空 item=QueueList[front]。 front=(front+1) % MaxQSize。 if(front==rear) tag=0。 return(item)。 } 97 補(bǔ)充題 : 已知 A[n]為整數(shù)數(shù)組，試寫出實現(xiàn)下列運算的遞歸算法。 (1) 求數(shù)組 A中的最大整數(shù)。 (2) 求 n個整數(shù)的和。 (1) int MaxKey(int n) { if(n==1) return(A[0])。 temp=MaxKey(n1)。 if(A[n1]temp) return A[n1]。 else return temp。 } 98 (2) 求 n個整數(shù)的和。 int Sum(int n) { if(n==1) return(A[0])。 else return(A[n1]+Sum(n1))。 } 99