约瑟夫环

已知n个人（以编号1，2，···，n分别表示）围坐在一个桌子周围，从编号为k的人开始报数，数到的那个人出列，他的下一个人又从1开始报数，数到m的那个人又出列，依次重复下去，要求找到最后出列的人。

源代码：

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

typedef struct A{
    int number;     //编号
    struct A *next;
}LinkList;
LinkList* initList(int n){
    //定义一个头结点
    LinkList *head;
    head = (LinkList *)malloc(sizeof(LinkList));
    head->number = 1;
    head->next = NULL;
    //定义一个尾结点
    LinkList *temp;
    temp = head;
    int i;
    //循环创建结点
    for(i = 2; i <= n; i++)
    {
        LinkList *body;
        body = (LinkList *)malloc(sizeof(LinkList));
        body->number = i;
        body->next = NULL;
        temp->next = body;
        //temp总是指向最后一个结点
        temp = body;
    }
    //temp指向头结点，构成循环链表
    temp->next = head;
    return head;
}
void fidLink(LinkList *head, int k, int m){
    //在编号为k的人开始报数，报的数为m的人出列
    LinkList *by;
    //tail始终指向by的前一个结点
    LinkList *tail;
    by = head;

    //找到编号为k的人
    while(by->number != k)
    {
        tail = by;
        by = by->next;
    }
    //链表中除了by，其他的都已经出列
    while(by->next != by)
    {
        int i;
        //找到报数为m的人
        for(i = 1; i < m; i++)
        {
            tail = by;
            by = by->next;
        }
        //tail指向by的下一个结点
        tail->next = by->next;
        printf("出列人的编号：%d\n",by->number);
        //释放by结点
        free(by);
        //继续游戏
        by = tail->next;
    }
    //输出最后剩余的一个结点，并释放结点
    printf("最后一个人是：%d\n",by->number);
    free(by);
}
int main()
{
    int n,k,m;
    printf("请输入圆桌上的人数：");
    scanf("%d",&n);
    LinkList *head;
    head = initList(n);
    printf("请输入开始报数的人的编号：");
    scanf("%d",&k);
    printf("请输入出列人报的数：");
    scanf("%d",&m);
    fidLink(head,k,m);
    return 0;
}

运行结果：