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

目录

1.循环链表的定义

2.约瑟夫环问题

3.创建循环链表

4.删除节点操作

5.打印所有节点

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

---

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

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

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

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

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

1.循环链表的定义

循环链表与常规链表的区别在于，其尾节点指向头节点，形成一个环形结构。循环链表可以分为单向循环链表和双向循环链表两种类型。

单向循环链表的定义为：每个节点包含一个数据元素和指向下一个节点的指针，而最后一个节点的指针会指向第一个节点，形成一个环形结构。

双向循环链表的定义为：每个节点包含一个数据元素以及两个指针，一个指向前一个节点，一个指向后一个节点，而第一个节点的前驱指针指向最后一个节点，最后一个节点的后继指针指向第一个节点，也形成了一个环形结构。

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

2.约瑟夫环问题

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

解决约瑟夫环问题的步骤（设定问题的输入为n个人和要出局的报数m）：

1. 将n个人编号为1到n。
2. 从第一个人开始报数，报到m的人出局。
3. 从出局的人的下一个人开始重新报数，继续报到m的人出局。
4. 重复第3步，直到只剩下一个人为止。

3.创建单向循环链表

typedef struct node {
    int number;
    struct node* next;
} person;

// 初始化一个循环链表，表示圆桌上的人
person* initlink(int n) {
    person* head = (person*)malloc(sizeof(person));
    head->number = 1;
    head->next = NULL;
    person* cyclic = head;
    
    // 创建 n-1 个节点，并连接成循环链表
    for (int i = 2; i <= n; i++) {
        person* body = (person*)malloc(sizeof(person));
        body->number = i;
        body->next = NULL;
        cyclic->next = body;
        cyclic = cyclic->next; 
    }
    
    cyclic->next = head;
    return head;
}

定义一个名为person的结构体，由整型变量number和指向下一节点的指针next构成。

函数initlink用于初始化一个循环链表，表示圆桌上的人。函数首先创建一个头节点，然后使用for循环创建其他的节点并连接成循环链表。最后返回头节点。

这段代码用于创建一个循环链表，其中头节点的number字段表示第一个人在圆桌上的位置，后续节点的number字段按顺序递增，最后一个节点的next字段指向头节点形成一个循环链表结构。

4.约瑟夫环求解过程

// 找到第 k 个人并开始报数，数到第 m 个人出列
void findandkillk(person* head, int k, int m) {
    person* tail = head;
    while (tail->next != head) {
        tail = tail->next;
    }
    
    person* p = head;
    while (p->number != k) {
        tail = p;
        p = p->next;
    }
    
    // 从第 k 个人开始报数，直到只剩下一个人
    while (p->next != p) {
        for (int i = 1; i < m; i++) {
            tail = p;
            p = p->next;
        }
        
        // 删除第 m 个人出列，并释放内存
        tail->next = p->next;
        printf("出列人的编号为: %d\n", p->number);
        
        person* temp = p;
        p = p->next;
        free(temp);
    }
    
    printf("出列人的编号为: %d\n", p->number);
    free(p);
}

从第k个人开始报数，每次报到第m个人就将其出列。

先用循环找到链表中的尾节点，即满足tail->next = head的节点。

再用循环找到链表中编号为k的节点，并在找到之前更新尾节点的位置。

再用循环进行报数和出列操作，直到链表中只剩下最后一个人。循环中的内层循环每次进行m-1次迭代，找到第m个人之前的节点并更新尾节点的位置。随后，删除第m个人，并释放其内存。外层循环在每次迭代之后更新当前节点的位置，并继续进行报数和出列操作。

最后，输出剩下的最后一个人的编号，并释放其内存。

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

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

typedef struct node {
    int number;
    struct node* next;
} person;

// 初始化一个循环链表，表示圆桌上的人
person* initlink(int n) {
    person* head = (person*)malloc(sizeof(person));
    head->number = 1;
    head->next = NULL;
    person* cyclic = head;
    
    // 创建 n-1 个节点，并连接成循环链表
    for (int i = 2; i <= n; i++) {
        person* body = (person*)malloc(sizeof(person));
        body->number = i;
        body->next = NULL;
        cyclic->next = body;
        cyclic = cyclic->next; 
    }
    
    cyclic->next = head;
    return head;
}

// 找到第 k 个人并开始报数，数到第 m 个人出列
void findandkillk(person* head, int k, int m) {
    person* tail = head;
    while (tail->next != head) {
        tail = tail->next;
    }
    
    person* p = head;
    while (p->number != k) {
        tail = p;
        p = p->next;
    }
    
    // 从第 k 个人开始报数，直到只剩下一个人
    while (p->next != p) {
        for (int i = 1; i < m; i++) {
            tail = p;
            p = p->next;
        }
        
        // 删除第 m 个人出列，并释放内存
        tail->next = p->next;
        printf("出列人的编号为: %d\n", p->number);
        
        person* temp = p;
        p = p->next;
        free(temp);
    }
    
    printf("出列人的编号为: %d\n", p->number);
    free(p);
}

int main() {
    printf("输入圆桌上的人数 n: ");
    int n;
    scanf("%d", &n);
    person* head = initlink(n);
    
    printf("从第 k 人开始报数 (k > 1 且 k < %d): ", n);
    int k;
    scanf("%d", &k);
    
    printf("数到第 m 个人出列：");
    int m;
    scanf("%d", &m);
    
    findandkillk(head, k, m);
    
    return 0; 
}

代码中的主要函数有initlink和findandkillk。

initlink函数根据输入的人数 n，初始化一个循环链表。循环链表中的每个节点都存储一个人的编号，编号从 1 到 n。该函数返回链表的头节点指针。

findandkillk函数用于解决约瑟夫环问题。它接收初始化好的循环链表的头节点指针，起始编号 k 和报数间隔 m 作为参数。首先，它找到从第 k 个人开始报数的位置，并且记录该位置的上一个节点，即tail。接着，通过迭代法，每次报数到第 m 个人时，将其从链表中删除，并释放相应的内存空间。直到链表中只剩一个节点时，停止迭代，并输出最后剩下的那个人的编号。

在main函数中，用户输入要解决的约瑟夫环问题的相关参数，然后调用findandkillk函数进行求解。

程序截图如下：