数据结构-猴子选大王(约瑟夫环（Josephus）)（链表）-C语言-[输入有n只猴子，从第q只猴子开始，从1到m报数。最后编号为m的猴子被选为大王]

题目描述

【问题描述】（建议用链表实现）

要从n只猴子中选出一位大王。它们决定使用下面的方法：
n只猴子围成一圈，从1到n顺序编号。从第q只猴子开始，从1到m报数，凡报到m的猴子退出竞选，下一次又从退出的那只猴子的下一只开始从1到m报数，直至剩下的最后一只为大王。请问最后哪只猴子被选为大王。
【输入形式】

控制台输入三个整数n，m，q，各整数间以一个空格分隔。
【输出形式】

输出最后选为大王的猴子编号。
【样例输入】
7 4 3
【样例输出】
4
【样例说明】

输入有7只猴子，从第3只猴子开始，从1到4报数。最后编号为4的猴子被选为大王。

题目分析

此类题型统称为约瑟夫环（Josephus）问题。

若运用链表实现，应选择单向循环链表加以实现。

实现思路

1. 单向链表插入
2. 寻找开始报数的位置
3. 循环报数，跳过报m数字的几点并释放，直至节点的next指针指向这个节点本身为止。
4. 打印结果

代码

#include <stdio.h>
#include <stdlib.h>struct circle_list
{
    int num;struct circle_list *next;
};int main()
{
    int i, j = 0;int n, m, q;scanf("%d%d%d", &n, &m, &q); struct circle_list *List = NULL, *p = NULL, *r = NULL;for (i = 0; i < n; i++){
    r = (struct circle_list *)malloc(sizeof(struct circle_list));r->num = ++j;if (List == NULL){
    List = p = r;//头结点}else{
    p->next = r;p = p->next;}}p->next = List;//指向头结点//找到q位置并使r存储q所在结点位置，p指向q所在结点的next结点for (p = List, i = 0; i < q - 1; i++ ) {
    r = p, p = p->next;}//找到大王while (p->next != p){
    for (i = 1; i < m; i++){
    r = p;p = p->next;}r->next = r->next->next;//跳过报m数的猴子free(p);//将被调过位置的结点释放p = r->next;}printf("%d", p->num);return 0;
}