约瑟夫环之循环链表用c语言写单链表

约瑟夫环（Josephus Problem）是一个经典的问题，涉及到在一个循环链表中按照给定步长删除节点。我们可以用C语言编写一个函数来解决这个问题。首先，我们需要创建一个结构体表示链表节点，并实现单链表的基本操作。下面是一个简单的示例：

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

// 链表节点结构体
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed.\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 插入节点到链表
void insertNode(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* temp = *head;
        while (temp->next != *head) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

// 约瑟夫环函数
Node* josephusRing(Node* head, int steps) {
    if (head == NULL || steps <= 0) {
        return head;
    }

    int count = 1; // 当前轮数
    Node* current = head;
    Node* next;

    while (true) {
        for (int i = 0; i < steps - 1 && current != NULL; ++i) {
            current = current->next;
        }
        if (current == NULL) { // 如果已经遍历完一圈
            current = head;
        } else {
            current = current->next;
            free(head); // 释放当前节点
        }
        ++count;
        if (count > 1) { // 每隔steps节点前进
            head = current;
        }
    }
    return head;
}

// 打印链表
void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    Node* head = NULL;
    // 初始化你的循环链表...
    
    int steps;
    printf("Enter the step size for Josephus problem: ");
    scanf("%d", &steps);

    head = josephusRing(head, steps);
    printList(head);

    return 0;
}

在这个程序中，`josephusRing` 函数根据给定的步骤 `steps` 删除链表中的节点，直到只剩下最后一个节点为止。注意这只是一个简化版本，实际应用中需要先构建一个完整的循环链表。