Public Group

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

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 on other sites
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 on other sites
Quote:
 Original post by vinbDoes 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 on other sites
Quote:
 Original post by vinbDoes 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 on other sites
Quote:
 Original post by ApochPiQBaldPython: in case you missed it, check your original "untitled" thread for a hint as to where your problem is coming from.

Quote:
 Original post by ApochPiQThink 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 on other sites
Quote:
 Original post by ApochPiQThink carefully about your insert() function and what it does when L is null.

Quote:
 Original post by BaldPythoninsert() 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 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 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 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 on other sites
I noticed the same as above, and I only get 11 for Count not the 12 you were mentioning.

• What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 14
• 11
• 28
• 15
• 41
• Forum Statistics

• Total Topics
634837
• Total Posts
3019559
×