queue.h

理发馆问题。基于vc的模拟试验.包括试验设计文稿。

//--------------------定义队列元素类型（一个元素记录一个顾客的相关信息）--------------------
typedef struct{
	int ArrivalTime;   //顾客进门时间
	int Duration;      //顾客理发时间
}QElemType;

//--------------------定义队列节点类型（一个节点对应于一个队列中顾客）---------------------
typedef struct QNode{
 QElemType data;       //当前顾客信息
 struct QNode *next;   //下一个顾客指针
}QNode,*QueuePtr;

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

//--------------------构造一个空链队列Q（即摆好椅子，但还没有顾客）------------------------
status InitQueue(LinkQueue &Q)
{
	Q.front=Q.rear=new QNode;
	if(!Q.front || !Q.rear) ERRORMESSAGE("初始化队列失败");
	Q.front->next=NULL;
	return OK;
}

//--------------------销毁队列Q（即将椅子全部搬走，顾客无法入座）--------------------------
//销毁队列的过程即删除所有节点，包括队头、队尾的过程
status DestroyQueue(LinkQueue &Q)
{
	while(Q.front){
		Q.rear=Q.front->next;  //队尾存储队列下一个顾客信息
		delete(Q.front);       //删除队头信息，即当前顾客离开队列
		Q.front=Q.rear;        //队头指向队尾同一个顾客
	}
	return OK;
}

//--------------------清空队列Q（即椅子不动，但将所有顾客赶走）---------------------------
//清空队列的过程即删除其余节点，但保留队头、队尾的过程
//注意清空队列和销毁队列在作循环判断时的不同之处：
//销毁队列时：while(Q.front)；
//清空队列时：while(Q.front->next)，并且循环结束后Q.rear=Q.front;
status ClearQueue(LinkQueue &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;                    //将队头值null赋予队尾
	return OK;
}

//--------------------判断当前队列Q是否为空队列，是返回true，否返回false------------------
status QueueEmpty(LinkQueue Q)
{
	if(!Q.front->next) return TRUE;     //空队列只有队头、队尾，如判断队头无下继节点信息则可认为当前队列为空
	return FALSE;
}

//--------------------返回队列Q的元素个数（即顾客人数）-----------------------------------
int QueueLength(LinkQueue Q)
{
 int k=0;
 QueuePtr p;
	p=Q.front;
	while(p->next){
		p=p->next;
		++k;
	}
	return k;
}
	
//--------------------返回队列Q的第一个顾客信息，存储在e中（注意队头、队尾不存储顾客信息，仅作为队列指针）-----------
status GetHead(LinkQueue Q,QElemType &e)
{
	if(!Q.front->next) return ERROR;
	e=Q.front->next->data;
	return OK;
}

//--------------------插入元素e为Q的新的队尾元素（即新到顾客e）---------------------------
status EnQueue(LinkQueue &Q,QElemType e)
{
    QueuePtr p;
	p=new QNode;
	if(!p) ERRORMESSAGE("安排新顾客入座理发时发生错误");
	p->data=e; p->next=NULL;   //初始化新到顾客，值赋为e，下位指针赋为空
	Q.rear->next=p;            //新队尾指向新到顾客
	Q.rear=p;
	return OK;
}

//--------------------若队列不空,则删除Q的队头元素,用e返回其值,并返回OK;否则返回ERROR---------------------------
status DeQueue(LinkQueue &Q,QElemType &e)
{
    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;
}

//--------------------输出结点p（即当前顾客）的信息--------------------------------
status visit1(QueuePtr p)          
{
	cout<<p->data.ArrivalTime<<",";
	cout<<p->data.Duration<<",";
	return OK;
}

//--------------------利用visit1函数输出队列每个元素信息---------------------------
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;
}