An Unsorted Type ADT is to be extended by the addition of function SplitLists, w
ID: 3531954 • Letter: A
Question
An Unsorted Type ADT is to be extended by the addition of function SplitLists, which as 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.
Post conditions: list1 contains all the items of list whose keys are less than or equal to items key;
list2 contains all of the items of list whose keys are greater than items 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
Answer:
Here is sample ItemType and Unsorted List ADT is provided with added split function.
The item that are stored in the UnsortedType are depends on the usage.
Like whether it is able to store the values in array form or linked list form.
The SplitLists() function is highlighted in bold letters.
(a) The SplitLists() function that is provided below is for the array based:
#include <iostream>
using namespace std;
const int MAX_ITEMS = 5;
enum RelationType
{
LESS, GREATER, EQUAL
};
class ItemType
{
public:
ItemType();
RelationType ComparedTo(ItemType item);
void Print(ofstream &)const;
void Initialize(int number);
private:
int value;
};
template<class ItemType>
class UnsortedType
{
public:
void MakeEmpty();
bool IsFull();
int LengthIs();
void RetrieveItem(ItemType &item, bool &found);
void InsertItem(ItemType item);
void DeleteItem(ItemType item);
void ResetList();
void GetNextItem(ItemType &item);
// added function as specified in the question
void SplitListsSplitLists(UnsortedType<ItemType> list, ItemType item, UnsortedType<ItemType>& list1, UnsortedType<ItemType>& list2);
private:
int length;
ItemType info[MAX_ITEMS];
int currentPos;
};
// An added SplitLists function to the Unsorted Type ADT
// This takes four arguments
// 1. UnsortedType list: The list which has to be splited
// 2. ItemType item: item is used to compare with list' item to split the list at
// 3. UnsortedType& list1: to store the values which are less than or equal to the
// given item from the given list
// 4. UnsortedType& list2: to store the values which are greater than the given item
// from the given list
template<class ItemType>
void UnsortedType::SplitLists(UnsortedType<ItemType> list, ItemType item, UnsortedType<ItemType>& list1, UnsortedType<ItemType>& list2)
{
// define the index value
int index = 0;
// declare an ItemType to hold each list's item
ItemType listItem;
// reset the list current postion
list.ResetList();
// make two empty unsorted lists by calling MakeEmpty() method
list1.MakeEmpty();
list2.MakeEmpty();
// Use a loop to split the values of list into list1 and list2
for(index = 0; index < list.LengthIs(); index++)
{
list.GetNextItem(listItem);
// condition to check whether the given list at index is
// greater than the item or not
if(listItem.ComparedTo(item) == LESS || listItem.ComparedTo(item) == EQUAL)
// if listItem is less than or equal to item then add the listItem
// to list1
list1.InsertItem(listItem);
else
//if the listItem is greater than the item then add the listItem
// to list2
list2.InsertItem(listItem);
}
}
(b) Here is the SplitLists() function for the linkedlist based:
#include <iostream>
using namespace std;
const int MAX_ITEMS = 5;
enum RelationType
{
LESS, GREATER, EQUAL
};
class ItemType
{
public:
ItemType();
RelationType ComparedTo(ItemType item);
void Print(ofstream &)const;
void Initialize(int number);
private:
int value;
};
template<class ItemType>
struct NodeType
{
ItemType info;
NodeType *next;
};
template<class ItemType>
class UnsortedType
{
public:
UnsortedType();
~UnsortedType();
void MakeEmpty();
bool IsFull() const;
int LengthIs() const;
void RetrieveItem(ItemType&, bool&);
void InsertItem(ItemType);
void DeleteItem(ItemType);
void ResetList();
bool IsLastItem() const;
void GetNextItem(ItemType&);
// added function as specified in the question
void SplitLists(UnsortedType<ItemType> list, ItemType item, UnsortedType<ItemType>& list1, UnsortedType<ItemType>& list2);
private:
int list_length;
NodeType<ItemType> *list_Data;
NodeType<ItemType> *current_Pos;
};
// An added SplitLists function to the Unsorted Type ADT
// This takes four arguments
// 1. UnsortedType list: The list which has to be splited
// 2. ItemType item: item is used to compare with list' item to split the list at
// 3. UnsortedType& list1: to store the values which are less than or equal to the
// given item from the given list
// 4. UnsortedType& list2: to store the values which are greater than the given item
// from the given list
template<class ItemType>
void UnsortedType::SplitLists(UnsortedType<ItemType> list, ItemType item, UnsortedType<ItemType>& list1, UnsortedType<ItemType>& list2)
{
// declare an ItemType to hold each list's item
ItemType listItem;
// reset the list current postion
list.ResetList();
// make two empty unsorted lists by calling MakeEmpty() method
list1.MakeEmpty();
list2.MakeEmpty();
// Use a loop to split the values of list into list1 and list2
while(!list.IsLastItem())
{
list.GetNextItem(listItem);
// condition to check whether the given list at index is
// greater than the item or not
if(listItem.ComparedTo(item) == LESS || listItem.ComparedTo(item) == EQUAL)
// if listItem is less than or equal to item then add the listItem
// to list1
list1.InsertItem(listItem);
else
//if the listItem is greater than the item then add the listItem
// to list2
list2.InsertItem(listItem);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.