using namespace std;template statement: template<class ItemType>; // Indicates this is a template definitiontemplate statement: template<class ItemType>; template statement: template<class ItemType>; template statements: template<class ItemType>;PlainBox constructor twice, once explcitly and once implicitly. A detailed discussion of defining constructors in a derived class is at this link. firstItemStored is initialized to false instead of true.PlainBox constructor, since it is called implicitly. See the previous note for pages 41 and 42. setItem in the 4th line of displayed code in the top half of the page with virtual void setItem(const ItemType& theItem); writeBackward at the top of the page, as follows: int length = (int)s.size(); // Length of stringanArray[0] <= anArray[1] <= anArray[2] <= . . . <= anArray[size - 1]target:anArray[first] <= target <= anArray[last] anArraygetNumberOfGroups as follows: return statement, delete the >; the statement should be return 0;return statement, replace the two calls to g with calls to getNumberOfGroups; the statement should be return getNumberOfGroups(n - 1, k - 1) + getNumberOfGroups(n - 1, k); writeBackward, as follows: int length = (int)s.size(); // Length of stringArrayBag creates a bag aBag and a vector v containing five items, what happens tov = aBag.toVector() executes?
Therefore, replace the phrase "called the heap, or free store," in the fifth line of this first paragraph with
"called the free store, or application heap,"
Page 123 (May 21, 2015)
In the third line from the bottom of the page, delete RED in ToyBox<double>(.RED)
Page 131 (Nov. 20, 2012)
The section number 2.5.1 should be C2.5.1.
clear at the top of the page, the statementnodeToDeletePtr = nullptr;nodeToDeletePtr is undefined after the while statement. The simple fix is to delete this statement; afterall, nodeToDeletePtr is local to the method and will no longer exist after the method ends execution. A better solution is to move the declaration of nodeToDeletePtr to before the while statement , as follows:
template<class ItemType>
<-------The first two lines are on page 145.
void LinkedBag::clear()
<-------
{
Node<ItemType>* 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 clearitemCount = aBag.itemCount;Node<ItemType>* origChainPtr = aBag.headPtr;while statement, replace origPtr with origChainPtr:while (origChainPtr != nullptr)while loop, origChainPtr = origChainPtr->getNext(); // Advance pointerwhile statement and again on page 148 as the last statement in the loop's body.fillVector:void fillVector(vector<ItemType>& bagContents, Node<ItemType>* curPtr) const;LinkedBag<ItemType>:: is missing before the method's name:void LinkedBag<ItemType>::fillVector(vector<ItemType>& bagContents, Node<ItemType>* curPtr) const// end toVector should be // end fillVectorgetPointerTo at the bottom of the page, LinkedBag<ItemType>:: is missing before the method's name:
Node<ItemType>* LinkedBag<ItemType>::getPointerTo(const ItemType& target,
Node<ItemType>* curPtr) const
displayBag by replacing the two statements after the cout statement withvector<string> bagItems = bag->toVector();main at the bottom of the page by deleting the semicolon at the end of the first part of the cout statement:cout << "Enter 'A' to test the array-based implementation\n";
delete operator in the main method. This occurs because BagInterface, as given in Listing 1-1 of Chapter 1, is abstract and has a non-virtual destructor. To avoid the warning, you should add the following declaration of a destructor to the definition of BagInterface:virtual ~BagInterface() {} - - a / b + c * d e f convert should bereturn postExpplaceQueens should begin with bool instead of const:bool placeQueens(Queen* queenPtr);isPal should be isPalindrome if statemnt should be >=
(new Stack()).isEmpty()-> instead of a dot as follows: (new Stack())->isEmpty() new in the notation and making the following two changes near the bottom of the page:We can state this axiom succinctly in termsPage 201 (Nov. 10, 2012)
of the ADT stack operations as follows, if we represent a newly created stack by the pseudocode
expression:newStack()
(newStack()).isEmpty() = true
Note: Axioms for the ADT stackPage 220 (Mar. 5, 2015)
(newStack()).isEmpty() = true
(newStack()).pop() = false
(newStack()).peek() = error
Node<ItemType>* origChainPtr = aStack.topPtr;topPtr = nullptr; // Original stack is empty;while loop, origChainPtr = origChainPtr->getNext();while statement and again at the end of the loop's body.(new List()).isEmpty() = trueNote: Axioms for the ADT listPage 260 (Sept. 27, 2015)
1.(newList()).isEmpty() = true
2.(newList()).getLength() = 0
.
.
.
6.(newList()).remove(i) = false
.
8.(newList()).getEntry(i) = error
.
.
.
12.(newList()).setEntry(i, x) = error
replace, newItem should be newEntry.template<class ItemType> loc is misplaced, and the comments that end the while and for loops are interchanged. The corrections follow:
while ((loc > 0) && (theArray[loc - 1] > nextItem))
{
// Shift theArray[loc - 1] to the right
theArray[loc] = theArray[loc - 1];
loc--;
} // end while
// At this point, theArray[loc] is where nextItem belongs
theArray[loc] = nextItem; // Insert nextItem into sorted region
loc--;
} // end for
} // end insertionSort
partition algorithm, delete the first line in the body of the if statement:
if (indexFromLeft < indexFromRight)
{
Move theArray[firstUnknown] into S1
Interchange theArray[indexFromLeft] and theArray[indexFromRight]
. . .
Page 332 (Nov. 20, 2012)DataItem within the second for loop of the function shellSort with ItemType.
for (int unsorted = h; unsorted < n; unsorted++)
{
ItemType nextItem = theArray[unsorted];template statement: template<class ItemType>; template statement: template<class ItemType>; setItem in the class PlainBox with virtual void setItem(const ItemType& theItem);
setItem, precede item with PlainBox<ItemType>::. The statement is thenPlainBox<ItemType>::item = theItem; // item has protected accessSortedListInterface, the method getPosition should be a const method. Thus, its declaration should be virtual int getPosition(const ItemType& anEntry) const = 0;removeSorted to remove.itemCount = aList.itemCount;copyChain, delete the two statements that involve itemCount.else clause in the method copyChain, delete Node<ItemType>* that precedes copiedChainPtr, since it has been declared already.Checkpoint Question 9 asks you to defineNote that the online answers assume these changes.getPosition. You can do so by using the methods
getLengthandgetEntry.
Question 9 Define the methodgetPositionfor the classSortedListHasA.
Question 10 Repeat Checkpoint Question 7 using the methodinsertSortedof the classSortedListHasA.
Question 11 Can a client ofSortedListHasAinvoke the methodinsertof the ADT list? Explain.
Question 12 Define the methodremoveSortedfor the classSortedListHasA.
List to LinkedList.peek should be calls to peekFront.new" in the list of axioms (see the explanation given previously for page 200 in Chapter 6):
(new Queue()).isEmpty() = true
(new Queue()).dequeue() = false
(new Queue()).peekFront() = error
((new Queue()).enqueue(item)).dequeue() = new Queue()
((new Queue()).enqueue(item)).peekFront() = item
listPtr(aQueue.listPtr), to aQueue.listPtr to listPtr.ListQueue, as given in Listing 14-1, maintains the queue's back at the end of a list of the queue's entries and has the front of the queue at the beginning of that list. Note that the list is an object of the class LinkedList. What is the impact on the efficiency of the operations enqueue and dequeue if we were to maintain the queue's back at the beginning of the list and the queue's front at the list's end?
#define and template statements:#include "NotFoundException.h"add and remove, delete the */ at the end of the @param lines. contains, the postcondition should be "The binary insert should be calls to the method add.void in the class header with class:class BinaryNodeTree : public BinaryTreeInterface<ItemType>treePtr two times with tree to be consistent with the header file on page 461:template<class ItemType>
BinaryNodeTree::
BinaryNodeTree(const BinaryNodeTree& tree)
{
rootPtr = copyTree(tree.rootPtr);
} // end copy constructor else clause should be aligned with their previous else:
else if (N has only one child C)
{
// C replaces N as the child of N’s parent
if ()
nodeToConnectPtr = nodePtr->getLeftChildPtr()
else
nodeToConnectPtr = nodePtr->getRightChildPtr()
delete nodePtr
nodePtr = nullptr
return nodeToConnectPtr
}
else // N has two children
{ . . .
removeLeftmostNode, inorderSuccesssor with inorderSuccessor twice ("ss" instead of "sss")else clause with the following code:
else
{
tempPtr = removeLeftmostNode(nodePtr->getLeftChildPtr(), inorderSuccessor)
nodePtr->setLeftChildPtr(tempPtr)
return nodePtr
}readFullTree at the bottom of page 484:treePtr as the first parameter of the method.
// Builds a full binary search tree from n sorted values in a file.// Returns a pointer to the tree’s root.
readFullTree(treePtr: BinaryNodePointer, n: integer): BinaryNodePointer
if (n > 0)
{
treePtr = nullptr as its child pointers
//
leftPtr = readFullTree(treePtr->getLeftChildPtr(), n / 2)
treePtr->setLeftChildPtr(leftPtr)
//
rootItem =
treePtr->setItem(rootItem)
//
rightPtr = readFullTree(treePtr->getRightChildPtr(), n / 2)
treePtr->setRightChildPtr(rightPtr)
return treePtr
}
else
return nullptr
readTree that you made to the method readFullTree on pages 484 - 485. Also, change the recursive calls so that they are to readTree instead of to readFullTree. Thus, the method should be as follows:
// Builds a full binary search tree from n sorted values in a file.// Returns a pointer to the tree’s root.
readTree(treePtr: BinaryNodePointer, n: integer): BinaryNodePointer
if (n > 0)
{
treePtr = nullptr as its child pointers
//
leftPtr = readTree(treePtr->getLeftChildPtr(), n / 2)
treePtr->setLeftChildPtr(leftPtr)
//
rootItem =
treePtr->setItem(rootItem)
//
rightPtr = readTree(treePtr->getRightChildPtr(), (n - 1) / 2)
treePtr->setRightChildPtr(rightPtr)
return treePtr
}
else
return nullptr
add should be calls to remove. Thus, the four C++ statements should be
bst.add("Doug");
bst.remove("Nancy");
bst.remove("Bob");
bst.add("Sarah");
LinkedIterator<string> currentIterator = myList.begin();
while (currentIterator != myList.end())
{
cout << *currentIterator; // O(1) operation
++currentIterator;
} // end while
*/ instead of * /count and distance returns a value that is of type long instead of int. Thus, in the examples of their use, aceCount and numberRemaining should be declared as long instead of int.
if (items[newDataIndex] <= items[parentIndex]) itemCount itemCount / 2 in the previous for statement. Thus, our pseudocode becomesfor (index = itemCount / 2 - 1 down to 0)index in the for statement begins at 6 / 2 - 1, or 2.
TreeDictionary(int maxNumberOfEntries);add:add(searchKey: KeyType, newItem: ItemType): booleanadd, exchange the declarations of the two parameters:bool HashedDictionary<KeyType, ItemType>::add(const KeyType& searchKey,
const ItemType& newItem)
.cpp after TriNode in the #include statement.#include "TriNode.cpp"
getItem, insert data.getRecord(k) within the body of the third (innermost) if statement, as indicated:data.getRecord(k) whose search key equals searchKeygetItem.