## Search This Blog

Simplicity is the ultimate sophistication.” — Leonardo da Vinci
Contact me: sreramk360@gmail.com

## Friday 27 March 2015

### Program to implement the solution of josephus problem in a form of a game: using circular liked list.

Program to implement the solution of Josephus problem in a form of a game:  using circular liked list

/*
* Program to implement the solution of josephus problem in a form of a game
* using circular liked list.
*/

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

enum BOOL {FALSE, TRUE};
typedef int BOOL;
struct NODE_dc;
typedef struct NODE_dc Node_dc;
typedef Node_dc* PtrNode_dc;
typedef PtrNode_dc List_dc;
typedef PtrNode_dc Position_dc;

struct Player{
int index;
char name[50];
};
typedef struct Player DataType; // this is a default data type

struct NODE_dc{ // single link list node
DataType data;
PtrNode_dc next;
PtrNode_dc previous;
};

PtrNode_dc NewList_dc() // returns the List's header
{
PtrNode_dc tempNode =  malloc(sizeof(Node_dc));
tempNode->next = NULL;
tempNode->previous = NULL;
return tempNode;
}
Position_dc NewNode_dc()
{
return malloc(sizeof(Node_dc));
}

void Delete_dc(PtrNode_dc node)
{
free(node);
}
//***************************************************

void DeleteNode_dc(List_dc L, Position_dc pos)
{
if(pos == NULL)
{
fprintf(stderr, "error: in function DeleteNode, value of pos is NULL");
return;
}
if(pos->next == pos) //i.e., previous position is equal to itself. this shows that there is only one node in the list
{
Delete_dc(L->next);
L->next = NULL;
return;
}
if(L->next == pos)
L->next = pos->next;
pos->previous->next = pos->next;
pos->next->previous = pos->previous;
Delete_dc(pos);
}

void DeleteList_dc(List_dc L)
{
PtrNode_dc tempNode = L->next, tempNode2;
L->next->previous->next = NULL;// converts a circular list to a linear list
while (tempNode != NULL)
{
tempNode2 = tempNode->next;
Delete_dc(tempNode);
tempNode = tempNode2;
}
L->next = NULL;
}
BOOL IsLast_dc(List_dc L, Position_dc pos)
{
return (pos->next == L->next); // circular list links back to the first node and not the header
}
BOOL IsEmpty_dc(List_dc L)
{
return (L->next == NULL); // holds good even here
}
void Insert_dc ( List_dc L, DataType data, Position_dc pos)
{
Position_dc tempPos;
tempPos = NewNode_dc(); // creates and allocates memory space
if(tempPos == NULL)
{
fprintf(stderr, "error: request for allocation of memory using function \"malloc\" rejected");
return;
}

tempPos->data = data;
if(IsEmpty_dc(L))// a special case is required when the list is empty
{
L->next = tempPos;
tempPos->previous = tempPos->next = tempPos; // the node does not connects back to the header
return;
}
tempPos->next = pos->next;
tempPos->previous = pos->next->previous;
pos->next = pos->next->previous->next = tempPos;
tempPos->next->previous = tempPos;
}
void DisplayElement_dc(DataType element)
{
printf("\n %d - %s", element.index, element.name);
}
void Display_dc (List_dc L)
{

Position_dc pos = L;
if(IsEmpty_dc(L))
return;
do{
pos = pos->next;
DisplayElement_dc(pos->data);
}while (!IsLast_dc(L, pos));
}
BOOL solveStep (List_dc L,int eleminateNo)
{
int i;
if(L->next == L->next->next)
{
printf("\n\n\n\tthe winner is!!!!!!!!!!: ");
DisplayElement_dc(L->next->data);
return TRUE;
}
for(i=0; i<eleminateNo; i++)
L->next = L->next->next;
printf("\n the eliminated player is: ");
DisplayElement_dc(L->next->data);
DeleteNode_dc(L, L->next);
return FALSE;
}
DataType getElement(int* index)
{
DataType d;
printf("\nenter the name of the player:");
fflush(stdin);
gets(d.name);
d.index  = ++(*index);
return d;
}
int main()
{
List_dc  L = NewList_dc();
Position_dc top = L;
char ch = '\0';  int index = 0, n;
printf("\n\n\t welcome to the \"pass the message for n times game\" !!! ");
printf("\n enter the value n:");
scanf("%d", &n);
while(ch != 'N')
{
Insert_dc(L, getElement(&index), top);
if(index >=3 )
{
printf("do you want to add more members?(Y/N)");
scanf("%c", &ch);
}
}
while(solveStep(L, n )) getch();
getch();
DeleteList_dc(L);
free(L);
return 0;
}

copyright (c) 2015 K Sreram.