- 1收藏这篇两万字总结，❤️Docker❤️这一块保证你拿捏的死死的，我说的，耶稣都不行
- 2GEE代码实例教程详解：地表温度长时间序列分析_gee案例——如何利用landsat数据中的温度数据进行指定区域不同年份的温度计算
- 3HTML5期末大作业：游戏网站设计——腾讯游戏(页)学生HTML个人网页作业作品下载 个人网页设计制作 大学生个人网站作业模板 简单个人网页制作_html5网页游戏期末
- 4CasaOS设备使用Docker安装SyncThing文件同步神器并实现远程管理_docker syncthing
- 5关于com.microsoft.sqlserver.jdbc.SQLServerException: 驱动程序无法通过使用安全套接字层(SSL)加密与 SQL Server 建立安全连接。错误:“ja...
- 6合并k个升序链表
- 7pandas使用笔记(一)导入,查看,读取数据_导入pand库
- 8鲇鱼效应_鲇鱼效应和鲶鱼效应
- 9服务器模式
- 10使用git管理gitee（码云）项目
队列的链式存储结构与实现_2. 链队列定义与实现 (1)链队列的存储结构定义(在.h文件中定义,采用分离编译的方
赞
踩
前言
在前面我们学习了队列的概念与循环队列，我们知道了循环链表的队列长度事先就得确定好，但是实际中队列长度我们事先大多不知道，所以还是得研究一下动态的队列长度的队列储存与实现。
虽然顺序存储也可以通过realloc来实现扩容，但是顺序存储出队列不太好出——①如果队头位置定在下标0的位置，出队列的效率低；②如果每一次出队列队头位置+1，虽然效率高了，但是空间利用率低下。
所以对于动态的队列长度的队列储存与实现，我们用链式结构实现更优一些，下面我们就来学习队列的链式存储结构与实现。
一、队列的链式存储结构与实现
1、队列的链式存储结构
队列的链式存储结构，就是使用链表实现，可以简称为链队列。注意该链队列是受到限制的，要满足队列先进先出FIFO(first in first out)的原则。
链队列结构的分析：
①实现我们选择单链表，因为节省空间。
②为了方便先进先出的操作，我们将队头指针指向链队列的头结点，队尾指针指向终端结点（单链表我们为什么不定义一个尾指针呢——因为在单链表tail只能解决尾插，还不如不用）。如下图：
不带哨兵位
带哨兵位
③空队列时，不带哨兵位——head = tail = NULL；带哨兵位——head与tail指向哨兵位。
2、队列的链式存储实现
（1）（无哨兵位）链队列结构的类型
解读：
①链队列由一个个结点组成，所以需要定义链队列结点类型。
②为了方便先进先出的操作，所以定义队首指针与队尾指针。
③为了方便求队列有效数据个数，所以定义一个size储存个数（我们可以使用哨兵位来存储size吗——不可以，如当数据域为char时，129就溢出了。）。
④多个数据组成的复杂类型，最好将其定义为结构体（因为方便传参数，不管要改变结构体的多少成员，我们只需传结构体一个变量即可）。
代码示例：
//无哨兵位链队列的实现 //链队列元素类型的重命名（①方便更改；②见名知意） typedef int QDataType; //链队列结点类型 typedef struct QueueNode { QDataType data;//数据域 struct QueueNode* next;//指向后继结点 }QNode; //链队列的结构类型 typedef struct Queue { QNode* head;//队首指针——指向队头结点 QNode* tail;//队尾指针——指向队尾结点 int size;//保存有效数据个数——方便 }Queue;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
（2）链队列的接口实现
0X00队列的初始化
解读： 首先结构体指针pq一定不为空，为了程序的健壮性断言一下。其次初始化队首指针、队尾指针与有效数据个数。
代码示例：
//初始化链队列
void QueueInit(Queue* pq)
{
//断言pq不为空
assert(pq);
//链队列为空时
pq->head = pq->tail = NULL;//不带哨兵位
pq->size = 0;//空队列，有效数据个数为0
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
0X01队列的销毁
解读：
①断言pq不为空。
②在堆区申请的空间，如果不用记得自己释放，避免内存泄漏。
③链队列的销毁与链表的销毁一样，要从头结点逐个向后释放。注意释放cur结点之前要先保存它的后继结点，否则找不到。
④销毁结束之后，防止野指针将队首与队尾指针置为空。并且有效个数也为0。
代码示例：
//销毁链队列 void QueueDesttroy(Queue* pq) { assert(pq); //保存队头位置 QNode* cur = pq->head; //链队列的销毁与链表一样，要从头指针逐个销毁 while (cur) { //保存cur的后继结点 QNode* next = cur->next; //释放cur free(cur); //cur向后迭代 cur = next; } //释放完记得将队首指针与队尾指针置为空 pq->head = pq->tail = NULL; //有效数据个数为0 pq->size = 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
0X02入队列
解读：
①断言pq不为空。
②创建新节点，注意判断是否开辟成功，并且malloc之后记得初始化新节点。
③入队列，在队尾指针追加一个元素，即尾插。
④尾插注意分情况：情况1——队列为空，即头插，head与tail都要改变；情况2——队列不为空，即正常尾插，先链接再改变tail。
⑤入队列结束后，记得有效数据个数+1。
代码示例：
//入队列——队尾追加一个元素 void QueuePush(Queue* pq, QDataType x) { assert(pq); //创建新的队列结点 QNode* newnode = (QNode*)malloc(sizeof(QNode)); //判断是否开辟成功 if (NULL == newnode) { //打印错误信息 perror("malloc fail"); return; } //malloc不会初始化，记得自己初始化新节点 newnode->data = x; newnode->next = NULL; //入队列，即尾插 //情况1：队列为空时，队首与队尾都要改变 if (NULL == pq->head) { //head为空，tail也一定为空 assert(pq->tail == NULL); //tail(head)指向newnode pq->tail = pq->head = newnode; } //情况2：队列不为空，只改变队尾 else { //草图：tail newnode（待插） pq->tail->next = newnode; //更新队尾位置 pq->tail = newnode; } //入队之后有效数据个数+1 pq->size++; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
0X03出队列
解读：
①断言pq不为空。
②出队列，即删除队首元素，要断言队列不为空。
③删除队首元素注意tail是否要改变。情况1——只有一个结点时，释放之后head与tail都要置为空；情况2——有两个及以上结点——tail不会变，只改变head，注意要先保存head的后继结点，再释放头结点，最后链接。
④出队列之后，有效数据个数-1。
代码示例：
//出队列——队头删除一个元素 void QueuePop(Queue* pq) { assert(pq); //断言队列不为空 assert(!QueueEmpty(pq)); //出队列，即头删 //情况1：只有一个结点，删除后队首指针与队尾指针都要置为空 if (NULL == pq->head->next) { //草图：head（待删） free(pq->head); //避免野指针，队首指针与队尾指针都要置为空 pq->head = pq->tail = NULL; } //情况2：有两个及以上结点，删除后只改变队首指针 else { //head（待删） headnext QNode* next = pq->head->next; free(pq->head); pq->head = next; } //出队列后，有效数据个数-1 pq->size--; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
0X04获取队列中的元素个数
解读：
①断言pq不为空。
②直接返回size即可，从这里就可以看出我们在队列结构中添加size成员的好处。
代码示例：
**//获取队列中的元素个数
int QueueSize(Queue* pq)
{
assert(pq);
//从这就能看出我们在队列成员中添加size的作用，直接返回size即可
return pq->size;
}**
- 1
- 2
- 3
- 4
- 5
- 6
- 7
0X05检查队列是否为空
解读：
①断言pq不为空。
②有两种方式判断队列是否为空：方式1——有效数据个数为0，即表示队列为空；方式2——head与tail都为空，也表示队列为空。
代码示例：
//检查队列是否为空——为空返回真。
bool QueueEmpty(Queue* pq)
{
assert(pq);
//size等于0，即队列为空
return pq->size == 0;
//队首指针与队尾指针为空，也表示队列为空
//return (pq->head == NULL && pq->tail == NULL);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
0X06获取队首元素
解读：
①断言pq不为空。
②断言队列不为空。
③直接返回队首元素pq->head->data即可。
代码示例：
//获取队首元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
//断言队列不为空
assert(!QueueEmpty(pq));
//返回队首元素
return pq->head->data;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
0X07获取队尾元素
解读：
①断言pq不为空。
②断言队列不为空。
③直接返回队尾元素pq->tail->data即可。
代码示例：
//获取队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
//断言队列不为空
assert(!QueueEmpty(pq));
//返回队尾元素
return pq->tail->data;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
总结：
①注意删除与获取队列元素时，都要判断队列不为空。
②入队列注意head是否要改变，出队列tail是否要改变。
③在入队列、出队列、销毁队列、初始化队列时队列的有效数据个数都有改变。
④free释放之后，指针的指向不会改变，防止野指针，记得free之后指针一般置为空等等。
二、总代码
1、Queue.h——声明头文件、队列结构、队列接口等
//头文件的声明 #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> //无哨兵位链队列的实现 //链队列元素类型的重命名（①方便更改；②见名知意） typedef int QDataType; //链队列结点类型 typedef struct QueueNode { QDataType data;//数据域 struct QueueNode* next;//指向后继结点 }QNode; //链队列的结构类型 typedef struct Queue { QNode* head;//队首指针——指向队头结点 QNode* tail;//队尾指针——指向队尾结点 int size;//保存有效数据个数——方便 }Queue; //链队列接口函数的声明 //初始化链队列 void QueueInit(Queue* pq); //销毁链队列 void QueueDesttroy(Queue* pq); //入队列——队尾追加一个元素 void QueuePush(Queue* pq, QDataType x); //出队列——队头删除一个元素 void QueuePop(Queue* pq); //获取队列中的元素个数 int QueueSize(Queue* pq); //检查队列是否为空——为空返回真。 bool QueueEmpty(Queue* pq); //获取队首元素 QDataType QueueFront(Queue* pq); //获取队尾元素 QDataType QueueBack(Queue* pq);
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
2、Queue.c——接口的实现
#include"Queue.h" //初始化链队列 void QueueInit(Queue* pq) { //断言pq不为空 assert(pq); //链队列为空时 pq->head = pq->tail = NULL;//不带哨兵位 pq->size = 0;//空队列，有效数据个数为0 } //销毁链队列 void QueueDesttroy(Queue* pq) { assert(pq); //保存队头位置 QNode* cur = pq->head; //链队列的销毁与链表一样，要从头指针逐个销毁 while (cur) { //保存cur的后继结点 QNode* next = cur->next; //释放cur free(cur); //cur向后迭代 cur = next; } //释放完记得将队首指针与队尾指针置为空 pq->head = pq->tail = NULL; //有效数据个数为0 pq->size = 0; } //入队列——队尾追加一个元素 void QueuePush(Queue* pq, QDataType x) { assert(pq); //创建新的队列结点 QNode* newnode = (QNode*)malloc(sizeof(QNode)); //判断是否开辟成功 if (NULL == newnode) { //打印错误信息 perror("malloc fail"); return; } //malloc不会初始化，记得自己初始化新节点 newnode->data = x; newnode->next = NULL; //入队列，即尾插 //情况1：队列为空时，队首与队尾都要改变 if (NULL == pq->head) { //head为空，tail也一定为空 assert(pq->tail == NULL); //tail(head)指向newnode pq->tail = pq->head = newnode; } //情况2：队列不为空，只改变队尾 else { //草图：tail newnode（待插） pq->tail->next = newnode; //更新队尾位置 pq->tail = newnode; } //入队之后有效数据个数+1 pq->size++; } //出队列——队头删除一个元素 void QueuePop(Queue* pq) { assert(pq); //断言队列不为空 assert(!QueueEmpty(pq)); //出队列，即头删 //情况1：只有一个结点，删除后队首指针与队尾指针都要置为空 if (NULL == pq->head->next) { //草图：head（待删） free(pq->head); //避免野指针，队首指针与队尾指针都要置为空 pq->head = pq->tail = NULL; } //情况2：有两个及以上结点，删除后只改变队首指针 else { //head（待删） headnext QNode* next = pq->head->next; free(pq->head); pq->head = next; } //出队列后，有效数据个数-1 pq->size--; } //获取队列中的元素个数 int QueueSize(Queue* pq) { assert(pq); //从这就能看出我们在队列成员中添加size的作用，直接返回size即可 return pq->size; } //检查队列是否为空——为空返回真。 bool QueueEmpty(Queue* pq) { assert(pq); //size等于0，即队列为空 return pq->size == 0; //队首指针与队尾指针为空，也表示队列为空 //return (pq->head == NULL && pq->tail == NULL); } //获取队首元素 QDataType QueueFront(Queue* pq) { assert(pq); //断言队列不为空 assert(!QueueEmpty(pq)); //返回队首元素 return pq->head->data; } //获取队尾元素 QDataType QueueBack(Queue* pq) { assert(pq); //断言队列不为空 assert(!QueueEmpty(pq)); //返回队尾元素 return pq->tail->data; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
3、Test.c——测试
#include"Queue.h" int main() { //定义一个队列对象 Queue pq; //初始化队列 QueueInit(&pq); //入队列：1 2 3 4 5 QueuePush(&pq, 1); QueuePush(&pq, 2); QueuePush(&pq, 3); QueuePush(&pq, 4); QueuePush(&pq, 5); //打印队列的个数 printf("%d\n", QueueSize(&pq)); //出队列 while (!QueueEmpty(&pq)) { //打印队首元素 printf("%d ", QueueFront(&pq)); //出队列 QueuePop(&pq); } //销毁队列 QueueDesttroy(&pq); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
