Share
Explore BrainMass

A client function that merges two instances of the Sorted List ADT

Write a client function that merges two instances of the Sorted List ADT using
the following specification.

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

Function: Merge two sorted lists into a thirdsorted list.
Preconditions: list1 and list2 have been initialized
and are sorted 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 the items from list1 and list2.
a. Write the prototype for MergeLists.
b. Write the function definition, using an array-based implementation.
c. Write the function definition, using a linked implementation.
d. Describe the algorithm in terms of Big-O.

Then I need to rewrite it making MergeLists an array-based member function of the
Sorted List ADT. Also to rewrite that making MergeLists a linked member function of the SortedList ADT.

Solution Preview

a. Write the prototype for MergeLists.
void MergeLists(SortedType list1, SortedType list2, SortedType& result);

b. Write the function definition, using an array-based implementation.
void MergeLists(SortedType list1, SortedType list2, SortedType& result)
{
int length1;
int length2;
int counter1 = 1;
int counter2 = 1;
ItemType item1;
ItemType item2;

length1 = list1.GetLength();
length2 = list2.GetLength();
list1.ResetList();
list2.ResetList();
list1.GetNextItem(item1);
list2.GetNextItem(item2);
result.MakeEmpty();

while (counter1 <= length1 && counter2 <= length2)
switch (item1.ComparedTo(item2))
{
case LESS : result.InsertItem(item1);
list1.GetNextItem(item1);
counter1++;
break;
case EQUAL : result.InsertItem(item1);
...

Solution Summary

The solution gives complete C++ code for a client function that merges two instances of the Sorted List ADT.

$2.19