专栏首页WindCoder队列的动态链式存储实现—C语言

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

头文件

ElemType.h

/***
*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

/***
*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

主函数

Lab.cpp

#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.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

/***
*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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • friend关键字使用之雇员与雇主类-C++

    汐楓
  • 求最大公约数与最小公倍数

    汐楓
  • 函数模板之名为List的类模板—C++

    汐楓
  • C/C++协程的简单尝试

    最近用tars框架编写后台服务的时候,逐渐抛弃了之前的异步调用方式,而是使用协程,以同步代码的写法实现并发调用,所以希望可以了解学习一下协程的相关知识。

    jackieluo
  • 动物类及修改-C++

    汐楓
  • 学生管理系统-C++

    汐楓
  • 关于muduo网络库的注解

    http://blog.csdn.net/liuxuejiang158blog/article/details/17056537#comments

    bear_fish
  • 铁路与多核多线程

      多核多线程已经成为当前一个时髦的话题,早在2005年C++大师Herb Sutter就说过免费的午餐已经结束,并发编程的时代已经来临。从接触第一个多线程项目...

    ternturing
  • C#基础知识之方法重载总结

    方法重载是指在同一个类中方法同名,参数不同,调用时根据实参的形式,选择与他匹配的方法执行操作的一种技术。

    跟着阿笨一起玩NET
  • 继承练习之学生教师类—C++

    汐楓

扫码关注云+社区

领取腾讯云代金券