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; 
} 

以上就是约瑟夫环的简质朴现，若有疑问请留言可能到本站社区交换接头，感激阅读，但愿能辅佐到各人，感谢各人对本站的支持！

（编辑：湖南网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!