Implementation of Joseph rings in C language

Implementation of Joseph rings in C language

1. The allusion:

It is said that the famous jewish historian Josephus had the following story: after the Romans occupied chautapat, 39 jews hid in a cave with Josephus and his friends. 39 jews decided that they would rather die than be caught by the enemy, so they discussed a way to commit suicide:

41 people in a circle, from the first person to count, each count to the third person must commit suicide, and then the next person to count again until all of them have committed suicide. However, Josephus and his friend did not want to comply. Josephus asked his friend to pretend to comply. He placed his friend in the 16th and 31st positions with him, thus avoiding the death game.

2. Using circular linked lists

1. Joseph ring implementation

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 Substitution method  
 cur->data = cur->next->data; 
 sListNode* del = cur->next; 
 cur->next = cur->next->next; 
 free(del); 
 del=NULL; 
 } 

2. The test

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); 
 // Building the ring  
 sListNode* cur = list; 
 while(cur->next != NULL) 
 { 
 cur = cur->next; 
 } 
 cur->next = list; 
 sListNode* ret = JosephCycle(list, 3); 
 cout<<"Joseph:"<<ret->data<<endl; 
 // Power network  
 free(ret); // Know that only 1 Nodes, directly released  
 ret = NULL; 
} 

The above is the simple implementation of Joseph ring, if you have any questions please leave a message or to the site community exchange discussion, thank you for reading, hope to help you, thank you for the support of the site!