Source Code for Data Structures and Problem Solving with C++, Second Edition

LAST UPDATE: September 4, 2013, after 13 years
THIS CODE WAS WRITTEN ABOUT 15 YEARS AGO AND RECENT C++11 COMPILERS DO NOT ACCEPT SIGNIFICANT PARTS OF THE CODE THAT USE CERTAIN COMPILATION FEATURES. CODE HAS BEEN MODIFIED SLIGHTLY FROM ORIGINAL TO REMOVE C++11 ERRORS, THOUGH CODE IS NOT UPDATED TO C++11. THESE ARE THE MAJOR EDITS:
  1. In some places when inheritance is used, either scoping or this-> is used to access inherited members (both data or member functions)
  2. In some places, notably template return types in separate compilation units are used, the typename word is added.
  3. In some places, global scope (::) is used to access global functions that now clash with standard names (e.g. hash).
The following files were impacted: StackAr.h, StorageCell.h, TestFunctional.cpp, Iterate.cpp, Sort.h, PairingHeap.cpp, queue.h, QuadraticProbing.cpp, map.h, set.cpp, RedBlackTree.cpp, BinarySearchTree.cpp, BinaryTree.cpp, list.cpp, SortLinkedList.cpp.

Here is the source code for Data Structures and Algorithm Analysis in C++ (Second Edition), by Mark Allen Weiss. The materials here are copyrighted. I have successfully compiled and tested (most of) the programs under Borland 5.0, 5.2, 5.3, Visual C++ 5.0 and 6.0, g++ 2.8.1. Several symbols control how the code is compiled:
 
USE_DOT_H If this symbol is defined, iostream.h is used instead of iostream
SAFE_STL If this symbol is defined, the safe STL classes from the book are used. This is done by including StartConv.h and EndConv.h, which use #define to give the illusion that vector is declared as Vector, etc

Compiler Bugs

Jeffrey Walton has supplied some common workarounds for C++ compilers.

VISUAL C++ 6.0

  1. Incorrectly handles the scoping of variables declared in the for loop initialization expression.
  2. [Fixed in Service Pack 3] When the entire std namespace is imported, it appears there is a bug declaring input and output functions as friends. This shows up in the Rational examples. To fix, either do not use friends, or do not import the std namespace in its entirety (import only ostream and istream), or use fully qualified names.So the three options are:
    1. Implement operator<< by calling a public print member function
    2. using std::ostream
    3. std::ostream & operator<< ( std::ostream & out, const Object & x )
  3. getline seems to be broken when used with cin (it is one line behind).I have provided getline.cpp that seems to work better.
  4. It does not occur in the code, but function templates occasionally do not get correctly expanded -- the compiler can get confused. It is best to place the functions in class templates if you can (You can make them static, but see the g++ bugs below!).

BORLAND 5.0 (there are several different releases; some or all have these bugs)

  1. The push_back method for vector is inefficient because it expands by a fixed amount rather than doubling.
  2. iostream stuff does not seem to be in the std namespace. Fixed in 5.3 (??)
  3. Does not understand default template parameters, so many of the STL components require templates types that are normally optional. For instance, set requires that you supply less<Comparable>, as is done in the code.
  4. getline does not seem to work in 5.2 and lower (different bug than Visual 6.0!). I have provided getline.cpp that seems to work better.

g++ 2.8.1 and egs

  1. Namespaces are not implemented. There is a hack so that using namespace std; is recognized by the compiler, but clearly the Standard Library is not really in a namespace.
  2. Static methods of class templates are not supported.
  3. Does not seem to know about istringstream. Instead, the older istrstream needs to be used.

Complete Bundle

code.zip (not available, but winzip reads tar files)
code.tar
code.tar.gz

Global Utilities

StartConv.h
EndConv.h
getline.cpp

Chapter 1: Arrays, Pointers, Structures

ArrayDemo.cpp
GetInts.cpp
TestString.cpp
TestSwap.cpp

Chapter 2: Classes

IntCell.h  IntCell.cpp  TestIntCell.cpp
BuggyIntCell.cpp
DeepIntCell.cpp
Rational.h  Rational.cpp  RatMain.cpp
mystring.h  string.cpp

Chapter 3: Templates

FuncTemplates.cpp
InsSort.cpp
MemoryCell.h  MemoryCell.cpp  TestMemoryCell.cpp
Matrix.h
vector.h  vector.cpp

Chapter 4: Inheritance

Except.h
Shape.cpp 
Hiding.cpp
StaticBinding.cpp

Chapter 5: Patterns

Rectangle.cpp
Wrapper.h
Ambiguity.cpp
AutoPtr.cpp
StorageCell.h TestStorageCell.cpp
Iterator1.cpp
Iterator2.cpp
Iterator3.cpp
pair.h
Observer.cpp

Chapter 6: Running Times

MaxSum.cpp
BinarySearch.cpp

Chapter 7: STL

vector.h  vector.cpp
functional.h TestFunctional.cpp
algorithm.h
SimpleSetDemo.cpp
TestPQ.cpp

Chapter 8: Recursion

RecSum.cpp
PrintInt.cpp
BinarySearchRec.cpp
Ruler.java
FractalStar.java
Math.cpp
MaxSum.cpp
MkChnge.cpp
TicTacSlow.cpp

Chapter 9: Sorting

Duplicate.cpp
Sort.h  TestSort.cpp

Chapter 10: Randomization

Random.h  Random.cpp  RandTest.cpp
Permute.cpp
Math.cpp

Chapter 11: Fun and Games

WordSrch.cpp
TicTac.cpp

Chapter 12: Applications of Stacks -- Compilers and Parsing

Tokenizer.h  Tokenizer.cpp  Balance.cpp
Infix.cpp

Chapter 13: Utilities

Hzip.cpp
Tokenizer.h  Tokenizer.cpp  Xref.cpp

Chapter 14: Simulation

Josephus.cpp
Modems.cpp

Chapter 15: Shortest Path Algorithms

Paths.cpp Note for DotNet users: on line 40 of PairingHeap.cpp, insert the word typename in front of the line so it appears as typename PairingHeap::Position

Chapter 16: Stacks

StackAr.h  StackAr.cpp  TestStackAr.cpp
StackLi.h  StackLi.cpp  TestStackLi.cpp
QueueAr.h  QueueAr.cpp  TestQueueAr.cpp
QueueLi.h  QueueLi.cpp  TestQueueLi.cpp

Chapter 17: Linked Lists

LinkedList.h  LinkedList.cpp  SortLinkedList.h  SortLinkedList.cpp  TestLinkedList.cpp
list.h  list.cpp  TestList.cpp

Chapter 18: Trees

BinaryTree.h  BinaryTree.cpp
Iterate.h  Iterate.cpp  TestBinaryTree.cpp

Chapter 19: Search Trees

BinarySearchTree.h  BinarySearchTree.cpp  TestBinarySearchTree.cpp
RedBlackTree.h  RedBlackTree.cpp  TestRedBlackTree.cpp
AATree.h  AATree.cpp  TestAATree.cpp
set.h  set.cpp  TestSet.cpp
map.h  map.cpp  TestMap.cpp

Chapter 20: Hash Tables

QuadraticProbing.h  QuadraticProbing.cpp  TestQuadraticProbing.cpp

Chapter 21: Heaps

BinaryHeap.h  BinaryHeap.cpp  TestBinaryHeap.cpp
queue.h  queue.cpp  TestQueue.cpp

Chapter 22: Splay Trees

SplayTree.h  SplayTree.cpp  TestSplayTree.cpp

Chapter 23: Pairing Heaps

PairingHeap.h  PairingHeap.cpp  TestPairingHeap.cpp Note for DotNet users: on line 40 of PairingHeap.cpp, insert the word typename in front of the line so it appears as typename PairingHeap::Position

Chapter 24: Disjoint Sets

DisjSets.h  DisjSets.cpp  TestDisjSets.cpp

Appendix D: Primitive Arrays

PointerHopping.cpp