Walls and Mirrors: C++ (4th ed.) Errata
Data Abstraction and Problem Solving with C++
Walls and Mirrors
(4th edition)
by Frank M. Carrano
Errata List
Last updated on December 13, 2005.
The date after each error is the date it was posted on this list. Subsequent printings of the book will correct these errors.
If you find an error and it is not on this list, please
e-mail a description of the error and the page number.
Chapter 1
Page 11 (Apr. 23, 2004)
In the lower half of the page, the comments in the code should have superscripts, as follows:
// Computes an approximation to ex for a real x
// Invariant: t == xk-1/(k-1)! and
// s == 1+x+x2/2!+...+xk-1/(k-1)!
Chapter 2
Page 111, Exercise 23 (Feb. 7, 2005)
In the definition of the function gcd, the first return value should be b instead of a. Thus, replace
if ( a % b == 0 ) //base case
return a;
with
if ( a % b == 0 ) //base case
return b;
Chapter 3
Page 131 (Dec. 13, 2005)
In the last axiom on the page, change retrieve(x) to retrieve(i)
Chapter 4
Page 171 (Apr. 23, 2004)
Item 5 should read, as follows:
5. If, for some reason, new cannot allocate memory, it throws the exception
std::bad_alloc
Page 172 (Apr. 23, 2004)
Delete Item 6.
Change 7 to 6.
Erase the number 8.
Page 174, first paragraph (May 5, 2004)
Replace the first sentence with
You also can use a pointer offset notation to reference any array element.
Replace the sentence in parentheses with
This notation uses pointer arithmetic.
Page 179, next-to-last paragraph, Line 4 (Apr. 23, 2004)
Change *Node to Node*
Page 189, (Apr. 26, 2004)
Delete the #include statement for ListException.
Delete ListException from the throw clause of the function insert.
Page 191, next-to-last line of code (Apr. 23, 2004)
Delete the assert statement.
Page 192, Line 9 (Apr. 23, 2004)
Delete the assert statement.
Page 194 (Apr. 26, 2004)
Add a throw clause to each of the definitions of the functions retrieve and insert, so that they begin
void List::retrieve(int index, ListItemType& dataItem) const throw(ListIndexOutOfRangeException)
void List::insert(int index, ListItemType newItem) throw(ListIndexOutOfRangeException)
When the functions retrieve and insert throw an exception, the message should begin ListIndexOutOfRangeException instead of ListOutOfRangeException.
Pages 194 - 195 (Apr. 26, 2004)
In the definition of the function insert, do not compare newPtr
with NULL after a new ListNode is allocated. Instead, replace
the else clause of the first if statement with
else
{ // create new node and place newItem in it
ListNode *newPtr = new ListNode;
size = newLength;
newPtr->item = newItem;
// attach new node to list
if (index == 1)
{ // insert new node at beginning of list
newPtr->next = head;
head = newPtr;
}
else
{ ListNode *prev = find(index-1);
// insert new node after node
// to which prev points
newPtr->next = prev->next;
prev->next = newPtr;
} // end if
} // end if
Page 195 (Apr. 26, 2004)
Add a throw clause to the definition of the function remove, so that it begins
void List::remove(int index) throw(ListIndexOutOfRangeException)
When remove throws an exception, the message should begin ListIndexOutOfRangeException instead of ListOutOfRangeException.
Page 206 (Apr. 23, 2004)
Replace
if (newPtr == NULL)
throw ListException("ListException: insert cannot allocate memory");
else
{ newPtr->item = newItem;
newPtr->next = headPtr;
headPtr = newPtr;
} // end if
with
newPtr->item = newItem;
newPtr->next = headPtr;
headPtr = newPtr;
Chapter 5
page 259 (May 5, 2004)
Replace the first line of the pseudocode function endPre with
+endPre(in first: integer): integer
Chapter 6
Page 297 (Apr. 23, 2004)
Line 2: Delete the throw clause from the function push.
At the bottom of the page, delete two assert statements.
Page 298 (Apr. 23, 2004)
Delete the throw clause from the function push.
Replace the if-else statement in the function push with
// set data portion of new node
newPtr->item = newItem;
// insert the new node
newPtr->next = topPtr;
topPtr = newPtr;
Page 320 (Apr. 26, 2004)
Indent the statements
if (!aStack.isEmpty())
aStack.getTop(topCity);
so that the if statement aligns with the preceding close brace.
Chapter 7
Page 347 (Apr. 23, 2004)
Delete the throw clause from the function enqueue
and the comments that describe the exception.
Page 348 (Apr. 23, 2004)
Delete the throw clause from the function enqueue.
Replace the if-else statement in the function enqueue with
newPtr->item = newItem;
newPtr->next = NULL;
Page 349 (Apr. 23, 2004)
Delete the line
} // end if
Chapter 8
Page 400, Figure 8-9b (Jan. 6, 2005)
The first line of the function displayStatistics should be
virtual void displayStatistics() const
Page 407 (Jan. 6, 2005)
The two constructors in ListNode should not end with a semicolon.
Page 414 (Jan. 6, 2005)
Near the bottom of the page, the second argument of sortedRetrieve should be a reference argument:
virtual void sortedRetrieve(int index, ListIndexType& anItem) const
Page 418 (Jan. 6, 2005)
The two constructors in ListNode should not end with a semicolon.
Pages 420 - 421 (Apr. 23, 2004)
Replace the definition of the function insert with
template <class T>
void List<T>::insert(int index, T newItem) throw(ListIndexOutOfRangeException)
{
int newLength = getLength() + 1;
if ((index < 1) || (index > newLength))
throw ListIndexOutOfRangeException(
"ListIndexOutOfRangeException: insert index out of range");
else
{ // create new node and place newItem in it
ListNode<T> *newPtr = new ListNode<T>;
size = newLength;
newPtr->item = newItem;
// attach new node to list
if (index == 1)
{ // insert new node at beginning of list
newPtr->next = head;
head = newPtr;
}
else
{ ListNode<T> *prev = find(index-1);
// insert new node after node
// to which prev points
newPtr->next = prev->next;
prev->next = newPtr;
} // end if
} // end if
} // end insert
Page 424 (Apr. 23, 2004)
The declaration of count should be just before the for statement, not within it.
Page 428 (Jan. 6, 2005)
The constructor in ListIterator should match its definition of page 429:
ListIterator(const *aList, ListNode *nodePtr);
Pages 432 - 433 (Apr. 23, 2004)
In the definition of the function insert at the bottom of page 432,
replace the if-else statement that compares newPtr with NULL
by the statements that are in its else clause.
In the return statement on page 433, this should be bold.
Chapter 9
page 489 (Apr. 23, 2004)
The third for should be bold.
Chapter 10
page 509 (Jan. 6, 2005)
setRootData and attachLeft should not throw a TreeException if a new node cannot be allocated. Thus, make the following changes:
Delete throw TreeException from setRootData, and
delete its last two comments.
Delete the last comment on the page, and change the preceding line to
// a binary tree. Throws TreeException if the
page 510 (Jan. 6, 2005)
attachRight should not throw TreeException if a new node cannot be allocated. Thus, make the following changes:
In attachRight, change the 2nd comment to
// a binary tree. Throws TreeException if the
and delete the 3rd comment.
page 519 (Jan. 6, 2005)
The first constructor in TreeNode should not end with a semicolon.
page 521 (Jan. 6, 2005)
Near the top of the page, delete throw(TreeException) from setRootData.
Near the bottom of the page, copyTree should not throw TreeException, so delete the last sentence in its comments.
page 522 (Apr. 23, 2004)
Delete the assert statement from the constructor at the bottom of the page.
page 523 (Apr. 23, 2004)
Line 2: Delete the assert statement.
In the definition of the function setRootData at the bottom of the page,
1. Delete the throw clause
2. Delete the if statement that compares root with NULL
page 524 (Apr. 23, 2004)
In the definition of the function attachLeft,
delete the if statement that compares root->leftChildPtr with NULL.
In the definition of the function attachRight,
delete the if statement that compares root->rightChildPtr with NULL.
page 524 (Jan. 6, 2005)
Three else clauses are labeled with the comment Assertion. Add assert statements, as follows:
else // Assertion: nonempty tree; no left child
{
assert(root != NULL && root->leftChildPtr == NULL);
root->leftChildPtr = new treeNode(newItem, NULL, NULL);
} // end if
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
else // Assertion: nonempty tree; no right child
{
assert(root != NULL && root->rightChildPtr == NULL);
root->rightChildPtr = new treeNode(newItem, NULL, NULL);
} // end if
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
else // Assertion: nonempty tree; no left child
{
assert(root != NULL && root->leftChildPtr == NULL);
root->leftChildPtr = leftTree.root;
leftTree.root = NULL;
} // end if
page 525 (Jan. 6, 2005)
In attachRightSubtree near the top of the page, add an assert statement to the 2nd else clause, as follows:
else // Assertion: nonempty tree; no right child
{
assert(root != NULL && root->rightChildPtr == NULL);
root->rightChildPtr = rightTree.root;
rightTree.root = NULL;
} // end if
page 526 (Apr. 23, 2004)
In the definition of the function copyTree at the bottom of the page,
delete the if statement that compares newTreePtr with NULL.
page 556
Line 3 (Dec. 22, 2004)
Either omit the default constructor for KeyedItem or move it to the private section and delete the semicolon.
Line 12 (June 1, 2004)
Replace the comment just before the end of the class KeyedItem with
//... and possibly other data
page 557 (Dec. 9, 2004)
Skip a line before the signature of searchTreeInsert and
remove the blank line after it.
page 558 (Jan. 6, 2005)
In the protected section, delete throw(TreeException) from insertItem.
page 560, last line (Apr. 23, 2004)
At the bottom of the page, delete the throw clause from the function insertItem.
page 561 (Apr. 23, 2004; clarified Jan. 6, 2005)
In the definition of the function insertItem at the top of the page,
delete these 3 lines:
// was allocation successful?
if (treePtr == NULL)
throw TreeException("TreeException: insert failed");
Chapter 11
page 594 (Dec. 22, 2004)
In KeyedItem, either omit the default constructor or move it to the private section and delete the semicolon.
page 605, Line 8 (Dec. 14, 2004)
After the default constructor, add the destructor
virtual ~Table();
and change the comments to
// copy constructor is supplied by the compiler
page 609, mid-page (Dec. 14, 2004)
After the default constructor, add the destructor
virtual ~Table();
and change the comments to
// copy constructor is supplied by the compiler
page 609 (Apr. 23, 2004)
Delete the throw clause from the function tableInsert.
page 610 (Apr. 23, 2004)
Delete the throw clause from the function tableInsert.
Replace the try-catch block with
bst.searchTreeInsert(newItem);
++size;
page 623, Line 4 (Dec. 14, 2004)
After the default constructor, add the destructor
virtual ~Heap();
and change the comments to
// copy constructor is supplied by the compiler
page 626, bottom third of page (Dec. 14, 2004)
In the class PriorityQueue, replace the comments after public with
virtual ~PriorityQueue();
// default constructor and copy constructor
// are supplied by the compiler
page 631, Line 7 (Dec. 9, 2004)
Insert the word Sorted in the third comment after the for statement:
// Sorted region by swapping items
page 634 (June 1, 2004)
Delete the 2nd line of code
Iter (const value_type& e)
Chapter 12
page 679 (Dec. 9, 2004)
The figure labeled 12-25 should be Figure 12-26, and
the figure labeled 12-26 should be Figure 12-25.
page 688 (Dec. 9, 2004)
In the next-to-last sentence, change 20 to 40.
page 690, Figures 12-42 and 12-43 (Dec. 9, 2004)
Figure 12-42: Add a node containing 5 as the left child of the node containing 10 in each part of the figure.
Figure 12-43: The subtree T1 should have a height of h + 1.
page 703, Line 4 (Dec. 14, 2004)
The destructor should be virtual:
virtual ~HashTable();
In the declarations of tableDelete and tableRetrieve,
change bool to void and remove the extra semicolons.
Thus, these lines should be
virtual void tableDelete(KeyType searchKey)
throw(TableException);
virtual void tableRetrieve(KeyType searchKey,
TableItemType& tableItem) const
throw(TableException);
page 704 (Dec. 22, 2004)
In KeyedItem:
Either omit the default constructor or move it to the private section and delete the semicolon.
In ChainNode:
Replace the semicolon with the empty body {}
page 705, mid-page (Dec. 22, 2004)
The second parameter of tableRetrieve should be an output parameter, not an input parameter:
tableRetrieve(in searchKey:KeyType,
out tableItem:TableItemType)
throw TableException
Chapter 13
page 737 (Jan. 6, 2005)
The implementation of the constructor should be
Graph::Graph(int n)
{
map<int, int> element;
adjList.assign(n, element);
numVertices = n;
} // end constructor
page 745 (June 1, 2004)
The alignment within the while loop is incorrect. It should read, as follows:
while (!q.empty())
{
// get the edge at the front if the queue
e = q.front();
// pop the edge off the queue
q.pop();
// if the vertex w has not visited yet, visit it
if (mark[e.w] == -1)
{
int v = e.v,
w = e.w,
weight = e.weight;
mark[w] = count++; // mark w visited
parents[w] = v; // store w's parent
// go through adjacency list of w
m = g.adjList[w];
for (iter = m.begin(); iter != m.end(); iter++)
// if w's neighbor vertices have not been visited,
// push the edge on the queue
if (mark[iter->first] == -1)
q.push(Edge(w, iter->first, iter->second));
} // end if
} // end while
pages 749 and 750 (Dec. 22, 2004)
The figure at the bottom of page 749 should be numbered 13-18, and
the figure at the top of page 750 should be numbered 13-17.
End of errata page