單向循環鏈表

一，循環鏈表的概念

1.什麼是循環鏈表

　　所謂的循環鏈表就是讓單向鏈表的首尾相連，組成一個環狀。

2.循環鏈表的典型應用

　　約瑟夫環問題。

3.實現循環鏈表的重點

　　1，循環鏈表在插入第一個元素的時候，需要我們將第一元素的指針域指向其自身，也就構成了循環鏈表。

　　2，循環鏈表基於單向鏈表而生，單是比循環鏈表多了游標這個概念。要想實現循環鏈表的插入，刪除的關鍵是考慮頭結點問題，因為在頭插法方式（往鏈表的頭部插入數據）中，需要將末尾數據元素的指針域指向新插入的節點。將新插入的節點的指針域指向頭結點的指針域的指針域，還需要將頭結點指向新插入的結點。（插入相同）。

二，循環鏈表新增概念和功能

1，什麼是游標

　　所謂的游標就是在鏈表中可以移動的指針，游標初始化一般是指向鏈表的第一個結點。

2，游標的功能

• 初始化游標
• 移動游標：將移動前的游標所對應得結點返回，並將游標指向下一個數據元素。
• 獲取游標：獲取當前游標所對應得數據元素
• 刪除游標：刪除當前游標所對應得數據元素，並將游標指向下一個數據元素。

三，循環鏈表的實現

1，循環鏈表的功能

# ifndef CIRCLE_LINK_LIST
# define CIRCLE_LINK_LIST

/* 業務節點 */
typedef void Node;

/* 鏈表節點(被包含) */
typedef struct CircleNode
{
    struct CircleNode * next;
}CircleNode;

/* 鏈表 */
typedef struct CircleLinkList
{
    /* 頭指針 */
    Node * ptr;
    /* 頭結點 */
    CircleNode header;
    /* 游標 */
    CircleNode slider;
    /* 長度 */
    int length;
}CircleLinkList;

/* 創建循環鏈表 */
CircleLinkList * createList();

/* 獲取鏈表長度 */
int length(CircleLinkList * list);

/* 銷毀鏈表 */
void destory(CircleLinkList * list);

/* 清空鏈表 */
void clear(CircleLinkList * list);

/* 判斷鏈表是否為空 */
int empty(CircleLinkList * list);

/* 插入結點 */
void insert(CircleLinkList * list,int pos, Node * node);

/* 刪除結點 */
Node * del(CircleLinkList * list, int pos);

/* 獲取結點 */
Node * get(CircleLinkList * list, int pos);

/* 將游標重置指向鏈表的第一個元素 */
void resetSlider(CircleLinkList * list);

/* 獲取當前游標指向的數據元素 */
Node * current(CircleLinkList * list);

/* 將游標指向到鏈表的下一個數據元素並返回當前游標的數據元素 */
Node * next(CircleLinkList * list);

/* 刪除游標，並將游標指向下一個數據元素 */
Node * deleteNode(CircleLinkList * list);

# endif 

2，循環鏈表的實現

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

/* 創建循環鏈表 */
CircleLinkList * createList()
{
    /* 在堆上分配內存 */
    CircleLinkList * list = (CircleLinkList *)malloc(sizeof(CircleLinkList));
    /* 初始化 */
    list->ptr = &list->header;
    list->header.next = NULL;
    list->slider.next = NULL;
    list->length = 0;
    return list;
}

/* 獲取鏈表長度 */
int length(CircleLinkList * list)
{
    return list->length;
}

/* 銷毀鏈表 */
void destory(CircleLinkList * list)
{
    if (list != NULL)
    {
        free(list);
    }
}

/* 清空鏈表 */
void clear(CircleLinkList * list)
{
    if (list != NULL)
    {
        list->header.next = NULL;
        list->slider.next = NULL;
    }
}

/* 判斷鏈表是否為空 */
int empty(CircleLinkList * list)
{
    if (list->length == 0)
    {
        return 1;
    }
    else {
        return 0;
    }
}

/* 插入結點 */
void insert(CircleLinkList * list, int pos, Node * node)
{
    if (list == NULL)
    {
        printf("鏈表為NULL\n");
        return;
    }
    /* 判斷插入位置是否超過鏈表長度或小於0 */
    pos = pos < 0 ? 0 : pos;
    pos = pos > length(list) ? length(list) : pos;
    /* 注意：如果在第一個位置插入，則需要遍歷到最後一個元素，然後再把最後一個元素的指針域指向第一個 */
    /* 將業務節點轉換為鏈表節點 */
    CircleNode * _node = (CircleNode *)node;
    /* 判斷是否第一次插入 */
    if (length(list) == 0)
    {
        list->header.next = _node;
        _node->next = _node;
        list->length++;
        return;
    }
    /* 定義posNode結點 */
    CircleNode * posNode = list->header.next;
    /* 判斷是否在頭部插入 */
    if (pos == 0)
    {
        /* 將posNode移動到尾部 */
        for (int i = 0; i < length(list)-1; i++)
        {
            posNode = posNode->next;
        }
        /* 將尾部指針指向新節點 */
        posNode->next = _node;
        /* 將新節點指針指向頭節點指向的節點 */
        _node->next = list->header.next;
        /* 將頭節點指向新節點 */
        list->header.next = _node;
    }
    else {
        /* 將posNode移動到pos位置上 */
        for (int i = 0; i < pos-1; i++)
        {
            posNode = posNode->next;
        }
        /* 插入 */
        _node->next = posNode->next;
        posNode->next = _node;
    }
    list->length++;
}

/* 刪除結點 */
Node * del(CircleLinkList * list, int pos)
{
    if (list == NULL)
    {
        printf("鏈表為NULL\n");
        return NULL;
    }
    if (length(list) <= 0)
    {
        printf("鏈表已空\n");
        return NULL;
    }
    /* 判斷插入位置是否超過鏈表長度或小於0 */
    pos = pos < 0 ? 0 : pos;
    pos = pos > length(list) ? length(list) : pos;
    /* 定義要刪除的節點 */
    CircleNode * result = NULL;
    /* 定義posNode結點 */
    CircleNode * posNode = list->header.next;
    /* 判斷是否刪除頭結點 */
    if (pos == 0)
    {
        /* 移動posNode到pos位置 */
        for (int i = 0; i < length(list) - 1; i++)
        {
            posNode = posNode->next;
        }
        /* 保存要刪除的節點 */
        result = posNode->next;
        /* 刪除 */
        posNode->next = list->header.next->next;
        list->header.next = list->header.next->next;
    }
    else {
        /* 定義緩存上一個結點 */
        CircleNode * previous = posNode;
        /* 移動posNode到pos位置 */
        for (int i = 0; i < pos; i++)
        {
            previous = posNode;
            posNode = posNode->next;
        }
        /* 保存要刪除的節點 */
        result = posNode;
        /* 刪除 */
        previous->next = posNode->next;
    }
    list->length--;
    return result;
}

/* 獲取結點 */
Node * get(CircleLinkList * list, int pos)
{
    if (list == NULL)
    {
        printf("鏈表為NULL\n");
        return NULL;
    }
    /* 判斷插入位置是否超過鏈表長度或小於0 */
    pos = pos < 0 ? 0 : pos;
    pos = pos > length(list) ? pos%length(list) : pos;
    /* 定義頭結點 */
    CircleNode * header = list->header.next;
    /* 定義pos結點 */
    CircleNode * posNode = header;
    /* 移動posNode到指定位置 */
    for (int i = 0; i < pos; i++)
    {
        posNode = posNode->next;
    }
    return posNode;
}

/* 將游標重置指向鏈表的第一個元素 */
void resetSlider(CircleLinkList * list)
{
    list->slider.next = list->header.next;
}

/* 獲取當前游標指向的數據元素 */
Node * current(CircleLinkList * list)
{
    return list->slider.next;
}

/* 將游標指向到鏈表的下一個數據元素並返回當前游標的數據元素 */
Node * next(CircleLinkList * list)
{
    CircleNode * result = list->slider.next;
    list->slider.next = list->slider.next->next;
    return result;
}

/* 刪除游標，並將游標指向下一個數據元素 */
Node * deleteNode(CircleLinkList * list)
{
    if (list == NULL)
    {
        printf("鏈表為NULL\n");
        return NULL;
    }
    if (length(list) <= 0)
    {
        printf("鏈表已空\n");
        return NULL;
    }
    /* 獲取當前游標的數據結點 */
    Node * node = current(list);
    /* 將當前游標下移 */
    next(list);
    /* 定義要刪除的節點 */
    CircleNode * result = NULL;
    /* 定義posNode結點 */
    CircleNode * posNode = list->header.next;
    /* 將業務節點轉換為鏈表節點 */
    CircleNode * _node = (CircleNode *)node;
    /* 判斷是否刪除頭結點 */
    if (_node == list->header.next)
    {
        /* 移動posNode到pos位置 */
        for (int i = 0; i < length(list) - 1; i++)
        {
            posNode = posNode->next;
        }
        /* 保存要刪除的節點 */
        result = posNode->next;
        /* 刪除 */
        posNode->next = list->header.next->next;
        list->header.next = list->header.next->next;
    }
    else {
        /* 定義緩存上一個結點 */
        CircleNode * previous = posNode;
        /* 移動posNode到pos位置 */
        while (posNode != _node)
        {
            previous = posNode;
            posNode = posNode->next;
        }
        /* 保存要刪除的節點 */
        result = posNode;
        /* 刪除 */
        previous->next = posNode->next;
    }
    list->length--;
    return result;
} 

3，循環鏈表的測試

# include<stdio.h>
# include"CircleLinkList.h"

typedef struct Student
{
    CircleNode next;
    char name[64];
    int age;
}Student;

int main()
{
    Student s1 = { NULL,"劉備",56 };
    Student s2 = { NULL,"關羽",40 };
    Student s3 = { NULL,"張飛",36 };
    Student s4 = { NULL,"趙雲",34 };
    Student s5 = { NULL,"馬超",20 };
    Student s6 = { NULL,"黃忠",80 };

    CircleLinkList * list = createList();
    insert(list, length(list), &s1);
    insert(list, length(list), &s2);
    insert(list, length(list), &s3);
    insert(list, length(list), &s4);
    insert(list, length(list), &s5);
    insert(list, length(list), &s6);

    printf("##############遍歷################\n");
    for (int i = 0; i < length(list); i++)
    {
        Student * student = (Student *)get(list, i);
        printf("name = %s,age = %d\n", student->name, student->age);
    }

    //printf("##############刪除################\n");
    //for (int i = 0; i < 6; i++)
    //{
    //    Student * student = (Student *)del(list, length(list)-1);
    //    printf("name = %s,age = %d\n", student->name, student->age);
    //}

    resetSlider(list);
    printf("##############游標遍歷################\n");
    for (int i = 0; i < length(list); i++)
    {
        Student * student = next(list);
        printf("name = %s,age = %d\n", student->name, student->age);
    }

} 

三，約瑟夫環問題

/*
*    約瑟夫環運作如下：
*    1、一群人圍在一起坐成環狀（如：N）
*    2、從某個編號開始報數（如：K）
*    3、數到某個數（如：M）的時候，此人出列，下一個人重新報數
*    4、一直循環，直到所有人出列，約瑟夫環結束
*/
# include<stdio.h>
# include"CircleLinkList.h"

typedef struct value 
{
    CircleNode next;
    int value;
}value;

int main()
{
    /* 創建循環鏈表 */
    CircleLinkList * list = createList();
    
    /* 從0到9十個學生圍成環狀 */
    value v0 = { NULL,0 };
    value v1 = { NULL,1 };
    value v2 = { NULL,2 };
    value v3 = { NULL,3 };
    value v4 = { NULL,4 };
    value v5 = { NULL,5 };
    value v6 = { NULL,6 };
    value v7 = { NULL,7 };
    value v8 = { NULL,8 };
    value v9 = { NULL,9 };

    /* 尾插法 */
    insert(list, length(list), &v0);
    insert(list, length(list), &v1);
    insert(list, length(list), &v2);
    insert(list, length(list), &v3);
    insert(list, length(list), &v4);
    insert(list, length(list), &v5);
    insert(list, length(list), &v6);
    insert(list, length(list), &v7);
    insert(list, length(list), &v8);
    insert(list, length(list), &v9);

    /* 重置游標 */
    resetSlider(list);

    /* 將游標移動到2位置，從第三個人開始報數 */
    for (int i = 0; i < 2; i++)
    {
        next(list);
    }

    /* 將數到4的人刪除 */
    while (empty(list) == 0)
    {
        /* 循環4次 */
        for (int i = 0; i < 3; i++)
        {
            next(list);
        }
        /* 刪除當前游標 */
        value * t = (value *)deleteNode(list);
        printf("result = %d\n", t->value);
    }
    return 0;
}