使用循环链表解决约瑟夫问题(Josephus Problem)

问题说明

约瑟夫问题是个有名的问题:N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。
同理还有丢手绢，猴子称王都是一模一样的问题，首先用循环就可以直接一次性解决，记录当前位置的数并且循环取余即可，但是直观而言，肯定是循环数组更加的直观！

代码分析

不哆嗦了，直接贴上，里面注释还是很多的：

#include <stdio.h>
#include <stdlib.h>
//定义循环链表
typedef struct node//定义node结构体
{
    int data;
    struct node* next;
}cLinkList;//typedef struct node* cLinkList;定义一个struct node类型的循环链表

//主函数
int main()
{
    cLinkList *head, *p, *s, *temp;
    int n, k;
    int i = 1;
    printf("Please enter the total number n:\n");
    scanf("%d", &n);
    printf("Please enter the key value:\n");
    scanf("%d", &k);
    k %= n;
    head = (cLinkList *)malloc(sizeof(cLinkList));
    p = head;
    p->next = p;//这里要赋值为p，不能赋值为head，要保持head的位置不变
    p->data = i;
    for(i = 2; i <= n; i++)
    {
        s = (cLinkList *)malloc(sizeof(cLinkList));
        s->data = i;
        s->next = p->next;
        p->next = s;
        p = s;
    }

    p = head;
    int total = n;
    while(n--)
    {
        for(i = 1; i < k - 1; i++)
        {
            p = p->next;
        }
        printf("%d->", p->next->data);
        temp = p->next;//temp为要删除的元素
        p->next = temp->next;//链表中跳过temp
        free(temp);//释放temp
        p = p->next;//p向前移动继续寻找
    }
    printf("Done！\n");
    return 0;
}