Recursion Revisited again, and again!

**clegs** · 12-05-2007

Should I post the ENTIRE code? That way you can look at everything?

**Elysia** · 12-05-2007

Doesn't hurt.

**clegs** · 12-05-2007

OK I will.
This is the class definition:

Code:

#ifndef H_OrderedListType
#define H_OrderedListType

#include <iostream>
#include "arrayListType.h"

using namespace std;

template<class elemType>
class orderedArrayListType: public arrayListType<elemType>
{
public:
	void insertOrd(const elemType&);
	
	int binarySearch(const elemType& item);

	int seqSearch(const elemType& item);

	orderedArrayListType(int size = 100);
private:
	int binarySearchImpl(const elemType& item, int first, int last);
};

template<class elemType>
void orderedArrayListType<elemType>::insertOrd(const elemType& item)
{
	int first = 0;
	int last = length - 1;
	int mid;

	bool found = false;

	if(length == 0)   //list is empty
    {
        list[0] = item;
        length++;
    }
	else
		if(length == maxSize)
			cerr<<"Cannot insert into a full list."<<endl;
		else
		{
			while(first <= last && !found)
			{
				mid = (first + last) / 2;

				if(list[mid] == item)
					found = true;
				else
					if(list[mid] > item)
						last = mid - 1;
					else
						first = mid + 1;
			}//end while

			if(found)
	   			cerr<<"The insert item is already in the list. "
					<<"Duplicates are not allowed.";
			else
			{
				if(list[mid] < item)
					mid++;

				insertAt(mid, item);
			}
		}
}//end insertOrd

template<class elemType> 
int orderedArrayListType<elemType>::binarySearch(const elemType& item)
{
	int first = 0;
	int last = length - 1;
	return binarySearchImpl(item, first, last);
}

//Function written for Test 5 Question 22
template<class elemType> 
int orderedArrayListType<elemType>::binarySearchImpl(const elemType& item, int first, int last)
{
	
	if(first >= last)
		return -1;
	int mid = (first + last) / 2;
	if(list[mid] == item)
		   return mid;
	if (list[mid] > item)
		return binarySearchImpl(item, first, mid - 1);
    else
		return binarySearchImpl(item, mid + 1, last);
}//end binarySearch

template<class elemType>
int orderedArrayListType<elemType>::seqSearch(const elemType& item)
{	
	for (int loc = 0; loc < length; loc++)
		if (list[loc] == item)
			return loc;
	return -1;
}//end seqSearch on ordered list

template<class elemType>
orderedArrayListType<elemType>::orderedArrayListType(int size)
   : arrayListType<elemType>(size)
{
}

#endif

This is the driver. Most of this code was source code from the text website. I only had to deal with changing the iterative binary search to a recursive function.
And then test it.

Code:

#include <iostream>

#include "orderedArrayListType.h"

using namespace std;

int main()
{
	orderedArrayListType<int> intList(10);			 			//Line 1

    int counter;											//Line 3
	int number;

    cout<<"Line 5: Processing the integer list"
		<<endl;												//Line 5
    cout<<"Line 6: Enter 5 integers (small to large): ";	//Line 6
										
    for(counter = 0; counter < 5; counter++)				//Line 7
    {	
		cin>>number;						 				//Line 8
		intList.insertAt(counter, number);		 			//Line 9
    }

    cout<<endl;												//Line 10
    cout<<"Line 11: The list you entered is: ";				//Line 11
    intList.print();										//Line 12
    cout<<endl;												//Line 13

	//using binarySearch function
	cout << "Enter a number to find in the list: ";
	int x;
	cin >> x;
	int pos1 = intList.binarySearch(x);
	if( pos1 == -1)
	{
		cout << "The number " << x << " was not found in: ";
		intList.print();
		cout<<endl;
	}
	else
	{
        cout << "The number " << x << " was found in: "; 
		intList.print();
		cout << "at position number: " << pos1 + 1 << endl;				
	}

    cout<<"Line 14: Enter the item to be deleted: ";		//Line 14
    cin>>number;											//Line 15
    intList.remove(number);									//Line 16
    cout<<"Line 17: After removing "<< number
		<<", the list is: ";								//Line 17
    intList.print();										//Line 18
    cout<<endl;												//Line 19

    int intListSize;										//Line 36

    cout<<"Line 37: Enter the size of the integer "
	  	 <<"list: ";						 				//Line 37
    cin>>intListSize;										//Line 38

    orderedArrayListType<int> intList2(intListSize);		//Line 39

    cout<<"Line 40: Processing the integer list"
	 	 <<endl;											//Line 40
    cout<<"Line 41: Enter "<<intListSize
	 	 <<" integers (small to large): ";					//Line 41

    for(counter = 0; counter < intListSize; counter++) 		//Line 42
    {
	 	 cin>>number;										//Line 43
	  	 intList2.insertAt(counter, number);		 		//Line 44
    }

    cout<<endl;												//Line 45
    cout<<"Line 46: The list you entered is: ";				//Line 46
    intList2.print();										//Line 47

	//using binarySearch function
	cout << "Enter a number to find in the list: ";
	int y;
	cin >> y;
	int pos2 = intList2.binarySearch(y);
	if( pos2 == -1)
	{
		cout << "The number " << y << " was not found in: ";
		intList2.print();
		cout<<endl;
	}
	else
	{
        cout << "The number " << y << " was found in: "; 
		intList2.print();
		cout << "at position number: " << pos2 + 1 << endl;				
	}
	cout << endl;												//Line 48
    return 0;
}

I really appreciate your help in this. I am going crazy!

**Elysia** · 12-05-2007

Just a note, but the base class is missing from your code.

**clegs** · 12-05-2007

Do you want me to post the parent? I can do that, but I thought this was way long as it is.

**clegs** · 12-05-2007

Base Class:

Code:

#ifndef H_arrayListType
#define H_arrayListType

#include <iostream>
#include <cassert>

using namespace std;

template <class elemType>
class arrayListType
{
public:
    const arrayListType<elemType>& operator=(const arrayListType<elemType>&);
		//Overload the assignment operator

    bool isEmpty();
		//Function to determine whether the list is empty
		//Postcondition: Returns true if the list is empty; 
 		//        	    otherwise, returns false.
    bool isFull();
		//Function to determine whether the list is full
		//Postcondition: Returns true if the list is full; 
 		//               otherwise, returns false.
    int listSize();
		//Function to determine the number of elements in the list
		//Postcondition: Returns the value of length.
    int maxListSize();
		//Function to determine the size of the list
 		//Postcondition: Returns the value of maxSize.
    void print() const;
		//Function to output the elements of the list
		//Postcondition: Elements of the list are output on the 
 		//               standard output device.
    bool isItemAtEqual(int location, const elemType& item);
		//Function to determine whether the item is the same 
 		//as the item in the list at the position specified by location
		//Postcondition: Returns true if the list[location] 
		//               is the same as the item; otherwise, 
		//		     returns false.
   void insertAt(int location, const elemType& insertItem);
		//Function to insert an item in the list at the 
		//position specified by location. The item to be inserted 
		//is passed as a parameter to the function.
		//Postcondition: Starting at location, the elements 
 		//               of the list are shifted down, 
 		//               list[location] = insertItem;, and
 		//               length++;    
 		//       If the list is full or location is out of
		//	   range, an appropriate message is displayed.    
   void insertEnd(const elemType& insertItem);
		//Function to insert an item at the end of the list 
		//The parameter insertItem specifies the item to be 
		//inserted.
		//Postcondition: list[length] = insertItem; and length++;
 		//               If the list is full, an appropriate 
		//               message is displayed.
    void removeAt(int location);
		//Function to remove the item from the list at the 
		//position specified by location 
		//Postcondition: The list element at list[location] is 
		//               removed and length is decremented by 1.
		//       If location is out of range, an appropriate message
		//       is displayed.
    void retrieveAt(int location, elemType& retItem);
		//Function to retrieve the element from the list at the  
		//position specified by location 
		//Postcondition: retItem = list[location] 
		//      If location is out of range, an appropriate 
		//      message is displayed.
    void replaceAt(int location, const elemType& repItem);
		//Function to replace the elements in the list at the 
		//position specified by location. The item to be replaced 
		//is specified by the parameter repItem.
		//Postcondition: list[location] = repItem 
		//      If location is out of range, an appropriate 
		//      message is displayed.
    void clearList();
		//Function to remove all the elements from the list 
		//After this operation, the size of the list is zero.
 		//Postcondition: length = 0;
    int seqSearch(const elemType& item);
  		//Function to search the list for a given item. 
		//Postcondition: If the item is found, returns the location 
		//               in the array where the item is found; 
   		//               otherwise, returns -1.
    void insert(const elemType& insertItem);
		//Function to insert the item specified by the parameter 
		//insertItem at the end of the list. However, first the
		//list is searched to see whether the item to be inserted 
		//is already in the list. 
		//Postcondition: list[length] = insertItem and length++
		//     If the item is already in the list or the list
		//     is full, an appropriate message is displayed.
    void remove(const elemType& removeItem);
		//Function to remove an item from the list. The parameter 
		//removeItem specifies the item to be removed.
		//Postcondition: If removeItem is found in the list,
		//      it is removed from the list and length is 
		//      decremented by one.

    arrayListType(int size = 100);
		//constructor
		//Creates an array of the size specified by the 
		//parameter size. The default array size is 100.
		//Postcondition: The list points to the array, length = 0, 
		//               and maxSize = size

    arrayListType(const arrayListType<elemType>& otherList); 
		//copy constructor

    ~arrayListType();
		//destructor
		//Deallocates the memory occupied by the array.

protected:
    elemType *list; 	//array to hold the list elements
    int length;		    //variable to store the length of the list
    int maxSize;		//variable to store the maximum size of the list
};



template <class elemType>
bool arrayListType<elemType>::isEmpty()
{
	return (length == 0);
}

template <class elemType>
bool arrayListType<elemType>::isFull()
{
	return (length == maxSize);
}

template <class elemType>
int arrayListType<elemType>::listSize()
{
	return length;
}

template <class elemType>
int arrayListType<elemType>::maxListSize()
{
	return maxSize;
}

template <class elemType>
void arrayListType<elemType>::print() const
{
	for(int i = 0; i < length; i++)
		cout<<list[i]<<" ";
	cout<<endl;
}

template <class elemType>
bool arrayListType<elemType>::isItemAtEqual
                   (int location, const elemType& item)
{
	return(list[location] == item);
}

template <class elemType>
void arrayListType<elemType>::insertAt
                   (int location, const elemType& insertItem)
{
	if(location < 0 || location >= maxSize)
		cerr<<"The position of the item to be inserted "
			<<"is out of range"<<endl;
	else
		if(length >= maxSize)  //list is full
			cerr<<"Cannot insert in a full list"<<endl;
		else
		{
			for(int i = length; i > location; i--)
				list[i] = list[i - 1];	//move the elements down

			list[location] = insertItem;	//insert the item at the 
 										//specified position

			length++;	//increment the length
		}
} //end insertAt

template <class elemType>
void arrayListType<elemType>::insertEnd(const elemType& insertItem)
{
	if(length >= maxSize)  //the list is full
		cerr<<"Cannot insert in a full list"<<endl;
	else
	{
		list[length] = insertItem;	//insert the item at the end
		length++;	//increment length
	}
} //end insertEnd

template <class elemType>
void arrayListType<elemType>::removeAt(int location)
{
	if(location < 0 || location >= length)
    	cerr<<"The location of the item to be removed "
			<<"is out of range"<<endl;
	else
	{
   		for(int i = location; i < length - 1; i++)
	 		list[i] = list[i+1];

		length--;
	}
} //end removeAt

template <class elemType>
void arrayListType<elemType>::retrieveAt
                     (int location, elemType& retItem)
{
	if(location < 0 || location >= length)
    	cerr<<"The location of the item to be retrieved is "
			<<"out of range"<<endl;
	else
		retItem = list[location];
} // retrieveAt

template <class elemType>
void arrayListType<elemType>::replaceAt
                    (int location, const elemType& repItem)
{
	if(location < 0 || location >= length)
    	cerr<<"The location of the item to be replaced is "
			<<"out of range"<<endl;
	else
		list[location] = repItem;

} //end replaceAt

template <class elemType>
void arrayListType<elemType>::clearList()
{
	length = 0;
} // end clearList

template <class elemType>
int arrayListType<elemType>::seqSearch(const elemType& item)
{
	int loc;
	bool found = false;

	for(loc = 0; loc < length; loc++)
	   if(list[loc] == item)
	   {
		found = true;
		break;
	   }

	if(found)
		return loc;
	else
		return -1;
} //end seqSearch

template <class elemType>
void arrayListType<elemType>::insert(const elemType& insertItem)
{
	int loc;

	if(length == 0)					 //list is empty
		list[length++] = insertItem; //insert the item and 
 									 //increment the length
	else
		if(length == maxSize)
			cout<<"Cannot insert in a full list."<<endl;
		else
		{
			loc = seqSearch(insertItem);

			if(loc == -1)   //the item to be inserted 
							//does not exist in the list
				list[length++] = insertItem;
			else
				cerr<<"the item to be inserted is already in "
 					<<"the list. No duplicates are allowed."<<endl;
	}
} //end insert

template <class elemType>
void arrayListType<elemType>::remove(const elemType& removeItem)
{
	int loc;

	if(length == 0)
		cerr<<"Cannot delete from an empty list."<<endl;
	else
	{
		loc = seqSearch(removeItem);

		if(loc != -1)
			removeAt(loc);
		else
			cout<<"The item to be deleted is not in the list."
				<<endl;
	}

} //end remove


template <class elemType>
arrayListType<elemType>::arrayListType(int size)
{
	if(size < 0)
	{
		cerr<<"The array size must be positive. Creating "
 			<<"an array of size 100. "<<endl;

 	   maxSize = 100;
 	}
 	else
 	   maxSize = size;

	length = 0;

	list = new elemType[maxSize];
	assert(list != NULL);
}



template <class elemType>
arrayListType<elemType>::~arrayListType()
{
	delete [] list;
}


	//copy constructor
template <class elemType>
arrayListType<elemType>::arrayListType
                   (const arrayListType<elemType>& otherList)
{
   maxSize = otherList.maxSize;
   length = otherList.length;
   list = new elemType[maxSize]; 	//create the array
   assert(list != NULL);	//terminate if unable to allocate
 							//memory space

   for(int j = 0; j < length; j++)  //copy otherList
 	   list [j] = otherList.list[j];
}//end copy constructor


template <class elemType>
const arrayListType<elemType>& arrayListType<elemType>::operator=
			(const arrayListType<elemType>& otherList)
{
	if(this != &otherList)	//avoid self-assignment
	{				   
	   delete [] list;				   
	   maxSize = otherList.maxSize;		   
       length = otherList.length;			   
	  
       list = new elemType[maxSize];		   
	   assert(list != NULL);			   

       for(int i = 0; i < length; i++)	   
	   	    list[i] = otherList.list[i];	   
	}

    return *this;					   	   
}


#endif

**Elysia** · 12-05-2007

Well, I'm trying to get an understand of how it works, but calls to the base class are present and I can't see them. You can attach the source file (or header) in case it's too long.

I also notice that you create a list of a size of 10:

Code:

orderedArrayListType<int> intList(10);

But you ask and insert 5 numbers.

**clegs** · 12-05-2007

Yea, Everything other than the two calls in the driver and the rewrite of the binarySearch is all from the textbook source code.

**Elysia** · 12-05-2007

I also notice that this class is kind of dangerous. I suggest you ONLY create a list big enough to hold all your numbers (ie, size = 5), and not more. It also seems more reasonable to use insert instead of insertAt, since you're just putting them in order.
If you don't set the size correctly, there's a small change you can get false answers (because of junk in the array).

**clegs** · 12-05-2007

I assumes that everything that was written was correct since it was from the author. Should set the default to 5 since that is what he wrote in the program to enter?
But, then the bottom call (there are two parts - one the list size is set the second the list size is set by the user).

**Elysia** · 12-05-2007

Where does the error occour? The first or second part?

**clegs** · 12-05-2007

In the driver, I change this:

orderedArrayListType<int> intList(5);

And I still get the upper and lower element not found.

**Elysia** · 12-05-2007

It looks fine to me (but there's probably some subtle bug somewhere that I'm just missing). I don't have a debugger here, but I'd love to debug this >_<
Someone else may help, I can't do it right now.

**clegs** · 12-05-2007

In the top part, if I enter 5 integers:
2 3 4 5 6
and ask to find 2 or 6 they aren't.
but the delete works no matter which number.

On the bottom part it doesn't find any number, no matter how big or small I define the list. And no matter which number I ask to find.

**clegs** · 12-05-2007

Well, I think I have to leave it alone, it is almost 4am and I need to get up at 5 to get ready for work. I may stay up and keep playing with the code to see if I can come up with something. But, I will leave the board and hope a miracle happens tomorrow morning.
I won't be able to visit the board while at work, but I will check it when I get home tomorrow evening.

Thanks for your time and help Elysia, and Mats, and iMalc.
I haven't put this one to bed yet, but I would love to.

Thread: Recursion Revisited again, and again!

Thread Tools

Search Thread

Display