21、数据结构笔记之十九列队实现离散事件模拟

           “努力学习，勤奋工作，让青春更加光彩。”

           再来看下列队实现离散事件模拟。从下篇开始我们去搞串了。

1.  离散事件模拟

离散事件模拟，将银行业务作为模拟，假设有4个窗口对外接待客户，从早晨银行开门起不断有客户进入银行，每个窗口在某一时刻只能接待一个客户，因此客户人数众多时需要每个窗口前顺序排队，对于刚进入银行的客户，如果某个窗口业务员正空闲，则可上前办理业务；反之，若4个窗口均有客户所占，他便会排在人数最少的队伍后面。现需要编制一个程序以模拟银行这种业务活动并计算一天中客户在银行逗留的平均时间。其中，客户到达时间的间隔在1~5分钟之间，客户的业务办理时间在1~30分钟之间，所有时间使用int型，表示从开始营业始所经历的分钟数。

算法处理的主要对象是“事件”，事件的主要信息是事件类型和事件发生的时刻。算法中处理的事件有两类：一类是客户到达事件；另一类是客户离开事件。前一类事件发生的时刻随客户到来自然形成；后一类事件发生时刻则有客户事务所需时间和等待所耗时间而定。

任何时刻只有5种可能①新的客户到达，②1号窗口客户离开，③2号窗口客户离开，④3号窗口客户离开，⑤4号窗口客户离开。

接下去看下代码实现。

2.  定义

定义一个事件结构体，包含事件发生时刻，事件类型。

typedefintStatus;

typedefstructEvent{  //事件类型

   intOccurTime; //事件发生时刻

   intNType;     //事件类型，0表示到达事件，1至4表示四个窗口的离开事件

   structEvent*next;

}Event,ElemType;

定义一个链表

typedefstruct{//单向链表结构

   ElemType*head;//头指针

   ElemType*tail;//尾指针

   intlen;   //长度

}LinkList;

typedefLinkListEventList;//事件链表

定义队列元素

typedefstructQElemType{//队列元素

   intArriveTime;//到达时间

   intDuration;//办理业务所需时间

   structQElemType*next;

}QElemType;

定义一个队列结构

typedefstruct{//队列结构

   QElemType*head;//头指针

   QElemType*tail;//尾指针

}LinkQueue;

3.  全局变量

创建如下全局变量，包括链表，事件，队列数组，事件类型，总共使用时间，总共客户数量，营业事件。

EventListev;

Eventen;

LinkQueueq[5];

QElemTypecustomer;

intTotalTime,CustomerNum;

intCloseTime=50;//关闭时间，即营业时间长度

4.  InitList函数

初始化事件链表函数。

5.  OrderInsert

插入事件到事件链表中。

6.  InitQueue

初始化队列,银行排队队列。

7.  OpenForDay函数

初始化TotalTime,CustomerNum，初始化ev链表。初始化事件en，插入第一个事件到ev链表。

然后初始化4个队列。

voidOpenForDay(){

   //初始化操作

   inti;

    TotalTime=0;    CustomerNum=0;

   InitList(&ev);//初始化事件队列

   en.OccurTime=0;

   en.NType=0;

   OrderInsert(&ev,en);

   for(i=1;i<=4;i++)

       InitQueue(&q[i]);//初始化四个窗口队列

}//OpenForDay

8.  CustomerArrived

新客户到达，同时将全局变量CustomerNum自加。

同时定义这个客户的处理时间为30分钟内，下一个客户时间在5分钟内，

然后判断下个客户到达的时间是否在银行关闭之前，如果超过则结束，否则将该事件插入到事件队列中去。此外调用ShortestQueue函数得到排队最少的窗口所在队列。

将客户事件加入到最少窗口队列。最后判断这个窗口队列是否只有1个客户，如果是一个客户，则在事件列表中插入一个离开的事件。

9.  CustomerDepature

事件中标注了哪个队列，然后从该队列中删除事件并打印。

接着将总耗时加上该客户的消耗。

最后判断该窗口队列是否为空，如果不为空，则获得该窗口队列头客户。

将该客户仍入到事件链表中。

10.      Bank_Simulation

Bank_Simulation函数是main 函数中的主函数。基本算法也在改函数中体现。

先调用  OpenForDay初始化。然后判断事件队列是否为空，如果为空，则结束程序。

不为空，则进入处理。

从事件链表中删除一个事件赋值给en变量，判断类型如果是0则是新顾客到来，如果不是则说明需有客户离开，打印队列，以此往复。

voidBank_Simulation(){

   //银行排队模拟

   OpenForDay();

    srand((unsigned)time(NULL));

   while(!ListEmpty(&ev)){

       DelFirst(&ev,&en);

       if(en.NType==0)

           CustomerArrived();

       else

           CustomerDepature();

       //PrintEventList();

       PrintQueue();

    }

    printf("\nTotaltime is: %d min,average time is: %g min.\n",TotalTime,(float)TotalTime/CustomerNum);

}

11.      Main函数

Main函数就一个Bank_Simulation函数。

开始初始化时候，在事件链表中有第一个客户到达。然后进入主循环，从事件链表中得到第一个客户事件并从链表去掉，然后调用客户到达或者离开函数。

客户到达函数，然后将当前时间变成客户事件时间加上下一个客户到达事件时间，然后插入到客户事件链表中，并放入到最短窗口队列中，判断窗口队列是否是1，插入客户离开的事件到客户链表中。（注意事件链表是按时间顺序排列的）

客户离开函数，从窗口队列中删除一个客户，打印消息，判断该窗口队列是否为空，如果不为空则或者当前队列头客户，然后向事件链表中插入一个离开事件。

执行如下图1所示：

12.      源码

//离散事件模拟，模拟银行营业时的排队情况

//不考虑顾客中途离开，顾客到达事件随机，业务办理时间

//长度随机，选择最短的队排队，不再换队

//作者：nuaazdh

//时间：2011年12月10日08:52:37

#include<stdio.h>

#include<time.h>

#include<stdlib.h>

#defineOK1

#defineERROR0

#defineTRUE1

#defineFALSE0

typedefintStatus;

typedefstructEvent{  //事件类型

   intOccurTime; //事件发生时刻

   intNType;     //事件类型，0表示到达事件，1至4表示四个窗口的离开事件

   structEvent*next;

}Event,ElemType;

typedefstruct{//单向链表结构

   ElemType*head;//头指针

   ElemType*tail;//尾指针

   intlen;   //长度

}LinkList;

typedefLinkListEventList;//事件链表

typedefstructQElemType{//队列元素

   intArriveTime;//到达时间

   intDuration;//办理业务所需时间

   structQElemType*next;

}QElemType;

typedefstruct{//队列结构

   QElemType*head;//头指针

   QElemType*tail;//尾指针

}LinkQueue;

EventNewEvent(intoccurT,intnType);

   //根据OccurTime和NType值，创建新事件

StatusInitList(LinkList*L);

   //初始化事件链表

StatusOrderInsert(LinkList*L,Evente);

   //将事件e按发生时间顺序插入有序链表L中

StatusListEmpty(LinkList*L);

   //判断链表L是否为空，为空返回TRUE，否则返回FALSE

StatusDelFirst(LinkList*L,ElemType*e);

   //链表L不为空，删除其首结点，用e返回，并返回OK；否则返回ERROR

StatusListTraverse(LinkList*L);

   //遍历链表

StatusInitQueue(LinkQueue*Q);

   //初始化队列Q

StatusEmptyQueue(LinkQueue*Q);

   //若队列Q为空，返回TRUE，否则返回FALSE

StatusDelQueue(LinkQueue*Q,QElemType*e);

   //若队列Q不为空，首结点出队，用e返回，并返回OK；否则返回ERROR

StatusEnQueue(LinkQueue*Q,QElemTypee);

   //结点e入队Q

intQueueLength(LinkQueueQ);

   //返回队列Q的长度，即元素个数

StatusGetHead(LinkQueue*Q,QElemType*e);

   //若队列Q不为空，用e返回其首结点，并返回OK,否则返回ERROR

StatusQueueTraverse(LinkQueue*Q);

   //遍历队列Q

//------------------//

intMin(inta[],intn);

   //返回长度为n的数组a第一个最小值的下标，从1开始

intShortestQueue();

   //获取最短队列的编号

voidOpenForDay();

   //初始化操作

voidCustomerArrived();

   //顾客达到事件

voidCustomerDepature();

   //顾客离开事件

voidBank_Simulation();

   //银行排队模拟

voidPrintEventList();

   //输出事件队列

voidPrintQueue();

   //打印当前队列

//----全局变量-----//

EventListev;

Eventen;

LinkQueueq[5];

QElemTypecustomer;

intTotalTime,CustomerNum;

intCloseTime=50;//关闭时间，即营业时间长度

//--------------main()------------------//

intmain()

{

   Bank_Simulation();

   return0;

}

//--------------模拟排队----------------//

voidOpenForDay(){

   //初始化操作

   inti;

   TotalTime=0;    CustomerNum=0;

   InitList(&ev);//初始化事件队列

   en.OccurTime=0;

   en.NType=0;

   OrderInsert(&ev,en);

   for(i=1;i<=4;i++)

       InitQueue(&q[i]);//初始化四个窗口队列

}//OpenForDay

voidCustomerArrived(){

   //顾客达到事件

   intdurtime,intertime,i,t;

   QElemTypee;

   ++CustomerNum;

   intertime=rand()%5+1;//间隔时间在5分钟内

   durtime=rand()%30+1;//办理业务时间在30分钟内

   t=en.OccurTime+intertime;

   if(t<CloseTime){//银行尚未关门

        printf("Anew customer will arrive at:%d\n",en.OccurTime);//下一位顾客达到时间

       OrderInsert(&ev,NewEvent(t,0));

       i=ShortestQueue();//最短队列

       e.ArriveTime=en.OccurTime;

       e.Duration=durtime;

       EnQueue(&q[i],e);

       if(QueueLength(q[i])==1)

           OrderInsert(&ev,NewEvent(en.OccurTime+durtime,i));

    }

}

voidCustomerDepature(){

   //顾客离开事件

   inti=en.NType;

   DelQueue(&q[i],&customer);

    printf("Acustomer leaves at:%d\n",en.OccurTime);//输出顾客离开时间

    TotalTime+=en.OccurTime-customer.ArriveTime;

   if(!EmptyQueue(&q[i])){

       GetHead(&q[i],&customer);

       OrderInsert(&ev,NewEvent(en.OccurTime+customer.Duration,i));

    }

}

voidBank_Simulation(){

   //银行排队模拟

   OpenForDay();

    srand((unsigned)time(NULL));

   while(!ListEmpty(&ev)){

       DelFirst(&ev,&en);

       if(en.NType==0)

           CustomerArrived();

       else

           CustomerDepature();

       //PrintEventList();

       PrintQueue();

    }

    printf("\nTotaltime is: %d min,average time is: %g min.\n",TotalTime,(float)TotalTime/CustomerNum);

}

voidPrintQueue(){

   //打印当前队列

   inti;

   for(i=1;i<=4;i++){

       printf("Queue %d have %d customer(s):",i,QueueLength(q[i]));

       QueueTraverse(&q[i]);

    }

    printf("\n");

}

voidPrintEventList(){

   //输出事件队列

    printf("CurrentEventlist is：\n");

   ListTraverse(&ev);

}

intMin(inta[],intn){

   //返回长度为n的数组a第一个最小值的下标，从0开始

   inti,tmp,ind=0;

    tmp=a[0];

   for(i=1;i<n;i++){

       if(a[i]<tmp){

           tmp=a[i];

           ind=i;

        }

    }

   returnind;

}

intShortestQueue(){

   //获取最短队列的编号

   inti,a[4];

   for(i=1;i<=4;i++){

       a[i-1]=QueueLength(q[i]);

       //printf("队%d的长度为%d\n",i,QueueLength(q[i]));

    }

   returnMin(a,4)+1;//队列从1开始编号

}

//-----------队和链表操作--------------//

EventNewEvent(intoccurT,intnType){

   //根据OccurTime和NType值，创建新事件

   Evente;

   e.OccurTime=occurT;

    e.NType=nType;

   returne;

}

StatusInitList(LinkList*L){

   //初始化事件链表

   L->head=L->tail=(ElemType*)malloc(sizeof(ElemType));

   if(!L->head){

       printf("Apply for memory error.LinkList initializefailed.\n");

       exit(0);

    }

   L->head->next=NULL;

   returnOK;

}

StatusOrderInsert(LinkList*L,Evente){

   //将事件e按发生时间顺序插入有序链表L中

   ElemType*p,*q,*newptr;

    newptr=(ElemType*)malloc(sizeof(ElemType));

   if(!newptr){

       printf("Apply for memory error，new node can't insert intot theEventlist.\n");

       exit(0);

    }

    *newptr=e;

   if(TRUE==ListEmpty(L)){//链表为空

      L->head->next=newptr;

      L->tail=newptr;

      L->tail->next=NULL;

      returnOK;

    }

    q=L->head;

    p=L->head->next;

   while(p){//遍历整个链表

       if(p->OccurTime>=newptr->OccurTime)

           break;

        q=p;

       p=p->next;

    }

   q->next=newptr;

   newptr->next=p;

   if(!p)//插入位置为链表尾部

       L->tail=newptr;

   returnOK;

}

StatusListEmpty(LinkList*L){

   //判断链表L是否为空，为空返回TRUE，否则返回FALSE

   if((L->head==L->tail)&&(L->head!=NULL))

       returnTRUE;

   else

       returnFALSE;

}

StatusDelFirst(LinkList*L,ElemType*e){

   //链表L不为空，删除其首结点，用e返回，并返回OK；否则返回ERROR

   ElemType*p=L->head->next;

   if(!p)

       returnERROR;

   L->head->next=p->next;

    *e=*p;

    free(p);

   if(L->head->next==NULL)

       L->tail=L->head;

   returnOK;

}

StatusListTraverse(LinkList*L){

   //遍历链表

   Event*p=L->head->next;

   if(!p){

       printf("List is empty.\n");

       returnERROR;

    }

   while(p!=NULL){

       printf("OccurTime:%d,Event Type:%d\n",p->OccurTime,p->NType);

       p=p->next;

    }

    printf("\n");

   returnOK;

}

StatusInitQueue(LinkQueue*Q){

   //初始化队列Q

   Q->head=Q->tail=(QElemType*)malloc(sizeof(QElemType));

   if(!Q->head){

       printf("Apply for memory error.LinkQueue initializefailed.\n");

       exit(0);

    }

   Q->head->next=NULL;

   returnOK;

}

StatusEmptyQueue(LinkQueue*Q){

   //若队列Q为空，返回TRUE，否则返回FALSE

   if(Q->head==Q->tail&&Q->head!=NULL)

       returnTRUE;

   else

       returnFALSE;

}

StatusDelQueue(LinkQueue*Q,QElemType*e){

   //若队列Q不为空，首结点出队，用e返回，并返回OK；否则返回ERROR

   QElemType*p=Q->head->next;

   if(!p)

       returnERROR;

    *e=*p;

   Q->head->next=p->next;//修正队首指针

    free(p);

   if(!Q->head->next)//队空

       Q->tail=Q->head;

   returnOK;

}

StatusEnQueue(LinkQueue*Q,QElemTypee){

   //结点e入队Q

   QElemType*p=(QElemType*)malloc(sizeof(QElemType));

   if(!p){

       printf("Apply for memory error,new element can'tenqueue.\n");

        exit(0);

    }

    *p=e;

   p->next=NULL;

   Q->tail->next=p;//插入队尾

   Q->tail=p;//修改队尾指针

   returnOK;

}

intQueueLength(LinkQueueQ){

   //返回队列Q的长度，即元素个数

   intcount=0;

   QElemType*p=Q.head->next;

   while(p){

       p=p->next;

       count++;

    }

   returncount;

}

StatusGetHead(LinkQueue*Q,QElemType*e){

   //若队列Q不为空，用e返回其首结点，并返回OK,否则返回ERROR

   if(EmptyQueue(Q))

       returnERROR;

    *e=*(Q->head->next);

       returnOK;

}

StatusQueueTraverse(LinkQueue*Q){

   //遍历队列Q

   QElemType*p=Q->head->next;

   if(!p){

       printf("--Is empty.\n");

       returnERROR;

    }

   while(p){

       printf("(%d,%d) ",p->ArriveTime,p->Duration);

       p=p->next;

    }

    printf("\n");

   returnOK;

}