An Unsorted Type ADT is to be extended by the addition of fu

An Unsorted Type ADT is to be extended by the addition of function SplitLists, which has the following specifications: SplitLists(UnsortedType list, ItemType item, UnsortedType& list1, UnsortedType& list2) Function: Divides list into two lists according to the key of item. Preconditions: List has been initialized and is not empty. Postconditions: list1 contains all the items of list whose keys are less than or equal to item’s key; list2 contains all the items of list whose keys are greater than item’s key. a. Implement SplitLists as an array-based member function of the Unsorted List ADT. b. Implement SplitLists as a linked member function of the Unsorted List ADT.

Solution

1. Implement SplitLists as an array-based member function of the Unsorted List ADT.

void UnsortedType::SplitLists(ItemType item, UnsortedType&

list1, UnsortedType& list2)

{

int counter = 0;

list1.MakeEmpty();

list2.MakeEmpty();

for (counter; counter < list1.GetLength(); counter++)

if (info[counter].ComparedTo(item) == GREATER)

list2.InsertItem(info[counter]);

else list1.InsertItem(info[counter]);

}

2.Implement SplitLists as a linked member function of the Unsorted List ADT.

void UnsortedType::SplitLists(ItemType item, UnsortedType&

list1, UnsortedType& list2)

{

NodeType* listPtr = listData;

while (listPtr != NULL)

{

if (listPtr->info <= item)

list1.InsertItem(listPtr->info);

else

list2.InsertItem(listPtr->info);

listPtr = listPtr->next;

}

}