Complete the C program given with the codes below: Codes: LinkedBagTest.cpp code
ID: 3889948 • Letter: C
Question
Complete the C program given with the codes below:
Codes:
LinkedBagTest.cpp code:
#include "LinkedBag.h"
#include
#include
#include
void printVector(vector& v)
{
for (vector::iterator i = v.begin(); i != v.end(); ++i)
{
cout << *i << " " ;
}
cout << endl;
}
int main()
{
LinkedBag bag;
cout << "initial size = " << bag.getCurrentSize() << endl;
cout << "is empty should be true: " << bag.isEmpty() << endl;
bag.add("aa");
bag.add("bb");
bag.add("cc");
bag.add("dd");
bag.add("aa");
cout << "current size should be 5: " << bag.getCurrentSize() << endl;
cout << "is empty should be false: " << bag.isEmpty() << endl;
cout << "there should be 2 'aa' nodes: " << bag.getFrequencyOf("aa") << endl;
vector v = bag.toVector();
printVector(v);
cout << "contains 'cc' should be true: " << bag.contains("cc") << endl;
bag.remove("aa");
bag.remove("cc");
cout << "removed 'aa' and 'cc' - current size should be 3: " << bag.getCurrentSize() << endl;
v = bag.toVector();
printVector(v);
} // end main
LinkedBag.h code:
#ifndef LINKED_BAG_
#define LINKED_BAG_
#include
#include
#include "Node.h"
using namespace std;
class LinkedBag
{
private:
Node* headPtr; // Pointer to first 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* getPointerTo(const ItemType& target) const;
public:
LinkedBag(); // Default constructor
// Copy constructor
LinkedBag::LinkedBag(const LinkedBag& aBag)
{
itemCount = aBag.itemCount;
Node* origChainPtr = aBag.headPtr; // Points to nodes in original chain
if (origChainPtr == nullptr)
headPtr = nullptr; // Original bag is empty
else
{
// Copy first node
headPtr = new Node();
headPtr->setItem(origChainPtr->getItem());
// Copy remaining nodes
Node* newChainPtr = headPtr; // Points to last node in new chain
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* newNodePtr = new Node(nextItem);
// 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 new chain
} // end if
} // end copy constructor
~LinkedBag(); // Destructor
int getCurrentSize() const;
bool isEmpty() const;
bool add(const ItemType& newEntry);
bool remove(const ItemType& anEntry);
void clear();
bool contains(const ItemType& anEntry) const;
int getFrequencyOf(const ItemType& anEntry) const;
vector toVector() const;
}; // end LinkedBag
#endif
LinkedBag.cpp code:
#include "LinkedBag.h"
LinkedBag::LinkedBag() : headPtr(nullptr), itemCount(0)
{
} // end default constructor
bool LinkedBag::add(const ItemType& newEntry)
{
// (headPtr is null if chain is empty)
Node* nextNodePtr = new Node();
nextNodePtr->setItem(newEntry);
nextNodePtr->setNext(headPtr); // New node points to chain
// alternate code: Node* nextNodePtr = new Node(newEntry, headPtr);
headPtr = nextNodePtr; // New node is now first node
itemCount++;
return true; // The method is always successful
} // end add
int LinkedBag::getCurrentSize() const
{
return itemCount;
} // end getCurrentSize
bool LinkedBag::isEmpty() const
{
return itemCount == 0;
} // end isEmpty
int LinkedBag::getFrequencyOf(const ItemType& anEntry) const
{
int frequency = 0;
int counter = 0;
Node* curPtr = headPtr;
while ((curPtr != nullptr) && (counter < itemCount))
{
if (anEntry == curPtr->getItem())
{
frequency++;
} // end if
counter++;
curPtr = curPtr->getNext();
} // end while
return frequency;
} // end getFrequencyOf
// Returns either a pointer to the node containing a given entry
// or the null pointer if the entry is not in the bag.
Node* LinkedBag::getPointerTo(const ItemType& target) const
{
bool found = false;
Node* curPtr = headPtr;
while (!found && (curPtr != nullptr))
{
if (target == curPtr->getItem())
found = true;
else
curPtr = curPtr->getNext();
} // end while
return curPtr;
} // end getPointerTo
bool LinkedBag::contains(const ItemType& anEntry) const
{
return (getPointerTo(anEntry) != nullptr);
} // end contains
void LinkedBag::clear()
{
Node* nodeToDeletePtr = headPtr;
while (headPtr != nullptr)
{
headPtr = headPtr->getNext();
// Return node to the system
nodeToDeletePtr->setNext(nullptr);
delete nodeToDeletePtr;
nodeToDeletePtr = headPtr;
} // end while
// headPtr is nullptr; nodeToDeletePtr is nullptr
itemCount = 0;
} // end clear
bool LinkedBag::remove(const ItemType& anEntry)
{
Node* entryNodePtr = getPointerTo(anEntry);
bool canRemoveItem = !isEmpty() && (entryNodePtr != nullptr);
if (canRemoveItem)
{
// Copy data from first node to located node
entryNodePtr->setItem(headPtr->getItem());
// Delete first node
Node* nodeToDeletePtr = headPtr;
headPtr = headPtr->getNext();
// Return node to the system
nodeToDeletePtr->setNext(nullptr);
delete nodeToDeletePtr;
nodeToDeletePtr = nullptr;
itemCount--;
} // end if
return canRemoveItem;
} // end remove
vector LinkedBag::toVector() const
{
std::vector bagContents;
Node* curPtr = headPtr;
int counter = 0;
while ((curPtr != nullptr) && (counter < itemCount))
{
bagContents.push_back(curPtr->getItem());
curPtr = curPtr->getNext();
counter++;
} // end while
return bagContents;
} // end toVector
LinkedBag::~LinkedBag()
{
clear();
} // end destructor
Node.cpp code:
#include "Node.h"
Node::Node() : next(nullptr)
{
} // end default constructor
Node::Node(const ItemType& anItem) : item(anItem), next(nullptr)
{
} // end constructor
Node::Node(const ItemType& anItem, Node* nextNodePtr) :
item(anItem), next(nextNodePtr)
{
} // end constructor
void Node::setItem(const ItemType& anItem)
{
item = anItem;
} // end setItem
void Node::setNext(Node* nextNodePtr)
{
next = nextNodePtr;
} // end setNext
ItemType Node::getItem() const
{
return item;
} // end getItem
Node* Node::getNext() const
{
return next;
} // end getNext
Node.h code:
#include "Node.h"
Node::Node() : next(nullptr)
{
} // end default constructor
Node::Node(const ItemType& anItem) : item(anItem), next(nullptr)
{
} // end constructor
Node::Node(const ItemType& anItem, Node* nextNodePtr) :
item(anItem), next(nextNodePtr)
{
} // end constructor
void Node::setItem(const ItemType& anItem)
{
item = anItem;
} // end setItem
void Node::setNext(Node* nextNodePtr)
{
next = nextNodePtr;
} // end setNext
ItemType Node::getItem() const
{
return item;
} // end getItem
Node* Node::getNext() const
{
return next;
} // end getNext
For this project, we will add to the LinkedBag class we discussed in class. Code for the LinkedBag has been posted. Add the following 3 methods to the LinkedBag class: LinkedBag union (const LinkedBag&otherBag;) Returns a new LinkedBag that has the contents of the calling bag combined with the contents of bag otherBag Calling bag Other Bag New Bag (order does not matter) LinkedBag intersection (const LinkedBag& otherBag) Returns a new LinkedBag that has only those elements that are in both the calling bag and in otherBag. Calling bag Other Bag New Bag (order does not matter) LinkedBag difference (const LinkedBag& otherBag) Returns a new LinkedBag that has the contents of the calling bag with any item removed that also occurs in otherBag Calling bag Other Bag New Bag (order does not matter) Note: You will need the Copy Constructor for the LinkedBag class as discussed in class.Explanation / Answer
Given below is the code with added functionalities.
Note:
1. Copy all the modified/ new files in a new project. Reason: The ItemType for this test program is using int and not strings. So the ItemType in Node.h is modified to be int. Also if you have the new test program, then there will conflictin main() i.e. 2 main functions and will not compile. So copy all these files into a new project and run. I have also modified the signature of printFunction().
2. Don't worry about the order of elements in the output. Since it is a bag, the order of elements does not matter. Only the correct elements should all be present in any order.
If the answer helped, please don't forget to rate the anser. Thank you.
Node.h
#include <iostream>
typedef int ItemType;
class Node
{
ItemType item;
Node* next;
public:
Node() ;
Node(const ItemType& anItem);
Node(const ItemType& anItem, Node* nextNodePtr) ;
void setItem(const ItemType& anItem);
void setNext(Node* nextNodePtr);
ItemType getItem() const;
Node* getNext() const;
};
Node.cpp
#include "Node.h"
Node::Node() : next(nullptr)
{
} // end default constructor
Node::Node(const ItemType& anItem) : item(anItem), next(nullptr)
{
} // end constructor
Node::Node(const ItemType& anItem, Node* nextNodePtr) :
item(anItem), next(nextNodePtr)
{
} // end constructor
void Node::setItem(const ItemType& anItem)
{
item = anItem;
} // end setItem
void Node::setNext(Node* nextNodePtr)
{
next = nextNodePtr;
} // end setNext
ItemType Node::getItem() const
{
return item;
} // end getItem
Node* Node::getNext() const
{
return next;
} // end getNext
LinkedBag.h
#ifndef LINKED_BAG_
#define LINKED_BAG_
#include <iostream>
#include <vector>
#include "Node.h"
using namespace std;
class LinkedBag
{
private:
Node* headPtr; // Pointer to first 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* getPointerTo(const ItemType& target) const;
public:
LinkedBag(); // Default constructor
LinkedBag(const LinkedBag& aBag);// Copy constructor
~LinkedBag(); // Destructor
int getCurrentSize() const;
bool isEmpty() const;
bool add(const ItemType& newEntry);
bool remove(const ItemType& anEntry);
void clear();
bool contains(const ItemType& anEntry) const;
int getFrequencyOf(const ItemType& anEntry) const;
vector<ItemType> toVector() const;
LinkedBag Union(const LinkedBag& otherBag);
LinkedBag intersection(const LinkedBag& otherBag);
LinkedBag difference(const LinkedBag& otherBag);
}; // end LinkedBag
#endif
LinkedBag.cpp
#include "LinkedBag.h"
LinkedBag::LinkedBag() : headPtr(nullptr), itemCount(0)
{
} // end default constructor
LinkedBag::LinkedBag(const LinkedBag& aBag)
{
itemCount = aBag.itemCount;
Node* origChainPtr = aBag.headPtr; // Points to nodes in original chain
if (origChainPtr == nullptr)
headPtr = nullptr; // Original bag is empty
else
{
// Copy first node
headPtr = new Node();
headPtr->setItem(origChainPtr->getItem());
// Copy remaining nodes
Node* newChainPtr = headPtr; // Points to last node in new chain
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* newNodePtr = new Node(nextItem);
// 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 new chain
} // end if
} // end copy constructor
bool LinkedBag::add(const ItemType& newEntry)
{
// (headPtr is null if chain is empty)
Node* nextNodePtr = new Node();
nextNodePtr->setItem(newEntry);
nextNodePtr->setNext(headPtr); // New node points to chain
// alternate code: Node* nextNodePtr = new Node(newEntry, headPtr);
headPtr = nextNodePtr; // New node is now first node
itemCount++;
return true; // The method is always successful
} // end add
int LinkedBag::getCurrentSize() const
{
return itemCount;
} // end getCurrentSize
bool LinkedBag::isEmpty() const
{
return itemCount == 0;
} // end isEmpty
int LinkedBag::getFrequencyOf(const ItemType& anEntry) const
{
int frequency = 0;
int counter = 0;
Node* curPtr = headPtr;
while ((curPtr != nullptr) && (counter < itemCount))
{
if (anEntry == curPtr->getItem())
{
frequency++;
} // end if
counter++;
curPtr = curPtr->getNext();
} // end while
return frequency;
} // end getFrequencyOf
// Returns either a pointer to the node containing a given entry
// or the null pointer if the entry is not in the bag.
Node* LinkedBag::getPointerTo(const ItemType& target) const
{
bool found = false;
Node* curPtr = headPtr;
while (!found && (curPtr != nullptr))
{
if (target == curPtr->getItem())
found = true;
else
curPtr = curPtr->getNext();
} // end while
return curPtr;
} // end getPointerTo
bool LinkedBag::contains(const ItemType& anEntry) const
{
return (getPointerTo(anEntry) != nullptr);
} // end contains
void LinkedBag::clear()
{
Node* nodeToDeletePtr = headPtr;
while (headPtr != nullptr)
{
headPtr = headPtr->getNext();
// Return node to the system
nodeToDeletePtr->setNext(nullptr);
delete nodeToDeletePtr;
nodeToDeletePtr = headPtr;
} // end while
// headPtr is nullptr; nodeToDeletePtr is nullptr
itemCount = 0;
} // end clear
bool LinkedBag::remove(const ItemType& anEntry)
{
Node* entryNodePtr = getPointerTo(anEntry);
bool canRemoveItem = !isEmpty() && (entryNodePtr != nullptr);
if (canRemoveItem)
{
// Copy data from first node to located node
entryNodePtr->setItem(headPtr->getItem());
// Delete first node
Node* nodeToDeletePtr = headPtr;
headPtr = headPtr->getNext();
// Return node to the system
nodeToDeletePtr->setNext(nullptr);
delete nodeToDeletePtr;
nodeToDeletePtr = nullptr;
itemCount--;
} // end if
return canRemoveItem;
} // end remove
vector<ItemType> LinkedBag::toVector() const
{
std::vector<ItemType> bagContents;
Node* curPtr = headPtr;
int counter = 0;
while ((curPtr != nullptr) && (counter < itemCount))
{
bagContents.push_back(curPtr->getItem());
curPtr = curPtr->getNext();
counter++;
} // end while
return bagContents;
} // end toVector
LinkedBag::~LinkedBag()
{
clear();
} // end destructor
LinkedBag LinkedBag::Union(const LinkedBag& otherBag)
{
LinkedBag result(otherBag); //start with other bag's contents
Node* curPtr = headPtr;
//add all elements from this bag
while(curPtr != nullptr)
{
result.add(curPtr->getItem());
curPtr = curPtr->getNext();
}
return result;
}
LinkedBag LinkedBag::intersection(const LinkedBag& otherBag)
{
LinkedBag result;
Node* curPtr = headPtr;
//add all elements from this bag
while(curPtr != nullptr)
{
if(otherBag.contains(curPtr->getItem()) && !result.contains(curPtr->getItem())) //only if the current item is present in otherbag, add it to result if its not already in result
result.add(curPtr->getItem());
curPtr = curPtr->getNext();
}
return result;
}
LinkedBag LinkedBag::difference(const LinkedBag& otherBag)
{
LinkedBag result;
Node* curPtr = headPtr;
//add all elements from this bag
while(curPtr != nullptr)
{
if(!otherBag.contains(curPtr->getItem()) && !result.contains(curPtr->getItem())) //only if the current item is NOT present in otherbag, add it to result if not already in result
result.add(curPtr->getItem());
curPtr = curPtr->getNext();
}
return result;
}
Test.cpp
#include "LinkedBag.h"
#include <iostream>
using namespace std;
void printVector(const vector<ItemType> &v)
{
for (vector<ItemType>::const_iterator i = v.begin(); i != v.end(); ++i)
{
cout << *i << " " ;
}
cout << endl;
}
int main()
{
LinkedBag bag1, bag2, bag3, bag4;
int arr1[15] = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5};
int arr2[5] = {6, 6, 7, 7, 7};
int arr3[7] = {2, 3, 4, 4, 5 , 6, 7};
int arr4[8] = {2, 3, 3, 4, 4, 4, 4, 5};
//fill up the elements in the 4 bags
for(int i = 0; i < 15; i++)
bag1.add(arr1[i]);
for(int i = 0; i < 5; i++)
bag2.add(arr2[i]);
for(int i = 0; i < 7; i++)
bag3.add(arr3[i]);
for(int i = 0; i < 8; i++)
bag4.add(arr4[i]);
cout << "bag1: "; printVector(bag1.toVector());
cout << "bag2: "; printVector(bag2.toVector());
cout << "bag3: "; printVector(bag3.toVector());
cout << "bag4: "; printVector(bag4.toVector());
LinkedBag uni = bag1.Union(bag2);
LinkedBag inter = bag1.intersection(bag3);
LinkedBag diff = bag1.difference(bag4);
cout << "bag1 union bag2: "; printVector(uni.toVector());
cout << "bag1 inter bag3: "; printVector(inter.toVector());
cout << "bag1 diff bag4: "; printVector(diff.toVector());
}
output
bag1: 5 5 5 5 5 4 4 4 4 3 3 3 2 2 1
bag2: 7 7 7 6 6
bag3: 7 6 5 4 4 3 2
bag4: 5 4 4 4 4 3 3 2
bag1 union bag2: 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 7 7 7 6 6
bag1 inter bag3: 2 3 4 5
bag1 diff bag4: 1
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.