Jump to content
  • Advertisement
Sign in to follow this  
BaldPython

Recurisve LinkList Problem

This topic is 5089 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

Hello, I am studying Data Structures and Algorithms, and I've been ordained by the instructor to make a recursive LinkList ADT. Well, I am almost there but still having certain problems, like I am inserting digits from 0 to 10 in the list and i am getting an extra zero at the end of traversal() function. Can anyone please help me out, here's the code:

#include<iostream>
#include<cstdlib>
#include<cstring>

typedef struct node
{
	int 	data;
	node*	next;
}*List;

void initialize( List X )
{
	X->data = 0;
	X->next = NULL;
}

void initialize( List X , List Y )
{
	X->data = Y->data;
	X->next = Y->next;
}

int count( List X )
{
	if( X == 0 ) return 0;
	return ( 1 + count( X->next ));
}

void traverse( List L )
{
	if( L == 0 )
		return;
	else
		traverse( L->next );
		std::cout << L->data << std::ends ;
}

void traverse_reverse( List L )
{
	if( L->next == 0 ) return;
	std::cout << L->data << std::ends ;
	traverse_reverse( L->next );
}

void insert( List L , int value )
{
	List Temp = new node;
	if( Temp == NULL )
		std::cerr << "Out of Space" << std::endl;
	if( L == NULL )
		L = new node;
		
	Temp->data	= value;
	Temp->next	= L->next;
	L->next		= Temp;
}

void remove( List& L , int value )
{
	while( L != 0 && L->data == value )
	{
		List Tmp = L;
		L	 = L->next;
		delete[] Tmp;
	}
	
	if( L != 0 ) remove( L->next , value );
}

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

int main()
{
	List x = new node;
	initialize(x);
	for ( int i=0 ; i<=10 ;i++ )
		insert(x,i);
	std::cout << count(x) << std::endl;
	traverse(x);
	std::cout << std::endl;	
	traverse_reverse(x);
	std::cout << std::endl;	
	return 0;
}



[Edited by - BaldPython on November 30, 2005 4:07:52 PM]

Share this post


Link to post
Share on other sites
Advertisement
Does this actually compile? Specifically - List x = new node; from main(). Shouldn't that be List *x = new node();

Using the new operator implies your allocating memory on the heap which means using pointers.

Share this post


Link to post
Share on other sites
Quote:
Original post by vinb
Does this actually compile? Specifically - List x = new node; from main(). Shouldn't that be List *x = new node();

Using the new operator implies your allocating memory on the heap which means using pointers.


The code as written is fine, if not the most clear expression of the intent. Note the typedef struct{} at the top of the source file, which defines List as a pointer type rather than a value type. node is the name of the struct, and List has the type (node *).


BaldPython: in case you missed it, check your original "untitled" thread for a hint as to where your problem is coming from.

Share this post


Link to post
Share on other sites
Quote:
Original post by vinb
Does this actually compile? Specifically - List x = new node; from main(). Shouldn't that be List *x = new node();

Using the new operator implies your allocating memory on the heap which means using pointers.


yes it compiles...

because i havnt typedefined struct's pointer to be named as List, here's that part:


typedef struct node
{
int data;
node* next;
}*List;


Share this post


Link to post
Share on other sites
Quote:
Original post by ApochPiQ
BaldPython: in case you missed it, check your original "untitled" thread for a hint as to where your problem is coming from.


from the "untitled" thread:
Quote:
Original post by ApochPiQ
Think carefully about your insert() function and what it does when L is null.


Also, it isn't the source of your problem, but just an FYI: in your traverse() function your else clause is not formatted correctly. If an else block has multiple lines, they need to be surrounded by braces (the { and } characters). The code will work as it is currently, but only by pure luck.


insert() function ... I have checked it again, its alright.

and for the else clause, yes there's no difference either i put brakets or not, even if i remove 'else' it works the same ... :-

void traverse( List L )
{
if( L == 0 ) return;
traverse( L->next );
std::cout << L->data << std::ends;
}



All I could think of locating error now, is probably i suppose error lies in either initialize() function or traverse() function is moving one extra step. But still the count returns 12 entries including the extra zeros at start and end which is weird :(

Share this post


Link to post
Share on other sites
Quote:
Original post by ApochPiQ
Think carefully about your insert() function and what it does when L is null.


Quote:
Original post by BaldPython
insert() function ... I have checked it again, its alright.


.. no, not quite :) Check it again, and if you can, step through the code during debug. Otherwise, just jot down the values and whatnot on a piece of paper :)

Share this post


Link to post
Share on other sites
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.

Also, your traverse() code will definitely work the same by changing the else/brackets, but that's pure luck, as I said earlier. If you want to run multiple statements in an else block, you have to put them in braces.

Share this post


Link to post
Share on other sites
I think ApochPiQ has you covered on the errors you're asking about, but there are also some other unrelated errors in your code (the errors are coding errors, not data structure/algorithm errors so I assume it's OK to point them out to you):
  • You use the wrong form of delete in remove. delete what you new and delete[] what you new[]. Anything else is undefined behaviour.

  • List Temp = new node;
    if( Temp == NULL )
    std::cerr << "Out of Space" << std::endl;
    Unless you're using Visual C++ 6.0 or another compiler equally as decrepit Temp will never be NULL. The C++ Standard requires that new throws an exception of type std::bad_alloc (or derived from std::bad_alloc) if it is unable to allocate memory and returns a non-NULL pointer if it is able to allocate memory.

Enigma

Share this post


Link to post
Share on other sites
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.

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!