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

相关文章

mybatis执行insert返回id实现详解

mybatis执行insert返回id实现详解

《mybatis执行insert返回id实现详解》MyBatis插入操作默认返回受影响行数,需通过useGeneratedKeys+keyProperty或selectKey获取主键ID,确保主键为自... 目录 两种方式获取自增 ID：1. ​​useGeneratedKeys+keyProperty（推
阅读更多...
Spring Boot集成Druid实现数据源管理与监控的详细步骤

Spring Boot集成Druid实现数据源管理与监控的详细步骤

《SpringBoot集成Druid实现数据源管理与监控的详细步骤》本文介绍如何在SpringBoot项目中集成Druid数据库连接池,包括环境搭建、Maven依赖配置、SpringBoot配置文件... 目录1. 引言1.1 环境准备1.2 Druid介绍2. 配置Druid连接池3. 查看Druid监控
阅读更多...
Linux在线解压jar包的实现方式

Linux在线解压jar包的实现方式

《Linux在线解压jar包的实现方式》：本文主要介绍Linux在线解压jar包的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux在线解压jar包解压 jar包的步骤总结Linux在线解压jar包在 Centos 中解压 jar 包可以使用 u
阅读更多...
c++ 类成员变量默认初始值的实现

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中，如果使用类成员变量时未给定其初始值，那么它将被
阅读更多...
Qt使用QSqlDatabase连接MySQL实现增删改查功能

Qt使用QSqlDatabase连接MySQL实现增删改查功能

《Qt使用QSqlDatabase连接MySQL实现增删改查功能》这篇文章主要为大家详细介绍了Qt如何使用QSqlDatabase连接MySQL实现增删改查功能,文中的示例代码讲解详细,感兴趣的小伙伴... 目录一、创建数据表二、连接mysql数据库三、封装成一个完整的轻量级 ORM 风格类3.1 表结构
阅读更多...
基于Python实现一个图片拆分工具

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片，默认是输出到项目文件夹中，可以自己选择其他的文件夹，选择需要拆分的行数和列数，可以通过
阅读更多...
Python中将嵌套列表扁平化的多种实现方法

Python中将嵌套列表扁平化的多种实现方法

《Python中将嵌套列表扁平化的多种实现方法》在Python编程中,我们常常会遇到需要将嵌套列表（即列表中包含列表）转换为一个一维的扁平列表的需求,本文将给大家介绍了多种实现这一目标的方法,需要的朋... 目录python中将嵌套列表扁平化的方法技术背景实现步骤1. 使用嵌套列表推导式2. 使用itert
阅读更多...
Java操作Word文档的全面指南

Java操作Word文档的全面指南

《Java操作Word文档的全面指南》在Java开发中,操作Word文档是常见的业务需求,广泛应用于合同生成、报表输出、通知发布、法律文书生成、病历模板填写等场景,本文将全面介绍Java操作Word文... 目录简介段落页头与页脚页码表格图片批注文本框目录图表简介Word编程最重要的类是org.apach
阅读更多...
Python使用pip工具实现包自动更新的多种方法

Python使用pip工具实现包自动更新的多种方法

《Python使用pip工具实现包自动更新的多种方法》本文深入探讨了使用Python的pip工具实现包自动更新的各种方法和技术,我们将从基础概念开始,逐步介绍手动更新方法、自动化脚本编写、结合CI/C... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核
阅读更多...
在Linux中改变echo输出颜色的实现方法

在Linux中改变echo输出颜色的实现方法

《在Linux中改变echo输出颜色的实现方法》在Linux系统的命令行环境下,为了使输出信息更加清晰、突出,便于用户快速识别和区分不同类型的信息,常常需要改变echo命令的输出颜色,所以本文给大家介... 目python录在linux中改变echo输出颜色的方法技术背景实现步骤使用ANSI转义码使用tpu
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2