#include \"BagInterface.h\" #include \"DoubleLinkedBag.hpp\" #include <iostream>
ID: 3749384 • Letter: #
Question
#include "BagInterface.h" #include "DoubleLinkedBag.hpp" #include <iostream> #include <string> #include <cctype>
using namespace std;
void displayBag(BagInterface<string>* bagPtr) { cout << "The bag contains " << bagPtr->getCurrentSize() << " items:" << endl; vector<string> bagItems = bagPtr->toVector(); int numberOfEntries = (int)bagItems.size(); for (int i = 0; i < numberOfEntries; i++) { cout << bagItems[i] << " "; } // end for cout << endl << endl; } // end displayBag
void bagTester(BagInterface<string>* bagPtr) { cout << "isEmpty: returns " << bagPtr->isEmpty() << "; should be 1 (true)" << endl; string items[] = {"one", "two", "three"}; cout << "Add 3 items to the bag: " << endl; for (int i = 0; i < 3; i++) { bagPtr->add(items[i]); } // end for displayBag(bagPtr); cout << "isEmpty: returns " << bagPtr->isEmpty() << "; should be 0 (false)" << endl; cout << "getCurrentSize returns : " << bagPtr->getCurrentSize() << "; should be 3" << endl; cout << endl << "Clear the bag." << endl; bagPtr->clear();
cout << "isEmpty: returns " << bagPtr->isEmpty() << "; should be 1 (true)" << endl;
cout << "Add 3 items to the bag again: " << endl; for (int i = 0; i < 3; i++) { bagPtr->add(items[i]); } // end for
displayBag(bagPtr);
} // end bagTester
int main() { BagInterface<string>* bagPtr = nullptr; bagPtr = new DoubleLinkedBag<string>(); cout << "Testing the Double Linked Bag:" << endl; cout << "The initial bag is empty." << endl; bagTester(bagPtr); delete bagPtr; bagPtr = nullptr; cout << "All done!" << endl; // Keep the console open so we can see the output cin.ignore(); cin.get();
return 0; } // end main
#include "BagInterface.h" #include "DoubleLinkedBag.hpp" #include <iostream> #include <string> #include <cctype>
using namespace std;
void displayBag(BagInterface<string>* bagPtr) { cout << "The bag contains " << bagPtr->getCurrentSize() << " items:" << endl; vector<string> bagItems = bagPtr->toVector(); int numberOfEntries = (int)bagItems.size(); for (int i = 0; i < numberOfEntries; i++) { cout << bagItems[i] << " "; } // end for cout << endl << endl; } // end displayBag
void bagTester(BagInterface<string>* bagPtr) { cout << "isEmpty: returns " << bagPtr->isEmpty() << "; should be 1 (true)" << endl; string items[] = {"one", "two", "three"}; cout << "Add 3 items to the bag: " << endl; for (int i = 0; i < 3; i++) { bagPtr->add(items[i]); } // end for displayBag(bagPtr); cout << "isEmpty: returns " << bagPtr->isEmpty() << "; should be 0 (false)" << endl; cout << "getCurrentSize returns : " << bagPtr->getCurrentSize() << "; should be 3" << endl; cout << endl << "Clear the bag." << endl; bagPtr->clear();
cout << "isEmpty: returns " << bagPtr->isEmpty() << "; should be 1 (true)" << endl;
cout << "Add 3 items to the bag again: " << endl; for (int i = 0; i < 3; i++) { bagPtr->add(items[i]); } // end for
displayBag(bagPtr);
} // end bagTester
int main() { BagInterface<string>* bagPtr = nullptr; bagPtr = new DoubleLinkedBag<string>(); cout << "Testing the Double Linked Bag:" << endl; cout << "The initial bag is empty." << endl; bagTester(bagPtr); delete bagPtr; bagPtr = nullptr; cout << "All done!" << endl; // Keep the console open so we can see the output cin.ignore(); cin.get();
return 0; } // end main #include "BagInterface.h" #include "DoubleLinkedBag.hpp" #include <iostream> #include <string> #include <cctype>
using namespace std;
void displayBag(BagInterface<string>* bagPtr) { cout << "The bag contains " << bagPtr->getCurrentSize() << " items:" << endl; vector<string> bagItems = bagPtr->toVector(); int numberOfEntries = (int)bagItems.size(); for (int i = 0; i < numberOfEntries; i++) { cout << bagItems[i] << " "; } // end for cout << endl << endl; } // end displayBag
void bagTester(BagInterface<string>* bagPtr) { cout << "isEmpty: returns " << bagPtr->isEmpty() << "; should be 1 (true)" << endl; string items[] = {"one", "two", "three"}; cout << "Add 3 items to the bag: " << endl; for (int i = 0; i < 3; i++) { bagPtr->add(items[i]); } // end for displayBag(bagPtr); cout << "isEmpty: returns " << bagPtr->isEmpty() << "; should be 0 (false)" << endl; cout << "getCurrentSize returns : " << bagPtr->getCurrentSize() << "; should be 3" << endl; cout << endl << "Clear the bag." << endl; bagPtr->clear();
cout << "isEmpty: returns " << bagPtr->isEmpty() << "; should be 1 (true)" << endl;
cout << "Add 3 items to the bag again: " << endl; for (int i = 0; i < 3; i++) { bagPtr->add(items[i]); } // end for
displayBag(bagPtr);
} // end bagTester
int main() { BagInterface<string>* bagPtr = nullptr; bagPtr = new DoubleLinkedBag<string>(); cout << "Testing the Double Linked Bag:" << endl; cout << "The initial bag is empty." << endl; bagTester(bagPtr); delete bagPtr; bagPtr = nullptr; cout << "All done!" << endl; // Keep the console open so we can see the output cin.ignore(); cin.get();
return 0; } // end main Lab 4 In chapter 4 we learned about linked chains (also called linked lists) that take this form: nullptr "ab" "cd" "ef" "ij" headPtr item next emnext em next item next item next In a linked chain each node points to the next node. For this lab we're going to create a double- linked chain ef tailPh head Ptr Each node in a double-linked chain contains a pointer to the next node and the previous node We'll do this by beginning with the LinkedBag code from the textbook. Step 1 Download and unzip the starter files: main.cpp- A driver program that includes the polymorphic bag tester functions
Explanation / Answer
Node.hpp
#ifndef NODE_
#define NODE_
template<class ItemType>
class Node
{
private:
ItemType item; // A data item
Node<ItemType>* next; // Pointer to next node
// STEP 2
Node<ItemType> * prev;
public:
Node();
Node(const ItemType& anItem);
Node(const ItemType& anItem, Node<ItemType>* nextNodePtr, Node<ItemType> * prevNodePtr);
void setItem(const ItemType& anItem);
void setNext(Node<ItemType>* nextNodePtr);
ItemType getItem() const;
Node<ItemType>* getNext() const;
void setPrev(Node<ItemType> * prev);
Node<ItemType> * getPrev();
}; // end Node
// STEP 3 - Modify constructor below
template<class ItemType>
Node<ItemType>::Node() : next(nullptr), prev(nullptr)
{
} // end default constructor
// STEP 3 - Modify constructor below
template<class ItemType>
Node<ItemType>::Node(const ItemType& anItem) : item(anItem), next(nullptr), prev(nullptr)
{
} // end constructor
// STEP 3 - Modify constructor below
template<class ItemType>
Node<ItemType>::Node(const ItemType& anItem, Node<ItemType>* nextNodePtr, Node<ItemType> * nodePrevPtr) :
item(anItem), next(nextNodePtr), prev(prevNodePtr)
{
} // end constructor
template<class ItemType>
void Node<ItemType>::setItem(const ItemType& anItem)
{
item = anItem;
} // end setItem
template<class ItemType>
void Node<ItemType>::setNext(Node<ItemType>* nextNodePtr)
{
next = nextNodePtr;
} // end setNext
// STEP 4
template<class ItemType>
void Node<ItemType>::setPrev(Node<ItemType> * prevNode) {
prev = prevNode;
}
template<class ItemType>
ItemType Node<ItemType>::getItem() const
{
return item;
} // end getItem
template<class ItemType>
Node<ItemType>* Node<ItemType>::getNext() const
{
return next;
} // end getNext
// STEP 5
template<class ItemType>
Node<ItemType> * Node<ItemType>::getPrev() {
return prev;
}
#endif
main2.cpp
#include "BagInterface.h"
#include "DoubleLinkedBag.hpp"
#include <iostream>
#include <string>
#include <cctype>
using namespace std;
void displayBag(BagInterface<string>* bagPtr)
{
cout << "The bag contains " << bagPtr->getCurrentSize()
<< " items:" << endl;
vector<string> bagItems = bagPtr->toVector();
int numberOfEntries = (int)bagItems.size();
for (int i = 0; i < numberOfEntries; i++)
{
cout << bagItems[i] << " ";
} // end for
cout << endl << endl;
} // end displayBag
void bagTester(BagInterface<string>* bagPtr)
{
cout << "isEmpty: returns " << bagPtr->isEmpty()
<< "; should be 1 (true)" << endl;
string items[] = { "one", "two", "three" };
cout << "Add 3 items to the bag: " << endl;
for (int i = 0; i < 3; i++)
{
bagPtr->add(items[i]);
} // end for
displayBag(bagPtr);
cout << "isEmpty: returns " << bagPtr->isEmpty()
<< "; should be 0 (false)" << endl;
cout << "getCurrentSize returns : " << bagPtr->getCurrentSize()
<< "; should be 3" << endl;
cout << endl << "Clear the bag." << endl;
bagPtr->clear();
cout << "isEmpty: returns " << bagPtr->isEmpty()
<< "; should be 1 (true)" << endl;
cout << "Add 3 items to the bag again: " << endl;
for (int i = 0; i < 3; i++)
{
bagPtr->add(items[i]);
} // end for
displayBag(bagPtr);
} // end bagTester
int main()
{
BagInterface<string>* bagPtr = nullptr;
bagPtr = new DoubleLinkedBag<string>();
cout << "Testing the Double Linked Bag:" << endl;
cout << "The initial bag is empty." << endl;
bagTester(bagPtr);
delete bagPtr;
bagPtr = nullptr;
cout << "All done!" << endl;
// Keep the console open so we can see the output
cin.ignore();
cin.get();
return 0;
} // end main
BagInterface.h
#ifndef BAG_INTERFACE_
#define BAG_INTERFACE_
#include <vector>
template<class ItemType>
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 std::vector<ItemType> toVector() const = 0;
/** Destroys object and frees memory allocated by object.
(See C++ Interlude 2) */
virtual ~BagInterface() { }
}; // end BagInterface
#endif#pragma once
DoubleLinkedBag.hpp
#ifndef DOUBLE_LINKED_BAG_RECURSIVE_
#define DOUBLE_LINKED_BAG_RECURSIVE_
#include "BagInterface.h"
#include "Node.hpp"
#include <cstddef>
template<class ItemType>
class DoubleLinkedBag : public BagInterface<ItemType>
{
private:
Node<ItemType>* headPtr; // Pointer to first node
// STEP 6
Node<ItemType> * tailPtr;
int itemCount; // Current count of bag items
// Fills the vector bagContents with the data in the nodes of
// the linked chain to which curPtr points.
void fillVector(std::vector<ItemType>& bagContents, Node<ItemType>* curPtr) const;
// Locates a given entry within this bag.
// Returns either a pointer to the node containing a given entry or
// the null pointer if the entry is not in the bag.
Node<ItemType>* getPointerTo(const ItemType& target,
Node<ItemType>* curPtr) const;
// Counts the frequency of occurrence of a given entry in this bag.
int countFrequency(const ItemType& anEntry, int counter,
Node<ItemType>* curPtr) const;
// Deallocates all nodes assigned to this bag
void deallocate(Node<ItemType>* nextNodePtr);
public:
DoubleLinkedBag();
virtual ~DoubleLinkedBag(); // 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<ItemType> toVector() const;
}; // end LinkedBagRecursive
// STEP 7 - Update constructor below
template<class ItemType>
DoubleLinkedBag<ItemType>::DoubleLinkedBag() : headPtr(nullptr), itemCount(0), tailPtr(nullptr)
{
} // end default constructor
template<class ItemType>
DoubleLinkedBag<ItemType>::~DoubleLinkedBag()
{
clear();
} // end destructor
template<class ItemType>
bool DoubleLinkedBag<ItemType>::isEmpty() const
{
return itemCount == 0;
} // end isEmpty
template<class ItemType>
int DoubleLinkedBag<ItemType>::getCurrentSize() const
{
return itemCount;
} // end getCurrentSize
template<class ItemType>
bool DoubleLinkedBag<ItemType>::add(const ItemType& newEntry)
{
// Add to beginning of chain: new node references rest of chain;
// (headPtr is null if chain is empty)
Node<ItemType>* nextNodePtr = new Node<ItemType>();
nextNodePtr->setItem(newEntry);
nextNodePtr->setNext(headPtr); // New node points to chain
// STEP 9
// if node is added, second node (used to be first node) prev pointer points to head node
if (headPtr != nullptr) {
headPtr->setPrev(nextNodePtr);
}
headPtr = nextNodePtr; // New node is now first node
/*
if (headPtr != nullptr) {
headPtr->getNext()->setPrev(nextNodePtr);
}
*/
// STEP 8
if (tailPtr == nullptr) {
tailPtr = nextNodePtr;
}
itemCount++;
return true;
} // end add
template<class ItemType>
std::vector<ItemType> DoubleLinkedBag<ItemType>::toVector() const
{
std::vector<ItemType> bagContents;
fillVector(bagContents, tailPtr); // STEP 12
return bagContents;
} // end toVector
template<class ItemType>
bool DoubleLinkedBag<ItemType>::remove(const ItemType& anEntry)
{
Node<ItemType>* entryNodePtr = getPointerTo(anEntry, headPtr);
bool canRemoveItem = !isEmpty() && (entryNodePtr != nullptr);
if (canRemoveItem)
{
// Copy data from first node to located node
entryNodePtr->setItem(headPtr->getItem());
// Delete first node
Node<ItemType>* nodeToDeletePtr = headPtr;
headPtr = headPtr->getNext();
// STEP 10
if (headPtr == nullptr) {
tailPtr = nullptr;
}
// Return node to the system
nodeToDeletePtr->setNext(nullptr);
delete nodeToDeletePtr;
nodeToDeletePtr = nullptr;
itemCount--;
} // end if
return canRemoveItem;
} // end remove
template<class ItemType>
void DoubleLinkedBag<ItemType>::clear()
{
deallocate(headPtr);
headPtr = nullptr;
// STEP 11
tailPtr = nullptr;
itemCount = 0;
} // end clear
template<class ItemType>
int DoubleLinkedBag<ItemType>::getFrequencyOf(const ItemType& anEntry) const
{
return countFrequency(anEntry, 0, headPtr);
} // end getFrequencyOf
template<class ItemType>
bool DoubleLinkedBag<ItemType>::contains(const ItemType& anEntry) const
{
return (getPointerTo(anEntry, headPtr) != nullptr);
} // end contains
// Private Methods:
template<class ItemType>
void DoubleLinkedBag<ItemType>::fillVector(std::vector<ItemType>& bagContents,
Node<ItemType>* curPtr) const
{
if (curPtr != nullptr)
{
bagContents.push_back(curPtr->getItem());
fillVector(bagContents, curPtr->getPrev()); // STEP 13
} // end if
} // end toVector
template<class ItemType>
Node<ItemType>* DoubleLinkedBag<ItemType>::getPointerTo(const ItemType& target,
Node<ItemType>* curPtr) const
{
Node<ItemType>* result = nullptr;
if (curPtr != nullptr)
{
if (target == curPtr->getItem())
result = curPtr;
else
result = getPointerTo(target, curPtr->getNext());
} // end if
return result;
} // end getPointerTo
template<class ItemType>
int DoubleLinkedBag<ItemType>::countFrequency(const ItemType& anEntry, int counter,
Node<ItemType>* curPtr) const
{
int frequency = 0;
if ((curPtr != nullptr) && (counter < itemCount))
{
if (anEntry == curPtr->getItem())
{
frequency = 1 + countFrequency(anEntry, counter + 1, curPtr->getNext());
}
else
{
frequency = countFrequency(anEntry, counter + 1, curPtr->getNext());
} // end if
} // end while
return frequency;
} // end countFrequency
template<class ItemType>
void DoubleLinkedBag<ItemType>::deallocate(Node<ItemType>* nextNodePtr)
{
Node<ItemType>* nodeToDeletePtr = nextNodePtr;
if (nextNodePtr != nullptr)
{
nextNodePtr = nextNodePtr->getNext();
delete nodeToDeletePtr;
nodeToDeletePtr = nextNodePtr;
deallocate(nextNodePtr);
} // end if
} // end deallocate
#endif
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.