第三章+栈和队列

栈队列

递归第三章栈和队列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){//若栈空返回0,否则栈顶元素读到x并返回1

if(StackEmpty(S))return0; x=*(S->top-1); return1;}10出栈intPop(SeqStack*S,StackData&x){//若栈空返回0,否则栈顶元素退出到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判栈空intStackEmpty(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;}置栈空intMakeEmpty(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）首先置数据栈为空栈，表达式起始符“＃”为算符栈的栈底元素（2）自左向右扫描表达式，读到操作数进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。由此应产生一个新的客户到达事件插入事件表；刚到达的客户则应插入到当前所含元素最少的队列中；若该队列在插入前为空，则还应产生一个客户离开事件插入事件表。客户离开事件先计算该客户在银行逗留的时间,然后从队列中删除该客户后查看队列是否空,若不空则设定一个新的队头客户离开事件.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