队列的动态链式存储实现—C语言

/***
*ElemType.h - ElemType的定义
*
****/

#ifndef ELEMTYPE_H
#define ELEMTYPE_H

typedef int ElemType;

int  compare(ElemType x, ElemType y);
void visit(ElemType e);

#endif /* ELEMTYPE_H */

/***
*DynaLnkQueue.h - 动态链式队列的定义
*
****/

#if !defined(DYNALNKQUEUE_H)
#define DYNALNKQUEUE_H

#include "ElemType.h"

/*------------------------------------------------------------
// 链式队列结构的定义
------------------------------------------------------------*/

typedef struct Node
{
	ElemType data;				// 元素数据
	struct Node *next;			// 链式队列中结点元素的指针
} QNode, *QueuePtr;

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

/*------------------------------------------------------------
// 链式队列的基本操作
------------------------------------------------------------*/

bool InitQueue(LinkQueue *Q);
void DestroyQueue(LinkQueue *Q);
bool QueueEmpty(LinkQueue Q);
int  QueueLength(LinkQueue Q);
bool GetHead(LinkQueue Q, ElemType *e);
void QueueTraverse(LinkQueue Q, void (*fp)(ElemType));
void ClearQueue(LinkQueue *Q);
bool EnQueue(LinkQueue *Q, ElemType e);
bool DeQueue(LinkQueue *Q, ElemType *e);

#endif

#include <stdio.h>
#include <stdlib.h>
#include "DynaLnkQueue.h"

int main()
{
	LinkQueue *Q;
	ElemType e=3;
	 InitQueue(&Q);
	DestroyQueue(&Q);
	QueueEmpty(&Q);
	QueueLength(&Q);
	GetHead(&Q,e);
	QueueTraverse(&Q, visit(e));
	ClearQueue(&Q);
	EnQueue(&Q,e);
	DeQueue(&Q,&e);
	system("pause");
	return true;
}

/***
*ElemType.cpp - ElemType的实现
*
****/

#include <stdio.h>
#include "ElemType.h"

int compare(ElemType x, ElemType y)
{
	return(x-y);
}

void visit(ElemType e)
{
	printf("%dn", e);
}

/***
*DynaLnkQueue.cpp - 动态链式队列，即队列的动态链式存储实现
*
*
*题目：实验4 队列的动态链式存储实现
*

*
****/

#include <stdlib.h>
#include <malloc.h>
#include <memory.h>
#include <assert.h>
#include "DynaLnkQueue.h"

/*------------------------------------------------------------
操作目的：	初始化队列
初始条件：	无
操作结果：	构造一个空的队列
函数参数：
		LinkQueue *Q	待初始化的队列
返回值：
		bool			操作是否成功
------------------------------------------------------------*/
bool InitQueue(LinkQueue *Q)//初始化带头结点的队列
{
	Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
	if (!Q->front)
	{
		return false;
	}
    Q->front->next = NULL;
	return true;

}

/*------------------------------------------------------------
操作目的：	销毁队列
初始条件：	队列Q已存在
操作结果：	销毁队列Q
函数参数：
		LinkQueue *Q	待销毁的队列
返回值：
		无
------------------------------------------------------------*/
void DestroyQueue(LinkQueue *Q)
{
	while(Q->front)
	{
		Q->rear = Q->front->next;
		free(Q->front);
		Q->front = Q->rear;
	}

}

/*------------------------------------------------------------
操作目的：	判断队列是否为空
初始条件：	队列Q已存在
操作结果：	若Q为空队列，则返回true，否则返回false
函数参数：
		LinkQueue Q		待判断的队列
返回值：
		bool			是否为空
------------------------------------------------------------*/
bool QueueEmpty(LinkQueue Q)
{
	if (Q.front!=Q.rear)
	{
		return false;
	}
	return true;
}

/*------------------------------------------------------------
操作目的：	得到队列的长度
初始条件：	队列Q已存在
操作结果：	返回Q中数据元素的个数
函数参数：
		LinkQueue Q		队列Q
返回值：
		int				数据元素的个数
------------------------------------------------------------*/
int QueueLength(LinkQueue Q)
{
	int i;
	QueuePtr p= Q.front;
	while(p)
	{
		p = p->next;
		i++;
	}
	return i;
}

/*------------------------------------------------------------
操作目的：	得到队列首元素
初始条件：	队列Q已存在
操作结果：	用e返回队列首元素
函数参数：
		LinkQueue Q		队列Q
		ElemType *e		队列首元素的值
返回值：
		bool			操作是否成功
------------------------------------------------------------*/
bool GetHead(LinkQueue Q, ElemType *e)
{
	if (Q.front == Q.rear)
	{
		return false;
	}
	*e = Q.front->data;
	return true;
}

/*------------------------------------------------------------
操作目的：	遍历队列
初始条件：	队列Q已存在
操作结果：	依次对Q的每个元素调用函数fp
函数参数：
		LinkQueue Q		队列Q
		void (*fp)()	访问每个数据元素的函数指针
返回值：
		无
------------------------------------------------------------*/
void QueueTraverse(LinkQueue Q, void (*fp)(ElemType))
{
    QueuePtr p = Q.front->next;
	while(p)
	{
         fp(p->data);
		 p = p->next;
	}
}

/*------------------------------------------------------------
操作目的：	清空队列
初始条件：	队列Q已存在
操作结果：	将队列清空
函数参数：
		LinkQueue *Q	队列Q
返回值：
		无
------------------------------------------------------------*/
void ClearQueue(LinkQueue *Q)
{
	   QueuePtr p=Q->front->next;
      while(p)
	  {
         p->data = NULL;
		 p= p->next;
	  }
}

/*------------------------------------------------------------
操作目的：	在队列末尾插入元素e
初始条件：	队列Q已存在
操作结果：	插入元素e作为队列新的尾结点
函数参数：
		LinkQueue *Q		队列Q
		ElemType e		待插入的数据元素
返回值：
		bool			操作是否成功
------------------------------------------------------------*/
bool EnQueue(LinkQueue *Q, ElemType e)
{
   QueuePtr p =(QueuePtr)malloc(sizeof(QNode));
   if (!p)
   {
	   return false;
   }
   p->data = e;
   p->next = NULL;
   Q->rear->next = p;
   Q->rear = p;
	return true;

}

/*------------------------------------------------------------
操作目的：	删除链式队列的头结点
初始条件：	队列Q已存在
操作结果：	删除链式队列的头结点
函数参数：
		LinkQueue *Q		队列Q
		ElemType *e		待插入的数据元素
返回值：
		bool			操作是否成功
------------------------------------------------------------*/
bool DeQueue(LinkQueue *Q, ElemType *e)
{
	QueuePtr p =Q->front->next;
	if (Q->front == Q->rear)
	{
		return false;
	}
	*e = p->data;
	Q->front->next = p->next;
	if (!p->next)
	{
		Q->rear = Q->front;
	}
	free(p);


	return true;
}