循環鏈表進階：游標遍歷、約瑟夫問題與C語言完整實現

在單鏈表基礎上將尾節點指向頭節點，即構成循環鏈表。它保留單鏈表所有操作，並引入游標機制，支持高效的循環遍歷與當前節點定位，是解決約瑟夫問題等環狀結構問題的理想數據結構。

核心概念與操作

基本操作

• 創建/銷毀/清空鏈表
• 獲取長度、按位置查找/插入/刪除

游標擴展操作

• CircleList_Current：獲取游標指向的數據元素
• CircleList_Reset：游標重置至首元素
• CircleList_Next：游標移至下一元素
• CircleList_DeleteNode：直接刪除指定節點

插入與刪除邊界情況分析

插入操作需處理四種情況：首次插入、頭插、尾插、中間插入。關鍵在於維護環狀結構與游標一致性：

經典應用：約瑟夫問題

N 人圍圈，從 1 開始報數，報到 M 的人出列，剩餘者繼續，求出列順序。循環鏈表天然契合此場景：

C 語言完整實現（含測試主程序）

頭文件 CircleList.h

typedef struct _tag_CircleListNode {
    struct _tag_CircleListNode *next;
} CircleListNode;

typedef void CircleList;

CircleList* CircleList_Create();
void CircleList_Destroy(CircleList* list);
int CircleList_Insert(CircleList* list, CircleListNode* node, int pos);
CircleListNode* CircleList_Get(CircleList* list, int pos);
CircleListNode* CircleList_Delete(CircleList* list, int pos);
CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node);
CircleListNode* CircleList_Reset(CircleList* list);
CircleListNode* CircleList_Current(CircleList* list);
CircleListNode* CircleList_Next(CircleList* list);

核心源文件 CircleList.c（節選關鍵函數）

// 插入：處理首次插入、頭插、尾插、中間插入
int CircleList_Insert(CircleList* list, CircleListNode* node, int pos) {
    TCircleList* sList = (TCircleList*)list;
    CircleListNode* current = (CircleListNode*)sList;
    for (int i = 0; i < pos && current->next; i++) current = current->next;
    node->next = current->next;
    current->next = node;
    if (sList->length == 0) sList->slider = node; // 首次插入設游標
    if (current == (CircleListNode*)sList) {      // 頭插需更新尾節點指向
        CircleListNode* last = CircleList_Get(sList, sList->length - 1);
        last->next = current->next;
    }
    sList->length++;
    return 0;
}

// 刪除：懶惰刪除+游標保護
CircleListNode* CircleList_Delete(CircleList* list, int pos) {
    TCircleList* sList = (TCircleList*)list;
    CircleListNode* current = (CircleListNode*)sList;
    for (int i = 0; i < pos; i++) current = current->next;
    CircleListNode* ret = current->next;
    current->next = ret->next;
    if (sList->slider == ret) sList->slider = ret->next; // 保護游標
    sList->length--;
    return ret;
}

測試主程序

int main() {
    CircleList* list = CircleList_Create();
    struct Value { CircleListNode header; int v; } v1={0,1}, v2={0,2}, v3={0,3}, v4={0,4}, v5={0,5}, v6={0,6}, v7={0,7}, v8={0,8};
    // 尾插 1-4，位置5插5，刪除首元素，遍歷驗證
    CircleList_Insert(list, (CircleListNode*)&v1, CircleList_Length(list));
    CircleList_Insert(list, (CircleListNode*)&v2, CircleList_Length(list));
    CircleList_Insert(list, (CircleListNode*)&v3, CircleList_Length(list));
    CircleList_Insert(list, (CircleListNode*)&v4, CircleList_Length(list));
    CircleList_Insert(list, (CircleListNode*)&v5, 5);
    CircleList_Delete(list, 0);
    // 游標遍歷模擬約瑟夫：每次移動2步刪除當前
    CircleList_Reset(list);
    while (CircleList_Length(list) > 0) {
        for (int i = 1; i < 3; i++) CircleList_Next(list);
        struct Value* pv = (struct Value*)CircleList_Current(list);
        printf("%d\n", pv->v);
        CircleList_DeleteNode(list, (CircleListNode*)pv);
    }
    CircleList_Destroy(list);
    return 0;
}

優缺點總結