目录
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函数进行求解。
程序截图如下：文章来源：https://www.toymoban.com/news/detail-800700.html
文章来源地址https://www.toymoban.com/news/detail-800700.html
到了这里，关于【数据结构】使用循环链表结构实现约瑟夫环问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
