The function removeAt of the class arrayListType removes an element from the lis
ID: 3854336 • Letter: T
Question
The function removeAt of the class arrayListType removes an element from the list by shifting the elements of the list. However, if the element to be removed is at the beginning of the list and the list is fairly large, it could tak a lot of computer time. Because the list elements are in no particular order, you could simply remove the element by swapping the last element of the list with the item to be removed and reducing the length of the list. Rewrite the definition of the function removeAt using this technique.
See program exercise 1 on page 204.
The function remove of the class arrayListType removes only the first occurrence of an element. Add the function removeAll to the class arrayListType that would remove all occurrences of a given element. Also, write the definition of the function removeAll and a program to test this function.
See programming exercises 2 on page 204
Write a program to test the functions, removeAt and removeAll.
c++
Explanation / Answer
arrayListType.h
#ifndef H_arrayListType
#define H_arrayListType
class arrayListType
{
public:
bool isEmpty() const;
bool isFull() const;
int listSize() const;
int maxListSize() const;
void print() const;
bool isItemAtEqual(int location, int item) const;
virtual void insertAt(int location, int insertItem) = 0;
virtual void insertEnd(int insertItem) = 0;
void removeAt( int location);
void retrieveAt(int location, int& retItem) const;
virtual void replaceAt(int location, int repItem) = 0;
void clearList();
virtual int seqSearch(int searchItem) const = 0;
virtual void remove(int removeItem) = 0;
void removeAll(const arrayListType& removeItem);
arrayListType(int size = 100);
int min(int first, int last);
int max(int first, int last);
arrayListType (const arrayListType& otherList);
virtual ~arrayListType();
protected:
int *list;
int length;
int maxSize;
};
#endif
arrayListTypeImp.cpp
#include <iostream>
#include "arrayListType.h"
using namespace std;
bool arrayListType::isEmpty() const
{
return (length == 0);
}
bool arrayListType::isFull() const
{
return (length == maxSize);
}
int arrayListType::listSize() const
{
return length;
}
int arrayListType::maxListSize() const
{
return maxSize;
}
void arrayListType::print() const
{
for (int i = 0; i < length; i++)
cout << list[i] << " ";
cout << endl;
}
bool arrayListType::isItemAtEqual(int location, int item) const
{
if (location < 0 || location >= length)
{
cout << "The location of the item to be removed "
<< "is out of range." << endl;
return false;
}
else
return (list[location] == item);
}
void arrayListType::removeAt(int location)
{
if (location < 0 || location >= length)
cout << "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--;
}
}
void arrayListType::removeAll( const arrayListType& removeItem)
{
int loc=seqSearch(removeItem);
for(int i=0; i < maxSize; i++)
{
remove(removeItem);
}
int arrayListType::min(int first, int last)
{
int minIndex;
minIndex = first;
for (int loc = first + 1; loc <= last; loc++)
if (list[loc] < list[minIndex])
minIndex = loc;
return minIndex;
}
int arrayListType::max(int first, int last)
{
int maxIndex;
maxIndex = first;
for (int loc = first + 1; loc <= last; loc++)
if (list[loc] < list[maxIndex])
maxIndex = loc;
return maxIndex;
}
void arrayListType::retrieveAt(int location, int& retItem) const
{
if (location < 0 || location >= length)
cout << "The location of the item to be retrieved is "
<< "out of range" << endl;
else
retItem = list[location];
}
void arrayListType::clearList()
{
length = 0;
}
arrayListType::arrayListType(int size)
{
if (size <= 0)
{
cout << "The array size must be positive. Creating "
<< "an array of the size 100." << endl;
maxSize = 100;
}
else
maxSize = size;
length = 0;
list = new int[maxSize];
}
arrayListType::~arrayListType()
{
delete [] list;
}
arrayListType::arrayListType(const arrayListType& otherList)
{
maxSize = otherList.maxSize;
length = otherList.length;
list = new int[maxSize];
for (int j = 0; j < length; j++)
list [j] = otherList.list[j];
}
unorderedArrayListType.h
#ifndef H_unorderedArrayListType
#define H_unorderedArrayListType
#include "arrayListType.h"
class unorderedArrayListType: public arrayListType
{
public:
void insertAt(int location, int insertItem);
void insertEnd(int insertItem);
void replaceAt(int location, int repItem);
int seqSearch(int searchItem) const;
void remove(int removeItem);
void removeAt( int location, const arrayListType& removeItem);
void removeAll(const arrayListType& removeItem);
int min(int first, int last);
int max(int first, int last);
unorderedArrayListType(int size = 100);
};
#endif
unorderedArrayListTypeImp.cpp
#include <iostream>
#include "unorderedArrayListType.h"
using namespace std;
void unorderedArrayListType::insertAt(int location,
int insertItem)
{
if (location < 0 || location >= maxSize)
cout << "The position of the item to be inserted "
<< "is out of range." << endl;
else if (length >= maxSize)
cout << "Cannot insert in a full list" << endl;
else
{
for (int i = length; i > location; i--)
list[i] = list[i - 1];
list[location] = insertItem;
length++;
}
}
void unorderedArrayListType::insertEnd(int insertItem)
{
if (length >= maxSize)
cout << "Cannot insert in a full list." << endl;
else
{
list[length] = insertItem;
length++;
}
}
int unorderedArrayListType::seqSearch(int searchItem) const
{
int loc;
bool found = false;
loc = 0;
while (loc < length && !found)
if (list[loc] == searchItem)
found = true;
else
loc++;
if (found)
return loc;
else
return -1;
}
void unorderedArrayListType::remove(int removeItem)
{
int loc;
if (length == 0)
cout << "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;
}
}
void unorderedArrayListType::replaceAt(int location, int repItem)
{
if (location < 0 || location >= length)
cout << "The location of the item to be "
<< "replaced is out of range." << endl;
else
list[location] = repItem;
}
void arrayListType::removeAt(int location, const arrayListType& removeItem)
{
if (location < 0 || location >= length)
cout << "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--;
}
}
void arrayListType::removeAll( const arrayListType& removeItem)
{
int loc=seqSearch(removeItem);
for(int i=0; i < maxSize; i++)
{
remove(removeItem);
}
int arrayListType::min(int first, int last)
{
int minIndex;
minIndex = first;
for (int loc = first + 1; loc <= last; loc++)
if (list[loc] < list[minIndex])
minIndex = loc;
return minIndex;
}
int arrayListType::max(int first, int last)
{
int maxIndex;
maxIndex = first;
for (int loc = first + 1; loc <= last; loc++)
if (list[loc] < list[maxIndex])
maxIndex = loc;
return maxIndex;
}
unorderedArrayListType::unorderedArrayListType(int size)
: arrayListType(size)
{
}
testProgUnorderedList.cpp
#include <iostream>
#include "unorderedArrayListType.h"
using namespace std;
void unorderedArrayListType::insertAt(int location,
int insertItem)
{
if (location < 0 || location >= maxSize)
cout << "The position of the item to be inserted "
<< "is out of range." << endl;
else if (length >= maxSize)
cout << "Cannot insert in a full list" << endl;
else
{
for (int i = length; i > location; i--)
list[i] = list[i - 1];
list[location] = insertItem;
length++;
}
}
void unorderedArrayListType::insertEnd(int insertItem)
{
if (length >= maxSize)
cout << "Cannot insert in a full list." << endl;
else
{
list[length] = insertItem;
length++;
}
}
int unorderedArrayListType::seqSearch(int searchItem) const
{
int loc;
bool found = false;
loc = 0;
while (loc < length && !found)
if (list[loc] == searchItem)
found = true;
else
loc++;
if (found)
return loc;
else
return -1;
}
void unorderedArrayListType::remove(int removeItem)
{
int loc;
if (length == 0)
cout << "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;
}
}
void unorderedArrayListType::replaceAt(int location, int repItem)
{
if (location < 0 || location >= length)
cout << "The location of the item to be "
<< "replaced is out of range." << endl;
else
list[location] = repItem;
}
unorderedArrayListType::unorderedArrayListType(int size)
: arrayListType(size)
{
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.