An Unsorted Type ADT is to be extended by the addition of function SplitLists, w

Question

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.

Explanation / Answer

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;

}

}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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