Question
Use a Binary Search Tree to implement Sorted List class. The sorted list class should have all the functionalities of a regular sorted list class.
Use a Binary Search Tree to implement Sorted List class. The sorted list class
should have all the functionalities of a regular sorted list class.
In the driver file, create Sorted List object, insert a few items in it and finally print the List.
#ifndef SORTEDTYPE_H_INCLUDED
#define SORTEDTYPE_H_INCLUDED
template
class SortedType
{
struct NodeType
{
ItemType info;
NodeType* next;
};
public:
SortedType();
~SortedType();
bool IsFull();
int LengthIs();
void MakeEmpty();
bool RetrieveItem(ItemType&);
bool InsertItem(ItemType);
bool DeleteItem(ItemType);
void ResetList();
bool GetNextItem(ItemType&);
private:
int length;
NodeType* listData;
NodeType* currentPos;
};
#include "sortedtype.tpp"
#endif // SORTEDTYPE_H_INCLUDED
#include "sortedtype.h"
#include
using namespace std;
template
SortedType
{
length = 0;
listData = NULL;
currentPos = NULL;
}
template
int SortedType
{
return length;
}
template
bool SortedType
{
NodeType* location;
try
{
location = new NodeType;
delete location;
return false;
}
catch(bad_alloc& exception)
{
return true;
}
}
template
bool SortedType
{
if(IsFull())
return false;
NodeType* newNode;
newNode = new NodeType;
newNode->info = item;
NodeType* predLoc = NULL;
NodeType* location = listData;
bool moreToSearch;
//location = listData;
//predLoc = NULL;
moreToSearch = (location != NULL);
while (moreToSearch)
{
if (location->info < item)
{
predLoc = location;
location = location->next;
moreToSearch = (location != NULL);
}
else
moreToSearch = false;
}
if (predLoc == NULL)// when the item is inserted at the front of the list
{
newNode->next = listData;
listData = newNode;
}
else
{
newNode->next = location;
predLoc->next = newNode;
}
length++;
return true;
}
template
bool SortedType
{
NodeType* location = listData;
NodeType* tempLocation;
if (item == listData->info)
{
tempLocation = location;
listData = listData->next;
}
else
{
while (!(item==(location->next)->info)){
location = location->next;
if(location->next == NULL)
return false;
}
tempLocation = location->next;
location->next = (location->next)->next;
}
delete tempLocation;
length--;
return true;
}
template
bool SortedType
{
NodeType* location = listData;
bool moreToSearch = (location != NULL);
bool found = false;
while (moreToSearch && !found)
{
if (item == location->info){
found = true;
item = location->info;
}
else if (item > location->info)
{
location = location->next;
moreToSearch = (location != NULL);
}
else
moreToSearch = false;
}
return found;
}
template
void SortedType
{
NodeType* tempPtr;
while (listData != NULL)
{
tempPtr = listData;
listData = listData->next;
delete tempPtr;
}
length = 0;
}
template
SortedType
{
MakeEmpty();
}
template
void SortedType
{
currentPos = NULL;
}
template
bool SortedType
{
if (currentPos == NULL)
currentPos = listData;
else
currentPos = currentPos->next;
if(currentPos == NULL)
return false;
item = currentPos->info;
return true;
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started