Jump to content
  • Advertisement
Sign in to follow this  
BaldPython

Recurisve LinkList Problem

This topic is 4880 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Quote:
Original post by the_dannobot
I can see a few problems with your code. First is the recursion in your traverse and reverse_traverse functions, which are actually doing the opposite of what they say. Since you recurse first and then print, your traverse function is going to the end of your list and printing it in reverse order. The reason it looks like they are being printed in order is because your insert function is not appending nodes to the end of the list, it is inserting them behind the head. So if you insert:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
it outputs:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0
but the actual linked list in memory is ordered:
0, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
The reason there is a 0 at the end of the output is because of the way you initialize the X->data value in the initialize() function.


Yes, i know but i cannot remove it, because if i don't initialize X->data then the program displays junk values at its place. Even my count() function is getting unbalanced due to that zero.

Quote:
Original post by ApochPiQ
Try walking through your insert() code by hand and writing down all of the variables and their values, including the nodes that you create. Do that for the initialization loop from your main() function, and it should become clear what's going on.


Probably, you mean that the when i reach to last node a new node is been allocated, and this is probably you what you were trying to tell me, but its a circular list, so there's no zero in list, unless it reaches the first element.

Share this post


Link to post
Share on other sites
Advertisement
In your count(), traverse() and traverse_reverse() functions change

if (L == 0)
.
.
.

to

if (L == NULL)
.
.
.

I could be wrong.. it's been a LONG time since I've had to mess with pointers but I know it was drummed into me to check NULL not 0.

On paper it should work, traverse() giving the output 10 9 8 7 6 5 4 3 2 1 0.

traverse_reverse() has a bug where it SHOULD only print 0 1 2 3 4 5 6 7 8 9. It should skip 10 because 10's node->next is null so it shouldn't get to the std::cout... line.

There IS a bug in your insert function if you pass in a NULL List value it'll create a new one and then link yet another one to it.


BTW, do you HAVE to use recursion? A simple while loop should suffice, but I suppose the point of the program is to teach you recursion.. recursion should almost never be used (not that I haven't used it as a quick way out of a problem.. but just that ONE time! =)

Share this post


Link to post
Share on other sites
Quote:
Original post by LiyonDR
I only get 11 for Count not the 12 you were mentioning.


Sorry! that's what it's been giving at: for ( int i=0; i<=10 ;i++ )

that was a mistake in the first post, i am editing it though. it should display count as 11 but displaying it as 12.

Share this post


Link to post
Share on other sites
I also notice that when you go to search you use the below

int rFind( List L , int value )
{
if( L->data != value || L->next == NULL ) return 0;
else
return 1 + rFind( L->next, value );
}

Are you sure you don't want it to be..

int rFind( List L , int value )
{
if( L->data != value && L->next == NULL ) return 0;
else
return 1 + rFind( L->next, value );
}

That way it will actually move to the next node and search, as it is now it seems it will always return 0. I didn't walk through too many times but it seems it will always return 0?

Share this post


Link to post
Share on other sites
the_dannobot caught the other bug in insert so change my answer to:

traverse should give: 1 2 3 4 5 6 7 8 9 10 0
traverse_reverse should give: 0 10 9 8 7 6 5 4 3 2 (not printing 1)

=)

Share this post


Link to post
Share on other sites
If you're implementing a circular linked list, you need to keep track of the head pointer so the list itself knows where the circle begins and ends. (Either that, or your individual traversal functions need to check for the original starting node and stop traversing when it is reached.) If you're implementing a vanilla linked list, your tail node needs to have a NULL next pointer, not a pointer to an allocated-but-empty node.

Share this post


Link to post
Share on other sites
Quote:
Original post by that1guy
traverse_reverse() has a bug where it SHOULD only print 0 1 2 3 4 5 6 7 8 9.


No! sir, the last element of list is 10, So it should print it too ...

Quote:

It should skip 10 because 10's node->next is null so it shouldn't get to the std::cout... line.


Quote:

There IS a bug in your insert function if you pass in a NULL List value it'll create a new one and then link yet another one to it.


its a circular list, hence the new list is only allocated if List L is NULL( if no place is allocated to it. )

Quote:

BTW, do you HAVE to use recursion? A simple while loop should suffice, but I suppose the point of the program is to teach you recursion.. recursion should almost never be used (not that I haven't used it as a quick way out of a problem.. but just that ONE time! =)


yes! i know, it's alot easier by iterative approach, and yes it is to teach us recursion and that's why it's must work through recursion.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Did your instructor say you could ask random people on the internet for help? I thought no HW questions were allowed on GD'net.

Share this post


Link to post
Share on other sites
After further testing the rFind function, my proposed resolution doesn't resolve anything properly and unfortunately I don't have more time to step through it. So the && doesn't work right either, but it does cause it to check the next node.

The || will cause it to return only 0 unless you pass it the value at the start of the list, as an && seems to work if you pass it the value at the end of the list.

Probably not too helpful but if you look into that more you should be able to fix it.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
Did your instructor say you could ask random people on the internet for help? I thought no HW questions were allowed on GD'net.


well, if so ... then i request Fruny to lock this thread. Thank you...

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!