Corrections for Printings 4 through 5 (August 1998)

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 printing printings 4 through 5 of the text. You can tell whether you have these printings of the text by checking the bottom of the publisher's page (page iv). The bottom of the printing has a sequence of numbers beginning with 4 or 5. The first printing has a sequence beginning with 1, and has a longer list of corrections available at . Printings 2/3 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 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 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 12: Reference should be Figure 7.10 on page 334.

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 543: The formula in the box needs an extra +1: H(n) = |_ log2 n_| + 1

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 727: The three calls to setf should have a comma after the first
  argument (not a semi-colon).