一、問題描述及解決思想
1、問題描述
2、解決思想
我們需要注意“事件”的概念，客戶到達和客戶離開都稱為“事件”。
二、C語言描述
三、C語言實作
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#define Qu 4 //客戶隊列數
#define Khjg 5 //兩相鄰到達的客戶的時間間隔最大值
#define Blsj 30//每個客戶辦理業務的時間最大值
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int Boolean;
typedef struct
{
int OccurTime; //事件發生時刻
int NType; //事件類型，Qu表示到達事件，
//0-Qu-1表示Qu個視窗的離開事件
}Event,ElemType;//事件類型，有序連結清單LinkList的資料元類型
typedef struct LNode // 結點類型
{
ElemType data;
LNode *next;
}*Link,*Position;
struct LinkList // 連結清單類型
{
Link head,tail; // 分别指向線性連結清單中的頭結點和最後一個結點
int len; // 訓示線性連結清單中資料元素的個數
};
typedef LinkList EventList; // 事件連結清單類型，定義為有序連結清單
typedef struct
{
int ArrivalTime;
int Duration;
}QElemType; //隊列的資料元素類型
typedef struct QNode
{
QElemType data;
QNode *next;
}*QueuePtr; //隊列
struct LinkQueue
{
QueuePtr front,rear; // 隊頭、隊尾指針
};
EventList ev;//事件表
Event en; //事件
Event et;//臨時變量
LinkQueue q[Qu]; //Qu個隊列客戶
QElemType customer; //客戶記錄
int TotalTime=0,CustomerNum=0;//累計客戶逗留時間,客戶數(初值為0)
int CloseTime; // 銀行營業時間(機關是分)
int cmp(Event a,Event b)
{ //依事件a的發生時刻<、=或>事件b的發生時刻分别傳回-1、0或1
if(a.OccurTime==b.OccurTime)
return 0;
else
return (a.OccurTime-b.OccurTime)/abs(a.OccurTime-b.OccurTime);
}
Status InitList(LinkList &L)
{ // 構造一個空的線性連結清單
Link p;
p=(Link)malloc(sizeof(LNode)); // 生成頭結點
if(p)
{
p->next=NULL;
L.head=L.tail=p;
L.len=0;
return OK;
}
else
return ERROR;
}//InitList
Status InitQueue(LinkQueue&Q)
{ // 構造一個空隊列Q
if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode))))
exit(-1);
Q.front->next=NULL;
return OK;
}//InitQueue
Status OrderInsert(LinkList&L,ElemType e,int (*comp)(ElemType,ElemType))
{ //已知L為有序線性連結清單，将元素e按非降序插入在L中。（用于一進制多項式）
Link o,p,q;
q=L.head;
p=q->next;
while(p!=NULL&&comp(p->data,e)<0) // p不是表尾且元素值小于e
{
q=p;
p=p->next;
}
o=(Link)malloc(sizeof(LNode)); // 生成結點
o->data=e; // 指派
q->next=o; // 插入
o->next=p;
L.len++; // 表長加1
if(!p) // 插在表尾
L.tail=o; // 修改尾結點
return OK;
}//OrderInsert
void OpenForDay()
{
int i;
InitList(ev);
en.OccurTime=0;
en.NType=Qu;
OrderInsert(ev,en,cmp);//插入事件表
for(i=0;i<Qu;++i)
InitQueue(q[i]);
}//OpenForDay
void Random(int &d,int&i)
{
d=rand()%Blsj+1;//1到Blsj之間的随機數
i=rand()%Khjg+1;
}//Random
int QueueLength(LinkQueue Q)
{ // 求隊列的長度
int i=0;
QueuePtr p;
p=Q.front;
while(Q.rear!=p)
{
i++;
p=p->next;
}
return i;
}//QueueLength
int Minimum(LinkQueue Q[]) //傳回最短隊列的序号
{
int l[Qu],i,k;
for(i=0;i<Qu;i++)
l[i]=QueueLength(Q[i]);
k=0;
for(i=1;i<Qu;i++)
if(l[i]<l[0])
{
l[0]=l[i];
k=i;
}//if
return k;
}//Minimum
Status EnQueue(LinkQueue&Q,QElemType e)
{ // 插入元素e為Q的新的隊尾元素
QueuePtr p;
if(!(p=(QueuePtr)malloc(sizeof(QNode))))// 存儲配置設定失敗
exit(OVERFLOW);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}//EnQueue
Status DeQueue(LinkQueue&Q,QElemType &e)
{ //若隊列不空,删除Q的隊頭元素,用e傳回其值,并傳回OK,否則傳回ERROR
QueuePtr p;
if(Q.front==Q.rear)
return ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
return OK;
}//DeQueue
void CustomerArrived()
{
QElemType f;
int durtime,intertime,i;
++CustomerNum;
Random(durtime,intertime);
et.OccurTime=en.OccurTime+intertime;//下一客戶到達時刻，隔了intertime來了下一//個客戶
et.NType=Qu; // 隊列中隻有一個客戶到達事件
if(et.OccurTime<CloseTime)
OrderInsert(ev,et,cmp); //不讓下一個進入營業廳了
i=Minimum(q); //處理目前進來的人
f.ArrivalTime=en.OccurTime;
f.Duration=durtime;
EnQueue(q[i],f);
if(QueueLength(q[i])==1)
{
et.OccurTime=en.OccurTime+durtime;
et.NType=i;
OrderInsert(ev,et,cmp); // 設定第i隊列的一個離開事件并插入事件表
}//if
}//CustomerArrived
Status GetHead(LinkQueueQ,QElemType &e)
{ // 若隊列不空,則用e傳回Q的隊頭元素,并傳回OK,否則傳回ERROR
QueuePtr p;
if(Q.front==Q.rear)
return ERROR;
p=Q.front->next;
e=p->data;
return OK;
}//GetHead
Position GetHead(LinkList L)
{ //傳回線性連結清單L中頭結點的位置
return L.head;
}//GetHead
Status QueueEmpty(LinkQueue Q)
{ //若Q為空隊列,則傳回TRUE,否則傳回FALSE
if(Q.front==Q.rear)
return TRUE;
else
return FALSE;
}//QueueEmpty
void CustomerDeparture()
{ // 處理客戶離開事件，en.NType<Qu
int i;
i=en.NType;
DeQueue(q[i],customer);
TotalTime+=en.OccurTime-customer.ArrivalTime;
if(!QueueEmpty(q[i])) //設定第i隊列的一個離開事件，并插入事件表
{
GetHead(q[i],customer);
et.OccurTime=en.OccurTime+customer.Duration;
et.NType=i;
OrderInsert(ev,et,cmp);
}//if
}//CustomerDeparture
Status ListEmpty(LinkList L)
{ //若線性連結清單L為空表，則傳回TRUE，否則傳回FALSE
if(L.len)
return FALSE;
else
return TRUE;
}//ListEmpty
Status DelFirst(LinkList&L,Link h,Link &q) // 形參增加L,因為需修改L
{ // h指向L的一個結點，把h當做頭結點，删除連結清單中的第一個結點并以q傳回。
//若連結清單為空(h指向尾結點)，q=NULL，傳回FALSE
q=h->next;
if(q) // 連結清單非空
{
h->next=q->next;
if(!h->next) // 删除尾結點
L.tail=h; // 修改尾指針
L.len--;
return OK;
}
else
return FALSE; // 連結清單空
}//DelFirst
ElemType GetCurElem(Link p)
{ // 已知p指向線性連結清單中的一個結點，傳回p所指結點中資料元素的值
return p->data;
}//GetCurElem
void Bank_Simulation()
{
Link p;
OpenForDay();
while(!ListEmpty(ev))
{
DelFirst(ev,GetHead(ev),p);
en.OccurTime=GetCurElem(p).OccurTime;
en.NType=GetCurElem(p).NType;
if(en.NType==Qu)
CustomerArrived();
else
CustomerDeparture();
}//while
printf("顧客總數:%d, 所有顧客共耗時:%d分鐘, 平均每人耗時: %d分鐘\n",CustomerNum,TotalTime,TotalTime/CustomerNum);
}//Bank_Simulation
int main()
{
printf("請輸入銀行營業時間長度（機關：分）\n");
scanf("%d",&CloseTime);
Bank_Simulation();
return OK;
}
四、舉例
五、說明
相當于一個時間軸，但是管着四個隊列的進出情況。
第個隊列的人員進入時，都要預報下一個人員進來的時刻，并登記下一個人員進來時刻到時間軸，同時将自己進來的時刻及逗留時間選擇一個最短的隊列進行注冊，如果自己是第一個進來的，或者可以排到某一隊列的第一位，則還要在時間軸上登記出的時間。
離開時，自己将注冊的隊列資訊删除，同時，目前隊列的下一個人向時間軸預報自己離開的時間。
可見，時間軸就是一個事件（無論是來了的，還是走了的）集，通過預判事件的先後發生順序而控制着整個過程的發展。