数据结构|【数据结构】约瑟夫环（单向循环链表的应用）——C语言数据结构|c语言|链表

题目：一堆猴子都有编号，编号是1，2，3 …n ,这群猴子（n个）按照1-n的顺序围坐一圈，从第1开始数，每数到第m个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。请设计算法编写程序输出为大王的猴子的编号。
思路：建立单向循环链表，链表结点值对应猴子编号，对循环链表进行扫描，每计数到m时则删除该结点，直到链表中只剩下一个结点则停止，输出该结点值即为猴王编号。
单向循环链表的存储结构及基本运算：https://blog.csdn.net/weixin_51450101/article/details/121845708
完整代码+注释

/* 单向循环链表的应用——约瑟夫环 */# include # include/*链表的存储结构*/ typedef struct Node {//结点类型定义 int data; struct Node* next; }Node,*CLinkList; CLinkList CL; /*初始化循环链表*/ InitCLinkList(CLinkList* CL) { *CL = (CLinkList)malloc(sizeof(Node)); //建立头结点 (*CL)->next = *CL; //建立空的循环单链表CL }/*尾插法建立循环链表，长度为n*/ void CreateCLinkList(CLinkList CL,int n) { Node* rear, * s; rear = CL; //rear指针动态指向链表的当前表尾，其初值指向头结点 int i; for (i = 0; i < n; i++) { s = (Node*)malloc(sizeof(Node)); s->data = https://www.it610.com/article/i + 1; //对每个结点进行赋值，对应猴子序号 rear->next = s; //修改指针，完成新结点s的插入 rear = s; } rear->next = CL; //最后一个结点的链域指向头结点 }void Joseph(CLinkList CL, int m) { Node* pre, * r; int j = 0; pre = CL; //pre初值指向头结点 r = NULL; /*删除头结点*/ while (pre->next != CL) { pre = pre->next; //pre指向最后一个结点 } r = pre->next; //修改指针删除头结点 pre->next = r->next; free(r); /*循环，j每计数到m-1时删除其后一个结点，只剩一个结点时循环终止*/ while (pre != pre->next) { if (j == m - 1) { r = pre->next; //结点删除 pre->next = r->next; free(r); j = 0; //每完成一次删除后，j置0以便下一次计数 } pre = pre->next; //pre指向下一结点 j++; } printf("猴王的号码为：%d\n", pre->data); //输出最后剩下的结点值即为最终结果 }int main() { int m, n; //n表示猴子总个数，m表示数到第m个的猴子需要离开 printf("请输入正整数m,n："); scanf("%d%d", &m, &n); while (m <= 0 || n <= 0) {//判断输入数据是否合法 printf("请输入正整数m,n!\n"); printf("请重新输入正整数m,n："); scanf("%d%d", &m, &n); } if (m == 1)//m=1时单独考虑 printf("猴王的号码为：%d\n", n); if (m > 1 && n > 0) { InitCLinkList(&CL); CreateCLinkList(CL, n); Joseph(CL, m); } return 0; }

【数据结构|【数据结构】约瑟夫环（单向循环链表的应用）——C语言】运行结果