2925人阅读
VC++初尝（22）
数据结构(C语言版)记录（34）
队列数组实现的简单操作：
/***********************************************************/
//&程序名称：StackOfLink.cpp
//&程序目的：设计一个数组实现的队列的程序
//&程序来源：数据结构与算法分析(C语言描述)&P-60
//&日期：&10:32:58
/***********************************************************/
#include&&stdio.h&
#include&&stdlib.h&
#define&Error(&str&)&&&&&&&&FatalError(&str&)
#define&FatalError(&str&)&&&fprintf(&stderr,&&%s\n&,&str&),&exit(&1&)
typedef&int&ElementT
#define&MINQUEUESIZE&5
struct&QueueRecord
&&&&int&&&&&&&&//&容量
&&&&int&&&&&&&&&&&//&对头
&&&&int&&&&&&&&&&&&//&队尾
&&&&int&&&&&&&&&&&&
&&&&ElementType*&arrayQ&&&&
typedef&struct&QueueRecord*&Q
int&IsEmpty(Queue&q);
int&IsFull(Queue&q);
Queue&CreateQueue(int&maxElements);
void&DisposeQueue(Queue&q);
void&MakeEmpty(Queue&q);
void&Enqueue(ElementType&x,&Queue&q);
ElementType&Front(Queue&q);
void&Dequeue(Queue&q);
ElementType&FrontAndDequeue(Queue&q);
/************************************************************************/
/************************************************************************/
int&main(void)
&&&&Queue&sqQ
&&&&int&maxElements&=&10;
&&&&sqQueue&=&CreateQueue(maxElements);
&&&&if&(IsEmpty(sqQueue))
&&&&&&&&printf(&创建了空队列！&);
&&&&int&value&=&0;
&&&&printf(&队列中的数据为(front-&rear)：\n&);
&&&&while&(!IsFull(sqQueue))
&&&&&&&&Enqueue(value*value,&sqQueue);&&//&入队
&&&&&&&&printf(&%d&&,&value*value);
&&&&&&&&value++;
&&&&printf(&队列已满\n&);
&&&&ElementType&frontQ
&&&&frontQueue&=&Front(sqQueue);
&&&&printf(&对头元素为：%d\n&,&frontQueue);
&&&&Dequeue(sqQueue);
&&&&frontQueue&=&Front(sqQueue);
&&&&printf(&执行出队操作Dequeue之后，对头元素是：%d\n&,&frontQueue);
&&&&DisposeQueue(sqQueue);
&&&&return&0;
/************************************************************************/
//&队列是否为空
/************************************************************************/
int&IsEmpty(Queue&q)
&&&&return&q-&size&==&0;
/************************************************************************/
//&队列是否已满&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
/************************************************************************/
int&IsFull(Queue&q)
&&&&return&q-&size&==&q-&
/************************************************************************/
//&创建队列&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
/************************************************************************/
Queue&CreateQueue(int&maxElements)
&&&&Queue&q;
&&&&if&(maxElements&&&MINQUEUESIZE)
&&&&&&&&Error(&要创建的队列太小！&);
&&&&q&=&(Queue)malloc(sizeof(struct&QueueRecord));
&&&&if&(NULL&==&q)
&&&&&&&&FatalError(&空间不足，队列内存分配失败！&);
&&&&q-&arrayQueue&=&(ElementType*)malloc(sizeof(ElementType)&*&maxElements);
&&&&if&(NULL&==&q-&arrayQueue)
&&&&&&&&FatalError(&空间不足，队列内数组创建失败！&);
&&&&q-&capacity&=&maxE
&&&&MakeEmpty(q);
&&&&return&q;
/************************************************************************/
//&释放队列&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
/************************************************************************/
void&DisposeQueue(Queue&q)
&&&&if&(NULL&!=&q)
&&&&&&&&free(q-&arrayQueue);
&&&&&&&&free(q);
&&&&return;
/************************************************************************/
//&使队列为空&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
/************************************************************************/
void&MakeEmpty(Queue&q)
&&&&q-&size&=&0;
&&&&q-&front&=&1;
&&&&q-&rear&=&0;
/************************************************************************/
//&检测对头/队尾位置是否已到尾端&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
/************************************************************************/
static&int&Succ(&int&value,&Queue&q&)
&&&&if(&++value&==&q-&capacity&)
&&&&&&&&value&=&0;
&&&&return&
/************************************************************************/
//&入队列&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
/************************************************************************/
void&Enqueue(ElementType&x,&Queue&q)
&&&&if&(IsFull(q))
&&&&&&&&Error(&队列已满&);
&&&&&&&&q-&size++;
&&&&&&&&q-&rear&=&Succ(q-&rear,&q);
&&&&&&&&q-&arrayQueue[q-&rear]&=&x;
&&&&return;
/************************************************************************/
//&出队列&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
/************************************************************************/
void&Dequeue(Queue&q)
&&&&if&(IsEmpty(q))
&&&&&&&&Error(&队列为空！&);
&&&&&&&&q-&size--;
&&&&&&&&q-&front&=&Succ(q-&front,&q);
&&&&return;
/************************************************************************/
//&返回对列头元素&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
/************************************************************************/
ElementType&Front(Queue&q)
&&&&if&(!IsEmpty(q))
&&&&&&&&return&q-&arrayQueue[q-&front];
&&&&Error(&队列为空\n&);
&&&&return&0;
/************************************************************************/
//&返回对列头元素并使对头元素出对&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
/************************************************************************/
ElementType&FrontAndDequeue(Queue&q)
&&&&ElementType&x&=&0;
&&&&if(&IsEmpty(q)&)
&&&&&&&&Error(&&队列为空！&&);
&&&&&&&&q-&size--;
&&&&&&&&x&=&q-&arrayQueue[q-&front];
&&&&&&&&q-&front&=&Succ(&q-&front,&q&);
&&&&return&x;
输出结果：
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：317382次
积分：3827
积分：3827
排名：第7862名
原创：131篇
评论：50条
(1)(1)(1)(1)(1)(1)(3)(2)(2)(3)(4)(17)(4)(1)(2)(4)(8)(2)(3)(19)(23)(7)(2)(5)(9)(1)(2)(9)您所在的位置： &
链队列（1）
链队列（1）
试题研究编写组
机械工业出版社
《数据结构考研指导》按线性逻辑、层次逻辑、网状逻辑的顺序讲解数据结构的基本概念，根据学生对新知识学习认知的规律，对每种数据结构从数据的逻辑结构开始，逐渐地引入数据的存储结构和相关的方法，达到深化学生对概念的理解和掌握的目的。第2章讲述栈和队列。本节说的是链队列。
2.3.2& 链队列
(1)链队列的基本概念
链队列是队列的链式存储表示，或者说链队列是只允许在表尾进行插入、表头进行删除运算的单链表。在该单链表中指向允许删除的一端即表头的指针称为队头（front）指针，指向允许插入的一端即表尾的指针称为队尾（rear）指针。一个链队列由队头、队尾指针唯一确定。在表尾的插入运算称为入队，在表头的删除运算称为出队。
链队列和链栈类似，其优点也是不受连续存储空间大小的限制，故不需考虑队满的问题。与线性单链表类似，为简化边界条件的处理，可为链队列添加一个头结点，并另队头指针指向头结点。需注意在有头结点的链队列的出队操作中，一般只需修改队头指针，但当原队列中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改队尾指针，使其指向头结点，且删去此结点后队列变空。在无头结点的链队列中，判断链队列为空的条件是队头指针为空；在添加了头结点的链队列中，判断链队列为空的条件是队头指针和队尾指针相等均指向头结点。图2-11a是一个带头结点的链队列示意图，其中front表示队头指针，rear表示队尾指针，图2-11b是带头结点的空链队列示意图。
图2-12a是元素x和y依次入队后的链队列示意图，图2-12b是元素x出队示意图，注意图中指针的变化。
(2)链队列的基本操作
本部分的描述均为带头结点的链队列。在链队列的基本操作中着重掌握链队列的初始化、判队空、入队、出队、取队头元素、销毁队列操作。
队列的链式存储表示：&&&&&&&&typedef&struct&QNode{ &&&&&&&DataType&&&&&&&&&&&∥结点的数据域 &&&&&&&struct&QNode*∥结点的指针域 &}QNode,*QueueP &&typedef&struct{ &&&&&&&QueuePtr&∥队头指针 &&&&&&&QueuePtr&∥队尾指针 &}LinkQ&
链队列的六种基本操作：
①初始化队列：队头和队尾都指向头结点，且头结点的下个结点为空。void&InitQueue(LinkQueue&&Q){ &∥构造一个空队列 &Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); &∥队头和队尾指向头结点 &if(!Q.front)exit(OVERFLOW);&&&&&&&&&&&&&&&&&&&&&&&& &∥存储分配失败 &Q.front-&next=NULL; &} &②判队空：判断队头和队尾指针是否相等。 &int&QueueEmpty(LinkQueue&&Q){ &return&Q.front==Q. &} &③入队：将一个元素插入队尾。 &void&EnQueue(LinkQueue&&Q,DataType&x){ &∥将元素x插入队尾 &p=(QueuePtr)malloc(sizeof(QNode)); &if(!p)exit(OVERFLOW);&&∥存储分配失败 &p-&data=x; &p-&next=NULL; &Q.rear-&next=p;&&&&&&∥p插入原队尾 &Q.rear=p;&&&&&&&&&&&&&&∥p成为新的队尾 &} &④出队：从队头删除一个元素。 &DataType&DeQueue(LinkQueue&&Q){ &∥若队列不空则删除队头元素，用x返回该元素的值，否则返回ERROR &DataType&x;&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &∥用来保存被删除结点中的数据 &if(QueueEmpty(Q))Error("Queue&is&empty.");&& &∥若队列为空则显示错误提示 &p=Q.front-& &x=p-& &Q.front-&next=p-& &if(Q.rear==p)&&Q.rear=Q.&&&&&&&&&&&&&& &∥当队列中仅有一个元素时需修改尾指针 &free(p); &return&x; &} &⑤取队头元素： &DataType&GetFront(LinkQueue&&Q){ &if(QueueEmpty(Q))Error("Queue&is&empty."); &return&Q.front-& &} &⑥销毁队列：依次删除队头元素直到队列为空。 &void&DestroyQueue(LinkQueue&&Q){ &while(Q.front){ &Q.rear=Q.front-& &free(Q.front); &Q.front=Q. &} &}&
【责任编辑： TEL：（010）】&&&&&&
关于&&&&&&的更多文章
AngularJS是很多Web开发人员在打造单页面应用程序时的首选创建方
本书描述了黑客用默默无闻的行动为数字世界照亮了一条道路的故事。
讲师： 14人学习过讲师： 35人学习过讲师： 15人学习过
本书由业界最先进的动画库Velocity.js的作者所著，书
本书是一本全面的C++教程，介绍C++编程知识及问题解决
本书主要阐述了云计算中PaaS 平台的实现与运维管理，
本书是在《网管员必读―网络安全》第1版的基础上修改而成的。新版在保留第1版实用内容的基础上增加了大量新的实用内容，同时删除
51CTO旗下网站