1.cpp

利用数据结构的查找做的理发馆的排队

#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include<process.h>
#include<string.h>
/************************* 出错信息处理函数定义 ***********************/
 
void ERRORMESSAGE(char *s)                 
{
   cout<<s<<endl;
   exit(1);
} //0MESSAGE


/****************************** 各种类型定义 **************************/
 #define MAXINT 30000
typedef int status; 

typedef struct{
	int OccurTime;//事件发生时刻
	int NType;
}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的结点，并返回1，若分配失败返回0
	p=new LNode;
	if(!p) return 0;
	else
	{   p->data.OccurTime=e.OccurTime;
	    p->data.NType=e.NType;
		p->next=NULL;
	    return 1;
	}    		
}

status FreeNode(Link &p)
{ //释放p所指结点
	delete p;
	return 1;
}
 
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 1;
	 else return 0;
}

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 0;
 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 1;
}


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

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

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

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

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

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

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

status OrderInsert(LinkList &L,ElemType e)
{ Link p,r,q;
  if(!MakeNode(p,e)) return 0;
  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 1;
}

status DelAfter(LinkList &L,ElemType &e)
{  //若当前指针及其后继在链表中，则删除表L中当前指针所指结点之后的结点，
	//并返回1，否则返回0 
	Link q;
	if(!(L.current&&L.current->next)) return 0;
	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 1;
}//DelAfter

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


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

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

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

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

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

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

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

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 0;
	e=Q.front->next->data;
	return 1;
}

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

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

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

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

typedef LinkList EventList;  //事件链表类型，定义为有序链表
EventList ev;                //事件表
Event en;                    //事件
LinkQueue Q;          //等候理发的顾客队列
QElemType customer;  //顾客记录
int t2,t1,Totaltime,CustomerNum,CloseTime,k,CurrentChair;  //累计顾客逗留时间，顾客数
float Totallength;
void OpenForDay()
{  //初始化操作
	t1=t2=0;
	Totaltime=0;
	Totallength=0;
	CustomerNum=0;
	InitList(ev);
	en.OccurTime=0;
	en.NType=0;
	OrderInsert(ev,en);
	InitQueue(Q);
	cout<<"Input the chairs' number: ";
	cin>>k;
	CurrentChair=k;
	cout<<"Input CloseTime:";
	cin>>CloseTime;
	cout<<endl;
}

void CustomerArrived()
{  //处理顾客到达事件
	QElemType e1;
	ElemType e;
	int durtime,intertime,R;
	CustomerNum++;
	R=rand();
	durtime=15+R%50;
	intertime=2+R%10;
/*	cout<<"Input durtime: ";
	cin>>durtime;
	cout<<"Input intertime: ";
	cin>>intertime;
	cout<<endl;*/
	e.OccurTime=en.OccurTime+intertime;
	if(e.OccurTime>t1) t1=e.OccurTime;
	e.NType=0;
	if(e.OccurTime<CloseTime) 
		OrderInsert(ev,e);
	if(CurrentChair>0) 
	{
        e.OccurTime=en.OccurTime+durtime;
        if(e.OccurTime>t1) t1=e.OccurTime;
	    e.NType=1;
		OrderInsert(ev,e);
		Totaltime+=durtime;
		CurrentChair--;
	}
    else
	{
		e1.ArrivalTime=en.OccurTime;
		e1.Duration=durtime;
		EnQueue(Q,e1);
		Totallength+=QueueLength(Q);	//累计队长
	}
}

void CustomerDeparture()
{
	int Departuretime;
	ElemType e; 
	if(!QueueEmpty(Q))
	{
		DeQueue(Q,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  CurrentChair++;
}



void main()
{
    int t=0;
	OpenForDay();
	while(!ListEmpty(ev))
	{
		DelFirst(ev,en);
		if(en.NType==0) CustomerArrived();
		else CustomerDeparture();
	}
	cout<<"Number of customer "<<CustomerNum<<endl;
	cout<<"Average time "<<setprecision(3)<<Totaltime/CustomerNum<<endl;
    cout<<"Average queuelength "<<Totallength/CustomerNum<<endl;  
	t=(t1>=t2)?t1:t2;
	cout<<"Addition time "<<t-CloseTime<<endl;

}