(精品)数据结构清华（严蔚敏版）chap03(1).ppt

《(精品)数据结构清华（严蔚敏版）chap03(1).ppt》由会员分享，可在线阅读，更多相关《(精品)数据结构清华（严蔚敏版）chap03(1).ppt（115页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章栈和队列栈和队列第第3 3章章 栈和队列栈和队列出出进进排队排队签名签名汉诺塔汉诺塔进进出出通常称，栈和队列是限定插入和删除插入和删除只能只能在表的“端点端点”进行的线性表。线性表线性表 栈栈 队列队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1in+1Delete(L,i)Delete(S,n)Delete(Q,1)1in栈和队列是两种常用的数据类型栈和队列是两种常用的数据类型3.1 栈的类型定义栈的类型定义3.2 栈的应用举例栈的应用举例3.3 栈类型的实现栈类型的实现3.4 队列的类型定义队列的类型定义3.5 队列类型的实现队列类型

2、的实现3.1 栈的类型定义栈的类型定义3.1 栈的类型定义栈的类型定义 ADT Stack数据对象数据对象：Dai|aiElemSet,i=1,2,.,n,n0数据关系数据关系：R1|ai-1,aiD,i=2,.,n约定an端为栈顶，a1端为栈底。基本操作：基本操作：ADT StackInitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit()InitStack(&S)操作结果：构造一个空栈S。Destroy

3、Stack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则FALE。StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。a1a2an ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。a1a2ane Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用

4、e返回其值。a1a2anan-1 3.2 栈的应用举例栈的应用举例例一、例一、数制转换数制转换例二、例二、括号匹配的检验括号匹配的检验例三、例三、行编辑程序问题行编辑程序问题例四、例四、迷宫求解迷宫求解例五、例五、表达式求值表达式求值例六、例六、实现递归实现递归例一、例一、数制转换数制转换算法基于原理：N=(N div d)d+N mod d例如：例如：（1348)10=(2504)8，其运算过程如下：voidconversion()InitStack(S);scanf(%d,N);while(N)Push(S,N%8);N=N/8;while(!StackEmpty(S)Pop(S,e);p

5、rintf(%d,e);/conversion 例二、例二、括号匹配的检验括号匹配的检验假设在表达式中（）或（）等为正确的格式，（）或（）或（）)均为不正确的格式。则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。分析可能出现的不匹配不匹配的情况:到来的右括弧并非是所“期待”的；例如：考虑下列括号序列：()12345678到来的是“不速之客”；直到结束，也没有到来所“期待”的括弧。算法的设计思想：算法的设计思想：1）凡出现左括弧左括弧，则进栈进栈；2）凡出现右括弧右括弧，首先检查栈是否空 若栈空栈空，则表明该“右括弧右括弧”多余多余，否则和栈顶元素和栈顶元素比较，若相匹配相匹配，则

6、“左括弧出栈左括弧出栈”，否则表明不匹配不匹配。3）表达式表达式检验结束时结束时，若栈空栈空，则表明表达式中匹配正确匹配正确，否则表明“左括弧左括弧”有余有余。Statusmatching(string&exp)intstate=1;while(i0Factorial(4);对于一个较为复杂的问题，如果能够分解成几个相对简单的且解法相同或类似的子问题来求解分治法分治法例例:递归的执行情况分析递归的执行情况分析 void print(int w)int i;if(w!=0)print(w-1);for(i=1;i1时，先把上面n-1个圆盘从A移到B,然后将n号盘从A移到C,再将n-1个盘从B移到

7、C。即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题执行情况：递归工作栈保存内容：形参n,x,y,z和返回地址返回地址用行编号表示nxyz返回地址void hanoi(intn,charx,chary,charz)/将塔座x上按直径由小到大且至上而下编号为1至n/的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1 if(n=1)2move(x,1,z);/将编号为的圆盘从x移到z3 else 4hanoi(n-1,x,z,y);/将x上编号为至n-1的/圆盘移到y,z作辅助塔5move(x,n,z);/将编号为n的圆盘从x

8、移到z6hanoi(n-1,y,x,z);/将y上编号为至n-1的/圆盘移到z,x作辅助塔7 8 TowerofHanoi83abc返址nxyz52acb51abc71cabvoid hanoi(intn,charx,chary,charz)1 if(n=1)2move(x,1,z);3 else 4hanoi(n-1,x,z,y);5move(x,n,z);6hanoi(n-1,y,x,z);7 8 3.3栈类型的实现栈类型的实现顺序栈顺序栈链栈链栈/-栈的顺序存储表示栈的顺序存储表示-#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;typ

9、edef struct SElemType*base;SElemType*top;intstacksize;SqStack;类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。StatusInitStack(SqStack&S)/构造一个空栈SS.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType);if(!S.base)exit(OVERFLOW);/存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;StatusPush(SqStack&S,SElemTypee)i

10、f(S.top-S.base=S.stacksize)/栈满，追加存储空间S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType);if(!S.base)exit(OVERFLOW);/存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;StatusPop(SqStack&S,SElemType&e)/若栈不空，则删除S的栈顶元素，/用e返回其值，并返回OK；/否则返回ERRORif(S.t

11、op=S.base)returnERROR;e=*-S.top;returnOK;栈顶指针链栈链栈a1an注意注意:链栈中链栈中指针的方向指针的方向an-1 ADTQueue数据对象：数据对象：Dai|aiElemSet,i=1,2,.,n,n0数据关系：数据关系：R1|ai-1,aiD,i=2,.,n约定其中a1端为队列头队列头，an端为队列尾队列尾基本操作：基本操作：3.4 队列的类型定义队列的类型定义ADT Queue队列的基本操作：队列的基本操作：InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)C

12、learQueue(&Q)DeQueue(&Q,&e)EnQueue(&Q,e)QueueTravers(Q,visit()InitQueue(&Q)操作结果：操作结果：构造一个空队列Q。DestroyQueue(&Q)初始条件：初始条件：队列Q已存在。操作结果：操作结果：队列Q被销毁，不再存在。QueueEmpty(Q)初始条件：初始条件：队列Q已存在。操作结果：操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。QueueLength(Q)初始条件：初始条件：队列Q已存在。操作结果：操作结果：返回Q的元素个数，即队列的长度。GetHead(Q,&e)初始条件：初始条件：Q为非空队列

13、。操作结果：操作结果：用e返回Q的队头元素。a1a2an ClearQueue(&Q)初始条件：初始条件：队列Q已存在。操作结果：操作结果：将Q清为空队列。EnQueue(&Q,e)初始条件：初始条件：队列Q已存在。操作结果：操作结果：插入元素e为Q的新的队尾元素。a1a2ane DeQueue(&Q,&e)初始条件：初始条件：Q为非空队列。操作结果：操作结果：删除Q的队头元素，并用e返回其值。a1a2an 3.5 队列类型的实现队列类型的实现链队列链队列链式映象循环队列循环队列顺序映象typedef struct QNode/结点类型结点类型QElemTypedata;struct QNod

14、e*next;QNode,*QueuePtr;链队列链队列链式映象typedef struct /链队列类型链队列类型QueuePtrfront;/队头指针队头指针QueuePtrrear;/队尾指针队尾指针LinkQueue;a1anQ.frontQ.rearQ.frontQ.rear空队列空队列StatusInitQueue(LinkQueue&Q)/构造一个空队列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);/存储分配失败Q.front-next=NULL;returnOK;Status

15、EnQueue(LinkQueue&Q,QElemTypee)/插入元素e为Q的新的队尾元素p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(OVERFLOW);/存储分配失败p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;returnOK;StatusDeQueue(LinkQueue&Q,QElemType&e)/若队列不空，则删除Q的队头元素，/用e返回其值，并返回OK；否则返回ERRORif(Q.front=Q.rear)returnERROR;p=Q.front-next;e=p-data;Q.front-

16、next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);returnOK;#defineMAXQSIZE100/最大队列长度typedef struct QElemType *base;/动态分配存储空间intfront;/头指针，若队列不空，/指向队列头元素 intrear;/尾指针，若队列不空，指向/队列尾元素的下一个位置SqQueue;循环队列循环队列顺序映象StatusInitQueue(SqQueue&Q)/构造一个空队列QQ.base=(ElemType*)malloc (MAXQSIZE*sizeof(ElemType);if(!Q.base

17、)exit(OVERFLOW);/存储分配失败Q.front=Q.rear=0;returnOK;StatusEnQueue(SqQueue&Q,ElemTypee)/插入元素e为Q的新的队尾元素if(Q.rear+1)%MAXQSIZE=Q.front)returnERROR;/队列满Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;StatusDeQueue(SqQueue&Q,ElemType&e)/若队列不空，则删除Q的队头元素，/用e返回其值，并返回OK;否则返回ERROR if(Q.front=Q.rear)returnERROR

18、;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;returnOK;第1行11第2行121第3行1331第4行14641二项式系数值（杨辉三角）设第i-1行的值：(a0=0)a1.ai(ai+1=0)则第i行的值：bj=aj-1+aj,j=1,2,i+100利用“循环队列”计算二项式系数的过程0123450110s+e=Q.frontQ.rear011输出:Q.front11Q.rear11Q.front22Q.rear11Q.front011Q.rear0Q.rear0Q.front1111Q.rear1Q.front23223Q.rearQ.fro

19、nt1133Q.rear1Q.front011Q.rear0Q.reardo DeQueue(Q,s);GetHead(Q,e);if(e!=0)cout0)行QueueQ;InitQueue(Q,n+2);EnQueue(Q,0);/添加行界值EnQueue(Q,1);EnQueue_Sq(Q,1);k=1;while(kn)EnQueue(Q,0);/行界值“0”入队列do/输出第k行，计算第k+1行 while(e!=0);k+;/while/yanghui DeQueue(Q,e);/行界值“0”出队列while(!QueueEmpty(Q)/单独处理第n行的值的输出DeQueue_S

20、q(Q,e);coute；/while 1.掌掌握握栈栈和和队队列列类类型型的的特特点点，并并能能在在相相应应的应用问题中正确选用它们。的应用问题中正确选用它们。2.熟练掌握栈类型的两种实现方法，特别应熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。注意栈满和栈空的条件以及它们的描述方法。3.熟练掌握循环队列和链队列的基本操作实熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。现算法，特别注意队满和队空的描述方法。4.理解递归算法执行过程中栈的状态变化过理解递归算法执行过程中栈的状态变化过程。程。本章学习要点本章学习要点练习练习队列通常采用两

21、种存储结构是()。A顺序存储结构和链表存储结构B散列方式和索引方式C链表存储结构和数组D线性存储结构和非线性存储结构若让元素1，2，3依次进栈，则出栈次序不可能出现（）种情况。A3，2，1B2，1，3C3，1，2D1，3，2栈和队列都是（）。A链式存储的线性结构B顺序存储的线性结构C限制存取位置的线性结构D限制存取位置的非线性结构对于给定的结点序列abcdef，规定进栈只能从序列的左端开始。通过栈的操作，能得到的序列为（）。AabcfedBcabfedCabcfdeDcbafde练习练习栈的插入与删除操作在（）进行。A栈顶B栈底C任意位置D指定位置设一个栈的输入序列为A、B、C、D，则借助一个

22、栈所能得到的输出序列不可能是（）。AABCDBDCBACACDBDDABC练习练习一个队列的入队序列是a、b、c、d，则队列的输出序列为_。栈结构通常采用的两种存储结构是_和_。中缀算术表达式5+6/(23-(6+15)*8所对应的后缀算术表达式为_。中缀表达式3+x*(2.4/5-6)所对应的后缀表达式为_。练习练习用单链表表示的链式队列的队头在链表的（）位置。A）链头B）链尾C）链中D）任意若用单链表来表示队列，则应该选用（）。A）带尾指针的非循环链表B）带尾指针的循环链表C）带头指针的非循环链表D）带头指针的循环链表练习练习铁路进行列车调度时,常把站台设计成栈式结构的站台，如下图所示。试

23、问：(1)设有编号为1,2,3,4,5,6的六辆列车,顺序开入栈式结构的站台,则可能的出栈序列有多少种?(2)若进站的六辆列车顺序如上所述,那么4第一个出站，5第二个出站，那么出栈序列有哪些？应用案例题应用案例题作业三：数个数作业三：数个数请问，从1到100中存在着多少个9？请编程实现解决如下问题：接受用户输入一个整数n（0n264）和正整数m（1m9），请输出从0到n的所有整数中存在着多少个m？例如从0到24356中，存在多少个4？Tips：用堆栈实现。机场模拟机场模拟计算机模拟（计算机模拟（simulation）：）：用软件模仿另一个系统的行为。用软件模仿另一个系统的行为。将研究对象表示为

24、数据结构，对象动作表示为对将研究对象表示为数据结构，对象动作表示为对数据的操作，控制动作的规则转换为算法。数据的操作，控制动作的规则转换为算法。通过更改数据的值或改变算法设置，可以观察到通过更改数据的值或改变算法设置，可以观察到计算机模拟的变化，从而使用户能够推导出关于计算机模拟的变化，从而使用户能够推导出关于实际系统行为的有用结论。实际系统行为的有用结论。在计算机处理一个对象的动作期间，其它对象和在计算机处理一个对象的动作期间，其它对象和动作需等待。动作需等待。队列在计算机模拟中具有重要应用。队列在计算机模拟中具有重要应用。简单机场模拟：简单机场模拟：只有一个跑道。只有一个跑道。在每个时间单

25、元，可起飞或降落一架飞机，但不在每个时间单元，可起飞或降落一架飞机，但不可同时起降。可同时起降。飞机准备降落或起飞的时间是随机的，在任一时飞机准备降落或起飞的时间是随机的，在任一时间单元，跑道可能处于空闲、降落或起飞状态，间单元，跑道可能处于空闲、降落或起飞状态，并且可能有一些飞机在等待降落或起飞。并且可能有一些飞机在等待降落或起飞。飞机在地上等待的代价比在空中等待的小，只有飞机在地上等待的代价比在空中等待的小，只有在没有飞机等待降落的情况下才允许飞机起飞。在没有飞机等待降落的情况下才允许飞机起飞。当出现队列满的情况时，则拒绝为新到达的飞机当出现队列满的情况时，则拒绝为新到达的飞机服务。服务。

26、需要两个队列需要两个队列landing和和takeoff。飞机可描述为：飞机可描述为：struct plane int id;/编号 int tm;/到达队列时间;飞机的动作为：飞机的动作为：enum action ARRIVE,DEPART;模拟运行模拟运行:时间单元时间单元:1 endtime，并产生关于机场行为的，并产生关于机场行为的重要统计信息，如处理的飞机数量，平均等待时重要统计信息，如处理的飞机数量，平均等待时间，被拒绝服务飞机的数量等。间，被拒绝服务飞机的数量等。采用基于泊松分布的随机整数决定在每个时间单采用基于泊松分布的随机整数决定在每个时间单元有多少架新飞机需要降落或起飞。元

27、有多少架新飞机需要降落或起飞。假设在假设在10个时间单元中到达的飞机数分别是：个时间单元中到达的飞机数分别是：2，0，0，1，4，1，0，0，0，1，那么每个时间单元，那么每个时间单元的平均到达数是的平均到达数是0.9。一个非负整数序列满足给定期望值一个非负整数序列满足给定期望值v v的泊松分布的泊松分布意味着，对于该序列的一段足够长的子序列，其意味着，对于该序列的一段足够长的子序列，其中整数的平均值接近中整数的平均值接近v v 在模拟中还需要建立新到达飞机的数据，处理被在模拟中还需要建立新到达飞机的数据，处理被拒绝服务的飞机，起飞、降落飞机，处理机场空拒绝服务的飞机，起飞、降落飞机，处理机场

28、空闲和总结模拟结果闲和总结模拟结果 下面是机场模拟类定义：下面是机场模拟类定义：class AirportSimulation/机场模拟。一个时间单元=起飞或降落的时间public:AirportSimulation();/构造函数 void RunSimulation();/模拟运行private:Queuelanding(6);/等待降落飞机队列，假设用环/型队列，实际长度为5 Queuetakeoff(6);/等待起飞飞机队列，同上 double expectarrive;/一个时间单元内期望到达降落飞机数 doubleexpectdepart;/一个时间单元内期望到达起飞飞机数 int

29、 curtime;/当前时间 int endtime;/模拟时间单元数 int idletime;/跑道空闲时间单元数 int landwait;/降落飞机的总等待时间 int nland;/降落的飞机数 int nplanes;/处理的飞机数 int nrefuse;/拒绝服务的飞机数 int ntakeoff;/起飞的飞机数 void Randomize();/设置随机数种子 int PoissionRandom(double&expectvalue);/根据泊松分布和给定期望值生成随机非负整数plane*NewPlane(plane&p,actionkind);/建立新飞机的数据项 vo

30、id Refuse(plane&p,actionkind);/拒绝服务 void Land(plane&p);/降落飞机 void Fly(plane&p);/起飞飞机 void Idle();/处理空闲时间单元 void Conclude();/总结模拟结果;构造函数初始化各变量，如下所示：构造函数初始化各变量，如下所示：AirportSimulation:AirportSimulation()/构造函数 Booleanok;cout endtime;idletime=landwait=nland=nplanes=0;nrefuse=ntakeoff=takoffwait=0;/初值 Ran

31、domize();/设置随机数种子 do cout expectarrive;cout expectdepart;if(expectarrive0.0|expectdepart0.0)cout“这些数不能为负！请重新输入。”1.0)cout“机场将饱和！请重新输入。”endl;ok=FALSE;else ok=TRUE;while(ok=FALSE);RunSimulation()是模拟运行的主控程序：是模拟运行的主控程序：void AirportSimulation:RunSimulation()int pri;/伪随机整数 planep;for(curtime=1;curtime=endt

32、ime;curtime+)cout“时间单元”curtime“：”;pri=PoissionRandom(expectarrive);for(int i=1;i=pri;i+)/处理新到达准备降落的飞机 p=*NewPlane(p,ARRIVE);if(landing.IsFull()Refuse(p,ARRIVE);else landing.Add(p);pri=PoissionRandom(expectdepart);for(int i=1;ilimit)n+;x*=rand()/(double)INT_MAX;return n;建立新飞机的数据项由函数建立新飞机的数据项由函数NewPla

33、ne实现：实现：plane*AirportSimulation:NewPlane(plane&p,actionkind)nplanes+;/飞机总数加1 p.id=nplanes;p.tm=curtime;switch(kind)case ARRIVE:cout“飞机”nplanes“准备降落。”endl;break;case DEPART:cout“飞机”nplanes“准备起飞。”endl;break;return&p;处理被拒绝的飞机由函数处理被拒绝的飞机由函数Refuse实现实现:void AirportSimulation:Refuse(plane&p,actionkind)swit

34、ch(kind)case ARRIVE:cout“引导飞机”p.id“到其它机场降落。”endl;break;case DEPART:cout“告诉飞机”p.id“等一会儿再试。”endl;break;nrefuse+;/被拒绝飞机总数加1 处理飞机降落由函数处理飞机降落由函数Land实现：实现：void AirportSimulation:Land(plane&p)int wait;wait=curtimep.tm;cout“飞机”p.id“降落，该机等待时间：”wait“。”endl;nland+;/降落飞机总数加1 landwait+=wait;/累加总降落等待时间 处理飞机起飞由函数处

35、理飞机起飞由函数Fly实现：实现：void AirportSimulation:Fly(plane&p)int wait=curtimep.tm;cout“飞机”p.id“起飞，该机等待时间：”wait“。”endl;ntakeoff+;/起飞飞机总数加1 takeoffwait+=wait;/累加总起飞等待时间 处理机场空闲由函数处理机场空闲由函数Idle实现：实现：void AirportSimulation:Idle()cout“跑道空闲。”endl;idletime+;/跑道空闲时间加1 总结模拟结果由函数总结模拟结果由函数Conclude实现：实现：void AirportSimul

36、ation:Conclude()cout“总模拟时间单元数：”endtimeendl;cout“总共处理的飞机数：”nplanesendl;cout“降落飞机总数：”nlandendl;cout“起飞飞机总数：”ntakeoffendl;cout“拒绝服务的飞机总数：”nrefuseendl;cout“队列中剩余的准备降落飞机数：”landing.Size()endl;/假设队列成员函数Size()返回队列中元素个数 cout“队列中剩余的准备起飞飞机数：”takeoff.Size()0)cout“跑道空闲时间百分比：”(double)idletime/endtime)*100.00)cout

37、“降落平均等待时间：”(double)landwait/nland0)cout“起飞平均等待时间：”(double)takeoffwait/ntakeoffendl;可通过下列程序模拟运行：可通过下列程序模拟运行：#include“common.h”#include“simdefs.h”/存放模拟类定义及相关函数实现void main()AirportSimulations;s.RunSimulation();模拟过程产生的数据如下：模拟过程产生的数据如下：请输入模拟时间单元数：请输入模拟时间单元数：30请输入一个时间单元内期望到达降落飞机数：请输入一个时间单元内期望到达降落飞机数：0.47请

38、输入一个时间单元内期望到达起飞飞机数：请输入一个时间单元内期望到达起飞飞机数：0.47时间单元时间单元1：飞机：飞机1准备降落。准备降落。飞机飞机1降落，该机等待时间：降落，该机等待时间：0。时间单元时间单元2：跑道空闲。：跑道空闲。时间单元时间单元3：飞机：飞机2准备降落。准备降落。飞机飞机3准备降落。准备降落。飞机飞机2降落，该机等待时间：降落，该机等待时间：0。时间单元时间单元4：飞机飞机3降落，该机等待时间：降落，该机等待时间：1。时间单元时间单元5：飞机：飞机4准备降落。准备降落。飞机飞机5准备降落。准备降落。飞机飞机6准备起飞。准备起飞。飞机飞机7准备起飞。准备起飞。飞机飞机4降落

39、，该机等待时间：降落，该机等待时间：0。时间单元时间单元6：飞机：飞机8准备起飞。准备起飞。飞机飞机5降落，该机等待时间：降落，该机等待时间：1。时间单元时间单元7：飞机：飞机9准备起飞。准备起飞。飞机飞机10准备起飞。准备起飞。飞机飞机6起飞，该机等待时间：起飞，该机等待时间：2。时间单元时间单元8：飞机飞机7起飞，该机等待时间：起飞，该机等待时间：3。时间单元时间单元9：飞机飞机8起飞，该机等待时间：起飞，该机等待时间：3。时间单元时间单元10：飞机：飞机11准备降落。准备降落。飞机飞机11降落，该机等待时间：降落，该机等待时间：0。时间单元时间单元11：飞机：飞机12准备起飞。准备起飞。

40、飞机飞机9起飞，该机等待时间：起飞，该机等待时间：4。时间单元时间单元12：飞机：飞机13准备降落。准备降落。飞机飞机14准备降落。准备降落。飞机飞机13降落，该机等待时间：降落，该机等待时间：0。时间单元时间单元13：飞机飞机14降落，该机等待时间：降落，该机等待时间：1。时间单元时间单元14：飞机飞机10起飞，该机等待时间：起飞，该机等待时间：7。时间单元时间单元15：飞机飞机15准备降落。准备降落。飞机飞机16准备起飞。准备起飞。飞机飞机17准备起飞。准备起飞。飞机飞机15降落，该机等待时间：降落，该机等待时间：0。时间单元时间单元16：飞机：飞机18准备降落。准备降落。飞机飞机19准备

41、降落。准备降落。飞机飞机20准备起飞。准备起飞。飞机飞机21准备起飞。准备起飞。飞机飞机18降落，该机等待时间：降落，该机等待时间：0。时间单元时间单元17：飞机飞机22准备降落。准备降落。飞机飞机19降落，该机等待时间：降落，该机等待时间：1。时间单元时间单元18：飞机飞机23准备起飞。准备起飞。告诉飞机告诉飞机23等一会儿再试。等一会儿再试。飞机飞机22降落，该机等待时间：降落，该机等待时间：1。时间单元时间单元19：飞机飞机24准备降落。准备降落。飞机飞机25准备降落。准备降落。飞机飞机26准备降落。准备降落。飞机飞机27准备起飞。准备起飞。告诉飞机告诉飞机27等一会儿再试。等一会儿再试

42、。飞机飞机24降落，该机等待时间：降落，该机等待时间：0。时间单元时间单元20：飞机飞机28准备降落。准备降落。飞机飞机29准备降落。准备降落。飞机飞机30准备降落。准备降落。飞机飞机31准备降落。准备降落。引导飞机引导飞机31到其它机场降落。到其它机场降落。飞机飞机25降落，该机等待时间：降落，该机等待时间：1。时间单元时间单元21：飞机：飞机32准备降落。准备降落。飞机飞机33准备起飞。准备起飞。告诉飞机告诉飞机33等一会儿再试。等一会儿再试。飞机飞机26降落，该机等待时间：降落，该机等待时间：2。时间单元时间单元22：飞机：飞机28降落，该机等待时间：降落，该机等待时间：2。时间单元时间

43、单元23：飞机：飞机29降落，该机等待时间：降落，该机等待时间：3。时间单元时间单元24：飞机：飞机34准备起飞。准备起飞。告诉飞机告诉飞机34等一会儿再试。等一会儿再试。飞机飞机30降落，该机等待时间：降落，该机等待时间：4。时间单元时间单元25：飞机：飞机35准备起飞。准备起飞。告诉飞机告诉飞机35等一会儿再试。等一会儿再试。飞机飞机36准备起飞。准备起飞。告诉飞机告诉飞机36等一会儿再试。等一会儿再试。飞机飞机32降落，该机等待时间：降落，该机等待时间：4。时间单元时间单元26：飞机：飞机37准备起飞。准备起飞。告诉飞机告诉飞机37等一会儿再试。等一会儿再试。飞机飞机12起飞，该机等待时

44、间：起飞，该机等待时间：15。时间单元时间单元27：飞机：飞机16起飞，该机等待时间：起飞，该机等待时间：12。时间单元时间单元28：飞机：飞机17起飞，该机等待时间：起飞，该机等待时间：13。时间单元时间单元29：飞机：飞机20起飞，该机等待时间：起飞，该机等待时间：13。时间单元时间单元30：飞机：飞机38准备起飞。准备起飞。飞机飞机21起飞，该机等待时间：起飞，该机等待时间：14。总模拟时间单元数：总模拟时间单元数：30总共处理的飞机数：总共处理的飞机数：38降落飞机总数：降落飞机总数：19起飞飞机总数：起飞飞机总数：10拒绝服务的飞机总数：拒绝服务的飞机总数：8队列中剩余的准备降落飞机数：队列中剩余的准备降落飞机数：0 队列中剩余的准备起飞飞机数：队列中剩余的准备起飞飞机数：1跑道空闲时间百分比：跑道空闲时间百分比：3.33降落平均等待时间：降落平均等待时间：1.11起飞平均等待时间：起飞平均等待时间：8.60