C语言实现循环链表

实现循环链表，我们需要定义一个结构体来表示链表中的每个节点，其中包含一个指向下一个结点的指针。

下面是一个示例结构体的定义：

struct Node {
    int data;
    struct Node* next;
};

其中，data表示节点存储的数据，next是指向下一个节点的指针。

我们需要定义以下操作来构建循环链表：

1. 创建一个空链表

struct Node* createList() {
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->next = head;
    return head;
}

其中，我们建立了一个空链表，头节点的next指针指向它自身。

1. 在链表的末尾插入一个元素

void insert(struct Node* head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = head;

    struct Node* p = head;
    while (p->next != head) {
        p = p->next;
    }

    p->next = newNode;
}

通过这种方式，我们可以将一个元素添加到链表的末尾。

1. 从链表中删除元素

void delete(struct Node* head, int data) {
    struct Node* p = head;
    while (p->next != head) {
        if (p->next->data == data) {
            struct Node* temp = p->next;
            p->next = temp->next;
            free(temp);
            return;
        }
        p = p->next;
    }
}

从链表中删除一个元素，需要遍历链表查找该元素，找到后删除节点。

下面是一个简单的例子，展示如何使用循环链表来实现Josephus问题。该问题的描述如下：

• N个人围成一个圆圈，依次编号为1, 2, … ,N
• 从第一个人开始依次报数，报到M的人出圈，下一个人继续从1开始报数，直到只剩下一个人为止

假设N=5，M=2，下面是解决方案：

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

struct Node {
    int data;
    struct Node* next;
};

struct Node* createList() {
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->next = head;
    return head;
}

void insert(struct Node* head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = head;

    struct Node* p = head;
    while (p->next != head) {
        p = p->next;
    }

    p->next = newNode;
}

void delete(struct Node* head, int data) {
    struct Node* p = head;
    while (p->next != head) {
        if (p->next->data == data) {
            struct Node* temp = p->next;
            p->next = temp->next;

            free(temp);
            return;
        }
        p = p->next;
    }
}

void josephus(int n, int m) {
    struct Node* head = createList();

    for (int i = 1; i <= n; i++) {
        insert(head, i);
    }

    struct Node* p = head->next;
    while (p->next != p) {
        for (int i = 0; i < m - 1; i++) {
            p = p->next;
        }
        delete(head, p->data);
        p = p->next;
    }
    printf("The last one is %d.\n", p->data);

    free(p);
    free(head);
}

int main() {
    int n = 5, m = 2;
    josephus(n, m);

    return 0;
}

上面的代码首先创建了一个包含元素1到元素N的循环链表。然后通过遍历链表的方式进行Josephus问题的求解。最后输出最终剩余的元素编号。

下面是该代码的运行结果：

The last one is 3.

除了Josephus问题，循环链表还可以用于实现栈和队列等数据结构，这里就不再赘述。