《数据结构（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。

相关文章

闲置电脑也能活出第二春？鲁大师AiNAS让你动动手指就能轻松部署

闲置电脑也能活出第二春？鲁大师AiNAS让你动动手指就能轻松部署

对于大多数人而言，在这个“数据爆炸”的时代或多或少都遇到过存储告急的情况，这使得“存储焦虑”不再是个别现象，而将会是随着软件的不断臃肿而越来越普遍的情况。从不少手机厂商都开始将存储上限提升至1TB可以见得，我们似乎正处在互联网信息飞速增长的阶段，对于存储的需求也将会不断扩大。对于苹果用户而言，这一问题愈发严峻，毕竟512GB和1TB版本的iPhone可不是人人都消费得起的，因此成熟的外置存储方案开
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
hdu1180（广搜+优先队列）

hdu1180（广搜+优先队列）

此题要求最少到达目标点T的最短时间，所以我选择了广度优先搜索，并且要用到优先队列。 另外此题注意点较多，比如说可以在某个点停留，我wa了好多两次，就是因为忽略了这一点，然后参考了大神的思想，然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...
C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

哈喽，你好啊，我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记，这是第6篇； 接下来实现实时显示当前选中红球数量，蓝球数量； 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时，在对应的位置显示实时已选择的红球、蓝球的数量； 02 标签名称 分别设置Label标签名称为：lblRedCount、lblBlueCount
阅读更多...
4B参数秒杀GPT-3.5：MiniCPM 3.0惊艳登场！

4B参数秒杀GPT-3.5：MiniCPM 3.0惊艳登场！

​ 面壁智能 在 AI 的世界里，总有那么几个时刻让人惊叹不已。面壁智能推出的 MiniCPM 3.0，这个仅有4B参数的"小钢炮"，正在以惊人的实力挑战着 GPT-3.5 这个曾经的AI巨人。 MiniCPM 3.0 MiniCPM 3.0 MiniCPM 3.0 目前的主要功能有： 长上下文功能：原生支持 32k 上下文长度，性能完美。我们引入了
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2