运行环境：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是多么聪明的一个人啊！