banksuccess.cpp

假设某银行有4个窗口对外接待客户,从早晨银行开门起不断有客户进入银行。由于每个窗口在某个时刻只能接待一个客户

#include<iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct {
	size_t OccurTime; //事件发生时刻
    size_t	NType; //事件类型 
} Event,ElemType; // 链表数据元素类型 

typedef struct Enode {
	Event event;
	struct Enode *next;
} Enode, *EventList;

typedef struct {
	size_t ArrTime, Duration;  // 到达时刻；办理时间 
} QElemType;  // 队列数据元素类型 

typedef struct Qnode {
	QElemType Cust;  // 客户记录 
	struct Qnode *next;
} Qnode, *Qptr;

typedef struct {
	Qptr front;
	Qptr rear; // 队头指针，队尾指针 
} LinkQueue;



EventList ev;          // 事件表 
Event en;              // 事件 
LinkQueue q[4];  // 客户队列 
QElemType customer;        // 客户记录 
size_t TotalTime, CustNum;  //累计客户逗留时间，客户数 
int DeQueue(LinkQueue *Q)  // 出队 
{
	Qptr tmp;

	if ( Q->front == Q->rear ) {
		return 0;  // 如果队列已空，返回 0 
    }

	tmp = Q->front->next;
	customer = tmp->Cust;
	Q->front->next = tmp->next;
	if ( Q->rear == tmp ) {  // 如果队尾元素被删除，则队尾指针要指向头结点 
		Q->rear = Q->front;
    }
	free(tmp);
	
	return 1;
}  


void DestroyList( EventList L ) // 销毁链表 
{
	EventList T = L;

	for ( L = L->next; L; T = L, L = L->next ) {
		free( T );
	}
	free( T );
} 


void DestroyQueue(LinkQueue *Q) // 销毁队列 
{
	while ( Q->front ) {
		Q->rear = Q->front->next;
		free( Q->front );
		Q->front = Q->rear;
	}
} 


void DestroyAll( )  // 销毁链表和队列 
{
     size_t i;
     
     DestroyList( ev );
     for ( i = 0; i < 4; ++i ) {
         DestroyQueue( &q[i] );
     }
} 

EventList InitList( void )  // 创建链表 
{
	EventList h;
	if ( !( h =(EventList) malloc(sizeof(Qnode)) ) ) {  // 创建失败，返回 NULL 
		return NULL;
    }
	h->next = NULL;
	
	return h;
} 


int OrderInsert(EventList ev, Event a)  // 插入事件表 
{
	EventList tmp, h = ev, e = ev->next;

	if ( !( tmp = InitList() ) ) {  // 分配空间失败，返回 0 
		return 0;
    }
	// 插入 
	tmp->event = a;
	while ( e && (a.OccurTime > e->event.OccurTime) ) {
		h = e;
		e = e->next;
	}
	h->next = tmp;
	tmp->next = e;

	return 1;
} 
int InitQueue(LinkQueue *Q)  // 建立空队列 
{

	Q->rear = Q->front = (Qptr)malloc( sizeof (Qnode) );
	if ( !Q->front ) {  // 创建失败，返回 0 
		return 0;
    }
	Q->front->next = NULL;
	
	return 1;
} 
size_t QueueLength(LinkQueue Q) // 计算队列长度 

{
	size_t i;

	for ( i = 0; Q.front->next; ++i ) {
		Q.front = Q.front->next;
    }

	return i;
} /* End of QueueLength */


size_t Minimun( void )  // 求长度最短队列 
{
	size_t h = 0, i, j, k;

	j = QueueLength(q[0]);
	for ( i = 1; i < 4; ++i ) {
		k = QueueLength(q[i]);
		if ( j > k ) {
			j = k;
			h = i;
		}
	}
	
	return h;
} 
int EnQueue(LinkQueue *Q, QElemType e)  // 进队 
{
	Qptr tmp;
      tmp=(Qptr)malloc(sizeof(Qnode));
	if ( !tmp ) {
		return 0; // 进队失败，返回 0 
    }
    
	tmp->Cust = e;
	tmp->next = NULL;
	Q->rear->next = tmp;
	Q->rear = tmp;

	return 1;
} 


int bank_Simulation( void )  // 初始化操作 
{
	size_t i;

	srand( time(NULL) );          // 生成随机数种子 
	
	CustNum = TotalTime = 0;      // 初始化累计时间和客户数 
	if ( !( ev = InitList() ) ) {  // 初始化事件链表 
		return 0;  /* 创建失败，返回 0 */
    }
	en.OccurTime = 0;
	en.NType = 4;  // 设定第一个客户到达事件 
	
	if ( !OrderInsert(ev, en) ) {  // 插入事件表 
		DestroyList( ev );
        return 0;  // 插入失败，返回0 
    }
	for ( i = 0; i < 4; ++i ) {  // 置空队列 
		if ( !InitQueue(&q[i]) ) {
			DestroyList( ev );
            for ( i = 0; q[i].front; ++i ) {
                DestroyQueue( &q[i] );
            }
            return 0;  // 创建队列失败，返回 0 
        }
	}
	
	return 1;
} 


int CustomerArrived( void ) // 处理客户到达事件  
{
	int durtime, intertime;
	QElemType e;
	int i;

	++CustNum;
	// 生成随机数 
    durtime = rand() / (RAND_MAX / 30 + 1) + 1; // 事务处理时间不超过 30 分钟
	intertime = rand() / (RAND_MAX / 5);    //5 分钟内有一位客人到达银行，0 表示客户同时到达 
	e.ArrTime = en.OccurTime;
	e.Duration = durtime;
	en.OccurTime += intertime;          // 下一客户到达时间 
	if ( en.OccurTime < 480 ) {   // 银行尚未关门，插入事件表 
		if ( !OrderInsert(ev, en) ) {   // 插入失败 
			DestroyAll();
            return 0;
        }
	}

	i = Minimun();  // 求长度最短队列 
	if ( !EnQueue(&q[i], e) ) {
		DestroyAll();
        return 0;
    }

	// 如果此时 i 号窗口只有一位顾客，则马上把他的离开事件插入事件表 
    if ( QueueLength(q[i]) == 1 ) {
		en.NType = i;
		en.OccurTime = e.ArrTime + durtime;
		if ( !OrderInsert(ev, en) ) {
             DestroyAll();
             return 0;
        }
	}

	return 1;
} 

int CustomerDeparture( void ) // 处理客户离开事件 
{
	Qptr tmp;
	size_t i = en.NType;

	if ( !DeQueue( &q[i] ) ) {  // 删除排头客户 
		DestroyAll();
        return 0;
    }
    
	TotalTime = TotalTime + en.OccurTime - customer.ArrTime; // 累计逗留时间 
	if ( q[i].front != q[i].rear ) {
		tmp = q[i].front->next;
		customer = tmp->Cust;
		en.OccurTime += customer.Duration;
		if ( !OrderInsert(ev, en) ) {
			DestroyAll();
            return 0;
        }
	}

	return 1;
}  


void DelFirst()  // 删除事件表第一个节点，并把值赋给en 
{
	EventList tmp = ev->next;

	ev->next = tmp->next;
	en = tmp->event;

	free(tmp);
} 

int main(void)
{
	bank_Simulation();
	while (ev->next )
	{
		DelFirst();
		if(en.NType ==4)
		
			CustomerArrived();
		else
			CustomerDeparture();
	}
	cout<<"平均逗留时间为:"<<(float)TotalTime/CustNum<<endl;
	cout<<"Press ENTER to quit..." <<endl;
	getchar();
	DestroyAll();
	
	return EXIT_SUCCESS;
}