一.了解项目功能
在本次项目中我们的目标是实现一个链队列:
该链队列使用动态内存分配空间,可以用来存储任意数量的同类型数据.
队列结点(QNode)需要包含两个要素:数据域data,指针域next.
队列结点(QNode)逻辑结构图示如下:
提供的功能有:
- 队列的初始化.
- 队列的入队.
- 队列的出队.
- 队列的长度.
- 队列的判空.
- 队列取队头元素.
- 队列取队尾元素.
- 队列的销毁
二.项目功能演示
要编写一个链队列项目，首先要明确我们想要达到的效果是什么样，下面我将用vs2022编译器来为大家演示一下链队列程序运行时的样子：
三.逐步实现项目功能模块及其逻辑详解
通过第二部分对项目功能的介绍，我们已经对链队列的功能有了大致的了解，虽然看似需要实现的功能很多，貌似一时间不知该如何下手，但我们可以分步分模块来分析这个项目的流程，最后再将各部分进行整合，所以大家不用担心，跟着我一步一步分析吧！
！！！注意，该部分的代码只是为了详细介绍某一部分的项目实现逻辑，故可能会删减一些与该部分不相关的代码以便大家理解，需要查看或拷贝完整详细代码的朋友可以移步本文第四部分。
1.实现链队列程序菜单
菜单部分的逻辑比较简单，就是利用C语言printf函数打印出这个菜单界面即可。但要注意菜单的标序要和后续switch...case语句的分支相应,以免导致后续执行语句错乱的问题.基础问题就不过多赘述了，代码如下：
该部分功能实现代码如下:
void QMenu() { printf("**********************************\n"); printf("******请选择要进行的操作 ******\n"); printf("******1.链队列入队 ******\n"); printf("******2.链队列出队 ******\n"); printf("******3.取队首元素 ******\n"); printf("******4.取队尾元素 ******\n"); printf("******5.队列判空 ******\n"); printf("******6.查询当前队列长 ******\n"); printf("******7.清空队列 ******\n"); printf("******0.退出链队列程序 ******\n"); printf("**********************************\n"); printf("请选择:>"); }
2.实现链程序功能可循环使用
由于我们要实现 的功能可以反复使用的逻辑，且至少在一开始执行一次,因此我们选择do...while的循环语句来实现这一部分的逻辑.
该部分功能实现代码如下:
int main() { Que Q;//创建队头尾指针结构体 QueueInit(&Q);//初始化 int swi = 0;//创建变量swi作为do...while循环的终止条件,以及switch语句的运行条件 do //使用do...while实现 { QMenu(); scanf("%d", &swi); switch (swi) { case 0: // 释放队列内存 QueueDestroy(&Q); printf("您已退出程序:>\n"); break; case 1: printf("请输入要入队的数据:>"); QDatatype pushback_data = 0; scanf("%d", &pushback_data); QueuePush(&Q, pushback_data); printf("已成功入队:>\n"); break; case 2: QueuePop(&Q); printf("出队成功:>\n"); break; case 3: printf("队首元素为:"); QDatatype e = QueueFront(&Q); printf("%d\n", e); break; case 4: printf("队尾元素为:"); QDatatype n = QueueBack(&Q); printf("%d\n", n); break; case 5: if (!QueueEmpty(&Q)) { printf("当前队列不为空:>\n"); } else { printf("当前队列为空\n"); } break; case 6: printf("当前队列长度为:"); int size= QueueSize(&Q); printf("%d\n", size); break; case 7: QueueDestroy(&Q); QueueInit(&Q); printf("队列已清空:>\n"); break; default: printf("输入错误,请重新输入\n"); break; } } while (swi); return 0; }
3.创建链队列
创建链队列结点的结构体应该包括:存储数据的数据域data,以及存储下一个结点地址的指针域next.
图示如下:
因此我们创建QNode结构体类型时应由一个数据成员类型及一个指向该结构体的结构体指针组成.
然后队列特殊与单链表的点出现了:队列额外需要一个指向队头的队头指针,以及一个指向队尾的队尾指针,以及一个记录队长的整型size.
为了避免设计函数时要传好几个参数的情况,我们将这三个变量额外封装一个结构体,这样只要给函数传结构体变量就可以在函数内部访问这三个变量了.
如果有朋友对队列的两个结构体还搞不太清楚,可以这样理解:Queue结构体中的head指针相当于链表中的头指针,它的使用方式和链表中的头指针完全相同.然后在此基础上,只是多一个tail指针记录尾,多一个整型记录队列长度.
综上,该部分代码如下:
#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h> typedef int QDatatype; typedef struct QueueNode//一个是结点结构 { struct QueueNode* next; QDatatype data; }QNode; typedef struct Queue//一个是队列整体结构 { QNode* head; QNode* tail; int size ; }Que;
4.链队列的初始化.
回忆我们在链表部分对链表的初始化仅仅是将头指针置为NULL.而到了链队列这里,我们还多出两个需要处理的变量,一个是尾指针tail,一个是链队列长度size.
因此我们封装一个初始化函数将这3个变量一起初始化.
链队列结构初始化部分代码逻辑图示如下:
综上,该部分代码如下:
void QueueInit(Que* pq) { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; }
5.链队列的入队.
链队列在入队时思路如下:
- 开辟新结点
- 判断队列是否为空队列
- 为空则将新结点"头插"进队列
- 不为空则将新结点"尾插"进队列
综上,该部分代码如下:
void QueuePush(Que* pq, QDatatype x) //入队是尾插 { //创建新结点 QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } //新结点赋值 newnode->data = x; newnode->next = NULL; //当队列为空时,入队相当于头插 if (pq->head == NULL) { assert(pq->tail == NULL); //head为空,tail不为空就出事了,即队头为空但是队尾不为空 //将head和tail一起指向newnode pq->head = pq->tail = newnode; } else//否则就是尾插 { //尾插直接将新结点链接在原来的队尾后面 pq->tail->next = newnode; //然后更新队尾 pq->tail = newnode; } //新结点插入成功后队列长度要+1 pq->size++; }
6.链队列的出队.
链队列在出队思路如下:
- 判断队列是否为空队列
- 如果是,抛出异常终止程序
- 如果不是,则判断队列中是否仅剩一个结点
- 如果只剩一个结点,释放该结点,然后将head和tail置为空
- 如果不是只剩一个结点,那么使用一个指针记录下当前队头的下一个结点的位置
- 释放当前队头结点,然后更新队头指针
- 最后队列长度-1
综上,该部分代码如下:
void QueuePop(Que* pq)//出队是头删,删前先判空 { assert(pq); assert(!QueueEmpty(pq));//assert为假会终止程序 QNode* cur = pq; if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* next = pq->head->next; free(pq->head); pq->head = next; } pq->size--; }
7.链队列的长度.
求链队列的长度,因为我们有设计记录链队列长度的变量size,因此我们直接返回结构体中的size成员的值即可.
int QueueSize(Que* pq) { assert(pq); return pq->size; }
8.链队列的判空.
判断队列是否为空,我们可以返回(pq->size==0)表达式的值:
- 如果队列为空,则size=0,则pq->size==0表达式为真,函数返回true.
- 如果队列不为空,则size不等于0,则pq->size==0表达式为假,函数返回false.
综上,该部分代码如下:
bool QueueEmpty(Que* pq)//判空!为空返回真! { assert(pq); return pq->size==0; }
9.链队列取队头元素.
取队头元素思路:
- 判断队列是否为空
- 为空抛出异常
- 不为空返回队头指针指向的头节点的数据域
综上,该部分代码如下:
QDatatype QueueFront(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; }
10.链队列取队尾元素.
取队尾元素思路:
- 判断队列是否为空
- 为空抛出异常
- 不为空返回队尾指针指向的尾节点的数据域
综上,该部分代码如下:
QDatatype QueueBack(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; }
11.链队列的销毁
链队列的销毁思路:
- 从头遍历队列的元素,逐一释放链队列中的结点
- 释放完将队头指针和队尾指针置为NULL,将队列长度size置为0.
综上,该部分代码如下:
void QueueDestroy(Que* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; pq->size = 0; }
四.项目完整代码
我们将程序运行的代码分别在三个工程文件中编辑,完整代码如下:
test.c文件
#include"Queue.h" //因为链队列头指针是必须的 //而在队尾插入则尾指针同样也是必须的 //因此我们不妨设置两个指针,一个记录队头,一个记录队尾 //为方便起见,多个数据我们把头指针和尾指针再封装一个结构体 //单链表不设置尾指针的原因是它不能解决尾删问题 int main() { Que Q;//初始化 QueueInit(&Q); int swi = 0;//创建变量swi作为do...while循环的终止条件,以及switch语句的运行条件 do //使用do...while实现 { QMenu(); scanf("%d", &swi); switch (swi) { case 0: // 释放队列内存 QueueDestroy(&Q); printf("您已退出程序:>\n"); break; case 1: printf("请输入要入队的数据:>"); QDatatype pushback_data = 0; scanf("%d", &pushback_data); QueuePush(&Q, pushback_data); printf("已成功入队:>\n"); break; case 2: QueuePop(&Q); printf("出队成功:>\n"); break; case 3: printf("队首元素为:"); QDatatype e = QueueFront(&Q); printf("%d\n", e); break; case 4: printf("队尾元素为:"); QDatatype n = QueueBack(&Q); printf("%d\n", n); break; case 5: if (!QueueEmpty(&Q)) { printf("当前队列不为空:>\n"); } else { printf("当前队列为空\n"); } break; case 6: printf("当前队列长度为:"); int size= QueueSize(&Q); printf("%d\n", size); break; case 7: QueueDestroy(&Q); QueueInit(&Q); printf("队列已清空:>\n"); break; default: printf("输入错误,请重新输入\n"); break; } } while (swi); return 0; }
Queue.c 文件
#include"Queue.h" void QueueInit(Que* pq) { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; } void QueueDestroy(Que* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; pq->size = 0; } void QueuePush(Que* pq, QDatatype x) //入队是尾插 { QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->data = x; newnode->next = NULL; if (pq->head == NULL)//头插 { assert(pq->tail == NULL);//head为空,tail不为空就出事了,队头为空但是队尾不为空 pq->head = pq->tail = newnode; } else//尾插 { pq->tail->next = newnode; pq->tail = newnode; } pq->size++; } void QueuePop(Que* pq)//出队是头删 { assert(pq); assert(pq->head!=NULL);//*** QNode* cur = pq; if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* next = pq->head->next; free(pq->head); pq->head = next; } pq->size--; } int QueueSize(Que* pq) { assert(pq); return pq->size; } bool QueueEmpty(Que* pq)//判空!为空返回真! { assert(pq); return pq->size==0; } QDatatype QueueFront(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } QDatatype QueueBack(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; } void QMenu() { printf("**********************************\n"); printf("******请选择要进行的操作 ******\n"); printf("******1.链队列入队 ******\n"); printf("******2.链队列出队 ******\n"); printf("******3.取队首元素 ******\n"); printf("******4.取队尾元素 ******\n"); printf("******5.队列判空 ******\n"); printf("******6.查询当前队列长 ******\n"); printf("******7.清空队列 ******\n"); printf("******0.退出链队列程序 ******\n"); printf("**********************************\n"); printf("请选择:>"); }
Queue.h文件
#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h> typedef int QDatatype; typedef struct QueueNode//一个是结点结构 { struct QueueNode* next; QDatatype data; }QNode; typedef struct Queue//一个是队列整体结构 { QNode* head; QNode* tail; int size ; }Que; void QueueInit(Que* pq); void QueueDestroy(Que* pq); void QueuePush(Que* pq,QDatatype x); void QueuePop(Que* pq); int QueueSize(Que* pq); bool QueueEmpty(Que* pq); QDatatype QueueFront(Que* pq); QDatatype QueueBack(Que* pq); void QMenu();
结语
希望这篇链队列的实现详解能对大家有所帮助,欢迎大佬们留言或私信与我交流.
学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!
数据结构栈与队列篇思维导图:
