Programming and Problem Solving with Java

CASE STUDY

566

This algorithm is by far the most complex we have examined to date. You are well

advised to study it until you completely understand it. The merging of two ordered lists

is one of those familiar algorithms that appears in many different places. For example,

the union of two sets is calculated in exactly the same way.

Now we must simply examine the “Print labels” and “Write combined file” responsi-

bilities. We have all the entries in alphabetical order in resultList. We can use a forloop

to iterate through the list, printing out the address labels. We can also use a forloop to

write out the entries in resultList. In fact, as both these responsibilities require for

loops to process the combined list of entries, we can combine the processing into the

same loop.

//***********************************************************

// This application merges two address books into one and

// prints out address labels.

//***********************************************************

Insert rest of secondList into resultList

whilesecondCount <= secondLimit

resultList.insert(secondEntry)

secondCount++

ifsecondCount <= secondLimit

Set secondEntry to next entry in secondList

Insert rest of firstList into resultList

whilefirstCount <= firstLimit

resultList.insert(firstEntry)

firstCount++

iffirstCount <= firstLimit

Set firstEntry to next entry in firstList

Process both entries

resultList.insert(firstEntry)

iffirstCount equals firstLimit

Set moreData1 to false

else

Set firstEntry to next entry in firstList

firstCount++

ifsecondCount equals secondLimit

Set moreData2 to false

else

Set secondEntry to next item in secondList

secondCount++