约瑟夫生死者 c语言 单链表尾插法

单链表的尾插法也可以用来实现约瑟夫生死者问题。以下是一个使用单链表尾插法的 C 语言实现：

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

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

Node *createList(int n) {
    Node *head = NULL;
    Node *tail = NULL;
    for (int i = 1; i <= n; i++) {
        Node *node = (Node *)malloc(sizeof(Node));
        node->num = i;
        node->next = NULL;
        if (head == NULL) {
            head = node;
        } else {
            tail->next = node;
        }
        tail = node;
    }
    tail->next = head;  // 首尾相连，形成循环链表
    return head;
}

void josephus(int n, int m) {
    Node *head = createList(n);
    Node *tail = head;
    while (tail->next != head) {
        tail = tail->next;
    }
    Node *p = head;
    while (p->next != p) {  // 只剩一个结点时结束
        for (int i = 1; i < m; i++) {
            p = p->next;
            tail = tail->next;
        }
        printf("%d ", p->num);  // 输出要出圈的数
        tail->next = p->next;  // 删除出圈的数
        free(p);  // 释放出圈的结点的内存
        p = tail->next;  // 移动到下一个位置
    }
    printf("%d\n", p->num);  // 输出最后剩下的数
    free(p);
}

int main() {
    int n, m;
    printf("请输入总人数和出圈间隔：");
    scanf("%d %d", &n, &m);
    josephus(n, m);
    return 0;
}

这个程序同样通过 `createList` 函数创建一个有 `n` 个结点的循环链表，然后通过 `josephus` 函数模拟约瑟夫生死者问题的过程。在每一轮中，先循环 `m - 1` 次，找到要出圈的结点的前一个结点和尾结点，然后输出要出圈的结点的值，并删除这个结点。最后释放出圈的结点的内存，并移动指针到下一个位置，直到只剩下一个结点为止。