C语言约瑟夫环的实现
C语言约瑟夫环的实现
一、典故:
据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是商量了一个自杀方式：
41个人排成一个圆圈，由第1个人开始报数，每数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
二、用循环链表实现
1.约瑟夫环实现
sListNode*JosephCycle(sListNode*pHead,DataTypex)
{
if(pHead==NULL)
returnNULL;
sListNode*cur=pHead;
while(1)
{
DataTypem=x;
if(cur->next==cur)
{
returncur;
}
while(--m)
{
cur=cur->next;
}
//delete替换法
cur->data=cur->next->data;
sListNode*del=cur->next;
cur->next=cur->next->next;
free(del);
del=NULL;
}
2.测试
voidTestJosephCycle()
{
sListNode*list=NULL;
Push_Back(list,1);
Push_Back(list,2);
Push_Back(list,3);
Push_Back(list,4);
Push_Back(list,5);
Push_Back(list,6);
Push_Back(list,7);
Push_Back(list,8);
Push_Back(list,9);
PrintList(list);
//建环
sListNode*cur=list;
while(cur->next!=NULL)
{
cur=cur->next;
}
cur->next=list;
sListNode*ret=JosephCycle(list,3);
cout<<"Joseph:"<data<
以上就是约瑟夫环的简单实现，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！