Source Code for Data Structures and Algorithm Analysis in C++ (Fourth Edition)

Here is the source code for Data Structures and Algorithm Analysis in C++ (Fourth Edition), by Mark Allen Weiss. The materials here are copyrighted.

Many C++11 features are used. I have successfully compiled and tested the programs under g++ 4.6.2. IMPORTANT: the code WILL NOT compile on pre-C++11 compilers.

  1. If you do not have a C++11 compiler or do not want to deal with C++11 yet, use the code from the 3rd edition.
  2. If you have a C++11 compiler, some features still might not be available. Check compiler support for C++11 here. Prominent features that are used include: auto, uniform initialization (i.e. the use of braces instead of the prior style of parentheses in constructor initialization lists), long long, deduced return types (occasionally), nullptr (define to 0 if not supported), right angle brackets (>> is now ok in nested template instantiation), rvalue references and moves, range-based for loops, and some library features such as the random number generation facility.
  3. Please read Section 1.6.5, pg 44, to understand the simplifications made to present the code in the text (to avoid having code run across many pages with redundant references to figures). Except as noted, code below can be compiled by downloading everything and then compiling a test program that has provided a main and has included the appropriate .h and .cpp file. For example, this is a normal compilation first and then a second example (that illustrates one of the occasional cases where a second file is needed). 
      g++ -std=c++0x TestAvlTree.cpp
  g++ -std=c++0x TestIntCell.cpp IntCell.cpp

Complete Bundle

Individual Files

matrix.h: Simple matrix class

dsexceptions.h: Simple exception classes

Fig01_02.cpp: A simple recursive routine with a test program

Fig01_03.cpp: An example of infinite recursion

Fig01_04.cpp: Recursive routine to print numbers, with a test program

Fig01_05.cpp: Simplest IntCell class, with a test program

Fig01_06.cpp: IntCell class with a few extras, with a test program

IntCell.h: IntCell class interface (Fig 1.7)

IntCell.cpp: IntCell class implementation (Fig 1.8)

TestIntCell.cpp: IntCell test program (Fig 1.9) (need to compile IntCell.cpp also)

Fig01_10.cpp: Illustration of using the vector class

Fig01_11.cpp: Dynamically allocating an IntCell object (lame)

BuggyIntCell.cpp: Buggy IntCell class implementation (Figs 1.16 and 1.17)

Fig01_18.cpp: IntCell class with pointers and Big Five

FindMax.cpp: Function template FindMax (Figs 1.19 and 1.20)

Fig01_21.cpp: MemoryCell class template without separation

Fig01_25.cpp: Using function objects: Case insensitive string comparison

LambdaExample.cpp: (Not in the book): rewriting Fig 1.25 with lambdas

MaxSumTest.cpp: Various maximum subsequence sum algorithms

Fig02_09.cpp: Test program for binary search

Fig02_10.cpp: Euclid's algorithm, with a test program

Fig02_11.cpp: Recursive exponentiation algorithm, with a test program

RemoveEveryOtherItem.cpp: Remove every other item in a collection

Vector.h: Vector class

List.h: List class

BinarySearchTree.h: Binary search tree

TestBinarySearchTree.cpp: Test program for binary search tree

AvlTree.h: AVL tree

TestAvlTree.cpp: Test program for AVL trees

mapDemo.cpp: Map demos

WordLadder.cpp: Word Ladder Program and Word Changing Utilities

SeparateChaining.h: Header file for separate chaining

SeparateChaining.cpp: Implementation for separate chaining

TestSeparateChaining.cpp: Test program for separate chaining hash tables (need to compile SeparateChaining.cpp also)

QuadraticProbing.h: Header file for quadratic probing hash table

QuadraticProbing.cpp: Implementation for quadratic probing hash table

TestQuadraticProbing.cpp: Test program for quadratic probing hash tables (need to compile QuadraticProbing.cpp also)

CuckooHashTable.h: Header file for cuckoo hash table

CuckooHashTable.cpp: Implementation for cuckoo hash table

TestCuckooHashTable.cpp: Test program for cuckoo hash tables (need to compile CuckooHashTable.cpp also)

CaseInsensitiveHashTable.cpp: Case insensitive hash table from STL (Figure 5.23)

BinaryHeap.h: Binary heap

TestBinaryHeap.cpp: Test program for binary heaps

LeftistHeap.h: Leftist heap

TestLeftistHeap.cpp: Test program for leftist heaps

BinomialQueue.h: Binomial queue

TestBinomialQueue.cpp: Test program for binomial queues

TestPQ.cpp: Priority Queue Demo

Sort.h: A collection of sorting and selection routines

TestSort.cpp: Test program for sorting and selection routines

RadixSort.cpp: Radix sorts

DisjSets.h: Header file for disjoint sets algorithms

DisjSets.cpp: Efficient implementation of disjoint sets algorithm

TestFastDisjSets.cpp: Test program for disjoint sets algorithm

WordLadder.cpp: Word Ladder Program and Word Changing Utilities

Fig10_38.cpp: Simple matrix multiplication algorithm with a test program

Fig10_40.cpp: Algorithms to compute Fibonacci numbers

Fig10_43.cpp: Inefficient recursive algorithm (see text)

Fig10_45.cpp: Better algorithm to replace fig10_43.c (see text)

Fig10_46.cpp: Dynamic programming algorithm for optimal chain matrix multiplication, with a test program

Fig10_53.cpp: All-pairs algorithm, with a test program

Random.h: Header file for random number class

Random.cpp: Implementation for random number class

TestRandom.cpp: Test program for random number class

UniformRandom.h: Random number class using standard library

Fig10_63.cpp: Randomized primality testing algorithm, with a test program

SplayTree.h: Top-down splay tree

TestSplayTree.cpp: Test program for splay trees

RedBlackTree.h: Top-down red black tree

TestRedBlackTree.cpp: Test program for red black trees

Treap.h: Treap

TestTreap.cpp: Test program for treap

SuffixArray.cpp: Suffix array

KdTree.cpp: Implementation and test program for k-d trees

PairingHeap.h: Pairing heap

TestPairingHeap.cpp: Test program for pairing heaps

MemoryCell.h: MemoryCell class interface (Appendix)

MemoryCell.cpp: MemoryCell class implementation (Appendix)

MemoryCellExpand.cpp: MemoryCell instantiation file (Appendix)

TestMemoryCell.cpp: MemoryCell test program (Appendix)