C语言实现-带头结点循环链表队列（单指针）

C语言实现：带头结点循环链表队列（单指针）

本文介绍如何使用带头结点的循环链表实现队列，并只使用一个指针指向队尾元素结点，包含队列的初始化、入队列、出队列操作的C语言代码示例和详细解释。

1. 队列结构定义c#include <stdio.h>#include <stdlib.h>#include <stdbool.h>

typedef int QElemType;

typedef struct QNode { QElemType data; struct QNode *next;} QNode, *LinkQueue;

QElemType: 定义队列元素类型，这里以 int 为例，可以根据需要修改。- QNode: 定义队列节点结构体，包含数据域 data 和指向下一个节点的指针域 next。- LinkQueue: 定义指向队列节点的指针类型。

2. 队列初始化cvoid InitQueue(LinkQueue* Q) { Q = (LinkQueue)malloc(sizeof(QNode)); (Q)->next = *Q; // 链接头节点的指针域指向自己，表示空队列}

InitQueue 函数用于初始化队列。- 首先，动态分配一个头节点，并将 Q 指向它。- 然后，将头节点的 next 指针指向自身，表示这是一个空队列。

3. 入队列cvoid EnQueue(LinkQueue Q, QElemType e) { QNode* newNode = (QNode*)malloc(sizeof(QNode)); newNode->data = e;

// 将新节点插入到队尾    newNode->next = Q->next;    Q->next = newNode;    Q = newNode;  // 更新队尾指针}

EnQueue 函数用于将元素 e 入队列。- 首先，动态分配一个新节点 newNode，并将数据 e 存入其中。- 然后，将 newNode 插入到队尾，即将 newNode 的 next 指针指向原先队尾节点的下一个节点（即头节点），再将队尾节点的 next 指针指向 newNode。- 最后，更新队尾指针 Q，使其指向新的队尾节点 newNode。

4. 出队列cbool DeQueue(LinkQueue Q, QElemType* e) { if (Q->next == Q) { return false; // 队列为空，无法出队列 }

QNode* frontNode = Q->next->next;    *e = frontNode->data;

// 删除队头节点    Q->next->next = frontNode->next;    free(frontNode);

return true;}

DeQueue 函数用于将队头元素出队列，并将出队的元素保存到 e 指向的变量中。- 首先，判断队列是否为空，如果为空则返回 false。- 否则，获取队头节点 frontNode。- 将 frontNode 的数据保存到 e 指向的变量中。- 更新头节点的 next 指针，指向下一个节点，从而删除原队头节点。- 释放 frontNode 的内存空间。- 最后，返回 true，表示出队成功。

5. 完整代码示例c#include <stdio.h>#include <stdlib.h>#include <stdbool.h>

typedef int QElemType;

typedef struct QNode { QElemType data; struct QNode *next;} QNode, *LinkQueue;

// 初始化队列void InitQueue(LinkQueue* Q) { *Q = (LinkQueue)malloc(sizeof(QNode)); (*Q)->next = *Q; }

// 入队列void EnQueue(LinkQueue Q, QElemType e) { QNode* newNode = (QNode*)malloc(sizeof(QNode)); newNode->data = e; newNode->next = Q->next; Q->next = newNode; Q = newNode; }

// 出队列bool DeQueue(LinkQueue Q, QElemType* e) { if (Q->next == Q) { return false; } QNode* frontNode = Q->next->next; *e = frontNode->data; Q->next->next = frontNode->next; free(frontNode); return true;}

int main() { LinkQueue Q; QElemType e;

// 初始化队列    InitQueue(&Q);

// 入队列    EnQueue(Q, 1);    EnQueue(Q, 2);    EnQueue(Q, 3);

// 出队列    while (DeQueue(Q, &e)) {        printf('%d ', e);    }    printf('

');

return 0;}

输出结果:

1 2 3

这段代码演示了如何使用带头结点的循环链表实现队列，并使用单指针指向队尾元素，包含了队列的初始化、入队、出队等操作。

C语言实现-带头结点循环链表队列（单指针）