CSE225L Lab 10 -Unsorted List (linked list based) Solution

In today’s lab we will design and implement the List ADT where the items in the list are unsorted.
unsortedtype.h

#ifndef UNSORTEDTYPE_H_INCLUDED
#define UNSORTEDTYPE_H_INCLUDED

template <class ItemType> class UnsortedType
{
struct NodeType
{
ItemType info;
NodeType* next;
}; public:
UnsortedType(); ~UnsortedType(); bool IsFull(); int LengthIs(); void MakeEmpty();
void RetrieveItem(ItemType&, bool&);
void InsertItem(ItemType); void DeleteItem(ItemType); void ResetList();
void GetNextItem(ItemType&); private:
NodeType* listData; int length;
NodeType* currentPos;
};

#endif // UNSORTEDTYPE_H_INCLUDED

unsortedtype.cpp

#include "unsortedtype.h" #include <iostream> using namespace std;

template <class ItemType>
UnsortedType<ItemType>::UnsortedType()
{
length = 0; listData = NULL; currentPos = NULL;
}
template <class ItemType>
int UnsortedType<ItemType>::LengthIs()
{
return length;
}
template<class ItemType>
bool UnsortedType<ItemType>::IsFull()
{
NodeType* location; try {
location = new NodeType; delete location; return false;
}
catch(bad_alloc& exception)
{
return true;
}
} template <class ItemType>
void UnsortedType<ItemType>::InsertItem(ItemType item)
{
NodeType* location; location = new NodeType; location->info = item; location->next = listData; listData = location; length++;
}
template <class ItemType>
void UnsortedType<ItemType>::DeleteItem(ItemType item)
{
NodeType* location = listData; NodeType* tempLocation; if (item == listData->info)
{
tempLocation = location; listData = listData->next;
} else {
while (!(item==(location->next)->info)) location = location->next; tempLocation = location->next;
location->next = (location->next)->next;
}
delete tempLocation; length--;
}
template <class ItemType>
void UnsortedType<ItemType>::RetrieveItem(ItemType& item, bool& found)
{
NodeType* location = listData; bool moreToSearch = (location != NULL); found = false;
while (moreToSearch && !found)
{
if (item == location->info) found = true; else {
location = location->next;
moreToSearch = (location != NULL);
}
}
}
template <class ItemType>
void UnsortedType<ItemType>::MakeEmpty()
{
NodeType* tempPtr; while (listData != NULL)
{
tempPtr = listData; listData = listData->next; delete tempPtr;
}
length = 0;
}
template <class ItemType>
UnsortedType<ItemType>::~UnsortedType()
{
MakeEmpty();
}

template <class ItemType>
void UnsortedType<ItemType>::ResetList()
{
currentPos = NULL;
}
template <class ItemType>
void UnsortedType<ItemType>::GetNextItem(ItemType& item)
{
if (currentPos == NULL) currentPos = listData; else
currentPos = currentPos->next; item = currentPos->info; }

Generate the driver file (main.cpp) where you perform the following tasks. Note that you cannot make any change to the header file or the source file.
Operation to Be Tested and Description of Action Input Values
• You are given two sequences of integers arranged in ascending order. Your task is to combine the sequences into one ascending sequence. In order to get full marks, you have to make sure that the time complexity of combining two sequences is O(N). You can safely assume that no integer will be repeated. Input starts with a positive integer m which specifies the number of elements in the first sequence. Next m values are the elements in the first sequence. The next positive integer n specifies the number of elements in the second sequence. Next n values are the elements in the second sequence. The output is the combined sequence. 10 1 5 6 10 14 20 25 31 38 40
12 2 4 7 9 16 19 23 24 32 35 36 42
Expected Output
1 2 4 5 6 7 9 10 14 16 19 20 23 24
25 31 32 35 36 38 40 42