using namespace std;
template
statement: template<class ItemType>; // Indicates this is a template definition
template
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 string
anArray[0] <= anArray[1] <= anArray[2] <= . . . <= anArray[size - 1]
target
:anArray[first] <= target <= anArray[last]
anArray
getNumberOfGroups
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 string
ArrayBag
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 clear
itemCount = aBag.itemCount;
Node<ItemType>* origChainPtr = aBag.headPtr;
while
statement, replace origPtr
with origChainPtr
:while (origChainPtr != nullptr)
while
loop, origChainPtr = origChainPtr->getNext(); // Advance pointer
while
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 fillVector
getPointerTo
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 postExp
placeQueens
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() = true
Note: 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 access
SortedListInterface
, 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
getLength
andgetEntry
.
Question 9 Define the methodgetPosition
for the classSortedListHasA
.
Question 10 Repeat Checkpoint Question 7 using the methodinsertSorted
of the classSortedListHasA
.
Question 11 Can a client ofSortedListHasA
invoke the methodinsert
of the ADT list? Explain.
Question 12 Define the methodremoveSorted
for 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 (
C is a left child)
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 =
pointer to new node with nullptr
as its child pointers
//
Construct the left subtree
leftPtr = readFullTree(treePtr->getLeftChildPtr(), n / 2)
treePtr->setLeftChildPtr(leftPtr)
//
Get the root
rootItem =
next item from file
treePtr->setItem(rootItem)
//
Construct the right subtree
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 =
pointer to new node with nullptr
as its child pointers
//
Construct the left subtree
leftPtr = readTree(treePtr->getLeftChildPtr(), n / 2)
treePtr->setLeftChildPtr(leftPtr)
//
Get the root
rootItem =
next item from file
treePtr->setItem(rootItem)
//
Construct the right subtree
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): boolean
add
, 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 searchKey
getItem
.