第三章+栈和队列

1、栈 队列 递归第三章栈和队列第三章栈和队列1栈 ( Stack )定义:是限定仅在表尾进行插入或删除操作的线性表。允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点：后进先出 (LIFO)a1topbottoman.进栈进栈 出栈出栈2栈的主要操作ADT Stack /对象由数据类型为StackData的元素构成 int Push (stack *S, StackData x); /进栈 int Pop (stack *S, StackData &x); /出栈 int GetTop (stack *S, StackData &x); /取栈顶 void

2、 InitStack (stack *S); /置空栈 int StackEmpty (stack *S); /判栈空否 int StackFull (stack *S); /判栈满否3栈的表示和实现顺序栈：栈的顺序存储结构，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，指针top指向栈顶元素在顺序栈中的下一个位置，base为栈底指针，指向栈底的位置。base空栈a 进栈b 进栈aabtopbasetopbasetop4toptopabcdee 进栈abcdef 进栈溢出abde 出出栈cbasebasebasetop5顺序栈的类型表示:#define STACK_INIT_SIZ

3、E 100；#define STACKINCREMENT 10；typedef char StackData;typedef struct /顺序栈定义 StackData *base; /栈底指针 StackData *top; /栈顶指针int stacksize；/当前已分配的全部存储空间 SeqStack；6判栈空int StackEmpty (SeqStack *S) if( S-top = S-base ) return 1 /判栈空,空则返回1 else return 0; /否则返回0判栈满int StackFull (SeqStack *S) if( S-top- S-bas

4、e = S- StackSize ) return 1 /判栈满,满则返回1else return 0; /否则返回0顺序栈的基本运算顺序栈的基本运算:7初始化初始化void InitStack ( SeqStack *S) /置空栈置空栈S-base-base =( StackData *)malloc(STACK_INIT_SIZE * sizeof(StackData);if (!S-base) exit(OVERFLOW);S-top = S-base-base ; S-stacksize= S-stacksize= STACK_INIT_SIZE ;Return ok; 8入栈int

5、 Push (SeqStack *S, StackData x) /插入元素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）+;Return ok9取栈顶元素int GetTop (Se

6、qStack *S, StackData &x) /若栈空返回0, 否则栈顶元素读到x并返回1 if ( StackEmpty(S) ) return 0; x = *(S-top-1); return 1;10出栈int Pop (SeqStack *S, StackData &x) /若栈空返回0, 否则栈顶元素退出到x并返回1 if ( StackEmpty(S) ) return 0; -(S-top);x = *(S-top); return 1;11链式栈:栈的链接表示 链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头top12链式栈 (Lin

7、kStack)的定义typedef int StackData;typedef struct node StackData data; /结点 struct node *link; /链指针 StackNode;typedef struct StackNode *top; /栈顶指针 LinkStack;13链式栈操作实现初始化void InitStack ( LinkStack *S ) S-top = NULL;入栈int Push ( LinkStack *S, StackData x ) StackNode *p = ( StackNode * ) malloc ( sizeof (

8、StackNode ) ); p-data = x; p-link = S-top; S-top = p; return 1;14判栈空int StackEmpty (LinkStack *S) return S-top = NULL;出栈int Pop ( LinkStack *S, StackData &x ) if ( StackEmpty (S) ) return 0; StackNode * p = S-top; S-top = p-link; x = p-data; free (p); return 1; 15取栈顶int GetTop ( LinkStack *S, St

9、ackData &x ) if ( StackEmpty (S) ) return 0; x = S-top-data; return 1;置栈空int MakeEmpty ( LinkStack *S) While(S-top!=NULL)StackNode * p = S-top; S-top = S-top -link;free(p);16程序中定义多个栈程序中定义多个栈（1）定义共享栈数据结构）定义共享栈数据结构#define MAX 100 int stackMAX,top1=0,top2=MAX-1;栈1top1top2栈217(2)共享进栈算法共享进栈算法 void pu

10、sh1(int x) if (top1top2) printf(“overflow”); else stacktop1=x;top1+; void push2(int x) if(top1top2) printf(“overflow”); else stacktop2=x;top2-;18(3)共享出栈算法共享出栈算法 int pop1()if top1=0)printf(“underflow”);return(NULL);top1-;return(stacktop1);int pop2()if(top2=MAX-1)printf(“underflow”);return(NULL): top2

11、+;return(stacktop2);19栈的应用举例栈的应用举例数制转换数制转换行编辑程序行编辑程序迷宫求解迷宫求解表达式求值表达式求值20采用对十进制数除8取余的方法，可得到八进制数的倒序。 N = (N div d)d + N mod d 例如：（1348)10 = (2504)8 ，其运算过程如下：N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2计算顺序计算顺序输出顺序输出顺序21数制转换十进制数转换为八进制数。void conversion () InitStack(S); scanf (%d,N); while (N) Push(

12、S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion22行编辑程序行编辑程序在用户输入一行的过程中，允许在用户输入一行的过程中，允许 用户输入用户输入出差错，并在发现有误时可以及时更正。出差错，并在发现有误时可以及时更正。设立一个输入缓冲区，用以接受用户输入设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区的一行字符，然后逐行存入用户数据区; 并假设并假设“#”为退格符，为退格符，“”为退行符。为退行符。假设从终端接受两行字符：假设从终端接受两行字符： whli#

13、ilr#e（s#*s) outchaputchar(*s=#+);实际有效行为：实际有效行为： while (*s) putchar(*s+);23Void LineEdit()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 = ge

14、tchar(); / 从终端接收下一个字符从终端接收下一个字符 /while24将从栈底到栈顶的字符传送至调用过程的将从栈底到栈顶的字符传送至调用过程的数据区；数据区；ClearStack(S); / 重置重置S为空栈为空栈if (ch != EOF) ch = getchar(); /whileDestroyStack(s);25v迷宫求解迷宫求解通常用的是通常用的是“穷举求解穷举求解”的方法的方法# #$# #$# $# # # # # #26v迷宫路径算法的基本思想若当前位置“可通”，则纳入路径，继续前进;若当前位置“不可通”，则后退，换方向继续探索;若四周“均无通路”，则将当前位置从路

15、径中删除出去。27设定当前位置的初值为入口位置；设定当前位置的初值为入口位置； do 若当前位置可通，若当前位置可通， 则将当前位置插入栈顶；则将当前位置插入栈顶； 若该位置是出口位置，则算法结束；若该位置是出口位置，则算法结束； 否则切换当前位置的东邻方块为新的否则切换当前位置的东邻方块为新的 当前位置；当前位置； . 28否则否则 若栈不空且栈顶位置尚有其他方向未被探索，若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为则设定新的当前位置为: 沿顺时针方向旋转沿顺时针方向旋转 找到的栈顶位置的下一相邻块；找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，若栈不空但栈顶

16、位置的四周均不可通，则则删去栈顶位置；删去栈顶位置；/ 从路径中删去该通道块从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置，若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空直至找到一个可通的相邻块或出栈至栈空;while (栈不空）；栈不空）；29typedef struct int ord;/序号PosType seat;/坐标int di;/方向SElemType;/栈元素Status MazePath (MazeType maze, PosType start, PosType end) InitStack(S); curpos=start;/当前位置cu

17、rstep=1;30do if (Pass(curpos) /可通过且未走过FootPrint(curpos);/记已通过标记e=(curstep, curpos, 1);Push (S, e);if (curpos = end) return (TRUE);curpos = NextPos ( curpos, 1);curstep+;/if31else if (!StackEmpty(S) Pop(S, e);while (e.di=4 & !StackEmpty(S) MarkPrint(e.seat); Pop(S,e);/记不能通过标记/whileif(e.di4) e.di+

18、; Push(S, e);curpos = NextPos(e.seat, e.di);/if/if/elsewhile (!StackEmpty(S);return (FALSE);/MazePath32限于二元运算符的表达式定义限于二元运算符的表达式定义: 表达式表达式 := (操作数操作数) + (运算符运算符) + (操作数操作数) 操作数操作数 := 简单变量简单变量 | 表达式表达式 简单变量简单变量 : = 标识符标识符 | 无符号整数无符号整数Exp = S1 + OP + S2前缀表示法前缀表示法OP + S1 + S2中缀表示法中缀表示法 S1 + OP + S2后缀表示法

19、后缀表示法 S1 + S2 + OP表达式求值表达式求值33例如例如: Exp = a b + (c d / e) f前缀式前缀式: + a b c / d e f中缀式中缀式: a b + c d / e f后缀式后缀式: a b c d e / f + 表达式标识方法表达式标识方法b-ca/*def*+34后缀表达式求值先找运算符，再找操作数例如：例如： a b c d e / f +a bd/ec-d/e(c-d/e) f35从原表达式求得后缀式方法从原表达式求得后缀式方法设立暂存设立暂存运算符运算符的的栈栈;设表达式的结束符为设表达式的结束符为“#”, 予设予设运算符栈运算符栈的的栈底

20、为栈底为“#”若若当前字符当前字符是操作数是操作数，则，则直接发送给后缀直接发送给后缀式式;(后缀与前缀式操作数的顺序是相同的后缀与前缀式操作数的顺序是相同的)若若当前当前运算符的运算符的优先数高优先数高于栈顶运算符，于栈顶运算符，则则进栈进栈;否则，退出栈顶运算符发送给后缀式否则，退出栈顶运算符发送给后缀式;“(” 对它之前后的运算符对它之前后的运算符起隔离作用起隔离作用，“)”为自左括弧开始的表达式的结束符。为自左括弧开始的表达式的结束符。36表达式求值的算法采用“算符优先法”，在表达式中,优先级的顺序是:（1）括号的优先级最高,对括号内的各种运算符有:先乘除、再加碱，同级运算从左至右。（

21、2）先括号内，后括号外，多层括号，由内向外。任何表达式都是由操作数、运算符和界符组成。操作数可以是常量、变量、常数运算符有算术运算符、关系运算符、逻辑运算符界符包括左右括号算式结束符。运算符和界符统称为“算符”。37在算符集中，在每一个运算步，相邻的算符c1 和c2之间的关系是如下三种情况（c1出现在c2之前）：c1c2,c1的优先级大于c27*(5-3)38算符间优先级 / ( ) （） =c2c139为实现算符优先算法，在这里用了两个工作栈。一个存放算符OPTR，另一个存放数据OPND。算法思想是：（1）首先置数据栈为空栈，表达式起始符“”为算符栈的栈底元素（2）自左向右扫描表达式，读到操

22、作数进OPND栈，读到运算符，则和OPTR栈顶元素比较（栈顶元素为c1，读到的算符为c2);若c1c2,则将c1出栈，并在操作数栈取出两个元素a和b按c1做运算，运算结果进OPND.重复直到表达式求值完毕。40例如：表达式3*(7-2),求值过程如下表：步骤步骤OPTROPTR栈栈OPNDOPND栈栈输入字符输入字符主要操作主要操作13*(7-2)#PUSH(OPND,3)23*(7-2)#PUSH(OPTR,*)3 3(7-2)#PUSH(OPTR,()4 （37-2)#PUSH(OPND,7)5 （3 7-2)#PUSH(OPTR,-)6 （ - 3 72)#PUSH(OPND,2)7 （

23、3 7 2)#operate(7,-,2)8 （3 5)#POP(OPTR)消消去括号去括号9 15 #operate(3,*,5)41为使两个算符比较方便,给算符设置优先级,如下表,其中c1为栈内元素,c2为栈外元素算算符符栈内优先级栈内优先级栈外优先级栈外优先级* /43+ -21(05)50#-1-142算符比较算法算符比较算法char Precede(char c1,char c2)int c_temp1,c_temp2; switch(c1) case *: case /:c_temp1=4;break;case +: case -:c_temp1=2;break; case (:c

24、_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_temp1c_temp2) return(c_temp2) return();switch(c1) case *: case /:c_temp1=4;break;case +: case

25、-:c_temp1=2;break; case (:c_temp1=0;break; case ):c_temp1=5;break; case #:c_temp1=-1;44int express()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 : op=Pop(OPTR);b=Pop(OPND);a=P

26、op(OPND);push(OPND,Operate(a,op,b);break;return(Getop(OPND);45OperandType EvaluateExpression() InitStack (OPTR); Push ( OPTR,#);InitStack (OPND); c=getchar();while (c!=#| GetTop(OPTR)!=#) if(!In(c,OP)Push(OPND,c);c=getchar();elseswitch(Precede(GetTop(OPTR),c)case :/退栈并计算Pop(OPTR,theta);Pop(OPND,b);

27、Pop(OPND,a);Push(OPND, Operate(a,theta,b);break;/switch/whilereturn GetTop(OPND);/EvaluateExpression47队列定义:只允许在表的一端进行插入，而在另一端删除元素的线性表。在队列中，允许插入的一端叫队尾（rear），允许删除的一端称为对头(front)。特点：先进先出 (FIFO) a1 ，a2， a3，an出队列出队列入队列入队列队队头头队队尾尾48链队列：队列的链式表示链队列中，有两个分别指示队头和队尾的指针。链式队列在进队时无队满问题，但有队空问题。data nextfrontreardata

28、 nextfrontrear49frontrearx元素元素x入队入队frontrearxy元素元素y入队入队frontrearxy元素元素x出队出队frontrear空队列空队列frontrearNULL空队列空队列50链式队列的定义typedef int QueueData;typedef struct node QueueData data; /队列结点数据 struct node *link; /结点链指针 QueueNode;typedef struct QueueNode *rear, *front; LinkQueue;51链队列的主要操作初始化void InitQueue (

29、LinkQueue *Q ) Q-rear = Q-front = NULL;队空int QueueEmpty ( LinkQueue *Q ) return Q-front = NULL;取队头元素int GetFront ( LinkQueue *Q, QueueData &x ) if ( QueueEmpty (Q) ) return 0; x = Q-front-data; return 1;52入队int EnQueue ( LinkQueue *Q, QueueData x ) QueueNode *p = ( QueueNode * ) malloc ( sizeof

30、( QueueNode ) ); p-data = x; p-link = NULL; if ( Q-front = NULL ) /空,创建第一个结点 Q-front = Q-rear = p; else Q-rear-link = p; /入队 Q-rear =p; return 1;53出队int DeQueue ( LinkQueue *Q, QueueData &x) /删去队头结点，并返回队头元素的值 if ( QueueEmpty (Q) ) return 0;/判队空 QueueNode *p = Q-front; x = p-data;/保存队头的值 Q-front=

31、 Q-front-link; /新队头free (p); return 1;54循环队列 (Circular Queue)顺序队列队列的顺序存储表示。用一组地址连续的存储单元依次存放从队列头到队列尾的元素，指针front和rear分别指示队头元素和队尾元素的位置。插入新的队尾元素，尾指针增1，rear = rear + 1，删除队头元素，头指针增1， front = front + 1，因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。 队满时再进队将溢出 解决办法：将顺序队列臆造为一个环状的空间，形成循环(环形)队列55队列的进队和出队frontrear空

32、队列空队列frontrearA,B,C, D进队进队A B C DfrontrearA,B出队出队C DfrontrearE,F,G进队进队C D E F GC D E F GfrontrearH进队进队,溢出溢出56循环队列 (Circular Queue)队头、队尾指针加1，可用取模(余数)运算实现。队头指针进1: front = (front+1) %maxsize;队尾指针进1: rear = (rear+1) % maxsize;队列初始化：front = rear = 0;队空条件：front = rear;队满条件：(rear+1) % maxsize = front;01234

33、567循环队列循环队列frontrearMaxsizerontBCDrear一般情况一般情况AC01234567队满队满(错误错误)frontrearDEFGABCH01234567rear空队列空队列frontC01234567队满队满(正确正确)frontrearDEFGABC58#define MAXSIZE 100Typedef structQueueData *data;int front;int rear; SeqQueue循环队列的类型定义59循环队列操作的实现初始化队列void InitQueue ( SeqQueue *Q ) /构造空队列Q-dat

34、a=(QueueData *)malloc(MAXSIZE *sizeof(QueueData);If(! Q-data)exit(OVERFLOW); Q-rear = Q-front = 0;Return ok60判队空int QueueEmpty ( SeqQueue *Q ) return Q-rear = Q-front;判队满int QueueFull ( SeqQueue *Q ) return (Q-rear+1) % QueueSize = Q-front;入队int EnQueue ( SeqQueue *Q, QueueData x ) if ( QueueFull (Q

35、) ) return 0; Q-dataQ-rear = x; Q-rear = ( Q-rear+1) % MAXSIZE;return 1;61出队int DeQueue ( SeqQueue *Q, QueueData &x ) if ( QueueEmpty (Q) ) return 0; x = Q-dataQ-front; Q-front = ( Q-front+1) % MAXSIZE;return 1;取队头int GetFront ( SeqQueue *Q, QueueData &x ) if ( QueueEmpty (Q) ) return 0; x =

36、 Q-dataQ-front; return 1;求队列长度int QueueLength (SeqQueue *Q) return (Q-rear Q-front + MAXSIZE) % MAXSIZE;62队列应用举例队列应用举例 打印二项展开式打印二项展开式 (a + b)i 的系数的系数杨辉三角形杨辉三角形 (Pascals triangle) 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行元素的关系行元素的关系目的是从前一行的数

37、据可以计算下一行的数据目的是从前一行的数据可以计算下一行的数据64从第从第 i 行数据计算并存放第行数据计算并存放第 i+1 行数据行数据65void YANGHUI ( int n ) Queue q; /队列初始化队列初始化 q.MakeEmpty ( ); q.EnQueue (1); q.EnQueue (1);/预放入第一行的两个系数预放入第一行的两个系数 int s = 0;for ( int i=1; i=n; i+ ) /逐行处理逐行处理 cout endl;/换行换行 q.EnQueue (0); for ( int j=1; j=i+2; j+ ) /处理第处理第i行的行的

38、i+2个系数个系数 int t = q.DeQueue ( );/读取系数读取系数 q.EnQueue ( s+t );/计算下一行系数，并进队列计算下一行系数，并进队列 s = t; if ( j != i+2 ) cout s ;/打印一个系数，第打印一个系数，第 i+2个个为为0 66 任任务务编编号号 1 2 3 4 5 优优先先权权 20 0 40 30 10 执执行行顺顺序序 3 1 5 4 2优先级队列 (Priority Queue)优先级队列 是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素例如下表：任务的优先权及执行顺序的关系数字越小，优先权越高，

39、设不存在同优数字越小，优先权越高，设不存在同优先级元素先级元素67#include #include $include const int maxPQSize = 50; /缺省元素个数缺省元素个数template class PQueue public: PQueue ( ); PQueue ( ) delete pqelements; void PQInsert ( const Type & item ); Type PQRemove ( ); 优先队列的类定义优先队列的类定义68 void makeEmpty ( ) count = -1; int IsEmpty ( ) con

40、st return count = -1; int IsFull ( ) const return count = maxPQSize; int Length ( ) const return count; / /优先级队列元优先级队列元素个数素个数private: Type *pqelements;/存放数组（优先级队列数组）存放数组（优先级队列数组） int count; /队列元素计数队列元素计数 69template PQueue:PQueue ( ) : count (- -1) pqelements = new TypemaxPQSize; assert ( pqelements

41、!= 0 ); /分配断言分配断言/创建优先级队列创建优先级队列template void PQueue :PQInsert ( const Type & item ) assert ( !IsFull ( ) ); /判队满断言判队满断言 count +； pqelementscount = item;/插入元素到队尾插入元素到队尾优先级队列部分成员函数的实现优先级队列部分成员函数的实现70template Type PQueue:PQRemove ( ) assert ( !IsEmpty ( ) ); /判队空断言判队空断言 Type min = pqelements0; int

42、 minindex = 0; for ( int i=1; icount; i+ ) /寻找最小元素寻找最小元素 if ( pqelementsi min ) /存于存于min min = pqelementsi; minindex = i; pqelementsminindex = pqelementscount- -1; /用最后一个元素填补要取走的最小值元素用最后一个元素填补要取走的最小值元素 count- - ;/优先级队列中元素个数减一优先级队列中元素个数减一 return min;/从队中删除最小值（优先级最高）元素从队中删除最小值（优先级最高）元素71离散事件模拟离散事件模拟日常

43、生活中排队活动的模拟程序需要用到队列和日常生活中排队活动的模拟程序需要用到队列和线性表的数据结构，是队列的典型应用。线性表的数据结构，是队列的典型应用。设银行有四个窗口，从开门起每个窗口一个时刻设银行有四个窗口，从开门起每个窗口一个时刻只能接待一个客户，人多时客户需排队。当客只能接待一个客户，人多时客户需排队。当客户进入银行时，如有窗口空闲则直接办理业务，户进入银行时，如有窗口空闲则直接办理业务，否则会排在人数最少的队伍后面。先要求编程否则会排在人数最少的队伍后面。先要求编程序模拟银行的业务活动并计算一天中客户在银序模拟银行的业务活动并计算一天中客户在银行的平均逗留时间。行的平均逗留时间。72

44、思路：思路： 为求平均时间要知道每个客户到达和离为求平均时间要知道每个客户到达和离开银行的两个时刻，所有客户逗留时间开银行的两个时刻，所有客户逗留时间总和除以客户数便是平均时间。总和除以客户数便是平均时间。1. 客户到达和离开银行两个时刻发生的事客户到达和离开银行两个时刻发生的事情成为情成为“事件事件”，整个程序按事件发生，整个程序按事件发生的先后顺序进行处理，即事件驱动模拟。的先后顺序进行处理，即事件驱动模拟。73银行客户的离散事件驱动模拟程序：银行客户的离散事件驱动模拟程序：void Bank_Simulation(int CloseTime) /银行业务模拟，统计一天内客户在银行逗留的平

45、均时间。银行业务模拟，统计一天内客户在银行逗留的平均时间。OpenForDay; /初始化初始化while(MoreEvent) do EventDrived( OccurTime, EventType); /事件驱动事件驱动switch (EventType) case A:CustomerArrived; break; /处理客户到达事处理客户到达事件件case D:CustomerDeparture; break; /处理客户离开处理客户离开事件事件default: Invalid; /switch /while CloseForDay; /计算平均逗留时间计算平均逗留时间 /Bank_

46、Simulation74具体实现：具体实现：1.算法中处理的主要对象为算法中处理的主要对象为“事件事件”，事件的主要信息是，事件的主要信息是事件类型和发生时刻。事件有两类：客户到达事件，事件类型和发生时刻。事件有两类：客户到达事件，其发生时刻随客户到来自然形成；客户离开事件，其其发生时刻随客户到来自然形成；客户离开事件，其发生时刻由客户事物所需时间和等待时间决定。由于发生时刻由客户事物所需时间和等待时间决定。由于事件驱动是按事件发生时刻的先后顺序进行，则事件驱动是按事件发生时刻的先后顺序进行，则事件事件表表是有序表，其主要操作是插入和删除事件。是有序表，其主要操作是插入和删除事件。类型定义如下

47、：类型定义如下：typedef struct int OccurTime; /事件发生时刻事件发生时刻int NType; /事件类型，事件类型，0表示到达事件，表示到达事件，1至至4表示四表示四个窗口的离开事件个窗口的离开事件Event, ElemType; /事件类型，有序链表事件类型，有序链表LinkList的数据的数据元素类型元素类型typedef LinkList EventList /事件链表类型，定义为有序事件链表类型，定义为有序链表链表752.模拟程序的另一种数据结构是表示客户模拟程序的另一种数据结构是表示客户排队的队列，银行的四个窗口对应四个排队的队列，银行的四个窗口对应四个

48、队列，队列中客户的信息是其到达的时队列，队列中客户的信息是其到达的时刻和办理事物所需时间。刻和办理事物所需时间。typedef struct int ArrivalTime; /到达时刻到达时刻int Duration; /办理事物所需时间办理事物所需时间QElemType; /队列的数据元素类型队列的数据元素类型763.每个队列的队头是正在办理事物的客户，每个队列的队头是正在办理事物的客户，他办完事物离开队列的时刻就是即将发他办完事物离开队列的时刻就是即将发生的客户离开事件的时刻，即对每个队生的客户离开事件的时刻，即对每个队头客户都存在一个将要驱动的客户离开头客户都存在一个将要驱动的客户离开

49、事件。因此在任何时刻即将发生的事件事件。因此在任何时刻即将发生的事件只有五种可能只有五种可能：（：（1）新客户到达；（）新客户到达；（2）1号窗口客户离开；（号窗口客户离开；（3）2号窗口客户离号窗口客户离开；（开；（4）3号窗口客户离开；（号窗口客户离开；（5）4号号窗口客户离开。窗口客户离开。由以上分析可见，在这个模拟程序中只需由以上分析可见，在这个模拟程序中只需要两种数据类型：有序链表和队列。要两种数据类型：有序链表和队列。77主要操作的实现：主要操作的实现：设第一个客户进门的时刻为设第一个客户进门的时刻为0，即是模拟程序处理的第一，即是模拟程序处理的第一个事件，之后每个客户到达的时刻在

50、前一个客户到达个事件，之后每个客户到达的时刻在前一个客户到达时设定。因此在客户到达事件发生时须先产生两个随时设定。因此在客户到达事件发生时须先产生两个随机数：其一为此时刻到达的客户办理事务所需时间机数：其一为此时刻到达的客户办理事务所需时间durtime;其二为下一客户将到达的时间间隔其二为下一客户将到达的时间间隔intertime,假设当前事件发生的时刻为假设当前事件发生的时刻为occurtime，则下一个客户，则下一个客户到达事件发生的时刻为到达事件发生的时刻为occurtime+intertime。由此应。由此应产生一个新的客户到达事件插入事件表；刚到达的客产生一个新的客户到达事件插入事

51、件表；刚到达的客户则应插入到当前所含元素最少的队列中；若该队列户则应插入到当前所含元素最少的队列中；若该队列在插入前为空，则还应产生一个客户离开事件插入事在插入前为空，则还应产生一个客户离开事件插入事件表。件表。客户离开事件先计算该客户在银行逗留的时间客户离开事件先计算该客户在银行逗留的时间,然后从队然后从队列中删除该客户后查看队列是否空列中删除该客户后查看队列是否空,若不空则设定一个若不空则设定一个新的队头客户离开事件新的队头客户离开事件.78银行事件驱动模拟程序算法银行事件驱动模拟程序算法:EventList ev;/事件表事件表Eventen;/事件事件LinkQueueq4;/4个客户

52、队列个客户队列QElemTypecustomer;/客户记录客户记录int TotalTime, CustomerNum;/累计客户逗留时间，客户数累计客户逗留时间，客户数int cmp (Event a, Event b); /依事件依事件a的发生时刻的发生时刻事件事件b的发的发生时刻分别返回生时刻分别返回-1或或0或或1void OpenForDay() /初始化操作初始化操作TotalTime=0; CustomerNum=0; /初始化累计时间和客户数为初始化累计时间和客户数为0InitList(ev); /初始化事件链表为空表初始化事件链表为空表en.OccurTime=0; en.

53、NType=0; /设定第一个客户到达事件设定第一个客户到达事件OrderInsert(ev, en, (* cmp)(); /插入事件表插入事件表for (i=0; i4; +i) InitQueue(qi); /置空队列置空队列 /OpenForDay79void CustomerArrived() /处理客户到达事件，处理客户到达事件，en.NType=0+CustomerNum;Random(durtime, intertime); /生成随机数生成随机数t=en.OccurTime+intertime; /下一客户到达时刻下一客户到达时刻if (t0i=en.NType; DelQu

54、eue(qi, customer); /删除第删除第i队列的排头客户队列的排头客户TotalTime+=en.OccurTime customer.ArrivalTime; /累计客户逗留时间累计客户逗留时间if (!QueueEmpty(qi) /设定第设定第i队列的一个离队列的一个离开事件并插入事件表开事件并插入事件表GetHead(qi, customer);OrderInsert (ev, (en.OccurTime+customer.Duration, i), (* cmp(); /if /CustomerDeparture81void Bank_Simulation(int Clo

55、seTime)OpenForDay; /初始化初始化while (!EmptyEventList(ev)DelFirst( GetHead(ev),p); en=GetCurElem(p);if (en.NType=0)CustomerArrived; /处理客户到达事件处理客户到达事件else CustomerDeparture; /处理客户离开事件处理客户离开事件/计算并输出平均逗留时间计算并输出平均逗留时间printf(“The Average Time is %f n”, TotalTime / CustomerNum); /Bank_Simulation82递 归定义定义若一个对象部

56、分地包含它自己若一个对象部分地包含它自己, 或用它或用它自己给自己定义自己给自己定义, 则称这个对象是递归的；则称这个对象是递归的； 若一个过程直接地或间接地调用自己若一个过程直接地或间接地调用自己, 则称这则称这个过程是递归的过程。个过程是递归的过程。三种递归情况三种递归情况定义是递归的定义是递归的 数据结构是递归的数据结构是递归的 问题的解法是递归的问题的解法是递归的83定义是递归的定义是递归的求解阶乘函数的递归算法求解阶乘函数的递归算法long Factorial ( long n ) if ( n = 0 ) return 1; else return n * Factorial (n

57、- -1);例例1.阶乘函数阶乘函数时时当当时时当当 1 ,)!1( 0 , 1!nnnnn84求解阶乘求解阶乘 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)的定义的定义递归算法递归算法 long Fib ( long n

58、 ) if ( n =0) return 1; if(n=1 & m=0) return 2; if(m=0 & n=2) return n+2; return ackerman(ackerman(n-1,m),m-1);88 A(nA(n，m)m)的自变量的自变量m m的每一个值都定义了一个单变量的每一个值都定义了一个单变量函数：函数： M=0M=0时，时，A(n,0)=n+2A(n,0)=n+2 M=1M=1时，时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和，和A(1,1)=2A(1,1)

59、=2故故A(n,1)=2A(n,1)=2* *n n M=2M=2时，时，A(n,2)=A(A(n-1,2),1)=2A(n-1,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)=2A(1,2)=A(A(0,2),1)=A(1,1)=2，故，故A(n,2)= 2n A(n,2)= 2n 。( (小于小于n!)n!) M=3M=3时，类似的可以推出时，类似的可以推出 ( (大于大于n n！) ) M=4M=4时，时，A(n,4)A(n,4)的增长速度非常快，以至于没有适当的增长速度非常快，以至于没有适当的数学式子来表示这一

60、函数。的数学式子来表示这一函数。( (远远大于远远大于n n！) )n222289 定义单变量的定义单变量的AckermanAckerman函数函数A(n)A(n)为，为，A(n)=A(nA(n)=A(n，n)n)。 定义其拟逆函数定义其拟逆函数B(n)B(n)为：为：B(n)=minkB(n)=minkA(k)nA(k)n。即。即B(n)B(n)是使是使nA(k)nA(k)成立的最小的成立的最小的k k值。值。 但在理论上但在理论上B(n)B(n)没有上界，随着没有上界，随着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。由此可以看