Question: *Using the following code * Consider a sparse implementation of the ADT polynomial that stores only the terms with nonzero coeffi cients. a. Complete the
*Using the following code *
Consider a sparse implementation of the ADT polynomial that stores only the terms with nonzero coeffi cients. 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 coeffi cients explicitly.
Node.h
#pragma once
#include
template
class Node
{
private:
ItemType item; // A data item
Node
public:
Node();
Node(const ItemType& anItem);
Node(const ItemType& anItem, Node
void setItem(const ItemType& anItem);
void setNext(Node
ItemType getItem() const;
Node
};
template
Node
{
} // end default constructor
template
Node
{
} // end constructor
template
Node
item(anItem), next(nextNodePtr)
{
} // end constructor
template
void Node
{
item = anItem;
} // end setItem
template
void Node
{
next = nextNodePtr;
} // end setNext
template
ItemType Node
{
return item;
} // end getItem
template
Node
{
return next;
}
BagInterface.h
#pragma once
#include
using namespace std;
template
class BagInterface
{
public:
/** Gets the current number of entries in this bag.
@return The integer number of entries currently in the bag. */
virtual int getCurrentSize() const = 0;
/** Sees whether this bag is empty.
@return True if the bag is empty, or false if not. */
virtual bool isEmpty() const = 0;
/** Adds a new entry to this bag.
@post If successful, newEntry is stored in the bag and
the count of items in the bag has increased by 1.
@param newEntry The object to be added as a new entry.
@return True if addition was successful, or false if not. */
virtual bool add(const ItemType& newEntry) = 0;
/** Removes one occurrence of a given entry from this bag,
if possible.
@post If successful, anEntry has been removed from the bag
and the count of items in the bag has decreased by 1.
@param anEntry The entry to be removed.
@return True if removal was successful, or false if not. */
virtual bool remove(const ItemType& anEntry) = 0;
/** Removes all entries from this bag.
@post Bag contains no items, and the count of items is 0. */
virtual void clear() = 0;
/** Counts the number of times a given entry appears in bag.
@param anEntry The entry to be counted.
@return The number of times anEntry appears in the bag. */
virtual int getFrequencyOf(const ItemType& anEntry) const = 0;
/** Tests whether this bag contains a given entry.
@param anEntry The entry to locate.
@return True if bag contains anEntry, or false otherwise. */
virtual bool contains(const ItemType& anEntry) const = 0;
/** Empties and then fills a given vector with all entries that
are in this bag.
@return A vector containing all the entries in the bag. */
virtual vector
LinkedBag.h
#pragma once
#include "BagInterface.h"
#include "Node.h"
template
class LinkedBag : public BagInterface
{
private:
Node
int itemCount; // Current count of bag items
// Returns either a pointer to the node containing a given entry
// or the null pointer if the entry is not in the bag.
Node
public:
LinkedBag();
LinkedBag(const LinkedBag
virtual ~LinkedBag(); // Destructor should be virtual
int getCurrentSize() const;
bool isEmpty() const;
bool add(const ItemType& newEntry);
bool add2(const ItemType& newEntry);
bool remove(const ItemType& anEntry);
void printPtr();
void clear();
bool contains(const ItemType& anEntry) const;
int getFrequencyOf(const ItemType& anEntry) const;
vector
};
template
LinkedBag
{
cout
} // end default constructor
template
LinkedBag
{
itemCount = aBag.itemCount;
Node
if (origChainPtr == nullptr)
headPtr = nullptr; // Original bag is empty
else
{
// Copy first node
headPtr = new Node
headPtr->setItem(origChainPtr->getItem());
// Copy remaining nodes
Node
origChainPtr = origChainPtr->getNext(); // Advance original-chain pointer
while (origChainPtr != nullptr)
{
// Get next item from original chain
ItemType nextItem = origChainPtr->getItem();
// Create a new node containing the next item
Node
// Link new node to end of new chain
newChainPtr->setNext(newNodePtr);
// Advance pointer to new last node
newChainPtr = newChainPtr->getNext();
// Advance original-chain pointer
origChainPtr = origChainPtr->getNext();
} // end while
newChainPtr->setNext(nullptr); // Flag end of chain
} // end if
} // end copy constructor
template
LinkedBag
{
clear();
} // end destructor
template
bool LinkedBag
{
return itemCount == 0;
} // end isEmpty
template
int LinkedBag
{
return itemCount;
} // end getCurrentSize
template
bool LinkedBag
{
// Add to beginning of chain: new node references rest of chain;
// (headPtr is null if chain is empty)
Node
nextNodePtr->setItem(newEntry);
nextNodePtr->setNext(headPtr); // New node points to chain
// Node
headPtr = nextNodePtr; // New node is now first node
itemCount++;
return true;
} // end add
template
vector
{
vector
Node
int counter = 0;
while ((curPtr != nullptr) && (counter
{
bagContents.push_back(curPtr->getItem());
curPtr = curPtr->getNext();
counter++;
} // end while
return bagContents;
} // end toVector
template
bool LinkedBag
{
Node
bool canRemoveItem = !isEmpty() && (entryNodePtr != nullptr);
if (canRemoveItem)
{
// Copy data from first node to located node
entryNodePtr->setItem(headPtr->getItem());
// Delete first node
Node
headPtr = headPtr->getNext();
// Return node to the system
nodeToDeletePtr->setNext(nullptr);
delete nodeToDeletePtr;
nodeToDeletePtr = nullptr;
itemCount--;
} // end if
return canRemoveItem;
} // end remove
template
void LinkedBag
{
Node
while (headPtr != nullptr)
{
headPtr = headPtr->getNext();
nodeToDeletePtr->setNext(nullptr);
delete nodeToDeletePtr;
nodeToDeletePtr = headPtr;
}
itemCount = 0;
}
template
int LinkedBag
{
int frequency = 0;
int counter = 0;
Node
while ((curPtr != nullptr) && (counter
{
if (anEntry == curPtr->getItem())
{
frequency++;
}
counter++;
curPtr = curPtr->getNext();
}
return frequency;
}
template
bool LinkedBag
{
return (getPointerTo(anEntry) != nullptr);
}
template
Node
{
bool found = false;
Node
while (!found && (curPtr != nullptr))
{
if (anEntry == curPtr->getItem())
found = true;
else
curPtr = curPtr->getNext();
}
return curPtr;
}
template
void LinkedBag
{
Node
while (disPtr != nullptr)
{
cout getItem()
disPtr = disPtr->getNext();
}
cout
}
template
bool LinkedBag
{
Node
Node
nextNodePtr->setItem(newEntry);
nextNodePtr->setNext(nullptr);
if (this->isEmpty())
headPtr = nextNodePtr;
else {
for (int i = 1; i
lastPtr = lastPtr->getNext();
lastPtr->setNext(nextNodePtr);
}
itemCount++;
return true;
}
LinkedBagMain.cpp
#include"LinkedBag.h"
#include
using namespace std;
int main() {
LinkedBag
LinkedBag
copy.printPtr();
cout
bag.add(10);
bag.add(13);
bag.add(66);
bag.add(42);
bag.add(31);
bag.add(9);
bag.printPtr();
cout
cout
cout
cout
cout
cout
bag.remove(31);
bag.printPtr();
cout
cout
bag.add2(45);
bag.printPtr();
cout
system("pause");
return 0;
}
FIGURE 4-10 A sparse polynomial degree headPtr coeff power next
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help