#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;
}
Recurisve LinkList Problem
Author
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:
[Edited by - BaldPython on November 30, 2005 4:07:52 PM]
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.
Using the new operator implies your allocating memory on the heap which means using pointers.
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.
Author
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;
Author
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 :(
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 :)
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.
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.
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):
Enigma
- You use the wrong form of delete in remove. delete what you new and delete[] what you new[]. Anything else is undefined behaviour.
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.List Temp = new node;if( Temp == NULL ) std::cerr << "Out of Space" << std::endl;
Enigma
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
