This problem deals with the Array and Linked List implementations of the Unsorted List (AUList and LLUList). Your solution must begin with the base code available via Blackboard (AUList.h, AUList.cpp, LLUList.h, LLUList.cpp).

a. Create a function for the AUList structure AUList copyReverse() which creates a new AUList with identical elements, but in reverse order. Ex: if myList is an AUList with elements in the order 1, 4, 2, 8, 6, myList.copyReverse() will return an AUList with elements in the order 6, 8, 2, 4, 1.

b. Create the function from part a. but for the LLUList structure (it should return a LLUList with elements in reverse order).

// Implementation file for AUList #include #include "LLUList.h"

struct LNode { int item; LNode* next; };

LLUList::LLUList() { ListStart=NULL; }

LLUList::~LLUList() { LNode* tempPtr; while (ListStart != NULL) { tempPtr = ListStart; ListStart = ListStart->next; delete tempPtr; } }

bool LLUList::IsFull() const { LNode* testNode; try { testNode = new LNode; delete testNode; return false; } catch(std::bad_alloc exception) { return true; } }

int LLUList::GetLength() const { LNode* LenPos = ListStart; int length=0; while (LenPos != NULL) { LenPos=LenPos->next; length++; } return length; };

int LLUList::GetItem(int gitem) { //Procedure is similar to that of AUList, although the relevant data is stored different. //also, it's better for LLUList to proceed in order from the beginning int position=0; LNode* nodeIter; nodeIter=ListStart; while ((nodeIter != NULL) && (nodeIter->item !=gitem)) { nodeIter=nodeIter->next; position++; } if (nodeIter==NULL) return -1; else return position; }

void LLUList::MakeEmpty() { //Unlike the AUList implementation, we need to step through and delete EVERY node LNode* tempPtr; while (ListStart != NULL) { tempPtr = ListStart; ListStart = ListStart->next; delete tempPtr; } }

void LLUList::PutItem(int newitem) { LNode* newNode; //Get a pointer newNode = new LNode; //Create a new node. newNode->item = newitem; // Store the item in the node newNode->next = ListStart; // Store address of next node ListStart = newNode; // Redirect start of list }

void LLUList::DeleteItem(int ditem) { //A little bit tricky because we need to "scout ahead" and relink the object //before the deleted object to the one after. LNode *tmpNode, *nodeIter; if (ListStart->item == ditem) { tmpNode=ListStart; ListStart=ListStart->next; } else{ nodeIter=ListStart; while ((nodeIter->next->item !=ditem)) nodeIter=nodeIter->next; tmpNode=nodeIter->next; nodeIter->next=(nodeIter->next)->next; } delete(tmpNode); }

void LLUList::ResetList() { curPos=ListStart; }

int LLUList::GetNextItem() { int myitem; if (curPos == NULL) //The implemented option throw an errors if someone tries to access an item past the last one. throw(38); //EOS Exception myitem = curPos->item; curPos=curPos->next; return myitem; };

void LLUList::PrintList() { LNode* printPtr; printPtr=ListStart; std::cout<<"("; while (printPtr != NULL) { std::cout<item; if (printPtr->next!=NULL) std::cout<<", "; printPtr=printPtr->next; } std::cout<<")"<

// Implementation file for AUList #include #include "AUList.h"

AUList::AUList() { length = 0; //a newly constructed list has 0 elements; we don't care about the contents of the array. } bool AUList::IsFull() const { return (length == MAXSIZE); //Remember that preprocessor commands like #define carry over into files to which they are included (like this one!) } int AUList::GetLength() const { return length; }

int AUList::GetItem(int gitem) { int searchiter; for (searchiter = length-1; searchiter>=0; searchiter--) { //main loop decrements from the final index in the list down to -1 if (ListItems[searchiter] == gitem) //if this condition is met, we have a match break; //break terminates the innermost-loop in progress (so in this case, the for-loop. Has no impact on other conditionals or scope. } return searchiter; } void AUList::MakeEmpty() { length = 0; //as with the constructor, we need do nothing to the actual array, as it now "junk" data } void AUList::PutItem(int item) { //This function assumes the "IsFull" condition hasn't been met. ListItems[length] = item; //Remember that C++ uses 0-indexing. length++; } void AUList::DeleteItem(int item) { //This is the less efficient version of what we discussed ("Move-Up") that maintains list order //Note: assumes item is actually in list

bool indexfound=false; for (int loc=0; loc

void AUList::ResetList() { currentPos = -1; //We want the position BEFORE the first element, since incrementation in GetNextItems happens first }

int AUList::GetNextItem() { currentPos++; //Remember that currentPos is a class member variable return ListItems[currentPos]; }

void AUList::PrintList() { //simple function to print a list's items in stored order std::cout<<"("; for (int loc=0; loc