《数据结构（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调用Orator ORM进行数据库操作

Python调用Orator ORM进行数据库操作

《Python调用OratorORM进行数据库操作》OratorORM是一个功能丰富且灵活的PythonORM库,旨在简化数据库操作,它支持多种数据库并提供了简洁且直观的API,下面我们就... 目录Orator ORM 主要特点安装使用示例总结Orator ORM 是一个功能丰富且灵活的 python O
阅读更多...
Java实现检查多个时间段是否有重合

Java实现检查多个时间段是否有重合

《Java实现检查多个时间段是否有重合》这篇文章主要为大家详细介绍了如何使用Java实现检查多个时间段是否有重合,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录流程概述步骤详解China编程步骤1：定义时间段类步骤2：添加时间段步骤3：检查时间段是否有重合步骤4：输出结果示例代码结语作
阅读更多...
使用C++实现链表元素的反转

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定
阅读更多...
Java覆盖第三方jar包中的某一个类的实现方法

Java覆盖第三方jar包中的某一个类的实现方法

《Java覆盖第三方jar包中的某一个类的实现方法》在我们日常的开发中,经常需要使用第三方的jar包,有时候我们会发现第三方的jar包中的某一个类有问题,或者我们需要定制化修改其中的逻辑,那么应该如何... 目录一、需求描述二、示例描述三、操作步骤四、验证结果五、实现原理一、需求描述需求描述如下：需要在
阅读更多...
如何使用Java实现请求deepseek

如何使用Java实现请求deepseek

《如何使用Java实现请求deepseek》这篇文章主要为大家详细介绍了如何使用Java实现请求deepseek功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1.deepseek的api创建2.Java实现请求deepseek2.1 pom文件2.2 json转化文件2.2
阅读更多...
python使用fastapi实现多语言国际化的操作指南

python使用fastapi实现多语言国际化的操作指南

《python使用fastapi实现多语言国际化的操作指南》本文介绍了使用Python和FastAPI实现多语言国际化的操作指南,包括多语言架构技术栈、翻译管理、前端本地化、语言切换机制以及常见陷阱和... 目录多语言国际化实现指南项目多语言架构技术栈目录结构翻译工作流1. 翻译数据存储2. 翻译生成脚本
阅读更多...
如何通过Python实现一个消息队列

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque
阅读更多...
Python如何实现PDF隐私信息检测

Python如何实现PDF隐私信息检测

《Python如何实现PDF隐私信息检测》随着越来越多的个人信息以电子形式存储和传输,确保这些信息的安全至关重要,本文将介绍如何使用Python检测PDF文件中的隐私信息,需要的可以参考下... 目录项目背景技术栈代码解析功能说明运行结php果在当今，数据隐私保护变得尤为重要。随着越来越多的个人信息以电子形
阅读更多...
使用 sql-research-assistant进行 SQL 数据库研究的实战指南(代码实现演示)

使用 sql-research-assistant进行 SQL 数据库研究的实战指南(代码实现演示)

《使用sql-research-assistant进行SQL数据库研究的实战指南(代码实现演示)》本文介绍了sql-research-assistant工具,该工具基于LangChain框架,集... 目录技术背景介绍核心原理解析代码实现演示安装和配置项目集成LangSmith 配置（可选）启动服务应用场景
阅读更多...
使用Python快速实现链接转word文档

使用Python快速实现链接转word文档

《使用Python快速实现链接转word文档》这篇文章主要为大家详细介绍了如何使用Python快速实现链接转word文档功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 演示代码展示from newspaper import Articlefrom docx import
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2