C 语言循环链表

介绍

循环链表是一种特殊的链表数据结构，它与普通链表的区别在于：循环链表的最后一个节点的指针指向链表的第一个节点，而不是指向 NULL。这种结构使得链表形成一个闭环，可以在某些场景下提供更高效的操作。

循环链表可以是单向的，也可以是双向的。在本文中，我们将重点介绍单向循环链表。

循环链表的定义

循环链表的基本结构与普通链表类似，每个节点包含两个部分：

数据域：存储节点的数据。
指针域：存储指向下一个节点的指针。

与普通链表不同的是，循环链表的最后一个节点的指针指向链表的头节点，而不是 NULL。

循环链表的实现

定义节点结构

首先，我们需要定义一个结构体来表示链表的节点：

c
struct Node {
    int data;           // 数据域
    struct Node* next;  // 指针域，指向下一个节点
};

创建循环链表

接下来，我们编写一个函数来创建一个简单的循环链表。假设我们要创建一个包含三个节点的循环链表：

c
#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

void createCircularLinkedList() {
    struct Node* head = NULL;
    struct Node* second = NULL;
    struct Node* third = NULL;

    // 分配内存
    head = (struct Node*)malloc(sizeof(struct Node));
    second = (struct Node*)malloc(sizeof(struct Node));
    third = (struct Node*)malloc(sizeof(struct Node));

    // 赋值
    head->data = 1;
    head->next = second;

    second->data = 2;
    second->next = third;

    third->data = 3;
    third->next = head;  // 最后一个节点指向头节点，形成循环

    // 打印链表
    struct Node* current = head;
    do {
        printf("%d -> ", current->data);
        current = current->next;
    } while (current != head);

    printf("HEAD\n");
}

int main() {
    createCircularLinkedList();
    return 0;
}

输出：

1 -> 2 -> 3 -> HEAD

备注

注意：在循环链表中，遍历时需要特别注意终止条件，通常使用 do-while 循环来确保至少遍历一次。

插入节点

在循环链表中插入节点的操作与普通链表类似，但需要特别注意处理头节点和尾节点的指针。

c
void insertNode(struct Node** head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;

    if (*head == NULL) {
        *head = newNode;
        newNode->next = newNode;  // 只有一个节点时，指向自己
    } else {
        struct Node* temp = *head;
        while (temp->next != *head) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->next = *head;
    }
}

删除节点

删除节点的操作也需要特别注意循环链表的特性，确保链表的闭环不被破坏。

c
void deleteNode(struct Node** head, int key) {
    if (*head == NULL) return;

    struct Node *current = *head, *prev = NULL;

    // 查找要删除的节点
    do {
        if (current->data == key) {
            break;
        }
        prev = current;
        current = current->next;
    } while (current != *head);

    // 如果节点不存在
    if (current->data != key) return;

    // 如果链表只有一个节点
    if (current->next == *head && prev == NULL) {
        *head = NULL;
        free(current);
        return;
    }

    // 如果删除的是头节点
    if (current == *head) {
        prev = *head;
        while (prev->next != *head) {
            prev = prev->next;
        }
        *head = current->next;
        prev->next = *head;
        free(current);
    } else {
        prev->next = current->next;
        free(current);
    }
}

实际应用场景

循环链表在某些场景下非常有用，例如：

约瑟夫问题：循环链表可以用于解决经典的约瑟夫问题，即一群人围成一圈，每隔一定数量的人就被淘汰，直到最后剩下一个人。
轮询调度：在操作系统中，循环链表可以用于实现轮询调度算法，确保每个任务都能公平地获得CPU时间。
环形缓冲区：循环链表可以用于实现环形缓冲区，用于数据流的处理。

总结

循环链表是一种非常有用的数据结构，特别适用于需要循环访问的场景。通过本文的学习，你应该已经掌握了循环链表的基本概念、实现方法以及实际应用场景。

提示

建议你尝试自己实现一个循环链表，并编写一些操作函数，如插入、删除、遍历等，以加深对循环链表的理解。

附加资源

练习

编写一个函数，计算循环链表中节点的数量。
实现一个函数，将两个循环链表合并为一个。
尝试用循环链表解决约瑟夫问题。

通过完成这些练习，你将更好地掌握循环链表的使用和操作。

介绍​

循环链表的定义​

循环链表的实现​

定义节点结构​

创建循环链表​

插入节点​

删除节点​

实际应用场景​

总结​

附加资源​

练习​

介绍