1.txt

以队列和栈实现的仿真技术预测理发馆的经营状况

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0

#define INFEASIBLE -1
#define OVERFLOW -2

#define MAXINT 30000
typedef int status;

/************************* 出错信息处理函数定义 ***********************/
 
void ERRORMESSAGE(char *s)                 
{
   cout<<s<<endl;
   exit(1);
} //ERRORMESSAGE

/****************************** 各种类型定义 **************************/ 

typedef struct{
	int OccurTime;//事件发生时刻
	int NType;
	int select;
}ElemType,Event;

typedef struct LNode{ //结点类型
	ElemType data;
	struct LNode *next;
}*Link,*Position;

typedef struct {    //链表类型
	Link head,tail;
	int len;
	Link current;
}LinkList;

void visit(Link p)
{   
    cout<<p->data.OccurTime<<",";
	cout<<p->data.NType<<" ";
}

void InitList(LinkList &L)
{ //建立一个空的单链表
	L.current=new LNode;
	L.current->next=NULL;
	if(!L.current) ERRORMESSAGE("OVERFLOW");
	else
	{
		L.head=L.tail=L.current;
	    L.len=0;
		}
}

status MakeNode(Link &p,ElemType e)
{ //分配由p指向的值为e的结点，并返回OK，若分配失败返回ERROR
	p=new LNode;
	if(!p) return ERROR;
	else
	{   p->data.OccurTime=e.OccurTime;
	    p->data.NType=e.NType;
		p->next=NULL;
	    return OK;
	}    		
}

status FreeNode(Link &p)
{ //释放p所指结点
	delete p;
	return OK;
}
 
void DestroyList(LinkList &L) //销毁单链表L
{Link p,q;
     p=L.head;
     while(p){
	  q=p;
	  p=p->next;
	  FreeNode(q);
     }
    L.head=NULL;
}//destroyList_L

int ListLength(LinkList L)
{  //求表长
	int i=L.len;
	return i;
} //ListLength

status ListEmpty(LinkList L)
{  //判断链表是否为空
	if(ListLength(L)==0) return OK;
	 else return ERROR;
}

void ClearList(LinkList &L)
{Link p;
 while(L.head->next){
 	p=L.head->next;L.head->next=p->next;
    FreeNode(p);}
 L.len=0;
 L.current=L.tail=L.head;
}//clearlist

status DelFirst(LinkList &L,ElemType &e)
{
	Link p;
	if (L.head->next==NULL) return ERROR;
	p=L.head->next;
	e.OccurTime=p->data.OccurTime;
	e.NType=p->data.NType;
	L.head->next=p->next;
	if(L.current==p) L.current=L.head->next;
	if(L.tail==p) L.tail=L.head;
	delete(p);
	L.len--;
	return OK;
}


ElemType GetCurElem(LinkList L)
{  //返回当前指针的数据元素
	ElemType e;
	e=L.current->data;
	return e;
}

status SetCurElem(LinkList &L,ElemType e)
{  //更新当前指针的数据元素
	L.current->data=e;
	return OK;
}

status Prior(LinkList &L)
{  //改变当前指针指向其前驱
	Link p;
	p=L.head;
	if(p==L.current||!L.current) return ERROR;//若当前指针指向头结点，返回ERROR
	while(p->next!=L.current)  p=p->next;
	L.current=p;
	return OK;
}	

status Next(LinkList &L)
{  //改变当前指针指向其后继
	if(!L.current) return ERROR;//L.current为空
    else 
	{  L.current=L.current->next;
	   return OK;
	}
}//next

status LocatePos(LinkList &L,int i)
{  //改变当前指针指向第i个结点                     
	int k=0;
	Link p=L.head;
	if (i>L.len||i<0) return ERROR;
	//i值不合理，当i等于零时L.current指向头结点
	while(k!=i) {p=p->next;k++;}
    L.current=p;
	return OK;
}//Locatepos

status GetElem(LinkList L,int i,ElemType &e)
{  //以e返回L中第i个元素值
	LocatePos(L,i);
	e=GetCurElem(L);
    return OK;
}

status InsAfter(LinkList &L,ElemType e)
{ //若当前指针在链表中，则将数据元素e插入表L中当前指针所指结点之后，
  //并返回OK，否则返回ERROR         
    Link s;
	if(!L.current) return ERROR;
	if(!MakeNode(s,e)) return ERROR;
	s->next=L.current->next;
	L.current->next=s;
	if(L.tail==L.current) L.tail=s;
	L.current=s;
	L.len++;
	return OK;
}

status OrderInsert(LinkList &L,ElemType e)
{ Link p,r,q;
  if(!MakeNode(p,e)) return ERROR;
  q=L.head;
  r=q->next;
  while(r&&(p->data.OccurTime>r->data.OccurTime)) {q=r;r=r->next;}
  if(!r) {
	  L.tail->next=p;
      if(L.current==L.tail) L.current=p;
	  L.tail=p;
  }
  else{p->next=r;
       q->next=p;
       L.current=p;
  }
  L.len++;
  return OK;
}

status DelAfter(LinkList &L,ElemType &e)
{  //若当前指针及其后继在链表中，则删除表L中当前指针所指结点之后的结点，
	//并返回OK，否则返回ERROR 
	Link q;
	if(!(L.current&&L.current->next)) return ERROR;
	q=L.current->next;
	L.current->next=q->next;
	if(L.tail==q) L.tail=L.current;
	e=q->data;
	L.current=L.current->next;
	FreeNode(q);
	L.len--;
	return OK;
}//DelAfter

status ListTraverse(LinkList L,void(*visit)(Link))
{
	if(!L.head->next)return ERROR;
	L.current=L.head->next;
	while(L.current){
		(*visit)(L.current);
		L.current=L.current->next;
	}
	cout<<endl;
	return OK; 
}

typedef struct{
	int ArrivalTime;
	int Duration;
}QElemType;

typedef struct QNode{  //结点类型
 QElemType data;
 struct QNode *next;
}QNode,*QueuePtr;

typedef struct{        //链队列类型
	QueuePtr front;    //队头指针
	QueuePtr rear;     //队尾指针
}LinkQueue;

status InitQueue(LinkQueue &Q)
{//构造一个空队列Q
	Q.front=Q.rear=new QNode;
	if(!Q.front) ERRORMESSAGE("OVERFLOW");  //存储分配失败
	Q.front->next=NULL;
	return OK;
}

status DestroyQueue(LinkQueue &Q)
{//销毁队列Q
	while(Q.front){
		Q.rear=Q.front->next;
		delete(Q.front);
		Q.front=Q.rear;
	}
	return OK;
}

status ClearQueue(LinkQueue &Q)
{//将Q清为空队列
	if(!Q.front) return ERROR;
	while(Q.front->next){
		Q.rear=Q.front->next;
		Q.front->next=Q.rear->next;
		delete(Q.rear);
	}
	Q.rear=Q.front;
	return OK;
}

status QueueEmpty(LinkQueue Q)
{//若队列Q为空队列，则返回TRUE，否则返回FALSE
	if(!Q.front->next) return TRUE;
	return FALSE;
}

int QueueLength(LinkQueue Q)
{//返回Q的元素个数
 int k=0;
 QueuePtr p;
	p=Q.front;
	while(p->next){
		p=p->next;
		++k;
	}
	return k;
}
	
status GetHead(LinkQueue Q,QElemType &e)
{//用e返回Q的对头元素
	if(!Q.front->next) return ERROR;
	e=Q.front->next->data;
	return OK;
}

status EnQueue(LinkQueue &Q,QElemType e)
{//插入元素e为Q的新的队尾元素
    QueuePtr p;
	p=new QNode;
	if(!p) ERRORMESSAGE("OVERFLOW");
	p->data=e; p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
	return OK;
}

status DeQueue(LinkQueue &Q,QElemType &e)
{//若队列不空,则删除Q的队头元素,用e返回其值,并返回OK;否则返回ERROR
   QueuePtr p;	
    if(Q.front==Q.rear) return ERROR;
	p=Q.front->next;
	e=p->data;
	Q.front->next=p->next;
	if(Q.rear==p) Q.rear=Q.front;
	delete(p);
	return OK;
}

status QueueTraverse(LinkQueue Q,status (*visit1)(QueuePtr))
{//输出队列
    QueuePtr p;
    if(Q.front->next==NULL) return ERROR;
	p=Q.front->next;
	while(p){
		(*visit1)(p);
		p=p->next;
	}
	return OK;
}

status visit1(QueuePtr p)          
{                             //输出结点p的元素  
	cout<<p->data.ArrivalTime<<",";
	cout<<p->data.Duration<<",";
	return OK;
}

typedef LinkList EventList;  //事件链表类型，定义为有序链表
EventList ev;                //事件表
Event en;                    //事件
LinkQueue Q1,Q2,Q3;          //等候理发的顾客队列
QElemType customer;  //顾客记录
int t2,t1,Totaltime,CustomerNum,CloseTime,k,CurrentChair;  //累计顾客逗留时间，顾客数
float Totallength;//累计的顾客排队长度
int n1,n2,n3,CurrentChair1,CurrentChair2,CurrentChair3,select;  
double y;

void OpenForDay()
{  //初始化操作
	t1=t2=0;y=0;
	Totaltime=0;
	Totallength=0;
	CustomerNum=0;
	InitList(ev);
	en.OccurTime=0;
	en.NType=0;
	OrderInsert(ev,en);
	InitQueue(Q1);
	InitQueue(Q2);
	InitQueue(Q3);
    cout<<"--------------------------------------------------------------"<<endl;
	cout<<"--------------欢迎进入预测理发馆的经营情况系统----------------"<<endl;
	cout<<"***********************请填写以下信息*************************"<<endl;
	cout<<"理发椅的数量:";
	cin>>k;
	CurrentChair=k;
	cout<<"一级理发椅的数量:";
	cin>>n1;
	CurrentChair1=n1;
	cout<<"二级理发椅的数量:";
	cin>>n2;
	CurrentChair2=n2;
	cout<<"三级理发椅的数量:";
	cin>>n3;
	CurrentChair3=n3;
	cout<<"营业时间:";
	cin>>CloseTime;
	cout<<"--------------------------------------------------------------"<<endl;
	cout<<"--------------------------------------------------------------"<<endl;
    cout<<endl;
}

void CustomerArrived() //处理顾客到达事件
{  
	QElemType e1;
	ElemType e;
	int intertime,R,durtime;
	CustomerNum++;      //累计顾客数
	R=rand();           //产生随机数
	durtime=15+R%50;    //顾客理发所需时间
	intertime=2+R%10;   //下一顾客到达的时间间隔
    select=1+R%3;      
	e.OccurTime=en.OccurTime+intertime;
	if(e.OccurTime>t1) t1=e.OccurTime;select=select;
	e.NType=0;             //进门事件为0类事件
	if(e.OccurTime<CloseTime)   //事件发生时间小于关门时间
		OrderInsert(ev,e);      //进门事件插入事件表
	if(CurrentChair1>0) 
	{   
        e.OccurTime=en.OccurTime+durtime;
        if(e.OccurTime>t1) t1=e.OccurTime;
	    e.NType=1;                 //出门事件为1类事件
		OrderInsert(ev,e);         //出门事件插入事件表
		Totaltime+=durtime;
		y=durtime*(4-select)*0.4;
		CurrentChair1--;
	}
    else                           //无空闲理发椅,顺序排队
	{
		e1.ArrivalTime=en.OccurTime;    //进门时间
		e1.Duration=durtime;            //理发时间
		EnQueue(Q1,e1);                  //因无空椅,顾客入队列
		Totallength+=QueueLength(Q1);	//累计队长
	}
	if(CurrentChair2>0) 
	{   
        e.OccurTime=en.OccurTime+durtime;
        if(e.OccurTime>t1) t1=e.OccurTime;
	    e.NType=1;                 //出门事件为1类事件
		OrderInsert(ev,e);         //出门事件插入事件表
		Totaltime+=durtime;
		y=durtime*(4-select)*0.4;
		CurrentChair2--;
	}
    else                           //无空闲理发椅,顺序排队
	{
		e1.ArrivalTime=en.OccurTime;    //进门时间
		e1.Duration=durtime;            //理发时间
		EnQueue(Q2,e1);                  //因无空椅,顾客入队列
		Totallength+=QueueLength(Q2);	//累计队长
	}
	if(CurrentChair3>0) 
	{   
        e.OccurTime=en.OccurTime+durtime;
        if(e.OccurTime>t1) t1=e.OccurTime;
	    e.NType=1;                 //出门事件为1类事件
		OrderInsert(ev,e);         //出门事件插入事件表
		Totaltime+=durtime;
		y=durtime*(4-select)*0.4;
		CurrentChair3--;
	}
    else                           //无空闲理发椅,顺序排队
	{
		e1.ArrivalTime=en.OccurTime;    //进门时间
		e1.Duration=durtime;            //理发时间
		EnQueue(Q3,e1);                  //因无空椅,顾客入队列
		Totallength+=QueueLength(Q3);	//累计队长
	}
}

void CustomerDeparture()
{
	int Departuretime;
	ElemType e; 
	if(!QueueEmpty(Q1)&&select==1)
	{   
		DeQueue(Q1,customer);                    //队不空,队头顾客退队
		Departuretime=en.OccurTime+customer.Duration;    //计算顾客离开时间
		if(Departuretime>t2) t2=Departuretime;      //计算顾客最晚离开时间
		e.OccurTime=Departuretime;
		e.NType=1;
		OrderInsert(ev,e);                          //出门事件插入事件表
		Totaltime+=Departuretime-customer.ArrivalTime;     //累计时间
		
	}
	else  CurrentChair1++;

	if(!QueueEmpty(Q2)&&select==2)
	{
		DeQueue(Q2,customer);                    //队不空,队头顾客退队
		Departuretime=en.OccurTime+customer.Duration;    //计算顾客离开时间
		if(Departuretime>t2) t2=Departuretime;      //计算顾客最晚离开时间
		e.OccurTime=Departuretime;
		e.NType=1;
		OrderInsert(ev,e);                          //出门事件插入事件表
		Totaltime+=Departuretime-customer.ArrivalTime;     //累计时间
		
	}
	else  CurrentChair2++;

	if(!QueueEmpty(Q3)&&select==3)
	{
		DeQueue(Q3,customer);                    //队不空,队头顾客退队
		Departuretime=en.OccurTime+customer.Duration;    //计算顾客离开时间
		if(Departuretime>t2) t2=Departuretime;      //计算顾客最晚离开时间
		e.OccurTime=Departuretime;
		e.NType=1;
		OrderInsert(ev,e);                          //出门事件插入事件表
		Totaltime+=Departuretime-customer.ArrivalTime;     //累计时间
		
	}
	else  CurrentChair3++;
}