在日常生活中,我们经常会遇到许多为了维护社会正常秩序而需要排队的情景。这样一类活动的模拟程序通常需要用到队列和线性表之类的数据结构,因此是队列的典型应用例子之一。这里将向读者介绍一个银行业务的模拟程序。
假设某银行有4个窗口对外接待客户,从早晨银行开门起不断有客户进入银行。由于每个窗口在某个时刻只能接待一个客户,因此在客户人数众多时需在每个窗口前顺次排队,对于刚进入银行的客户,如果某个窗口的业务员正空闲,则可上前办理业务;反之,若4个窗口均有客户,他便会排在人数最少的队伍后面。现在需要编制一个程序以模拟银行的这种业务活动,同时计算一天中客户在银行逗留的平均时间。
为了计算这个平均时间,我们自然需要掌握每个客户到达银行和离开银行这两个时刻,后者减去前者即为每个客户在银行的逗留时间。所有客户逗留时间的总和除以一天内进入银行的客户数便是所求的平均时间。客户到达银行和离开银行这两个时刻发生的事情称为“事件”,则整个模拟程序将按事件发生的先后顺序进行处理,这样一种模拟程序称做事件驱动模拟。下述算法正是上述银行客户的离散事件驱动模拟程序。
void Bank_Simulation(int CloseTime)
{ /*银行业务模拟,统计一天内客户在银行逗留的平均时间*/
OpenForDay( ); /*初始化*/
while(MoreEvent)
{
EventDrived(OccurTime,EventType);
switch(EventType)
{
case'A':CustomerArrived( );break; /*处理客户到达事件*/
case'D':CustomerDeparture( );break; /*处理客户离开事件*/
default:Invalid( );
}
} /*计算平均逗留时间*/
CloseForDay;
}
下面讨论模拟程序的实现,首先要讨论模拟程序中需要的数据结构及其操作。
上述算法处理的主要对象是“事件”,事件的主要信息是事件类型和事件发生的时刻。算法中处理的事件有两类:一类是客户到达事件;另一类是客户离开事件。前一类事件发生的时刻随客户到来而自然形成;后一类事件发生时刻则由客户事务所需时间和等待所耗时间而定。由于程序驱动是按事件发生时刻的先后顺序进行,因此事件表应是有序表,其主要操作是插入和删除事件。
模拟程序中需要的另一种数据结构是表示客户排队的队列,由于前面假设银行有4个窗口,因此程序中需要4个队列,队列中有关客户的主要信息是客户到达时刻和客户办理事务所需的时间。每个队列中的队头客户即为正在窗口办理事务的客户,他办完事务离开队列的时刻就是即将发生的客户离开事件的时刻,也就是说,对每个队头客户都存在一个将要驱动的客户离开事件。因此,在任何时刻即将发生的事件只有下列5种可能:①新的客户到达;②1号窗口客户离开;③2号窗口客户离开;④3号窗口客户离开;⑤4号窗口客户离开。
从以上分析可见,在这个模拟程序中只需要两种数据类型:有序链表和队列。它们的数据元素类型分别定义如下:
typedef struct
{
int OccurTime; /*事件发生时刻*/
int NType; /*事件类型,0表示到达事件,1~4表示4个窗口的离开事件*/
}Event,ElemType; /*事件类型,有序链表LinkList的数据元素类型*/
typedef LinkList EventList /*事件链表类型,定义为有序链表*/
typedef struct
{
int ArrivalTime; /*到达时刻*/
int Duration; /*办理事务所需时间*/
}QElemType; /*队列的数据元素类型*/
现在我们详细分析上述算法中的两个主要操作步骤是如何实现的。
先看对新客户到达事件的处理。
由于在实际的银行中,客户到达的时刻及其办理事务所需时间都是随机的,因此在模拟程序中可以用随机数来代替。假设第一个客户进门的时刻为0,即是模拟程序处理的第一个事件,之后每个客户到达的时刻均在前一个客户到达时设置。因此在客户到达事件发生时需先产生两个随机数:其一为此时刻到达的客户办理事务所需时间DurTime;其二为下一客户将到达的时间间隔InterTime,假设当前事件发生的时刻为OccurTime,则下一个客户到达事件发生的时刻为OccurTime+InterTime。由此应产生一个新的客户到达事件插入事件表;刚到达的客户则应插入到当前所含元素最少的队列中;若该队列在插入前为空,则还应产生一个客户离开事件插入事件表。
客户离开事件的处理比较简单。首先计算该客户在银行的逗留时间,然后从队列中删除该客户后查看队列是否为空,若不空则设置一个新的队头客户离开事件。
最后给出在上述数据结构下实现的银行事件驱动模拟程序的算法。
EventList ev; /*事件表*/
Event ev; /*事件*/
LinkQueue q[5]; /*4个客户队列*/
QElemType cstomer; /*客户记录*/
int TotalTime,CustomerNum; /*累计客户逗留时间,客户数*/
int cmp(Event b); /*依事件a的发生时刻<或=或>事件b的发生时刻分别返回-1或0或1*/
void OpenForDay( )
{
TotalTime=0; CustomerNum=0; /*初始化累计时间和客户数为0*/
InitList(ev); /*初始化事件链表为空表*/
en.OccurTime=0;en.NType=0; /*设置第一个客户到达事件*/
OrderInsert(ev,en.cmp); /*插入事件表*/
for(i=1;i<=4;++i) InitQueue(q[i]); /*置空队列*/
}
void CustomerArrived( )
{
++CustomerNum;
Random(Durtime,InterTime); /*生成随机数*/
t=en.OccurTime+InterTime; /*下一客户到达时刻*/
if(t<CloseTime) /*银行尚未关门,插入事件表*/
OrderInsert(ev,(t,0),cmp);
i=Minimum(q); /*求长度最短队列*/
EnQueue(q[i],(en.OccurTime,DurTime));
if(QueueLength(q[i])==1)
/*设置第i队列的一个离开事件并插入事件表*/
OrderInsert(ev,(en.OccurTime+DurTime,i),cmp);
}
void CustomerDeparture()
{
i=en.NType;DelQueue(q[i],customer); /*删除第i队列的队头客户*/
TomtalTime+=en.OccurTime-customer.ArrivalTime; /*累计客户逗留时间*/
if(!QueueEmpty(q[i]))
{
GetHead(q[i],customer); /*设置第i队列的一个离开事件并插入事件表*/
OrderInsert(ev,(en.OccurTime+curtomer.Duratiom,i),(*cmp)());
}
}
void Bank_Simulation(int CloseTime)
{
OpenForDay(); /*初始化*/
while(!ListEmpty(ev))
{
DelFirst (GetHead(ev),p); en=GetCurElem(p);
if(en.NType==0)
CustomerArrived(); /*处理客户到达事件*/
else CustomerDeparture(); /*处理客户离开事件*/
}
/*计算并输出平均逗留时间*/
printf("The Average Time is%f\n",(float)TotalTime/CustomerNum);
} /*Bank_Simulation*/