棧隊列

遞歸第三章棧和隊列1棧(Stack)定義:是限定僅在表尾進行插入或刪除操作的線性表。允許插入和刪除的一端 稱為棧頂(top)，另一端 稱為棧底(bottom)特點：后進先出(LIFO)a1topbottoman....進棧

出棧2棧的主要操作ADTStack{//對象由數據類型為StackData的元素構成

intPush(stack*S,StackDatax);//進棧

intPop(stack*S,StackData&x);//出棧

intGetTop(stack*S,StackData&x);//取棧頂

voidInitStack(stack*S);//置空棧

intStackEmpty(stack*S);//判棧空否

intStackFull(stack*S);//判棧滿否}3棧的表示和實現順序棧：棧的順序存儲結構，利用一組地址連續的存儲單元依次存放自棧底到棧頂的數據元素，指針top指向棧頂元素在順序棧中的下一個位置，

base為棧底指針，指向棧底的位置。base空棧a進棧b進棧aabtopbasetopbasetop4toptopabcdee進棧abcdef進棧溢出abde出棧cbasebasebasetop5順序棧的類型表示:#defineSTACK_INIT_SIZE100；#defineSTACKINCREMENT10；typedefcharStackData;typedefstruct{ //順序棧定義

StackData*base;//棧底指針

StackData*top;//棧頂指針

intstacksize；//當前已分配的全部存儲空間}SeqStack；6判棧空intStackEmpty(SeqStack*S){ if(S->top==S->base)return1//判?？?空則返回1elsereturn0;//否則返回0

}判棧滿intStackFull(SeqStack*S){ if(S->top-S->base>=S->StackSize)return1

//判棧滿,滿則返回1 elsereturn0;//否則返回0}順序棧的基本運算:7初始化voidInitStack(SeqStack*S){//置空棧S->base=(StackData*)malloc(STACK_INIT_SIZE* sizeof(StackData));

if(!S->base)exit(OVERFLOW);S->top=S->base;S->stacksize=STACK_INIT_SIZE;Returnok;}8入棧intPush(SeqStack*S,StackDatax){//插入元素x為新的棧頂元素

if(StackFull(S)){ S->base=(StackData*)realloc(S->base, (S->stacksize+STACKINCREMENT)* sizeof(StackData)); if(!S->base)exit(overflow); S->top=S->base+S->stacksize; S->stacksize+=STACKINCREMENT;//追加存儲空間} *(S->top)=x;

（S->top）++;Returnok}9取棧頂元素intGetTop(SeqStack*S,StackData&x){//若?？辗祷?,否則棧頂元素讀到x并返回1

if(StackEmpty(S))return0; x=*(S->top-1); return1;}10出棧intPop(SeqStack*S,StackData&x){//若?？辗祷?,否則棧頂元素退出到x并返回1

if(StackEmpty(S))return0;

--(S->top); x=*(S->top);return1;}11鏈式棧:棧的鏈接表示

鏈式棧無棧滿問題，空間可擴充插入與刪除僅在棧頂處執行鏈式棧的棧頂在鏈頭top12鏈式棧(LinkStack)的定義typedefintStackData;typedefstructnode{StackDatadata; //結點

structnode*link; //鏈指針}StackNode;typedefstruct{StackNode*top;//棧頂指針}LinkStack;13鏈式棧操作實現初始化voidInitStack(LinkStack*S){S->top=NULL;}入棧intPush(LinkStack*S,StackDatax){StackNode*p=(StackNode*)malloc(sizeof(StackNode));p->data=x;p->link=S->top;S->top=p;return1;}14判?？読ntStackEmpty(LinkStack*S){returnS->top==NULL;}出棧intPop(LinkStack*S,StackData&x){if(StackEmpty(S))return0;

StackNode*p=S->top;

S->top=p->link;

x=p->data;free(p);return1;}15取棧頂intGetTop(LinkStack*S,StackData&x){if(StackEmpty(S))return0;x=S->top->data;return1;}置?？読ntMakeEmpty(LinkStack*S){While(S->top!=NULL){ StackNode*p=S->top; S->top=S->top->link; free(p); }}16程序中定義多個棧（1）定義共享棧數據結構#defineMAX100intstack[MAX],top1=0,top2=MAX-1;棧1top1top2棧217(2)共享進棧算法

voidpush1(intx){if(top1>top2)printf(“overflow”);else{stack[top1]=x;top1++;}}voidpush2(intx){if(top1>top2)printf(“overflow”);else{stack[top2]=x;top2--;}18(3)共享出棧算法

intpop1(){iftop1==0){printf(“underflow”);return(NULL);}top1--;return(stack[top1]);}intpop2(){if(top2==MAX-1){printf(“underflow”);return(NULL):}top2++;return(stack[top2]);}19棧的應用舉例

數制轉換 行編輯程序 迷宮求解 表達式求值20采用對十進制數除8取余的方法，可得到八進制數的倒序。

N=(Ndivd)×d+Nmodd

例如：（1348)10=(2504)8

，其運算過程如下：

NNdiv8Nmod8

13481684

16821 0

212 5

20 2計算順序輸出順序21數制轉換

十進制數轉換為八進制數。voidconversion(){InitStack(S);scanf("%d",N);while(N){Push(S,N%8);N=N/8;}while(!StackEmpty(S)){Pop(S,e);printf("%d",e);}}//conversion22行編輯程序 在用戶輸入一行的過程中，允許用戶輸入出差錯，并在發現有誤時可以及時更正。 設立一個輸入緩沖區，用以接受用戶輸入的一行字符，然后逐行存入用戶數據區;并假設“#”為退格符，“@”為退行符。假設從終端接受兩行字符：

whli##ilr#e（s#*s)outcha@putchar(*s=#++);實際有效行為：

while(*s)putchar(*s++);23VoidLineEdit(){ InitStack(s); ch=getchar(); while(ch!=EOF){//EOF為全文結束符

while(ch!=EOF&&ch!='\n'){ switch(ch){ case'#':Pop(S,ch);break; case'@':ClearStack(S);break;

//重置S為空棧

default:Push(S,ch);break; } ch=getchar();//從終端接收下一個字符

}//while24將從棧底到棧頂的字符傳送至調用過程的數據區；ClearStack(S);//重置S為空棧if(ch!=EOF)ch=getchar(); }//whileDestroyStack(s);}25迷宮求解通常用的是“窮舉求解”的方法26迷宮路徑算法的基本思想若當前位置“可通”，則納入路徑，繼續前進;若當前位置“不可通”，則后退，換方向繼續探索;若四周“均無通路”，則將當前位置從路徑中刪除出去。27設定當前位置的初值為入口位置；

do｛若當前位置可通，則｛將當前位置插入棧頂；若該位置是出口位置，則算法結束；否則切換當前位置的東鄰方塊為新的 當前位置；｝

………..

28否則

{若棧不空且棧頂位置尚有其他方向未被探索，則設定新的當前位置為:沿順時針方向旋轉找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，則｛ 刪去棧頂位置；//從路徑中刪去該通道塊

若棧不空，則重新測試新的棧頂位置，直至找到一個可通的相鄰塊或出棧至?？?｝｝｝while(棧不空）；29typedefstruct{ int ord; //序號

PosType seat;//坐標

int di; //方向}SElemType; //棧元素StatusMazePath(MazeTypemaze,PosTypestart,PosTypeend){ InitStack(S);curpos=start;//當前位置

curstep=1;30 do{ if(Pass(curpos)){//可通過且未走過

FootPrint(curpos);//記已通過標記

e=(curstep,curpos,1); Push(S,e); if(curpos==end)return(TRUE); curpos=NextPos(curpos,1); curstep++; }//if31 else{ if(!StackEmpty(S)){ Pop(S,e); while(e.di==4&&!StackEmpty(S)){ MarkPrint(e.seat);Pop(S,e);

//記不能通過標記

}//while if(e.di<4){ e.di++;Push(S,e); curpos=NextPos(e.seat,e.di); }//if }//if }//else }while(!StackEmpty(S)); return(FALSE);}//MazePath32限于二元運算符的表達式定義:

表達式::=(操作數)+(運算符)+(操作數)

操作數::=簡單變量|表達式簡單變量::=標識符|無符號整數Exp=S1+OP+S2前綴表示法OP

+S1+S2中綴表示法

S1+

OP

+S2后綴表示法

S1+S2+

OP表達式求值33例如:Exp=ab

+

(cd/e)f前綴式:+

ab

c/def中綴式:ab

+

cd/ef后綴式:ab

cde/f

+表達式標識方法b-ca/*def*+34后綴表達式求值先找運算符，再找操作數例如：

abcde/f+abd/ec-d/e(c-d/e)f35從原表達式求得后綴式方法設立暫存運算符的棧;設表達式的結束符為“#”,予設運算符棧的棧底為“#”若當前字符是操作數，則直接發送給后綴式;(后綴與前綴式操作數的順序是相同的)若當前運算符的優先數高于棧頂運算符，則進棧;否則，退出棧頂運算符發送給后綴式;“(”對它之前后的運算符起隔離作用，“)”為自左括弧開始的表達式的結束符。36表達式求值的算法采用“算符優先法”，在表達式中,優先級的順序是:（1）括號的優先級最高,對括號內的各種運算符有:先乘除、再加堿，同級運算從左至右。（2）先括號內，后括號外，多層括號，由內向外。任何表達式都是由操作數、運算符和界符組成。操作數可以是常量、變量、常數運算符有算術運算符、關系運算符、邏輯運算符界符包括左右括號算式結束符。運算符和界符統稱為“算符”。37在算符集中，在每一個運算步，相鄰的算符c1和c2之間的關系是如下三種情況（c1出現在c2之前）：c1<c2,c1的優先級低于c2c1=c2,c1的優先級等于c2c1>c2,c1的優先級大于c27*(5-3)38算符間優先級＋－＊/()＃＋－＊／（）＃>><<<>>>><<<>>>>>><>>>>>><>><<<<<=>>>>>><<<<<=c2c139為實現算符優先算法，在這里用了兩個工作棧。一個存放算符OPTR，另一個存放數據OPND。算法思想是：（1）首先置數據棧為空棧，表達式起始符“?！睘樗惴麠５臈５自兀?）自左向右掃描表達式，讀到操作數進OPND棧，讀到運算符，則和OPTR棧頂元素比較（棧頂元素為c1，讀到的算符為c2);若c1<c2,則c2進棧繼續掃描后面表達式；若c1＝c2,則（“＝”），即括號內運算結束，將c1出棧，并且c2放棄,繼并在操作數棧掃描后面表達式；若c1>c2,則將c1出棧，并在操作數棧取出兩個元素a和b按c1做運算，運算結果進OPND.重復直到表達式求值完畢。40例如：表達式3*(7-2),求值過程如下表：步驟OPTR棧OPND棧輸入字符主要操作1＃3*(7-2)#PUSH(OPND,’3’)2＃3*(7-2)#PUSH(OPTR,’*’)3＃＊3(7-2)#PUSH(OPTR,’(’)4＃＊（37-2)#PUSH(OPND,’7’)5＃＊（37-2)#PUSH(OPTR,’-’)6＃＊（-372)#PUSH(OPND,’2’)7＃＊（372)#operate(‘7’,’-’,’2’)8＃＊（35)#POP(OPTR)消去括號9＃＊15#operate(‘3’,’*’,’5’)10＃15#PUSH(OPTR,’*’)41為使兩個算符比較方便,給算符設置優先級,如下表,其中c1為棧內元素,c2為棧外元素算符棧內優先級棧外優先級*/43+-21(05)50#-1-142算符比較算法算符比較算法charPrecede(charc1,charc2){intc_temp1,c_temp2;switch(c1){case‘*’:case‘/’:c_temp1=4;break;case‘+’:case‘-’:c_temp1=2;break;case‘(’:c_temp1=0;break;case‘)’:c_temp1=5;break;case‘#’:c_temp1=-1;}43switch(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_temp1<c_temp2)return(‘<‘);if(c_temp1=c_temp2)return(‘=‘);if(c_temp1>c_temp2)return(‘>‘);}switch(c1){case‘*’:case‘/’:c_temp1=4;break;case‘+’:case‘-’:c_temp1=2;break;case‘(’:c_temp1=0;break;case‘)’:c_temp1=5;break;case‘#’:c_temp1=-1;}44intexpress(){Initstack(OPTR);Push(OPTR,’#’);InitStack(OPND);w=getchar();while(w!=‘#’||GetTop(OPTR)!=‘#’){if(!In(w,OP)){Push(OPND,w);w=getchar();}else //OP是操作符集合switch(Precede(GetTop(OPTR),w)){case‘<‘:Push(OPTR,w);w=getchar();break;case‘=‘:Pop(OPTR);w=getchar();break;case‘>‘:op=Pop(OPTR);b=Pop(OPND);a=Pop(OPND);push(OPND,Operate(a,op,b));break;}}return(Getop(OPND));45OperandTypeEvaluateExpression(){ InitStack(OPTR);Push(OPTR,’#’); InitStack(OPND);c=getchar(); while(c!=‘#’||GetTop(OPTR)!=‘#’){ if(!In(c,OP)){Push(OPND,c); c=getchar();} else switch(Precede(GetTop(OPTR),c){ case‘<‘://棧頂元素優先權低

Push(OPTR,c);c=getchar(); break;算符優先算法求表達式值46 case‘=‘://脫括號

Pop(OPTR,x);c=getchar(); break; case‘>’://退棧并計算

Pop(OPTR,theta); Pop(OPND,b);Pop(OPND,a); Push(OPND,Operate(a,theta,b)); break; }//switch }//while returnGetTop(OPND);}//EvaluateExpression47隊列定義:只允許在表的一端進行插入，而在另一端刪除元素的線性表。在隊列中，允許插入的一端叫隊尾（rear），允許刪除的一端稱為對頭(front)。特點：先進先出(FIFO)

a1，a2，a3，…，an出隊列入隊列隊頭隊尾48鏈隊列：隊列的鏈式表示鏈隊列中，有兩個分別指示隊頭和隊尾的指針。鏈式隊列在進隊時無隊滿問題，但有隊空問題。datanextfrontreardatanextfrontrear49frontrearx^元素x入隊frontrearx^y^元素y入隊frontrearx^^y元素x出隊frontrear^空隊列^frontrearNULL空隊列50鏈式隊列的定義typedefintQueueData;typedefstructnode{ QueueDatadata; //隊列結點數據

structnode*link;//結點鏈指針}QueueNode;typedefstruct{QueueNode*rear,*front;}LinkQueue;51鏈隊列的主要操作初始化voidInitQueue(LinkQueue*Q){Q->rear=Q->front=NULL;}隊空intQueueEmpty(LinkQueue*Q){returnQ->front==NULL;}取隊頭元素intGetFront(LinkQueue*Q,QueueData&x){if(QueueEmpty(Q))return0; x=Q->front->data;return1; }52入隊intEnQueue(LinkQueue*Q,QueueDatax){QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode));p->data=x;p->link=NULL;if(Q->front==NULL)

//空,創建第一個結點

Q->front=Q->rear=p;elseQ->rear->link=p;//入隊

Q->rear=p;return1;}53出隊intDeQueue(LinkQueue*Q,QueueData&x){//刪去隊頭結點，并返回隊頭元素的值

if(QueueEmpty(Q))return0; //判隊空

QueueNode*p=Q->front; x=p->data; //保存隊頭的值

Q->front=Q->front->link; //新隊頭

free(p);return1; }54循環隊列(CircularQueue)順序隊列—隊列的順序存儲表示。用一組地址連續的存儲單元依次存放從隊列頭到隊列尾的元素，指針front和rear分別指示隊頭元素和隊尾元素的位置。插入新的隊尾元素，尾指針增1，rear=rear+1，刪除隊頭元素，頭指針增1，front=front+1，因此，在非空隊列中，頭指針始終指向隊列頭元素，而尾指針始終指向隊列尾元素的下一個位置。隊滿時再進隊將溢出解決辦法：將順序隊列臆造為一個環狀的空間，形成循環(環形)隊列55隊列的進隊和出隊frontrear空隊列frontrearA,B,C,D進隊ABCDfrontrearA,B出隊CDfrontrearE,F,G進隊CDEFGCDEFGfrontrearH進隊,溢出56循環隊列(CircularQueue)隊頭、隊尾指針加1，可用取模(余數)運算實現。隊頭指針進1:front=(front+1)%maxsize;隊尾指針進1:rear=(rear+1)%maxsize;隊列初始化：front=rear=0;隊空條件：front==rear;隊滿條件：(rear+1)%maxsize==front;

01234567循環隊列frontrearMaxsizerontBCDrear一般情況AC01234567隊滿(錯誤)frontrearDEFGABCH01234567rear空隊列frontC01234567隊滿(正確)frontrearDEFGABC58#defineMAXSIZE100Typedefstruct{ QueueData*data; intfront; intrear;}SeqQueue循環隊列的類型定義59循環隊列操作的實現

初始化隊列voidInitQueue(SeqQueue*Q){//構造空隊列Q->data=(QueueData*)malloc(MAXSIZE*sizeof(QueueData));If(!Q->data)exit(OVERFLOW);Q->rear=Q->front=0;Returnok}60判隊空intQueueEmpty(SeqQueue*Q){returnQ->rear==Q->front;}判隊滿intQueueFull(SeqQueue*Q){return(Q->rear+1)%QueueSize==Q->front;}入隊intEnQueue(SeqQueue*Q,QueueDatax){if(QueueFull(Q))return0;Q->data[Q->rear]=x;Q->rear=(Q->rear+1)%MAXSIZE;return1;}61出隊intDeQueue(SeqQueue*Q,QueueData&x){if(QueueEmpty(Q))return0; x=Q->data[Q->front]; Q->front=(Q->front+1)%MAXSIZE; return1;}取隊頭intGetFront(SeqQueue*Q,QueueData&x){if(QueueEmpty(Q))return0;x=Q->data[Q->front];return1;}求隊列長度intQueueLength(SeqQueue*Q){ return(Q->rear–Q->front+MAXSIZE)%MAXSIZE;}62隊列應用舉例—打印二項展開式(a+b)i的系數楊輝三角形(Pascal’striangle)

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

63分析第i行元素與第i+1行元素的關系目的是從前一行的數據可以計算下一行的數據64從第i行數據計算并存放第i+1行數據65voidYANGHUI(intn){Queueq;//隊列初始化

q.MakeEmpty();q.EnQueue(1);q.EnQueue(1);//預放入第一行的兩個系數

ints=0;for(inti=1;i<=n;i++){//逐行處理

cout<<endl; //換行

q.EnQueue(0); for(intj=1;j<=i+2;j++){//處理第i行的i+2個系數

intt=q.DeQueue();//讀取系數

q.EnQueue(s+t);//計算下一行系數，并進隊列

s=t;if(j!=i+2)cout<<s<<‘’;//打印一個系數，第i+2個為0 }}}66優先級隊列(PriorityQueue)優先級隊列是不同于先進先出隊列的另一種隊列。每次從隊列中取出的是具有最高優先權的元素例如下表：任務的優先權及執行順序的關系數字越小，優先權越高，設不存在同優先級元素67#include<assert.h>#include<iostream.h>$include<stdlib.h>constint

maxPQSize=50;//缺省元素個數template<classType>class

PQueue

{public:

PQueue();

~PQueue(){delete[]pqelements;}

voidPQInsert(constType&

item);

Type

PQRemove();

優先隊列的類定義68

voidmakeEmpty(){

count=-1;}

int

IsEmpty()const{returncount==

-1;}

intIsFull()const{returncount==maxPQSize;}

int

Length()const{returncount;}/

/優先級隊列元素個數private:Type*pqelements;

//存放數組（優先級隊列數組）

int

count;

//隊列元素計數 }69template<classType>PQueue<Type>::PQueue():count(-1){pqelements=newType[maxPQSize]; assert(pqelements!=0);//分配斷言} //創建優先級隊列template<classType>voidPQueue<Type>::PQInsert(constType&item){assert(!IsFull()); //判隊滿斷言

count++；pqelements[count]=item; } //插入元素到隊尾優先級隊列部分成員函數的實現70template<classType>TypePQueue<Type>::PQRemove(){assert(!IsEmpty()); //判隊空斷言

Typemin=pqelements[0]; intminindex=0;for(inti=1;i<count;i++)//尋找最小元素

if(pqelements[i]<min)//存于min {min=pqelements[i];minindex=i;}pqelements[minindex]=pqelements[count-1];

//用最后一個元素填補要取走的最小值元素

count--;//優先級隊列中元素個數減一

returnmin;} //從隊中刪除最小值（優先級最高）元素71離散事件模擬日常生活中排隊活動的模擬程序需要用到隊列和線性表的數據結構，是隊列的典型應用。設銀行有四個窗口，從開門起每個窗口一個時刻只能接待一個客戶，人多時客戶需排隊。當客戶進入銀行時，如有窗口空閑則直接辦理業務，否則會排在人數最少的隊伍后面。先要求編程序模擬銀行的業務活動并計算一天中客戶在銀行的平均逗留時間。72思路：為求平均時間要知道每個客戶到達和離開銀行的兩個時刻，所有客戶逗留時間總和除以客戶數便是平均時間?？蛻舻竭_和離開銀行兩個時刻發生的事情成為“事件”，整個程序按事件發生的先后順序進行處理，即事件驅動模擬。73銀行客戶的離散事件驅動模擬程序：voidBank_Simulation(intCloseTime){//銀行業務模擬，統計一天內客戶在銀行逗留的平均時間。

OpenForDay;//初始化

while(MoreEvent)do{ EventDrived(OccurTime,EventType);//事件驅動

switch(EventType){ case‘A’:CustomerArrived;break;//處理客戶到達事件

case‘D’:CustomerDeparture;break;//處理客戶離開事件

default:Invalid; }//switch }//while

CloseForDay;//計算平均逗留時間}//Bank_Simulation74具體實現：1.算法中處理的主要對象為“事件”，事件的主要信息是事件類型和發生時刻。事件有兩類：客戶到達事件，其發生時刻隨客戶到來自然形成；客戶離開事件，其發生時刻由客戶事物所需時間和等待時間決定。由于事件驅動是按事件發生時刻的先后順序進行，則事件表是有序表，其主要操作是插入和刪除事件。類型定義如下：typedefstruct{ intOccurTime;//事件發生時刻

intNType; //事件類型，0表示到達事件，1至4表示四個窗口的離開事件}Event,ElemType;//事件類型，有序鏈表LinkList的數據元素類型typedefLinkListEventList//事件鏈表類型，定義為有序鏈表752.模擬程序的另一種數據結構是表示客戶排隊的隊列，銀行的四個窗口對應四個隊列，隊列中客戶的信息是其到達的時刻和辦理事物所需時間。typedefstruct{ intArrivalTime;//到達時刻

intDuration;//辦理事物所需時間}QElemType;//隊列的數據元素類型763.每個隊列的隊頭是正在辦理事物的客戶，他辦完事物離開隊列的時刻就是即將發生的客戶離開事件的時刻，即對每個隊頭客戶都存在一個將要驅動的客戶離開事件。因此在任何時刻即將發生的事件只有五種可能：（1）新客戶到達；（2）1號窗口客戶離開；（3）2號窗口客戶離開；（4）3號窗口客戶離開；（5）4號窗口客戶離開。由以上分析可見，在這個模擬程序中只需要兩種數據類型：有序鏈表和隊列。77主要操作的實現：設第一個客戶進門的時刻為0，即是模擬程序處理的第一個事件，之后每個客戶到達的時刻在前一個客戶到達時設定。因此在客戶到達事件發生時須先產生兩個隨機數：其一為此時刻到達的客戶辦理事務所需時間durtime;其二為下一客戶將到達的時間間隔intertime,假設當前事件發生的時刻為occurtime，則下一個客戶到達事件發生的時刻為occurtime+intertime。由此應產生一個新的客戶到達事件插入事件表；剛到達的客戶則應插入到當前所含元素最少的隊列中；若該隊列在插入前為空，則還應產生一個客戶離開事件插入事件表?？蛻綦x開事件先計算該客戶在銀行逗留的時間,然后從隊列中刪除該客戶后查看隊列是否空,若不空則設定一個新的隊頭客戶離開事件.78銀行事件驅動模擬程序算法:EventListev; //事件表Event en; //事件LinkQueue q[4]; //4個客戶隊列QElemType customer; //客戶記錄intTotalTime,CustomerNum; //累計客戶逗留時間，客戶數intcmp(Eventa,Eventb);//依事件a的發生時刻<或=或>事件b的發生時刻分別返回-1或0或1voidOpenForDay(){//初始化操作

TotalTime=0;CustomerNum=0;//初始化累計時間和客戶數為0 InitList(ev); //初始化事件鏈表為空表

en.OccurTime=0;en.NType=0;//設定第一個客戶到達事件

OrderInsert(ev,en,(*cmp)());//插入事件表

for(i=0;i<4;++i)InitQueue(q[i]);//置空隊列}//OpenForDay79voidCustomerArrived(){//處理客戶到達事件，en.NType=0 ++CustomerNum; Random(durtime,intertime);//生成隨機數

t=en.OccurTime+intertime;//下一客戶到達時刻

if(t<CloseTime) //銀行尚未關門，插入事件表

OrderInsert(ev,(t,0),(*cmp)()); i=Minimun(q); //求長度最短隊列

EnQueue(q[i],(en.OccurTime,durtime)); if(QueueLength(q[i])==1) OrderInsert(ev,(en.OccurTime+durtime,i),(*cmp)());//設定第i隊列的一個離開事件并插入事件表}//CustomerArrived80VoidCustomerDeparture(){ //處理客戶離開事件，en.NType>0 i=en.NType;DelQueue(q[i],customer); //刪除第i隊列的排頭客戶

TotalTime+=en.OccurTime–customer.ArrivalTime;//累計客戶逗留時間

if(!QueueEmpty(q[i])){//設定第i隊列的一個離開事件并插入事件表

GetHead(q[i],customer); OrderInsert(ev,(en.OccurTime+customer.Duration,i),(*cmp()); }//if}//CustomerDeparture81voidBank_Simulation(intCloseTime){ OpenForDay;//初始化

while(!EmptyEventList(ev)){ DelFirst(GetHead(ev),p);en=GetCurElem(p); if(en.NType==0) CustomerArrived;//處理客戶到達事件

elseCustomerDeparture;//處理客戶離開事件

}

//計算并輸出平均逗留時間

printf(“TheAverageTimeis%f\n”,TotalTime/CustomerNum);}//Bank_Simulation82遞歸定義

若一個對象部分地包含它自己,或用它自己給自己定義,則稱這個對象是遞歸的； 若一個過程直接地或間接地調用自己,則稱這個過程是遞歸的過程。三種遞歸情況

定義是遞歸的數據結構是遞歸的問題的解法是遞歸的83定義是遞歸的求解階乘函數的遞歸算法longFactorial(longn){if(n==0)return1;elsereturnn*Factorial(n-1);}例1.階乘函數84求解階乘n!的過程主程序

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

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

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

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

返回1參數0直接定值=1

返回1參數傳遞結果返回遞歸調用回歸求值85例2.計算斐波那契數列函數Fib(n)的定義遞歸算法

longFib(longn){

if(n<=1)returnn;

elsereturnFib(n-1)+Fib(n-2);}

如F0=0,F1=1,F2=1,F3=2,F4=3,F5=5

8687當一個函數及它的一個變量是由函數自身定義時，稱這個函數是雙遞歸函數。Ackerman函數A(n，m)定義如下：例3Ackerman函數intackerman(intn,intm)

{if(n==0&&m>=0)return1;if(n==1&&m==0)return2;

if(m==0&&n>=2)returnn+2;returnackerman(ackerman(n-1,m),m-1);

}88A(n，m)的自變量m的每一個值都定義了一個單變量函數：M=0時，A(n,0)=n+2M=1時，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2*nM=2時，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)=2^n。(小于n!)M=3時，類似的可以推出(大于n！)M=4時，A(n,4)的增長速度非常快，以至于沒有適當的數學式子來表示這一函數。(遠遠大于n！)89定義單變量的Ackerman函數A(n)為，A(n)=A(n，n)。定義其擬逆函數B(n)為：B(n)=min{k｜A(k)≥n}。即B(n)是使n≤A(k)成立的最小的k值。但在理論上B(n)沒有上界，隨著n的增加，它以難以想象的慢速度趨向正無窮大。由A(0)=1,A(1)=2,A(2)=4,A(3)=16推知B(1)=0,B(2)=1,B(3)=B(4)=2和B(5)=…=B(16)=3。由此可以看出B(n)的增長速度非常慢。A(4)=2^22…2其中2的層數為65535，這個數有log(A(4))位。所以，對于通常所見到的正整數n，有B(n)<=4但是理論上B(n)沒有上界，隨著n的增加，它將以難以想象的慢速度趨向正無窮大。（大大小于logn）數據結構是遞歸的有若干結點的單鏈表

例如單鏈表結構ff只有一個結點的單鏈表90例1.搜索鏈表最后一個結點并打印其數值voidSearch(ListNode*f){if(f->link==NULL)printf(“%d\n”,f->data);elseSearch(f->link);}fffffa0a1a2a3a4遞歸找鏈尾91例2.在鏈表中尋找等于給定值的結點,并打印其數值

void

Search(ListNode*f,ListData&

x){

if(f!=NULL)

if(f->data==x)

printf(“%d\n”,

f->data);

else

Search(f->link,x);

}ffff遞歸找含x值的結點x92

例如，漢諾塔(TowerofHanoi)問題的解法：如果n=1，則將這一個盤子直接從A柱移到C柱上。否則，執行以下三步：①用C柱做過渡，將A柱上的(n-1)個盤子移到B柱上：②將A柱上最后一個盤子直接移到C柱上；③用A柱做過渡，將B柱上的(n-1)個盤子移到C柱上。問題的解法是遞歸的9394設n個金盤移動F(n)次F(1)=1F(n)=F(n-1)+1+F(n-1)=2*F(n-1)+1F(n)+1=2*(F(n-1)+1)=22*(F(n-2)+1)=······=2n-1*(F(1)+1)=2n

F(n)=2n-1算法#include<iostream.h>#include"strclass.h”voidHanoi(intn,StringA,StringB,StringC){

//解決漢諾塔問題的算法

if(n==1)printf("move%s",A,"to%s,C); else{Hanoi(n-1,A,C,B); printf("move%s",A,"to%s,C);Hanoi(n-1,B,A,C);}}96遞歸過程與遞歸工作棧遞歸過程在實現時，需要自己調用自己。層層向下遞歸，退出時的次序正好相反：遞歸調用

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

返回次序主程序第一次調用遞歸過程為外部調用；遞歸過程每次遞歸調用自己為內部調用。97遞歸工作棧每一次遞歸調用時，需要為過程中使用的參數、局部變量等另外分配存儲空間。每層遞歸調用需分配的空間形成遞歸工作記錄，按后進先出的棧組織。局部變量返回地址參數活動記錄框架遞歸工作記錄98函數遞歸時的活動記錄……………….<下一條指令>Function(<參數表>)……………….<return>調用塊函數塊返回地址(下一條指令)局部變量參數99

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

RetLoc2

returntemp; }voidmain(){ intn;

n=Factorial(4);

RetLoc1

}

100計算Fact時活動記錄的內容遞歸調用序列0RetLoc21RetLoc22RetLoc23RetLoc24RetLoc1參數返回地址返回時的指令RetLoc1return4*6//返回24

RetLoc2return3*2//返回6

RetLoc2return1//返回1

RetLoc2return1*1//返回1

RetLoc2return2*1//返回2

101遞歸函數先操作后調用

例voidFunc(charch){if(ch<=‘z’){cout<<ch;

Func(ch+1);}}調用Func(‘a’);輸出abcdefghijklmnopqrstuvwxyz遞歸函數先調用后操作例voidFunc(charch){if(ch<=‘z’){Func(ch+1);cout<<ch;}}調用Func(‘a’);輸出zyxwvutsrqponmlkjihgfedcba遞歸函數操作調用操作例voidFunc(charch){if(ch<=‘z’){cout<<ch;Func(ch+1);cout<<ch;}}調用Func(‘a’);輸出

abcdefghijklmnopqrstuvwxyzzyxwvutsrqponmlkjihgfedcba遞歸函數調用操作調用例voidFunc(charch){if(ch<=‘d’){Func(ch+1);cout<<ch;

Func(ch+1);}}調用Func(‘a’);輸出dcdbdcdadcdbdcd遞歸過程改為非遞歸過程遞歸過程簡潔、易編、易懂遞歸過程效率低，重復計算多改為非遞歸過程的目的是提高效率單向遞歸和尾遞歸可直接用迭代實現其非遞歸過程其他情形必須借助棧實現非遞歸過程1061.用單純的循環方式非遞歸化

階乘的非遞歸算法（直接轉換法）longFactorial(longn){intprod=1,i;if(n>0)for(i=1;i<=n;i++)prod*=i;returnprod;}107求解階乘函數的遞歸算法longFactorial(longn){if(n==0)return1;elsereturnn*Factorial(n-1);}計算斐波那契數列的函數Fib(n)的定義求解斐波那契數列的遞歸算法

longFib(longn){

if(n<=1)returnn;

elsereturnFib(n-1)+Fib(n-2);}

如F0=0,F1=1,F2=1,F3=2,F4=3,F5=5108用單純的循環方式非遞歸化Fibonacci數列

（直接轉換法，迭代法計算）Fibonacci數列的迭代計算longFibIter(intn){longtwoback=1,oneback=1,current;inti;if(n==1‖n==2)return1;//FibIter(1)=FibIter(2)=1Else//current=twoback+oneback,n>=3for(i=3;i<=n;i++){current=twoback+oneback;twoback=oneback;oneback=current;}}1092.斐波那契數列的遞歸調用樹（間接轉換法，用棧保存中間結果）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)110Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)棧結點ntagtag=1,向左遞歸；tag=2,向右遞歸111Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)213141n=1sum=0+1223141n=2-23141n=0sum=1+03241n=3-241n=1sum=1+142n=4-2112Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)2142n=1sum=2+12242n=2-242n=0sum=3+0113longFibnacci(longn){ Stack<Node>S;Node*w;longsum=0;

//反復執行直到所有終端結點數據累加完

do{ while(n>1){w->n=n;w->tag=1;S.push(w);n--;}//向左遞歸到底,邊走邊進棧

sum=sum+n; //執行求和

114

while(!S.IsEmpty()){ w=S.getTop();S.Pop(); if(w->tag==1){//改為向右遞歸

w->tag=2;S.push(w);n=w->n–2;//F(n)右側為F(n-2)break;} } }while(!S.IsEmpty()); returnsum;}115遞歸與回溯n皇后問題 在n行n列的國際象棋棋盤上，若兩個皇后位于同一行、同一列、同一對角線上，則稱為它們為互相攻擊。n皇后問題是指找到這n個皇后的互不攻擊的布局。1161#主對角線3#主對角線5#主對角線0#次對角線2#次對角線4#次對角線6#次對角線1#次對角線3#次對角線5#次對角線0#主對角線2#主對角線4#主對角線6#主對角線01230123k=i+j