Corrections for the First 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 first printing of the text. You can tell whether you have the first printing of the text by checking the bottom of the publisher's page (page iv). The bottom of the first printing has a sequence of numbers beginning with 1. The second/third printings have a sequence beginning with 2 or 3, and has a shorter 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 46, line 2: "When your write" is changed to "When you write".

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, should be: "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 222, line 4: "list_locate" is changed to "list_search"

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).

Page 410, 5 lines from the bottom: Change "2.0" to "3.0".

Page 417, Solution number 3:
  Each of these lines: cout << "Hip";
  is changed to this:  cout << "Hip" << endl;

Page 420, end of 2nd column:
  The final asterisk is moved right to align with the end of the previous line.

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 455, line 11: Change the line to: cout << node_ptr->data << endl;

Page 464, Exercise 11: Change "numbers" to "letters".

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)

Pages 476-477, all four tree diagrams: Change the upper 54 to 53.

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

Page 519, line 7: Change "data_count" to "child_count".

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 557, 2 lines from the bottom: Change "never_used" to "is_vacant".

Page 566, 3rd column of the figure: Change 1,72 to a decimal point 1.72

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, Exercise 4: Change sections 2b and 2c as given here:
  2b. If the area before the pivot index has more than one element, then
      we must sort this area. This area begins at data[i] and has
      pivot_index elements, so push i and pivot_index onto the stack.
  2c. If the area after the pivot index has more than one element, then
      we must sort this area. This area begins at data[i+pivot_index+1]
      and has n - pivot_index - 1 elements, so push i+pivot_index+1
      and n - pivot_index - 1 onto the stack.

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 650, end of Exercise 11: Change the if statement to:
  if (rand( )/double(RAND_MAX) < chance)
  (also set the word "if" in italic).

Page 660, Solution 11:
  Use italic for the two "if"s, and change "MAX_RAND" to "double(RAND_MAX)".

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: Change "cout.setprecision(12);" to "cout.precision(12);"
  and, in the last paragraph of "Precison of Float and Double Numbers":
  Change "setpoint" to "showpoint"

Page 738, first line of the Header File: Change "item.h" to "items.h"

Page 739, in the precondition after the third shaded box:
  Change "0 <= i < n" to "0 <= i <= n".

Page 740, just before the indentation begins, insert a new line:
  #include <stdlib.h>  // Provides size_t from stdlib.h

Page 743, line 6: Change "SizeType(i+1)" to simply "i+1".

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