数据结构与算法学习笔记十---链队列的表示和实现(C语言)

目录

前言

1.什么是链队

2.链队的表示和实现

1.定义

2.初始化

3.销毁

4.清空

5.空队列

6.队列长度

7.获取队头

8.入队

9.出队

10.遍历队列

11.完整代码

前言

    本篇博客介绍链栈队列的表示和实现。

1.什么是链队

    链队是采用链式存储结构实现的队列。通常链队使用单链表表示。

   

图1.链队的示意图

     为了操作方便，我们给链队列增加一个头结点，令头指针始终指向头结点。

2.链队的表示和实现

1.定义

typedef int QElemType;
typedef int Status;
typedef struct QNode{
    QElemType data;
    struct QNode * next;
}QNode,*QueuePtr;
typedef struct {
    QueuePtr front;//队头指针
    QueuePtr rear;//队尾指针
}LinkQueue;

2.初始化

            初始化的时候给链队分配一个结点。

        图2.空队列

//初始化
Status initLinkQueue(LinkQueue * linkQueue){
    linkQueue->front =  linkQueue->rear = (QueuePtr)malloc(sizeof(QNode));
    if (!linkQueue->front) {
        return 0;
    }
    return 1;
}

3.销毁

        当需要销毁队列时，我们需要释放队列中所有节点的内存，并将队列结构体中的指针置空。

         我们需要遍历所有的结点，释放结点内存，最后置空头结点。

// 销毁队列
void destroyLinkQueue(LinkQueue *linkQueue) {
    while (linkQueue->front) { // 循环释放队列中所有节点的内存
        QueuePtr temp = linkQueue->front;
        linkQueue->front = linkQueue->front->next;
        free(temp);
    }
    linkQueue->rear = NULL; // 将 rear 指针置空
}

4.清空

        清空队列的方法与销毁队列的方法类似，但不释放队列结构体本身的内存，只释放队列中节点的内存并将队列恢复到初始状态。

// 清空队列
void clearLinkQueue(LinkQueue *linkQueue) {
    while (linkQueue->front) { // 循环释放队列中所有节点的内存
        QueuePtr temp = linkQueue->front;
        linkQueue->front = linkQueue->front->next;
        free(temp);
    }
    linkQueue->rear = NULL; // 将 rear 指针置空
}

5.空队列

        队头和队尾相同的时候为空队列。

// 判断队列是否为空
Status isLinkQueueEmpty(LinkQueue *linkQueue) {
    return linkQueue->front == NULL; // 如果队头指针为空，则队列为空
}

6.队列长度

// 计算队列长度
int getLinkQueueLength(LinkQueue *linkQueue) {
    int length = 0;
    QueuePtr p = linkQueue->front->next; // 从队头指针开始
    while (p != NULL) { // 遍历队列
        length++;
        p = p->next;
    }
    return length;
}

7.获取队头

        获取队头元素。

// 获取队列头结点
Status getLinkQueueFront(LinkQueue *linkQueue, QElemType *element) {
    if (linkQueue->front == NULL) { // 队列为空
        return 0;
    }
    *element = linkQueue->front->next->data; // 将队头节点的数据存储到 element 中
    return 1;
}

8.入队

        入队列的时候如下所示。

        图3.入队列示意图

// 入队列
Status enLinkQueue(LinkQueue * linkQueue,QElemType element){
    QueuePtr newNode = (QNode *)malloc(sizeof(QNode));//生成一个新节点
    if (!newNode) {
        return 0;
    }
    newNode->data = element;
    newNode->next = NULL;
    
    linkQueue->rear->next = newNode;
    linkQueue->rear = newNode;
    
    
    return 1;
}

9.出队

        出队列的时候如下如所示：

图4.出队列示意图

// 出队列
Status deLinkQueue(LinkQueue * linkQueue,QElemType *element){
    if (linkQueue->front == linkQueue->rear) {//空队列
        return 0;
    }
    QueuePtr p = linkQueue->front->next;// 指向头结点
    * element = p->data;
    
    linkQueue->front->next = p->next;//修改头指针
    if (linkQueue->front == p) {//如果仅有一个节点
        linkQueue->rear = linkQueue->front;//修改尾指针
    }
    free(p);
    return 1;
}

10.遍历队列

// 遍历队列（忽略头结点）
void traverseLinkQueueIgnoreHead(LinkQueue *linkQueue) {
    if (linkQueue->front == NULL || linkQueue->front->next == NULL) { // 队列为空或只有头结点
        printf("队列为空\n");
        return;
    }
    QueuePtr current = linkQueue->front->next; // 从头结点的下一个节点开始遍历
    while (current != NULL) { // 遍历直到队尾
        printf("%d\t", current->data); // 打印当前节点的数据
        current = current->next; // 移动到下一个节点
    }
    printf("\n");
}

11.完整代码

#include <stdlib.h>

typedef int QElemType;
typedef int Status;
typedef struct QNode{
    QElemType data;
    struct QNode * next;
}QNode,*QueuePtr;
typedef struct {
    QueuePtr front;//队头指针
    QueuePtr rear;//队尾指针
}LinkQueue;

//初始化
Status initLinkQueue(LinkQueue * linkQueue){
    linkQueue->front =  linkQueue->rear = (QueuePtr)malloc(sizeof(QNode));
    if (!linkQueue->front) {
        return 0;
    }
    return 1;
}
// 销毁队列
void destroyLinkQueue(LinkQueue *linkQueue) {
    while (linkQueue->front) { // 循环释放队列中所有节点的内存
        QueuePtr temp = linkQueue->front;
        linkQueue->front = linkQueue->front->next;
        free(temp);
    }
    linkQueue->rear = NULL; // 将 rear 指针置空
}
// 清空队列
void clearLinkQueue(LinkQueue *linkQueue) {
    while (linkQueue->front) { // 循环释放队列中所有节点的内存
        QueuePtr temp = linkQueue->front;
        linkQueue->front = linkQueue->front->next;
        free(temp);
    }
    linkQueue->rear = NULL; // 将 rear 指针置空
}
// 判断队列是否为空
Status isLinkQueueEmpty(LinkQueue *linkQueue) {
    return linkQueue->front == NULL; // 如果队头指针为空，则队列为空
}
// 计算队列长度
int getLinkQueueLength(LinkQueue *linkQueue) {
    int length = 0;
    QueuePtr p = linkQueue->front->next; // 从队头指针开始
    while (p != NULL) { // 遍历队列
        length++;
        p = p->next;
    }
    return length;
}
// 获取队列头结点
Status getLinkQueueFront(LinkQueue *linkQueue, QElemType *element) {
    if (linkQueue->front == NULL) { // 队列为空
        return 0;
    }
    *element = linkQueue->front->next->data; // 将队头节点的数据存储到 element 中
    return 1;
}
// 遍历队列
// 遍历队列（忽略头结点）
void traverseLinkQueueIgnoreHead(LinkQueue *linkQueue) {
    if (linkQueue->front == NULL || linkQueue->front->next == NULL) { // 队列为空或只有头结点
        printf("队列为空\n");
        return;
    }
    QueuePtr current = linkQueue->front->next; // 从头结点的下一个节点开始遍历
    while (current != NULL) { // 遍历直到队尾
        printf("%d\t", current->data); // 打印当前节点的数据
        current = current->next; // 移动到下一个节点
    }
    printf("\n");
}


// 入队列
Status enLinkQueue(LinkQueue * linkQueue,QElemType element){
    QueuePtr newNode = (QNode *)malloc(sizeof(QNode));//生成一个新节点
    if (!newNode) {
        return 0;
    }
    newNode->data = element;
    newNode->next = NULL;
    
    linkQueue->rear->next = newNode;
    linkQueue->rear = newNode;
    
    
    return 1;
}
// 出队列
Status deLinkQueue(LinkQueue * linkQueue,QElemType *element){
    if (linkQueue->front == linkQueue->rear) {//空队列
        return 0;
    }
    QueuePtr p = linkQueue->front->next;// 指向头结点
    * element = p->data;
    
    linkQueue->front->next = p->next;//修改头指针
    if (linkQueue->front == p) {//如果仅有一个节点
        linkQueue->rear = linkQueue->front;//修改尾指针
    }
    free(p);
    return 1;
}

void testLinkQueue(void){
    LinkQueue queue;
    if (initLinkQueue(&queue)) {
        printf("链队列初始化成功！\n");
    }else {
        printf("链队列初始化失败！\n");
    }
    if (isLinkQueueEmpty(&queue)) {
        printf("队列为空\n");
    }
    printf("队列长度:%d\n",getLinkQueueLength(&queue));
    for (int i = 1; i <= 10 ; i++) {
        if (enLinkQueue(&queue, i)) {
            printf("数据元素%d入队成功!\n",i);
        }else{
            printf("入队失败!\n");
        }
    }
    printf("遍历链队列初！\n");
    if (!isLinkQueueEmpty(&queue)) {
        printf("队列不为空\n");
    }
    QElemType headFront;
    if (getLinkQueueFront(&queue, &headFront)) {
        printf("队列头结点获取成功,队头元素为:%d\n",headFront);
    }
    traverseLinkQueueIgnoreHead(&queue);
    printf("队列长度:%d\n",getLinkQueueLength(&queue));
    printf("队列长度:%d\n",getLinkQueueLength(&queue));
    for (int i = 1; i <= 10 ; i++) {
        int element;
        if (deLinkQueue(&queue, &element)) {
            printf("出队列成功,出队列的数据元为素%d!\n",element);
        }else{
            printf("入队失败!\n");
        }
    }
    destroyLinkQueue(&queue);
}

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

RAG 面向 LLM: 基于检索增强的大语言模型调研

RAG 面向 LLM: 基于检索增强的大语言模型调研

摘要 作为 AI 领域最先进的技术之一,检索增强生成(RAG)技术可以提供可靠和最新的外部知识,为众多任务提供巨大的便利。特别是在 AI 生成内容(AIGC)时代,RAG 中检索强大的提供额外知识的能力使得检索增强生成能够辅助现有生成式 AI 生产高质量输出。最近,大语言模型(LLM)在语言…
阅读更多...
如何将3DMax中制作的特效渲染为AVI格式视频？---模大狮模型网

如何将3DMax中制作的特效渲染为AVI格式视频？---模大狮模型网

在3D设计中&#xff0c;制作出精美的特效是吸引眼球的关键之一。然而&#xff0c;仅仅制作特效还不够&#xff0c;将其渲染为视频并分享给观众才能展现出其真正的魅力。本文将为您提供一份完整的指南&#xff0c;教您如何在3ds Max中将制作的特效渲染为AVI格式视频&#xff0c;…
阅读更多...
【iOS】——RunLoop学习

【iOS】——RunLoop学习

文章目录 一、RunLoop简介1.RunLoop介绍2.RunLoop功能3.RunLoop使用场景4.Run Loop 与线程5.RunLoop源代码和模型图 二、RunLoop Mode1.CFRunLoopModeRef2.RunLoop Mode的五种模式3.RunLoop Mode使用 三、RunLoop Source1.CFRunLoopSourceRefsourc0&#xff1a;source1: 2.CFRu…
阅读更多...
EEL中 python端的函数名是如何传递给js端的

EEL中 python端的函数名是如何传递给js端的

python端的函数名是如何传递给js端的 核心步骤&#xff1a;将函数名列表注入到动态生成的 eel.js 中&#xff0c;这样前端一开始引用的eel.js本身已经包含有py_function的函数名列表了。你打开开发者工具看看浏览器中的 eel.js文件源代码就知道了。 具体实现&#xff1a; # 读…
阅读更多...
如何将一个流固耦合的爆炸案例修改成一个没有固体的爆炸案例（类似于blastfoam的twochargeDetonation案例，可以重点模仿这个来）

如何将一个流固耦合的爆炸案例修改成一个没有固体的爆炸案例（类似于blastfoam的twochargeDetonation案例，可以重点模仿这个来）

t技巧总结&#xff1a;~/myapp/OpenFOAM-7/blastfoam_2_0/tutorials/twoChargeDetonation案例对比&#xff0c;发现确实这个案例也没有固体文件夹和precice-config文件夹&#xff0c;只需要用到openfoam7与blastfoam2.0.0。&#xff08;这个案例可以当做一个很好的爆炸案例的入…
阅读更多...
Spring MVC 介绍及其使用（详细）

Spring MVC 介绍及其使用（详细）

目录 一.什么是SpringMVC呢&#xff1f; 1.1MVC的介绍 1.2SpringMVC和MVC的关系 二.SpringMVC的学习 第一步&#xff1a;创建项目 第二步&#xff0c;SpringMVC的连接 第三步&#xff0c;Spring MVC获取参数 第四步 SpringMVC的输出 总结 特点和优势 核心组件 一.什…
阅读更多...
ue引擎游戏开发笔记（37）——实现造成伤害

ue引擎游戏开发笔记（37）——实现造成伤害

1.需求分析&#xff1a; 在游戏中已经能够射击&#xff0c;并且能得到实际的落点反馈&#xff0c;但本质上这种射击没有任何实际数值伤害&#xff0c;为射击添加实际的子弹伤害数值。 2.操作实现&#xff1a; 1.思路&#xff1a;ue本身函数FPointDamageEvent就可以解决&#x…
阅读更多...
谷歌邮箱2024最新注册教程

谷歌邮箱2024最新注册教程

大家好&#xff0c;我是蓝胖子&#xff0c;今天教大家如何注册谷歌邮箱 谷歌邮箱的注册后面的用途会经常用得到 首先&#xff0c;需要魔法自行解决 第一步&#xff1a;打开谷歌官网 www.google.com 确保谷歌官网能正常打开 第二步&#xff1a;创建账号 接下来可能会遇到这…
阅读更多...
鸿蒙原生应用数量激增20倍，鸿蒙生态“一路狂奔”！

鸿蒙原生应用数量激增20倍，鸿蒙生态“一路狂奔”！

过去几个月&#xff0c;在各地政府和千行百业伙伴的全面支持下&#xff0c;鸿蒙生态建设正在以前所未有的速度和规模蓬勃发展。 鸿蒙生态跑出“加速度”&#xff0c;再迎里程碑进展 从1月华为宣布首批200多家应用厂商加速开发鸿蒙原生应用以来&#xff0c;到3月底已有超4000款…
阅读更多...
鸿蒙ArkUI开发：常用布局【相对布局】

鸿蒙ArkUI开发：常用布局【相对布局】

相对布局&#xff08;RelativeContainer&#xff09; 相对布局可以让子元素指定兄弟元素或父容器作为锚点&#xff0c;基于锚点做位置布局必须为RelativeContainer及其子元素设置ID&#xff0c;用于指定锚点信息。未设置ID的子元素不会显示RelativeContainer ID为“__containe…
阅读更多...
nginx配置域名与IP访问服务冲突问题

nginx配置域名与IP访问服务冲突问题

在最近的一次开发中遇到一个问题&#xff0c;我在云服务器上部署了两个服务&#xff0c;A服务和B服务&#xff0c; A服务在服务器中用的端口是80端口&#xff0c;所以我在浏览器访问的地址就是 B服务在服务器中用的是9818端口&#xff0c;所以我在浏览器访问的是 现在我给B服务…
阅读更多...
【综述】人工智能、机器学习、深度学习

【综述】人工智能、机器学习、深度学习

文章目录 前言 概念 算法 训练 性能 应用 参考资料 前言 见《初试人工智能》 概念 人工智能系统&#xff08;artifieial intelligence system&#xff09;&#xff0c;针对人类定义的给定目标&#xff0c;产生诸如内容、预测、推荐或决策等输出的一类工程系统。该工程系…
阅读更多...
黑马程序员鸿蒙HarmonyOS端云一体化开发【13-15】

黑马程序员鸿蒙HarmonyOS端云一体化开发【13-15】

前置知识&#xff1a;arkts 一套开发工具&#xff0c;一套语言&#xff0c;搞定客户端和云端两个的编写。其中application就是客户端&#xff0c;cloudProgram就是云端。 开发人员->全栈开发工程师&#xff0c;降低了开发成本&#xff0c;且提供了很多现成的云服务&#xf…
阅读更多...
如何使用AI总结超长PDF文件？NoteGPT做到了！

如何使用AI总结超长PDF文件？NoteGPT做到了！

NoteGPT&#xff08;PDF Summary with AI - NoteGPT&#xff09;是我在做一个产品&#xff0c;其中一个功能就是如题&#xff0c;总结超长的PDF文件。 这篇文章从业务和技术的角度&#xff0c;来给大家分享下&#xff0c;我是如何实现的。 为什么要做总结总结超长PDF文件&…
阅读更多...
npm install 卡在reify:rxjs: timing reifyNode的解决办法

npm install 卡在reify:rxjs: timing reifyNode的解决办法

今天要逆向跑一个electron&#xff0c;但是npm install一直卡在 reify:element-plus: timing reifyNode:node_modules/lodash Completed in 6664ms这里一动不动&#xff0c;一番研究之后发现可能跟用的镜像有关系&#xff0c;我原本是官方镜像&#xff0c;总感觉第三方镜像有一…
阅读更多...
vuex的基本认知

vuex的基本认知

目录 一、什么是vuex 二、vuex的应用场景 三、vuex的优势 一、什么是vuex Vuex是一个vue的状态管理工具&#xff0c;状态就是数据。 进一步解释&#xff1a;vuex是一个插件&#xff0c;可以帮助我们管理vue通用的数据&#xff08;多组件共享的数据&#xff09; 二、vuex的…
阅读更多...
Java零拷贝技术实战

Java零拷贝技术实战

文章目录 引入传统IO内存映射mmap文件描述符sendFile测试总结 引入 为什么要使用零拷贝技术&#xff1f; 传统写入数据需要4次拷贝&#xff0c;如下图&#xff1a; 传统IO import java.io.*; import java.net.Socket;public class TranditionIOClient {private static fina…
阅读更多...
【Java】/*方法的递归*/

【Java】/*方法的递归*/

目录 一、递归的概念 二、递归执行过程分析 三、递归练习 3.1 按顺序打印一个数字的每一位&#xff0c;例如123打印出1 2 3 3.2 递归求 1 2 3 ... n 的和 3.3 输入一个非负整数&#xff0c;返回组成它的数字之和&#xff0c;例如123&#xff0c;得123 3.4 求斐波那契…
阅读更多...
工业无风扇计算机的优点

工业无风扇计算机的优点

无风扇计算机往往采用紧凑且密封的外形&#xff0c;使其坚固耐用&#xff0c;使其能够在需要现场工程师进行维护之前承受恶劣的环境数年。机载移动部件较少或没有移动部件会降低组件无法按预期运行的可能性&#xff0c;或者更糟糕的是发生故障和损坏。采用工业组件和较低的散热…
阅读更多...
mysql，sqlserver数据库查询表，获得表结构，结构类型说明，获得这些数据，可以拿去创建表

mysql，sqlserver数据库查询表，获得表结构，结构类型说明，获得这些数据，可以拿去创建表

mysql&#xff0c;sqlserver数据库查询表&#xff0c;获得表结构&#xff0c;结构类型说明&#xff0c;获得这些数据&#xff0c;可以拿去创建表 //表名p_order select * from information_schema.COLUMNS where TABLE_NAMEp_order;1、TABLE_CATALOG &#xff0c;nvarchar(128…
阅读更多...
最新文章

Copyright @ 2022~2023