Question & Answer: Please help me with this program (please write it in computer)……

Please help me with this program (please write it in computer).

Consider a sparse implementation of the ADT polynomial that stores only the terms with nonzero coefficients.

a. Complete the sparse implementation.

b. Define a traverse operation for the ADT polynomial that will allow you to add two sparse polynomials

without having to consider terms with zero coefficients explicitly.

Node.h

#pragma once

#include <cstddef>

template<class ItemType>

class Node

{

private:

ItemType item;

Node<ItemType>* next;

public:

Node();

Node(const ItemType& anItem);

Node(const ItemType& anItem, Node<ItemType>* nextNodePtr);

void setItem(const ItemType& anItem);

void setNext(Node<ItemType>* nextNodePtr);

ItemType getItem() const;

Node<ItemType>* getNext() const;

};

template<class ItemType>

Node<ItemType>::Node() : next(nullptr)

{

}

template<class ItemType>

Node<ItemType>::Node(const ItemType& anItem) : item(anItem), next(nullptr)

{

}

template<class ItemType>

Node<ItemType>::Node(const ItemType& anItem, Node<ItemType>* nextNodePtr) :

item(anItem), next(nextNodePtr)

{

}

template<class ItemType>

void Node<ItemType>::setItem(const ItemType& anItem)

{

item = anItem;

}

template<class ItemType>

void Node<ItemType>::setNext(Node<ItemType>* nextNodePtr)

{

next = nextNodePtr;

}

template<class ItemType>

ItemType Node<ItemType>::getItem() const

{

return item;

}

template<class ItemType>

Node<ItemType>* Node<ItemType>::getNext() const

{

return next;

}

BagInterface.h

#pragma once

#include <vector>

using namespace std;

template<class ItemType>

class BagInterface

{

public:

virtual int getCurrentSize() const = 0;

virtual bool isEmpty() const = 0;

virtual bool add(const ItemType& newEntry) = 0;

virtual bool addBack(const ItemType& newEntry) = 0;

virtual bool remove(const ItemType& anEntry) = 0;

virtual bool remove2(const ItemType& anEntry) = 0;

virtual void clear() = 0;

virtual int getFrequencyOf(const ItemType& anEntry) const = 0;

virtual bool contains(const ItemType& anEntry) const = 0;

virtual vector<ItemType> toVector() const = 0;

};

LinkedBag.h

#pragma once

#include “BagInterface.h”

#include “Node.h”

#include <cstddef>

#include <iostream>

template<class ItemType>

class LinkedBag : public BagInterface<ItemType>

{

private:

Node<ItemType>* headPtr;

int itemCount;

Node<ItemType>* getPointerTo(const ItemType& target) const;

public:

LinkedBag();

LinkedBag(const LinkedBag<ItemType>& aBag);

virtual ~LinkedBag();

int getCurrentSize() const;

bool isEmpty() const;

bool add(const ItemType& newEntry);

bool addBack(const ItemType& newEntry);

bool remove(const ItemType& anEntry);

bool remove2(const ItemType& anEntry);

void clear();

bool contains(const ItemType& anEntry) const;

int getFrequencyOf(const ItemType& anEntry) const;

void display();

vector<ItemType> toVector() const;

};

template<class ItemType>

LinkedBag<ItemType>::LinkedBag() : headPtr(nullptr), itemCount(0)

{

}

template<class ItemType>

LinkedBag<ItemType>::LinkedBag(const LinkedBag<ItemType>& aBag)

{

itemCount = aBag.itemCount;

Node<ItemType>* origChainPtr = aBag.headPtr;

if (origChainPtr == nullptr)

headPtr = nullptr;

else

{

headPtr = new Node<ItemType>();

headPtr->setItem(origChainPtr->getItem());

Node<ItemType>* newChainPtr = headPtr;

origChainPtr = origChainPtr->getNext();

while (origChainPtr != nullptr)

{

ItemType nextItem = origChainPtr->getItem();

Node<ItemType>* newNodePtr = new Node<ItemType>(nextItem);

newChainPtr->setNext(newNodePtr);

newChainPtr = newChainPtr->getNext();

origChainPtr = origChainPtr->getNext();

}

newChainPtr->setNext(nullptr);

}

}

template<class ItemType>

LinkedBag<ItemType>::~LinkedBag()

{

clear();

}

template<class ItemType>

bool LinkedBag<ItemType>::isEmpty() const

{

return itemCount == 0;

}

template<class ItemType>

int LinkedBag<ItemType>::getCurrentSize() const

{

return itemCount;

}

template<class ItemType>

bool LinkedBag<ItemType>::add(const ItemType& newEntry)

{

Node<ItemType>* nextNodePtr = new Node<ItemType>();

nextNodePtr->setItem(newEntry);

nextNodePtr->setNext(headPtr);

headPtr = nextNodePtr;

itemCount++;

return true;

}

template<class ItemType>

vector<ItemType> LinkedBag<ItemType>::toVector() const

{

vector<ItemType> bagContents;

Node<ItemType>* curPtr = headPtr;

int counter = 0;

while ((curPtr != nullptr) && (counter < itemCount))

{

bagContents.push_back(curPtr->getItem());

curPtr = curPtr->getNext();

counter++;

}

return bagContents;

}

template<class ItemType>

bool LinkedBag<ItemType>::remove(const ItemType& anEntry)

{

Node<ItemType>* entryNodePtr = getPointerTo(anEntry);

bool canRemoveItem = !isEmpty() && (entryNodePtr != nullptr);

if (canRemoveItem)

{

entryNodePtr->setItem(headPtr->getItem());

Node<ItemType>* nodeToDeletePtr = headPtr;

headPtr = headPtr->getNext();

nodeToDeletePtr->setNext(nullptr);

delete nodeToDeletePtr;

nodeToDeletePtr = nullptr;

itemCount–;

}

return canRemoveItem;

}

template<class ItemType>

void LinkedBag<ItemType>::clear()

{

Node<ItemType>* nodeToDeletePtr = headPtr;

while (headPtr != nullptr)

{

headPtr = headPtr->getNext();

nodeToDeletePtr->setNext(nullptr);

delete nodeToDeletePtr;

nodeToDeletePtr = headPtr;

}

itemCount = 0;

}

template<class ItemType>

int LinkedBag<ItemType>::getFrequencyOf(const ItemType& anEntry) const

{

int frequency = 0;

int counter = 0;

Node<ItemType>* curPtr = headPtr;

while ((curPtr != nullptr) && (counter < itemCount))

{

if (anEntry == curPtr->getItem())

{

frequency++;

}

counter++;

curPtr = curPtr->getNext();

}

return frequency;

}

template<class ItemType>

bool LinkedBag<ItemType>::contains(const ItemType& anEntry) const

{

return (getPointerTo(anEntry) != nullptr);

}

template<class ItemType>

Node<ItemType>* LinkedBag<ItemType>::getPointerTo(const ItemType& anEntry) const

{

bool found = false;

Node<ItemType>* curPtr = headPtr;

while (!found && (curPtr != nullptr))

{

if (anEntry == curPtr->getItem())

found = true;

else

curPtr = curPtr->getNext();

}

return curPtr;

}

template<class ItemType>

bool LinkedBag<ItemType>::addBack(const ItemType& newEntry)

{

Node<ItemType>* lastNodePtr = new Node<ItemType>();

lastNodePtr->setItem(newEntry);

Node<ItemType>* curPtr = headPtr;

while (curPtr->getNext() != nullptr)

{

curPtr = curPtr->getNext();

}

curPtr->setNext(lastNodePtr);

itemCount++;

return true;

}

template<class ItemType>

bool LinkedBag<ItemType>::remove2(const ItemType& anEntry)

{

Node<ItemType>* entryNodePtr = headPtr;

bool canRemoveItem = !isEmpty() && (entryNodePtr != nullptr);

if (canRemoveItem)

{

if (entryNodePtr->getItem() == anEntry)

{

headPtr = headPtr->getNext();

}

else

{

while (entryNodePtr->getNext()->getItem() != anEntry)

{

entryNodePtr = entryNodePtr->getNext();

}

entryNodePtr->setNext(entryNodePtr->getNext()->getNext());

}

itemCount–;

}

return canRemoveItem;

}

template<class ItemType>

void LinkedBag<ItemType>::display()

{

Node<ItemType>*entryNodePtr = headPtr;

while (entryNodePtr != nullptr)

{

cout << entryNodePtr->getItem() << endl;

entryNodePtr = entryNodePtr->getNext();

}

}