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

男娘i 2022-04-13 04:14 207阅读 0赞

#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;
    }