考研篇——数据结构王道3.2.3_队列的链式实现
目录
- 1.链队列
- 2.代码实现
- 2.1 带头结点
- 2.2 不带头结点
- 总结
1.链队列
队列是一种线性结构,线性是指其在逻辑结构,上一节我们顺序存储实现队列,这次链式存储实现队列。与单链表的实现不同的是,只能在表头删除,表尾插入。
2.代码实现
2.1 带头结点
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LinkNode {
ElemType data;
struct LinkNode* next;
}LinkNode;
typedef struct {
LinkNode* front, * rear;
//int size;//如果频繁使用队列长度的话,考虑增加变量size记录,否则每遍历的时间复杂度是O(n)
}LinkQueue;
//带头结点
void InitQueue(LinkQueue& Q)
{
Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
if (Q.front == NULL)
return;
Q.front->next = NULL;
}
bool IsEmpty(LinkQueue Q)
{
if (Q.front == Q.rear)//Q.front->next==NULL
return true;
else
return false;
}
void EnQueue(LinkQueue& Q, ElemType x)
{
LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
if (s == NULL)
return;
s->next = NULL;
s->data = x;
Q.rear->next = s;
Q.rear = s;
}
bool DeQueue(LinkQueue& Q, ElemType& x) {
if (Q.front == Q.rear)
return false;
LinkNode* s = Q.front->next;
x = s->data;
Q.front->next = s->next;
if (Q.rear == s)
Q.rear = Q.front;
free(s);
return true;
}
2.2 不带头结点
与代码2.1相同的部分省略
//不带头结点
void InitQueue1(LinkQueue &Q)
{
Q.front = Q.rear = NULL;
}
bool IsEmpty1(LinkQueue Q)
{
if (Q.front == NULL)//Q.rear==NULL
return true;
else
return false;
}
void EnQueue1(LinkQueue& Q, ElemType x)
{
LinkNode* s= (LinkNode*)malloc(sizeof(LinkNode));
if (s == NULL)
return;
s->next = NULL;
s->data = x;
if (Q.rear == NULL)
Q.front = Q.rear = s;//不带头结点,第一个元素入队时单独处理,与后续元素入队不同的是,要更改头指针的指向
else {
Q.rear->next = s;
Q.rear = s;
}
}
bool DeQueue1(LinkQueue& Q, ElemType& x) {
if (Q.front == Q.rear)
return false;
LinkNode* p = Q.front;
x = p->data;
Q.front = p->next;
if (Q.rear == p)
Q.rear = Q.front=NULL;
free(p);
return true;
}
总结
链式存储实现的队列与顺序存储相比,好处在于,顺序存储的空间是预分配的,一旦满了就不能再插入。但链式存储一般不存在队满的情况,除非内存不足。
在书写代码时,思考不带头结点与带头节点在操作上的区别,是否单独处理要分情况。