银行排队业务模拟

//数据结构与算法 P65-66  算法3.6 
#include
#include
#include


typedef struct{
int OccurTime;  //时间发生时刻 
int NType;      //事件类型，0表示到达事件，1至4表示四个窗口的离开事件 
}Event;


typedef struct EventList{
Event dat;
struct EventList *next;
}EventList;


typedef struct QElemType{
int ArrivalTime; //到达时间 
int Duration; //办理业务所需时间
struct QElemType *next; 
}QElemType;


typedef struct LinkQueue{
struct QElemType *front;
struct QElemType *rear;
}LinkQueue;


typedef unsigned char Status;


typedef int (*p_func)(int a, int b);


#define CloseTime 480 //8小时工作制 
#define DealTime 30  //每单交易最长30分钟 
#define CustomerInterval 5   // 


#define OK 1
#define FAILED 0


#define OVERFLOW -1


EventList ev;  //事件表 
Event en;  //事件 
LinkQueue customer_q[4];//4个客户队列 
QElemType customer; //客户记录 
int CustomerNum; //累计客户逗留时间，客户数 
long int TotalTime;


Status InitQueue(LinkQueue *q8)
{
q8->front = q8->rear = (QElemType *)malloc(sizeof(QElemType));

if(q8->front == NULL)
exit(OVERFLOW);
q8->front->next = NULL;

return OK;
}


Status DestroyQueue(LinkQueue *q7)
{
while(q7->front)
{
q7->rear = q7->front->next;
free(q7->front);
q7->front = q7->rear;
}

return OK;
}


Status QueueEmpty(LinkQueue *q6)
{
if(q6->front == q6->rear)
return OK;

return FAILED;
}


Status ClearQueue(LinkQueue *q5)
{
struct QElemType *tmp;

while(q5->front != q5->rear)
{
tmp = q5->front->next;
free(q5->front);
q5->front = tmp;
}
q5->front->next = NULL;

return OK;
}


int QueueLength(LinkQueue *q_tmp)
{
struct QElemType *tmp;
int len = 0;

tmp = q_tmp->front;
while(tmp != q_tmp->rear)
{
tmp = tmp->next;
len++;
}

return len;
}


int MinLenQueue(void)
{
int index, len, i;

index = 0;
len = QueueLength(&customer_q[0]);
for(i = 1; i < 4; i++)
{
if(len > QueueLength(&customer_q[i]))
{
len = QueueLength(&customer_q[i]);
index = i;
}
}

return index;
}


Status GetHead(LinkQueue *q4, QElemType *dat)
{
if(QueueEmpty(q4))
return FAILED;

dat = q4->front->next;

return OK;
}


Status InsertQueue(LinkQueue *q3, int ArrTime, int DurTime)
{
QElemType *p;

p = (QElemType *)malloc(sizeof(QElemType));
if(!p)
exit(OVERFLOW);

p->ArrivalTime = ArrTime;
p->Duration = DurTime;
p->next = q3->rear->next;

q3->rear->next = p;
q3->rear = p; 

return OK;
}


Status DelQueue(LinkQueue *q2, QElemType *dat)
{
QElemType *tmp;

if(q2->front == q2->rear)
return FAILED;

tmp = q2->front->next;
q2->front->next = tmp->next;
dat->ArrivalTime = tmp->ArrivalTime;
dat->Duration = tmp->Duration;
dat->next = NULL;
if(q2->rear == tmp)
q2->rear = q2->front;

free(tmp);

return OK;
}


Status InitList(EventList *L)
{
L = (EventList *)malloc(sizeof(EventList));

if(L == NULL)
exit(OVERFLOW);

L->next = NULL;

return OK;
}


Status ListEmpty(EventList *L)
{
if(L->next == NULL)
return OK;

return FAILED; 
}


Status DelListFirst(EventList *L, EventList *L2)
{
EventList *tmp;

if(L->next == NULL)
return FAILED;
tmp = L;
tmp = tmp->next;
L->next = tmp->next;

L2->dat.OccurTime = tmp->dat.OccurTime;
L2->dat.NType = tmp->dat.NType;
L2->next = NULL;

free(tmp);
return OK;
}


Status DestroyList(EventList *L)
{
free(L->next);
return OK;
}


int cmp(int a, int b)
{
if(a > b)
return 1;
else if(a == b)
return 0;

return -1;
}


Status OrderInsert(EventList *L, Event *p_evn, p_func cmp_func)
{
EventList *tmp, *tmp2;

tmp = L;

while((L->next != NULL) && (cmp_func(L->next->dat.OccurTime, p_evn->OccurTime) < 0))
{
L = L->next;
}

tmp2 = (EventList *)malloc(sizeof(EventList));
if(tmp2 == NULL)
exit(OVERFLOW);

tmp2->next = L->next;
L->next = tmp2;
tmp2->dat.OccurTime = p_evn->OccurTime;
tmp2->dat.NType = p_evn->NType;

L = tmp;

return OK;
}


void OpenForDay(void)
{
int i;

TotalTime = 0;
CustomerNum = 0;
InitList(&ev);
en.OccurTime = 0;
en.NType = 0;
OrderInsert(&ev, &en, cmp);

for(i = 0; i < 4; i++)
InitQueue(&customer_q[i]);
}


void CustorArrived(void)
{
int durtime, intertime, i;
Event QueueLeaveEvent;
Event   NextCustomer;

CustomerNum++;
srand((unsigned)(time(NULL)));
durtime = rand()%30 + 1;
NextCustomer.OccurTime = rand()%6 + en.OccurTime;
NextCustomer.NType = 0;

if(NextCustomer.OccurTime < CloseTime)
OrderInsert(&ev, &NextCustomer, cmp);

i = MinLenQueue();
InsertQueue(&customer_q[i], en.OccurTime, durtime);
if(QueueLength(&customer_q[i]) == 1)
{//设定第i个队列的一个离开事件并插入事件表 
QueueLeaveEvent.OccurTime = en.OccurTime + durtime;
QueueLeaveEvent.NType = i+1;
OrderInsert(&ev, &QueueLeaveEvent, cmp);
}
}


void CustomerLeave(void)
{
int i;
Event QueueLeaveEvent;

i = en.NType - 1;
DelQueue(&customer_q[i], &customer);
TotalTime = TotalTime + en.OccurTime - customer.ArrivalTime;

if(!QueueEmpty(&customer_q[i]))
{
GetHead(&customer_q[i], &customer);
QueueLeaveEvent.OccurTime = en.OccurTime + customer.Duration;
QueueLeaveEvent.NType = i;
OrderInsert(&ev, &QueueLeaveEvent, cmp);
}
}


void Bank_Simulation(void)
{
EventList p;

OpenForDay();
while(!ListEmpty(&ev))
{
DelListFirst(&ev, &p);
en.OccurTime = p.dat.OccurTime;
en.NType = p.dat.NType;

if(en.NType == 0)
CustorArrived();
else
CustomerLeave();
}

printf("\r\nThe average time is %f\n", (float)TotalTime/CustomerNum);
}


int main(void)
{
int i;

Bank_Simulation();
for(i = 0; i < 4; i++)
DestroyQueue(&customer_q[i]);

DestroyList(&ev);
return 1;
}