采用一个不带头结点只有一个尾结点指针rear的循环单链表存储队列,设计队列的初始化、进队和出队等算法。完整算法
时间: 2024-05-07 20:18:14 浏览: 134
数据结构算法习题答案带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针).docx
5星 · 资源好评率100%
1. 队列初始化算法:
```
void InitQueue(LinkQueue &Q) {
Q.rear = NULL;
}
```
2. 进队算法:
```
void EnQueue(LinkQueue &Q, ElemType x) {
QueuePtr p = (QueuePtr)malloc(sizeof(QNode)); // 创建新结点
p->data = x;
if (Q.rear == NULL) { // 队列为空,插入第一个结点
Q.rear = p;
p->next = p;
} else {
p->next = Q.rear->next; // 新结点插入到队尾之后
Q.rear->next = p;
Q.rear = p; // 修改队尾指针
}
}
```
3. 出队算法:
```
bool DeQueue(LinkQueue &Q, ElemType &x) {
if (Q.rear == NULL) { // 队列为空
return false;
}
if (Q.rear->next == Q.rear) { // 队列中只有一个结点
x = Q.rear->data;
free(Q.rear);
Q.rear = NULL;
} else {
QueuePtr p = Q.rear->next; // 取出队头结点
x = p->data;
Q.rear->next = p->next; // 修改队头指针
free(p);
}
return true;
}
```
阅读全文