约瑟夫环游戏 - 单链表实现 - 常规

约瑟夫环游戏 - 单链表实现

问题描述:

有 M 个人，编号分别为 1 到 M，玩约瑟夫环游戏。初始时他们按编号顺序排成队列。每一轮游戏开始时，有一个正整数报数密码 N。队列中的人依次围坐成一圈，从队首的人开始报数，报到 N 的人出列。然后从出列的人的下一人开始重新报数，报到 N 的人出列。重复这一过程，直到所有人都出列，完成一轮游戏。所有出列的人形成新队列。游戏可能玩很多遍，每遍都有新的报数密码。求若干遍游戏完成后队列的次序。

要求:

使用单链表实现，程序要求采用模块化设计，格式规范，并有合适的注解。

输入描述:

每个测试用例包含若干个正整数（至少 1 个），第一个正整数为玩游戏人数 M，后续每个正整数为每遍游戏报数密码；报数密码可能为 1。

输出描述:

每个测试用例结果占一行，每个编号占 4 位。

算法思路:

定义单链表节点:

struct Node {
    int data; // 节点编号
    struct Node *next; // 指向下一个节点
};

创建循环链表:
- 创建 M 个节点，并按编号依次插入链表。
- 将最后一个节点的 next 指向第一个节点，形成循环链表。
删除节点函数:
- 输入参数：链表头指针，要删除节点的编号。
- 找到要删除的节点的前一个节点 prev。
- 将 prev->next 指向要删除节点的下一个节点。
- 释放被删除节点的内存空间。
- 返回被删除节点的编号。
遍历链表函数:
- 输入参数：链表头指针。
- 从头节点开始，依次遍历所有节点，输出每个节点的编号。
游戏逻辑:
- 循环遍历链表，每次删除报到 N 的节点，直到链表为空。
- 每次删除后，更新链表头指针。
- 将出列的节点组成新的链表，并输出链表中所有节点的编号。
重复游戏:
- 重复步骤 5 和步骤 6，直到所有人都出列。

代码示例:

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

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

// 创建循环链表
struct Node *createList(int M) {
    struct Node *head = NULL, *tail = NULL, *newNode;
    for (int i = 1; i <= M; i++) {
        newNode = (struct Node *)malloc(sizeof(struct Node));
        newNode->data = i;
        newNode->next = NULL;
        if (head == NULL) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }
    tail->next = head;
    return head;
}

// 删除节点
int deleteNode(struct Node **head, int N) {
    struct Node *prev = *head;
    struct Node *current = *head;
    int count = 1;
    while (count < N) {
        prev = current;
        current = current->next;
        count++;
    }
    int deleted = current->data;
    prev->next = current->next;
    free(current);
    if (*head == current) {
        *head = prev->next;
    }
    return deleted;
}

// 遍历链表
void printList(struct Node *head) {
    struct Node *current = head;
    do {
        printf("%04d", current->data);
        current = current->next;
    } while (current != head);
    printf("\n");
}

int main() {
    int M, N;
    scanf("%d", &M);
    struct Node *head = createList(M);
    while (scanf("%d", &N) != EOF) {
        struct Node *newHead = NULL, *newTail = NULL, *deletedNode;
        while (head != NULL) {
            deletedNode = deleteNode(&head, N);
            if (newHead == NULL) {
                newHead = (struct Node *)malloc(sizeof(struct Node));
                newHead->data = deletedNode;
                newHead->next = NULL;
                newTail = newHead;
            } else {
                newTail->next = (struct Node *)malloc(sizeof(struct Node));
                newTail->next->data = deletedNode;
                newTail->next->next = NULL;
                newTail = newTail->next;
            }
        }
        printList(newHead);
        head = newHead;
    }
    return 0;
}

代码说明:

createList() 函数用于创建循环链表。
deleteNode() 函数用于删除指定位置的节点，并返回被删除节点的编号。
printList() 函数用于遍历链表，输出链表中所有节点的编号。
main() 函数用于读取输入数据，调用相关函数实现游戏逻辑。

注意:

为了避免内存泄漏，需要在 deleteNode() 函数中释放被删除节点的内存空间。
在 main() 函数中，需要使用 malloc() 分配内存空间给新的链表节点。
实际编写代码时，可以根据需要进行修改和完善。

总结:

本文介绍了使用单链表实现约瑟夫环游戏的算法思路和代码示例。通过单链表数据结构，可以方便地实现节点的插入和删除操作，从而完成约瑟夫环游戏的模拟。在实际应用中，可以根据需要调整算法和代码，以满足不同的需求。

相关资料: