约瑟夫环C语言实现

// use C99 
#include <stdio.h>
#include <malloc.h>

#define uint unsigned int

//构建结构体
typedef struct Node {
    uint Num;
    struct Node *next;
} JoseNode, *PNode, *Head;

//初始化循环单链表
Head init_head() {
    Head h = (Head) malloc(sizeof(JoseNode));
    if (!h) {
        printf("初始化链表错误！\n");
        return 0;
    }
    h->next = h;
    return h;
}

//单链表插入操作
uint insert(PNode h, uint N) {
    PNode p = h, q;
    if (N == 1) {
        p->Num = 1;
        p->next = p;
        return 1;
    }
    for (int pos = 2; pos <= N; pos++) {
        p = p->next;
        q = (JoseNode *) malloc(sizeof(JoseNode));
        if (!q) {
            return 0;
        }
        q->Num = pos;
        q->next = p->next;
        p->next = q;
    }
    return 1;
}

//出局函数
PNode delete(Head h, uint n, uint k) {
    PNode p = h, q;
    while (n-- > 1) {
        for (int i = 1; i < k - 1; i++) {
            p = p->next;
        }

        q = p->next;
        p->next = q->next;
        p = p->next;

        printf("出局的人为：%3d号\n", q->Num);
        free(q);
    }
    return p;
}

//遍历
void print_list(Head h, uint M) {
    int i = 0;
    PNode p = h;
    printf("参与的人的编号为：\n");
    while (i++ < M) {
        printf("%d ", p->Num);
        p = p->next;
    }
    printf("\n");
}

int main() {
    uint n = 0;//参与的人数
    uint k = 0;//报数密码
    while (n <= 1) {
        printf("请输入参与人数(大于1)：");
        scanf("%d", &n);
    }
    while (k <= 1) {
        printf("请输入出局密码(大于1)：");
        scanf("%d", &k);
    }

    Head h = init_head();
    insert(h, n);
    print_list(h, n);

    PNode r = delete(h, n, k);
    printf("\n\n获胜者为：%3d号\n", r->Num);

    return 0;
}