Answer to Question #254885 in C for Lucifer

Question

Learn more about at the Josephus Problem from the following links and make a Circular Doubly Linked List simulation of this problem. (Your program should print the remaining people in each iteration). C language programming. 1. https://www.youtube.com/watch?v=uCsD3ZGzMgE 2. https://github.com/alextop30/Josephus-Problem

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