Problem 1 (40 pts): Modify the array-based UnsortedType (which uses ItemType class) based upon the following instructions:

Modify the UnsortedType class to use a dynamically allocated array to store the items (this will replace the fixed size array info).

Modify zero-parameter constructor so that it allocates an array of size 10 (default size)

Modify the parameterized constructor that takes an int as parameter, specifying the size of array to allocate.

Add a destructor for the class (why do you need to do so?). Write your answer as a comment above the destructor.

Modify IsFull( ): It will return true, if the current length of list equals to the size of array; otherwise, it returns false.

Overload index operator (i.e., []) to return the reference of i-th element in the list.

Modify PutItem( ) so that it can be called to put an item into a "full" list:

1. Allocate a larger array (which can be double of current size)

2. Copy current array elements to the new array

3. Delete current array

4. insert item into new array

5. set info points to new array

Problem 2 (60 pts): Write a class named Appointment to represent a linked list of appointments. A node will represent an appointment, which consists of Year, Month, and Day.Problem 2 is link list implementation not array

In this scenario, a node will have multiple info fields in addition to a pointer (Next).

Implement the following member functions:

1. Constructor

2. Destructor

3. PutItem: add a new appointment to the list

4. DeleteItem: delete an existing appointment

5. IsFull()

6. CompareAppoint: compare two appointments

7. SearchItem: find whether an appointment exists in the list of appointments or not

8. EmptyList: empty the list of appointments

9. PrintList: display the list of existing appointments

Bonus/Extra Credit (10 pts): Write main function that runs in a loop that allow the user to choose a command:

1. Display: display all appointments

2. Add: add a new appointment. If there is already an appointment on the date, reports error.

3. Search: search for an appointment on a user specified date

4. Delete: delete an appointment on a user specified date

5. Quit: to quite the program

When a command is chosen, the program shall prompt the user to enter relevant info, for example, to add a new appointment, the program prompts the user to enter the date and then create an Appointment object, call PutItem() to add the item into the list.

Implementation of linked list-based unsorted list:

Specification file (.h):unsorted.h

Implementation file (.cpp):unsorted.cpp

Test file (main.cpp):main.cpp

ADT unsorted list with ItemType

ItemType.h:ItemType.h

ItemType.cpp:ItemType.cpp

unsorted.h (array):Unsorted.h

unsorted.cpp (array):Unsorted.cpp

unsorted.h (linked list):unsorted.h

unsorted.cpp (linked list):unsorted.cpp

See below all the source codes provided for .h and .ccp files. If you need to use them to solve above problems, please do so. That's all the information I have for these problems.

struct NodeType;

class UnsortedType

{

public:

UnsortedType ();

~ UnsortedType ();

void MakeEmpty ();

int GetLength () const;

void PutItem (int item);

void DeleteItem (int item);

void printList (NodeType * head);

bool serchItem (int item);

public:

NodeType * listData;

int length;

NodeType * currentPos;

};

#include

#include

#include "unsorted.h"

using namespace std;

struct NodeType

{

int info;

NodeType* next;

};

UnsortedType::UnsortedType(){

length = 0;

listData = NULL;

}

UnsortedType::~UnsortedType(){

NodeType* tempPtr;

while (listData != NULL)

{

tempPtr = listData;

listData = listData->next;

delete tempPtr;

}

}

void UnsortedType::PutItem(int item){

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

}

int UnsortedType::GetLength() const{

return length;

}

void UnsortedType :: printList(NodeType* head) {

while (head != NULL) {

cout << head->info << " ";

head = head->next;

}

}

void UnsortedType::DeleteItem(int item){

NodeType* location = listData;

NodeType* tempLocation;

// Locate node to be deleted.

if (item == listData->info)

{

tempLocation = location;

listData = listData->next; // Delete first node.

}

else

{

while (item != (location->next)->info)

location = location->next;

// Delete node at location->next

tempLocation = location->next;

location->next = (location->next)->next;

}

delete tempLocation;

length--;

}

void UnsortedType::MakeEmpty(){

NodeType* tempPtr;

while (listData != NULL)

{

tempPtr = listData;

listData = listData->next;

delete tempPtr;

}

length = 0;

}

bool UnsortedType::serchItem(int item){

bool moreToSearch;

NodeType* location;

location = listData;

bool found = false;

moreToSearch = (location != NULL);

while (moreToSearch && !found)

{

if (item == location->info){

found = true;

//item = location->info;

return true;

}

location = location->next;

moreToSearch = (location != NULL);

}

return false;

}

#include

#include

#include

#include

#include

#include "unsorted.h"

using namespace std;

int main(int argc, char** argv) {

UnsortedType list;

bool found;

list.PutItem(1);

list.PutItem(2);

list.PutItem(3);

list.PutItem(4);

list.PutItem(5);

cout << list.GetLength() << " ";

list.printList(list.listData);

cout << " ";

// Another way of printing the list:

int length;

int item;

list.ResetList();

length = list.GetLength();

for (int counter = 1; counter <= length; counter++)

{

item = list.GetNextItem();

cout << "Item is: " << item << " ";

}

cout << "Test DeleteItem() ";

list.DeleteItem(2);

cout << list.GetLength() << " ";

list.printList(list.listData);

cout << " ";

cout << "Test SearchItem() ";

cout << list.serchItem(4) << " ";

return 0;

}

#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;

};

.

#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;

}

#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

class UnsortedType

{

public:

UnsortedType();

// Constructor

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, bool&);

// 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:

int length;

ItemType info[MAX_ITEMS];

int currentPos;

};

// Implementation file for Unsorted.h

#include "Unsorted.h"

UnsortedType::UnsortedType()

{

length = 0;

}

bool UnsortedType::IsFull() const

{

return (length == MAX_ITEMS);

}

int UnsortedType::GetLength() const

{

return length;

}

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 returned;

// otherwise, item is returned.

{

bool moreToSearch;

int location = 0;

found = false;

moreToSearch = (location < length);

while (moreToSearch && !found)

{

switch (item.ComparedTo(info[location]))

{

case LESS :

case GREATER : location++;

moreToSearch = (location < length);

break;

case EQUAL : found = true;

item = info[location];

break;

}

}

return item;

}

void UnsortedType::MakeEmpty()

// Post: list is empty.

{

length = 0;

}

void UnsortedType::PutItem(ItemType item)

// Post: item is in the list.

{

info[length] = item;

length++;

}

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.

{

int location = 0;

while (item.ComparedTo(info[location]) != EQUAL)

location++;

info[location] = info[length - 1];

length--;

}

void UnsortedType::ResetList()

// Post: currentPos has been initialized.

{

currentPos = -1;

}

ItemType UnsortedType::GetNextItem()

// Pre: ResetList was called to initialized iteration.

// No transformer has been executed since last call.

// currentPos is defined.

// Post: item is current item.

// Current position has been updated.

{

currentPos++;

return info[currentPos];

}

#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;

};

// 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;

//currentPos = -1;

}

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;

}

}