循环队列及链队列的基本操作_本关任务是实现循环队列的基本操作函数,以实现判断队列是否为满、是否为空、求队

第1关：循环队列的基本操作

任务描述

本关任务是实现循环队列的基本操作函数，以实现判断队列是否为满、是否为空、求队列元素个数、进队和出队等功能。

相关知识

队列的基本概念

队列（简称队）也是一种运算受限的线性表，在这种线性表上，插入限定在表的某一端进行，删除限定在表的另一端进行。

队列的插入操作称为进队，删除操作称为出队。

允许插入的一端称为队尾，允许删除的一端称为队头。

新插入的元素只能添加到队尾，被删除的只能是排在队头的元素。

一个队列的示意图:

队列通常有两种存储结构，即顺序存储结构和链式存储结构。

队列的顺序存储结构简称为顺序队列，它由一个一维数组（用于存储队列中元素）及两个分别指示队头和队尾的变量组成，这两个变量分别称为“队头指针”和“队尾指针”。

通常约定队尾指针指示队尾元素的当前位置，队头指针指示队头元素的前一个位置。

循环队列的类型定义

1. #define MAX_QSIZE 5 // 最大队列长度+1
2. struct SqQueue
3. {
4. QElemType *base; // 初始化的动态分配存储空间
5. int front; // 头指针，若队列不空，指向队列头元素
6. int rear; // 尾指针，若队列不空，指向队列尾元素的下一个位置
7. };

使用顺序队列时会出现“假溢出现象”，为了能够充分地使用数组中的存储空间，可以把数组的前端和后端连接起来，形成一个环形的表，即把存储队列元素的表从逻辑上看成一个环。这个环形的表叫做循环队列。

一个循环队列示意图：

队头队尾指针进1的操作为：

• 队头指针进1：front=(front+1) MOD MaxSize
• 队尾指针进1：rear=(rear+1) MOD MaxSize

为了在循环队列中区分队空和队满，规定：

• 设置队空条件为front==rear。
• 设置队满条件为(rear+1) MOD MaxSize==front。也就是说，当rear指到front的前一位置时就认为队列满了。

显然在这样设置的队满条件下，队满条件成立时队中还有一个空闲单元，也就是说这样的队中最多只能进队MaxSize-1个元素。

编程要求

根据提示，在右侧编辑器补充代码，编写循环队列的基本操作函数。

1. void InitQueue(SqQueue &Q); // 构造一个空队列Q
2. void DestroyQueue(SqQueue &Q); // 销毁队列Q，Q不再存在
3. void ClearQueue(SqQueue &Q); // 将Q清为空队列
4. int QueueEmpty(SqQueue Q); // 若队列Q为空队列，则返回TRUE；否则返回FALSE
5. int QueueLength(SqQueue Q); // 返回Q的元素个数，即队列的长度
6. int GetHead(SqQueue Q,QElemType &e); // 若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR
7. int EnQueue(SqQueue &Q,QElemType e); // 插入元素e为Q的新的队尾元素
8. int DeQueue(SqQueue &Q,QElemType &e); // 若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR
9. void QueueTraverse(SqQueue Q,void(*vi)(QElemType)); // 从队头到队尾依次对队列Q中每个元素调用函数vi()

测试说明

平台会对你编写的代码进行测试：

测试输入： 10 20 30 40 50 60

预期输出： 队列长度为: 4 现在队列中元素: 10 20 30 40 删除的元素是10 删除的元素是20 队列长度为: 3 现在队列中元素: 30 40 60 现在队头元素为:30

#include <stdio.h>
#include<stdlib.h>
#include <iostream>
using namespace std;
 
 // 函数结果状态代码
 #define TRUE 1
 #define FALSE 0
 #define OK 1
 #define ERROR 0
 #define OVERFLOW -1
 typedef int QElemType;
 
#define MAX_QSIZE 5 // 最大队列长度+1
 
struct SqQueue
{
   QElemType *base; // 初始化的动态分配存储空间
   int front; // 头指针，若队列不空，指向队列头元素
   int rear; // 尾指针，若队列不空，指向队列尾元素的下一个位置
};
 
void print(QElemType i)
{
   printf("%d ",i);
}
void InitQueue(SqQueue &Q); // 构造一个空队列Q
void DestroyQueue(SqQueue &Q); // 销毁队列Q，Q不再存在
void ClearQueue(SqQueue &Q); // 将Q清为空队列
int QueueEmpty(SqQueue Q); // 若队列Q为空队列，则返回TRUE；否则返回FALSE
int QueueLength(SqQueue Q); // 返回Q的元素个数，即队列的长度
int GetHead(SqQueue Q,QElemType &e); // 若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR
int EnQueue(SqQueue &Q,QElemType e); // 插入元素e为Q的新的队尾元素
int DeQueue(SqQueue &Q,QElemType &e); // 若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR
void QueueTraverse(SqQueue Q,void(*vi)(QElemType)); // 从队头到队尾依次对队列Q中每个元素调用函数vi()  
 
int main()
{
   int j;
   int i=0,l;
   QElemType d;
   SqQueue Q;
   InitQueue(Q);
   for(i=0;i<MAX_QSIZE;i++)
   {
     scanf("%d",&d);     
     EnQueue(Q,d);
   };
   printf("队列长度为: %d\n",QueueLength(Q));
   printf("现在队列中元素:\n");
   QueueTraverse(Q,print);
   DeQueue(Q,d);
   printf("删除的元素是%d\n",d);
   DeQueue(Q,d);
   printf("删除的元素是%d\n",d);
   scanf("%d",&d);
   EnQueue(Q,d);
    printf("队列长度为: %d\n",QueueLength(Q));
   printf("现在队列中元素:\n");
   QueueTraverse(Q,print);
   j=GetHead(Q,d);
   if(j)
     printf("现在队头元素为:%d\n",d);
   ClearQueue(Q);
   DestroyQueue(Q);
}
// 循环队列的基本操作(9个)
void InitQueue(SqQueue &Q)
{ // 构造一个空队列Q
   /********** Begin **********/ 
 	Q.base=(QElemType*)malloc(MAX_QSIZE* sizeof(QElemType));
   
   Q.front=Q.rear=0;
    
	/********** End **********/  
}
 
void DestroyQueue(SqQueue &Q)
{ // 销毁队列Q，Q不再存在
   /********** Begin **********/ 
 
 Q.front=Q.rear=0;
 
	/********** End **********/  
}
 
void ClearQueue(SqQueue &Q)
{ // 将Q清为空队列
    /********** Begin **********/ 
 Q.front=Q.rear=0;
	/********** End **********/  
}
 
int QueueEmpty(SqQueue Q)
{ // 若队列Q为空队列，则返回TRUE；否则返回FALSE
   /********** Begin **********/ 
if(Q.front==Q.rear)
return 1;
else
return 0;
	/********** End **********/  
 }
 
int QueueLength(SqQueue Q)
{ // 返回Q的元素个数，即队列的长度
   /********** Begin **********/ 
return (Q.rear-Q.front+MAX_QSIZE)%MAX_QSIZE;
 
	/********** End **********/  
 }
 
 int GetHead(SqQueue Q,QElemType &e)
 { // 若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR
   /********** Begin **********/ 
 if(Q.front==Q.rear) // 队列空
     return ERROR;
   e=Q.base[Q.front];
   return OK;
 /********** End **********/  
}
 
int EnQueue(SqQueue &Q,QElemType e)
{ // 插入元素e为Q的新的队尾元素
   /********** Begin **********/ 
 if((Q.rear+1)%MAX_QSIZE==Q.front)
 return 0;
 Q.base[Q.rear]=e;
 Q.rear=(Q.rear+1)%MAX_QSIZE;
 return 1;
	/********** End **********/  
 }
 
int DeQueue(SqQueue &Q,QElemType &e)
{ // 若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR
   /********** Begin **********/ 
if(Q.rear==Q.front)
return 0;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAX_QSIZE;
return 1;
	/********** End **********/  
}
 
void QueueTraverse(SqQueue Q,void(*vi)(QElemType))
{ // 从队头到队尾依次对队列Q中每个元素调用函数vi()
   /********** Begin **********/ 
 while(Q.rear!=Q.front)
 {
    vi(Q.base[Q.front]);
    Q.front=(Q.front+1)%MAX_QSIZE;
 }
 printf("\n");
	/********** End **********/  
}

 

第2关：链队列的基本操作

任务描述

本关任务是实现链队列的基本操作函数，以实现判断队列是否为满、是否为空、求队列元素个数、进队和出队等功能。

相关知识

链队列的基本概念

队列的链式存储结构简称为链队列。

这里采用的链队是一个同时带有队头指针front和队尾指针rear的单链表。

队头指针指向队头结点，队尾指针指向队尾结点即单链表的尾结点，并将队头和队尾指针结合起来构成链队结点，

链队列逻辑示意图：

下面给出一种链队列的实现方案。

链队列的类型定义

1. typedef struct QNode
2. {
3. QElemType data;
4. QNode *next;
5. }*QueuePtr;
7. struct LinkQueue
8. {
9. QueuePtr front,rear; // 队头、队尾指针
10. };

编程要求

根据提示，在右侧编辑器补充代码，编写链队列的基本操作函数。

1. void InitQueue(LinkQueue &Q); // 构造一个空队列Q
2. void DestroyQueue(LinkQueue &Q); // 销毁队列Q，Q不再存在
3. void ClearQueue(LinkQueue &Q); // 将Q清为空队列
4. int QueueEmpty(LinkQueue Q); // 若队列Q为空队列，则返回TRUE；否则返回FALSE
5. int QueueLength(LinkQueue Q); // 返回Q的元素个数，即队列的长度
6. int GetHead(LinkQueue Q,QElemType &e); // 若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR
7. int EnQueue(LinkQueue &Q,QElemType e); // 插入元素e为Q的新的队尾元素
8. int DeQueue(LinkQueue &Q,QElemType &e); // 若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR
9. void QueueTraverse(LinkQueue Q,void(*vi)(QElemType)); // 从队头到队尾依次对队列Q中每个元素调用函数vi()

测试说明

平台会对你编写的代码进行测试：

测试输入： 10 20 30 40 50 60

预期输出： 队列长度为: 5 现在队列中元素: 10 20 30 40 50 删除的元素是10 删除的元素是20 队列长度为: 4 现在队列中元素: 30 40 50 60 现在队头元素为:30

#include <stdio.h>
#include<stdlib.h>
#include <iostream>
using namespace std;
 
 // 函数结果状态代码
 #define TRUE 1
 #define FALSE 0
 #define OK 1
 #define ERROR 0 
 #define OVERFLOW -1
 typedef int QElemType;
 
typedef struct QNode
{
   QElemType data;
   QNode *next;
}*QueuePtr;
struct LinkQueue
{
   QueuePtr front,rear; // 队头、队尾指针
};
 
void print(QElemType i)
{
   printf("%d ",i);
}
void InitQueue(LinkQueue &Q); // 构造一个空队列Q
void DestroyQueue(LinkQueue &Q); // 销毁队列Q，Q不再存在
void ClearQueue(LinkQueue &Q); // 将Q清为空队列
int QueueEmpty(LinkQueue Q); // 若队列Q为空队列，则返回TRUE；否则返回FALSE
int QueueLength(LinkQueue Q); // 返回Q的元素个数，即队列的长度
int GetHead(LinkQueue Q,QElemType &e); // 若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR
int EnQueue(LinkQueue &Q,QElemType e); // 插入元素e为Q的新的队尾元素
int DeQueue(LinkQueue &Q,QElemType &e); // 若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR
void QueueTraverse(LinkQueue Q,void(*vi)(QElemType)); // 从队头到队尾依次对队列Q中每个元素调用函数vi()  
 
int main()
{
   int j;
   int i=0,l;
   QElemType d;
   LinkQueue Q;
   InitQueue(Q);
   for(i=0;i<5;i++)
   {
     scanf("%d",&d);     
     EnQueue(Q,d);
   };
   printf("队列长度为: %d\n",QueueLength(Q));
   printf("现在队列中元素:\n");
   QueueTraverse(Q,print);
   DeQueue(Q,d);
   printf("删除的元素是%d\n",d);
   DeQueue(Q,d);
   printf("删除的元素是%d\n",d);
   scanf("%d",&d);
   EnQueue(Q,d);
    printf("队列长度为: %d\n",QueueLength(Q));
   printf("现在队列中元素:\n");
   QueueTraverse(Q,print);
   j=GetHead(Q,d);
   if(j)
     printf("现在队头元素为:%d\n",d);
   ClearQueue(Q);
   DestroyQueue(Q);
 }
// 链队列的基本操作(9个)
void InitQueue(LinkQueue &Q)
 { // 构造一个空队列Q
  /********** Begin **********/ 
 Q.rear=Q.front=(QueuePtr)malloc(sizeof(QNode));
 
  /********** End **********/  
}
 
void DestroyQueue(LinkQueue &Q)
{ // 销毁队列Q(无论空否均可)
   /********** Begin **********/ 
 
  while(Q.front)
  {
    Q.rear=Q.front->next;
    free(Q.front);
    Q.front=Q.rear;
  }
  /********** End **********/  
}
 
void ClearQueue(LinkQueue &Q)
{ // 将Q清为空队列
	/********** Begin **********/ 
  QueuePtr q=Q.front,s;
  Q.front=Q.rear;
  while(q->next)
  {
    s=q;
    q=q->next;
  }
 
 
	/********** End **********/  
 }
 
int QueueEmpty(LinkQueue Q)
 { // 若Q为空队列，则返回TRUE，否则返回FALSE
   /********** Begin **********/ 
   if(Q.front->next==NULL)
   {
     return 1;
   }
   else 
   return 0;
 
	/********** End **********/  
}
 
int QueueLength(LinkQueue Q)
{ // 求队列的长度
   /********** Begin **********/ 
   QueuePtr q=Q.front;
   int count=0;
   while(q!=Q.rear)
   {
     count++;
     q=q->next;
   }
   return count;
 
	/********** End **********/  
}
 
int GetHead(LinkQueue Q,QElemType &e)
{ // 若队列不空，则用e返回Q的队头元素，并返回OK，否则返回ERROR
   /********** Begin **********/ 
   QueuePtr q;
   if(Q.rear==Q.front)
   {
     return 0;
   }
   q=Q.front->next;
   e=q->data;
   return 1;
 
 
	/********** End **********/  
 }
 
int EnQueue(LinkQueue &Q,QElemType e)
{ // 插入元素e为Q的新的队尾元素
  /********** Begin **********/ 
  QueuePtr q=(QueuePtr)malloc(sizeof(QNode));
  q->data=e;
  q->next=NULL;
  Q.rear->next=q;
  Q.rear=q;
 
  /********** End **********/  
}
 
int DeQueue(LinkQueue &Q,QElemType &e)
{ // 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR
  /********** Begin **********/ 
  QueuePtr p;
  if(Q.front==Q.rear)
    return 0;
  p=Q.front->next;
  e=p->data;
  Q.front->next=p->next;
  if(Q.rear==p)
    Q.rear=Q.front;
  return 1;
 
  /********** End **********/  
}
 
void QueueTraverse(LinkQueue Q,void(*vi)(QElemType))
{ // 从队头到队尾依次对队列Q中每个元素调用函数vi()
  /********** Begin **********/ 
 
  QueuePtr q=Q.front->next;
  while(q!=NULL)
  {
    vi(q->data);
    q=q->next;
  }
  printf("\n");
	/********** End **********/  
 }