【数据结构初阶】六、线性表中的队列(C语言 -- 链式结构实现队列)

=========================================================================

相关代码gitee自取

C语言学习日记: 加油努力 (gitee.com)

 =========================================================================

接上期

【数据结构初阶】五、线性表中的栈(C语言 -- 顺序表实现栈)_高高的胖子的博客-CSDN博客

 =========================================================================

                     

1 . 队列(Queue)

队列的概念和结构:

队列的概念

  • 队列是一种只允许在一端执行插入数据操作另一端进行删除数据操作特殊线性表
                      
  • 入队列 -- 进行插入操作的一端称为队尾
    出队列 -- 进行删除操作的一端称为队头

                
  • 队列中的数据元素遵守
    先进先出FIFO -- First In First Out)的原则 -- 先进入的元素会先出来
    所以可以应用在公平性排队(抽号机)、BFS(广度优先遍历)
                        

队列的结构

         

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

             

2 . 队列的实现

                

使用 顺序表(数组)链表(链式结构) 都可以实现队列

使用顺序表的话,入队列比较简单,但在出队列时需要删除和挪动数据效率较低

所以下面用链表(链式结构)实现队列  --  单向 + 无头 + 非循环 链表

入队 -- 单链表尾部插入(尾插)         ;      出队 -- 单链表头部删除(头删)

               

(详细解释在图片的注释中,代码分文件放下一标题处)

               

实现具体功能前的准备工作

  • 定义队列(链式结构)中数据域存储的数据类型
                               
  • 定义队列(链式结构)结点类型
    包含 队列指针域 队列数据域
                 
  • 定义队列类型
    包含 头结点指针尾结点指针 和 队列结点(元素)个数
图示

            

            

---------------------------------------------------------------------------------------------

            

QueueInit函数 -- 将队列进行初始化

  • assert断言队列类型指针不为空
                               
  • 队头结点置为空
    队尾结点置为空
    队列结点(元素)个数置为0
图示

            

            

---------------------------------------------------------------------------------------------

            

QueueDestroy函数 -- 将队列销毁

  • assert断言队列类型指针不为空
                               
  • 创建一个在队列进行遍历的指针cur
    使用while循环进行遍历释放队列结点
                 
  • 结点都释放后,把队头队尾指针都置空
                   
  • 再把队列结点(元素)个数置为0
图示

            

            

---------------------------------------------------------------------------------------------

            

QueuePush函数 -- 用链表的尾插操作实现入队

  • assert断言队列类型指针不为空
                               
  • 为队列结点开辟动态空间检查空间开辟情况
                 
  • 结点开辟成功
    尾插值(x)赋给队列结点的数据域并将指针域置为空
                   
  • 空间开辟后进行尾插
    如果队列刚初始化队列为空,将刚开辟的结点newnode地址赋给头尾结点指针
    队列不为空正常进行尾插操作
                
  • 插入数据后队列结点(元素)个数++
图示

            

            

---------------------------------------------------------------------------------------------

            

QueuePop函数 -- 用链表的头删操作实现出队

  • assert断言队列类型指针不为空队列不为空
                               
  • 出队(头删)分两种情况
    队列中只剩一个结点 -- 头删后头指针移动尾指针也要移动
    队列不止一个结点 -- 头删后只需移动队头结点
                 
  • 删除队列结点(元素)个数--
图示

            

            

---------------------------------------------------------------------------------------------

            

QueueFront函数 -- 返回队头结点的数据域数据

  • assert断言队列类型指针不为空队列不为空
                               
  • 队列有数据,则直接返回队头结点数据域数据
图示

            

            

---------------------------------------------------------------------------------------------

            

QueueBack函数 -- 返回队尾结点的数据域数据

  • assert断言队列类型指针不为空队列不为空
                               
  • 队列有数据,则直接返回队尾结点数据域数据
图示

            

            

---------------------------------------------------------------------------------------------

            

QueueEmpty函数 -- 判断队列是否为空

  • assert断言队列类型指针不为空
                               
  • 直接判断队头结点指向的下个结点是否为空直接返回判断结果
图示

            

            

---------------------------------------------------------------------------------------------

            

QueueSize函数 -- 判断队列结点(元素)个数

  • assert断言队列类型指针不为空
                               
  • 直接返回size队列结点(元素)个数
图示

            

            

---------------------------------------------------------------------------------------------

            

总体测试:

         

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

             

3 . 对应代码

Queue.h -- 队列头文件

#pragma once//包含之后需要的头文件:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>//以链表(链式结构)实现队列:
//双向+循环 的链表可以解决找尾结点的问题,
//定义一个尾指针也可以解决该问题,
//哨兵位 可以解决二级指针的问题,
//且尾插时可以少一层判断,但还有方法可以解决//定义队列(链式结构)中数据域存储的数据类型:
typedef int QDataType;//定义队列(链式结构)结点类型:
typedef struct QueueNode
{//队列指针域:struct QueueNode* next;//队列数据域:QDataType data;}QNode; //将类型重命名为Qnode//定义队列类型:
typedef struct Queue
{//因为用链表尾插实现入队,//用链表头删实现出队,//那么就需要头结点和尾结点的指针,//所以可以直接将这两个指针封装为一个类型,//队列类型://头结点指针:QNode* head;//尾结点指针:QNode* tail;//记录队列结点(元素)个数:int size; //这样之后在出队和入队操作时,//就不需要用到二级指针,//直接接收这个结构体指针,//通过结构体指针运用结构体里的头尾结点指针,//再用头尾结点指针定义头尾结点//来实现 二级指针、带哨兵位头结点 和 返回值 的作用//所以现在已知的通过指针定义结点的方法就有4种://		1. 结构体包含结点指针//		2. 二级指针调用结点指针//		3. 哨兵位头结点指针域next指向结点地址//		4. 返回值返回改变的结点指针}Que; //重命名为Que//队列初始化函数 -- 将队列进行初始化
//接收队列类型指针(包含链表头尾结点) 
void QueueInit(Que* pq);//队列销毁函数 -- 将队列销毁
//接收队列类型指针(包含链表头尾结点) 
void QueueDestroy(Que* pq);//队列入队函数 -- 用链表的尾插操作实现入队
//接收队列类型指针(包含链表头尾结点) 、尾插值
void QueuePush(Que* pq, QDataType x);//队列出队函数 -- 用链表的头删操作实现出队
//接收队列类型指针(包含链表头尾结点) 
void QueuePop(Que* pq);//队头函数 -- 返回队头结点的数据域数据
//接收队列类型指针(包含链表头尾结点) 
QDataType QueueFront(Que* pq);//队尾函数 -- 返回队尾结点的数据域数据
//接收队列类型指针(包含链表头尾结点) 
QDataType QueueBack(Que* pq);//判空函数 -- 判断队列是否为空
//接收队列类型指针(包含链表头尾结点) 
bool QueueEmpty(Que* pq);//队列大小函数 -- 判断队列结点(元素)个数
//接收队列类型指针(包含链表头尾结点) 
int QueueSize(Que* pq);

            

            

---------------------------------------------------------------------------------------------

                

Queue.c -- 队列函数实现文件

#define _CRT_SECURE_NO_WARNINGS 1//包含队列头文件:
#include "Queue.h"//队列初始化函数 -- 将队列进行初始化
//接收队列类型指针(包含链表头尾结点) 
void QueueInit(Que* pq)
{//assert断言队列类型指针不为空:assert(pq != NULL);//将队头结点置为空:pq->head = NULL;//将队尾结点置为空:pq->tail = NULL;//队列结点(元素)个数置为0:pq->size = 0;
}//队列销毁函数 -- 将队列销毁
//接收队列类型指针(包含链表头尾结点) 
void QueueDestroy(Que* pq)
{//assert断言队列类型指针不为空:assert(pq != NULL);//释放队列跟单链表的释放一样//先创建一个在队列进行遍历的指针:QNode* cur = pq->head; //从队头结点开始//使用while循环进行遍历释放队列结点:while (cur != NULL)	{//先保存下个结点:QNode* next = cur->next;//再释放当前结点:free(cur);//再指向下个结点:cur = next;}//结点都释放后,把队头队尾指针都置空:pq->head = NULL;pq->tail = NULL;//再把队列结点(元素)个数置为0:pq->size = 0;
}//队列入队函数 -- 用链表的尾插操作实现入队
//接收队列类型指针(包含链表头尾结点) 、尾插值
void QueuePush(Que* pq, QDataType x)
{//assert断言队列类型指针不为空:assert(pq != NULL);//入队放入元素需要空间,//所以要先为队列结点开辟动态空间:QNode* newnode = (QNode*)malloc(sizeof(QNode));//检查是否开辟成功:if (newnode == NULL){//开辟失败则打印错误信息:perror("malloc fail");//终止程序:exit(-1);}//队列结点完成后将尾插值(x)//赋给队列结点数据域:newnode->data = x;//指针域指向空:newnode->next = NULL;//空间开辟后进行尾插:if (pq->tail == NULL)//如果队列刚初始化,队列为空,//头结点指针和尾结点指针都为空:{//那么将刚开辟的结点newnode地址//赋给头结点指针和尾结点指针pq->head = newnode;pq->tail = newnode;}else//队列不为空,进行尾插:{//将目前队尾结点指针域next指向尾插结点:pq->tail->next = newnode;//然后再指向尾插结点,成为新队尾结点:pq->tail = newnode;}//插入数据后队列结点(元素)个数++:pq->size++;
}//队列出队函数 -- 用链表的头删操作实现出队
//接收队列类型指针(包含链表头尾结点) 
void QueuePop(Que* pq)
{//assert断言队列类型指针不为空:assert(pq != NULL);//assert断言队列不为空,没数据不能删除:  assert(QueueEmpty != true); //不为空就继续程序//如果队列中只剩一个结点:if (pq->head->next == NULL)//队头指针指向空,说明只剩一个结点,//只剩一个结点说明队头队尾指针都指向这一个结点,//所以这时头删后头指针移动,尾指针也要移动{//先释放("删除")队列目前头结点:free(pq->head);//删除后将队头队尾指针都置为空:pq->head = NULL;pq->tail = NULL;}else//队列不止一个结点,则头删后只需移动队头结点:{//用链表的头删操作实现出队,//先保存第二个结点地址:QNode* next = pq->head->next;//释放("删除")队列目前头结点:free(pq->head);//再将队头结点指针指向原本第二个结点next,//让其成为新的队头结点:pq->head = next;}//“删除”后队列结点(元素)个数--:pq->size--; 
}//队头函数 -- 返回队头结点的数据域数据
//接收队列类型指针(包含链表头尾结点) 
QDataType QueueFront(Que* pq)
{//assert断言队列类型指针不为空:assert(pq != NULL);//assert断言队列不为空,没数据不能查找:  assert(QueueEmpty != true); //不为空就继续程序//队列有数据,则直接返回队头结点数据域数据:return pq->head->data;
}//队尾函数 -- 返回队尾结点的数据域数据
//接收队列类型指针(包含链表头尾结点) 
QDataType QueueBack(Que* pq)
{//assert断言队列类型指针不为空:assert(pq != NULL);//assert断言队列不为空,没数据不能查找:  assert(QueueEmpty != true); //不为空就继续程序//队列有数据,则直接返回队尾结点数据域数据:return pq->tail->data;
}//判空函数 -- 判断队列是否为空
//接收队列类型指针(包含链表头尾结点) 
bool QueueEmpty(Que* pq)
{//assert断言队列类型指针不为空:assert(pq != NULL);//直接判断队头结点指向的下个结点是否为空:return pq->head == NULL; //是则返回true -- 队列为空//是则返回false -- 队列不为空
}//队列大小函数 -- 判断队列结点(元素)个数
//接收队列类型指针(包含链表头尾结点) 
int QueueSize(Que* pq)
{//assert断言队列类型指针不为空:assert(pq != NULL);//直接返回size队列结点(元素)个数:return pq->size;
}

            

            

---------------------------------------------------------------------------------------------

                

Test.c -- 队列测试文件

#define _CRT_SECURE_NO_WARNINGS 1//包含队列头文件:
#include "Queue.h"//队列测试函数:
void TestQueue()
{//创建队列类型:Que q;//对队列类型进行初始化:QueueInit(&q);//进行入队操作:QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);QueuePush(&q, 5);//当前队尾值:printf("当前队尾值:%d\n", QueueBack(&q));//当前队列元素个数:printf("当前队列元素个数:%d\n", QueueSize(&q));//换行:printf("\n");//使用while循环遍历进行出队://(类似抽号机,当前号抽完就到下个号)while (!QueueEmpty(&q))//队列不为空就继续出队:{//打印出队值:printf("当前出队值为:%d\n", QueueFront(&q));//进行出队:QueuePop(&q); //出队后打印下个出队值}//换行:printf("\n");//当前队列元素个数:printf("当前队列元素个数:%d", QueueSize(&q));//销毁队列:QueueDestroy(&q);
}//主函数:
int main()
{//调用队列测试函数:TestQueue();return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/147328.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Linux】文件权限详解

&#x1f341; 博主 "开着拖拉机回家"带您 Go to New World.✨&#x1f341; &#x1f984; 个人主页——&#x1f390;开着拖拉机回家_Linux,Java基础学习,大数据运维-CSDN博客 &#x1f390;✨&#x1f341; &#x1fa81;&#x1f341; 希望本文能够给您带来一定的…

国庆作业6

TCP服务器 #include "head.h" #define PORT 2580 //端口号 #define IP "192.168.31.219" //本机IP int main(int argc, const char *argv[]) {sqlite3* dbNULL;if(sqlite3_open("./my.db",&db)!SQLITE_OK){fprintf(stde…

Java 随机数的获得方法(5种)

1. Math.random() 静态方法 产生的随机数是 0 - 1 之间的一个 double&#xff0c;即 0 < random < 1 代码&#xff1a; 结果&#xff1a; 当调用 Math.random() 方法时&#xff0c;自动创建了一个伪随机数生成器&#xff0c;实际上用的是 new java.util.Random()。当接…

pwnable_hacknote

pwnable_hacknote Arch: i386-32-little RELRO: Partial RELRO Stack: Canary found NX: NX enabled PIE: No PIE (0x8047000)32位&#xff0c;没开PIE main部分就不贴了&#xff0c;直接贴主要的函数 unsigned int ADD() {int v0; // ebxint i; // [e…

【Kafka专题】Kafka快速实战以及基本原理详解

目录 前言课程内容一、Kafka介绍1.1 MQ的作用1.2 为什么用Kafka 二、Kafka快速上手2.1 实验环境2.2 单机服务体验2.3 认识Kafka模型架构2.4 Kafka集群2.5 理解服务端的Topic、Partion和Broker2.6 章节总结&#xff1a;Kafka集群的整体结构 三、Kraft集群&#xff08;拓展&#…

【计算机网络】高级IO之select

文章目录 1. 什么是IO&#xff1f;什么是高效 IO? 2. IO的五种模型五种IO模型的概念理解同步IO与异步IO整体理解 3. 阻塞IO4. 非阻塞IOsetnonblock函数为什么非阻塞IO会读取错误&#xff1f;对错误码的进一步判断检测数据没有就绪时&#xff0c;返回做一些其他事情完整代码myt…

Linux和本地Windows如何互传文件(sz和rz指令)

目录 关于 rzsz 注意事项 安装软件 rz的使用&#xff08;本地主机文件传到Windows中&#xff09; sz的使用(Linux中的文件传到本地Windows主机中) 关于 rzsz 这个工具用于 windows 机器和远端的 Linux 机器通过 XShell 传输文件. 安装完毕之后可以通过直接拖拽的方式将文件…

【源码】hamcrest 源码阅读及空对象模式、模板方法模式的应用

文章目录 前言1. 类图概览2. 源码阅读2.1 抽象类 BaseMatcher2.1 接口 Description提炼模式&#xff1a;空对象模式 2. 接口 Description 与 SelfDescribing 配合使用提炼模式 模板方法 后记 前言 hamcrest &#xff0c;一个被多个测试框架依赖的包。听说 hamcrest 的源码质量…

Linux性能优化--性能工具:系统内存

3.0.概述 本章概述了系统级的Linux内存性能工具。本章将讨论这些工具可以测量的内存统计信息&#xff0c;以及如何使用各种工具收集这些统计结果。阅读本章后&#xff0c;你将能够&#xff1a; 理解系统级性能的基本指标&#xff0c;包括内存的使用情况。明白哪些工具可以检索…

解决u盘在我的电脑中重复显示两个

删除注册表&#xff1a; [HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Explorer\Desktop\NameSpace\DelegateFolders\{F5FB2C77-0E2F-4A16-A381-3E560C68BC83}]

910数据结构(2019年真题)

算法设计题 问题1 有一种排序算法叫做计数排序。这种排序算法对一个待排序的表&#xff08;采用顺序存储&#xff09;进行排序&#xff0c;并将排序结果存放到另一个新的表中。必须注意的是&#xff0c;表中所有待排序的关键字互不相同&#xff0c;计数排序算法针对表中的每个…

视频增强修复工具Topaz Video AI mac中文版安装教程

Topaz Video AI mac是一款使用人工智能技术对视频进行增强和修复的软件。它可以自动降噪、去除锐化、减少压缩失真、提高清晰度等等。Topaz Video AI可以处理各种类型的视频&#xff0c;包括低分辨率视频、老旧影片、手机录制的视频等等。 使用Topaz Video AI非常简单&#xff…

5-1.(OOP)初步分析MCV架构模式

组成&#xff1a;模型&#xff08;model&#xff09;、视图&#xff08;view&#xff09;、控制器&#xff08;controller&#xff09; view&#xff1a;界面、显示数据 model&#xff1a;数据管理、负责在数据库中存取数据以及数据合法性验证 controller&#xff1a;负责转…

Python大数据之PySpark(四)SparkBaseCore

文章目录 SparkBase&Core环境搭建-Spark on YARN扩展阅读-Spark关键概念[了解]PySpark角色分析[了解]PySpark架构后记 SparkBase&Core 学习目标掌握SparkOnYarn搭建掌握RDD的基础创建及相关算子操作了解PySpark的架构及角色 环境搭建-Spark on YARN Yarn 资源调度框…

Linux 下如何调试代码

debug 和 release 在Linux下的默认模式是什么&#xff1f; 是release模式 那你怎么证明他就是release版本? 我们知道如果一个程序可以被调试&#xff0c;那么它一定是debug版本&#xff0c;如果它是release版本&#xff0c;它是没法被调试的&#xff0c;所以说我们可以来调试一…

FPGA project : TFT_LCD

实验目标&#xff1a; 驱动TFT_LCD显示十色彩条。 重点掌握的知识&#xff1a; 1&#xff0c;液晶显示器&#xff0c;简称LCD(Liquid Crystal Display)&#xff0c;相对于上一代CRT显示器(阴极射线管显示器)&#xff0c;LCD显示器具有功耗低、体积小、承载的信息量大及不伤眼…

王道考研操作系统——I/O管理

I/O设备的基本概念 键盘&#xff1a;输入设备&#xff08;把设备准备好的数据读入计算机当中&#xff09;&#xff1b; 显示器&#xff1a;输出设备&#xff08;把计算机中准备好的数据写出到设备上&#xff09;&#xff1b; 移动硬盘&#xff1a;既是输入又是输出 中断驱动…

数据挖掘(2)数据预处理

一、数据预处理 1.1概述 数据预处理的重要性 杂乱性&#xff1a;如命名规则。重复性&#xff1a;同一客观事再不完整性&#xff1a;噪声数据&#xff1a;数据中存在错误或异常的现象。 数据预处理的常见方法 数据清洗&#xff1a;去掉数据中的噪声&#xff0c;纠正不一致。数…

HTML的学习 Day02(列表、表格、表单)

文章目录 一、列表列表主要分为以下三种类型&#xff1a;1. 无序列表&#xff08;Unordered List&#xff09;&#xff1a;2. 有序列表&#xff08;Ordered List&#xff09;&#xff1a;将有序列表的数字改为字母或自定义内容li.../li 列表项标签中value属性&#xff0c;制定列…

OpenCV实现视频的追踪(meanshift、Camshift)

目录 1&#xff0c;meanshift 1.1 算法流程 1.2 算法实现 1.3 代码实现 1.4 结果展示 1&#xff0c;meanshift 1.1 算法流程 1.2 算法实现 1.3 代码实现 import numpy as np import cv2 as cv# 读取视频 cap cv.VideoCapture(video.mp4)# 检查视频是否成功打开 if n…