Should I post the ENTIRE code? That way you can look at everything?
Printable View
Should I post the ENTIRE code? That way you can look at everything?
Doesn't hurt.
OK I will.
This is the class definition:
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.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
And then test it.
I really appreciate your help in this. I am going crazy!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;
}
Just a note, but the base class is missing from your code.
Do you want me to post the parent? I can do that, but I thought this was way long as it is.
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
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:
But you ask and insert 5 numbers.Code:orderedArrayListType<int> intList(10);
Yea, Everything other than the two calls in the driver and the rewrite of the binarySearch is all from the textbook source code.
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).
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).
Where does the error occour? The first or second part?
In the driver, I change this:
orderedArrayListType<int> intList(5);
And I still get the upper and lower element not found.
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.
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.
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.