Purchase Solution

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

Not what you're looking for?

Ask Custom Question

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.

Purchase this Solution
Solution Summary

The solution gives complete C++ code for a client function that merges two instances of the Sorted List 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);
...

Purchase this Solution
Free BrainMass Quizzes
C# variables and classes

This quiz contains questions about C# classes and variables.

Word 2010: Table of Contents

Ever wondered where a Table of Contents in a Word document comes from? Maybe you need a refresher on the topic? This quiz will remind you of the keywords and options used when working with a T.O.C. in Word 2010.

Basic UNIX commands

Use this quiz to check your knowledge of a few common UNIX commands. The quiz covers some of the most essential UNIX commands and their basic usage. If you can pass this quiz then you are clearly on your way to becoming an effective UNIX command line user.

Basic Networking Questions

This quiz consists of some basic networking questions.

Java loops

This quiz checks your knowledge of for and while loops in Java. For and while loops are essential building blocks for all Java programs. Having a solid understanding of these constructs is critical for success in programming Java.

View More Free Quizzes
Related BrainMass Solutions

  • Javascript: merge two sorted arrays into one sorted array

    306134 Create a JavaScript function "merge" that take two sorted arrays as parameters and merges them into one sorted array. I'm trying to write a function merge that take two sorted arrays as parameters.

  • Merging Arrays in VB.NET

    127850 Merging Arrays (Must be in vb.NET) Merging is the process of combining two sorted lists into a single sorted list. In some cases, one list can be appended to the other, and the new list then can be sorted.

  • C++ code to implement SplitLists

    and linked member function of the Unsorted List ADT.

  • Data Structures Question

    32446 Data Structures Question 1) (a) Consider the following axioms from the Unsorted List ADT: Delete(Create, i1) = Create Delete(Make(L1, i2), i1) = IF i1 = i2 THEN L1 ELSE Make(Delete(L1, i1), i2) END IF Briefly describe the behaviour of the

  • Java data structures and alg.

    Outputs: a sorted list that is the merging of L1 and L2, and, the number of times two list elements were compared during the merging process (call it C). The recursive Merge method returns the merging of L1 and L2 as its result.

  • Search using a divide-and-conquer algorithm

    Doing this as a divide-and-conquer algorithm implies a recursive approach. For this solution I'll assume that the elements are integers and there is a Max(a,b) function that returns the maximum of two elements.

  • Writing a Function that Revises a List

    424710 Writing a Function that Revises a List Imagine a circular linked list of integers that are sorted into ascending order as shown in the attached file.

  • Applet, Servlet, UML

    An applet is a Java software component that runs in the context of another program. An applet performs a narrow function that has no independent use. Therefore, it is an application -let.

  • Java - ListMerge

    129549 Java - ListMerge Write a program that merges two ordered-list objects of integers into a single ordered-list object of integers.

View More Related Solutions