Input codes:(5)5
Input codes:(6)8
Input codes:(7)9   约瑟夫问题是一个十分有趣的小游戏，问题的描述如下：编号为1，2，3，......，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数），开始选一正整数m,从第一人开始，按顺时针方向自1开始顺序报数，报到m时此人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始从1报数，如此下去，直至全部人出列。我们的游戏就是看一下出列的次序。要求编者使用循环链表的方法将问题解决，下面给出程序的类型定义，其他代码编者自己完成。(运行后的输入和输出界面如下显示)
# include <stdio.h># include <malloc.h># include <conio.h>typedef struct node_type
{
int seq,code;   //分别存放编号和密码struct node_type *next;
}link;


**运行时屏幕显示如下。输入队列中的人数Input number n:7   
依次输入每一个人的手持密码
Input codes:(1)2     
Input codes:(2)1
Input codes:(3)4
Input codes:(4)3
      
至此可以建立起一个循环链表




Input the first code m:3   输入一个正整数作为起始密码
输入完成以后,可得以下的结果:
the result is :3 7 5 6 2 4 1

提示:
1 可以用循环链表,设立一个头结点.这样便于判断链表为空.
2用合适的算法让指针P指向要出列(删去)的节点,
3删去P所指的结点，注意删除的结点是不是链尾，要分情况讨论
4 当队列不空,回到2,重新定位指针P的位置,注意删去节点的CORD值是下次定位的依据.

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

typedef struct nodeTag {
    unsigned seq;
    unsigned code;
    struct nodeTag *pNextNode;
} node, *pNode;

pNode addNode(pNode pHead, unsigned seq, unsigned code)
{
    pNode pLast;
    pNode pNewNode;

    assert(pNewNode = malloc(sizeof(node)));
    pNewNode->seq       = seq;
    pNewNode->code      = code;
    pNewNode->pNextNode = pHead ? pHead : pNewNode;
    if (!pHead)
        pHead = pNewNode;
    else {
        pLast = pHead;
        while (pLast->pNextNode != pHead)
            pLast = pLast->pNextNode;
        pLast->pNextNode = pNewNode;
    }
    return pHead;
}

unsigned test(pNode *ppBeg, unsigned *pM)
{
    pNode    pBefore = *ppBeg;
    pNode    pRemove;
    pNode    pNext;
    unsigned seq;
    unsigned i;

    if (*pM == 1) {
        while (pBefore->pNextNode != *ppBeg)
            pBefore = pBefore->pNextNode;
        pRemove = pBefore->pNextNode;
        pNext   = pRemove->pNextNode;
    } else if (*ppBeg == (*ppBeg)->pNextNode) {
        pRemove = *ppBeg;
        pNext   = 0;
    } else {
        for (i = 2; i < *pM; ++i)
            pBefore = pBefore->pNextNode;
        pRemove = pBefore->pNextNode;
        pNext   = pRemove->pNextNode;
    }
    pBefore->pNextNode = pNext;
    *ppBeg             = pNext;
    *pM                = pRemove->code;
    seq                = pRemove->seq;
    free(pRemove);
    return seq;
}

int main(void)
{
    pNode    pHead = 0;
    pNode    pBeg;
    unsigned code;
    unsigned n;
    unsigned m;
    unsigned i;

    printf("Input number n: ");
    fflush(stdout);
    scanf("%u", &n);

    for (i = 1; i <= n; ++i) {
        printf("Input codes:(%u) ", i);
        fflush(stdout);
        scanf("%u", &code);
        pHead = addNode(pHead, i, code);
    }

    printf("Input the first code m: ");
    fflush(stdout);
    scanf("%u", &m);

    pBeg = pHead;
    while (pBeg)
        printf("%u ", test(&pBeg, &m));
}


/*
    m = 2(input)
    begin = node0(default)
    node0               node1               node2               node3               node4               node5
    |-----------------| |-----------------| |-----------------| |-----------------| |-----------------| |-----------------|
    | seq:       1    | | seq:       2    | | seq:       3    | | seq:       4    | | seq:       5    | | seq:       6    |
    | code:      2    | | code:      3    | | code:      1    | | code:      4    | | code:      3    | | code:      2    |
    | pNextNode: node1| | pNextNode: node2| | pNextNode: node3| | pNextNode: node4| | pNextNode: node5| | pNextNode: node0|
    |-----------------| |-----------------| |-----------------| |-----------------| |-----------------| |-----------------|

    m = 3(node1.code)
    being = node2(node1.pNextNode)
    node0               node2               node3               node4               node5
    |-----------------| |-----------------| |-----------------| |-----------------| |-----------------|
    | seq:       1    | | seq:       3    | | seq:       4    | | seq:       5    | | seq:       6    |
    | code:      2    | | code:      1    | | code:      4    | | code:      3    | | code:      2    |
    | pNextNode: node2| | pNextNode: node3| | pNextNode: node4| | pNextNode: node5| | pNextNode: node0|
    |-----------------| |-----------------| |-----------------| |-----------------| |-----------------|

    m = 3(node4.code)
    being = node5(node4.pNextNode)
    node0               node2               node3               node5
    |-----------------| |-----------------| |-----------------| |-----------------|
    | seq:       1    | | seq:       3    | | seq:       4    | | seq:       6    |
    | code:      2    | | code:      1    | | code:      4    | | code:      2    |
    | pNextNode: node2| | pNextNode: node3| | pNextNode: node5| | pNextNode: node0|
    |-----------------| |-----------------| |-----------------| |-----------------|

    m = 1(node2.code)
    begin = node3(node2.pNextNode)
    node0               node3               node5
    |-----------------| |-----------------| |-----------------|
    | seq:       1    | | seq:       4    | | seq:       6    |
    | code:      2    | | code:      4    | | code:      2    |
    | pNextNode: node3| | pNextNode: node5| | pNextNode: node0|
    |-----------------| |-----------------| |-----------------|

    m = 4(node3.code)
    begin = node5(node3.pNextNode)
    node0               node5
    |-----------------| |-----------------|
    | seq:       1    | | seq:       6    |
    | code:      2    | | code:      2    |
    | pNextNode: node5| | pNextNode: node0|
    |-----------------| |-----------------|

    m = 2(node0.code)
    being = node5(node0.pNextNode)
    node5
    |-----------------|
    | seq:       1    |
    | code:      2    |
    | pNextNode: node5|
    |-----------------|

    2 5 3 4 1 6
*/