C++ Plus Data Structures 5th Edition: Chapter 3 Exercise 3 A&B: An Unsorted Type

Question

C++ Plus Data Structures 5th Edition:

Chapter 3 Exercise 3 A&B:

An Unsorted Type ADT is to be extended by the addition of function SplitLists, which has the following specifications:

SplitLists(Unsorted Type 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;

lis2t 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 C
• Subjects

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