《数据结构（C语言版）第二版》第三章-栈和队列（3.5 队列的表示和操作的实现）

2024-05-06 14:20
文章标签 实现 第三章 操作 数据结构 队列 第二 语言版 表示 3.5

本文主要是介绍《数据结构（C语言版）第二版》第三章-栈和队列（3.5 队列的表示和操作的实现），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

3.5 队列的表示和操作的实现

3.5.1 循环列队的表示和操作的实现

3.5.1.1 循环列队的初始化

#include <stdio.h>
#include <stdlib.h>#define MAXQSIZE 100typedef int QElemType;typedef struct
{QElemType* base;int fornt;int rear;
}SqQueue;void InitQueue(SqQueue& Q);int  main()
{SqQueue N = { NULL,0,0 };InitQueue(N);return 0;
}void InitQueue(SqQueue& Q)
{Q.base = (QElemType*)malloc(sizeof(QElemType) * MAXQSIZE);if (!Q.base){printf("内存分配失败，导致初始化循环队列失败。");return;}Q.fornt = Q.rear = 0;printf("初始化循环队列成功。");
}

在这里插入图片描述

3.5.1.2 求循环列队的长度

循环队列长度公式推导——我想he可乐

已知：
当Q.rear≥Q.front时，L=Q.rear-Q.front；
当Q.rear<Q.front时，L=MaxSize-Q.front+Q.rear = Q.reare-Q.front+MaxSize.

数学取余的性质：（x+ky）%y=x（x<y，k∈N）.

当Q.rear≥Q.front时，x = Q.rear-Q.front，k = 1,
Q.rear-Q.front = （Q.rear-Q.front + MaxSize）% MaxSize；

当Q.rear<Q.front时，x = Q.rear-Q.front+ MaxSize，k = 1,
Q.reare-Q.front+MaxSize
= （Q.reare-Q.front + MaxSize + MaxSize )% MaxSize
=（Q.reare-Q.front + 2MaxSize )% MaxSize
= Q.reare-Q.front
= （Q.rear-Q.front + MaxSize）% MaxSize

所以可将三种情况下的公式合成一个：

循环队列中现有元素的个数：
L = （Q.rear-Q.front+MaxSize）%MaxSize.

①MaxSize是循环列队中整个环形所包含的元素的个数（或者叫循环列队的长度），是不变的。
②循环列队存储数据的一维数组QElemType base[MaxSize]的位置，及其每个位置所代表的数组下标（从0到MaxSize-1），在初始化成功，申请了内存空间之后，也是固定不变的。
③队头Q.front和队尾Q.rear也是数组下标，但在元素入队和出队过程中，均是动态变化的。
因此，不管是空队，还是满队，队头和队尾不一定就是0号下标或MaxSize-1号下标。

利用这个原则来判断循环链表中存储数据的到底是数组中的哪些位置：
①为了避免判别队列空间是“满”还是“空”的条件冲突，牺牲的那一个存储空间一定是在沿着从队头Q.front到队尾Q.rear顺时针方向的，队尾Q.rear的后面。
②且这个被牺牲掉的存储空间所代表的下标，可以是数组中的任意一个，不一定就是最大下标MaxSize-1处。

#include <stdio.h>
#include <stdlib.h>#define MAXQSIZE 100  //申请了MAXQSIZE个，可利用空间MAXQSIZE-1个typedef int QElemType;typedef struct
{QElemType* base;int front;int rear;
}SqQueue;void InitQueue(SqQueue& Q);
void ValueQueue(SqQueue& Q);
void printQueue(SqQueue Q);
int QueueLength(SqQueue Q);int  main()
{SqQueue N = { NULL,0,0 };InitQueue(N);ValueQueue(N);printQueue(N);printf("列队长度为：%d\n", QueueLength(N));return 0;
}//算法3.11 循环队列的初始化
void InitQueue(SqQueue& Q)
{Q.base = (QElemType*)malloc(sizeof(QElemType) * MAXQSIZE);//申请了MAXQSIZE个，可利用空间MAXQSIZE-1个if (!Q.base){printf("内存分配失败，导致初始化循环队列失败。");return;}Q.front = 0;Q.rear = 0;printf("初始化循环队列成功。\n");
}//批量元素进入循环队列
void ValueQueue(SqQueue& Q)
{int len = 0;int i = 0;int num = 0;if (!Q.base) {printf("循环队列不存在，元素无法入栈\n");return;}while (1){printf("请输入循环队列的长度：");scanf_s("%d", &len);if (len > MAXQSIZE-1){printf("长度过大，请重新输入。\n");continue;}if(len <= MAXQSIZE-1){break;}}for (i = 1;i <= len; i++){printf("请输入第%d个元素的值：", i);scanf_s("%d", &num);Q.base[Q.rear] = num;Q.rear = (Q.rear+1)%MAXQSIZE;}printf("%d个元素已成功进入循环队列。\n", i-1);
}//打印循环队列并求循环队列的长度
void printQueue(SqQueue Q)
{int i = 0;int temp = Q.front; //打印时不建议直接修改队头的位置Q.front，使用临时变量追踪打印位置if (Q.front == Q.rear){printf("打印循环队列时，队列为空。\n");return;}for (i = 0; i < ((Q.rear - Q.front + MAXQSIZE) % MAXQSIZE); i++)   	//或者是将判断条件改为：i != Q.rear，代表直到i到达了队尾Q.rear的位置即可宣告遍历的结束。{//队头的元素是先被存入队列的，从队头开始打印printf("%d ", Q.base[temp]);temp = (temp + 1) % MAXQSIZE; //临时变量代表的下标在循环队列中依环状增一}printf("\nQueue_length : %d\n",i);/*for循环中i从0开始，对应判断条件中i<长度，对应此处长度为i；for循环中i从1开始，对应判断条件中 i<=长度，对应此处长度为i-1原因：最后一次i加1之后，不执行语句，即跳出循环；下标从0开始，其最大值比长度小1  */
}//算法3.12 求循环队列的长度
int QueueLength(SqQueue Q)
{return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}

在这里插入图片描述

3.5.1.3 循环列队的入队、出队、取队头元素

#include <stdio.h>
#include <stdlib.h>#define MAXQSIZE 100  //申请了MAXQSIZE个，可利用空间MAXQSIZE-1个typedef int QElemType;typedef struct
{QElemType* base;int front;int rear;
}SqQueue;void InitQueue(SqQueue& Q);
void ValueQueue(SqQueue& Q);
void printQueue(SqQueue Q);
int QueueLength(SqQueue Q);
void EnQueue(SqQueue& Q, QElemType e);
int DeQueue(SqQueue& Q);
int GetHead(SqQueue Q);int  main()
{SqQueue N = { NULL,0,0 };InitQueue(N);ValueQueue(N);printQueue(N);printf("\n列队长度为：%d\n", QueueLength(N));EnQueue(N, 999);printQueue(N);printf("\n删除队头元素：%d\n", DeQueue(N));printf("\n新的队头元素：%d\n", GetHead(N));return 0;
}//算法3.11 循环队列的初始化
void InitQueue(SqQueue& Q)
{Q.base = (QElemType*)malloc(sizeof(QElemType) * MAXQSIZE);//申请了MAXQSIZE个，可利用空间MAXQSIZE-1个if (!Q.base){printf("内存分配失败，导致初始化循环队列失败。");return;}Q.front = 0;Q.rear = 0;printf("初始化循环队列成功。\n");
}//批量元素进入循环队列
void ValueQueue(SqQueue& Q)
{int len = 0;int i = 0;int num = 0;if (!Q.base) {printf("循环队列不存在，元素无法入栈\n");return;}while (1){printf("请输入循环队列的长度：");scanf_s("%d", &len);if (len > MAXQSIZE-1){printf("长度过大，请重新输入。\n");continue;}if(len <= MAXQSIZE-1){break;}}for (i = 1;i <= len; i++){printf("请输入第%d个元素的值：", i);scanf_s("%d", &num);Q.base[Q.rear] = num;Q.rear = (Q.rear+1)%MAXQSIZE;}printf("%d个元素已成功进入循环队列。\n", i-1);
}//打印循环队列并求循环队列的长度
void printQueue(SqQueue Q)
{int i = 0;int temp = Q.front; //打印时不建议直接修改队头的位置Q.front，使用临时变量追踪打印位置if (Q.front == Q.rear){printf("打印循环队列时，队列为空。\n");return;}for (i = 0; i < ((Q.rear - Q.front + MAXQSIZE) % MAXQSIZE); i++)   	//或者是将判断条件改为：i != Q.rear，代表直到i到达了队尾Q.rear的位置即可宣告遍历的结束。{//队头的元素是先被存入队列的，从队头开始打印printf("%d ", Q.base[temp]);temp = (temp + 1) % MAXQSIZE; //临时变量代表的下标在循环队列中依环状增一}printf("\nQueue_length : %d\n",i);/*for循环中i从0开始，对应判断条件中i<长度，对应此处长度为i；for循环中i从1开始，对应判断条件中 i<=长度，对应此处长度为i-1原因：最后一次i加1之后，不执行语句，即跳出循环；下标从0开始，其最大值比长度小1  */
}//算法3.12 求循环队列的长度
int QueueLength(SqQueue Q)
{return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}//算法3.13 循环列队的入队
void EnQueue(SqQueue& Q, QElemType e)
{//插入元素e为Q的新的队尾元素if ((Q.rear + 1) % MAXQSIZE == Q.front){printf("入队时，循环队列已满。\n");return;}Q.base[Q.rear] = e;Q.rear = (Q.rear +1)%MAXQSIZE;
}//算法3.14 循环列队的出队
int DeQueue(SqQueue& Q)
{//删除Q的队头元素int e = 0;if (Q.front == Q.rear){printf("删除队头元素时，循环队列为空。\n");return -1;}e = Q.base[Q.front];Q.front = (Q.front+1)%MAXQSIZE;return e;
}//算法3.15 取循环列队的队头元素
int GetHead(SqQueue Q)
{if (Q.front == Q.rear){printf("取队头元素时，循环队列为空。\n");return -1;}return Q.base[Q.front];
}

在这里插入图片描述

3.5.2 链队的表示和操作的实现

#include <stdio.h>
#include <stdlib.h>typedef struct QNode
{int data;struct QNode* next;
}QNode,*QueuePtr;typedef struct
{QueuePtr front;QueuePtr rear;
}LinkQueue;void InitQueue(LinkQueue& Q);
void ValueQueue(LinkQueue& Q);
void printQueue(LinkQueue& Q);
void Enqueue(LinkQueue& Q, int e);
int DeQueue(LinkQueue& Q);
int GetHead(LinkQueue Q);int main()
{LinkQueue N = { NULL,NULL };InitQueue(N);ValueQueue(N);printQueue(N);Enqueue(N,999);printQueue(N);printf("删除的链队的队头元素是：%d\n", DeQueue(N));printQueue(N);printf("\n新的链队的队头元素是：%d", GetHead(N));return 0;
}//算法3.16 链队的初始化
void InitQueue(LinkQueue& Q)
{//构造一个空队列QQ.front = (QueuePtr)malloc(sizeof(QNode)); //生成新结点作为头结点。在链队中头结点可能会被修改，但始终处于队头，且头指针始终指向头结点。//这里分配的内存不能仅是指向结点的指针大小，而应该是指针指向的整个结构体的大小Q.rear = Q.front; //将尾指针指向头结点Q.front->next = NULL;
}//批量元素进入链队
void ValueQueue(LinkQueue& Q)
{int len = 0;int i = 0;int num = 0;printf("请输入链队的长度：");scanf_s("%d", &len);for (i = 1; i <= len; i++){printf("请输入第%d个元素的值：", i);scanf_s("%d", &num);QueuePtr s = (QueuePtr)malloc(sizeof(QNode));s->data = num;s->next = NULL;Q.rear->next = s;Q.rear = s;}printf("%d个元素已入链队成功。\n", i - 1);
}//遍历打印链队
void printQueue(LinkQueue &Q)
{QueuePtr pMove = Q.front->next;int i = 1;while (pMove){printf("%d ", pMove->data);pMove = pMove->next;i++;}printf("\nQueue_length : %d\n", i);
}//算法3.17 链队的入队
void Enqueue(LinkQueue& Q, int e)
{//插入元素e为Q新的队尾元素QueuePtr p = (QueuePtr)malloc(sizeof(QNode));p->data = e;p->next = NULL;Q.rear->next = p;Q.rear = p;
}//算法3.18 链队的出队
int DeQueue(LinkQueue& Q)
{if (Q.front == Q.rear){printf("删除队头元素时，链队为空。\n");return -1;}QueuePtr p = Q.front->next;int e = p->data;Q.front->next = p->next;/*当链队中只有一个数值时，此时p和rear指向同一个结点。为了避免p所指结点的内存空间被释放之后rear失去指向的对象，要先将尾指针rear指向头结点。删除唯一的队头元素后，链队变为空。*/if (Q.rear == p){Q.rear = Q.front;}free(p);return e;
}//算法3.19 取链队的队头元素
int GetHead(LinkQueue Q)
{if (Q.front == Q.rear){printf("取队头元素时，链队为空。\n");return -1;}return Q.front->next->data;
}

在这里插入图片描述

这篇关于《数据结构（C语言版）第二版》第三章-栈和队列（3.5 队列的表示和操作的实现）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/964593。

相关文章

Python的Darts库实现时间序列预测

Python的Darts库实现时间序列预测

《Python的Darts库实现时间序列预测》Darts一个集统计、机器学习与深度学习模型于一体的Python时间序列预测库,本文主要介绍了Python的Darts库实现时间序列预测,感兴趣的可以了解... 目录目录一、什么是 Darts？二、安装与基本配置安装 Darts导入基础模块三、时间序列数据结构与
阅读更多...
Python正则表达式匹配和替换的操作指南

Python正则表达式匹配和替换的操作指南

《Python正则表达式匹配和替换的操作指南》正则表达式是处理文本的强大工具,Python通过re模块提供了完整的正则表达式功能,本文将通过代码示例详细介绍Python中的正则匹配和替换操作,需要的朋... 目录基础语法导入re模块基本元字符常用匹配方法1. re.match() - 从字符串开头匹配2.
阅读更多...
Python使用FastAPI实现大文件分片上传与断点续传功能

Python使用FastAPI实现大文件分片上传与断点续传功能

《Python使用FastAPI实现大文件分片上传与断点续传功能》大文件直传常遇到超时、网络抖动失败、失败后只能重传的问题,分片上传+断点续传可以把大文件拆成若干小块逐个上传,并在中断后从已完成分片继... 目录一、接口设计二、服务端实现（FastAPI）2.1 运行环境2.2 目录结构建议2.3 serv
阅读更多...
C#实现千万数据秒级导入的代码

C#实现千万数据秒级导入的代码

《C#实现千万数据秒级导入的代码》在实际开发中excel导入很常见,现代社会中很容易遇到大数据处理业务,所以本文我就给大家分享一下千万数据秒级导入怎么实现,文中有详细的代码示例供大家参考,需要的朋友可... 目录前言一、数据存储二、处理逻辑优化前代码处理逻辑优化后的代码总结前言在实际开发中excel导入很
阅读更多...
SpringBoot+RustFS 实现文件切片极速上传的实例代码

SpringBoot+RustFS 实现文件切片极速上传的实例代码

《SpringBoot+RustFS实现文件切片极速上传的实例代码》本文介绍利用SpringBoot和RustFS构建高性能文件切片上传系统,实现大文件秒传、断点续传和分片上传等功能,具有一定的参考... 目录一、为什么选择 RustFS + SpringBoot？二、环境准备与部署2.1 安装 RustF
阅读更多...
Nginx部署HTTP/3的实现步骤

Nginx部署HTTP/3的实现步骤

《Nginx部署HTTP/3的实现步骤》本文介绍了在Nginx中部署HTTP/3的详细步骤,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录前提条件第一步：安装必要的依赖库第二步：获取并构建 BoringSSL第三步：获取 Nginx
阅读更多...
MyBatis Plus实现时间字段自动填充的完整方案

MyBatis Plus实现时间字段自动填充的完整方案

《MyBatisPlus实现时间字段自动填充的完整方案》在日常开发中,我们经常需要记录数据的创建时间和更新时间,传统的做法是在每次插入或更新操作时手动设置这些时间字段,这种方式不仅繁琐,还容易遗漏,... 目录前言解决目标技术栈实现步骤1. 实体类注解配置2. 创建元数据处理器3. 服务层代码优化填充机制详
阅读更多...
Python实现Excel批量样式修改器(附完整代码)

Python实现Excel批量样式修改器(附完整代码)

《Python实现Excel批量样式修改器(附完整代码)》这篇文章主要为大家详细介绍了如何使用Python实现一个Excel批量样式修改器,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一... 目录前言功能特性核心功能界面特性系统要求安装说明使用指南基本操作流程高级功能技术实现核心技术栈关键函
阅读更多...
Java实现字节字符转bcd编码

Java实现字节字符转bcd编码

《Java实现字节字符转bcd编码》BCD是一种将十进制数字编码为二进制的表示方式,常用于数字显示和存储,本文将介绍如何在Java中实现字节字符转BCD码的过程,需要的小伙伴可以了解下... 目录前言BCD码是什么Java实现字节转bcd编码方法补充总结前言BCD码（Binary-Coded Decima
阅读更多...
SpringBoot全局域名替换的实现

SpringBoot全局域名替换的实现

《SpringBoot全局域名替换的实现》本文主要介绍了SpringBoot全局域名替换的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录 项目结构⚙️ 配置文件application.yml️ 配置类AppProperties.Ja
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2