Answer to Question #259714 in C for Lucifer

Question

Your task is to develop a circular linked-list based simulation of the Josephus problem. The simulation will be text based. The user should be presented with a text-based menu asking him to enter the total number of people (n), starting point (i), direction (clockwise/anti-clockwise) and number to be skipped (k). Your program then must populate a circular linked list with n nodes where data of each node should be their position in the circle (starting from 1).Your program should then work iteratively printing the remaining persons after each iteration (round of killing). After the last iteration only the node with the winning initial position should be left in the list. Example:

• For n =15

• k = 2

• starting point (i) = 1

• direction = clockwise

Initial scenario:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

After1st iteration: 1 3 5 7 9 11 13 15

After2nd iteration: 3 7 11 15

After3rd iteration: 7 15

After4th iteration: 15 (15 remains in the end). Program ends.

Answer 1

#include <stdio.h>
#include <stdlib.h>

typedef struct Node{
 int data;
 struct Node *next, *prev;
}node;

node *createDCLL(int n)
{
 node *head = NULL;
 node *ptr = head, *ptr_prev = head;

 for(int i=0; i<n; i++){
 if(i == 0){
 head = (node*)malloc(sizeof(node));
 head->data = i+1;
 head->next = head->prev = head;
 ptr_prev = head;
 }
 else{
 ptr = (node*)malloc(sizeof(node));
 ptr->data = i+1;
 ptr_prev->next = ptr;
 ptr->prev = ptr_prev;
 ptr_prev = ptr;
 }
 }
 ptr->next = head;
 head->prev = ptr;
 return head;
}

void display(node *head)
{
 node *ptr = head;
 do{
 printf("%d-> ", ptr->data);
 ptr = ptr->next;
 }while(ptr != head);
 printf("\b\b\b \n");
}

void display_rev(node *head)
{
 node *ptr = head;
 do{
 printf("%d-> ", ptr->data);
 ptr = ptr->prev;
 }while(ptr != head);
 printf("\b\b\b \n");
}

int josephus(node *head, int k)
{
 display(head);
 node *ptr = head;
 if(ptr->next == head)
 return ptr->data;
 
 node *todel=ptr, *todel_prev = todel->prev;
 for(int i=1; i< k; i++){
 todel_prev = todel;
 todel = todel->next;
 }
 node *new_head = todel->next;
 new_head->prev = todel_prev;
 todel_prev->next = new_head;
 
 free(todel);
 return josephus(new_head, k);
}

int main()
{
 node *head = NULL;
 int n, k;

 printf("Enter n: ");
 scanf("%d", &n);
 head = createDCLL(n);
 // display(head);
 // display_rev(head->prev);

 printf("Enter k: ");
 scanf("%d", &k);
 printf("Survival: %d\n", josephus(head, k));
 return 0;
}