Help regarding Josepheus problem.

[Rohini Ramamurthy]

Hi All,

I have taken up this problem to learn a bit in using linked lists.
I am trying a variant of it what it is supposed to so is delete the nth
person
clockwise and counter clockwise alternatively until last man is alive

I tried coding it.
I have completed it.
But i have a problem in my code.
The last man that shud live logically is not the result of my code.
I think i am making a small mistake in my logic cud not find it but.
Can u help.
Pls help soon.
I am attaching the code here.


The code is as follows



/****************************************************************************

This program creates a circular list of specified number of people and
then
eliminates one by one clockwise and counter clockwise until the last
one
element alone is in the list

****************************************************************************/




#include<stdio.h>
#include<stdlib.h>


typedef struct ppl_list
{
char name[20];
struct ppl_list *prev;
struct ppl_list *next;
}ppl_list;


struct ppl_list *FirstRec;
struct ppl_list *LastRec;
struct ppl_list *CurrElement, *PrevElement,*temp;
int i;
int pplnum,nthdel;


void insert(ppl_list*);
void display(ppl_list*);
void delete(ppl_list*);
void deleteorder(ppl_list*);
void moveclockwise(ppl_list*);
void moveanticlockwise(ppl_list*);


int main()
{

clrscr();
printf("\nEnter the number of ppl in the list\n");
scanf("%d",&pplnum);
printf("\nEnter the nth person to be removed\n");
scanf("%d",&nthdel);
FirstRec=(ppl_list*)malloc(sizeof(ppl_list));
printf("\nEnter the name of the first person\n");
scanf("%s",FirstRec->name);
FirstRec->next=(ppl_list*) malloc (sizeof(ppl_list));


insert(FirstRec);
display(FirstRec);
deleteorder(FirstRec);
display(FirstRec);



printf("\nThe list was created successfully\n");
getch();
}


void insert(ppl_list *FirstRec)

{

PrevElement=FirstRec;
for(i=1;i<pplnum;i++)
{

LastRec=PrevElement->next;
PrevElement->prev=LastRec;
printf("\nEnter the name of next person\n");
scanf("%s",LastRec->name);
LastRec->prev=PrevElement;
LastRec->next=(ppl_list*) malloc (sizeof(ppl_list));
PrevElement=LastRec;
}

LastRec->next=FirstRec;
}


void display(ppl_list *start)
{

PrevElement=start;
printf("\nThe elements in list are\n");
printf("1st is %s\n", PrevElement->name);
for(i=2;i<pplnum + 1;i++)
{

CurrElement=PrevElement->next;
printf("%dth is %s\n",i,CurrElement->name);
PrevElement=CurrElement;
}


}

void deleteorder(ppl_list* start)
{


while(pplnum >1)
{
CurrElement=start ;
moveclockwise(CurrElement);
delete(CurrElement);
pplnum--;
start=CurrElement->prev;

if(pplnum > 1)
{
CurrElement=start;
moveanticlockwise(CurrElement);
delete(CurrElement);
pplnum--;
start=CurrElement->next;
}
}
}

void delete(ppl_list* start)
{

CurrElement=start;
temp=CurrElement;
if(CurrElement == FirstRec)
{
FirstRec=CurrElement->next;
FirstRec->prev=LastRec;
}
else if(CurrElement == LastRec)
{
LastRec=CurrElement->prev;
LastRec->next=FirstRec;
}
else
{
CurrElement->prev->next=CurrElement->next;
CurrElement->next->prev=CurrElement->prev;
}
free(temp);
}

void moveclockwise(ppl_list* CurrElement)
{

for(i=1;i<=nthdel;i++)
{
CurrElement=CurrElement->next;
}


}

void moveanticlockwise(ppl_list* CurrElement)
{
for(i=1;i<=nthdel;i++)
{
CurrElement=CurrElement->prev;
}

}
Thanks in advance

regards
Rohini.

 

[Rohini Ramamurthy]

Hi guys..

I have solved the problem successfully..

I made a simple mistake wen i traced thru i spotted it and rectified..
Now its working fine..

regards
Rohini

 

[vcp]

Hi guys..

I have solved the problem successfully..

Congratulations !

I quickly had a look, just noticed that you are using pointers after
calling free on it.
See segment of your code below :

void deleteorder(ppl_list* start)
{

/* .................. */
delete(CurrElement);
pplnum--;
start=CurrElement->prev; /* WARNING : CurrElement is
freed. No? */

/* .................. */
}

void delete(ppl_list* start)
{

CurrElement=start;
temp=CurrElement;
/* .................. temp is not changing -------------- */
free(temp);

}

You are passing CurrElement and calling free on it, then using it to
access CurrElement->prev.

May be I missed something.

 

[Rod Pemberton]

Hi All,

I have taken up this problem to learn a bit in using linked lists.

That's nice, but do you know that you don't need linked lists to solve the
"Ring of Josephus?"

http://groups.google.com/group/comp.lang.c/msg/ad8b92ed90a5aab1?hl=en


Rod Pemberton