I have a client function that merges two instances of the Sorted List ADT. I nee
ID: 3538357 • Letter: I
Question
I have a client function that merges two instances of the Sorted List ADT. I need help with the following:
1. Make MergeLists an array-based member function of the Sorted List ADT
2. Make Mergelists a linked member function of the Sorted List ADT
MergeLists(SortedType list1, Sortedtype list2, SortedType& result)
{
item1=list1;
item2=list2;
item3=result;
while(item1!=null) &&(item2!=null)
{
if(item1->value < item2->value)
{
item3=item2;
item2=item2->next;
item3=item3->next;
}
if(item2->value < item1->value)
{
item3=item1;
item1=item1->next;
item3=item3->next;
}
}
if(item2=null)
{
while(item1!=null)
{
result=item1;
item1=item1->next;
item3=item3->next;
}
}
if(item1=null)
{
while(item2!=null)
{
result=item2;
item2=item2->next;
item3=item3->next;
}
}
}
Thank you!
Explanation / Answer
#include "sorted.h"SortedType::SortedType()
{
length = 0;
}
void SortedType::MakeEmpty()
{
length = 0;
}
bool SortedType::IsFull() const
{
return (length == MAX_ITEMS);
}
int SortedType::GetLength() const
{
return length;
}
void SortedType::RetrieveItem(ItemType& item, bool& found)
{
int midPoint;
int first = 0;
int last = length - 1;
bool moreToSearch = first <= last;
found = false;
while (moreToSearch && !found)
{
midPoint = ( first + last) / 2;
switch (item.ComparedTo(info[midPoint]))
{
case LESS : last = midPoint - 1;
moreToSearch = first <= last;
break;
case GREATER : first = midPoint + 1;
moreToSearch = first <= last;
break;
case EQUAL : found = true;
item = info[midPoint];
break;
}
}
}
void SortedType::DeleteItem(ItemType item)
{
int location = 0;
while (item.ComparedTo(info[location]) != EQUAL)
location++;
for (int index = location + 1; index < length; index++)
info[index - 1] = info[index];
length--;
}
void SortedType::InsertItem(ItemType item)
{
bool moreToSearch;
int location = 0;
moreToSearch = (location < length);
while (moreToSearch)
{
switch (item.ComparedTo(info[location]))
{
case LESS : moreToSearch = false;
break;
case GREATER : location++;
moreToSearch = (location < length);
break;
}
}
for (int index = length; index > location; index--)
info[index] = info[index - 1];
info[location] = item;
length++;
}
void SortedType::ResetList()
// Post: currentPos has been initialized.
{
currentPos = -1;
}
void SortedType::GetNextItem(ItemType& item)
// Post: item is current item.
// Current position has been updated.
{
currentPos++;
item = info[currentPos];
}
void SortedType::MergeLists(SortedType& list1, SortedType&list2, SortedType& list)
{
ItemType item;
bool found;
int length;
int i;
list.MakeEmpty();
list1.ResetList();
length = list1.GetLength();
for (i=0;i <= length - 1;i++)
{
list1.GetNextItem(item);
list.InsertItem(item);
}
list2.ResetList();
length = list2.GetLength();
for (i=0;i <= length - 1;i++)
{
list2.GetNextItem(item);
list.InsertItem(item);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.