Question
intLinkedList.h #ifndef H_intLinkedList #define H_intLinkedList #include unorderedLinkedList.h using namespace std; class intLinkedList: public unorderedLinkedList { public: // part a void splitEvensOddsList(intLinkedList &evensList, intLinkedList &oddLsist); //Function
intLinkedList.h
#ifndef H_intLinkedList #define H_intLinkedList
#include "unorderedLinkedList.h" using namespace std;
class intLinkedList: public unorderedLinkedList { public: // part a void splitEvensOddsList(intLinkedList &evensList, intLinkedList &oddLsist); //Function to rearrange the nodes of the linked list so //that evensList consists of even integers and oddsList //consists of odd integers. //Postcondition: evensList consists of even integers. // oddsList consists of odd integers. // The original list is empty. };
// part a void intLinkedList::splitEvensOddsList(intLinkedList &evensList, intLinkedList &oddsList) {
// write the definition for your splitEvenOddList function here
}//end splitEvenOddList
#endif
*******************************************************************************
linkedlist.h
#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 = nullptr;
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 /ode in the linked list };
template linkedListIterator::linkedListIterator() { this->current = nullptr; }
template linkedListIterator::linkedListIterator(nodeType *ptr) { current = ptr; }
template Type linkedListIterator::operator*() { return this->current->info; }
template linkedListIterator linkedListIterator::operator++() { this->current = this->current->link;
return *this; }
template bool linkedListIterator::operator== (const linkedListIterator& right) const { return (this->current == right.current); }
template bool linkedListIterator::operator!= (const linkedListIterator& right) const { return (this->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 = nullptr, last = nullptr, 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 = nullptr, last = nullptr, 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 nullptr.
linkedListType(); //default constructor //Initializes the list to an empty state. //Postcondition: first = nullptr, last = nullptr, 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 == nullptr); }
template linkedListType::linkedListType() //default constructor { first = nullptr; last = nullptr; count = 0; }
template void linkedListType::destroyList() { nodeType *temp; //pointer to deallocate the memory //occupied by the node while (first != nullptr) //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 = nullptr; //initialize last to nullptr; first has already //been set to nullptr 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 != nullptr) //while more data to print { cout info link; } }//end print
template int linkedListType::length() const { return count; } //end length
template Type linkedListType::front() const { assert(first != nullptr);
return first->info; //return the info of the first node }//end front
template Type linkedListType::back() const { assert(last != nullptr);
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(nullptr);
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 != nullptr) //if the list is nonempty, make it empty destroyList();
if (otherList.first == nullptr) //otherList is empty { first = nullptr; last = nullptr; 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 = nullptr; //set the link field of //the node to nullptr 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 != nullptr) { newNode = new nodeType; //create a node newNode->info = current->info; //copy the info newNode->link = nullptr; //set the link of /ewNode to nullptr 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 = nullptr; 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
*******************************************************************************
main.cpp
//This program tests various operation of a linked list //34 62 21 10 15 90 66 53 7 120 88 36 90 11 17 24 10 -999
#include #include "intLinkedList.h"
using namespace std;
// part b int main() { intLinkedList list;
intLinkedList evensList; intLinkedList oddsList;
int num;
cout > num;
while (num != -999) { list.insertLast(num); cin >> num; }
cout
cout
list.splitEvensOddsList(evensList, oddsList);
cout
cout
return 0; }
********************************************************************************
unorderedLinkedList.h
#ifndef H_UnorderedLinkedList #define H_UnorderedLinkedList
#include "linkedList.h" using namespace std;
template class unorderedLinkedList: public linkedListType { public: bool search(const Type& searchItem) const; //Function to determine whether searchItem is in the list. //Postcondition: Returns true if searchItem is in the // list, otherwise the value false is // returned.
void insertFirst(const Type& newItem); //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.
void insertLast(const Type& newItem); //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.
void deleteNode(const Type& deleteItem); //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. };
template bool unorderedLinkedList:: search(const Type& searchItem) const { nodeType *current; //pointer to traverse the list bool found = false; current = this->first; //set current to point to the first /ode in the list
while (current != nullptr && !found) //search the list if (current->info == searchItem) //searchItem is found found = true; else current = current->link; //make current point to //the next node return found; }//end search
template void unorderedLinkedList::insertFirst(const Type& newItem) { nodeType *newNode; //pointer to create the new node
newNode = new nodeType; //create the new node
newNode->info = newItem; //store the new item in the node newNode->link = this->first; //insert newNode before first this->first = newNode; //make first point to the //actual first node this->count++; //increment count
if (this->last == nullptr) //if the list was empty, newNode is also //the last node in the list this->last = newNode; }//end insertFirst
template void unorderedLinkedList::insertLast(const Type& newItem) { nodeType *newNode; //pointer to create the new node
newNode = new nodeType; //create the new node
newNode->info = newItem; //store the new item in the node newNode->link = nullptr; //set the link field of newNode //to nullptr
if (this->first == nullptr) //if the list is empty, newNode is //both the first and last node { this->first = newNode; this->last = newNode; this->count++; //increment count } else //the list is not empty, insert newNode after last { this->last->link = newNode; //insert newNode after last this->last = newNode; //make last point to the actual //last node in the list this->count++; //increment count } }//end insertLast
template void unorderedLinkedList::deleteNode(const Type& deleteItem) { nodeType *current; //pointer to traverse the list nodeType *trailCurrent; //pointer just before current bool found;
if (this->first == nullptr) //Case 1; the list is empty. cout first->info == deleteItem) //Case 2 { current = this->first; this->first = this->first->link; this->count--; if (this->first == nullptr) //the list has only one node this->last = nullptr; delete current; } else //search the list for the node with the given info { found = false; trailCurrent = this->first; //set trailCurrent to point //to the first node current = this->first->link; //set current to point to //the second node
while (current != nullptr && !found) { if (current->info != deleteItem) { trailCurrent = current; current = current-> link; } else found = true; }//end while
if (found) //Case 3; if found, delete the node { trailCurrent->link = current->link; this->count--;
if (this->last == current) /ode to be deleted //was the last node this->last = trailCurrent; //update the value //of last delete current; //delete the node from the list } else cout
#endif
intLinkedList.hlinkedList.h main.cppunorderedLinkedList.h Linked List 1 #ifndef H_1ntLinkedList 2 #define H ntLinkedList Derive the class intLinkedList from the class unorderedLinkedList as follows: 4 #include "unorderedLinkedList.h" class intLinkedList: public unordered public: 6 using namespace std; void splitEvens0ddsList(intLinkedL //Function to rearrange the nodes //that evenList consists of even i //consists of odd integers. //Postcondition: evenList consists // oddList consists of odd integer // The original list is empty 8 class intLinkedList: public unorderedLinkedListStep by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access with AI-Powered 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