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!