假设以带头节点的单向循环链表示队列,并且只设一个指针指向队尾元素节点,试设计并验证相应的队列初始化、队列判空、入队列、出队列和遍历队列算法
时间: 2023-12-07 09:57:33 浏览: 78
数据结构算法-习题-答案-带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点注意不设头指针.docx
5星 · 资源好评率100%
队列的带头节点的单向循环链表示可以用如下结构体表示:
```
typedef struct Node {
int data;
struct Node *next;
} Node, *Queue;
// 初始化队列,创建头节点
void initQueue(Queue *rear) {
*rear = (Queue) malloc(sizeof(Node));
(*rear)->next = *rear;
}
// 判断队列是否为空
int isQueueEmpty(Queue rear) {
return rear->next == rear;
}
// 入队列,在队尾插入元素
void enqueue(Queue *rear, int data) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = data;
newNode->next = (*rear)->next;
(*rear)->next = newNode;
*rear = newNode;
}
// 出队列,删除队头元素
int dequeue(Queue *rear) {
if (isQueueEmpty(*rear)) {
printf("队列为空\n");
return -1;
}
Node *p = (*rear)->next;
int data = p->data;
(*rear)->next = p->next;
if (p == *rear) {
*rear = (*rear)->next;
}
free(p);
return data;
}
// 遍历队列
void traverseQueue(Queue rear) {
if (isQueueEmpty(rear)) {
printf("队列为空\n");
return;
}
Node *p = rear->next;
while (p != rear) {
printf("%d ", p->data);
p = p->next;
}
printf("%d\n", p->data);
}
```
其中,`initQueue`函数用于初始化队列,创建头节点;`isQueueEmpty`函数用于判断队列是否为空;`enqueue`函数用于在队尾插入元素;`dequeue`函数用于删除队头元素;`traverseQueue`函数用于遍历队列。
下面是一个使用该队列结构体的例子:
```
int main() {
Queue rear;
initQueue(&rear);
int i;
for (i = 0; i < 5; i++) {
enqueue(&rear, i);
}
traverseQueue(rear);
dequeue(&rear);
traverseQueue(rear);
return 0;
}
```
该例子中,首先调用`initQueue`函数初始化队列,然后使用`enqueue`函数入队列,使用`traverseQueue`函数遍历队列,使用`dequeue`函数出队列并再次遍历队列。
阅读全文