Circular Link List program doesn't run

M

Maxx

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..
 
F

Fred

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.
 
B

Ben Bacarisse

Maxx said:
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>
 
I

Ike Naar

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.
 
B

Ben Bacarisse

Ike Naar said:
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>
 
J

James Kuyper

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.
 
M

Maxx

Coursework?

not course work but i was learning link lists by myself and i came
across this problem..
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>

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.
 
M

Maxx

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
 
J

James Kuyper

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.
 
P

Phil Carmody

James Kuyper said:
[...]
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.
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
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,479
Members
44,900
Latest member
Nell636132

Latest Threads

Top