2
\$\begingroup\$

I have written below code for the famous Josephus problem, or inky pinky ponky game, or many other names. Does this looks good or is there any loophole if anyone can highlight. I shall be looking forward to optimize it now as much as possible.

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

typedef struct ll_core
{
    int c_ll;
    struct ll_core * next;
} node_d;

node_d * create_c_list(int ,int);
void printList(node_d *);
node_d * elimination(node_d *, int);

int main(void)
{
    node_d *c_list;
    int n_kids,num;

    printf("How many kids? ");
    scanf("%d",&n_kids);
    printf("How many no. of words? ");
    scanf("%d",&num);

    node_d *first_kid=create_c_list(n_kids,num);    // create the circular list and get the pointer to first node/tail.
    printList(first_kid);

    node_d *victor=elimination(first_kid,num);      //returns pointer to the winner/last kid left
    printList(victor);
}

node_d * create_c_list(int n_k,int n_w)
{
    node_d *first=malloc(sizeof(node_d));
    int dat=1;
    first=malloc(sizeof(node_d));
    first->c_ll=dat;
    first->next=first;

    int iter=0;
    while(iter< n_k-1)
    {
        node_d * new_p=malloc(sizeof(node_d));
        new_p->next=first->next;
        first->next=new_p;                   /*We are not changing the node pointed to by tail pointer anywhere*/
        new_p->c_ll=++dat;
        iter++;
    }

    return first;
}

node_d * elimination(node_d * fix, int cntr)
{
    node_d *it=fix, *prev=fix;
    int iter;

    while(1)
    {
         for(iter=1;iter<cntr;iter++)
    it=it->next;                            /*This pointer is always on the node to be deleted. Once node is deleted, it points to the node from where
                                            from where counting is to start next.*/

    while(prev->next != it)
    prev=prev->next;                        // This always points to the node just before the one pointed to by pointer 'it'.

    //if(prev->next == it)
    prev->next=it->next;
    printf("removed : %d\n",it->c_ll);
    node_d *temp=it;
    free(temp);
    it=prev->next;

    if(it==it->next)
    break;
    }

    return it;
}

void printList(node_d *list_tail)
{
    node_d *p = list_tail->next;

    if(p->next==p)
    {
        printf("Only one element at %p: Value : %d  next : %p\n",p,p->c_ll,p->next);
     return;
    }

    while(p != list_tail)
    {
        printf("Value : %d   next : %p\n",p->c_ll,p->next);
        p=p->next;
    }

    if(p == list_tail)
    {
        printf("tail.. value : %d next : %p\n",p->c_ll,p->next);
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Your indentation is bad. It is inconsistent and makes it hard to read the code. Also adding comments at the end makes it hard to read the code. You could have placed it before the statements about which they are. Also not having braces around single statements can lead to problems later when you are editing the code and decide and add a statement but forget to add braces so you should use them even if they are optional. \$\endgroup\$ – Aseem Bansal Aug 20 '13 at 5:04
  • \$\begingroup\$ You could use a double linked list to avoid going through the whole circle to find the previous node in elimination. This is a memory/execution speed trade-off that I find sensible especially for long lists. \$\endgroup\$ – Andris Dec 11 '13 at 8:57
  • \$\begingroup\$ If possible I would use a linked list implementation from a standard library to avoid possible bugs from pointer handling. \$\endgroup\$ – Andris Dec 11 '13 at 9:07
2
\$\begingroup\$

Sorry, but I don't think this code is very good.

In create_c_list, the first node is allocated twice, leaking memory, and there are no checks for allocation failure. Parameters n_k and n_w are badly named and the latter is not used. The loop should be a for not while. new_p could just as well be n, for 'node'. Also, it is not obvious that the 'c' in the name means 'circular' and you should add spaces around operators ('=' etc).

In elimination, the function name should be a verb. The outer while(1) loop is often preferred as for (;;) , although that is a matter of personal preference. Indefinite loops are usually best avoided anyway.
Inside this loop is a for loop, which should define iter in the loop and call it i. Parameter cntr means nothing - it could be 'counter' of 'center'. Give it a better name. It derives from a value entered by the user called num which gives away no secrets, and the prompt was "How many no. of words?" - so num and cntr are the number of 'words', but the list created by create_c_list makes no mention of 'words'. It is as if you don't want the reader to understand what it does. The for loop locates the node according to the cntr, which takes a long time if cntr is zero, as the loops starts from 1. Then you do another loop, this time a while in which you find the list entry before the one (called it) that you located in the for loop. You could have combined the two loops. You then delete it using an unnecessary temporary variable.
And so the outer loop continues until there is only one entry in the list - that condition could have been the condition for the outer while loop.

In printList (which uses camelCase while create_c_list doesn't) you don't modify the list, so it should be passed const. Parameter list_tail is inaccurate - a circular list has no tail. Call it just list.

Also, putting main last avoids the need for prototypes, all functions except main should be static and the names of struct ll_core and c_ll would be better as struct node and value.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.