约瑟夫问题Ｃ语言单向链表实现

约瑟夫问题是一个经典的数学问题，它的具体描述是：有n个人围成一圈，从第k个人开始报数，报到m的人出列，然后从下一个人开始重新报数，直到所有人都出列。现在我来介绍一下如何使用C语言的单向链表来实现约瑟夫问题。

首先，我们需要定义一个链表节点的结构体，包含两个成员变量：一个是保存人员编号的整型变量，另一个是指向下一个节点的指针。

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

接下来，我们可以编写一个函数来创建一个包含n个节点的循环链表，并返回链表的头节点。

Node* createCircularLinkedList(int n) {
    Node* head = NULL;
    Node* prev = NULL;
    
    for (int i = 1; i <= n; i++) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = i;
        
        if (head == NULL) {
            head = newNode;
        } else {
            prev->next = newNode;
        }
        
        prev = newNode;
    }
    
    prev->next = head; // 将最后一个节点的next指针指向头节点，形成循环链表
    
    return head;
}

接下来，我们可以编写一个函数来模拟约瑟夫问题的求解过程。

void josephusProblem(Node* head, int k, int m) {
    Node* current = head;
    Node* prev = NULL;
    
    // 找到从第k个人开始报数的节点
    for (int i = 1; i < k; i++) {
        prev = current;
        current = current->next;
    }
    
    // 开始报数并出列，直到所有人都出列
    while (current->next != current) {
        // 报数m次
        for (int i = 1; i < m; i++) {
            prev = current;
            current = current->next;
        }
        
        // 出列
        prev->next = current->next;
        Node* temp = current;
        current = current->next;
        free(temp);
    }
    
    // 输出最后一个出列的人员编号
    printf("最后一个出列的人员编号：%d\n", current->data);
    
    // 释放头节点的内存
    free(current);
}

最后，我们可以在主函数中调用上述函数来解决约瑟夫问题。

int main() {
    int n, k, m;
    printf("请输入总人数n：");
    scanf("%d", &n);
    printf("请输入从第k个人开始报数：");
    scanf("%d", &k);
    printf("请输入报数m次出列：");
    scanf("%d", &m);
    
    Node* head = createCircularLinkedList(n);
    
    josephusProblem(head, k, m);
    
    return 0;
}

这样，我们就可以通过C语言的单向链表来实现约瑟夫问题了。