离散xxx.cpp

来自「数据结构中离散事件的实现」· C++ 代码 · 共 342 行

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
typedef struct linkqueue linkqueue;  
typedef int qelemtype; 
typedef struct qnode qnode;
typedef struct event event;
typedef struct eventlist eventlist;
struct event
{
	int occertime;  //事件发生时刻
	int ntype;      //事件类型,0表示到达事件,1至4表示四个窗口的离开事件
	event *next;
};
struct eventlist   //事件表
{
	event *front;   //队头指针 
};
//以下是对队列的一系列操作定义 
struct qnode   
{
	qelemtype data[2]; //data中的两个分别是"到达的时间"和"办理事务所需的时间"
    qnode *next;
};

struct linkqueue   //排队表
{
	qnode *front;  //队头指针
	qnode *rear;   //队尾指针
};

int listempty(eventlist ev) //是空的返回1,不是返回0
{
    if(ev.front==NULL)
		return 1;
	else
		return 0;
};

event *delist(eventlist &ev)  //若队列不空,则删除q的队头元素,用e返回其值.否则打印栈已空
{
	event *e;
	if(ev.front==NULL)
	{	
		printf("事件链表已空!");
		return 0;
	}
	else
	{
		//printf("%d",ev.front->ntype);
		//printf("%d",ev.front->occertime);
		e=ev.front;
        ev.front=ev.front->next;
		return (e);
	}
}

void initqueue(linkqueue &q)  //构造一个空队列q
{
	q.rear=q.front=(qnode*)malloc(sizeof(qnode));
	if(!q.front)
		printf("存储分配失败!");
	else
		q.front->next=NULL;

}

void destroyqueue(linkqueue &q)  //销毁队列q
{
    qnode *tmp;   //***
	while(q.front!=NULL)
	{
		tmp=q.front;
		q.front=q.front->next;
		free(tmp);
	}
}

void enqueue(linkqueue &q,qelemtype e[2])  //插入元素e为q的新的队尾元素   
{
	qnode *p=(qnode *)malloc(sizeof(qnode));
	if(!p)
		printf("存储分配失败!");
	else
	{
		p->data[0]=e[0];
		p->data[1]=e[1];   //?????
		p->next=NULL;
	    q.rear->next=p;//***
		q.rear=p;
	}
}

void dequeue(linkqueue &q,qelemtype e[2])  //若队列不空,则删除q的队头元素,用e返回其值.否则打印栈已空
{//***传地址,要不然改不了
	qnode *p;
	if(q.front==q.rear)
		printf("栈已空!");
	else
	{
		p=q.front->next;
		e[0]=p->data[0];
	    e[1]=p->data[1];
		q.front=p;
	}
}

int queueempty(linkqueue &q)  //若队列q为空队列,则返回1,否则返回0
{
	if(q.front->next==NULL)
		return 1;//****
	else
		return 0;

}


int queuelength(linkqueue q) //返回q的元素个数,即为队列的长度
{
	int length=0;
	qnode *tmp=q.front;
	while(tmp!=q.rear)
	{
		tmp=tmp->next;
		length++;
	}
	return length;
}


void gethead(linkqueue q,int a[2])  //若队列不空,则返回q的队头元素,否则返回0
{
	if(q.front->next==NULL)
	{
		printf("队列为空!");
	}
	else
	{
		a[0]=q.front->data[0];
		a[1]=q.front->data[1];
	}
}

// 以上是对队列的一系列基本操作的定义




eventlist ev;    //事件表,用来记录发生的事,它是由en按occertime的大小组成的
linkqueue q[5];  //4个客户队列,它是由customer[2]组成的			//***
int customer[2];   //客户记录,要有两个元素,一个是记录到达时间arrivaltime,一个是记录办理事务所需的时间duration
int totaltime;     //累计客户逗留时间
int customernum;   //客户数
int closetime=100;
int durtime;

int minimum (linkqueue q[5])//***
{
	int i, min,minlen;
    min=1;
	minlen=queuelength(q[1]);
	for(i=2;i<=4;i++)
	{
		if(queuelength(q[i])<minlen)
		{
			minlen=queuelength(q[i]);
			min=i;
		}
	}
	return min;
}


/*int random(int dtime,int intertime)   //它是可以生成随机数的函数
{
	printf("请给出随机的两个时间:\n");
    printf("办理事务所需的时间durtime: ");
	scanf("%d",&dtime);
	printf("离下一个客户的到达时间intertime: ");
	scanf("%d",&intertime);
}*/
int random1(int dtime)   //它是可以生成随机数的函数
{
	printf("请给出随机的两个时间:\n");
    printf("办理事务所需的时间durtime: ");
	//scanf("%d",&dtime);
	dtime=rand()%15+5;
	printf("%d\n",dtime);
	return dtime;
}
int random2(int intertime)   //它是可以生成随机数的函数
{
	printf("离下一个客户的到达时间intertime: ");
	//scanf("%d",&intertime);
	intertime=rand()%5+3;
	printf("%d\n",intertime);
	return intertime;
}

int cmp(event *a,event *b)  //依事件a,b的发生时间的先后来返回-1,0,1.  
{
	if(a->occertime>b->occertime)
	{
		return 1;
	}
	else if(a->occertime<b->occertime)
	{
		return -1;
	}
	else 
	{
		return 0;
	}
}

void orderinsert(eventlist &ev, int a[2])  //把a[2]插入事件表ev中,并且要按照e.occertime的先后顺序来排列.注意,ev只是一个活链表 ??????
{
	event *e=(event *)malloc(sizeof(event));
	event *p1,*p2;
	e->occertime=a[0];
	e->ntype=a[1];
	if(listempty(ev))
	{
		ev.front=e;
		ev.front->next=NULL;
	}
	else
	{
		if(cmp(ev.front,e)!=-1)  //比第一件事发生的还先//***
		{
			e->next=ev.front;
			ev.front=e;
		}
		else   
		{
            // printf("\nna er\n");
			for(p2=ev.front;p2->next!=NULL;p2=p2->next);
			if(cmp(p2,e)!=1)    //比最后一件事发生的还迟
			{
				p2->next=e;
				e->next=NULL;
				//printf("zhe er\n");
            }  
			else
			{
				for(p2=p1=ev.front;p1!=NULL;p2=p1,p1=p2->next)  //处于中间位置//***
				{
					if(cmp(p1,e)!=-1)//***
					{
						e->next=p1;
			            p2->next=e;
			            break;
					}
 
				}
			}
		}
	}
}


void initlist(eventlist q)  //构造一个空队列q
{
	q.front =NULL;//***
}

void openforday()   //初始化操作
{
	int i;
	totaltime=0;    //初始化累计时间
	customernum=0;  //初始化客户数
	initlist(ev);   //初始化事件链表为空表
    int	a[2]={0,0};     //设第一个客户的到达事件 a.occertime=0;  a.ntype=0;
    orderinsert(ev,a);  //插入事件表
	for(i=1;i<=4;i++)
		initqueue(q[i]);   //置空队列,初始化队列为空
}

void customerarrived(event *en)   //处理客户到达事件,en.ntype=0
{
	int t,i;                      
    int a[2];                    //相当于int durtime,intertime;   
	++customernum;
    a[0]=random1(a[0]);        //生成随机数---办理事务所需的时间durtime,    它和下一步相加相当于random(durtime,9intertime)
	a[1]=random2(a[1]);        //生成随机数---离下一个客户的到达时间intertime.
	t=en->occertime+a[1];      //下一个客户到达时刻
	if(t<closetime)
	{
	    int	a1[2]={t,0};  //这里的a1[2]是用来插入事件表的下一个客户到达事件,t为他的发生事件,0表示是到达事件 
		//printf("nextcustomerarrived"); 
	    orderinsert(ev,a1);
	}
	i=minimum(q);   //求长度最短的队列,返回它的组数
	int a2[2]={en->occertime,a[0]};  //a2为要插入队列的用户,t表示到达时间,a[0]表示处理用时
	printf("A customer arrived at %d and go to queue %d\n",en->occertime,i);
	enqueue(q[i],a2);   //把a2插入q[i]中
	if(queuelength(q[i])==1)     //表明为队列有且只有一个客户在 
	{
        int	a3[2]={en->occertime+a[0],i};
	    orderinsert(ev,a3);   //设定第i队列的一个离开事件并插入事件表 
	}
}

void customerdeparture(event *en)    //处理客户离开事件,en.type>0
{
	int i;   //组数
	i=en->ntype;  
	dequeue(q[i],customer);    //删除第i个队列的排头客户
    totaltime+=en->occertime-customer[0]; //累计客户逗留时间,customer[0]是用户到达时间arrivaltime
	printf("A customer departure at %d from queue %d\n",en->occertime,i);
    if(!queueempty(q[i]))      //如果第i队列不为空,设定一个离开事件并插入事件表
	{
		gethead(q[i],customer);
		int	a[2]={en->occertime+customer[1],i};
	    orderinsert(ev, a);
	}  
}


void main()
{
	event *p;
	openforday();  //初始化
	while(!listempty(ev))  //只要事件列表不空就继续循环
	{
		p=delist(ev);
		if(p->ntype==0)
			customerarrived(p); //处理客户到达事件
		else                       
			customerdeparture(p);     //处理客户离开事件 
	}
	  //计算并输出平均逗留时间
	printf("the average time is %0.3f\n",(float)totaltime/customernum);
}