C++ 链式队列(不带头结点)

文章目录

    • ​​总结归纳​​
    • ​​代码实现​​

总结归纳

  1. 对于不带头结点队列 / 链表等数据结构第一个插入的结点总要特殊处理带头结点的数据结构就没有这个问题。
  2. 对于销毁队列 DestroyQueue(LinkQueue &Q, ElemType &x) ,只需要一个循环判断:若队列一直不为空,则一直出队。其他的数据结构也是似,通过一个递归实现。
  3. PS:返回 bo数据结构ol 型的好处在这里体现了,while 循环里可以直接通过 ! 判断。
// 销毁队列
bool DestroyQueue(LinkQueue &Q, ElemType &x) {
while (!QueueEmpty(Q)) {
DeQuene(Q, x); // 如果队列不为空,则一直出队
}
return true;
}
  1. 在编写入队函数 EnQueu出队旗的正确姿势e(LinkQueue &Q,c#委托 ElemType x) 中,出现了问题,代码本身没有错,但运时会抛出 Segmentation fault (cor系统运维面试题及答案e dumped) 错误,查询都说访问了错误的内存空间,搞来搞去不知道哪里出了问题,但申请结点后加了个判断就没问题了,搞不懂,但保险起见以后还是都这么写,申请结点后 if 判断一下:

代码实现

/*
链式队列(不带头结点)
*/
#include <iostream>
using namespace std;
typedef int ElemType;
// 结点
struct LinkNode {
ElemType data;
LinkNode *next;
};
// 链式队列
struct LinkQueue {
LinkNode *front, *rear; // 队头指针,队尾指针
};
// 初始化队列
void InitQueue(LinkQueue &Q) {
Q.front = NULL;
Q.rear = NULL;
}
// 队列判空
bool QueueEmpty(LinkQueue &Q) {
if (Q.front == NULL) {
return true;
} else {
return false;
}
}
// 入队
bool EnQueue(LinkQueue &Q, ElemType x) {
// LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
LinkNode *s = new LinkNode;
if (s == NULL)
return false;
s->data = x;
s->next = NULL;
if (Q.front == NULL) {
Q.front = s;
Q.rear = s; // 队头队尾指针指向同一位置
} else {
Q.rear->next = s; // 新元素插入
Q.rear = s; // 修改表尾指针
}
return true;
}
// 出队
bool DeQuene(LinkQueue &Q, ElemType &x) {
if (Q.front == NULL) {
return false;
} else {
LinkNode *p = Q.front; // 指向头结点
x = p->data;
if (Q.rear == p) { // 队列中只有一个元素
Q.front = NULL;
Q.rear = NULL;
} else {
Q.front = p->next; // 更新队头指针
}
delete p;
return true;
}
}
// 获取队头元素
bool GetHead(LinkQueue &Q, ElemType &head) {
if (Q.front == NULL) {
return false;
} else {
head = Q.front->data;
return true;
}
}
// 获取队列长度
int GetLength(LinkQueue &Q, ElemType &len) {
if (Q.front == NULL) {
return 0;
} else {
len = 1;
LinkNode *p = Q.front; // 指向队头
while (p != Q.rear) {
p = p->next;
len++;
}
return len;
}
}
// 销毁队列
bool DestroyQueue(LinkQueue &Q, ElemType &x) {
while (!QueueEmpty(Q)) {
DeQuene(Q, x); // 如果队列不为空,则一直出队
}
return true;
}
int main() {
LinkQueue Q;
InitQueue(Q);
ElemType head, pop, length;
cout << "队列是否为空:" << QueueEmpty(Q) << endl;
for (int i = 10; i < 15; i++) {
EnQueue(Q, i);
}
cout << "队列是否为空:" << QueueEmpty(Q) << endl;
GetHead(Q, head);
cout << "队头元素:" << head << endl;
cout << "队列长度:" << GetLength(Q, length) << endl;
DeQuene(Q, pop);
cout << "出队元素:" << pop << endl;
GetHead(Q, head);
cout << "队头元素:" << head << endl;
cout << "队列长度:" << GetLength(Q, length) << endl;
DestroyQueue(Q, head);
cout << "队列是否为空:" << QueueEmpty(Q) << endl;
cout << "队列长度:" << GetLength(Q, length) << endl;
}