Josephus Problem Solution Code
This code is for implementing Josephus Problem using Circular Linked List. Actually Josephus problem is a concept of deleting node on counter basis.
If you take a counter of 3 for performing this problem then it will start by deleting the 3rd node starting from the head node, then and after the victim node(3rd node) will be counted from the next node of the last deleted node.
This process will be continuing until a single node is remaining.
For Such more codes click here and for video tutorial click here.
#include<stdio.h>
#include<stdlib.h>
typedef struct circular {
int val;
struct circular * next;
}
cir;
cir * create();
void disp(cir * );
cir * josephus(cir * , int);
void main() {
int ch, v, p;
cir * head;
while (1) {
printf("\n1) Create a circular linked list \n2) Display the circular linked list \n3) Josephus Problem \n4) Exit ");
printf("\nEnter your choice : ");
scanf("%d", &ch);
switch (ch) {
case 1: head = create();
break;
case 2: printf("\nValues in the circular linked list : ");
disp(head);
break;
case 3: printf("\nEnter the counter value for Josephus problem : ");
scanf("%d", & p);
head = josephus(head, p);
printf("\nThe last node remain untouched after solving the Josephus problem : %d ",head->val);
break;
case 4: exit(0);
default: printf("Wrong choice");
}
}
}
cir * create() {
cir * h = NULL, * ptr, * temp;
int v;
while (1) {
printf("Enter the value for the node (0 to exit) : ");
scanf("%d", &v);
if (v == 0)
return h;
temp = (cir * ) malloc(sizeof(cir));
temp -> val = v;
if (h == NULL)
h = temp;
else
ptr -> next = temp;
ptr = temp;
temp -> next = h;
}
}
void disp(cir * h) {
cir * ptr;
ptr = h;
while (ptr -> next != h) {
printf("%d,", ptr -> val);
ptr = ptr -> next;
}
printf("%d", ptr -> val);
}
cir * josephus(cir * h, int p) {
cir * ptr, * pre;
int i;
ptr = h;
while (ptr -> next != ptr) {
i = 1;
while (i < p) {
pre = ptr;
ptr = ptr -> next;
i++;
}
ptr = pre -> next = ptr -> next;
}
return ptr;
}
