第4章 队列
i=0; else i++;
②利用模运算
i=(i+1)%QueueSize;//i为Q->front或Q->rear
我们将采用此方法实现循环意义下的队头、队尾指针的加1操作。 （3）循环队列边界条件的处理方法
循环队列Q中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件Q->front== Q->rear来判别队列是“空”还是“满”。解决这个问题的方法至少有三种：
①另设一标志变量flag以区别队列的空和满，比如当条件Q->front== Q->rear成立，且 flag 为0时表示队列空，而为1时表示队列满。
②少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于队头指针，若相等则认为队满（注意：rear所指的单元始终为空），此时队空的条件是Q->front== Q->rear，队满的条件是(Q->rear+1)%QueueSize== Q->front。
③使用一个计数器count记录队列中元素的总数，当Q->count ==0时表示队列空；当Q->count ==QueueSize时表示队列满。 我们将使用此方法。
（4）循环队列的描述
#define QueueSize 100 //定义队列最大容量 typedef char DataType; //定义队列元素类型 typedef struct cirqueue{
DataType data[QueueSize];//队列元素定义 int front; int rear; int count; }CirQueue;
CirQueue *Q; //定义循环队列Q
//队头指针定义
//队尾指针定义
//计数器定义
设Q是CirQueue类型的指针变量，则Q是指向循环队列的指针，队头指针、队尾指可分别表示为Q->front、Q-> rear，计数器可表示为Q-> count，队头元素可表示为Q->data[Q->front]，队尾元素可表示为Q->data[Q-> rear]。
（5）循环队列的基本运算的算法 ① 置队空
void InitQueue(CirQueue *Q){
第4章 队列
Q->front=Q->rear=0; Q->count=0; //计数器置0 }
② 判队空
int QueueEmpty(CirQueue *Q){
return Q->count==0; //队列无元素为空 }
③ 判队满
int QueueFull(CirQueue *Q){
return Q->count==QueueSize; //队中元素个数等于QueueSize时队满 }
④ 入队
int EnQueue(CirQueue *Q,DataType x){
if(QueueFull(Q))
{puts(“队满”); return 0;} //队满上溢 Q->count ++; //队列元素个数加1 Q->data[Q->rear]=x; //新元素插入队尾
Q->rear=(Q->rear+1)%QueueSize; //循环意义下将尾指针加1 return 1; }
⑤ 出队
DataType DeQueue(CirQueue *Q){
DataType temp; if(QueueEmpty(Q))
{puts(“队空”); return 0;} //队空下溢 temp=Q->data[Q->front]; Q->count--;
//队列元素个数减1
Q->front=(Q->front+1)%QueueSize; //循环意义下的头指针加1 return temp; }
⑥取队头元素
DataType QueueFront(CirQueue *Q){
if(QueueEmpty(Q))
{puts(“队空”); return 0;}
第4章 队列
return Q->data[Q->front]; }
3．链队列及基本操作的实现
（1）链队列：队列的链式存储结构称为链队列，它是限制仅在表头删除和表尾插入的单链表。由于需要在表尾进行插入操作，所以为操作方便除头指针外有必要再增加一个指向尾结点的指针。
（2）链队列的描述
typedef char DataType; //定义队列元素类型 typedef struct queuenode{//队列中结点的类型
DataType data; struct queuenode *next; }QueueNode; typedef struct{
QueueNode *front; //队头指针 QueueNode *rear; //队尾指针 }LinkQueue;
LinkQueue *Q; //定义链队列Q
设Q是LinkQueue类型的指针变量，则Q是指向链队列的指针，队头指针、队尾指可分别表示为Q->front、Q-> rear。
设p是QueueNode类型的指针变量，则p是指向链队列某结点的指针，该结点的数据域可表示为p ->data，该结点的指针域可表示为p -> next。
（3）链队列示意图 链队列如图3.5。
Q->front Q->rear
*Q
*Q
Q->front Q->rear
^ ^
(a)空链队列
队头结点
… 队尾结点
^
（4）链队列的基本运算 (b)非空链队列 由于链队列结点的存储空间是动态分配的，所以无须考虑判队满的运算。
图3.5 链队列
第4章 队列
①置空队
void InitQueue(LinkQueue *Q){ Q->front=Q->rear=NULL; }
②判队空
int QueueEmpty(LinkQueue *Q){
return Q->front==NULL&&Q->rear==NULL;//实际上只须判断队头指针是否为空即可 }
③入队
void EnQueue(LinkQueue *Q,DataType x){//将元素x插入链队列尾部
QueueNode *p;
p=(QueueNode *)malloc(sizeof(QueueNode)); p->data=x; p->next=NULL; if(QueueEmpty(Q))
Q->front=Q->rear=p; //将x插入空队列 else { //x插入非空队列的尾
Q->rear->next=p; //*p链到原队尾结点后 Q->rear=p; //队尾指针指向新的尾 } }
④出队
DataType DeQueue (LinkQueue *Q){ DataType x; QueueNode *p; if(QueueEmpty(Q)) {puts(“队空”); return 0;} p=Q->front; //指向队头结点 x=p->data; //保存队头结点的数据 Q->front=p->next; //将对头结点从链上摘下
if(Q->rear==p)//原队中只有一个结点，删去后队列变空，此时队头指针已为空 Q->rear=NULL;
free(p); //释放被删队头结点 return x; //返回原队头数据 }
第4章 队列
⑤取队头元素
DataType QueueFront(LinkQueue *Q) {
if(QueueEmpty(Q)) {puts(“队空”); return 0;} return Q->front->data; }
注意：在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。
4.3 队列的应用
例1：一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。 如:阵列 0234500067 1034560500 2045600671 0000000089 有4个细胞。 算法步骤：
1． 从文件中读入m*n矩阵阵列，将其转换为boolean矩阵存入bz数组中； 2． 沿bz数组矩阵从上到下，从左到右，找到遇到的第一个细胞；
3． 将细胞的位置入队h，并沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置bz数组置为FLASE；
4． 将h队的队头出队，沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置bz数组置为FLASE；
5． 重复4，直至h队空为止，则此时找出了一个细胞； 6． 重复2，直至矩阵找不到细胞； 7． 输出找到的细胞数。
程序：练习：如下图：求图中被*围成的封闭区域的面积（方格的个数不包括*所在的方格，且*不在最外一层）。
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库NOIP高中信息技术竞赛资料 - -数据结构(6)在线全文阅读。
相关推荐：