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.