Data Structures using C++ Using the UnsortedList class below: #ifndef UNSORTEDLI
ID: 3791134 • Letter: D
Question
Data Structures using C++
Using the UnsortedList class below:
#ifndef UNSORTEDLIST_H
#define UNSORTEDLIST_H
#include <iostream>
#include <cstdlib> // Needed for the exit function
using namespace std;
const int MAX_LENGTH = 100; // Maximum number of components
template <class ItemType> // You may also choose to use
// typedef statement
class UnsortedList
{
public:
// Constructor
UnsortedList();
// Post: Empty list has been created. length has been set to zero.
// Knowledge responsibilities
int getLength() const;
// Post: Returns the length of the list
bool isEmpty() const;
// Post: Returns true if list is empty; false otherwise
bool isFull() const;
// Post: Returns true if list is full; false otherwise
bool isInList(const ItemType& item) const;
// Post: Returns true if item is int the list; false otherwise
int seqSearch(const ItemType& item) const;
// Function to search the list for a given item.
// Post: If item is found, returns the index in the array where
// item is found; otherwise, return -1.
// Action Responsibilities
void resetList();
// Post: The list becomes empty. length has been set to zero.
void insert(const ItemType& item);
// Function to insert item to the end of the list. However, first
// the list is searched to see whether the item to be inserted is
// already in the list.
// Post: list[length] = item and length++. If item is already in
// the list or the list is already full, an appropriate message is
// displayed.
void remove(const ItemType& item);
// Function to remove item from the list.
// Post: If item is found in the list, it is removed from the list
// and length is decremented by one.
// Overloaded [] operator declaration.
// This function returns a reference to the element in the
// array indexed by index.
ItemType& operator[](const int& index);
// Additional operations
void sort();
// Post: list items have been put into ascending order
private:
ItemType list[MAX_LENGTH]; // array to hold the list elements
int length; // to store the length of the list
};
//**********************************************************
template <class ItemType>
UnsortedList<ItemType>::UnsortedList()
{
length = 0;
}
//**********************************************************
template <class ItemType>
int UnsortedList<ItemType>::getLength() const
{
return length;
}
//**********************************************************
template <class ItemType>
bool UnsortedList<ItemType>::isEmpty() const
{
return (length == 0);
}
//**********************************************************
template <class ItemType>
bool UnsortedList<ItemType>::isFull() const
{
return (length == MAX_LENGTH);
}
//**********************************************************
template <class ItemType>
bool UnsortedList<ItemType>::isInList(const ItemType& item) const
{
int loc;
bool found = false;
for (loc = 0; loc < length; loc++)
if (list[loc] == item)
{
found = true;
break;
}
return found;
}
//**********************************************************
template <class ItemType>
int UnsortedList<ItemType>::seqSearch(const ItemType& item) const
{
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;
}
//**********************************************************
template <class ItemType>
void UnsortedList<ItemType>::resetList()
{
length = 0;
}
//**********************************************************
template <class ItemType>
void UnsortedList<ItemType>::insert(const ItemType& item)
{
if (length == 0) // list is empty
{
list[length] = item;
length++;
}
else if (length == MAX_LENGTH)
cout << "Cannot insert in a full list." << endl;
else
{
if (!isInList(item)) // the item is not already in the list
{
list[length] = item;
length++;
}
else
cout << "The item is already in the list. "
<< "No duplicates are allowed." << endl;
}
}
//**********************************************************
template <class ItemType>
void UnsortedList<ItemType>::remove(const ItemType& item)
{
int loc;
if (length == 0)
cout << "Cannot delete from an empty list." << endl;
else
{
loc = seqSearch(item);
if (loc != -1) // the item is already in the list
{
list[loc] = list[length - 1]; // copy the last element to
// where item to be deleted was
length--;
}
}
}
//**********************************************************
template <class ItemType>
ItemType& UnsortedList<ItemType>::operator[](const int& index)
{
if (index < 0 || index >= length)
{
cout << "ERROR: Index out of range. ";
exit(EXIT_FAILURE);
}
return list[index];
}
//**********************************************************
template <class ItemType>
void UnsortedList<ItemType>::sort()
{
ItemType temp;
int passCount; // Outer loop control variable
int searchIndex; // Inner loop control variable
int minIndex; // Index of minimum so far
for (passCount = 0; passCount < length - 1; passCount++)
{
minIndex = passCount;
// Find the index of the smallest component
// in list[passCount..length-1]
for (searchIndex = passCount + 1; searchIndex < length;
searchIndex++)
if (list[searchIndex] < list[minIndex])
minIndex = searchIndex;
// Swap list[minIndex] and list[passCount]
temp = list[minIndex];
list[minIndex] = list[passCount];
list[passCount] = temp;
}
}
#endif
Write a client function splitLists which divides the list into two lists according to the given item. The precondition of the function is: the list has been initialized and is not empty. The postconditions are: list1 contains all the items of the list whose values are less than or equal to the given item; list2 contains all the items of the list whose keys are greater than the given item. Implement the splitLists function as a client function (not a member function or a friend function of the UnsortedList class) whose declaration is:
template <class ItemType>
void splitLists(UnsortedList<ItemType>& list, const ItemType& item,
UnsortedList<ItemType>& list1, UnsortedList<ItemType>& list2);
Explanation / Answer
#ifndef UNSORTEDLIST_H
#define UNSORTEDLIST_H
#include <iostream>
#include <cstdlib> // Needed for the exit function
using namespace std;
const int MAX_LENGTH = 100; // Maximum number of components
template <class ItemType> // You may also choose to use
// typedef statement
class UnsortedList
{
public:
// Constructor
UnsortedList();
// Post: Empty list has been created. length has been set to zero.
// Knowledge responsibilities
int getLength() const;
// Post: Returns the length of the list
bool isEmpty() const;
// Post: Returns true if list is empty; false otherwise
bool isFull() const;
// Post: Returns true if list is full; false otherwise
bool isInList(const ItemType& item) const;
// Post: Returns true if item is int the list; false otherwise
int seqSearch(const ItemType& item) const;
// Function to search the list for a given item.
// Post: If item is found, returns the index in the array where
// item is found; otherwise, return -1.
// Action Responsibilities
void resetList();
// Post: The list becomes empty. length has been set to zero.
void insert(const ItemType& item);
// Function to insert item to the end of the list. However, first
// the list is searched to see whether the item to be inserted is
// already in the list.
// Post: list[length] = item and length++. If item is already in
// the list or the list is already full, an appropriate message is
// displayed.
void remove(const ItemType& item);
// Function to remove item from the list.
// Post: If item is found in the list, it is removed from the list
// and length is decremented by one.
// Overloaded [] operator declaration.
// This function returns a reference to the element in the
// array indexed by index.
ItemType& operator[](const int& index);
// Additional operations
void sort();
// Post: list items have been put into ascending order
private:
ItemType list[MAX_LENGTH]; // array to hold the list elements
int length; // to store the length of the list
};
//**********************************************************
template <class ItemType>
UnsortedList<ItemType>::UnsortedList()
{
length = 0;
}
//**********************************************************
template <class ItemType>
int UnsortedList<ItemType>::getLength() const
{
return length;
}
//**********************************************************
template <class ItemType>
bool UnsortedList<ItemType>::isEmpty() const
{
return (length == 0);
}
//**********************************************************
template <class ItemType>
bool UnsortedList<ItemType>::isFull() const
{
return (length == MAX_LENGTH);
}
//**********************************************************
template <class ItemType>
bool UnsortedList<ItemType>::isInList(const ItemType& item) const
{
int loc;
bool found = false;
for (loc = 0; loc < length; loc++)
if (list[loc] == item)
{
found = true;
break;
}
return found;
}
//**********************************************************
template <class ItemType>
int UnsortedList<ItemType>::seqSearch(const ItemType& item) const
{
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;
}
//**********************************************************
template <class ItemType>
void UnsortedList<ItemType>::resetList()
{
length = 0;
}
//**********************************************************
template <class ItemType>
void UnsortedList<ItemType>::insert(const ItemType& item)
{
if (length == 0) // list is empty
{
list[length] = item;
length++;
}
else if (length == MAX_LENGTH)
cout << "Cannot insert in a full list." << endl;
else
{
if (!isInList(item)) // the item is not already in the list
{
list[length] = item;
length++;
}
else
cout << "The item is already in the list. "
<< "No duplicates are allowed." << endl;
}
}
//**********************************************************
template <class ItemType>
void UnsortedList<ItemType>::remove(const ItemType& item)
{
int loc;
if (length == 0)
cout << "Cannot delete from an empty list." << endl;
else
{
loc = seqSearch(item);
if (loc != -1) // the item is already in the list
{
list[loc] = list[length - 1]; // copy the last element to
// where item to be deleted was
length--;
}
}
}
//**********************************************************
template <class ItemType>
ItemType& UnsortedList<ItemType>::operator[](const int& index)
{
if (index < 0 || index >= length)
{
cout << "ERROR: Index out of range. ";
exit(EXIT_FAILURE);
}
return list[index];
}
//**********************************************************
template <class ItemType>
void UnsortedList<ItemType>::sort()
{
ItemType temp;
int passCount; // Outer loop control variable
int searchIndex; // Inner loop control variable
int minIndex; // Index of minimum so far
for (passCount = 0; passCount < length - 1; passCount++)
{
minIndex = passCount;
// Find the index of the smallest component
// in list[passCount..length-1]
for (searchIndex = passCount + 1; searchIndex < length;
searchIndex++)
if (list[searchIndex] < list[minIndex])
minIndex = searchIndex;
// Swap list[minIndex] and list[passCount]
temp = list[minIndex];
list[minIndex] = list[passCount];
list[passCount] = temp;
}
}
#endif
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.