#include <iostream>
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
struct ItemType
{
int id;
float gpa;
char major[2];
};
struct NodeType
{
ItemType info;
NodeType* next;
};
class SortedType
{
public:
SortedType();
// Constructor
// Postcondition: Empty list is created
~SortedType();
// Destructor
// Postcondition: List is destroyed
SortedType(const SortedType& otherList);
// Copy-constructor
// Postcondition: List is created as a duplicate of otherList
bool IsFull() const;
// Determines whether list is full.
// Post: Function value = (list is full)
bool invalidItem(ItemType item) const;
int LengthIs() const;
// Determines the number of elements in list.
// Post: Function value = number of elements in list.
void MakeEmpty();
// Initializes list to empty state.
// Post: List is empty.
void RetrieveItem(ItemType& item, bool& found);
// Retrieves list element whose key matches item's key
// (if present).
// Pre: Key member of item is initialized.
// Post: If there is an element someItem whose key matches
// item's key, then found = true and item is a copy
// of someItem; otherwise found = false and item is
// unchanged.
// List is unchanged.
void InsertItem(ItemType item);
// Adds item to list.
// Pre: List is not full.
// item is not in list.
// Post: item is in list
// (added) // list order is preserved
void DeleteItem(ItemType item);
// Deletes the element whose key matches item's key.
// Pre: 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();
// Initializes current position to end of list for iteration
// through list.
// Post: Current position is at end of list.
void GetNextItem(ItemType& item);
// Gets the next element in list.
// Pre:
// Post: If Current position is at end, currentPos points to head of list,
// else item is copy of element at current position.
// Advance current position.
void Print(ofstream&);
private:
NodeType* listData;
int length;
NodeType* currentPos;
};
void GetNextItem(ItemType& item);
// Gets the next element in list.
// Pre:
// Post: If Current position is at end, currentPos points to head of list,
// else item is copy of element at current position.
// Advance current position.
void Print(ofstream&);
private:
NodeType* listData;
int length;
NodeType* currentPos;
};
// SortedType.cxx
SortedType::SortedType() // Class constructor
{
length = 0;
listData = NULL;
}
SortedType::~SortedType()
// Post: List is empty; all items have been deallocated.
{
MakeEmpty();
}
SortedType::SortedType(const SortedType& otherList)
// Copy-constructor
// Postcondition:
// IF otherList.listData == NULL
// listData == NULL
// ELSE
// listData points to a new linked list that is a copy of
// the linked list pointed to by otherList.listData
{
NodeType* fromPtr; // Pointer into list being copied from
NodeType* toPtr; // Pointer into new list being built
if(otherList.listData == NULL)
{
listData = NULL;
return;
}
// Copy first node
fromPtr = otherList.listData;
listData = new NodeType;
listData->info = fromPtr->info;
// Copy remaining nodes
toPtr = listData;
fromPtr = fromPtr->next;
while (fromPtr != NULL)
{
toPtr->next = new NodeType;
toPtr = toPtr->next;
toPtr->info = fromPtr->info;
fromPtr = fromPtr->next;
}
toPtr->next = NULL;
}
/* bool SortedType::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(bad_alloc exception)
{
return true;
}
} */
bool SortedType::invalidItem(ItemType item) const
//**********************************************************************
//Purpose: Determines whether the data assigned is valid given the parameters
//Input: item.id, gpa, major
//Pre: Variables must be set and have valid numbers
//output: bool, true or false
//post: so long as function runs, the data will be processed and determined
// as invalid or valid data
//note: None
//**********************************************************************
{
return(item.id >= 111 && item.id <= 999 &&
item.gpa >= 0.0 && item.gpa <= 4.0 &&
item.major[0] == 'C' || item.major[0] == 'I' &&
item.major[1] == 'S');
}
bool SortedType::IsFull() const
// Returns true if there is no room for another ItemType
// object on the free store; false otherwise.
{
NodeType* ptr;
ptr = new NodeType;
if (ptr == NULL)
return true;
else
{
delete ptr;
return false;
}
}
int SortedType::LengthIs() const
// Post: Number of items in the list is returned.
{
return length;
}
void SortedType::MakeEmpty()
// Post: List is empty; all items have been deallocated.
{
NodeType*
tempPtr;
while (listData != NULL) // traverse list, deallocating each node in turn
{
tempPtr = listData;
listData = listData->next;
delete tempPtr;
}
length = 0; // to agree with the fact that all nodes are deallocated
}
void SortedType::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.id == listData->info.id)
{
tempLocation = location;
listData = listData->next; // Delete first node.
}
else
{
while (!(item.id==(location->next)->info.id))
location = location->next;
// Delete node at location->next
tempLocation = location->next;
location->next = (location->next)->next;
}
delete tempLocation;
length--;
}
void SortedType::ResetList()
// Post: Current position has been initialized to AtEnd
{
currentPos = NULL;
}
void SortedType::RetrieveItem(ItemType& item, bool& found)
{
bool moreToSearch;
NodeType* location;
location = listData;
found = false;
moreToSearch = (location != NULL);
while (moreToSearch && !found)
{
if (location->info.id < item.id)
{
location = location->next;
moreToSearch = (location != NULL);
}
else if (item.id == location->info.id)
{
found = true;
item = location->info;
}
else
moreToSearch = false;
}
}
void SortedType::InsertItem(ItemType item)
{
NodeType* newNode; // pointer to node being inserted
NodeType* predLoc; // trailing pointer
NodeType* location; // traveling pointer
bool moreToSearch;
location = listData;
predLoc = NULL;
moreToSearch = (location != NULL);
// Find insertion point.
while (moreToSearch)
{
if (location->info.id < item.id)
{
predLoc = location;
location = location->next;
moreToSearch = (location != NULL);
}
else
moreToSearch = false;
// Prepare node for insertion
newNode = new NodeType;
newNode->info = item;
// Insert node into list.
if (predLoc == NULL) // Insert as first
{
newNode->next = listData;
listData = newNode;
}
else
{
newNode->next = location;
predLoc->next = newNode;
}
length++;
}
void SortedType::GetNextItem(ItemType& item)
// Pre: Current position is defined.
// Element at current position is not last in list.
// Post: Current position has been updated; item is current item.
{
if (currentPos == NULL) //Wrap at end of list
currentPos = listData;
item = currentPos->info;
currentPos = currentPos->next;
}
void SortedType::Print(ofstream& outFile)
{
currentPos = listData;
while(currentPos != NULL)
{
outFile << currentPos->info.id << " " << currentPos->info.gpa << currentPos->info.major[0] << currentPos->info.major[1]
currentPos = currentPos->next;
}
}
Unsolved 
