Question

Write a C program that will use the circular doubly linked list.

X-Kingdom has trapped n number of soldiers of their opponent. They want to execute them. They found out a strategy so that the prisoners will kill each other and at the end one prisoner will be alive and he will be released. As part of the process, they labeled each trapped soldier a sequence number starting from 1 and ending at n. So, all the n number of prisoners standing in a circle waiting to be executed. However, one soldier was distracting the sequence and it was found out that they were standing in reverse order instead of proper order like the following (lets say n = 7): 7 -> 6-> 5-> 4 -> 3 -> 2-> 1 After realizing the wrong order of sequence, they reversed the circle to the correct order: 1 ->2-> 3-> 4 -> 5 -> 6-> 7 Now they will start the executing. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom. Given the total number of persons n and a number k which indicates that k-1 persons are skipped and kth person is killed in circle. The task is to choose the place in the initial circle so that you are the last one remaining and so survive. Example For example, if n = 5 and k = 2, then the safe position is 3. Firstly, the person at position 2 is killed, then person at position 4 is killed, then person at position 1 is killed. Finally, the person at position 5 is killed. So, the person at position 3 survives. If n = 7 and k = 3, then the safe position is 4. The persons at positions 3, 6, 2, 7, 5, 1 are killed in order, and person at position 4 survives. Input: n and k Output: Print the list of prisoners in reverse order from n to 1 Then reverse the list to print it in correct order from 1 to n Display the position number who will survive. Requirement: You must have to use circular doubly linked list for your solution. You need to declare appropriate doubly linked list node structure to store a soldier with sequence number as the data value. In addition to the other functions, you code must have to implement the following functions as use them part of the solution:

a. soldier* create_soldier (int sequence): It takes an integer, dynamically allocate a soldier structure and returns a soldier node

b. soldier* create_reverse_circle(int n): It takes an integer and create a circular doubly linked list with n number of soldiers placed them in descending sequence. For example, if n=5 it should produce a circular doubly linked list starting from 5 and ending at 1 as sequence number. After creating the circle, it returns the head of the circular linked list.

c. soldier* rearrange_circle(soldier* head): This function reverses a given circular doubly linked list where head is the head pointer. After reversing the linked list, it returns the head pointer of the updated linked list

d. void display(soldier* head): This function displays a given circular doubly linked list. head is head pointer of the linked list

e. int kill(soldier* head, int n, int k): This function takes head of the linked list, number of soldiers n, and skip value k as parameter and returns the sequence number of the survived soldier. So, this function is kind of perform the killing task based on specification discussed above.

Note that in addition to the above functions, you will utilize other linked list functions for insertion, deletion, and you may create more function as you need for your solution. During the killing process, there is no use of doubly part of the linked list. However, this part is mainly to exercise the implementation of doubly linked list

Please include comments

Answer 1

Answer:

C code explained below

Explanation:

#include <stdio.h>

#include <stdlib.h>

// Define a structure

typedef struct soldier{

struct soldier* prev;

struct soldier* next;

int data;

}soldier;

// Initialize count variable

int count=0;

// Define necessary variable

soldier *head, *lastnode;

// Define the necessary methods

soldier* create_soldier(int sequence);

soldier* create_reverse_circle(int n);

soldier* rearrange_circle(soldier* head);

void display(soldier* head);

int kill(soldier* head, int n, int k);

int main()

{

// Define two int variables

int n, k;

// Prompt user to enter number of soldiers

printf("Enter the number of soldiers: \n");

scanf("%d",&n);

// Prompt user to enter skips

printf("Enter number of skip: \n");

scanf("%d",&k);

// Display list of prisoners from n to 1

printf("Reverse Circle:\n");

// Call display() method with create_reverse_circle() method as its parameter

display(create_reverse_circle(n));

// Display the reverse list from 1 to n

printf("Rearranged circle:\n");

// Call display() method with rearrange_circle() method as its parameter

display(rearrange_circle(head));

// Display the soldier that survives

// Call the kill() method

printf("The soldier that survives: %d \n",kill(head, n, k));

}

// Define the create_soldier() method

soldier* create_soldier(int sequence)

{

// Declare necessary pointers

struct soldier* ptr,*temp;

// Dynamically allocate memory

ptr=(struct soldier*)malloc(sizeof(soldier));

// Check if pointer is null

if(ptr==NULL)

{

// Print overflow

printf("OVERFLOW");

}

else

{

// Assign ptr->data equal to sequence

ptr->data=sequence;

// Check if head is null

if(head==NULL)

{

// Assign head equal to ptr

head=ptr;

// Assign head to ptr->next

ptr->next=head;

// Assign head to ptr->prev

ptr->prev=head;

// Assign head to lastnode

// To keep track of the lastnode

lastnode=head;

}

else

{

// Assign head to temp

temp=head;

while(temp->next!=head)

{

// Assign temp->next to temp

temp=temp->next;

}

// Assign ptr to temp->next

temp->next=ptr;

// Assign temp to ptr->prev

ptr->prev=temp;

// Assign ptr to head->prev

head->prev=ptr;

// Assign head to ptr->next

ptr->next=head;

// Assign head equal to ptr

head=ptr;

}

// Increment count

count++;

}

// Return head

return head;

}

// Define the create_reverse_circle() method

soldier* create_reverse_circle(int n)

{

for(int i=1; i<=n; i++)

{

// Call the create_soldier() method

create_soldier(i);

}

// Return head

return head;

}

// Define the rearrange_circle() method

soldier* rearrange_circle(soldier* head)

{

// Declare the necessary pointers

soldier *temp_head, *temp_last;

// Assign temp_head equal to head

temp_head=head;

// Assign temp_last equal to lastnode

temp_last=lastnode;

// Declare necessary int variables

int value;

// Start a for loop to rearrange the list

for(int i=0; i<(count/2);i++)

{

// Assign temp_head->data to value

value=temp_head->data;

// Assign temp_last->data to temp_head

temp_head->data=temp_last->data;

// Assign value to temp_last->data

temp_last->data=value;

// Assign temp_head equal to next element

temp_head=temp_head->next;

// Assign temp_last equal to previous element

temp_last=temp_last->prev;

}

// Return head

return head;

}

// Define the display() method

void display(soldier* head)

{

// Declare the necessary variable

soldier* start;

// Assign start equal to head

start=head;

// Check if head is null

if(head==NULL)

{

// Print no values

printf("\n no values present! \n");

}

while(start->next!=head)

{

// Display start->data

printf("%d", start->data);

printf("->");

// Assign start equal to start->next

start=start->next;

}

// Print the last element

printf("%d \t \n",start->data);

}

// Define the kill() method

int kill(soldier* head, int n, int k)

{

// Declare the necessary pointer

struct soldier *ptr, *t;

// Initialize trace equal to zero

int trace=1;

// Assign ptr equal to head

ptr=head;

// Assign t equal to head

t=head;

// Initialize counter equal to 1

int counter=1;

while(counter<n)

{

// Check if head equal to null

if(head==NULL)

{

// Print underflow

printf("UNDERFLOW");

break;

}

else

{

trace=1;

while(trace<k)

{

// Assign ptr equal to t

ptr=t;

// Assign t equal to next element

t=t->next;

// Increment trace

trace++;

}

// Assign t->next to ptr->next

ptr->next=t->next;

// Assign ptr t->next->prev

t->next->prev=ptr;

free(t);

// Assign ptr->next to t

t=ptr->next;

}

// Increment counter

counter++;

}

// Assign head->data equal to ptr->data

head->data=ptr->data;

// Assign head->next equal to head

head->next=head;

// Assign head->prev equal to head

head->prev=head;

// Return head->data

return (head->data);

}