90.2K

Verified Solution

Link Copied!

C++ Data Structures

4. Write a client function thatmerges two instances of the Sorted List ADT using the followingspecification.

MergeLists(SortedType list1, SortedType list2, SortedType&result)

Function: Merge two sorted lists into a third sorted list.

Preconditions: list1 and list2 have been initialized and aresorted by key using function ComparedTo.

list1 and list2 do not have any keys in common.

Postconditions: result is a sorted list that contains all of theitems from list1 and list2.

c. Write the function definition, using a linkedimplementation.

In order to verify that the code ofMergeLists(SortedType list1, SortedType list2, SortedType&result) works, please integrate your code in the SortedType codebelow

**Use a driver to test your code.

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

#include \"ItemType.h\"
// Header file for Sorted List ADT.
struct NodeType;

class SortedType
{
public:
SortedType(); // Class constructor  
~SortedType(); // Class destructor

bool IsFull() const;
int GetLength() const;
void MakeEmpty();
ItemType GetItem(ItemType& item, bool& found);
void PutItem(ItemType item);
void DeleteItem(ItemType item);
void ResetList();
ItemType GetNextItem();

private:
NodeType* listData;
int length;
NodeType* currentPos;
};

struct NodeType
{
ItemType info;
NodeType* next;
};

SortedType::SortedType() // Class constructor
{
length = 0;
listData = NULL;
}

bool SortedType::IsFull() const
{
NodeType* location;
try
{
location = new NodeType;
delete location;
return false;
}
catch(std::bad_alloc exception)
{
return true;
}
}

int SortedType::GetLength() const
{
return length;
}

void SortedType::MakeEmpty()
{
NodeType* tempPtr;

while (listData != NULL)
{
tempPtr = listData;
listData = listData->next;
delete tempPtr;
}
length = 0;
}

ItemType SortedType::GetItem(ItemType& item,bool& found)
{
bool moreToSearch;
NodeType* location;

location = listData;
found = false;
moreToSearch = (location != NULL);

while (moreToSearch && !found)
{
switch(item.ComparedTo(location->info))
{
case GREATER: location = location->next;
moreToSearch = (location != NULL);
break;
case EQUAL: found = true;
item = location->info;
break;
case LESS: moreToSearch = false;
break;
}
}
return item;
}

void SortedType::PutItem(ItemType item)
{
NodeType* newNode;     // pointer to node beinginserted
NodeType* predLoc;     // trailing pointer
NodeType* location;    // traveling pointer
bool moreToSearch;

location = listData;
predLoc = NULL;
moreToSearch = (location != NULL);

// Find insertion point.
while (moreToSearch)
{
switch(item.ComparedTo(location->info))
{
case GREATER: predLoc = location;
   location = location->next;
moreToSearch = (location != NULL);
break;
case LESS: moreToSearch = false;
break;
}
  
}

// 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::DeleteItem(ItemType item)
{
NodeType* location = listData;
NodeType* tempLocation;

// Locate node to be deleted.
if (item.ComparedTo(listData->info) == EQUAL)
{
tempLocation = location;
listData = listData->next;   // Delete firstnode.
}
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 SortedType::ResetList()
{
currentPos = NULL;
}

ItemType SortedType::GetNextItem()
{
ItemType item;
if (currentPos == NULL)
currentPos = listData;
item = currentPos->info;
currentPos = currentPos->next;
return item;

}

SortedType::~SortedType()
{
NodeType* tempPtr;

while (listData != NULL)
{
tempPtr = listData;
listData = listData->next;
delete tempPtr;
}

}