16.1)<in C++>Extend the class linkedListType by adding the following operations:
ID: 3832110 • Letter: 1
Question
16.1)<in C++>Extend the class linkedListType by adding the following operations:
(below)Find and delete the node with the smallest info in the list. (Delete only the first occurrence and traverse the list only once.)
(below)Find and delete all occurrences of a given info from the list. (Traverse the list only once.). For example, if the original list looks like this: 1, 2, 3, 4, 2, 5, 2 the revised list should look like this after deleting all occurrences of nodes with 2 in the info field: 1, 3, 4, 5
Add these as abstract functions in the class linkedListType and provide the definitions of these functions in the class unorderedLinkedList. Also, write a program to test these functions.(mostly what i'm having trouble with please type it out so i can read it)
Turn in
All your template files
Your test program
The results of running your test program
below is the source code for linkedlistType and unorderedlinkedListType:
#ifndef H_LinkedListType
#define H_LinkedListType
#include
#include
using namespace std;
//Definition of the node
template
struct nodeType
{
Type info;
nodeType *link;
};
template
class linkedListIterator
{
public:
linkedListIterator();
//Default constructor
//Postcondition: current = NULL;
linkedListIterator(nodeType *ptr);
//Constructor with a parameter.
//Postcondition: current = ptr;
Type operator*();
//Function to overload the dereferencing operator *.
//Postcondition: Returns the info contained in the node.
linkedListIterator operator++();
//Overload the pre-increment operator.
//Postcondition: The iterator is advanced to the next
// node.
bool operator==(const linkedListIterator& right) const;
//Overload the equality operator.
//Postcondition: Returns true if this iterator is equal to
// the iterator specified by right,
// otherwise it returns the value false.
bool operator!=(const linkedListIterator& right) const;
//Overload the not equal to operator.
//Postcondition: Returns true if this iterator is not
// equal to the iterator specified by
// right; otherwise it returns the value
// false.
private:
nodeType *current; //pointer to point to the current
//node in the linked list
};
template
linkedListIterator::linkedListIterator()
{
current = NULL;
}
template
linkedListIterator::
linkedListIterator(nodeType *ptr)
{
current = ptr;
}
template
Type linkedListIterator::operator*()
{
return current->info;
}
template
linkedListIterator linkedListIterator::operator++()
{
current = current->link;
return *this;
}
template
bool linkedListIterator::operator==
(const linkedListIterator& right) const
{
return (current == right.current);
}
template
bool linkedListIterator::operator!=
(const linkedListIterator& right) const
{ return (current != right.current);
}
//***************** class linkedListType ****************
template
class linkedListType
{
public:
const linkedListType& operator=
(const linkedListType&);
//Overload the assignment operator.
void initializeList();
//Initialize the list to an empty state.
//Postcondition: first = NULL, last = NULL, count = 0;
bool isEmptyList() const;
//Function to determine whether the list is empty.
//Postcondition: Returns true if the list is empty,
// otherwise it returns false.
void print() const;
//Function to output the data contained in each node.
//Postcondition: none
int length() const;
//Function to return the number of nodes in the list.
//Postcondition: The value of count is returned.
void destroyList();
//Function to delete all the nodes from the list.
//Postcondition: first = NULL, last = NULL, count = 0;
Type front() const;
//Function to return the first element of the list.
//Precondition: The list must exist and must not be
// empty.
//Postcondition: If the list is empty, the program
// terminates; otherwise, the first
// element of the list is returned.
Type back() const;
//Function to return the last element of the list.
//Precondition: The list must exist and must not be
// empty.
//Postcondition: If the list is empty, the program
// terminates; otherwise, the last
// element of the list is returned.
virtual bool search(const Type& searchItem) const = 0;
//Function to determine whether searchItem is in the list.
//Postcondition: Returns true if searchItem is in the
// list, otherwise the value false is
// returned.
virtual void insertFirst(const Type& newItem) = 0;
//Function to insert newItem at the beginning of the list.
//Postcondition: first points to the new list, newItem is
// inserted at the beginning of the list,
// last points to the last node in the list,
// and count is incremented by 1.
virtual void insertLast(const Type& newItem) = 0;
//Function to insert newItem at the end of the list.
//Postcondition: first points to the new list, newItem
// is inserted at the end of the list,
// last points to the last node in the list,
// and count is incremented by 1.
virtual void deleteNode(const Type& deleteItem) = 0;
//Function to delete deleteItem from the list.
//Postcondition: If found, the node containing
// deleteItem is deleted from the list.
// first points to the first node, last
// points to the last node of the updated
// list, and count is decremented by 1.
linkedListIterator begin();
//Function to return an iterator at the begining of the
//linked list.
//Postcondition: Returns an iterator such that current is
// set to first.
linkedListIterator end();
//Function to return an iterator one element past the
//last element of the linked list.
//Postcondition: Returns an iterator such that current is
// set to NULL.
linkedListType();
//default constructor
//Initializes the list to an empty state.
//Postcondition: first = NULL, last = NULL, count = 0;
linkedListType(const linkedListType& otherList);
//copy constructor
~linkedListType();
//destructor
//Deletes all the nodes from the list.
//Postcondition: The list object is destroyed.
protected:
int count; //variable to store the number of
//elements in the list
nodeType *first; //pointer to the first node of the list
nodeType *last; //pointer to the last node of the list
private:
void copyList(const linkedListType& otherList);
//Function to make a copy of otherList.
//Postcondition: A copy of otherList is created and
// assigned to this list.
};
template
bool linkedListType::isEmptyList() const
{
return(first == NULL);
}
template
linkedListType::linkedListType() //default constructor
{
first = NULL;
last = NULL;
count = 0;
}
template
void linkedListType::destroyList()
{
nodeType *temp; //pointer to deallocate the memory
//occupied by the node
while (first != NULL) //while there are nodes in the list
{
temp = first; //set temp to the current node
first = first->link; //advance first to the next node
delete temp; //deallocate the memory occupied by temp
}
last = NULL; //initialize last to NULL; first has already
//been set to NULL by the while loop
count = 0;
}
template
void linkedListType::initializeList()
{
destroyList(); //if the list has any nodes, delete them
}
template
void linkedListType::print() const
{
nodeType *current; //pointer to traverse the list
current = first; //set current so that it points to
//the first node
while (current != NULL) //while more data to print
{
cout << current->info << " ";
current = current->link;
}
}//end print
template
int linkedListType::length() const
{
return count;
} //end length
template
Type linkedListType::front() const
{
assert(first != NULL);
return first->info; //return the info of the first node
}//end front
template
Type linkedListType::back() const
{
assert(last != NULL);
return last->info; //return the info of the last node
}//end back
template
linkedListIterator linkedListType::begin()
{
linkedListIterator temp(first);
return temp;
}
template
linkedListIterator linkedListType::end()
{
linkedListIterator temp(NULL);
return temp;
}
template
void linkedListType::copyList
(const linkedListType& otherList)
{
nodeType *newNode; //pointer to create a node
nodeType *current; //pointer to traverse the list
if (first != NULL) //if the list is nonempty, make it empty
destroyList();
if (otherList.first == NULL) //otherList is empty
{
first = NULL;
last = NULL;
count = 0;
}
else
{
current = otherList.first; //current points to the
//list to be copied
count = otherList.count;
//copy the first node
first = new nodeType; //create the node
first->info = current->info; //copy the info
first->link = NULL; //set the link field of
//the node to NULL
last = first; //make last point to the
//first node
current = current->link; //make current point to
//the next node
//copy the remaining list
while (current != NULL)
{
newNode = new nodeType; //create a node
newNode->info = current->info; //copy the info
newNode->link = NULL; //set the link of
//newNode to NULL
last->link = newNode; //attach newNode after last
last = newNode; //make last point to
//the actual last node
current = current->link; //make current point
//to the next node
}//end while
}//end else
}//end copyList
template
linkedListType::~linkedListType() //destructor
{
destroyList();
}//end destructor
template
linkedListType::linkedListType
(const linkedListType& otherList)
{
first = NULL;
copyList(otherList);
}//end copy constructor
//overload the assignment operator
template
const linkedListType& linkedListType::operator=
(const linkedListType& otherList)
{
if (this != &otherList) //avoid self-copy
{
copyList(otherList);
}//end else
return *this;
}
#endif
#ifndef H_LinkedListType
#define H_LinkedListType
#include
#include
using namespace std;
//Definition of the node
template
struct nodeType
{
Type info;
nodeType *link;
};
template
class linkedListIterator
{
public:
linkedListIterator();
//Default constructor
//Postcondition: current = NULL;
linkedListIterator(nodeType *ptr);
//Constructor with a parameter.
//Postcondition: current = ptr;
Type operator*();
//Function to overload the dereferencing operator *.
//Postcondition: Returns the info contained in the node.
linkedListIterator operator++();
//Overload the pre-increment operator.
//Postcondition: The iterator is advanced to the next
// node.
bool operator==(const linkedListIterator& right) const;
//Overload the equality operator.
//Postcondition: Returns true if this iterator is equal to
// the iterator specified by right,
// otherwise it returns the value false.
bool operator!=(const linkedListIterator& right) const;
//Overload the not equal to operator.
//Postcondition: Returns true if this iterator is not
// equal to the iterator specified by
// right; otherwise it returns the value
// false.
private:
nodeType *current; //pointer to point to the current
//node in the linked list
};
template
linkedListIterator::linkedListIterator()
{
current = NULL;
}
template
linkedListIterator::
linkedListIterator(nodeType *ptr)
{
current = ptr;
}
template
Type linkedListIterator::operator*()
{
return current->info;
}
template
linkedListIterator linkedListIterator::operator++()
{
current = current->link;
return *this;
}
template
bool linkedListIterator::operator==
(const linkedListIterator& right) const
{
return (current == right.current);
}
template
bool linkedListIterator::operator!=
(const linkedListIterator& right) const
{ return (current != right.current);
}
//***************** class linkedListType ****************
template
class linkedListType
{
public:
const linkedListType& operator=
(const linkedListType&);
//Overload the assignment operator.
void initializeList();
//Initialize the list to an empty state.
//Postcondition: first = NULL, last = NULL, count = 0;
bool isEmptyList() const;
//Function to determine whether the list is empty.
//Postcondition: Returns true if the list is empty,
// otherwise it returns false.
void print() const;
//Function to output the data contained in each node.
//Postcondition: none
int length() const;
//Function to return the number of nodes in the list.
//Postcondition: The value of count is returned.
void destroyList();
//Function to delete all the nodes from the list.
//Postcondition: first = NULL, last = NULL, count = 0;
Type front() const;
//Function to return the first element of the list.
//Precondition: The list must exist and must not be
// empty.
//Postcondition: If the list is empty, the program
// terminates; otherwise, the first
// element of the list is returned.
Type back() const;
//Function to return the last element of the list.
//Precondition: The list must exist and must not be
// empty.
//Postcondition: If the list is empty, the program
// terminates; otherwise, the last
// element of the list is returned.
virtual bool search(const Type& searchItem) const = 0;
//Function to determine whether searchItem is in the list.
//Postcondition: Returns true if searchItem is in the
// list, otherwise the value false is
// returned.
virtual void insertFirst(const Type& newItem) = 0;
//Function to insert newItem at the beginning of the list.
//Postcondition: first points to the new list, newItem is
// inserted at the beginning of the list,
// last points to the last node in the list,
// and count is incremented by 1.
virtual void insertLast(const Type& newItem) = 0;
//Function to insert newItem at the end of the list.
//Postcondition: first points to the new list, newItem
// is inserted at the end of the list,
// last points to the last node in the list,
// and count is incremented by 1.
virtual void deleteNode(const Type& deleteItem) = 0;
//Function to delete deleteItem from the list.
//Postcondition: If found, the node containing
// deleteItem is deleted from the list.
// first points to the first node, last
// points to the last node of the updated
// list, and count is decremented by 1.
linkedListIterator begin();
//Function to return an iterator at the begining of the
//linked list.
//Postcondition: Returns an iterator such that current is
// set to first.
linkedListIterator end();
//Function to return an iterator one element past the
//last element of the linked list.
//Postcondition: Returns an iterator such that current is
// set to NULL.
linkedListType();
//default constructor
//Initializes the list to an empty state.
//Postcondition: first = NULL, last = NULL, count = 0;
linkedListType(const linkedListType& otherList);
//copy constructor
~linkedListType();
//destructor
//Deletes all the nodes from the list.
//Postcondition: The list object is destroyed.
protected:
int count; //variable to store the number of
//elements in the list
nodeType *first; //pointer to the first node of the list
nodeType *last; //pointer to the last node of the list
private:
void copyList(const linkedListType& otherList);
//Function to make a copy of otherList.
//Postcondition: A copy of otherList is created and
// assigned to this list.
};
template
bool linkedListType::isEmptyList() const
{
return(first == NULL);
}
template
linkedListType::linkedListType() //default constructor
{
first = NULL;
last = NULL;
count = 0;
}
template
void linkedListType::destroyList()
{
nodeType *temp; //pointer to deallocate the memory
//occupied by the node
while (first != NULL) //while there are nodes in the list
{
temp = first; //set temp to the current node
first = first->link; //advance first to the next node
delete temp; //deallocate the memory occupied by temp
}
last = NULL; //initialize last to NULL; first has already
//been set to NULL by the while loop
count = 0;
}
template
void linkedListType::initializeList()
{
destroyList(); //if the list has any nodes, delete them
}
template
void linkedListType::print() const
{
nodeType *current; //pointer to traverse the list
current = first; //set current so that it points to
//the first node
while (current != NULL) //while more data to print
{
cout << current->info << " ";
current = current->link;
}
}//end print
template
int linkedListType::length() const
{
return count;
} //end length
template
Type linkedListType::front() const
{
assert(first != NULL);
return first->info; //return the info of the first node
}//end front
template
Type linkedListType::back() const
{
assert(last != NULL);
return last->info; //return the info of the last node
}//end back
template
linkedListIterator linkedListType::begin()
{
linkedListIterator temp(first);
return temp;
}
template
linkedListIterator linkedListType::end()
{
linkedListIterator temp(NULL);
return temp;
}
template
void linkedListType::copyList
(const linkedListType& otherList)
{
nodeType *newNode; //pointer to create a node
nodeType *current; //pointer to traverse the list
if (first != NULL) //if the list is nonempty, make it empty
destroyList();
if (otherList.first == NULL) //otherList is empty
{
first = NULL;
last = NULL;
count = 0;
}
else
{
current = otherList.first; //current points to the
//list to be copied
count = otherList.count;
//copy the first node
first = new nodeType; //create the node
first->info = current->info; //copy the info
first->link = NULL; //set the link field of
//the node to NULL
last = first; //make last point to the
//first node
current = current->link; //make current point to
//the next node
//copy the remaining list
while (current != NULL)
{
newNode = new nodeType; //create a node
newNode->info = current->info; //copy the info
newNode->link = NULL; //set the link of
//newNode to NULL
last->link = newNode; //attach newNode after last
last = newNode; //make last point to
//the actual last node
current = current->link; //make current point
//to the next node
}//end while
}//end else
}//end copyList
template
linkedListType::~linkedListType() //destructor
{
destroyList();
}//end destructor
template
linkedListType::linkedListType
(const linkedListType& otherList)
{
first = NULL;
copyList(otherList);
}//end copy constructor
//overload the assignment operator
template
const linkedListType& linkedListType::operator=
(const linkedListType& otherList)
{
if (this != &otherList) //avoid self-copy
{
copyList(otherList);
}//end else
return *this;
}
#endif
template <class Type>
void unorderedLinkedList<Type>::deleteSmallest()
{
nodeType<Type> *current; //pointer to traverse the list
nodeType<Type> *trailCurrent; //pointer just before current
nodeType<Type> *small; // pointer to findout smallest element
nodeType<Type> *trailSmall;
if (first == NULL) //Check if the list is empty
cout << "Cannot delete from an empty list." << endl;
elseif (first->link == NULL) //conditions to execute if list is not empty
{
first = NULL;
delete last;
last = NULL;
}
else
{
small = first;
trailCurrent = first;
current = first->link;
while (current != NULL) //Check whether current node is null
{
if (small->info > current->info)
{
trailSmall = trailCurrent;
small = current;
}
trailCurrent = current;
current = current->link;
}
if (small == first)
first = first->link;
else
{
trailSmall->link = small->link;
if (small == last)
last = trailSmall;
}
delete small;
}
}
b.
// Find and delete all occurrences of a given info from the list.
template<class Type>
void linkedListType<Type>::deleteAll(const Type& deleteItem)
{
nodeType<Type> *current; //pointer to traverse the list
nodeType<Type> *trailCurrent; //pointer just before current
if(first == NULL) //Check if list is empty.
cout<<"Cannot delete from an empty list. ";
else
{
current = first;
while(current != NULL)
{
if(current->info == deleteItem)
{
if(current == first)
{
first = first->link;
delete current;
current = first;
if(first == NULL)
last = NULL;
}
else
{
trailCurrent->link = current->link;
if(current == last)
last = trailCurrent;
delete current;
current = trailCurrent-> link;
}
}
else
{
trailCurrent = current;
current = current->link;
}
} // end while
}
} //end deleteAll
Explanation / Answer
//LinkedList.h - defines a linked list
#include <iostream>
using namespace std;
template<class T>
struct nodeType
{
T info; //some arb data - eg to contain a pointer to a class
nodeType<T> *link;
};
template <class T>
class linkedListType
{
public:
void initializeList();
//function to initialize first element in list to zero
//postcondition: first=NULL last=NULL
bool isEmpty();
//function to see if list contains elements
int Length();
//function to return the number of elements initialized in the list
T firstItem();
//function to return the first item in the list
T lastItem();
//function to return the last item in the list
void appendItem(const T& newItem);
//function to append an item to the list
linkedListType();
//constructor
~linkedListType();
//destructor
protected:
nodeType<T> *first; //pointer to first node
nodeType<T> *last; //pointer to last node
int count; //stores number of items in the list
};
template<class T>
bool linkedListType<T>::isEmpty()
{
return(first==NULL);
}
template<class T>
linkedListType<T>::linkedListType()
{
first=NULL;
last=NULL;
count=0;
}
template<class T>
linkedListType<T>::~linkedListType()
{
nodeType<T> *temp;
while(first!=NULL)
{
temp=first;
first=first->link;
delete temp;
}
last=NULL;
count=0;
}
template<class T>
linkedListType<T>::Length()
{
return count;
}
template<class T>
T linkedListType<T>::firstItem()
{
if(!isEmpty())
{
return first->info;
//NB: return the first node's data member eg: return any object
}
else
{
return NULL;
}
}
template<class T>
T linkedListType<T>::lastItem()
{
if(!isEmpty())
{
return last->info;
//NB: return the first node's data member eg: return any object
}
else
{
return NULL;
}
}
template<class T>
void linkedListType<T>::appendItem(const T& newItem)
{
nodeType<T> newNode;
newNode->info=newItem;
last->link=newNode;
last=newNode;
count++;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.