bank.cpp

实现了一个离散时间事件序列的模板

///////////////////////////////////////////////////////////////////////
//                        离散事件的模拟                             //
///////////////////////////////////////////////////////////////////////

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

#define MAX_TIME 600							//开门的时间
#define NULL 0

////////////////////////////定义全局参量///////////////////////////

int dti=5,dra=60;						


////////////////////////////子函数声明/////////////////////////////

//返回指定区间的随机数
int rnd(int,int);

//判断是否继续的子函数
bool goon();

//修改全局参量
void change();


//////////////////////////////数据类型定义/////////////////////////////


//定义队列数据元素：顾客
typedef struct customer
{
	int arrivaltime;    //到达时间
	int duration;       //停留时间
	
	customer()
	{
		arrivaltime=0;
		duration=0;
	}
} customer;


//定义链表数据元素：事件
typedef struct event
{
	int occurtime;     //事件发生时间
	short int ntype;   //事件类型：0，离开；其他，对应窗口序号（1，2，3...）

	event()
	{
		occurtime=0;
		ntype=0;
	}
}event;


//定义链表节点类模板
template<class S>
class Cnode
{
public:

	S data;							//数据域
	Cnode *next;					//指针域


//创建结点，赋初值
Cnode(S s)
{
	data=s;
	next=NULL;
}

};


///////////////////////////////////类的定义///////////////////////////////////


//定义链表类模板
template<class T>
class Clink  
{
	Cnode<T> *head;             //事件链表的头结点
	Cnode<T> *tail;             //事件链表的尾结点	
	int length;                 //事件链表的长度

public:

//生成一个新链表
Clink()
{
	head=tail=NULL;             //空表头尾都为空
	length=0;                   //长度为零
}


//指定位置插入一个新元素
bool insert(T t , Cnode<T> *p=NULL)          //p==NULL则为插入表尾
{
	Cnode<T> *tt=new Cnode<T>(t);            //分配存储空间

	if(!length)                               //原先是空表
		head=tail=tt;
			
	else
	{
		Cnode<T> *p1=head,*p2;			//记录链表表头
		
		while((p1!=p)&&p1)
		{
			p2=p1;
			p1=p1->next;
			
		}
		if(p1==NULL)									
		{
			tail->next=tt;
			tail=tt;
		}
		else
		{
			tt->next=p1;
			
			if(p1!=head)			//插入中间 			
				p2->next=tt;
			else					//插入表头
				head=tt;
		}
	}
	
	length++;
	return 1;
}

//在指定位置删除结点
bool del(Cnode<T> *p)
{
	if(p==NULL)return 0;						//不进行删除
	
	else if(!length)return 0;					//空表，没的删
	
	else if(length==1)							//删成空表
	{
		if(p==head)
		{
			head=tail=NULL;
			length=0;
			delete p;
			return 1;
		}
		else
			return 0;					//没找到
	}
	
	else
	{
		Cnode<T> *p1=head,*p2;

		while((p1!=p)&&p1)
		{
			p2=p1;
			p1=p1->next;
			
		}
		
		if(p1==NULL)return 0;				//没找到
			
		else if(p1==tail)					//删除表尾
		{
			p2->next=NULL;
			tail=p2;
		}
		else
		{
			if(p1==head)					//删除表头
				head=p1->next;
			else
				p2->next=p1->next;
		}
		length--;
		delete p1;
		return 1;
	}
	return 0;
}

//判断空否
bool listempty()
{
	if(!length)return 1;
	else return 0;
}

//获得队长
int getlength()
{
	return length;
}

//获得队头地址
Cnode<T> *gethead()
{
	return head;
}

//获得队尾地址
Cnode<T> *gettail()
{
	return tail;
}

//析构函数
virtual ~Clink()
{
	Cnode<T> *p=head;
	
	while(head)
	{
		p=head->next;
		delete head;
		length--;
		head=p;
	}
}

};  //class Clink


///////////////////////////////////////////////////////////////////////////////


//定义顾客队列类（由Clink继承）
class Queue :private Clink<customer>
{
	int busytime;           //工作时间
	int waittime;           //顾客等待时间
	int number;				//顾客数

public:
//构造函数
Queue()
{
	Clink<customer>();
	number=0;
	busytime=0;                 //置零
	waittime=0;					//
}	
	
//加入一位顾客
void enqueue(customer t)
{
	insert(t,NULL);
}


//离开一位顾客
void dequeue()
{
	del(gethead());
}

//从队尾离开一位顾客
void detail()
{
	del(gettail());
}

//获得头顾客信息
customer getfirst()
{
	return gethead()->data;
}

//获得尾顾客信息
customer getlast()
{
	return gettail()->data;
}

//获得队长
int getlength()
{
	return Clink<customer>::getlength();
}

//获得总人数
int getnumber()
{
	return number;
}

//获得工作时间
int getbusytime()
{
	return busytime;
}

//加浪费时间
void addwaste(int t)
{
	waittime+=t;
}

//加工作时间
void addbusy(int t)
{
	busytime+=t;
}

//加顾客数
void addnumber()
{
	number++;
}

//得到浪费时间
int getwaste()
{
	return waittime;
}

//析构函数
virtual ~Queue()
{
	Clink<customer>::~Clink(); 
}

};  //class Queue


/////////////////////////////////////////////////////////////////////////////


//定义事件链表类（由Clink继承）
class Eventlink :private Clink<event>
{

public:

Eventlink()
{
	Clink<event>();
}

//按时间顺序插入
void orderinsert(event t)
{
	if(!getlength())						//原表为空
	{
		insert(t);							//直接插入 
		return ;
	}
	else
	{
		Cnode<event> *p=gethead();					//记录头结点

		while(p->data.occurtime<=t.occurtime)		//找到t的插入位置
		{
			p=p->next;	
			if(p==NULL)
			{
				insert(t);
				return;
			}
		}
		insert(t,p);
		return ;
	}
}

//判断是否为空
bool listempty()
{
	return Clink<event>::listempty();
}

//删除头结点并返回其值
event dehead()
{
	event t=gethead()->data;
	del(gethead());
	return t;
}

//得到头结点的值
int gettime()
{
	if(gethead())return gethead()->data.occurtime;
	else return 0;
}

//得到链表中事件数量
int getlength()
{
	return Clink<event>::getlength();
}

//析构函数
virtual ~Eventlink()
{
	Clink<event>::~Clink();
}

};  //class Link


////////////////////////////////////////////////////////////////////////////


//定义银行类
class Bank
{
	Queue *Q;				//队列数组,也就是窗口数组,动态分配空间
	Eventlink L;			//事件链表
	bool flag1;				//是否允许换队
	bool flag2;				//是否下班就关门
	const int winnum;       //窗口数,也就是队列数

public:
//构造函数
Bank(int n=2,bool f=0,bool h=0):winnum(n)					//参数为创建队列数
{
	flag1=f;
	flag2=h;

	if(n<1)
	{
		cout<<"好歹开一窗口啊!"<<endl;
		exit(0);
	}
	Q=new Queue[winnum+1];								//建立n个窗口

	//初始化事件,插入第一人
	event first;
	L.orderinsert(first);
}


//算法核心,事件驱动部分
int process()
{
	event e=L.dehead();						                //得到事件信息
	event t;
	int i;

	//输出信息
	printf("时%3d,事%2d,队",e.occurtime,e.ntype);
	
	for(i=1;i<=winnum;i++)
			printf("%3d",Q[i].getlength());
	printf("\n");


	if(!e.ntype)									//来人事件
	{
		if(e.occurtime<=MAX_TIME)						//没下班
		//到了下班时间就不再进人，但不赶人
		{			
			t.occurtime=e.occurtime+rnd(0,dti);				//下一位
			if(t.occurtime<=MAX_TIME)
			{
				L.orderinsert(t);					//入事件队
			}
		}

		int min=1;
			
		customer m;								//顾客来了并排队 
		m.arrivaltime=e.occurtime;
		m.duration=rnd(2,dra);

		for(i=2;i<=winnum;i++)							//找人最少的一队
			if(Q[i].getlength()<Q[min].getlength())
				min=i;

		Q[min].enqueue(m);							//进入队中
		
		if(Q[min].getlength()==1)						//不用等，直接接受服务
		{
			t.occurtime=e.occurtime+m.duration;
			t.ntype=min;
			L.orderinsert(t);
		}		
	}
	else										//走人事件
	{
		customer m=Q[e.ntype].getfirst();
		Q[e.ntype].dequeue();

		Q[e.ntype].addbusy(m.duration);						//加工作时间
		Q[e.ntype].addnumber();							//加顾客数

		if(Q[e.ntype].getlength()>0)						//后边人继续接受服务
		{			
			t.ntype=e.ntype;
			t.occurtime=e.occurtime+Q[e.ntype].getfirst().duration;
			L.orderinsert(t);
			Q[e.ntype].addwaste(e.occurtime-Q[e.ntype].getfirst().arrivaltime);
		}
	}

		jump(e.occurtime);							 //换队

	if(flag2)											//若到点就下班
		return e.occurtime;								//则返回正确时间
	else												//否则
		return 0;										//返回零
}

//有人换队
bool jump(int tt)
{
	if(winnum<2)return 0;         //只有一队不会换队
	if(!flag1)return 0;

//从人最多的队尾除一人到人最少队尾
	int min=1,max=1;

	for(int i=2;i<=winnum;i++)	
	{
		if(Q[i].getlength()<Q[min].getlength())min=i;			//找最短队
		if(Q[i].getlength()>Q[max].getlength())max=i;			//找最长队
	}

	if((Q[max].getlength()-Q[min].getlength())<2)return 1;

	else
	{
		customer m=Q[max].getlast();				//长队尾出来
		Q[max].detail();									
		Q[min].enqueue(m);							//进短队

		if(Q[min].getlength()==1)					//不用等，直接接受服务
		{
			event t;
			t.occurtime=tt+m.duration;
			t.ntype=min;
			L.orderinsert(t);
		}
		jump(tt);			//递归调用,至人数接近
	}
	return 1;
}

//事件是否结束
bool listempty()
{
	return L.listempty();
}

//效率评估
void judge()
{
	int number=0,waste=0;

	cout<<endl;
	cout<<"总结:"<<endl;
	cout<<endl;

	//各窗口情况
	for(int i=1;i<=winnum;i++)
	{
		cout<<"  窗口"<<i<<":"<<endl;
		cout<<"	总人数:"<<Q[i].getnumber()<<endl;
		cout<<"	工作时间"<<Q[i].getbusytime()<<endl;

		if(Q[i].getbusytime()<=MAX_TIME/2)					//若工作时间不足一半
			cout<<"		//建议关掉此窗口!!"<<endl;

		number+=Q[i].getnumber();
		waste+=Q[i].getwaste();
	}

	cout<<endl;
	cout<<"  银行:"<<endl;
	cout<<"	平均等待时间:"<<waste/number<<endl;
	if((waste/number)>=dra/2)							//若等待时间超过服务时间一半
		cout<<"		//建议加开窗口!!"<<endl;

	cout<<endl;
	cout<<"本次模拟完成。"<<endl;
	cout<<endl<<endl;
}

//获得当前时间
int gettime()
{
	return L.gettime();
}

//析构函数
virtual ~Bank()
{
	//...
	delete []Q;
}

};//class Bank


////////////////////////////主程序段///////////////////////////////

void main()
{
	int n;
	int t=0;
	char f;
	char h;
	Bank *mybank;

	change();

	srand((unsigned)time(NULL));			//初始化随机数种子

	while(goon())
	{

		cout<<"输入银行窗口数:";
		cin>>n;
		cout<<"是否允许换队(y/n):";
		cin>>f;
		cout<<"是否下班就关门(y/n):";
		cin>>h;

		mybank=new Bank(n,(f!='n'),(h!='n'));			//建立银行

		while(!mybank->listempty())						//判断有业务否
		{
			if(mybank->process()>MAX_TIME)break;		//完成业务
			if(mybank->gettime()-t>200)
			{
				cout<<"暂停(随便输入一键按回车)......";
				cin>>f;
				t+=200;
			}
				
		}

		mybank->judge();
		delete mybank;

	}
	

}

///////////////////////////子函数实现///////////////////////////////

int rnd(int low=2,int high=100)
{
	return (int)(rand()*(high-low)/(double)RAND_MAX)+low; 
}

bool goon()
{
	cout<<"//////////////////////////////////////////"<<endl;
	cout<<"银行开业么?(y/n)";
	char b;
	cin>>b;
	return (b!='n');
}

void change()
{
	cout<<"顾客最大间隔(5):";
	cin>>dti;
	cout<<"最大服务时间(60):";
	cin>>dra;
}


//备注
//1.假设顾客来后一直等，不会走。
//2.允许换队的效果不明显。
//3.duration越长换队效果越明显。
//4.未接受服务者的等待时间没算。
//
//
//
//