Answered step by step
Verified Expert Solution
Question
1 Approved Answer
C++ Programming Project - Please Help L inkedBag.cpp // Created by Frank M. Carrano and Timothy M. Henry. // Copyright (c) 2017 Pearson Education, Hoboken,
C++ Programming Project - Please Help
LinkedBag.cpp
// Created by Frank M. Carrano and Timothy M. Henry. // Copyright (c) 2017 Pearson Education, Hoboken, New Jersey. /** ADT bag: Link-based implementation. @file LinkedBag.cpp */ #include "LinkedBag.h" #include "Node.h" #includetemplate LinkedBag ::LinkedBag() : headPtr(nullptr), itemCount(0) { } // end default constructor template 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 chain } // end if } // end copy constructor template LinkedBag ::~LinkedBag() { clear(); } // end destructor template bool LinkedBag ::isEmpty() const { return itemCount == 0; } // end isEmpty template int LinkedBag ::getCurrentSize() const { return itemCount; } // end getCurrentSize template bool LinkedBag ::add(const ItemType& newEntry) { // Add to beginning of chain: new node references rest of chain; // (headPtr is null if chain is empty) Node * nextNodePtr = new Node (); nextNodePtr->setItem(newEntry); nextNodePtr->setNext(headPtr); // New node points to chain // Node * nextNodePtr = new Node (newEntry, headPtr); // alternate code headPtr = nextNodePtr; // New node is now first node itemCount++; return true; } // end add template std::vector LinkedBag ::toVector() const { std::vector bagContents; Node * curPtr = headPtr; int counter = 0; while ((curPtr != nullptr) && (counter getItem()); curPtr = curPtr->getNext(); counter++; } // end while return bagContents; } // end toVector template 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 template 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 template int LinkedBag ::getFrequencyOf(const ItemType& anEntry) const { int frequency = 0; int counter = 0; Node * curPtr = headPtr; while ((curPtr != nullptr) && (counter getItem()) { frequency++; } // end if counter++; curPtr = curPtr->getNext(); } // end while return frequency; } // end getFrequencyOf template bool LinkedBag ::contains(const ItemType& anEntry) const { return (getPointerTo(anEntry) != nullptr); } // end contains /* ALTERNATE 1 template bool LinkedBag ::contains(const ItemType& anEntry) const { return getFrequencyOf(anEntry) > 0; } */ /* ALTERNATE 2 template bool LinkedBag ::contains(const ItemType& anEntry) const { bool found = false; Node * curPtr = headPtr; int i = 0; while (!found && (curPtr != nullptr) && (i getItem()) { found = true; } else { i++; curPtr = curPtr->getNext(); } // end if } // end while return found; } // end contains */ // private // Returns either a pointer to the node containing a given entry // or the null pointer if the entry is not in the bag. template Node * LinkedBag ::getPointerTo(const ItemType& anEntry) const { bool found = false; Node * curPtr = headPtr; while (!found && (curPtr != nullptr)) { if (anEntry == curPtr->getItem()) found = true; else curPtr = curPtr->getNext(); } // end while return curPtr; } // end getPointerTo
LinkedBag.h
// Created by Frank M. Carrano and Timothy M. Henry. // Copyright (c) 2017 Pearson Education, Hoboken, New Jersey. /** ADT bag: Link-based implementation. @file LinkedBag.h Listing 4-3 */ #ifndef LINKED_BAG_ #define LINKED_BAG_ #include "BagInterface.h" #include "Node.h" templateclass LinkedBag : public BagInterface { 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(); LinkedBag(const LinkedBag & aBag); // Copy constructor virtual ~LinkedBag(); // Destructor should be virtual 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; std::vector toVector() const; }; // end LinkedBag #include "LinkedBag.cpp" #endif
Node.h
// Created by Frank M. Carrano and Timothy M. Henry. // Copyright (c) 2017 Pearson Education, Hoboken, New Jersey. /** @file Node.h Listing 4-1 */ #ifndef NODE_ #define NODE_ templateclass Node { private: ItemType item; // A data item Node * next; // Pointer to next node 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 ; }; // end Node #include "Node.cpp" #endif
Node.cpp
// Created by Frank M. Carrano and Timothy M. Henry. // Copyright (c) 2017 Pearson Education, Hoboken, New Jersey. /** @file Node.cpp Listing 4-2 */ #include "Node.h" //#includetemplate Node ::Node() : next(nullptr) { } // end default constructor template Node ::Node(const ItemType& anItem) : item(anItem), next(nullptr) { } // end constructor template Node ::Node(const ItemType& anItem, Node * nextNodePtr) : item(anItem), next(nextNodePtr) { } // end constructor template void Node ::setItem(const ItemType& anItem) { item = anItem; } // end setItem template void Node ::setNext(Node * nextNodePtr) { next = nextNodePtr; } // end setNext template ItemType Node ::getItem() const { return item; } // end getItem template Node * Node ::getNext() const { return next; } // end getNext
bagtester.cpp
// Created by Frank M. Carrano and Timothy M. Henry. // Copyright (c) 2017 Pearson Education, Hoboken, New Jersey. #include#include #include "LinkedBag.h" void displayBag(LinkedBag<:string>& bag) { std::cout bagItems = bag.toVector(); int numberOfEntries = (int) bagItems.size(); for (int i = 0; i bag; std::string items[] = {"zero", "one", "two", "three", "four", "five"}; for (int i = 0; i copyOfBag(bag); std::cout bag; std::cout No documentation is required in this assignment. Assignment 5.1 [20 points] Do Programming Problem 2 at the end of chapter 4. Similarly to what you did with the array-based implementation, you'll start with the LinkedBag code from chapter 4, and make the needed edits to change it to a link-based Set. Follow the example of how the link- based Bag is implemented in the text. I expect that the vast majority of your code will be copied directly from the LinkedBag class of chapter 4. You just need to make minor adjustments to reflect the fact that duplicate elements are not allowed. Also, we won't have a frequency of member function. Your LinkedSet class must be derived from a "SetInterface" abstract class. You should be able to reuse your SetInterface class from the last assignment. You should provide the big-3. The bag class in the text does not provide an overloaded assignment operator, so you will need to add that to your class. Here is the source code from the text that you are to use as a starting point: LinkedBag.cpp LinkedBag.h Node.h Node.cpp bagtester.cpp Assignment 5.2 [25 points] Add member functions setUnion(), setIntersection(), and set Difference(). The functions should all return the resulting LinkedSet object. We won't need that extra parameter in the setUnion() function, because the Set will have unlimited capacity. Although returning a reference to a LinkedSet object (with &) would be best practice here, to keep things simple I'm not requiring it. (In other words, the return type will be simply "LinkedSet" with no &.) You may use contains() and the Node class accessors and mutators, but, other than those, do not use any function calls in your definitions of these three functions! The operations must be coded without calling any other functions to help. The practice manipulating the pointers directly will be extremely valuable. No documentation is required in this assignment. Assignment 5.1 [20 points] Do Programming Problem 2 at the end of chapter 4. Similarly to what you did with the array-based implementation, you'll start with the LinkedBag code from chapter 4, and make the needed edits to change it to a link-based Set. Follow the example of how the link- based Bag is implemented in the text. I expect that the vast majority of your code will be copied directly from the LinkedBag class of chapter 4. You just need to make minor adjustments to reflect the fact that duplicate elements are not allowed. Also, we won't have a frequency of member function. Your LinkedSet class must be derived from a "SetInterface" abstract class. You should be able to reuse your SetInterface class from the last assignment. You should provide the big-3. The bag class in the text does not provide an overloaded assignment operator, so you will need to add that to your class. Here is the source code from the text that you are to use as a starting point: LinkedBag.cpp LinkedBag.h Node.h Node.cpp bagtester.cpp Assignment 5.2 [25 points] Add member functions setUnion(), setIntersection(), and set Difference(). The functions should all return the resulting LinkedSet object. We won't need that extra parameter in the setUnion() function, because the Set will have unlimited capacity. Although returning a reference to a LinkedSet object (with &) would be best practice here, to keep things simple I'm not requiring it. (In other words, the return type will be simply "LinkedSet" with no &.) You may use contains() and the Node class accessors and mutators, but, other than those, do not use any function calls in your definitions of these three functions! The operations must be coded without calling any other functions to help. The practice manipulating the pointers directly will be extremely valuable
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored 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