1) Use the implementation of Sorted linked list we used in class(SortLinkLst.h)
ID: 3756775 • Letter: 1
Question
1) Use the implementation of Sorted linked list we used in class(SortLinkLst.h) and make the following changes. When we implemented, the items were being included in ascending order.
Change the list to accommodate the items in descending order. Use string as the item under consideration. (15 points)
The Link list should be a list of strings. Strings should be included in the list in descending order of the alphabet.
So for example if you are inserting the following strings “cart “, “mart “, “dart “, “part”, “art”
The strings should be included in descending order of the alphabet which is the following order
part mart dart cart and art
where the listData or header should point to ‘part’ which is the highest string in descending order.
Add the following two functions besides the regular ones:
public boolean findWordEndIn(char endAlphabet) (15 points)
// checks for the first word in the list which ends with a particular alphabet. For example if char ‘w’ is passed in it should return true if there is any word in the list which ends in w like saw or slaw etc. If there are more than one word you can stop with the first one and return true. Don’t need to search anymore.
public void displayListBackwards() ( 20 points) // prints the list in ascending order of alphabets
// displays the words in the reverse alphabetic order. So for example if the list is
‘part mart dart cart art’
//it should print out the list in reverse order.
art, cart, dart, mart, part
You can add any other constructors or methods if needed to implement this.
SortedLinkLst.h:
#include <iostream>
using namespace std;
template<class ItemType>
struct NodeType
{
ItemType info;
NodeType<ItemType>* next;
};
template<class ItemType>
class SortedType
{
public:
SortedType();
void MakeEmpty();
bool IsFull() const;
int GetLength() const;
ItemType GetItem(ItemType item, bool& found);
void PutItem(ItemType item);
void DeleteItem(ItemType item);
void ResetList();
ItemType GetNextItem();
void PrintItem(SortedType u);
private:
NodeType<ItemType> * listData;
int length;
NodeType<ItemType>* currentPos;
};
template<class ItemType>
SortedType<ItemType>::SortedType() // Class constructor
{
length = 0;
listData = NULL;
}
template<class ItemType>
bool SortedType<ItemType>::IsFull() const
// Returns true if there is no room for another ItemType
// on the free store; false otherwise.
{
NodeType<ItemType>* location;
try
{
location = new NodeType;
delete location;
return false;
}
catch (std::bad_alloc exception)
{
return true;
}
}
template<class ItemType>
int SortedType<ItemType>::GetLength() const
// Post: Number of items in the list is returned.
{
return length;
}
template<class ItemType>
void SortedType<ItemType>::MakeEmpty()
// Post: List is empty; all items have been deallocated.
{
NodeType<ItemType>* tempPtr;
while (listData != NULL)
{
tempPtr = listData;
listData = listData->next;
delete tempPtr;
}
length = 0;
}
template<class ItemType>
void SortedType<ItemType>::PutItem(ItemType item)
// item is in the list; length has been incremented.
{
NodeType<ItemType> * newNode; //pointer to node being inserted
NodeType<ItemType> * predLoc; // Trailing Pointer
NodeType<ItemType> * location; // traveling pointer to a node
bool moreToSearch;
location = listData;
predLoc = NULL;
moreToSearch = (location != NULL);
while (moreToSearch)
{
if (item > location->info)
{
predLoc = location;
location = location->next;
moreToSearch = (location != NULL);
}
else if (item < location->info)
{
moreToSearch = false;
break;
}
}
newNode = new NodeType<ItemType>;
newNode->info = item;
if (predLoc == NULL) //Insert as first
{
newNode->next = listData;
listData = newNode;
}
else
{
newNode->next = location;
predLoc->next = newNode;
}
length++; // Increment length of the list
}
template<class ItemType>
ItemType SortedType<ItemType>::GetItem(ItemType item, bool& found)
// Pre: Key member(s) of item is initialized.
// Post: If found, item's key matches an element's key in the
// list and a copy of that element has been returned;
// otherwise, item is returned.
{
bool moreToSearch;
NodeType<ItemType> * location;
location = listData;
found = false;
moreToSearch = (location != NULL);
while (moreToSearch && !found)
{
if(item == location->info)
{
found = true;
item = location->info;
break;
}
else if (item > location->info)
{
location = location->next;
moreToSearch = (location != NULL);
}
else
{
moreToSearch = false;
break;
}
}
return item;
}
template<class ItemType>
void SortedType<ItemType>::DeleteItem(ItemType item)
// Pre: item's key has been initialized.
// An element in the list has a key that matches item's.
// Post: No element in the list has a key that matches item's.
{
NodeType<ItemType>* tempLocation = NULL;
NodeType<ItemType> * predLoc; // Trailing Pointer
NodeType<ItemType> * location; // traveling pointer to a node
bool moreToSearch;
location = listData;
predLoc = NULL;
moreToSearch = (location != NULL);
// Locate node to be deleted.
if (item == listData->info)
{
tempLocation = location;
listData = listData->next; // Delete first node.
}
else
{
while (moreToSearch)
{
if (item == location->info)
{
moreToSearch = false;
predLoc->next = location->next;
tempLocation = location;
}
else if (item > location->info)
{
predLoc = location;
location = location->next;
moreToSearch = (location != NULL);
}
else if (item < location->info)
{
moreToSearch = false;
break;
}
}
}
delete tempLocation;
length--;
}
template<class ItemType>
void SortedType<ItemType>::ResetList()
// Post: Current position has been initialized.
{
currentPos = NULL;
}
template<class ItemType>
ItemType SortedType<ItemType>::GetNextItem()
// Post: A copy of the next item in the list is returned.
// When the end of the list is reached, currentPos
// is reset to begin again.
{
ItemType item;
if (currentPos == NULL)
currentPos = listData;
item = currentPos->info;
currentPos = currentPos->next;
return item;
}
template<class ItemType>
void SortedType<ItemType>::PrintItem(SortedType list)
// Pre: list has been initialized.
// dataFile is open for writing.
// Post: Each component in list has been written to dataFile.
// dataFile is still open.
{
int length;
ItemType item;
list.ResetList();
length = list.GetLength();
if (length == 0)
cout << "List is Empty";
for (int counter = 1; counter <= length; counter++)
{
item = list.GetNextItem();
cout << item << " ";
}
cout << endl;
}
Explanation / Answer
#include <iostream>
//for knowing the type of any variable.
#include <typeinfo>
//for standard string class
#include <string>
//for backward list
#include <list>
#include <iterator>
using namespace std;
template<class ItemType>
struct NodeType
{
ItemType info;
NodeType<ItemType>* next;
};
template<class ItemType>
class SortedType
{
public:
SortedType();
void MakeEmpty();
bool IsFull() const;
int GetLength() const;
ItemType GetItem(ItemType item, bool& found);
void PutItem(ItemType item);
void DeleteItem(ItemType item);
void ResetList();
ItemType GetNextItem();
void PrintItem(SortedType u);
bool findWordEndIn(char endAlphabet);
void displayListBackwards();
private:
NodeType<ItemType> * listData;
int length;
NodeType<ItemType>* currentPos;
};
template<class ItemType>
SortedType<ItemType>::SortedType() // Class constructor
{
length = 0;
listData = NULL;
}
template<class ItemType>
bool SortedType<ItemType>::IsFull() const
// Returns true if there is no room for another ItemType
// on the free store; false otherwise.
{
NodeType<ItemType>* location;
try
{
location = new NodeType;
delete location;
return false;
}
catch (std::bad_alloc exception)
{
return true;
}
}
template<class ItemType>
int SortedType<ItemType>::GetLength() const
// Post: Number of items in the list is returned.
{
return length;
}
template<class ItemType>
void SortedType<ItemType>::MakeEmpty()
// Post: List is empty; all items have been deallocated.
{
NodeType<ItemType>* tempPtr;
while (listData != NULL)
{
tempPtr = listData;
listData = listData->next;
delete tempPtr;
}
length = 0;
}
template<class ItemType>
void SortedType<ItemType>::PutItem(ItemType item)
// item is in the list; length has been incremented.
{
NodeType<ItemType> * newNode; //pointer to node being inserted
NodeType<ItemType> * predLoc; // Trailing Pointer
NodeType<ItemType> * location; // traveling pointer to a node
bool moreToSearch;
location = listData;
predLoc = NULL;
moreToSearch = (location != NULL);
while (moreToSearch)
{
bool itemGreaterThanCurrentData = false;
//if the node data os of string type
if(typeid(location->info) == typeid(string))
{
if(strcmp(item, location->info) > 0)
itemGreaterThanCurrentData = true;
}
else
{
if(item > location->info)
itemGreaterThanCurrentData = true;
}
if (itemGreaterThanCurrentData)
{
moreToSearch = false;
break;
}
else
{
predLoc = location;
location = location->next;
moreToSearch = (location != NULL);
}
}
newNode = new NodeType<ItemType>;
newNode->info = item;
if (predLoc == NULL) //Insert as first
{
newNode->next = listData;
listData = newNode;
}
else
{
newNode->next = location;
predLoc->next = newNode;
}
length++; // Increment length of the list
}
template<class ItemType>
ItemType SortedType<ItemType>::GetItem(ItemType item, bool& found)
// Pre: Key member(s) of item is initialized.
// Post: If found, item's key matches an element's key in the
// list and a copy of that element has been returned;
// otherwise, item is returned.
{
bool moreToSearch;
NodeType<ItemType> * location;
location = listData;
found = false;
moreToSearch = (location != NULL);
while (moreToSearch && !found)
{
bool itemMatched = false;
bool itemGreaterThanCurrentData = false;
if(typeid(location->info) == typeid(string))
{
if(strcmp(item, location->info) == 0)
itemMatched = true;
else if(strcmp(item, location->info) > 0)
itemGreaterThanCurrentData = true;
}
else
{
if(item == location->info)
itemMatched = true;
else if (item > location->info)
itemGreaterThanCurrentData = true;
}
if(itemMatched)
{
found = true;
item = location->info;
break;
}
else if (itemGreaterThanCurrentData)
{
location = location->next;
moreToSearch = (location != NULL);
}
else
{
moreToSearch = false;
break;
}
}
return item;
}
template<class ItemType>
void SortedType<ItemType>::DeleteItem(ItemType item)
// Pre: item's key has been initialized.
// An element in the list has a key that matches item's.
// Post: No element in the list has a key that matches item's.
{
NodeType<ItemType>* tempLocation = NULL;
NodeType<ItemType> * predLoc; // Trailing Pointer
NodeType<ItemType> * location; // traveling pointer to a node
bool moreToSearch;
location = listData;
predLoc = NULL;
moreToSearch = (location != NULL);
// Locate node to be deleted.
if (item == listData->info)
{
tempLocation = location;
listData = listData->next; // Delete first node.
}
else
{
while (moreToSearch)
{
bool itemMatched = false;
bool itemGreaterThanCurrentData = false;
if(typeid(location->info) == typeid(string))
{
if(strcmp(item, location->info) == 0)
itemMatched = true;
else if(strcmp(item, location->info) > 0)
itemGreaterThanCurrentData = true;
}
else
{
if(item == location->info)
itemMatched = true;
else if (item > location->info)
itemGreaterThanCurrentData = true;
}
if (itemMatched)
{
moreToSearch = false;
predLoc->next = location->next;
tempLocation = location;
}
else if (itemGreaterThanCurrentData)
{
predLoc = location;
location = location->next;
moreToSearch = (location != NULL);
}
else
{
moreToSearch = false;
break;
}
}
}
delete tempLocation;
length--;
}
template<class ItemType>
void SortedType<ItemType>::ResetList()
// Post: Current position has been initialized.
{
currentPos = NULL;
}
template<class ItemType>
ItemType SortedType<ItemType>::GetNextItem()
// Post: A copy of the next item in the list is returned.
// When the end of the list is reached, currentPos
// is reset to begin again.
{
ItemType item;
if (currentPos == NULL)
currentPos = listData;
item = currentPos->info;
currentPos = currentPos->next;
return item;
}
template<class ItemType>
void SortedType<ItemType>::PrintItem(SortedType list)
// Pre: list has been initialized.
// dataFile is open for writing.
// Post: Each component in list has been written to dataFile.
// dataFile is still open.
{
int length;
ItemType item;
list.ResetList();
length = list.GetLength();
if (length == 0)
cout << "List is Empty";
for (int counter = 1; counter <= length; counter++)
{
item = list.GetNextItem();
cout << item << " ";
}
cout << endl;
}
template<class ItemType>
bool SortedType<ItemType>::findWordEndIn(char endAlphabet){
NodeType<ItemType> * location; // traveling pointer to a node
bool moreToSearch;
location = listData;
moreToSearch = (location != NULL);
while(moreToSearch){
string currentItem = location->info;
//compares the last character
if(currentItem[currentItem.length() - 1] == endAlphabet)
return true;
else
{
location = location->next;
moreToSearch = (location != NULL);
}
}
return false;
}
template<class ItemType>
void SortedType<ItemType>::displayListBackwards(){
list <int> :: iterator itr;
list<string> backwardList;
int length;
ItemType item;
list.ResetList();
length = list.GetLength();
if (length == 0)
cout << "List is Empty";
for (int counter = 1; counter <= length; counter++)
backwardList.push_front(list.GetNextItem());
for(itr = backwardList.begin(); it != backwardList.end(); ++it)
cout << *itr<<" ";
cout << ' ';
return;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.