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
