C 语言循环链表

循环链表是链表数据结构的一种变体，其特点是链表的最后一个节点不再指向空（NULL），而是指向链表的第一个节点，形成一个闭环。这种结构在某些场景下能提供更高的操作效率，例如需要频繁循环访问元素的场景。

基本概念

循环链表分为两种主要类型：

• 单向循环链表：每个节点包含数据和指向下一个节点的指针，尾节点指向头节点。
• 双向循环链表：每个节点包含指向前驱节点和后继节点的指针，头节点的前驱指向尾节点，尾节点的后继指向头节点。

循环链表的主要优势包括：

• 可以从任意节点开始遍历整个链表。
• 某些操作（如尾部插入）的时间复杂度从O(n)降低到O(1)。

与普通链表的区别

普通链表的尾节点指向NULL，而循环链表的尾节点指向头节点。这使得循环链表在实现环形缓冲区、轮询调度等场景中更具优势。

数据结构定义

以下是C语言中单向循环链表的节点定义：

typedef struct Node {
    int data;           // 数据域
    struct Node* next;  // 指针域
} Node;

基本操作

创建循环链表

Node* createCircularLinkedList(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = newNode;  // 指向自身形成循环
    return newNode;
}

插入节点

在头部插入新节点的示例：

void insertAtHead(Node** head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    
    if (*head == NULL) {
        newNode->next = newNode;
        *head = newNode;
    } else {
        Node* temp = *head;
        while (temp->next != *head) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->next = *head;
        *head = newNode;
    }
}

删除节点

删除特定值节点的示例：

void deleteNode(Node** head, int key) {
    if (*head == NULL) return;
    
    Node *current = *head, *prev = NULL;
    
    // 查找要删除的节点
    while (current->data != key) {
        if (current->next == *head) {
            printf("Key not found\n");
            return;
        }
        prev = current;
        current = current->next;
    }
    
    // 如果是唯一节点
    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 if (current->next == *head) {
        prev->next = *head;
        free(current);
    }
    // 中间节点
    else {
        prev->next = current->next;
        free(current);
    }
}

遍历链表

遍历并打印所有节点的示例：

void printList(Node* head) {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }
    
    Node* temp = head;
    do {
        printf("%d ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("\n");
}

可视化表示

以下是一个包含三个节点的单向循环链表的mermaid图示：

graph LR A[节点1] --> B[节点2] B --> C[节点3] C --> A

实际应用案例

约瑟夫问题

循环链表非常适合解决约瑟夫问题（Josephus Problem），即n个人围成一圈，从某个指定的人开始报数，数到k的那个人就被淘汰，接着下一个人重新从1开始报数，直到所有人都被淘汰。

解决方案示例：

int josephus(int n, int k) {
    // 创建循环链表
    Node* head = createCircularLinkedList(1);
    Node* prev = head;
    for (int i = 2; i <= n; i++) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = i;
        prev->next = newNode;
        newNode->next = head;
        prev = newNode;
    }
    
    Node *ptr1 = head, *ptr2 = head;
    while (ptr1->next != ptr1) {
        // 找到第k个节点
        for (int count = 1; count < k; count++) {
            ptr2 = ptr1;
            ptr1 = ptr1->next;
        }
        // 删除第k个节点
        ptr2->next = ptr1->next;
        free(ptr1);
        ptr1 = ptr2->next;
    }
    
    int result = ptr1->data;
    free(ptr1);
    return result;
}

轮询调度

操作系统中的轮询调度算法可以使用循环链表来实现，每个进程代表一个节点，CPU按顺序访问每个节点，实现公平调度。

性能分析

循环链表各种操作的时间复杂度：

操作	时间复杂度
插入(头/尾)	O(1) - 如果有尾指针 O(n) - 需要遍历找到尾节点
删除	O(n) - 最坏情况
查找	O(n)
访问	O(n)

常见错误与调试

1. 无限循环：忘记检查循环终止条件，导致遍历时陷入无限循环。解决方法：使用do-while循环确保至少执行一次，同时正确设置终止条件。

2. 内存泄漏：删除节点时忘记释放内存。解决方法：确保每次删除操作都伴随free()调用。

3. 头指针处理不当：在删除唯一节点或头节点时未正确更新头指针。解决方法：仔细处理边界条件。

进阶主题

双向循环链表

双向循环链表在每个节点中增加一个指向前驱节点的指针，提供双向遍历能力。

节点定义：

typedef struct DNode {
    int data;
    struct DNode* prev;
    struct DNode* next;
} DNode;

优化技巧

• 维护一个尾指针可以显著提高在尾部插入的效率。
• 使用哨兵节点（dummy node）可以简化某些边界条件的处理。

练习题

1. 实现一个函数，检测给定的链表是否是循环链表。 2. 编写代码将两个循环链表连接成一个循环链表。 3. 实现双向循环链表的基本操作（插入、删除、遍历）。

总结

循环链表是一种强大的数据结构，特别适合需要环形访问的场景。虽然它的实现比普通链表稍复杂，但在特定应用中能提供显著的性能优势。理解循环链表的工作原理有助于解决许多经典的计算机科学问题，并为学习更复杂的数据结构打下基础。