链队列的实现及应用

  • 本文记录单链队列(队列的链式存储结构)的数据结构定义及基本操作的算法描述,并对算法进行简单应用。
  • 采用C语言实现,其中应用了少数C++特性,比如引用等。


源程序

//LinkQueue.cpp
#include <stdio.h>
#include <stdlib.h>

#define MAXQSIZE 5
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2

typedef int Status;
typedef int 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=(QueuePtr)malloc(sizeof(QNode));
	if(!Q.front)
		exit(OVERFLOW);
	Q.front->next=NULL;
	return OK;
}

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

//把Q清为空队列
Status ClearQueue(LinkQueue &Q)
{
	QueuePtr p,q;
	Q.rear=Q.front;
	p=Q.front->next;
	Q.front->next=NULL;
	while(p)
	{
		q=p;
		p=p->next;
		free(q);
	}
	return OK;
}

//若队列Q为空队列,则返回TRUE,否则返回FALSE
Status QueueEmpty(LinkQueue Q)
{
	if(Q.front==Q.rear)
		return TRUE;
	else
		return ERROR;
}

//返回Q的元素个数,即队列的长度
int QueueLength(LinkQueue Q)
{
	int i=0;
	QueuePtr p;
	p=Q.front;
	while(Q.rear!=p)
	{
		i++;
		p=p->next;
	}
	return i;
}

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

//插入元素e作为新的队尾元素
Status EnQueue(LinkQueue &Q,QElemType e)
{
	QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
	if(!p)
		exit(OVERFLOW);
	p->data=e;
	p->next=NULL;
	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;
	free(p);
	return OK;
}

//从队头到队尾依次对队列Q中每个元素调用函数visit()。一旦visit失败,则操作失败
Status QueueTraverse(LinkQueue Q,void (*visit)(QElemType))
{
	QueuePtr p;
	p=Q.front->next;
	while(p)
	{
		visit(p->data);
		p=p->next;
	}
	printf("\n");
	return OK;
}

void visit(QElemType i)
{
	printf("%d ",i);
}

int main()
{
	int i;
	QElemType d;
	LinkQueue q;
	i=InitQueue(q);
	if(i)
		printf("成功地构造了一个空队列!\n");
	printf("初始化队列后,队列空否?%d(1:空 0:否),",QueueEmpty(q));
	printf("队列长度为:%d\n",QueueLength(q));
	EnQueue(q,-5);
	EnQueue(q,5);
	EnQueue(q,10);
	printf("插入3个元素(-5,5,10)后,队列长度为:%d\n",QueueLength(q));
	printf("现在队列空否?%d(1:空 0:否)\n",QueueEmpty(q));
	printf("现在队列中的元素为:");
	QueueTraverse(q,visit);
	i=GetHead(q,d);
	if(i==OK)
		printf("队头元素为:%d\n",d);
	DeQueue(q,d);
	printf("删除了队头元素:%d\n",d);
	i=GetHead(q,d);
	if(i==OK)
		printf("新的队头元素为:%d\n",d);
	ClearQueue(q);
	printf("清空队列后,q.front=%u q.rear=%u q.front->next=%u\n",q.front,q.rear,q.front->next);
	DestroyQueue(q);
	printf("销毁队列后,q.front=%u q.rear=%u\n",q.front,q.rear);
    return 0;
}


运行结果

成功地构造了一个空队列!
初始化队列后,队列空否?1(1:空 0:否),队列长度为:0
插入3个元素(-5,5,10)后,队列长度为:3
现在队列空否?0(1:空 0:否)
现在队列中的元素为:-5 5 10
队头元素为:-5
删除了队头元素:-5
新的队头元素为:5
清空队列后,q.front=10555928 q.rear=10555928 q.front->next=0
销毁队列后,q.front=0 q.rear=0

热门相关:帝少的专属:小甜心,太缠人   薄先生,情不由己   时间都知道(唐嫣、窦骁、杨烁主演)   天启预报   第一神算:纨绔大小姐