头歌c语言单链表循环队列
时间: 2023-11-02 16:03:05 浏览: 64
头歌C语言单链表循环队列是一种使用单链表实现的循环队列数据结构。它具有如下特点:
首先,它使用一个带有头节点的单链表来存储队列中的元素,头节点用于标识队列的头部位置。
其次,队列的尾部指针rear指向链表的最后一个节点,用于指示下一个元素应该插入的位置。
循环队列的实现可以通过使尾指针rear指向头节点的前一个节点,从而形成一个闭环,实现循环的效果。这样在插入和删除元素时,只需修改尾指针rear即可。
当队列为空时,头指针和尾指针都指向头节点。当队列满时,尾指针指向链表的最后一个节点,头指针指向第一个元素。
插入元素操作时,首先判断队列是否已满,如果满则无法插入;否则,创建一个新节点,将数据插入到新节点的数据域中,然后将新节点插入到链表尾部,修改尾指针rear指向新节点。
删除元素操作时,首先判断队列是否为空,如果为空则表示无法删除;否则,删除头节点的下一个节点,并将头指针指向新的头节点。
通过以上方式,循环队列可以不断处理新元素,并保持队列的大小固定。
总之,头歌C语言单链表循环队列是一种基于单链表实现的循环队列,它通过头节点和尾指针来标识队列的头部和尾部位置,通过修改尾指针来实现循环操作。它具有简单高效的特点,适用于需要频繁进行插入和删除操作的场景。
相关问题
带头结点的单链表和双链表
带头结点的单链表是指在链表的头部增加一个额外的结点,该结点不存储具体的数据,而是用来作为链表的头指针的前驱。这样做的好处是在进行插入和删除操作时不需要特殊处理链表为空的情况,因为头结点始终存在。
双链表是指每个结点都有两个指针,一个指向直接后继结点,一个指向直接前驱结点。这样可以方便地从任意一个结点开始访问它的前驱结点和后继结点。与单链表相比,双链表的操作更加灵活,但是相应地需要多维护一个指针域。
所以,带头结点的单链表和双链表的区别在于双链表每个结点都有指向前驱结点的指针,而带头结点的单链表只有指向后继结点的指针。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* [C语言使用非循环双向链表实现队列](https://download.csdn.net/download/weixin_38704565/13757045)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 33.333333333333336%"]
- *2* [链表(一) -- 单链表与双向链表](https://blog.csdn.net/JeremyIverson/article/details/104282271)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 33.333333333333336%"]
- *3* [数据结构之单链表与双链表](https://blog.csdn.net/guyuanxiang1995/article/details/76927042)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 33.333333333333336%"]
[ .reference_list ]
用C语言编写以带头结点,并只设尾指针的循环单链表,实现这种链式队列的初始化,入队列,出队列,取元素,判断非空函数。
```c
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
ElementType data;
PtrToNode next;
};
typedef struct {
PtrToNode rear; // 只设尾指针
} Queue;
// 初始化队列
void initQueue(Queue *q) {
PtrToNode head = (PtrToNode) malloc(sizeof(struct Node));
// 空队列时,head->next指向自己
head->next = head;
q->rear = head;
}
// 判断队列是否为空
int isEmpty(Queue *q) {
return q->rear->next == q->rear;
}
// 入队列
void enQueue(Queue *q, ElementType x) {
PtrToNode newNode = (PtrToNode) malloc(sizeof(struct Node));
newNode->data = x;
newNode->next = q->rear->next; // 新节点的next指向head
q->rear->next = newNode; // 把新节点放在最后
q->rear = newNode; // 尾指针指向新节点
}
// 出队列
ElementType deQueue(Queue *q) {
if (isEmpty(q)) {
printf("队列为空,无法出队列!\n");
return -1;
}
PtrToNode firstNode = q->rear->next->next; // 第一个节点
ElementType x = firstNode->data;
q->rear->next->next = firstNode->next; // 删除firstNode
if (q->rear == firstNode) { // 当出队列的是最后一个节点
q->rear = q->rear->next; // 修改rear指向最后一个节点,即head
}
free(firstNode);
return x;
}
// 取队首元素
ElementType getFront(Queue *q) {
if (isEmpty(q)) {
printf("队列为空,无法取元素!\n");
return -1;
}
return q->rear->next->next->data;
}
// 打印队列
void printQueue(Queue *q) {
if (isEmpty(q)) {
printf("队列为空,无法输出!\n");
return;
}
PtrToNode node = q->rear->next->next;
while (node != q->rear->next) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
// 主函数测试
int main() {
Queue q;
initQueue(&q);
printf("队列是否为空:%d\n", isEmpty(&q));
enQueue(&q, 1);
enQueue(&q, 2);
enQueue(&q, 3);
printf("队首元素:%d\n", getFront(&q));
printQueue(&q);
printf("出队列的元素:%d\n", deQueue(&q));
printf("队首元素:%d\n", getFront(&q));
printQueue(&q);
return 0;
}
```