Corrections for the Second/Third Printing

Data Structures and Other Objects Using C++
by Michael Main and Walter Savitch
ISBN 0-8053-7470-1, Softcover, 784 pages, 1997

Here is a list of corrections for the second printing of the text. You can tell whether you have the second printing of the text by checking the bottom of the publisher's page (page iv). The bottom of the second or third printing has a sequence of numbers beginning with 2 or 3. The first printing has a sequence beginning with 1, and has a longer list of corrections available at . Printings 4 through 5 have a list of corrections at .

If you find further errors, please drop me a line by email. I enjoy corresponding with readers!
--Michael Main (

Page 67, Figure 2.13: Add a return at the end: return sqrt(c_squared);

Page 73, by the arrow at the top of the page: Change "istream" to "ostream"

Page 84, bottom of column 1: Change the 90 degrees in the headings to "theta"

Page 88: The exercise does produce an approximate Gaussian distribution,
but the properties are all wrong! The formula should use the standard
deviation (not the variance). For a better approximation: generate 12 random
numbers in the range [0...1) and add the median to the value:
 (std dev) * (r1 + r2 + r3 + r4 + r5 + r6 + r7 + r8 + r9 + r10 + r11 + r12 - 6)

Page 154, two lines above the box, change to: "Cumbersome syntax of *&"

Page 157, Sample Dialogue at the bottom of the Figure 
  The correct prompt (7 lines from the end) is: 
  Please type 3 double numbers:

Page 179:
  The quotation is from P.J. Plauger (not P.L. Plauger). 

Page 229, list_clear prototype: first parameter is Node*& (rather than Node&)

Page 243, Figure 5.12: 
  The test in the if-statement should be: if (target_ptr == NULL)

Page 250:
  The operator += implementation has a bug for the case when addend is empty.
  Here's a corrected implementation:
  void Bag::operator +=(const Bag& addend)
  // Library facilities used: stdlib.h
      Node *copy_head_ptr;
      Node *copy_tail_ptr;
      if (addend.many_nodes > 0)
          list_copy(addend.head_ptr, copy_head_ptr, copy_tail_ptr);
          copy_tail_ptr->link = head_ptr;
          head_ptr = copy_head_ptr;
          many_nodes += addend.many_nodes;

Page 254, DNode definition:
  The backlink and forelink should be pointers to DNode, as shown here:
  struct DNode
      typedef ______ Item;
      Item data;
      DNode *backlink;
      DNode *forelink;

Page 272: There should be no semi-colon after the maximal implementation.

Page 297: The remove_current function is a member function, so it needs
   Bag<Item>:: in front of the function name.

Page 342, Answer to Self-Test Exercise 6 is inaccurate. Here's a better answer:
  A stack overflow can occur if the input expression has parentheses that are
  nested too dieeply. For example, consider the input expression 
  (1 + (2 + (3 + (4 + 5)))). By the time the 5 is read and pushed onto the
  stack, the 1, 2, 3 and 4 are already on the numbers stack. Thus, there is a 
  limit to how deeply we can nest this kind of subexpression without
  overflowing the stack.

Page 342, Answer 12: Reference should be Figure 7.10 on page 334.

Page 356, Figure 8.5:
  The third line in the if-statement of Step 2 should use this arithmetic
  expression: (current_second - next)
  (This replaces next - current_second).

Page 369: The second line of the figure says "Stack", but this is a Queue!

Page 384: Solution to #18 should have queues[priority].insert(entry);

Page 394: At the bottom of the page, the activation record is the THIRD call
to super_write_vertical (not the second).

Pages 450, 451, 486: leaf_ptr does not need to be a reference parameter.

Page 451, Problem 7: The limits for the example should be 1 and 3 (rather
than 1 and 4), and the final value of a[4] is upper-case 'E'.

Page 466, Documentation for the print function should have the template prefix:
  template <class Item, class SizeType>
  void print(BinaryTreeNode<Item>* node_ptr, SizeType depth)

Page 516, Step 1 of pseudocode should have: data[i] >= target.

Page 520: Change the 12 (in both trees) to 16. Otherwise they are not b-trees!

Page 543: The formula in the box needs an extra +1: H(n) = |_ log2 n_| + 1

Page 568, Solution to Exercise 12: The line used++ should be total_records++;

Page 594: The formulas at the top of the page should have
   FOUR n/4 arrays and EIGHT n/8 arrays.

Page 616: Answer 9 is missing a bracket: (k>0 && data[k] < data[parent(k)]).

Page 617: The four function calls at the bottom of Project 5 need two more
   parameters; for example: heapify_subtree(data, 4, 10);

Page 649: The right figure title is "Pond Simulation Dialogue".

Page 650, Problem 8: The new rate is 2 ounces per week (not per weed!).

Page 697-698: The call to rec_dfs in the middle of 697 needs parameters:
   rec_dfs(f, g, neighbors.current(), marked);
   Also, both pages must change NeighborIterator to NeighborIterator<Item>.

Page 705, halfway down: distance[3] should be distance[2].

Page 714, fourth line of first column should be: edges = new (bool*)[n];

Page 727: The three calls to setf should have a comma after the first
  argument (not a semi-colon).

Page 728, in the last paragraph of "Precison of Float and Double Numbers":
  Change "setpoint" to "showpoint"

Page 731, the eat_white implementation near the top of the page:
  The while loop should be: while (cin && isspace(cin.peek( )))