Use C++ template mechanism and define a generic SortedList ADT. Implement the So

Question

Use C++ template mechanism and define a generic SortedList ADT. Implement the SortedList ADT using a single linear linked list.

Add the following methods to SortedList.cpp

ItemType get(int index);

Function: Returns the element at the specified position (index) in this list. Precondition: List is initialized.
Postcondition: The function returns the element at the specified position in this list.

or throws IndexOutOfBoundsException - if the index is out of range (index < 0 || index >= length of the list).

void printList();

Function: Prints list elements.
Precondition: list is initialized.
Postcondition: List elements are displayed on the screen.

--------------

SortedList.cpp

#include "SortedList.h"
#include <iostream>

using std::exception;
using namespace std;

template
struct NodeType
{
ItemType info;
NodeType* next;
};

template
SortedType::SortedType()// class constructor
{
length = 0;
ListData = NULL;
}

template
bool SortedType::isEmpty() const
{
return (length == 0);
}

template
bool SortedType::isFull() const
{
NodeType* location;
try
{
location = new NodeType;
delete location;
return false;
}
catch(bad_alloc exception)
{
return true;
}
}

template
int SortedType::getLength() const
{
return length;
}

template
void SortedType::insertItem (ItemType item)
{
NodeType* newNode;
NodeType* predLoc;
NodeType* location;
location = ListData;
predLoc = NULL;
bool moreSearch;
moreSearch = (location != NULL);
  
while(moreSearch)
{
if(item >location ->info)
{
predLoc = location;
location = location ->next;
moreSearch = (location != NULL);
}
else
{
moreSearch = false;
}
}
  
newNode = new NodeType;
newNode->info = item;

if(predLoc==NULL)
{
newNode->next=ListData;
ListData = newNode;
}
else
{
newNode->next = location;
predLoc->next = newNode;
}
length++;
}

template
void SortedType::deleteItem (ItemType item)
{
NodeType* location = ListData;
NodeType* tempLoc;
  
if(item == ListData->info)
{
tempLoc = location;
ListData = ListData->next;
}
else
{
while(!(item==(location->next)->info))
{
location = location->next;
}
  
tempLoc = location->next;
location->next = (location->next)->next;
}
delete tempLoc;
length--;
}

template
void SortedType::makeEmpty()
{
NodeType* tempPtr;
while (ListData != NULL)
{
tempPtr = ListData;
ListData = ListData->next;
delete tempPtr;
}
length = 0;
}

template
ItemType SortedType::get(int index)
{

}

template
void SortedType::printList(std::ostream &out)
{

}

template
bool SortedType::findItem(ItemType item)
{
NodeType* location;
bool moreSearch;
bool found = false;
moreSearch = (location !=NULL);
  
while(moreSearch && !found)
{
if(location->info < item)
{
location = location->next;
moreSearch = (location!=NULL);
}
else if (item == location->info)
{
found = true;
item = location->info;
}
else
moreSearch = false;
}
return found;
}

----------------------------

SortedList.h

#include <iostream>

template <class ItemType>
struct NodeType;

template <class ItemType>
class SortedType
{
public:

SortedType();
bool isEmpty() const;
bool isFull() const;
int getLength() const;
void insertItem(ItemType item);
void deleteItem(ItemType item);
ItemType get(int index);
void makeEmpty();
void printList(std::ostream &out);
~SortedType();
bool findItem(ItemType item);
  
private:
NodeType<ItemType>* ListData;
int length;
};

Explanation / Answer

Answer for the Question:

I have written the two fujctions asked the printlist and getIndex data..see the below code.

template <class ItemType>
ItemType SortedType::get(int index)
{
   NodeType* tempPtr;
   tempPtr = ListData;
   int i =0;
   while (tempPtr!=NULL)
   {      
       if(i==index)
       {
           return tempPtr->info;
           break;
       }
       tempPtr = tempPtr->next;
       i++;
      
   }
}

template <class ItemType>
void SortedType::printList(std::ostream &out)
{
   NodeType* tempPtr;
   tempPtr = ListData;
   while (tempPtr != NULL)
   {      
       tempPtr = tempPtr->next;
       out<<tempPtr->info;
   }
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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