Using C++: Write a client function that merges two instances of the sorted list

ID: 3597179 • Letter: U

Question

Using C++: Write a client function that merges two instances of the sorted list ADT using the following specifications.

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

Function: Merge two sorted lists into a third sorted list

Preconditions: list1 and list2 have been initalized 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

E) Rewrite the prototype making MergeLists an array-based member function of the Sorted List ADT

F) Rewrite the prototype making MergeLists a linked member of the function of the Sorted List ADT.

Explanation / Answer

Array based implementation. Assuming SortedType has an array of numbers and we can get the access to that member through getArray() and a getSize() function to get their sizes

Mergelist(SortedType list1, SortedType list2, SortedType& result){

    int *a = list1.getArray();
    int *b = list2.getArray();
    int *c = result.getArray();
    int size1 = list1.getSize();
    int size2 = list2.getSize();
    int i,j, k,l;

    k = 0;
    i = 0;
    j = 0;
    while (i < size1 && j < size2){
         if (a[i] < b[j]){
             c[k] = a[i];
              k++;
              i++;
         }
         else {
             c[k] = b[j];
              k++;
              j++;
         }

    }
    if (i == size1 && j < size2){
       for (l=j; l<size2; l++){
           c[k]=b[l];
           k++;
       }
    }
    if (i < size1 && j == size2){
       for (l=i; l<size1; l++){
           c[k]=a[l];
           k++;
       }
    }
}

linked list based implementation. Assuming SortedType has a list of numbers and we can get the access to that member through getHead().

Mergelist(SortedType list1, SortedType list2, SortedType& result){

    Node *a = list1.getHead();
    Node *b = list2.getHead();

    while (a != NULL && b != NULL){
         if (a->data < b->data){
             result.insert(a->data);
             a = a->next;
         }
         else {
             result.insert(b->data);
             b = b->next;
         }

    }
    if (a == NULL && b != NULL){
       while (b!= NULL){
           result.insert(b->data)
           b = b->next;
       }
    }
    if (b == NULL && a != NULL){
       while (a!= NULL){
           result.insert(->data)
           a = a->next;
       }
    }
}

The complexity of the merging is O(n+m) as we are tarversing bothe the list/array where n and m represent the size of two lists

Navigate

Using C++: Using the Pythagorean Theorem, calculate the hypotenuse of a right tr

Using C++: Write a function that recursively calculates the sum of an array. The

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Using C++: Write a client function that merges two instances of the sorted list

Question

Explanation / Answer

Related Questions

Navigate