假设以带头结点的单向循环链表表示队列,并且只设一个指针指向队尾 元素结点(注意:不设头指针),试设计并验证相应的队列初始化、队列判空、入队列、出队列和遍历队列算法。用c语言编写,要求能够输入数据,并实现所有的功能
时间: 2024-05-14 20:19:47 浏览: 96
好的,我会根据要求给您演示关于单向循环链表实现队列的相应算法。以下是代码演示及解释:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构
typedef struct node {
int data;
struct node *next;
} node;
// 定义队列结构
typedef struct queue {
node *rear; // rear 指向队尾元素结点
} queue;
// 初始化队列
void initQueue(queue *q) {
q->rear = NULL; // 节点为空
}
// 判断队列是否为空
int isQueueEmpty(queue *q) {
return q->rear == NULL;
}
// 入队列
void enqueue(queue *q, int data) {
node *newNode = (node *)malloc(sizeof(node)); // 创建新的节点
newNode->data = data;
if (isQueueEmpty(q)) { // 如果队列为空,则将队列尾指向该节点
q->rear = newNode;
newNode->next = newNode; // 将该节点的 next 指向自己,因为是循环链表
} else {
newNode->next = q->rear->next; // 将该节点的 next 指向队列头结点
q->rear->next = newNode; // 将队列尾节点的 next 指向该节点
q->rear = newNode; // 将队列尾指向该节点
}
}
// 出队列
int dequeue(queue *q) {
if (isQueueEmpty(q)) {
printf("队列已经为空,无法继续出队列操作!\n");
return -1;
}
int data = q->rear->next->data; // 取出队列头节点的 data 值
node *temp = q->rear->next; // 创建一个临时节点指向队列头节点
if (q->rear->next == q->rear) { // 如果只剩一个节点
q->rear = NULL;
} else {
q->rear->next = q->rear->next->next; // 将队列头节点的 next 指向下一个节点
}
free(temp); // 删除队列头节点,释放内存
return data;
}
// 遍历队列
void traverse(queue *q) {
if (isQueueEmpty(q)) {
printf("队列为空,无法遍历!\n");
return;
}
node *temp = q->rear->next;
while (temp != q->rear) { // 遍历节点
printf("%d ", temp->data);
temp = temp->next;
}
printf("%d\n", q->rear->data);
}
int main() {
queue q;
initQueue(&q);
printf("请输入队列元素,以-1结束:\n");
int data;
scanf("%d", &data);
while (data != -1) { // 输入队列元素
enqueue(&q, data);
scanf("%d", &data);
}
printf("当前队列元素为:");
traverse(&q);
printf("出队列的元素为:%d\n", dequeue(&q));
printf("当前队列元素为:");
traverse(&q);
return 0;
}
```
以上就是单向循环链表实现队列的相关算法及代码示例。如果您有其他问题,欢迎继续提出。
阅读全文