【数据结构】 链队列的基本操作 （C语言版）
发布时间：2024年01月24日
目录
一、链队列
1、链栈的定义：
链队列是一种线性数据结构，采用链表来实现队列的操作。链队列具有队头指针和队尾指针，用于指示队列元素所在的位置。链队列只允许在队尾插入元素，在队头删除元素，符合先进先出（First In First Out，FIFO）的原则。
2、链栈的优缺点：
链队列的优点：
- 动态分配空间：链队列使用链表实现，可动态分配和释放空间。因此，不需要预先分配大量存储空间，可以根据实际需求进行空间分配。
- 无需移动元素：相比普通队列，链队列在删除元素时无需移动大量元素，只需修改指针即可。这使得链队列在处理大规模数据时具有更高的效率。
- 适合处理用户排队等待的情况：链队列适用于处理用户排队等待的情况，例如银行排队、网络请求等。通过链队列，可以快速地插入新用户和删除已处理的用户。
链队列的缺点：
- 需要额外的存储空间：为了实现链表结构，链队列需要额外的存储空间来维护指针和节点。这会增加存储空间的消耗。
- 插入和删除操作可能引起内存分配和释放：在链队列中插入和删除元素时，可能需要动态分配和释放内存。这会增加操作的时间复杂度，并可能引起内存碎片化问题。
- 无法充分利用连续空间的优势：链表结构使得链队列无法像数组一样充分利用连续空间的优势，这会影响空间利用率和访问速度。
二、链队列的基本操作算法（C语言）????
1、宏定义
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define MAXSIZE 100
typedef int QElemtype;
typedef int Status;??2、创建结构体
//创建结构体
typedef struct QNode {
QElemtype data;
struct QNode *next;
} QNode, *QueuePtr;
typedef struct {
QueuePtr front;
QueuePtr rear;
} LinkQueue;3、链栈的初始化?
//链队列的初始化
Status InitQueue(LinkQueue &Q) {
Q.front = Q.rear = (QueuePtr) malloc(sizeof(QNode));
if (!Q.front) {
exit(OVERFLOW);
}
Q.front->next = NULL;
return OK;
}4、链队列的入队?
//链队列的入队
Status EnQueue(LinkQueue &Q, QElemtype e) {
QueuePtr p = (QueuePtr) malloc(sizeof(QNode));
if (!p) {
exit(OVERFLOW);
}
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}5、链队列的出队
//链队列的出队
Status DeQueue(LinkQueue &Q, QElemtype &e) {
if (Q.front == Q.rear) {
return ERROR;
}
QueuePtr p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if (Q.rear == p) {
Q.rear = Q.front;
}
delete p;
return OK;
}6、取链队列的对头元素
//取链列的对头元素
Status GetQueueHead(LinkQueue &Q, QElemtype &e) {
if (Q.front == Q.rear) {
return ERROR;
}
e = Q.front->next->data;
return OK;
}7、链队列的销毁
//队列的销毁
Status DestoryQueue(LinkQueue &Q) {
while (Q.front) {
Q.rear = Q.front->next;
delete (Q.front);
Q.front = Q.rear;
}
// printf("销毁成功！");
return OK;
}
8、链队列的清空
//清空
Status ClearQueue(LinkQueue &Q) {
Q.rear = Q.front->next;
while (Q.front->next) {
Q.rear = Q.rear->next;
delete (Q.front->next);
Q.front->next = Q.rear;
}
Q.rear = Q.front;
// printf("清空成功！");
return OK;
}9、判断链队列是否为空
//判断是否为空
Status QueueEmpty(LinkQueue &Q) {
if (Q.front == Q.rear) {
// printf("队列为空！\n");
return true;
} else {
return false;
}
// printf("该队列不为空！");
}10、求队列长度
//求队列长度
Status QueueLength(LinkQueue Q) {
int i = 0;
while (Q.front != Q.rear) {
i++;
Q.front = Q.front->next;
}
// printf("该队列长度为：%d", i);
return i;
}?11、遍历队列元素
//遍历队列
Status QueueTraverse(LinkQueue Q) {
QNode *p;
if (Q.front == Q.rear) {
return ERROR;
}
p = Q.front->next;//存储头元素
printf("从队头依次读出该队列中的元素值为: ");
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
return OK;
}三、链队列的基本操作完整代码（C语言）
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define MAXSIZE 100
typedef int QElemtype;
typedef int Status;
//创建结构体
typedef struct QNode {
QElemtype data;
struct QNode *next;
} QNode, *QueuePtr;
typedef struct {
QueuePtr front;
QueuePtr rear;
} LinkQueue;
//链队列的初始化
Status InitQueue(LinkQueue &Q) {
Q.front = Q.rear = (QueuePtr) malloc(sizeof(QNode));
if (!Q.front) {
exit(OVERFLOW);
}
Q.front->next = NULL;
return OK;
}
//链队列的入队
Status EnQueue(LinkQueue &Q, QElemtype e) {
QueuePtr p = (QueuePtr) malloc(sizeof(QNode));
if (!p) {
exit(OVERFLOW);
}
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}
//链队列的出队
Status DeQueue(LinkQueue &Q, QElemtype &e) {
if (Q.front == Q.rear) {
return ERROR;
}
QueuePtr p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if (Q.rear == p) {
Q.rear = Q.front;
}
delete p;
return OK;
}
//取链列的对头元素
Status GetQueueHead(LinkQueue &Q, QElemtype &e) {
if (Q.front == Q.rear) {
return ERROR;
}
e = Q.front->next->data;
return OK;
}
//队列的销毁
Status DestoryQueue(LinkQueue &Q) {
while (Q.front) {
Q.rear = Q.front->next;
delete (Q.front);
Q.front = Q.rear;
}
// printf("销毁成功！");
return OK;
}
//清空
Status ClearQueue(LinkQueue &Q) {
Q.rear = Q.front->next;
while (Q.front->next) {
Q.rear = Q.rear->next;
delete (Q.front->next);
Q.front->next = Q.rear;
}
Q.rear = Q.front;
// printf("清空成功！");
return OK;
}
//判断是否为空
Status QueueEmpty(LinkQueue &Q) {
if (Q.front == Q.rear) {
// printf("队列为空！\n");
return true;
} else {
return false;
}
// printf("该队列不为空！");
}
//求队列长度
Status QueueLength(LinkQueue Q) {
int i = 0;
while (Q.front != Q.rear) {
i++;
Q.front = Q.front->next;
}
// printf("该队列长度为：%d", i);
return i;
}
//遍历队列
Status QueueTraverse(LinkQueue Q) {
QNode *p;
if (Q.front == Q.rear) {
return ERROR;
}
p = Q.front->next;//存储头元素
printf("从队头依次读出该队列中的元素值为: ");
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
return OK;
}
//功能菜单列表
void show_help() {
printf("******* 功能菜单列表 *******\n");
printf("1----入队------------------\n");
printf("2----求链队列长度----------\n");
printf("3----出队------------------\n");
printf("4----取队头元素-------------\n");
printf("5----清空循环队列-----------\n");
printf("6----销毁循环队列-----------\n");
printf("7----判断循环队列是否为空-----\n");
printf("8----批量插入元素------------\n");
printf("9----显示队列元素------------\n");
printf("10----退出------------------\n\n");
}
//主函数
int main() {
LinkQueue LQ;
Status reIn = InitQueue(LQ);
if (reIn == OK) {
printf("链队列初始时成功 \n");
} else {
printf("链队列初始时失败 \n");
}
while (1) {
//功能菜单列表
show_help();
int flag;
printf("请输入所需的功能编号：\n");
scanf("%d", &flag);
switch (flag) {
case 1: {//入队
Status EnQueueindex;
printf("请输入插入元素(请在英文状态下输入例如:1): \n");
scanf("%d", &EnQueueindex);
Status rEnQueue = EnQueue(LQ, EnQueueindex);
if (rEnQueue == OK) {
printf("向链队列入队%d成功！\n", EnQueueindex);
} else {
printf("向链队列入队失败！\n");
}
}
break;
case 2: {//求链队列的长度
int length = QueueLength(LQ);
printf("链队列的长度为:%d。 \n\n", length);
}
break;
case 3: {//出队
QElemtype DeElem;
Status DeEn = DeQueue(LQ, DeElem);
if (DeEn == OK) {
printf("从链队列中出队成功，出队的元素为 %d! \n", DeElem);
} else {
printf("从链队列中出队失败！\n");
}
}
break;
case 4: {//求队头元素
QElemtype getEl;
Status reGet = GetQueueHead(LQ, getEl);
if (reGet == OK) {
printf("从链队列中取对头元素成功，队头元素为:%d! \n", getEl);
} else {
printf("从链队列中取对头元素成功 \n");
}
}
break;
case 5: { //清空
Status rClearStack = ClearQueue(LQ);
if (rClearStack == OK) {
printf("链队列清空成功！\n");
} else {
printf("链队列清空失败！\n");
}
}
break;
case 6: {//销毁
Status rDestroyStack = DestoryQueue(LQ);
if (rDestroyStack == OK) {
printf("链队列销毁成功！\n");
} else {
printf("链队列销毁失败！\n");
}
}
break;
case 7: {///判空
Status ClearStatus = QueueEmpty(LQ);
if (ClearStatus == true) {
printf("链队列为空！\n\n");
} else {
printf("链队列不为空！\n\n");
}
}
break;
case 8: {//批量插入
int on;
printf("请输入想要插入的元素个数：\n");
scanf("%d", &on);
QElemtype array[on];
for (int i = 1; i <= on; i++) {
printf("向链队列第%d个位置插入元素为:", i);
scanf("%d", &array[i]);
}
for (int i = 1; i <= on; i++) {
Status InsertStatus = EnQueue(LQ, array[i]);
if (InsertStatus == OK) {
printf("向链队列第%d个位置插入元素%d成功！\n", i, array[i]);
} else {
printf("向链队列第%d个位置插入元素%d失败！\n", i, array[i]);
}
}
}
break;
case 9: {//输出链表元素
QueueTraverse(LQ);
// printf("\n");
}
break;
case 10: {//退出程序
return 0;
}
break;
default: {
printf("输入错误，无此功能，请检查输入:\n\n");
}
}
}
return 1;
}
??四、运行结果
文章来源:https://blog.csdn.net/weixin_56814370/article/details/135831656
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
最新文章
- Python教程
- 深入理解 MySQL 中的 HAVING 关键字和聚合函数
- Qt之QChar编码（1）
- MyBatis入门基础篇
- 用Python脚本实现FFmpeg批量转换
- 深度学习建模从零开始步骤流程
- e2studio开发LPS28DFW气压计(1)----轮询获取气压计数据
- [论文笔记] 大模型gpu机器推理测速踩坑 (llama/gpt类)
- Docker 编译OpenHarmony 4.0 release
- 什么台灯对眼睛好？分享适合考研使用的护眼台灯
- Android BUG 之 Error: Activity class {} does not exist
- ZZ014城市轨道交通运营与维护赛题第6套
- 【Redis数据类型】String实现及应用场景
- 文章解读与仿真程序复现思路——中国电机工程学报EI\CSCD\北大核心《考虑系统调峰需求与光热电站收益平衡的储热容量优化配置》
- LeetCode 42 接雨水