【头歌】循环队列及链队列的基本操作

news/2024/11/22 17:34:05/

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

任务描述

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

相关知识

队列的基本概念

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

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

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

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

一个队列的示意图:

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

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

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

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

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

一个循环队列示意图：

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

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

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

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

  • 设置队空条件为front==rear。

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

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

编程要求

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

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()

测试说明

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

测试输入：

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 // 最大队列长度+1struct 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 = new QElemType[MAX_QSIZE];if(!Q.base) exit(OVERFLOW); // 存储分配失败Q.front = Q.rear = 0;/********** End **********/  
}void DestroyQueue(SqQueue &Q)
{ // 销毁队列Q，Q不再存在/********** Begin **********/ free(Q.base);Q.base=NULL;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 TRUE;elsereturn FALSE;/********** 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 ERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAX_QSIZE;return OK;/********** End **********/  }int DeQueue(SqQueue &Q,QElemType &e)
{ // 若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR/********** Begin **********/ if(Q.front==Q.rear)return ERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAX_QSIZE;return OK;/********** End **********/  
}void QueueTraverse(SqQueue Q,void(*vi)(QElemType))
{ // 从队头到队尾依次对队列Q中每个元素调用函数vi()/********** Begin **********/ int i=Q.front;while(i!=Q.rear){vi(Q.base[i]);i=(i+1)%MAX_QSIZE;}printf("\n");/********** End **********/  
}

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

任务描述

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

相关知识

链队列的基本概念

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

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

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

链队列逻辑示意图：

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

链队列的类型定义
typedef struct QNode
{QElemType data;QNode *next;
}*QueuePtr;
struct LinkQueue
{QueuePtr front,rear; // 队头、队尾指针
};

编程要求

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

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()

测试说明

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

测试输入：

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 -1typedef 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.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front) exit(OVERFLOW);Q.front->next=NULL;/********** 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 p=Q.front,q;Q.front=Q.rear;while(p->next!=NULL){q=p;p=p->next;free(q);}/********** End **********/  }int QueueEmpty(LinkQueue Q){ // 若Q为空队列，则返回TRUE，否则返回FALSE/********** Begin **********/ if(Q.front->next==NULL)return TRUE;elsereturn FALSE;/********** End **********/  
}int QueueLength(LinkQueue Q)
{ // 求队列的长度/********** Begin **********/ QueuePtr p=Q.front;int i=0;while(p!=Q.rear){i++;p=p->next;}return i;/********** End **********/  
}int GetHead(LinkQueue Q,QElemType &e)
{ // 若队列不空，则用e返回Q的队头元素，并返回OK，否则返回ERROR/********** Begin **********/ QueuePtr p;if(Q.front==Q.rear)return ERROR;p=Q.front->next;e=p->data;return OK;/********** End **********/  }int EnQueue(LinkQueue &Q,QElemType e)
{ // 插入元素e为Q的新的队尾元素/********** Begin **********/ QueuePtr p=(QueuePtr)malloc(sizeof(QNode));if(!p) exit(OVERFLOW);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;/********** End **********/  
}int DeQueue(LinkQueue &Q,QElemType &e)
{ // 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR/********** Begin **********/ QueuePtr p;if(Q.front==Q.rear)return ERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);return OK;/********** End **********/  
}void QueueTraverse(LinkQueue Q,void(*vi)(QElemType))
{ // 从队头到队尾依次对队列Q中每个元素调用函数vi()/********** Begin **********/ QueuePtr p=Q.front->next;while(p!=NULL){vi(p->data);p=p->next;}printf("\n");/********** End **********/  }

http://www.ppmy.cn/news/20801.html

相关文章

洛谷 P1417 烹调方案 01背包题解 动态规划

洛谷 P1417 烹调方案 01背包题解 动态规划

真的好久没有写题解了 上次写还是在上次呢 先赞后看好习惯&#xff01; 昨天打了一月份的USACO(美国信奥赛) 给我一个感触&#xff08;也算是感想吧&#xff09;&#xff1a; 我是蒟蒻 我是蒟蒻 我是蒟蒻 我是蒟蒻 水内容&#xff08;&#xff09; 言归正传看今天这道题 题…
阅读更多...
不知道该学那一个语言？一文带你了解三门语言

不知道该学那一个语言？一文带你了解三门语言

名字&#xff1a;阿玥的小东东 学习&#xff1a;Python。正在学习c 主页&#xff1a;阿玥的小东东 目录 粉丝留言&#xff0c;回答问题 1.首先&#xff0c;初步了解 2.再明确自己要拿编程做什么 3.详细介绍以及建议 4.劝告 5.总结 1.如果你是一个初学者 2.你是个老手 …
阅读更多...
ip route 命令详解

ip route 命令详解

(523条消息) ip route 命令详解_thj_blog的博客-CSDN博客_ip route命令详解列出路由表条目ip命令的路由对象的参数还可以帮助你查看网络中的路由数据&#xff0c;并设置你的路由表。第一个条目是默认的路由条目&#xff0c;你可以随意改动它。在这个例子中&#xff0c;有几个路…
阅读更多...
Dart:函数、函数定义、可选参数

Dart:函数、函数定义、可选参数

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录前言一、Dart中函数定义内置函数自定义函数二、函数传参可选参数默认参数命名参数函数作为参数进行传递三、特别函数箭头函数自执行函数函数闭包总结前言 本篇是笔者…
阅读更多...
Dubbo 源码分析 – 服务导出

Dubbo 源码分析 – 服务导出

检查配置 本节我们接着前面的源码向下分析&#xff0c;前面说过 onApplicationEvent 方法在经过一些判断后&#xff0c;会决定是否调用 export 方法导出服务。那么下面我们从 export 方法开始进行分析&#xff0c;如下&#xff1a; public synchronized void export() {if (p…
阅读更多...
Minecraft 1.19.2 Fabric模组开发 09.Mixin

Minecraft 1.19.2 Fabric模组开发 09.Mixin

我们今天用mixin在1.19.2 fabric中实现一个望远镜 1.由于fabric已经自动配置好了mixin&#xff0c;所以我们无需配置mixin&#xff0c;先在ItemInit中新建一个我们的望远镜物品&#xff1a; ItemInit.java public static final Item BIRDWATCHER registerItem("birdwat…
阅读更多...
【Linux】makemakefile

【Linux】makemakefile

【Linux】make & makefile 文章目录【Linux】make & makefile1、makefile文件2、make命令3、make原理规则4、.PHONY5、编译与否的判断法1、makefile文件 makefile实际上是一个文件&#xff0c;配置文件 充当Linux上的工程管理工具&#xff0c;可以实现自动化编译 mak…
阅读更多...
linux 部署jmeter

linux 部署jmeter

一、linux 安装jdk Java Downloads | Oracle 二、 linux上传jmeter 2.1 上传jmeter jmeter 下载地址&#xff1a; Apache JMeter - Download Apache JMeter 注意&#xff1a; 我先在我本地调试脚本&#xff08;mac环境&#xff09;&#xff0c;调试完成后&#xff0c;再在…
阅读更多...
最新文章

Copyright @ 2022~2023