Answered step by step
Verified Expert Solution
Link Copied!

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

image text in transcribedLinkedBag.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" #include  template 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" template class 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_ template class 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" //#include  template 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

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Database Reliability Engineering Designing And Operating Resilient Database Systems

Authors: Laine Campbell, Charity Majors

1st Edition

978-1491925942

More Books

Students also viewed these Databases questions

Question

In Problem calculate the matrix product. 2 -3 0 [0 1]

Answered: 1 week ago

Question

Determine miller indices of plane A Z a/2 X a/2 a/2 Y

Answered: 1 week ago

Question

How reliable is this existing information?

Answered: 1 week ago