今天我们来学习C语言中一个有趣的数据结构——循环链表。如果你已经了解了单向链表，那么循环链表对你来说会很容易理解！

想象一下游乐场的旋转木马：每匹马都连接着前面的马，最后一匹马又连接着第一匹马，形成一个循环。循环链表就是这样的数据结构！

为什么要学习循环链表？

  • 它解决了单向链表不能循环访问的问题

  • 在许多实际应用中有独特优势（如游戏开发、轮询调度）

  • 帮助你更深入理解链表和指针的概念

第一部分：循环链表的基本结构

循环链表分为两种：单向循环链表和双向循环链表。我们先从简单的单向循环链表开始：

c

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

// 定义循环链表节点
struct Node {
    int data;           // 存储数据
    struct Node* next;  // 指向下一个节点的指针
};

新手注意事项：

  1. 循环链表和普通链表的节点结构是一样的

  2. 区别在于循环链表的最后一个节点指向第一个节点，形成环状

  3. 循环链表没有真正的"尾节点"，因为它是循环的

第二部分：创建循环链表

让我们一步步创建循环链表：

c

// 创建新节点
struct Node* createNode(int data) {
    // 申请内存空间
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    
    // 检查内存是否申请成功
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(1); // 退出程序
    }
    
    // 初始化节点
    newNode->data = data;
    newNode->next = NULL;
    
    return newNode;
}

// 创建循环链表并添加节点
void createCircularList(struct Node** head, int values[], int n) {
    if (n == 0) {
        *head = NULL;
        return;
    }
    
    // 创建第一个节点
    *head = createNode(values[0]);
    struct Node* current = *head;
    
    // 添加剩余节点
    for (int i = 1; i < n; i++) {
        current->next = createNode(values[i]);
        current = current->next;
    }
    
    // 将最后一个节点指向头节点，形成循环
    current->next = *head;
}

第三部分：循环链表的基本操作

1. 遍历循环链表

c

// 打印循环链表
void printCircularList(struct Node* head) {
    if (head == NULL) {
        printf("链表为空！\n");
        return;
    }
    
    struct Node* current = head;
    
    printf("循环链表: ");
    do {
        printf("%d ", current->data);
        current = current->next;
    } while (current != head); // 当再次遇到头节点时停止
    
    printf("\n");
}

2. 在循环链表中插入节点

c

// 在循环链表的指定位置插入节点
void insertNode(struct Node** head, int position, int data) {
    struct Node* newNode = createNode(data);
    
    // 如果链表为空
    if (*head == NULL) {
        *head = newNode;
        newNode->next = newNode; // 指向自己形成循环
        return;
    }
    
    struct Node* current = *head;
    
    // 如果要在头部插入
    if (position == 0) {
        // 找到尾节点
        while (current->next != *head) {
            current = current->next;
        }
        
        // 插入新节点
        newNode->next = *head;
        current->next = newNode;
        *head = newNode;
        return;
    }
    
    // 找到要插入位置的前一个节点
    for (int i = 0; i < position - 1; i++) {
        current = current->next;
        
        // 如果已经循环一圈，说明位置超出范围
        if (current == *head) {
            printf("位置超出范围！\n");
            free(newNode);
            return;
        }
    }
    
    // 插入新节点
    newNode->next = current->next;
    current->next = newNode;
}

3. 从循环链表中删除节点

c

// 从循环链表中删除指定位置的节点
void deleteNode(struct Node** head, int position) {
    if (*head == NULL) {
        printf("链表为空！\n");
        return;
    }
    
    struct Node* current = *head;
    struct Node* prev = NULL;
    
    // 如果要删除头节点
    if (position == 0) {
        // 如果只有一个节点
        if (current->next == *head) {
            free(current);
            *head = NULL;
            return;
        }
        
        // 找到尾节点
        while (current->next != *head) {
            current = current->next;
        }
        
        // 删除头节点
        current->next = (*head)->next;
        free(*head);
        *head = current->next;
        return;
    }
    
    // 找到要删除的节点和前一个节点
    for (int i = 0; i < position; i++) {
        prev = current;
        current = current->next;
        
        // 如果已经循环一圈，说明位置超出范围
        if (current == *head) {
            printf("位置超出范围！\n");
            return;
        }
    }
    
    // 删除节点
    prev->next = current->next;
    free(current);
}

第四部分：完整的示例程序

让我们写一个完整的程序来测试循环链表：

c

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

// 节点定义
struct Node {
    int data;
    struct Node* next;
};

// 函数声明
struct Node* createNode(int data);
void createCircularList(struct Node** head, int values[], int n);
void printCircularList(struct Node* head);
void insertNode(struct Node** head, int position, int data);
void deleteNode(struct Node** head, int position);
void freeCircularList(struct Node* head);

int main() {
    struct Node* head = NULL;
    int values[] = {10, 20, 30, 40, 50};
    int n = sizeof(values) / sizeof(values[0]);
    
    printf("创建循环链表...\n");
    createCircularList(&head, values, n);
    printCircularList(head);
    
    printf("\n在位置2插入值25...\n");
    insertNode(&head, 2, 25);
    printCircularList(head);
    
    printf("\n在头部插入值5...\n");
    insertNode(&head, 0, 5);
    printCircularList(head);
    
    printf("\n删除位置3的节点...\n");
    deleteNode(&head, 3);
    printCircularList(head);
    
    printf("\n删除头节点...\n");
    deleteNode(&head, 0);
    printCircularList(head);
    
    // 释放内存
    freeCircularList(head);
    
    return 0;
}

// 创建新节点
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    
    newNode->data = data;
    newNode->next = NULL;
    
    return newNode;
}

// 创建循环链表
void createCircularList(struct Node** head, int values[], int n) {
    if (n == 0) {
        *head = NULL;
        return;
    }
    
    *head = createNode(values[0]);
    struct Node* current = *head;
    
    for (int i = 1; i < n; i++) {
        current->next = createNode(values[i]);
        current = current->next;
    }
    
    current->next = *head;
}

// 打印循环链表
void printCircularList(struct Node* head) {
    if (head == NULL) {
        printf("链表为空！\n");
        return;
    }
    
    struct Node* current = head;
    
    printf("循环链表: ");
    do {
        printf("%d ", current->data);
        current = current->next;
    } while (current != head);
    
    printf("\n");
}

// 插入节点
void insertNode(struct Node** head, int position, int data) {
    struct Node* newNode = createNode(data);
    
    if (*head == NULL) {
        *head = newNode;
        newNode->next = newNode;
        return;
    }
    
    struct Node* current = *head;
    
    if (position == 0) {
        while (current->next != *head) {
            current = current->next;
        }
        
        newNode->next = *head;
        current->next = newNode;
        *head = newNode;
        return;
    }
    
    for (int i = 0; i < position - 1; i++) {
        current = current->next;
        
        if (current == *head) {
            printf("位置超出范围！\n");
            free(newNode);
            return;
        }
    }
    
    newNode->next = current->next;
    current->next = newNode;
}

// 删除节点
void deleteNode(struct Node** head, int position) {
    if (*head == NULL) {
        printf("链表为空！\n");
        return;
    }
    
    struct Node* current = *head;
    struct Node* prev = NULL;
    
    if (position == 0) {
        if (current->next == *head) {
            free(current);
            *head = NULL;
            return;
        }
        
        while (current->next != *head) {
            current = current->next;
        }
        
        current->next = (*head)->next;
        free(*head);
        *head = current->next;
        return;
    }
    
    for (int i = 0; i < position; i++) {
        prev = current;
        current = current->next;
        
        if (current == *head) {
            printf("位置超出范围！\n");
            return;
        }
    }
    
    prev->next = current->next;
    free(current);
}

// 释放循环链表内存
void freeCircularList(struct Node* head) {
    if (head == NULL) {
        return;
    }
    
    struct Node* current = head;
    struct Node* next;
    
    // 先断开循环，变成普通链表
    while (current->next != head) {
        next = current->next;
        free(current);
        current = next;
    }
    
    // 释放最后一个节点
    free(current);
    
    printf("内存已释放！\n");
}

运行结果：

text

创建循环链表...
循环链表: 10 20 30 40 50 

在位置2插入值25...
循环链表: 10 20 25 30 40 50 

在头部插入值5...
循环链表: 5 10 20 25 30 40 50 

删除位置3的节点...
循环链表: 5 10 20 30 40 50 

删除头节点...
循环链表: 10 20 30 40 50 
内存已释放！


第五部分：循环链表的应用场景


1. 约瑟夫问题（Josephus Problem）


这是一个经典的问题：N个人围成一圈，从第一个人开始报数，报到M的人出列，然后从下一个人重新开始报数，直到所有人出列。


c


// 解决约瑟夫问题
void josephusProblem(int n, int m) {
    // 创建循环链表，编号从1到n
    struct Node* head = NULL;
    for (int i = n; i >= 1; i--) {
        struct Node* newNode = createNode(i);
        if (head == NULL) {
            head = newNode;
            newNode->next = newNode;
        } else {
            newNode->next = head->next;
            head->next = newNode;
        }
    }
    
    struct Node* current = head;
    struct Node* prev = NULL;
    
    printf("约瑟夫问题(n=%d, m=%d)的出列顺序: ", n, m);
    
    while (current->next != current) { // 直到只剩一个节点
        // 数m-1个人
        for (int i = 0; i < m - 1; i++) {
            prev = current;
            current = current->next;
        }
        
        // 删除当前节点（报数到m的人）
        prev->next = current->next;
        printf("%d ", current->data);
        free(current);
        current = prev->next;
    }
    
    printf("%d\n", current->data);
    free(current);
}


2. 轮询调度（Round Robin Scheduling）


在操作系统中，循环链表可以用于实现轮询调度算法，让每个进程都有平等的机会使用CPU。


c


// 简单的轮询调度模拟
void roundRobinScheduling(int processes[], int n, int timeQuantum) {
    // 创建进程队列（循环链表）
    struct Node* head = NULL;
    for (int i = n - 1; i >= 0; i--) {
        struct Node* newNode = createNode(processes[i]);
        if (head == NULL) {
            head = newNode;
            newNode->next = newNode;
        } else {
            newNode->next = head->next;
            head->next = newNode;
        }
    }
    
    printf("轮询调度(时间片=%d):\n", timeQuantum);
    
    struct Node* current = head;
    while (current != NULL) {
        printf("进程%d运行%d时间片\n", current->data, timeQuantum);
        
        // 模拟进程执行
        // ...
        
        // 移动到下一个进程
        current = current->next;
        
        // 如果回到起点，说明所有进程都执行了一轮
        if (current == head) {
            printf("--- 一轮结束 ---\n");
            
            // 这里可以添加终止条件，比如所有进程都完成
            break;
        }
    }
    
    // 释放内存
    freeCircularList(head);
}


第六部分：常见错误和解决方法


错误1：无限循环


c


// 错误：遍历循环链表时使用错误的终止条件
void printListWrong(struct Node* head) {
    struct Node* current = head;
    
    while (current != NULL) { // 错误！循环链表没有NULL结尾
        printf("%d ", current->data);
        current = current->next;
    }
    // 这将导致无限循环！
}

// 正确：使用do-while循环
void printListCorrect(struct Node* head) {
    if (head == NULL) return;
    
    struct Node* current = head;
    
    do {
        printf("%d ", current->data);
        current = current->next;
    } while (current != head); // 当再次遇到头节点时停止
}


错误2：内存泄漏


c


// 错误：没有正确释放循环链表
void freeListWrong(struct Node* head) {
    struct Node* current = head;
    
    while (current != NULL) { // 错误！循环链表没有NULL结尾
        struct Node* next = current->next;
        free(current);
        current = next;
    }
    // 这将导致无限循环和内存泄漏！
}

// 正确：先断开循环再释放
void freeListCorrect(struct Node* head) {
    if (head == NULL) return;
    
    // 先找到尾节点并断开循环
    struct Node* current = head;
    while (current->next != head) {
        current = current->next;
    }
    current->next = NULL;
    
    // 然后像普通链表一样释放
    current = head;
    while (current != NULL) {
        struct Node* next = current->next;
        free(current);
        current = next;
    }
}


总结


恭喜你！现在你已经了解了循环链表的基本概念和操作。记住：


    
 
  1. 
  
    循环链表的最后一个节点指向第一个节点，形成环状结构
    2. 
 
  2. 
  
    遍历循环链表时需要特别注意终止条件，避免无限循环
    3. 
 
  3. 
  
    循环链表在处理周期性任务时非常有用
    4. 
 
  4. 
  
    一定要注意指针操作和内存管理，避免内存泄漏
    5. 



学习数据结构就像搭积木，掌握了基础结构后，你就能构建更复杂的程序。循环链表是你编程工具箱中的一个重要工具，多多练习，你会越来越熟练！


如果有任何问题，欢迎在评论区留言，我会尽力解答！
 
  

        # c语言
      
        # 链表
      
        # 数据结构
      
  
 
 Logo 
AI编程社区
 
汇聚全球AI编程工具，助力开发者即刻编程。
 
 
  
更多推荐
  
 
AI编程工具大比拼：谁是最强代码助手？
 
AI代码辅助工具对比分析 主流AI编程助手包括GitHub Copilot、Amazon CodeWhisperer、Tabnine等，各具特色。Copilot集成多语言支持但存在安全风险，CodeWhisperer深度适配AWS生态，Tabnine注重隐私保护。其他工具如Replit适合快速原型开发，DeepCode专注代码安全检测，ChatGPT支持自然语言交互，Cody擅长大型代码库维护，C
 
avatar AI编程社区
 
cover
 
「AI原生编程挑战赛」：用代码重构开发范式，让小型系统“一键生长”
 
 
avatar AI编程社区
 
cover
 
HttpClient入门与实战案例详解
 
 
avatar AI编程社区