假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针),试编写相应的定义,置空队、入队列和出队列,遍历的算法。
时间: 2023-05-24 12:07:35 浏览: 58
```
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node, *Queue;
// 创建循环链表队列
Queue createQueue(void) {
Queue q = (Queue) malloc(sizeof(Node));
q->next = q; // 空队时,队头和队尾的指针都指向头结点
return q;
}
// 置空队列
void clearQueue(Queue q) {
Node *cur = q->next, *tmp = NULL;
while (cur != q) {
tmp = cur->next;
free(cur);
cur = tmp;
}
q->next = q; // 空队时,队头和队尾的指针都指向头结点
}
// 入队列(插入队尾)
void enQueue(Queue q, int data) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = data;
newNode->next = q; // 新结点的next指向头结点
Node *tail = q;
while (tail->next != q) { // 找到队尾结点所在位置
tail = tail->next;
}
tail->next = newNode; // 将新结点插入队尾,旧队尾的next指向新结点
}
// 出队列(删除队头)
void deQueue(Queue q) {
if (q->next == q) { // 空队时
printf("队列已空,无法出队。\n");
return;
}
Node *head = q->next;
q->next = head->next;
printf("出队元素:%d\n", head->data);
free(head);
}
// 遍历队列
void traverseQueue(Queue q) {
if (q->next == q) { // 空队时
printf("队列为空。\n");
return;
}
Node *cur = q->next;
printf("队列元素:");
while (cur != q) {
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
int main() {
Queue q = createQueue();
enQueue(q, 1);
enQueue(q, 2);
enQueue(q, 3);
traverseQueue(q);
deQueue(q);
traverseQueue(q);
deQueue(q);
deQueue(q);
deQueue(q);
deQueue(q);
traverseQueue(q);
clearQueue(q);
traverseQueue(q);
free(q); // 释放头结点
return 0;
}
```
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)