数据结构——离散事件模拟实验

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

typedef struct
{
	int OccurTime; //事件发生时刻;
	int NType;     //0表示到达事件，1~4表示四个窗口的离开事件
}Event;            //事件类型，有序链表LinkList的数据元素类型

typedef struct ENode  //事件链表类型
{
	Event data;
	struct ENode *next;
}ENode,*EventList;

typedef struct
{
	int ArrivalTime;  //到达银行时间
	int Duration;     //办理事务所需时间
}QElemType;           //队列的数据元素类型

typedef struct QNode
{
	QElemType data;
	struct QNode *next;
}QNode,*QueuePtr;

typedef struct
{
	QueuePtr front;  //队头指针
	QueuePtr rear;   //队尾指针
	int num;
}LinkQueue;

int TotalTime;     //记录客户总逗留时间
int CustomerNum;   //记录总的客户
int CloseTime=9;  //银行关门时间初始化为22点

//函数原型声明: 
void InitList(EventList &ev);                       //构造空表
void InitQueue(LinkQueue &Q);                       //构造空队列
void OpenForDay(EventList &ev,LinkQueue Q[5]);      //初始化操作
void CustomerArrived(EventList &ev,LinkQueue Q[5],Event en); //客户到达函数
int Minimum(LinkQueue Q[5]);                        //找几个中队列人数最少的那队
int ListEmpty(EventList ev);                        //判断事件表是否为空；
void Delfirst(EventList &ev,Event &p);
void Bank_Simulation(EventList &ev,LinkQueue Q[5]);
void CustomerDeparture(EventList &ev,LinkQueue Q[5],Event en);
void DelQueue(LinkQueue &Q,QElemType &customer); //删除队头元素
int QueueEmpty(LinkQueue Q);                     //判断空队列函数
void GetHead(LinkQueue Q,QElemType &customer);   //取队头元素
void EnQueue(LinkQueue &Q,int n,int m);          //在队尾插入元素
int QueueLength(LinkQueue Q);                    //求队列长度
void OrderInsert(EventList &ev,Event en);
void show(EventList ev);
void ShowQ(LinkQueue Q);

//主函数
int main()
{
    EventList ev;
	LinkQueue Q[5];
	//******************
	Bank_Simulation(ev,Q);
	return 0;
}

//*
void Bank_Simulation(EventList &ev,LinkQueue Q[5])
{
    //*****************
	int n=5;
	OpenForDay(ev,Q);   //初始化
	Event p;
	while(ListEmpty(ev)!=1)   //条件事件表不空
	{
		printf("*********************************\n");
		Delfirst(ev,p);                            //删除第一个事件，信息存放在p中
//ok	printf("1=%d  ",p.NType);	printf("2=%d\n",p.OccurTime);
		if(p.NType==0)
		{
			CustomerArrived(ev,Q,p);               //=0,则处理客户到来事件
		}
		else CustomerDeparture(ev,Q,p);            //>0则处理客户离开事件
		show(ev);
		printf("[到银行的时间.办事时间]:\n");
		for(int j=1;j<=4;j++)
		{
			ShowQ(Q[j]);		
		}
	}
	printf("客户总数: %d\n",CustomerNum);
	printf("客户逗留总时间: %d\n",TotalTime);
	printf("平均时间: %f\n",(float)TotalTime/CustomerNum);
}

//处理客户到达事件,en.NType=0;
void CustomerArrived(EventList &ev,LinkQueue Q[5],Event en)
{ 
	srand(time(0));
	int durtime;                 //办理业务的时间
	int intertime;               //下一位客户的间隔时间
	int i; //数量最少的队列
	Event x,y;
	CustomerNum++;               //客户总数+1;
//test	printf("客户总数:%d\n",CustomerNum);
	durtime=rand()%5+1;        //范围在1~100之间
	printf("业务时间:%d\n",durtime);
	intertime=rand()%2+1;
	printf("间隔时间:%d\n",intertime);
	x.OccurTime=en.OccurTime+intertime;    //下一个用户到达的时间
	printf("下一个用户到达的时间:%d\n",x.OccurTime);
	x.NType=0;
	if(x.OccurTime<CloseTime)
	{
		OrderInsert(ev,x);//插入事件表
	}
	i=Minimum(Q);                //求长度最短队列
	EnQueue(Q[i],en.OccurTime,durtime);  //入队
	y.NType=i;
//	printf("哪一个队列=%d\n",y.NType);
	y.OccurTime=en.OccurTime+durtime;
	printf("用户离开时间=%d\n",y.OccurTime);
//	printf("Q[i].num=%d\n",Q[i].num);
	if(Q[i].num==1)
	{
		OrderInsert(ev,y);//设定第i队列的一个离开事件并插入事件表
	}
	return ;
}


//处理客户离开事件 en.NType>0
void CustomerDeparture(EventList &ev,LinkQueue Q[5],Event p)
{
//	printf("p.NType=%d\n",p.NType);
	int i=p.NType;
	Event x;
	QElemType customer;
	DelQueue(Q[i],customer);  //删除第i队列的排头客户
	TotalTime+=p.OccurTime-customer.ArrivalTime;  //累计客户逗留时间
//	printf("客户总逗留时间:%d\n",TotalTime);
	if(Q[i].front!=Q[i].rear)   //若队列不空，设置一个新的队头客户离开事件
	{
		GetHead(Q[i],customer);
		x.NType=i;
		x.OccurTime=p.OccurTime+customer.Duration;
		printf("%d %d\n",x.NType,x.OccurTime);
		OrderInsert(ev,x);
	}
}

//取某一队的队头元素函数
void GetHead(LinkQueue Q,QElemType &customer)
{
	customer=Q.rear->data;
}

//删除队头元素
void DelQueue(LinkQueue &Q,QElemType &customer)
{
	if(Q.front==Q.rear)
	{
		printf("该队列为空!\n");
		return;
	}
	QueuePtr p;
	p=Q.front->next;
	customer=p->data;
	Q.front->next=p->next;
	Q.num--;
	if(Q.rear==p) Q.rear=Q.front;
	free(p);
}


//删除事件表中第一个事件，信息存在p中
void Delfirst(EventList &ev,Event &p)
{
	if(ev->next==NULL) return;
	else
	{
		p=ev->next->data;
		ev->next=ev->next->next;
	}
}



//寻找人数最少队列
int Minimum(LinkQueue Q[5])
{
	int i;
    int min=1;
    for(i=1;i<=4;i++)
	{
		if(Q[min].num>Q[i].num)
		{
			min=i;
		}
	}
	return min;
}

//构造空表函数ok1
void InitList(EventList &ev)
{
	EventList en;
	ev=(EventList)malloc(sizeof(ENode));
	if(ev==NULL)
	{
		printf("构建空表失败!");
		exit(0);
	}
	ev->next=NULL;
	en=(EventList)malloc(sizeof(ENode));
	en->data.NType=0;
	en->data.OccurTime=0;
	en->next=ev->next;
	ev->next=en;	
}

//初始化函数ok2
void OpenForDay(EventList &ev,LinkQueue Q[5]) 
{
	int i;
	Event en;
	TotalTime=0;  //初始化客户总逗留时间为0；
	CustomerNum=0; //初始化总的客户数量为0；
	InitList(ev); //构建空表；
	ev->data.OccurTime=0; //设定第一个客户到达事件
	ev->data.NType=0;
	en.NType=0;
	en.OccurTime=0;
	OrderInsert(ev,en);
    for(i=1;i<=4;i++)  //构造空队列
	{
		InitQueue(Q[i]);
//test		ShowQ(Q[i]);
	}
}

//在事件表插入元素ok3
void OrderInsert(EventList &ev,Event en)
{
	EventList p;
  	EventList q=ev;
	p=(EventList)malloc(sizeof(ENode));
	p->data.NType=en.NType;
	p->data.OccurTime=en.OccurTime;
	while(q->next!=NULL)
	{
		if(q->next->data.OccurTime==0 ||en.OccurTime<q->next->data.OccurTime)
		{
            p->next=q->next;
			q->next=p;
			return;
		}
		else
		{
			q=q->next;
		}
	}
	return;
}

//展示事件表函数ok4
void show(EventList ev)
{
	while(ev->next->next)
	{
		printf("事件发生时间:%d",ev->next->data.OccurTime);
		printf("  事件类型:%d\n",ev->next->data.NType);
		ev=ev->next;
	}
}

//判断事件表是否为空ok5
int ListEmpty(EventList ev)
{
	if(ev->next->next==NULL) return 1;
	else return 0;
}

//构造空队列函数ok6
void InitQueue(LinkQueue &Q)
{
	Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
	if(Q.front==NULL)
	{
		printf("构造空队列失败!\n");
		exit(0);
	}
	Q.front->next=NULL;
	Q.rear->next=Q.front->next;
	Q.num=0;
}

//判断队列是否为空ok7
int QueueEmpty(LinkQueue Q)
{
	if(Q.front==Q.rear) return 1;
	else return 0;
}

//在某一队中队尾插入元素ok8
void EnQueue(LinkQueue &Q,int n,int m)
{
	QueuePtr p;
	p=(QueuePtr)malloc(sizeof(QNode));
	if(!p)
	{
		printf("分配内存失败!");
		exit(0);
	}
	p->data.ArrivalTime=n;
	p->data.Duration=m;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
	Q.num++;
}

//展示队列函数ok9
void ShowQ(LinkQueue Q)
{
	
	if(Q.front==Q.rear)
	{
		printf("打印队列为空!\n");
		return;
	}
	do
	{
		printf("[%d:",Q.front->next->data.ArrivalTime);
		printf("%d]    ",Q.front->next->data.Duration);
		Q.front=Q.front->next;
	}while(Q.rear->next!=Q.front->next);
	printf("\n");
	return;
}