Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Circular Link List program doesn't run

Reply
Thread Tools

Circular Link List program doesn't run

 
 
Maxx
Guest
Posts: n/a
 
      09-27-2011
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[i]=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[i]=l->item;


}


l=walk(l,x);

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

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..
 
Reply With Quote
 
 
 
 
Fred
Guest
Posts: n/a
 
      09-27-2011
On Sep 27, 10:46*am, Maxx <(E-Mail Removed)> 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[i]=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[i]=l->item;
>
> * * * * }
>
> * * * * l=walk(l,x);
>
> * * * * for(i=0;buff[i]!=9999;i++,l=l->next)
> * * * * {
> * * * * * * * * l->item=buff[i];
> * * * * }
> * * * * for(;l->next!=l;i++,l=l->next)
> * * * * {
> * * * * * * * * l->item=buff[i];
> * * * * }
>
> }
>
> 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
 
Reply With Quote
 
 
 
 
Ben Bacarisse
Guest
Posts: n/a
 
      09-27-2011
Maxx <(E-Mail Removed)> 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.
 
Reply With Quote
 
Ike Naar
Guest
Posts: n/a
 
      09-28-2011
On 2011-09-27, Fred <(E-Mail Removed)> wrote:
> On Sep 27, 10:46?am, Maxx <(E-Mail Removed)> 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.
 
Reply With Quote
 
Ben Bacarisse
Guest
Posts: n/a
 
      09-28-2011
Ike Naar <(E-Mail Removed)> writes:

> On 2011-09-27, Fred <(E-Mail Removed)> wrote:
>> On Sep 27, 10:46?am, Maxx <(E-Mail Removed)> 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.
 
Reply With Quote
 
James Kuyper
Guest
Posts: n/a
 
      09-28-2011
On 09/28/2011 03:18 AM, Ike Naar wrote:
> On 2011-09-27, Fred <(E-Mail Removed)> wrote:
>> On Sep 27, 10:46?am, Maxx <(E-Mail Removed)> 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
 
Reply With Quote
 
Maxx
Guest
Posts: n/a
 
      09-28-2011
On Sep 27, 12:21*pm, Ben Bacarisse <(E-Mail Removed)> wrote:
> Maxx <(E-Mail Removed)> 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.
 
Reply With Quote
 
Maxx
Guest
Posts: n/a
 
      09-28-2011
On Sep 28, 12:18*am, Ike Naar <(E-Mail Removed)> wrote:
> On 2011-09-27, Fred <(E-Mail Removed)> wrote:
>
> > On Sep 27, 10:46?am, Maxx <(E-Mail Removed)> 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
 
Reply With Quote
 
James Kuyper
Guest
Posts: n/a
 
      09-28-2011
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.
 
Reply With Quote
 
Phil Carmody
Guest
Posts: n/a
 
      10-03-2011
James Kuyper <(E-Mail Removed)> writes:
> On 09/28/2011 03:18 AM, Ike Naar wrote:
> > On 2011-09-27, Fred <(E-Mail Removed)> wrote:
> >> On Sep 27, 10:46?am, Maxx <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
iterating over a list as if it were a circular list Sven Python 3 03-08-2013 05:59 PM
iterating over a list as if it were a circular list Sven Python 1 03-07-2013 01:37 PM
Re: iterating over a list as if it were a circular list Chris Angelico Python 0 03-07-2013 09:28 AM
Problem in "+" operator.in doubly circular link list. Muzammil C++ 5 09-24-2008 12:14 AM
Semi-circular definitions (plus circular references) Kiuhnm C++ 16 01-03-2005 03:49 AM



Advertisments