hello, I am trying to write this code to solve the josephus problem.
All I am getting is Segmentation Fault(coredump)? i am assuming its something to do with me using calloc but i cant tell what i've done wrong? any suggestions? thanks!

``````/*program to give solution of josephus problem using linear linked list*/
#include <stdio.h>
#include <stdlib.h>

struct player{
int pnumb;
struct player *next;
}player;

int main(void)
{
struct player *firstplayer, *current_player, *victim; /*define pointers*/
int k, n;    /*define constants */
int i, j;    /*iterative counters*/

/*input n and k from user*/
printf("enter number of people in circle:  ");
scanf("%d",&n);
printf("enter k:  ");
scanf("%d",&k);

firstplayer = current_player = (struct player*)calloc(1, sizeof(struct player));
if(!firstplayer){
printf("failed to allocate memory(1)...exiting.n");
exit(1);
}
/*create circle*/
for(i=0; i<(n-2); i++){
current_player=current_player->next=(struct player *)calloc(1, (sizeof(struct player)));
if(!current_player){
printf("failed to allocate memory(2)...exiting.n");
exit(2);
}
}

while((sizeof(struct player)) > 1){
for (j=0; j<k;j++){   /*count k-1 places around circle*/
current_player = current_player->next;
}

current_player = current_player->next = victim; /*victim is kth player*/

while(current_player == victim){  /*eject victim by going to next player*/
printf("victim is in position %d", victim->pnumb);
free(victim);
current_player = current_player->next;
}
}

printf("last player is in position %d", current_player->pnumb);

free(firstplayer);
return 0;
}``````

## All 4 Replies

Segmentation faults come from trying to access memory that you don't own. In a linked list, this would be trying to dereference a null pointer, or access an invalid pointer.

>current_player = current_player->next = victim;
Hey look, and invalid pointer! You forgot to initialize victim.

well, i learn something new every day.

The problem is named after Flavius Josephus, a Jewish historian living in the 1st century.

According to Josephus' account of the siege of Yodfat, he and his 40 comrade soldiers were trapped in a cave, surrounded by Romans. They chose suicide over capture and decided that they would form a circle and start killing themselves using a step of three.

Josephus states that by luck, or maybe by the hand of God, he and another man remained the last and gave up to the Romans.

``````while((sizeof(struct player)) > 1)
{
for (j=0; j<k;j++)
{   /*count k-1 places around circle*/
current_player = current_player->next;
}``````

I dont really understand the logic here? Thats is gonna get into an infinite loop! You need to have a proper condition for while to exit.

-ssharish

I dont really understand the logic here? Thats is gonna get into an infinite loop!

i believe you're right. she's trying to find when there's only one player left, but that isnt how to do it. the size of the structure is constant and greater than 1... i think the end condition should be when the current player's 'next' field points back to the current player.

but i believe narue called the source seg fault: the non allocated pointer.

i'm also suspicious of the line 29. i think the for condition should be `i<(n-1)` : the number of players, minus the 'first player' that was already allocated. But in any event, that's not related to the seg fault.

.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.