用链队列求解约瑟夫问题 C语言

下面是用链队列求解约瑟夫问题的C语言代码：

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

// 定义节点结构体
typedef struct node {
    int data;
    struct node *next;
} Node;

// 定义队列结构体
typedef struct queue {
    Node *front;
    Node *rear;
    int size;
} Queue;

// 初始化队列
void initQueue(Queue *q) {
    q->front = NULL;
    q->rear = NULL;
    q->size = 0;
}

// 判断队列是否为空
int isEmpty(Queue *q) {
    return q->size == 0;
}

// 入队
void enQueue(Queue *q, int data) {
    Node *newNode = (Node *) malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    if (isEmpty(q)) {
        q->front = newNode;
        q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }

    q->size++;
}

// 出队
int deQueue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return -1;
    }

    Node *temp = q->front;
    int data = temp->data;

    q->front = q->front->next;
    q->size--;

    if (isEmpty(q)) {
        q->rear = NULL;
    }

    free(temp);

    return data;
}

// 求解约瑟夫问题
void josephus(int n, int m) {
    Queue q;
    initQueue(&q);

    // 将所有人入队
    for (int i = 1; i <= n; i++) {
        enQueue(&q, i);
    }

    // 开始报数
    int count = 1;
    while (!isEmpty(&q)) {
        int data = deQueue(&q);
        if (count % m != 0) {
            enQueue(&q, data);
        } else {
            printf("%d ", data);
        }
        count++;
    }
}

int main() {
    int n, m;
    printf("Enter the number of people and the count interval: ");
    scanf("%d %d", &n, &m);

    josephus(n, m);

    return 0;
}

代码思路：

1. 定义链队列结构体，包括节点结构体和队列结构体。
2. 初始化队列，包括初始化队首、队尾和队列长度。
3. 判断队列是否为空。
4. 入队，创建一个新节点，将其加入到队列尾部。
5. 出队，将队首节点删除，返回其数据。
6. 求解约瑟夫问题，首先将所有人入队，然后开始报数，如果报数不为m，则将该人重新入队，否则将该人出队，并输出其编号。
7. 主函数中，输入人数和报数间隔，调用函数求解约瑟夫问题。