追梦之旅【数据结构篇】 |
您所在的位置：网站首页 › c语言获取时间差 › 追梦之旅【数据结构篇】 |
追梦之旅【数据结构篇】
|
😎博客昵称：博客小梦 😊最喜欢的座右铭：全神贯注的上吧！！！ 😊作者简介：一名热爱C/C++，算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主！ 😘博主小留言：哈喽！😄各位CSDN的uu们，我是你的博客好友小梦，希望我的文章可以给您带来一定的帮助，话不多说，文章推上！欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！😘
哈喽各位友友们😊，我今天又学到了很多有趣的知识，现在迫不及待的想和大家分享一下！😘我仅已此文，手把手带领大家详解C语言实现链队列~ 结合链表的相关算法，根据队列先进先出的结构特点，实现我们链队列。都是精华内容，可不要错过哟！！！😍😍😍 整体实现内容分析💞首先先编写我们的Queue.h文件的内容，将需要的头文件和需要实现的功能函数做个声明。然后是Queue.c文件的编写，主要是针对各个功能函数的一一实现，最后是Test.c文件的编写，测试我们功能函数是否有问题。 预备小知识🙌队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。 队列的结构示意图：
头文件的编写的整体思路分析： 这里是有关头文件的编写和各种功能函数的声明，首先用typedef关键字给存储数据类型取别名，这样做的好处是以后想要改变队列的数据类型只需修改typedef int QDataType;里的int即可。定义一个结构体，包括next指针和data。然后是各个功能函数声明 #pragma once #include #include #include #include typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QNode; typedef struct Queue { QNode* head; QNode* tail; }Queue; //初始化 void QueueInit(Queue* pq); //销毁 void QueueDestory(Queue* pq); //队尾入 void QueuePush(Queue* pq, QDataType); //队头出 void QueuePop(Queue* pq); //队头元素 QDataType QueueFront(Queue* pq); //队尾元素 QDataType QueueBack(Queue* pq); //队列元素个数 int QueueSize(Queue* pq); //判空 bool QueueEmpty(Queue* pq); 2.链队列功能文件（Queue.c ）编写：🙌1）初始化函数实现编写的整体思路分析： 先用assert确保pq指针的有效性，然头尾指针置为空。 //初始化 void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; } 2）销毁函数实现编写的整体思路分析： 先用assert确保pq指针的有效性，先定义一个指针cur记录head指针的位置，然后用while循环进行一个个删除：先定义一个next指向cur指针指向的下一个队列元素，然后删掉cur指向的元素，再让cur移动到下一个。 //销毁 void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; } 3）队尾插入元素函数实现编写的整体思路分析： 先用assert确保pq指针的有效性，用malloc函数申请空间，用if语句来判断空间是否开辟失败。然后让newnode->next置为空，把数据放进去。如果是一开始时为空的，则让pq->head = pq->tail = newnode;如果不为空，则让之前的tail指向的节点与新节点相连。 //队尾入 void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->data = x; newnode->next = NULL; if (pq->tail == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; 4）队头删除元素函数实现编写的整体思路分析： 用assert确保pq指针的有效性，如果队列为空，就不用进行队头出的操作，如果执行则报错。先用next指针指向首结点的下一个节点 。然后删掉首节点，再让head指针指向next位置。删完后，将尾指针置为NULL //队头出 void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); QNode* next = pq->head->next; free(pq->head); pq->head = next; if (pq->head == NULL) { pq->tail = NULL; } } 5）获取队头元素函数实现编写的整体思路分析： 先用assert确保pq指针的有效性，如果队列为空，就不用进行此操作。然后直接返回首节点数据即可。 //队头元素 QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } 6）获取队尾元素函数实现编写的整体思路分析： 先用assert确保pq指针的有效性，如果队列为空，就不用进行此操作。然后直接返回尾节点数据即可。 //队尾元素 QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; } 7）获取队列元素个数的函数实现编写的整体思路分析： 先用assert确保pq指针的有效性，定义cur指向head的位置。利用while循环，先让Size加1，然后让cur指向下一个，知道cur为空时结束循环，返回Size大小就是队列元素的个数。 //队列元素个数 int QueueSize(Queue* pq) { assert(pq); int Size = 0; QNode* cur = pq->head; while (cur) { Size++; cur = cur->next; return Size; } } 8）判空函数实现编写的整体思路分析： 先用assert确保pq指针的有效性，然后pq->head == NULL为真，则返回1，为假则返回0； //判空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; } 3.链队列测试文件编写🙌（3）Tese.c文件的编写。 #define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" void test() { Queue q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); printf("队首元素：%d\n", QueueFront(&q)); printf("队尾元素：%d\n", QueueBack(&q)); printf("队列元素的个数：%d\n", QueueBack(&q)); printf("队列元素输出："); while (!QueueEmpty(&q)) { QDataType* front = QueueFront(&q); printf("%d", front); QueuePop(&q); } printf("\n"); QueueDestory(&q); } int main() { test(); return 0; }功能测试结果展示图：
本篇文章旨在分享详解C语言实现链队列。希望大家通过阅读此文有所收获！本次关于队列的实现相对于之前链表和顺序表的实现简单一点，实现起来的算法和之前的栈是相似的，但结构特点与栈是相反的。指针的指向没有那么复杂，主要是对入队列和出队列的功能实现。但也有很多地方需要注意的。比如说，野指针的问题，动态开辟的空间一定要free掉，并且把指针置为NULL。用动态实现，相对于静态实现还比较灵活，也能对空间有很大的节省。 😘如果我写的有什么不好之处，请在文章下方给出你宝贵的意见😊。如果觉得我写的好的话请点个赞赞和关注哦~😘😘😘 |
【本文地址】
今日新闻 |
推荐新闻 |