如何用C语言代码实现约瑟夫环

本篇内容介绍了“如何用C语言代码实现约瑟夫环”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

一、典故:

      据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是商量了一个自杀方式：

      41个人排成一个圆圈，由第1个人 开始报数，每数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从，Josephus要 他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

二、用循环链表实现

1.约瑟夫环实现

sListNode* JosephCycle(sListNode* pHead, DataType x) 
{ 
 if(pHead == NULL) 
 return NULL; 
 sListNode* cur = pHead; 
 while(1) 
 { 
 DataType m = x; 
 if(cur->next == cur) 
 { 
 return cur; 
 } 
 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.测试

void TestJosephCycle() 
{ 
 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:"<<ret->data<<endl; 
 //解环 
 free(ret); //明确知道只有一个节点，直接释放 
 ret = NULL; 
}

“如何用C语言代码实现约瑟夫环”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站，小编将为大家输出更多高质量的实用文章！