用C语言,非伪代码的形式设计一个以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(不设头指针),试编写相应的入队、出队算法。
时间: 2024-10-04 20:04:32 浏览: 51
C语言单链队列的表示与实现实例详解
在C语言中,我们可以设计一个循环链表来表示队列,其中只有一个指向队尾元素的指针`rear`。这里是一个简单的实现:
首先,我们需要定义一个结构体`Node`表示链表节点,包含数据域`data`和下一个节点的指针`next`:
```c
typedef struct Node {
int data;
struct Node *next;
} Node;
```
然后,我们创建一个全局变量`tail`作为循环链表的尾部指针:
```c
Node *tail = NULL;
```
### 入队操作 (enqueue)
入队操作(Enqueue)会将新的元素添加到队列尾部:
```c
void enqueue(int value) {
// 创建新节点
Node *new_node = (Node*)malloc(sizeof(Node));
if (new_node == NULL) {
printf("Memory allocation failed.\n");
return;
}
new_node->data = value;
// 如果队列为空,直接设置新节点为头尾
if (tail == NULL) {
tail = new_node;
new_node->next = tail; // 自环
} else {
// 将新节点链接到尾部
new_node->next = tail->next;
tail->next = new_node; // 更新尾部指针
// 自环
tail = tail->next;
}
}
```
### 出队操作 (dequeue)
出队操作(Dequeue)会移除并返回队列头部的元素,如果队列为空则返回错误:
```c
int dequeue() {
if (tail == NULL) {
printf("Queue is empty.\n");
return -1; // 或者抛出异常
}
int value = tail->data;
// 当前节点成为新的尾部
Node *temp = tail->next;
free(tail); // 释放旧尾部节点
tail = temp;
// 如果队列仅剩一个元素,调整自环
if (tail == tail->next) {
tail = NULL;
}
return value;
}
```
阅读全文