Circular Link List program doesn't run

Discussion in 'C Programming' started by Maxx, Sep 27, 2011.

  1. Maxx

    Maxx Guest

    I have this problem on circular link list which says to move nodes
    following t on the list to the node following x on the list. I have
    written this program and it also compiled with no errors, but its not
    running at all. I have tried a lot to solve this program but can't
    seem to make any headway.

    here is the program:::

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

    struct node
    {
    int item;
    struct node *next;
    };

    typedef struct node *link;

    link walk(link l,int v) /*to traverse a list pointed by l till node v
    */
    {

    while(l->next->item!=v)
    {

    l=l->next;
    }
    return l;
    }

    void shift(link l,int x,int t) /*to shift the contents of the list
    following t to positon following x on list */
    {
    int buff[30],i;

    l=walk(l,x);

    for(i=0; l->next->item!=t; i++)
    {
    l=l->next;
    buff=l->item;

    }buff[i++]=9999; /*used to mark the end of the conetents of the
    list following x till t*/

    for(;l->next!=l;i++)
    {
    l=l->next;
    buff=l->item;


    }


    l=walk(l,x);

    for(i=0;buff!=9999;i++,l=l->next)
    {
    l->item=buff;
    }
    for(;l->next!=l;i++,l=l->next)
    {
    l->item=buff;
    }
    }

    void init(link l,int n) /*to initialize a list with values till n */
    {
    int i=2;
    while(i<=n)
    {
    l=(l->next=malloc(sizeof *l));
    l->item=i;
    l->next=l;
    i++;

    }


    }
    void traverse(link l)
    {
    do
    {
    printf(" %d",l->item);
    l=l->next;
    }while(l->next!=l);
    }


    int main(int argc, char **argv)
    {
    int N=atoi(argv[1]), x=atoi(argv[2]), t=atoi(argv[3]);

    link l=malloc(sizeof *l);
    l->item=1;
    l->next=l;

    init(l,N);
    shift(l,x,t);

    traverse(l);

    return 0;
    }


    Please help, any solutions or hint would be very grateful..
     
    Maxx, Sep 27, 2011
    #1
    1. Advertising

  2. Maxx

    Fred Guest

    On Sep 27, 10:46 am, Maxx <> wrote:
    > I have this problem on circular link list which says to move nodes
    > following t on the list to the node following x on the list. I have
    > written this program and it also compiled with no errors, but its not
    > running at all. I have tried a lot to solve this program but can't
    > seem to make any headway.
    >
    > here is the program:::
    >
    > #include <stdio.h>
    > #include <stdlib.h>
    >
    > struct node
    > {
    >         int item;
    >         struct node *next;
    >
    > };
    >
    > typedef struct node *link;
    >
    > link walk(link l,int v)  /*to traverse a list pointed by l till node v
    > */
    > {
    >
    >         while(l->next->item!=v)
    >         {
    >
    >                 l=l->next;
    >         }
    >         return l;
    >
    > }
    >
    > void shift(link l,int x,int t) /*to shift the contents of the list
    > following t to positon following x on list */
    > {
    >         int buff[30],i;
    >
    >         l=walk(l,x);
    >
    >         for(i=0; l->next->item!=t; i++)
    >         {
    >                 l=l->next;
    >                 buff=l->item;
    >
    >         }buff[i++]=9999;    /*used to mark the end of the conetents of the
    > list following x till t*/
    >
    >         for(;l->next!=l;i++)
    >         {
    >                 l=l->next;
    >                 buff=l->item;
    >
    >         }
    >
    >         l=walk(l,x);
    >
    >         for(i=0;buff!=9999;i++,l=l->next)
    >         {
    >                 l->item=buff;
    >         }
    >         for(;l->next!=l;i++,l=l->next)
    >         {
    >                 l->item=buff;
    >         }
    >
    > }
    >
    > void init(link l,int n)   /*to initialize a list with values till n */
    > {
    >         int i=2;
    >         while(i<=n)
    >         {
    >                 l=(l->next=malloc(sizeof *l));
    >                 l->item=i;
    >                 l->next=l;
    >                 i++;
    >
    >         }
    >
    > }
    >
    > void traverse(link l)
    > {
    >         do
    >         {
    >                 printf(" %d",l->item);
    >                 l=l->next;
    >         }while(l->next!=l);
    >
    > }
    >
    > int main(int argc, char **argv)
    > {
    >         int N=atoi(argv[1]), x=atoi(argv[2]), t=atoi(argv[3]);
    >
    >         link l=malloc(sizeof *l);
    >         l->item=1;
    >         l->next=l;
    >
    >         init(l,N);
    >         shift(l,x,t);
    >
    >         traverse(l);
    >
    >         return 0;
    >
    > }
    >
    > Please help, any solutions or hint would be very grateful..



    Your init() method is flawed. For each new node, you set l->next=l
    so the final node's "next" pointer points to itself, not to the first
    node.
    --
    Fred K
     
    Fred, Sep 27, 2011
    #2
    1. Advertising

  3. Maxx <> writes:

    > I have this problem on circular link list which says to move nodes
    > following t on the list to the node following x on the list.


    Coursework?

    > I have
    > written this program and it also compiled with no errors, but its not
    > running at all. I have tried a lot to solve this program but can't
    > seem to make any headway.


    You've made some headway but I think you should slow down and build up
    from smaller bits. Start with init and traverse (both of which could be
    better named -- make_sequence and print_list maybe?). See if you can
    make these work first. Logically, init should be able to make a list
    with no elements and it certainly should not start at 2. Try printing
    an empty list, then one with a single element and so on. When you have
    these working in a rock-solid way you can move on the more complex
    parts.

    <snip code>
    --
    Ben.
     
    Ben Bacarisse, Sep 27, 2011
    #3
  4. Maxx

    Ike Naar Guest

    On 2011-09-27, Fred <> wrote:
    > On Sep 27, 10:46?am, Maxx <> wrote:
    >> [...]

    > Your init() method is flawed. For each new node, you set l->next=l
    > so the final node's "next" pointer points to itself, not to the first
    > node.


    It looks as if Maxx marks the end of the list with a node
    that links to itself, instead of using the more customary convention
    of letting the last node link to NULL.
    Although his method is unconventional, it is not wrong in itself,
    and I've seen situations where it works well.
    One drawback is that the list cannot be empty; that is probably
    the reason why Maxx initializes his list with a single element.
     
    Ike Naar, Sep 28, 2011
    #4
  5. Ike Naar <> writes:

    > On 2011-09-27, Fred <> wrote:
    >> On Sep 27, 10:46?am, Maxx <> wrote:
    >>> [...]

    >> Your init() method is flawed. For each new node, you set l->next=l
    >> so the final node's "next" pointer points to itself, not to the first
    >> node.

    >
    > It looks as if Maxx marks the end of the list with a node
    > that links to itself, instead of using the more customary convention
    > of letting the last node link to NULL.


    You maybe right, but I think it is more likely that it's an attempt to
    meet the specification gone wrong rather than a peculiar list design.
    The OP started:

    | I have this problem on circular link list

    so the link to itself is correct when there is one element.

    <snip>
    --
    Ben.
     
    Ben Bacarisse, Sep 28, 2011
    #5
  6. Maxx

    James Kuyper Guest

    On 09/28/2011 03:18 AM, Ike Naar wrote:
    > On 2011-09-27, Fred <> wrote:
    >> On Sep 27, 10:46?am, Maxx <> wrote:
    >>> [...]

    >> Your init() method is flawed. For each new node, you set l->next=l
    >> so the final node's "next" pointer points to itself, not to the first
    >> node.

    >
    > It looks as if Maxx marks the end of the list with a node
    > that links to itself, instead of using the more customary convention
    > of letting the last node link to NULL.


    Marking the last node with a link to NULL is the convention in a linear
    list, but the subject line says that this is supposed to be a circular
    linked list. A one-element circularly linked list should be linked to
    itself. However, it should not remain linked to itself after other
    elements are added to the list.

    > Although his method is unconventional, it is not wrong in itself,
    > and I've seen situations where it works well.
    > One drawback is that the list cannot be empty; that is probably
    > the reason why Maxx initializes his list with a single element.


    A circularly linked list can be pointed at by pointing at any element of
    the list; having that pointer be null is the way to indicate an empty list.
    --
    James Kuyper
     
    James Kuyper, Sep 28, 2011
    #6
  7. Maxx

    Maxx Guest

    On Sep 27, 12:21 pm, Ben Bacarisse <> wrote:
    > Maxx <> writes:
    > > I have this problem on circular link list which says to move nodes
    > > following t on the list to the node following x on the list.

    >
    > Coursework?
    >


    not course work but i was learning link lists by myself and i came
    across this problem..

    > > I have
    > > written this program and it also compiled with no errors, but its not
    > > running at all. I have tried a lot to solve this program but can't
    > > seem to make any headway.

    >
    > You've made some headway but I think you should slow down and build up
    > from smaller bits.  Start with init and traverse (both of which could be
    > better named -- make_sequence and print_list maybe?).  See if you can
    > make these work first.  Logically, init should be able to make a list
    > with no elements and it certainly should not start at 2.  Try printing
    > an empty list, then one with a single element and so on.  When you have
    > these working in a rock-solid way you can move on the more complex
    > parts.
    >
    > <snip code>
    > --
    > Ben.


    I started init with 2 cause the link list was declared earlier in
    main() and it only contained one item. So i thought to start the next
    item with 2 and initialize the list with the desired no of nodes. Yeah
    i was also thinking about starting from basics. This head pointer is
    giving me trouble and also the fact that my last node is pointing to
    itself instead of the first node on the list.
     
    Maxx, Sep 28, 2011
    #7
  8. Maxx

    Maxx Guest

    On Sep 28, 12:18 am, Ike Naar <> wrote:
    > On 2011-09-27, Fred <> wrote:
    >
    > > On Sep 27, 10:46?am, Maxx <> wrote:
    > >> [...]

    > > Your init() method is flawed. For each new node, you set l->next=l
    > > so the final node's "next" pointer points to itself, not to the first
    > > node.

    >
    > It looks as if Maxx marks the end of the list with a node
    > that links to itself, instead of using the more customary convention
    > of letting the last node link to NULL.
    > Although his method is unconventional, it is not wrong in itself,
    > and I've seen situations where it works well.
    > One drawback is that the list cannot be empty; that is probably
    > the reason why Maxx initializes his list with a single element.


    Thats the problem i'm facing i want the last node to point to the
    first node but its somehow its pointing to itself
     
    Maxx, Sep 28, 2011
    #8
  9. Maxx

    James Kuyper Guest

    On 09/28/2011 01:54 PM, Maxx wrote:
    ....
    > Thats the problem i'm facing i want the last node to point to the
    > first node but its somehow its pointing to itself


    Ask yourself one important question: "where in my code do I have a line
    that is supposed to cause the last node to be linked back to the first
    node?". The answer to that question should help you resolve that problem.
     
    James Kuyper, Sep 28, 2011
    #9
  10. Maxx

    Phil Carmody Guest

    James Kuyper <> writes:
    > On 09/28/2011 03:18 AM, Ike Naar wrote:
    > > On 2011-09-27, Fred <> wrote:
    > >> On Sep 27, 10:46?am, Maxx <> wrote:
    > >>> [...]
    > >> Your init() method is flawed. For each new node, you set l->next=l
    > >> so the final node's "next" pointer points to itself, not to the first
    > >> node.

    > >
    > > It looks as if Maxx marks the end of the list with a node
    > > that links to itself, instead of using the more customary convention
    > > of letting the last node link to NULL.

    >
    > Marking the last node with a link to NULL is the convention in a linear
    > list, but the subject line says that this is supposed to be a circular
    > linked list. A one-element circularly linked list should be linked to
    > itself.


    That's one way, but is not the linux implementation, for example. The
    list object (which is just a pointer or a pointer pair for doubly-linked
    lists) points to the first node, that node points back to the head object.

    > However, it should not remain linked to itself after other
    > elements are added to the list.


    That's certainly true.

    > > Although his method is unconventional, it is not wrong in itself,
    > > and I've seen situations where it works well.
    > > One drawback is that the list cannot be empty; that is probably
    > > the reason why Maxx initializes his list with a single element.

    >
    > A circularly linked list can be pointed at by pointing at any element of
    > the list; having that pointer be null is the way to indicate an empty list.


    For singly linked lists, almost always, but it doesn't have to be.
    The head object could point to itself, rather than at any nodes.
    In particular in linux' implementation, doubly-linked lists are always
    that way, with the list object pointing to itself in both directions.

    Phi
    --
    "Religion is what keeps the poor from murdering the rich."
    -- Napoleon
     
    Phil Carmody, Oct 3, 2011
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Kiuhnm
    Replies:
    16
    Views:
    750
    Jonathan Mcdougall
    Jan 3, 2005
  2. Muzammil
    Replies:
    5
    Views:
    358
    Muzammil
    Sep 24, 2008
  3. Sven
    Replies:
    1
    Views:
    156
    Roy Smith
    Mar 7, 2013
  4. Sven
    Replies:
    3
    Views:
    168
    Steven D'Aprano
    Mar 8, 2013
  5. Chris Angelico
    Replies:
    0
    Views:
    127
    Chris Angelico
    Mar 7, 2013
Loading...

Share This Page