linkqueue.cpp

校园导游参考 运用DIJKSTRA等算法实现

//------------基本操作的函数描述----------------------------

#include <stdio.h>      //引用标准头文件
#include <malloc.h>     //引用标准头文件
#include <stdlib.h>     //引用标准头文件
#include "Queue.h"      //引用自定义头文件

//  //  //  //  // //  //  // // // // // // // // // //  //  //

Status InitQueue(LinkQueue &Q)
{//构造一个空队列Q
	Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
	if(!Q.front)
		exit(ERROR);//分配空间失败
	Q.front->next=NULL;
	return OK;
}//InitQueue

//  //  //  //  // //  //  // // // // // // // // // //  //  //

Status DestroyQueue(LinkQueue &Q)
{//销毁队列Q
	while(Q.front){//销毁队列中所有节点
		Q.rear=Q.front->next;
		free(Q.front);
		Q.front=Q.rear;
	}
	return OK;
}//DestroyQueue

//  //  //  //  // //  //  // // // // // // // // // //  //  //

Status ClearQueue(LinkQueue &Q)
{//将队列清空
	Q.rear=Q.front;
	Q.front->next=NULL;
	return OK;
}//ClearQueue

//  //  //  //  // //  //  // // // // // // // // // //  //  //

Status QueueEmpty(LinkQueue Q)
{//判断队列是否为空
	if(Q.rear==Q.front&&Q.front->next==NULL)
		return TRUE;
	else
		return FALSE;
}//QueueEmpty

//  //  //  //  // //  //  // // // // // // // // // //  //  //

int QueueLength(LinkQueue Q)
{//返回Q的元素个数，即队列的长度
	int i=0;//i为计数器
    QueuePtr  q;

	q=Q.front;

	while(q!=Q.rear){
		q=q->next;
		i++;
	}

	return i;
}//QueueLength

//  //  //  //  // //  //  // // // // // // // // // //  //  //

Status GetHead(LinkQueue Q,QElemType &e)
{ //若队不空则用e返回队头元素，并返回OK；否则返回ERROR
	if(QueueEmpty(Q))
		return ERROR;

	QueuePtr  q;
	q=Q.front->next;
	e=q->data;
	return OK;
}// GetHead

//  //  //  //  // //  //  // // // // // // // // // //  //  //

Status EnQueue(LinkQueue &Q,QElemType e)
{  //插入元素e为Q的新的队尾元素
	QueuePtr  q=(QueuePtr)malloc(sizeof(QNode));
    if(!q)  exit(0);
	q->data=e;
	Q.rear->next=q;
	Q.rear=q;
	Q.rear->next=NULL;
	return OK;
}//EnQueue

//  //  //  //  // //  //  // // // // // // // // // //  //  //

Status DeQueue(LinkQueue &Q,QElemType &e)
{  //若队不空，则删除队头元素，用e返回其值，并返回OK
   //否则返回ERROR
	if(QueueEmpty(Q))  return ERROR;

	QueuePtr  q;
	q=Q.front->next;
	e=q->data;
	//if( QueueLength(Q)==1 ){//若队列只有一个元素
	Q.front->next=q->next;
	if(Q.rear==q)   Q.rear=Q.front;

	free(q);
	return OK;
}//DeQueue()

//  //  //  //  // //  //  // // // // // // // // // //  //  //

Status QueueTraverse(LinkQueue Q)
{  //打印队列中的数据元素
	QueuePtr  q=Q.front->next;
	while(q!=NULL){
		printf(" %d",q->data);
		q=q->next;
	}
	return OK;
}//QueueTraverse

//  //  //  //  // //  //  // // // // // // // // // //  //  //