ISBN13: 9781449646752 C++ Plus Data Structures 5th Edition Chapter 4 Question 4

Question

ISBN13: 9781449646752 C++ Plus Data Structures 5th Edition

Chapter 4

Question 4

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

MergeLists(sorted type list1, sorted type list 2, sorted type& result)

Function:            Merge two sorted lists into a third sorted list

Preconditions:    list1 and list2 have been initialized and are stored by key using function   

                          ComparedTo.

                          list1 and list2 do not have any keys in common.

Postcondition:    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

Explanation / Answer

void Merge(list<int> &one, list<int> &two, list<int> &result)
{
while((!one.empty()) && (!two.empty))
{
if(one.front() < two.front())
{
result.push_back(one.front());
one.pop_front();          
}
else
{
result.push_back(two.front());
two.pop_front();      
}      
}
while(!one.empty())
{
result.push_back(one.front());
one.pop_front();
}
while(!two.empty())
{
result.push_back(two.front());
two.pop_front();
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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