数据结构C语言描述5(图文结合)--队列,数组、链式、优先队列的实现

前言

  • 这个专栏将会用纯C实现常用的数据结构和简单的算法;
  • 有C基础即可跟着学习,代码均可运行;
  • 准备考研的也可跟着写,个人感觉,如果时间充裕,手写一遍比看书、刷题管用很多,这也是本人采用纯C语言实现的原因之一;
  • 欢迎收藏 + 关注,本人将会持续更新。

文章目录

    • 什么是队列
    • 队列基本操作
    • 队列的数组实现
    • 队列的链表实现
    • 双端队列
    • 优先队列简介

什么是队列

队列(Queue)也是一种运算受限的线性表,它限定在表的一端进行插入操作,在表的另一端进行删除操作。队列的结构特性是:先进先出FIFO ( First In First Out)。队列又被称为先进先出表。

队尾:允许插入的一端称作队尾(Rear)

队首:允许删除的一端称作队首(Front)

在这里插入图片描述

队列为空的时候 队头front和队尾tail都是0的位置,入队的时候队尾tail往后移动,出队的时候front往队列tail靠拢

因为front的移动,导致数组队列存在伪溢出现象,可以通过循环队列的方式解决伪溢出问题。

伪溢出:不是实际的的内存越界,只是队头下标比队尾下标前。

在这里插入图片描述

链式队列可以通过无表头链表记录头尾的方式实现,插入队列用表尾法插入,遍历表头法删除写法

队列基本操作

  • 创建栈
  • 入队
  • 出队
  • 获取队头元素
  • 队列是否为空
  • 队列元素个数

队列的数组实现

数组队列,就是数组模拟队列,实现方法有很多,这里也只是一种方法。

🚸队列封装

  • 数组队列实现是用过移动队头、队尾下标实现的,故核心在于front、tail的理解。
  • 数组采用扩容的方法存储数组。
typedef int DataType;
typedef struct Queue {DataType* data;int front, tail;int capacity;
}Queue;

🖍 创建队列(初始化)

这一步就是创建队列,为队列申请一块内存,并且初始化队列,注意,这里需要将tail赋值为-1 为什么呢? 这个可以随着看代码体会。

Queue* create_queue()
{Queue* queue = (Queue*)calloc(1, sizeof(Queue));assert(queue);queue->tail = -1;return queue;
}

🌓 入队

  • ++tail,采用后置++的方法从队尾巴插入,这里应该就能理解为什么要将tail赋值为-1
  • 注意:容量不够需要扩容。
void push(Queue* queue, DataType data)
{assert(queue);// 扩容if (queue->front == -1 || (queue->front >= queue->capacity)) {DataType* temp = (DataType*)realloc(queue->data, queue->capacity + 10);assert(temp);queue->data = temp;queue->capacity += 10;}queue->data[++queue->tail] = data;
}

✴️ 出队

  • 就是移动front,因为数组无法单独删除一个元素;
  • 注意:队列为空的情况,front>tail
void pop(Queue* queue)
{assert(queue);if (queue->front <= queue->tail) {queue->front++;}
}

🤕 获取对头元素

  • 这个就是通过数组下标直接获取即可。
DataType top(Queue* queue)
{assert(queue);return queue->data[queue->front];
}

🚄 万金油函数:队列大小、是否为空

  • 获取大小:注意获取的是大小,不是下标;
  • 判断是否为空:就是对头和队尾的下标对比。
int size(Queue* queue)
{assert(queue);return queue->tail + 1;
}bool empty(Queue* queue)
{assert(queue);return queue->tail < queue->front;
}

⚗️ 总代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>typedef int DataType;typedef struct Queue {DataType* data;int front, tail;int capacity;
}Queue;Queue* create_queue()
{Queue* queue = (Queue*)calloc(1, sizeof(Queue));assert(queue);queue->tail = -1;return queue;
}void push(Queue* queue, DataType data)
{assert(queue);// 扩容if (queue->front == -1 || (queue->front >= queue->capacity)) {DataType* temp = (DataType*)realloc(queue->data, queue->capacity + 10);assert(temp);queue->data = temp;queue->capacity += 10;}queue->data[++queue->tail] = data;
}DataType top(Queue* queue)
{assert(queue);return queue->data[queue->front];
}void pop(Queue* queue)
{assert(queue);if (queue->front <= queue->tail) {queue->front++;}
}int size(Queue* queue)
{assert(queue);return queue->tail + 1;
}bool empty(Queue* queue)
{assert(queue);return queue->tail < queue->front;
}int main()
{Queue* queue = create_queue();for (int i = 1; i <= 10; i++) {push(queue, i);}while (!empty(queue)) {printf("%d ", top(queue));pop(queue);}return 0;
}

队列的链表实现

链表这里采用的是无头单链表实现,其中:

  • 入栈:插入队头
  • 出栈:弹出队头

🌛 队列封装

这个部分就是正常的节点封装,队列封装。

// 无头链表,封装写法,尾插法typedef int DataType;typedef struct Node {DataType* data;struct Node* next;
}Node;typedef struct Queue {Node* queueHead;// Node* tailHead;     // 添加这个节点会更简单一点int size;
}Queue;

👤 创建队列(初始化)

这一部分也是正常的创建节点、队列,然后申请内存。

Node* create_node(DataType data)
{Node* node = (Node*)calloc(1, sizeof(Node));assert(node);node->data = data;return node;
}Queue* create_queue()
{Queue* queue = (Queue*)calloc(1, sizeof(Queue));assert(queue);return queue;
}

📌 入队

入队就是在链表头插入,但是要注意,再插入的时候需要判断是否为空表:

  • 空表:插入节点作为头;
  • 不为空,则头插。
void push(Queue* queue, DataType data)
{assert(queue);if (queue->size == 0) {queue->queueHead = create_node(data);}else {Node* temp = queue->queueHead;while (temp->next) {temp = temp->next;}temp->next = create_node(data);}queue->size++;
}

🏤 出队

出队就是弹出头节点,但是要注意提前判断链表是否为空的情况。

void pop(Queue* queue)
{assert(queue);if (queue->size == 0) {return;}Node* temp = queue->queueHead;queue->queueHead = temp->next;free(temp);temp = NULL;queue->size--;
}

🍿 获取对头元素

这个就是获取头节点的元素值,要注意的是空表的情况,这里空表是直接断言了。

DataType top(Queue* queue)
{assert(queue);assert(queue->size != 0);   // 队列为空,不能获取栈顶元素return queue->queueHead->data;
}

🔌 万金油函数:队列大小、是否为空

这个没有什么好说的,看代码吧。

bool empty(Queue* queue)
{assert(queue);return queue->size == 0;
}int size(Queue* queue)
{assert(queue);return queue->size;
}

总代码

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <assert.h>// 无头链表,封装写法,尾插法typedef int DataType;typedef struct Node {DataType* data;struct Node* next;
}Node;typedef struct Queue {Node* queueHead;// Node* tailHead;     // 添加这个节点会更简单一点int size;
}Queue;Node* create_node(DataType data)
{Node* node = (Node*)calloc(1, sizeof(Node));assert(node);node->data = data;return node;
}Queue* create_queue()
{Queue* queue = (Queue*)calloc(1, sizeof(Queue));assert(queue);return queue;
}void push(Queue* queue, DataType data)
{assert(queue);if (queue->size == 0) {queue->queueHead = create_node(data);}else {Node* temp = queue->queueHead;while (temp->next) {temp = temp->next;}temp->next = create_node(data);}queue->size++;
}DataType top(Queue* queue)
{assert(queue);assert(queue->size != 0);   // 队列为空,不能获取栈顶元素return queue->queueHead->data;
}void pop(Queue* queue)
{assert(queue);if (queue->size == 0) {return;}Node* temp = queue->queueHead;queue->queueHead = temp->next;free(temp);temp = NULL;queue->size--;
}bool empty(Queue* queue)
{assert(queue);return queue->size == 0;
}int size(Queue* queue)
{assert(queue);return queue->size;
}int main()
{Queue* queue = create_queue();for (int i = 1; i <= 10; i++) {push(queue, i);}while (!empty(queue)) {printf("%d ", top(queue));pop(queue);}return 0;
}

双端队列

双端队列(Deque)是一种具有队列和栈性质的数据结构,它允许我们从两端添加或删除元素。这种灵活性使得双端队列在多种场景下都非常有用。

双端队列支持的基本操作包括

  • 入队:在队列的前端或后端添加元素。
  • 出队:从队列的前端或后端移除元素。
  • 访问:访问队列的前端或后端元素而不移除它们。

🉑 实现

  • 采用无头双向链表实现

📦 节点封装

这个就是封装数据节点,双向链表节点,和之前一样,代码如下:

typedef int DataType;typedef	struct Node {DataType data;struct Node* prev;struct Node* next;
}Node;typedef struct Deque {Node* head;Node* tail;int count;
}Deque;

📇 初始化节点

这个也是和上面一样,封装创建节点、创建队列的节点。

Node* create_node(DataType data)
{Node* node = (Node*)calloc(1, sizeof(Node));assert(node);node->data = data;return node;
}Deque* create_deque()
{Deque* deque = (Deque*)calloc(1, sizeof(Deque));assert(deque);return deque;
}

🎧 头插

头插这个要注意的就是判断链表是否为空。

void push_front(Deque* deque, DataType data)
{assert(deque);if (deque->count == 0) {deque->head = deque->tail = create_node(data);}else {Node* node = create_node(data);node->next = deque->head;deque->head->prev = node;deque->head = node;}deque->count++;
}

🎉 尾插

尾插这个也是要注意的就是判断链表是否为空。

void push_back(Deque* deque, DataType data)
{assert(deque);if (deque->count == 0) {deque->head = deque->tail = create_node(data);}else {Node* node = create_node(data);node->prev = deque->tail;deque->tail->next = node;deque->tail = node;}deque->count++;
}

👟 头删

删除要注意几个点:

  • 空不能删;
  • 删除后,如果是一个节点删除,则要将指向尾节点指针赋值为NULL,如果不是,则需要将新的对头元素前指针赋值为NULL。
void pop_front(Deque* deque)
{assert(deque);assert(deque->count != 0);   // 空,不能弹出Node* temp = deque->head;deque->head = temp->next;free(temp);temp = NULL;(deque->head) ? (deque->head->prev = NULL) : (deque->tail = NULL);   // 这个写法deque->count--;
}

🚖 尾删

删除要注意几个点:

  • 空不能删;
  • 删除后,如果是一个节点删除,则要将指向头节点指针赋值为NULL,如果不是,则需要将新队尾的下一个指针赋值为NULL。
void pop_tail(Deque* deque)
{assert(deque);assert(deque->count != 0);Node* temp = deque->tail;deque->tail = temp->prev;(deque->tail) ? (deque->tail->next = NULL) : (deque->head = NULL);free(temp);temp = NULL;deque->count--;
}

📑 获取对头、队尾大小

这个就是获取对于节点的元素值,但是要注意的是没有元素的情况。

DataType top_front(Deque* deque)
{assert(deque);assert(deque->count != 0);return deque->head->data;
}DataType top_tail(Deque* deque)
{assert(deque);assert(deque->count != 0);return deque->tail->data;
}

🆎 总代码

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <assert.h>/*
C++: deque
实现:双向链表
*/typedef int DataType;typedef	struct Node {DataType data;struct Node* prev;struct Node* next;
}Node;typedef struct Deque {Node* head;Node* tail;int count;
}Deque;Node* create_node(DataType data)
{Node* node = (Node*)calloc(1, sizeof(Node));assert(node);node->data = data;return node;
}Deque* create_deque()
{Deque* deque = (Deque*)calloc(1, sizeof(Deque));assert(deque);return deque;
}void push_back(Deque* deque, DataType data)
{assert(deque);if (deque->count == 0) {deque->head = deque->tail = create_node(data);}else {Node* node = create_node(data);node->prev = deque->tail;deque->tail->next = node;deque->tail = node;}deque->count++;
}void push_front(Deque* deque, DataType data)
{assert(deque);if (deque->count == 0) {deque->head = deque->tail = create_node(data);}else {Node* node = create_node(data);node->next = deque->head;deque->head->prev = node;deque->head = node;}deque->count++;
}// 简单代码的思路,记住
void pop_front(Deque* deque)
{assert(deque);assert(deque->count != 0);   // 空,不能弹出Node* temp = deque->head;deque->head = temp->next;free(temp);temp = NULL;(deque->head) ? (deque->head->prev = NULL) : (deque->tail = NULL);   // 这个写法deque->count--;
}void pop_tail(Deque* deque)
{assert(deque);assert(deque->count != 0);Node* temp = deque->tail;deque->tail = temp->prev;(deque->tail) ? (deque->tail->next = NULL) : (deque->head = NULL);free(temp);temp = NULL;deque->count--;
}DataType top_front(Deque* deque)
{assert(deque);assert(deque->count != 0);return deque->head->data;
}DataType top_tail(Deque* deque)
{assert(deque);assert(deque->count != 0);return deque->tail->data;
}void print_deque(Deque* deque)
{assert(deque);Node* temp = deque->head;while (temp != NULL) {printf("%d ", temp->data);temp = temp->next;}printf("\n");
}int main()
{Deque* deque = create_deque();for (int i = 1; i <= 10; i++) {push_front(deque, i);}print_deque(deque);for (int i = 20; i <= 30; i++) {push_back(deque, i);}print_deque(deque);pop_front(deque);pop_tail(deque);print_deque(deque);return 0;
}

优先队列简介

优先队列,我们第一反应是,没错,应该是应用最广泛的优先队列,但是从优先队列的定义来看,堆也只是其一种实现方式,优先队列的定义是:按照权值出队。

这里实现了一个简单的优先队列,出队的时候按照优先权最高出队,代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>// 优先队列,按照权值出队,这里只是实现一个简易版本
#define MAX 100typedef struct Data {int key;    // 比较准则char name[20];
}Data;typedef struct PriQueue {Data data[MAX];    // 简单版本,不扩容int curSize;
}PriQueue;PriQueue* create_priqueue()
{PriQueue* queue = (PriQueue*)calloc(1, sizeof(PriQueue));assert(queue);queue->curSize = -1;  /// 头为 -1return queue;
}bool empty(PriQueue* queue)
{assert(queue);return queue->curSize == -1;
}size_t size(PriQueue* queue)
{assert(queue);return queue->curSize + 1;
}void push(PriQueue* queue, Data data)
{assert(queue);if (queue->curSize == MAX)return;queue->data[++queue->curSize] = data;
}// 这里规定:权重最大的优先权最高,故弹出优先权最大的
void pop(PriQueue* queue, Data* temp)   // temp:存储需弹出的元素
{assert(queue);Data t = queue->data[0];int max = 0;for (int i = 1; i <= queue->curSize; i++) {if (queue->data[i].key > t.key) {t = queue->data[i];max = i;}}// 存储*temp = queue->data[max];for (int i = max; i <= queue->curSize - 1; i++) {queue->data[i] = queue->data[i + 1];}queue->curSize--;
}int main()
{PriQueue* queue = create_priqueue();Data arr[5] = { {1,"小美"},{5,"小丽"},{3,"小芳"},{4,"coco"},{2,"花花"} };for (int i = 0; i < 5; i++) {push(queue, arr[i]);}while (!empty(queue)) {Data temp;pop(queue, &temp);printf("key: %d, value: %s\n", temp.key, temp.name);}return 0;
}

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

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

相关文章

Windows修复SSL/TLS协议信息泄露漏洞(CVE-2016-2183) --亲测

漏洞说明&#xff1a; 打开链接&#xff1a;https://docs.microsoft.com/zh-cn/troubleshoot/windows-server/windows-security/restrict-cryptographic-algorithms-protocols-schannel 可以看到&#xff1a; 找到&#xff1a;应通过配置密码套件顺序来控制 TLS/SSL 密码 我们…

深度学习图像视觉 RKNN Toolkit2 部署 RK3588S边缘端 过程全记录

深度学习图像视觉 RKNN Toolkit2 部署 RK3588S边缘端 过程全记录 认识RKNN Toolkit2 工程文件学习路线&#xff1a; Anaconda Miniconda安装.condarc 文件配置镜像源自定义conda虚拟环境路径创建Conda虚拟环境 本地训练环境本地转换环境安装 RKNN-Toolkit2&#xff1a;添加 lin…

controller中的参数注解@Param @RequestParam和@RequestBody的不同

现在controller中有个方法&#xff1a;&#xff08;LoginUserRequest是一个用户类对象&#xff09; PostMapping("/test/phone")public Result validPhone(LoginUserRequest loginUserRequest) {return Result.success(loginUserRequest);}现在讨论Param("login…

Android按键点击事件三种实现方法

1. 在xml文件中为 Button 添加android:onclick属性 由于没有onclick这个函数&#xff0c;onclick下面会提示红色波浪线错误&#xff0c;然后单击一下"onclick"按住键盘上AltEnter键,选择在activity中生成函数 public void onclick(View view) {Toast.makeText(this,&…

全景图像(Panorama Image)向透视图像(Perspective Image)的跨视图转化(Cross-view)

一、概念讲解 全景图像到透视图像的转化是一个复杂的图像处理过程&#xff0c;它涉及到将一个360度的全景图像转换为一个具有透视效果的图像&#xff0c;这种图像更接近于人眼观察世界的方式。全景图像通常是一个矩形图像&#xff0c;它通过将球面图像映射到平面上得到&#xf…

RabbitMQ7:消息转换器

欢迎来到“雪碧聊技术”CSDN博客&#xff01; 在这里&#xff0c;您将踏入一个专注于Java开发技术的知识殿堂。无论您是Java编程的初学者&#xff0c;还是具有一定经验的开发者&#xff0c;相信我的博客都能为您提供宝贵的学习资源和实用技巧。作为您的技术向导&#xff0c;我将…

C#开发合集

用C#轻松搞定m3u8视频下载与合并 嘿&#xff0c;程序员们&#xff01;今天咱们来聊聊如何用C#写个小程序&#xff0c;轻松下载和合并m3u8视频文件。没错&#xff0c;就是那种分段的流媒体视频。准备好了吗&#xff1f;让我们开始吧&#xff01; 准备工作 在动手之前&#xf…

HarmonyOS4+NEXT星河版入门与项目实战(22)------动画(属性动画与显示动画)

文章目录 1、属性动画图解2、案例实现-小鱼移动游戏1、代码实现2、代码解释3、资源图片4、实现效果3、显示动画4、案例修改-显示动画5、总结1、属性动画图解 这里我们用一张完整的图来汇整属性动画的用法格式和使用的主要属性范围,如下所示: 2、案例实现-小鱼移动游戏 1、代…

【rustdesk】客户端和服务端的安装和部署(自建服务器,docker,远程控制开源软件rustdesk)

【rustdesk】客户端和服务端的安装和部署&#xff08;自建服务器&#xff0c;docker&#xff09; 一、官方部署教程 https://rustdesk.com/docs/zh-cn/client/mac/ 官方服务端下载地址 https://github.com/rustdesk/rustdesk-server/releases 我用的docker感觉非常方便&am…

Qt程序发布及打包成exe安装包

参考:Qt之程序发布以及打包成exe安装包 目录 一、简述 Qt 项目开发完成之后,需要打包发布程序,而因为用户电脑上没有 Qt 配置环境,所以需要将 release 生成的 exe 文件和所依赖的 dll 文件复制到一个文件夹中,然后再用 Inno Setup 打包工具打包成一个 exe 安装包,就可以…

python学opencv|读取图像

【1】引言 前序学习了使用matplotlib模块进行画图&#xff0c;今天开始我们逐步尝试探索使用opencv来处理图片。 【2】学习资源 官网的学习链接如下&#xff1a; OpenCV: Getting Started with Images 不过读起来是英文版&#xff0c;可能略有难度&#xff0c;所以另推荐一…

数据结构 ——— 归并排序算法的实现

目录 归并排序的思想 归并排序算法的实现 归并排序的思想 将已经有序的子序列合并&#xff0c;得到完全有序的序列&#xff0c;即先使每个子序列有序后&#xff0c;再使子序列段间有序 若将两个有序表合并成一个有序表&#xff0c;称为二路归并 归并排序步骤示意图&#x…

Springboot项目搭建(6)-前端登录跳转与Pinia实用

1.添加响应错误拦截 文件地址&#xff1a;src\utils\request.js import axios from axios import { ElMessage } from element-plus const baseURL /api const instance axios.create({baseURL}) //添加拦截器 instance.interceptors.response.use(result>{&#x1f447…

多输入多输出 | Matlab实现TCN-LSTM时间卷积神经网络结合长短期记忆神经网络多输入多输出预测

多输入多输出 | Matlab实现TCN-LSTM时间卷积神经网络结合长短期记忆神经网络多输入多输出预测 目录 多输入多输出 | Matlab实现TCN-LSTM时间卷积神经网络结合长短期记忆神经网络多输入多输出预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 多输入多输出 | Matlab实现…

C++网络编程:select IO多路复用及TCP服务器开发

C网络编程&#xff1a;使用select实现IO多路复用 一、什么是 IO 多路复用&#xff1f;二、IO多路复用器 select三、相关接口3.1、fd_set 结构体3.2、宏和函数 四、select 实现 TCP 服务器五、总结 一、什么是 IO 多路复用&#xff1f; 在网络编程中&#xff0c;最容易想到的并…

HDU Go Running(最小点覆盖 + 网络流优化)

题目大意&#xff1a;有一条无限长跑道&#xff0c;每个人可以规定自己跑步的方向&#xff0c;起点&#xff0c;跑步起止时间。每个人跑步的速度都是1m/s。最后从监控人员哪里得到了n个报告&#xff0c;每个报告给出了某人在某一时候所在的位置&#xff0c;问跑步的最少可能人数…

28.UE5实现对话系统

目录 1.对话结构的设计&#xff08;重点&#xff09; 2.NPC对话接口的实现 2.1创建类型为pawn的蓝图 2.2创建对话接口 3.对话组件的创建 4.对话的UI设计 4.1UI_对话内容 4.2UI_对话选项 4.3UI_对话选项框 5.对话组件的逻辑实现 通过组件蓝图&#xff0c;也就是下图中的…

Reachy 2,专为AI与机器人实验室打造的卓越开源双臂移动操作平台!

近期&#xff0c;花粉机器人&#xff08;POLLEN ROBOTICS&#xff09;隆重推出Reachy 2仿生机器人——下一代开源操作平台&#xff0c;为AI与机器人实验室带来理想的双臂移动操作科研平台&#xff01; Reachy 2的仿生性&#xff1a; 》拥有两个基于Maxon无刷电机的仿生7自由度…

python的openpyxl库设置表格样式:字体/边框/对齐/颜色等

学习目录 1. 安装和使用openpyxl库设置表格样式 2 设置字体font 3 设置边框 4 设置对齐方式 5 设置单元格数据格式 6 设置行高和列宽 7 填充单元格颜色 附录-关于颜色说明 本章节主要介绍如何使用openpyxl库设置表格中的一些样式&#xff0c;比如字体&#xff0c;边框…

Git旧文件覆盖引发思考

一天&#xff0c;我的同事过来找到我&#xff0c;和我讲&#xff1a;张叫兽&#xff0c;大事不好&#xff0c;我的文件被人覆盖了。git是真的不好用啊 git不好用&#xff1f;文件被覆盖&#xff1b;瞬间我似乎知道了什么&#xff0c;让我想到了某位男明星的语法&#xff1a;他…