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.
About my blog