【数据结构】使用循环链表结构实现约瑟夫环问题

目录

1.循环链表的定义

2.约瑟夫环问题

3.创建循环链表

4.删除节点操作

5.打印所有节点

6.实现约瑟夫环问题的完整程序代码

---

🌈嗨！我是Filotimo__🌈。很高兴与大家相识，希望我的博客能对你有所帮助。

💡本文由Filotimo__??原创，首发于CSDN📚。

📣如需转载，请事先与我联系以获得授权??。

🎁欢迎大家给我点赞👍、收藏??，并在留言区📝与我互动，这些都是我前进的动力！

🌟我的格言：森林草木都有自己认为对的角度🌟。

1.循环链表的定义

循环链表是一种特殊的单链表，它的特点是链表中的最后一个节点指向链表的头节点，形成一个闭环。

这种结构使得循环链表可以从任意节点开始遍历，并且可以方便地在链表中插入或删除节点。它可以通过不断重复遍历整个链表来实现循环的效果。

2.约瑟夫环问题

约瑟夫环问题是一个经典的数学问题，假设 n 个人站成一个环状，从第一个人开始报数，每次报到 m 的人出列，再从下一个人开始重新报数，直到所有人都出列。最后剩下的人的编号即为最后的获胜者。

3.创建循环链表

// 定义循环链表的节点
typedef struct Node {
    int data;               // 节点数据
    struct Node* next;      // 指向下一个节点的指针
} Node;

// 创建循环链表
Node* createCircularLinkedList(int n) {
    Node* head = NULL;
    Node* temp = NULL;

    // 创建链表节点
    for (int i = 1; i <= n; i++) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = i;

        if (head == NULL) {
            head = newNode;
        } else {
            temp->next = newNode;
        }

        temp = newNode;
    }

    // 将最后一个节点指向头节点，形成循环
    temp->next = head;

    return head;
}

在函数createCircularLinkedList中，整数n作为参数，表示链表中节点的数量。它定义了两个指针变量head和temp，分别用于指向链表的头节点和临时节点。

该函数使用for循环创建链表的节点。对于每个节点，首先使用malloc函数动态分配内存空间，将返回的指针强制转换为 Node*类型，并将其赋值给newNode->data。然后，根据链表是否为空，将newNode插入链表中。如果链表为空，将head指向newNode；否则，将 newNode添加为temp的下一个节点。

完成节点的创建后，将最后一个节点的next指针指向头节点，形成循环。最后，返回头节点head。

4.删除节点操作

// 在循环链表中删除指定位置的节点
Node* deleteNode(Node* head, int k) {
    // 链表为空，直接返回
    if (head == NULL) {
        return NULL;
    }

    Node* current = head;
    Node* prev = NULL;

    // 遍历链表，直到找到要删除的节点
    int count = 1;
    while (count != k) {
        prev = current;
        current = current->next;
        count++;
    }

    // 删除节点并更新指针
    if (prev != NULL) {
        prev->next = current->next;
    } else {
        head = current->next;   // 删除头节点时更新头指针
    }
    free(current);

    return head;
}

函数deleteNode接受一个循环链表的头节点head和要删除的节点位置k作为参数。

它定义两个指针变量current和prev，并初始化current为head，prev为NULL。

我们使用while循环遍历链表，直到找到要删除的位置k。在循环中，将current赋值给prev，将current->next赋值给current，并将count递增。这样，当循环结束时，current就指向了要删除的节点，prev则指向了要删除节点的前一个节点。

在找到要删除的节点后，通过判断prev是否为NULL来确定要删除的是否是头节点。如果prev不为NULL，则设置prev->next为current->next，这样就将current节点从链表中删除。如果prev为NULL，则说明要删除的是头节点，需要将head指向current->next来更新头指针。

最后，使用free函数释放被删除节点current的内存，并返回更新后的头节点head。

5.打印所有节点

// 打印循环链表中的所有节点
void printCircularList(Node* head) {
    if (head == NULL) {
        return;
    }

    Node* current = head;

    do {
        printf("%d ", current->data);
        current = current->next;
    } while (current != head);

    printf("\n");
}

该函数定义指针变量current并初始化为head，同时使用do-while循环遍历循环链表。在循环中，打印current节点的数据域data，并将current->next赋值给current，这样就能够依次输出链表中的所有节点值。

在循环结束后，通过输出换行符\n，打印完整的链表内容。

6.实现约瑟夫环问题的完整程序代码

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

// 定义循环链表的节点
typedef struct Node {
    int data;               // 节点数据
    struct Node* next;      // 指向下一个节点的指针
} Node;

// 创建循环链表
Node* createCircularLinkedList(int n) {
    Node* head = NULL;
    Node* temp = NULL;

    // 创建链表节点
    for (int i = 1; i <= n; i++) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = i;

        if (head == NULL) {
            head = newNode;
        } else {
            temp->next = newNode;
        }

        temp = newNode;
    }

    // 将最后一个节点指向头节点，形成循环
    temp->next = head;

    return head;
}

// 在循环链表中删除指定位置的节点
Node* deleteNode(Node* head, int k) {
    // 链表为空，直接返回
    if (head == NULL) {
        return NULL;
    }

    Node* current = head;
    Node* prev = NULL;

    // 遍历链表，直到找到要删除的节点
    int count = 1;
    while (count != k) {
        prev = current;
        current = current->next;
        count++;
    }

    // 删除节点并更新指针
    if (prev != NULL) {
        prev->next = current->next;
    } else {
        head = current->next;   // 删除头节点时更新头指针
    }
    free(current);

    return head;
}

// 打印循环链表中的所有节点
void printCircularList(Node* head) {
    if (head == NULL) {
        return;
    }

    Node* current = head;

    do {
        printf("%d ", current->data);
        current = current->next;
    } while (current != head);

    printf("\n");
}

int main() {
    int n, k;
    printf("请输入总人数：");
    scanf("%d", &n);
    printf("请输入报数的间隔：");
    scanf("%d", &k);

    // 创建循环链表
    Node* head = createCircularLinkedList(n);
    printf("初始序列：");
    printCircularList(head);

    // 模拟约瑟夫环问题
    while (head->next != head) {
        head = deleteNode(head, k);
        printf("淘汰第 %d 号\n", k);
        printCircularList(head);
    }

    printf("胜出者是：%d\n", head->data);

    return 0;
}

createCircularLinkedList 函数用于创建循环链表，deleteNode 函数用于删除指定位置的节点，printCircularList 函数用于打印循环链表中的所有节点。在 main 函数中，首先获取用户输入的总人数和报数的间隔，然后创建循环链表并打印初始序列。然后通过循环调用 deleteNode 函数和 printCircularList 函数模拟约瑟夫环问题的过程，直到只剩下一个节点，即胜出者。最后，输出胜出者的编号。

程序运行结果如下：