Recursive Search

[AsheeG87]

Hello Everyone!
I have a linked list and am trying to include a recursive search.
However, I am having trouble understanding how I would go about that.
I don't quite understand a recursive search....would any of you be so
kind to explain it to me...maybe include some examples.

I would GREATLY appreciate it!!!

 

[Gianni Mariani]

Hello Everyone!
I have a linked list and am trying to include a recursive search.
However, I am having trouble understanding how I would go about that.
I don't quite understand a recursive search....would any of you be so
kind to explain it to me...maybe include some examples.

What do you know about "recursive" functions ?

 

[AsheeG87]

What do you know about "recursive" functions ?

*****
I know that recursive functions are used in sorting and you can use
recursive functions to add a collection of values. Such as adding the
fibonacci sequence.

 

[Gianni Mariani]

*****
I know that recursive functions are used in sorting and you can use
recursive functions to add a collection of values. Such as adding the
fibonacci sequence.

A linked list is one element and one linked list or the empty linked list.

Is that enough of a hint ?

 

[AsheeG87]

A linked list is one element and one linked list or the empty linked list.

Is that enough of a hint ?

****************************
Not really...

 

[Gianni Mariani]

****************************
Not really...

Try writing the data structure for a linked list and the outline of a
function. Once you have that think about how to operate on a linked
list like I described above i.e. an element and another linked list, or
the empty list.

 

[AsheeG87]

Try writing the data structure for a linked list and the outline of a
function. Once you have that think about how to operate on a linked
list like I described above i.e. an element and another linked list, or
the empty list.- Hide quoted text -

- Show quoted text -

Hmmm...ok. Here is what I have so far.
Here is the .cpp file:

#include <iostream>
using namespace std;
#include "List.h" // header file


template< typename NODETYPE>
List< NODETYPE >::List()
:firstPtr( 0 )
{
} // end default constructor

template< typename NODETYPE>
List< NODETYPE >::~List()
{
if ( !isEmpty() )//list is not empty
{
cout << "Destroying Nodes...\n";
ListNode< NODETYPE > *currentPtr = firstPtr;
ListNode< NODETYPE > *tempPtr;

while ( currentPtr != 0 ) //deletes nodes
{
tempPtr = currentPtr;
cout << tempPtr->Data << '\n';
currentPtr = currentPtr->nextPTR;
delete tempPtr;
}
}

//insert at front
template< typename NODETYPE>
void List< NODETYPE >::insertAtFront(const NODETYPE &value )
{
ListNode< NODETYPE > *newPtr = getNewNode( value ); //new node

if( isEmpty() ) //the list IS empty
firstPtr = lastPtr = newPtr;
else //if not empty
{
newPtr->nextPtr = firstPtr;
firstPtr = newPtr;
}
}

//insert at back
template< typename NODETYPE>
void List< NODETYPE >::insertAtBack(const NODETYPE &value )
{
ListNode< NODETYPE > *newPtr = getNewNode( value ); //new node

if( isEmpty() ) //the list IS empty
firstPtr = lastPtr = newPtr;
else //if not empty
{
lastPtr->nextPtr = newPtr;
lastPtr = newPtr;
}
}

//delete from front
template< typename NODETYPE>
bool List< NODETYPE >::removeFromFront(const NODETYPE &value )
{
if( isEmpty() )
return false; //unsuccessful delete
else
{
ListNode< NODETYPE > *tempPtr = firstPtr;

if (firstPtr == lastPtr )
firstPtr = lastPtr = 0; //no more nodes
else
firstPtr = firstPtr->nextPTR;
value = tempPtr->data;
delete tempPtr;
return true; //successful delete
}
}

//delete from back
template< typename NODETYPE>
bool List< NODETYPE >::removeFromBack( NODETYPE &value )
{
if( isEmpty() )
return false;
else
{
ListNode< NODETYPE > *tempPtr = lastPtr;
if (firstPtr == lastPtr )
firstPtr = lastPtr = 0;
else
{
ListNode< NODETYPE > *currentPtr = firstPtr;

//locate second-to-last element
while ( currentPtr->nextPtr != lastPtr )
currentPtr = currentPtr->nextPtr; //move to next node

lastPtr = currentPtr; //remove last node
currentPtr->nextPtr = 0; //becomes the last node
}

value = tempPtr->data; //return value from old last node
delete tempPtr; //reclaim former last node
return true; //delete successful
}
} //ends removeFromBack function

//is list empty?
template< typename NODETYPE >
bool List< NODETYPE >::isEmpty() const
{
return firstPtr == 0;
}//end isEmpty function

//return pointer
template< typename NODETYPE >
ListNode< NODETYPE > *List< NODETYPE >::getNewNode(const NODETYPE
&value )
{
return new ListNode< NODETYPE >( value );
}//end getNewNode

//display list
template< typename NODETYPE >
void List< NODETYPE >:rint() const
{
if ( isEmpty() )
{
cout << "The list is empty\n\n";
return;
}
ListNode< NODETYPE > *currentPtr = firstPtr;

cout << "The list is: ";

while ( currentPtr != 0 ) //get element data
{
cout << currentPtr->data << ' ';
currentPtr = currentPtr->nextPtr;
}

cout << "\n\n";
}

int main()
{
List();
void insertAtFront(5);
void insertAtFront(4);
int list;


}//end main

 

[Gianni Mariani]

Hmmm...ok. Here is what I have so far.
Here is the .cpp file:

What do you want your search function signature to look like ?

 

[AsheeG87]

What do you want your search function signature to look like ?- Hide quoted text -

- Show quoted text -

See...that is what I am very confused on. I just don't get it.

 

[Daniel T.]

I have a linked list and am trying to include a recursive search.
However, I am having trouble understanding how I would go about that.
I don't quite understand a recursive search....would any of you be so
kind to explain it to me...maybe include some examples.

I would GREATLY appreciate it!!!

I strongly suggest you use a loop instead of a recursive function. If
you have to make a recursive function because this is homework, then
write the looping version and convert it.

Here's a typical loop.

for ( <init> ; <cond> ; <update> )
<body>

This can be converted to two functions: the main function and the helper
recursive function.

recFunc() {
loopVar = <init>
recHelperFunc( loopVar );
}

recHelperFunc( loopVar ) {
if ( <cond> ) {
<body>
<update>
recHelperFunc( loopVar ); // recursive call
}
}

 

[Alf P. Steinbach]

* (e-mail address removed):

Hmmm...ok. Here is what I have so far.
Here is the .cpp file:

#include <iostream>
using namespace std;
#include "List.h" // header file


template< typename NODETYPE>
List< NODETYPE >::List()
....

int main()
{
List();

This should not compile.

First of all you need a list that works. std::list works.

If what you're interested in is writing a recursive function that
traverses a list, try to do that using std::list.

Then when you get that function to /work/, you can try it using your own
list.

Action list: (1) make function that works, using std::list, (2) make
your own list work, getting rid of template stuff and other stuff you
don't really know, and (3) adapt function to work with your own list.

Hth.,

- Alf

 

[Gianni Mariani]

See...that is what I am very confused on. I just don't get it.

Ah.

In general you need to know what you're searching for so something like
this would be the entry point:


iterator SearchEqual(const NODETYPE &value )
{
return SearchNodes( firstPtr, value );
}


iterator SearchEqualNodes(Node * ptr, const NODETYPE &value )
{
if ( ptr )
{
if ( value == ptr->Value )
{
return iterator( ptr );
}

return SearchNodes(ptr->nextPtr(), value );
}

return end();
}