Question
C++ Programming Going to hand in a working implementation of the linked list UnsortedType class detailed below Use project files to get started: ItemType.cpp //
C++ Programming
Going to hand in a working implementation of the linked list UnsortedType class detailed below
Use project files to get started:
ItemType.cpp
// The following definitions go into file ItemType.cpp.
#include
#include
#include "ItemType.h"
ItemType::ItemType()
{
value = 0;
}
RelationType ItemType::ComparedTo(ItemType otherItem) const
{
if (value < otherItem.value)
return LESS;
else if (value > otherItem.value)
return GREATER;
else return EQUAL;
}
void ItemType::Initialize(int number)
{
value = number;
}
void ItemType::Print(std::ostream& out) const
// pre: out has been opened.
// post: value has been sent to the stream out.
{
out << value;
}
ItemType.h
// The following declarations and definitions go into file
// ItemType.h.
#include
const int MAX_ITEMS = 5;
enum RelationType {LESS, GREATER, EQUAL};
class ItemType
{
public:
ItemType();
RelationType ComparedTo(ItemType) const;
void Print(std::ostream&) const;
void Initialize(int number);
private:
int value;
};
Linked_app.cpp
#include "unsorted.h"
#include
using namespace std;
int main() {
// Create UnsortedType object
UnsortedType ut;
// Create a few items
ItemType item1, item2, item3;
item1.Initialize(1);
item2.Initialize(2);
item3.Initialize(3);
// Check the length (should be 0)
cout << "Length: " << ut.GetLength() << endl;
// Add the items
ut.PutItem(item1);
ut.PutItem(item2);
ut.PutItem(item3);
// Check the length (should be 0)
cout << "Length: " << ut.GetLength() << endl;
/* ALL BELOW IS FROM ARRAY LIST (IGNORE FOR NOW)
// Display the list (should be nothing)
cout << " --- List contents ---" << endl;
for (int i = 0; i < ut.GetLength(); i++) {
// Get the next item
ItemType next = ut.GetNextItem();
next.Print(cout);
cout << endl;
}
// Put them in the list
ut.PutItem(item1);
ut.PutItem(item2);
ut.PutItem(item3);
// Check the length (should be 3)
cout << "Length: " << ut.GetLength() << endl;
// Display the list (should be 1 2 3)
cout << " --- List contents ---" << endl;
for (int i = 0; i < ut.GetLength(); i++) {
// Get the next item
ItemType next = ut.GetNextItem();
next.Print(cout);
cout << endl;
}
// Delete an item
ut.DeleteItem(item1);
// Check the length (should be 2)
cout << "Length: " << ut.GetLength() << endl;
// Display the list (should be 2, 3)
// NOTE -- 3 and 2 not 2 and 3 ??? review in class
cout << " --- List contents ---" << endl;
for (int i = 0; i < ut.GetLength(); i++) {
// Get the next item
ItemType next = ut.GetNextItem();
next.Print(cout);
cout << endl;
}
// IsFull should be false (only 2 items)
cout << "Is full? " << ut.IsFull() << endl;
ItemType it4, it5, it6;
it4.Initialize(4);
it5.Initialize(5);
it6.Initialize(6);
ut.PutItem(it4);
ut.PutItem(it5);
ut.PutItem(it6);
// Get the item with 3 in it.
bool found;
ItemType foundItem = ut.GetItem(item3, found);
//Check if found
cout << "Found: " << found << endl;
// Value of found item
if (found) {
foundItem.Print(cout);
cout << endl;
}
// IsFull should be true (5 items)
cout << "Is full? " << ut.IsFull() << endl;
// Check length (should be 5)
cout << "Length: " << ut.GetLength() << endl;
// empty the list.
ut.MakeEmpty();
// Check length (should be 0)
cout << "Length: " << ut.GetLength() << endl;
// Get the item with 3 in it.
foundItem = ut.GetItem(item3, found);
//Check if found
cout << "Found: " << found << endl;
// Value of found item
if (found) {
foundItem.Print(cout);
cout << endl;
}
*/
return 0;
}
Unsorted.cpp
// This file contains the linked implementation of class
// UnsortedType.
#include "unsorted.h"
struct NodeType
{
ItemType info;
NodeType* next;
};
UnsortedType::UnsortedType() // Class constructor
{
length = 0;
listData = NULL;
}
bool UnsortedType::IsFull() const
// Returns true if there is no room for another ItemType
// on the free store; false otherwise.
{
NodeType* location;
try
{
location = new NodeType;
delete location;
return false;
}
catch(std::bad_alloc exception)
{
return true;
}
}
int UnsortedType::GetLength() const
// Post: Number of items in the list is returned.
{
return length;
}
void UnsortedType::MakeEmpty()
// Post: List is empty; all items have been deallocated.
{
NodeType* tempPtr;
while (listData != NULL)
{
tempPtr = listData;
listData = listData->next;
delete tempPtr;
}
length = 0;
}
void UnsortedType::PutItem(ItemType item)
// item is in the list; length has been incremented.
{
NodeType* location; // Declare a pointer to a node
location = new NodeType; // Get a new node
location->info = item; // Store the item in the node
location->next = listData; // Store address of first node
// in next
field of new node
listData = location; // Store address of new node into
// external
pointer
length++; // Increment length of the list
}
ItemType UnsortedType::GetItem(ItemType& item, bool& found)
// Pre: Key member(s) of item is initialized.
// Post: If found, item's key matches an element's key in the
// list and a copy of that element has been stored in item;
// otherwise, item is unchanged.
{
bool moreToSearch;
NodeType* location;
location = listData;
found = false;
moreToSearch = (location != NULL);
while (moreToSearch && !found)
{
switch (item.ComparedTo(location->info))
{
case LESS :
case GREATER : location = location->next;
moreToSearch = (location != NULL);
break;
case EQUAL : found = true;
item = location->info;
break;
}
}
return item;
}
void UnsortedType::DeleteItem(ItemType item)
// Pre: item's key has been initialized.
// An element in the list has a key that matches item's.
// Post: No element in the list has a key that matches item's.
{
NodeType* location = listData;
NodeType* tempLocation;
// Locate node to be deleted.
if (item.ComparedTo(listData->info) == EQUAL)
{
tempLocation = location;
listData = listData->next; // Delete first node.
}
else
{
while (item.ComparedTo((location->next)->info) != EQUAL)
location = location->next;
// Delete node at location->next
tempLocation = location->next;
location->next = (location->next)->next;
}
delete tempLocation;
length--;
}
void UnsortedType::ResetList()
// Post: Current position has been initialized.
{
currentPos = NULL;
}
ItemType UnsortedType::GetNextItem()
// Post: A copy of the next item in the list is returned.
// When the end of the list is reached, currentPos
// is reset to begin again.
{
ItemType item;
if (currentPos == NULL)
currentPos = listData;
else
currentPos = currentPos->next;
item = currentPos->info;
return item;
}
UnsortedType::~UnsortedType()
// Post: List is empty; all items have been deallocated.
{
NodeType* tempPtr;
while (listData != NULL)
{
tempPtr = listData;
listData = listData->next;
delete tempPtr;
}
}
unsorted.h
#include "ItemType.h"
// File ItemType.h must be provided by the user of this class.
// ItemType.h must contain the following definitions:
// MAX_ITEMS: the maximum number of items on the list
// ItemType: the definition of the objects on the list
// RelationType: {LESS, GREATER, EQUAL}
// Member function ComparedTo(ItemType item) which returns
// LESS, if self "comes before" item
// GREATER, if self "comes after" item
// EQUAL, if self and item are the same
struct NodeType;
class UnsortedType
{
public:
UnsortedType();
// Constructor
~UnsortedType();
// Destructor
void MakeEmpty();
// Function: Returns the list to the empty state.
// Post: List is empty.
bool IsFull() const;
// Function: Determines whether list is full.
// Pre: List has been initialized.
// Post: Function value = (list is full)
int GetLength() const;
// Function: Determines the number of elements in list.
// Pre: List has been initialized.
// Post: Function value = number of elements in list
ItemType GetItem(ItemType& item, bool& found);
// Function: Retrieves list element whose key matches item's key (if
// present).
// Pre: List has been initialized.
// Key member of item is initialized.
// Post: If there is an element someItem whose key matches
// item's key, then found = true and someItem is returned;
// otherwise found = false and item is returned.
// List is unchanged.
void PutItem(ItemType item);
// Function: Adds item to list.
// Pre: List has been initialized.
// List is not full.
// item is not in list.
// Post: item is in list.
void DeleteItem(ItemType item);
// Function: Deletes the element whose key matches item's key.
// Pre: List has been initialized.
// Key member of item is initialized.
// One and only one element in list has a key matching item's key.
// Post: No element in list has a key matching item's key.
void ResetList();
// Function: Initializes current position for an iteration through the
list.
// Pre: List has been initialized.
// Post: Current position is prior to list.
ItemType GetNextItem();
// Function: Gets the next element in list.
// Pre: List has been initialized and has not been changed since last
call.
// Current position is defined.
// Element at current position is not last in list.
//
// Post: Current position is updated to next position.
// item is a copy of element at current position.
private:
NodeType* listData;
int length;
NodeType* currentPos;
};
In addition to the basic class provided, add the following functions:
* PutItemLast() - like PutItem, but puts at the end of the list instead of head of the list
* LastItem() -- return last item in list. For this one, create a pointer which points to the last item of the list, and the function will return the ItemType object it points to.
* FirstItem() -- return the first item
* GetMiddle() -- get the item that is in the middle of the list (hint: first look at the length and count as you iterate until you are length/2 into the list)
* Also: overload the + operator so that you can add two lists together (e.g. list 3 = list1 + list2)
Submit:
* unsorted.cpp, unsorted.h, itemtype.cpp, itemtype.h, and your application.cpp
* screenshot(s) of running program with output. Output should display the results of the above functions.
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started