Answer to Question #262153 in C for Haider

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), the starting point (i), direction (clockwise/anti-clockwise), and number to be skipped (k).

Let’s take an example. • For n =15 (i.e. number of people is 15) • k = 2 (i.e. every 2nd person is killed) • starting point (i) = 1 • direction = clockwise

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

After 1 st iteration: 1 3 5 7 9 11 13 15

After 2nd iteration: 3 7 11 15

After 3rd iteration: 7 15

After 4th iteration: 15 (15 remains in the end). The program stops here.

please give the right as given in the question and also show your output.

Answer 1

#include <stdio.h>


struct Node {
    int x;
    struct Node* next;
    struct Node* prev;
};


struct Node* init(int x) {
    struct Node* node = (struct Node* ) malloc(sizeof(struct Node));
    node->x = x;
    node->next = node->prev = node;


    return node;
}


void insertAfter(int x, struct Node* node) {
    struct Node* new_node = (struct Node* ) malloc(sizeof(struct Node));
    struct Node* tmp = node->next;


    new_node->x = x;
    node->next = new_node;
    new_node->next = tmp;
    new_node->prev = node;
    new_node->next->prev = new_node;
}


struct Node* removeNode(struct Node* node, int direction) {
    struct Node* res;


    if (node->next == node) {
        return node;
    }
    if (direction) {
        res = node->next;
    }
    else {
        res = node->prev;
    }
    node->next->prev = node->prev;
    node->prev->next = node->next;
    free(node);


    return res;
}


void printList(struct Node* node) {
    struct Node* pEnd = node;


    printf("%d ", node->x);
    node = node->next;
    while (node != pEnd) {
        printf("%d ", node->x);
        node = node->next;
    }
    printf("\n");
}


int main() {
    struct Node* list = init(1);
    int n, k, direction, new_n, iter;


    printf("Enter number of people: ");
    scanf("%d", &n);


    for (int i=2; i<=n; i++) {
        insertAfter(i, list);
        list = list->next;
    }
    list = list->next;


    printf("Enter number to be skipped: ");
    scanf("%d", &k);
    printf("Enter 1 to go clockwise, 0 counterclockwise: ");
    scanf("%d", &direction);


    printf("Initial scenario ");
    printList(list);
    new_n = n;
    iter = 0;
    while (new_n > 1) {
        iter++;
        new_n = (n+1) / 2;
        while ( n != new_n ) {
            for (int i=1; i<k; i++) {
                if (direction) {
                    list = list->next;
                }
                else {
                    list = list->prev;
                }
            }
            list = removeNode(list, direction);
            n--;
        }


        new_n = n;
        printf("After %dth iteration: ", iter);
        printList(list);
    }
}