编辑“︁C 语言循环链表”︁

{{DISPLAYTITLE:C语言循环链表}}

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

== 基本概念 ==

循环链表分为两种主要类型：
* '''单向循环链表'''：每个节点包含数据和指向下一个节点的指针，尾节点指向头节点。
* '''双向循环链表'''：每个节点包含指向前驱节点和后继节点的指针，头节点的前驱指向尾节点，尾节点的后继指向头节点。

循环链表的主要优势包括：
* 可以从任意节点开始遍历整个链表。
* 某些操作（如尾部插入）的时间复杂度从O(n)降低到O(1)。

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

== 数据结构定义 ==

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

<syntaxhighlight lang="c">
typedef struct Node {
    int data;           // 数据域
    struct Node* next;  // 指针域
} Node;
</syntaxhighlight>

== 基本操作 ==

=== 创建循环链表 ===

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

=== 插入节点 ===

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

<syntaxhighlight lang="c">
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;
    }
}
</syntaxhighlight>

=== 删除节点 ===

删除特定值节点的示例：

<syntaxhighlight lang="c">
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);
    }
}
</syntaxhighlight>

=== 遍历链表 ===

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

<syntaxhighlight lang="c">
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");
}
</syntaxhighlight>

== 可视化表示 ==

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

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

== 实际应用案例 ==

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

解决方案示例：

<syntaxhighlight lang="c">
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;
}
</syntaxhighlight>

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

== 性能分析 ==

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

{| class="wikitable"
|-
! 操作 !! 时间复杂度
|-
| 插入(头/尾) || O(1) - 如果有尾指针<br>O(n) - 需要遍历找到尾节点
|-
| 删除 || O(n) - 最坏情况
|-
| 查找 || O(n)
|-
| 访问 || O(n)
|}

== 常见错误与调试 ==

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

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

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

== 进阶主题 ==

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

节点定义：
<syntaxhighlight lang="c">
typedef struct DNode {
    int data;
    struct DNode* prev;
    struct DNode* next;
} DNode;
</syntaxhighlight>

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

== 练习题 ==

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

== 总结 ==

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

[[Category:编程语言]]
[[Category:C]]
[[Category:C 语言高级数据结构]]