Hi
I am writing a program of Josephus problem in which each player kills next player and the person which is left is winner.
For Example, for 5 players
1 -- 2 -- 3 -- 4 -- 5
Starting with 1, 1 kills 2
1 -- 3 -- 4 -- 5
3 kills 4
1 -- 3 -- 5
5 kills 1
3 -- 5
3 kills 5
3
So winner is 3.
Here's my Program, I use Circular Doubly Linked List:
Code:
#include <stdlib.h>
struct node
{
int data;
struct node *addrs_next, *addrs_prev;
}*start = NULL, *end = NULL, *new1, *free_me;
void insert_end();
void delete_next();
void display();
void main()
{
int i;
printf(" \n\n\t-- Russian Roulette -- \n\n");
new1 = (struct node*) malloc(6);
start = new1;
end = new1;
start -> addrs_next = start;
start -> addrs_prev = start;
start -> data = 1;
for (i=2; i<11; i++)
insert_end(i);
display();
printf("\tPlayers are ready, Press aky key to start killing ...\n\n");
getch();
while (start != end)
{
delete_next();
new1 = new1 -> addrs_next;
display();
getch();
}
printf("Winner: %d", start->data);
}
void delete_next()
{
if(new1 == end->addrs_prev)
end = end -> addrs_prev;
else if (new1 == end)
start = start -> addrs_next;
free_me = new1 -> addrs_next; // addrs bkp for free()
new1 -> addrs_next = new1 -> addrs_next -> addrs_next; // change addrs_next
new1 = new1 -> addrs_next; // advance new1
new1 ->addrs_prev = new1 ->addrs_prev ->addrs_prev; // change addrs_prev
new1 = new1 -> addrs_prev; // reset new1
free(free_me);
}
void insert_end(int value)
{
new1 = (struct node*) malloc(4);
end -> addrs_next = new1;
new1 -> addrs_prev = end;
start -> addrs_prev = new1;
new1 -> addrs_next = start;
end = new1;
end -> data = value;
}
void display()
{
int run = 1;
printf("\n\tList:\n\n\t");
if( start == NULL || end == NULL)
return;
for(new1 = start; run; new1 = new1->addrs_next)
{
if (new1->addrs_next == start)
run = 0;
printf("%d ", new1->data);
}
printf("\n");
}
But there is something wrong here, the change in new1 not done globally. I mean, if i set new1 = new1 -> addrs_prev in delete_next(), main() does not show this change.
PS: *.c file attached
RR_BKP.c