利用C语言实现自杀环---约瑟夫环

运行环境：win10，vs2013

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始从1报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到剩余一个人

linklist.c

#include
#include
#include
typedef int datatype;//定义数据类型
//节点的构造
typedef struct node
{
    datatype data;
    struct node*pnext;
}node,*pnode;
//初始化
void initlinklist(pnode* phead)
{
    assert(phead);//断言
    (*phead) = null;
}
//构造新节点
pnode buynode(datatype x)
{
    pnode pcur = (pnode)malloc(sizeof(node));
    if (null == pcur)
        return null;
    else
    {
        pcur->data = x;
        pcur->pnext = null;
        return pcur;
    }
}
//打印链表
void printlinklist(pnode phead)
{
    assert(phead);
    if (null == phead)
        printf("null");
    else
    {
        while (phead)
        {
            printf("%d--->", phead->data);
            phead = phead->pnext;
        }
        printf("null");
    }
    printf("\n");
}
//尾插
pnode pushback(pnode* phead,datatype x)
{
    assert(phead);
    pnode ptail = null;
    pnode pcur = buynode(x);//调用buynode()函数，对给出的data构造节点
    if (null == (*phead))
    {
        (*phead) = pcur;
    }
    else
    {
        ptail = (*phead);
        while (ptail->pnext)
        {
            ptail = ptail->pnext;
        }
        ptail->pnext = pcur;
    }
    return phead;
}
//约瑟夫环函数
pnode josephcircle(pnode phead, size_t m)
{
    pnode pcur = phead;
    pnode pdel = null;
    assert(phead);
    //如果链表是空链表或者只有一个节点，都返回头指针
    if (null == phead||null==phead->pnext)
        return phead;
    //给链表构环
    while (pcur->pnext)
    {
        pcur = pcur->pnext;
    }
    pcur->pnext = phead;
    pcur = phead;
    //循环删除节点
    while (pcur != pcur->pnext)
    {
        int count = m;//报数为count
        while (--count)
        {
            pcur = pcur->pnext;
        }
        //替换法删除节点（通过删除需要删除节点的下一个节点）
        pdel = pcur->pnext;
        pcur->data = pdel->data;
        pcur->pnext = pdel->pnext;
        free(pdel);
        pdel = null;
    }
    //解环
    pcur->pnext = null;
    return pcur;
}

test.c

void test()
{
    struct node* phead;
    struct node* p;
    initlinklist(&phead);
    pushback(&phead, 2);
    pushback(&phead, 3);
    pushback(&phead, 4);
    pushback(&phead, 5);
    pushback(&phead, 6);
    pushback(&phead, 7);
    pushback(&phead, 8);
    pushback(&phead, 9);
    printlinklist(phead);//打印链表
    p=josephcircle(phead, 3);
    printlinklist(p);
}
int main()
{
    test();
    system("pause");
    return 0;
}

运行结果：

ps：由此可见，josephus是多么聪明的一个人啊！