On Aug 9, 9:44 pm, Gianni Mariani <gi3nos...@mariani.wswrote:

Ashee...@msn.com wrote:
On Aug 9, 9:21 pm, Gianni Mariani <gi3nos...@mariani.wswrote:
Ashee...@msn.com wrote:

On Aug 9, 9:01 pm, Gianni Mariani <gi3nos...@mariani.wswrote:

Ashee...@msn.com wrote:

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 ?

*****

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 ?

****************************

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.- 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 >::print() 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