Explore BrainMass
Share

Explore BrainMass

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

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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.

    © BrainMass Inc. brainmass.com October 10, 2019, 7:18 am ad1c9bdddf
    https://brainmass.com/computer-science/cpp/576360

    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