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

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 the programs under Borland 5.0, Visual C++ 5.0 and 6.0, CodeWarrior Pro Release 2 (Windows), g++ 2.7.2 and 2.8.1, and SunPro 4.1. Greg Ozbirn from U.T. Dallas has rewritten the code using ANSI C++. This mostly involves fixing the header files. Click here to obtain the ANSI C++ conversion

Known Bugs

TestCursorList.cpp does not compile under g++ 2.7.2. I think it is a problem with static template members, which g++ does not understand until g++ 2.8.1.
Metrowerks insists on compiling the STL, which causes conflicts for swap and merge in Sort.h. Also, it does not understand default template parameters, making its vector and string incompatible with some of the code. The easy fix is to add preprocessor macros as follows: in vector.h, #define vector Vector; similarly for string.h and in Sort.h. This works as long as iostream.h is included prior to the other header files, as is done in the online code.

Compilation Instructions

Here are compilation instructions for g++, SunPro, Borland 5.0, and Visual 5.0. (How to setup Windows for Visual command line compilation.) You can use this to guide you on how to generate project files for Visual C++. Throughout I am assuming 32-bit ints. All template classes have the header file include the .cpp file, even though this defeats the purpose of separate compilation. There are ways around this, but I'd rather keep everything simple for now. Jeffrey Walton has supplied some common workarounds for C++ compilers. Finally, here is a zip file that contains CodeWarrior projects. You'll have to get everything in the correct directories. (Does not include some late additions from Chapter 1; check back later).

Complete Bundle

Unix tar | gzip
Unix tar
Note to Macintosh users: There is a utility to read zip files. Click here to download.

Individual Files

mystring.h: If you don't have a string type

string.cpp: If you don't have a string type

vector.h: If you don't have a vector type

vector.cpp: If you don't have a vector type

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)

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.14 and 1.15)

Fig01_16.cpp: IntCell class with pointers and Big Three

FindMax.cpp: Function template FindMax (Figs 1.17 and 1.18)

Fig01_19.cpp: MemoryCell class template without separation

MemoryCell.h: MemoryCell class interface (Fig 1.20)

MemoryCell.cpp: MemoryCell class implementation (Fig 1.21)

TestMemoryCell.cpp: MemoryCell test program (Fig 1.22)

Fig01_23.cpp: Using Comparable templates: Employee class example

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

LinkedList.h: Header file for linked list

LinkedList.cpp: Implementation for linked list

TestLinkedList.cpp: Test program for linked list package

Polynomial.cpp: Polynomials

CursorList.h: Header file for cursor linked list

CursorList.cpp: Implementation for cursor linked list

TestCursorList.cpp: Test program for cursor implementation of linked lists

StackAr.h: Header file for stack: array version

StackAr.cpp: Implementation for stack: array version

TestStackAr.cpp: Test program for (array-based) stacks

StackLi.h: Header file for stack: list version

StackLi.cpp: Implementation for stack: list version

TestStackLi.cpp: Test program for (list-based) stacks

QueueAr.h: Header file for queue: array version

QueueAr.cpp: Implementation for queue: array version

TestQueueAr.cpp: Test program for queues

BinarySearchTree.h: Header file for binary search tree

BinarySearchTree.cpp: Implementation for binary search tree

TestBinarySearchTree.cpp: Test program for binary search tree

AvlTree.h: Header file for AVL tree

AvlTree.cpp: Implementation for AVL tree

TestAvlTree.cpp: Test program for AVL trees

SeparateChaining.h: Header file for separate chaining

SeparateChaining.cpp: Implementation for separate chaining

TestSeparateChaining.cpp: Test program for separate chaining hash tables

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

BinaryHeap.h: Header file for binary heap

BinaryHeap.cpp: Implementation for binary heap

TestBinaryHeap.cpp: Test program for binary heaps

LeftistHeap.h: Header file for leftist heap

LeftistHeap.cpp: Implementation for leftist heap

TestLeftistHeap.cpp: Test program for leftist heaps

BinomialQueue.h: Header file for binomial queue

BinomialQueue.cpp: Implementation for binomial queue

TestBinomialQueue.cpp: Test program for binomial queues

Sort.h: A collection of sorting and selection routines

TestSort.cpp: Test program for sorting and selection routines

DisjSets.h: Header file for disjoint sets algorithms

DisjSets.cpp: Efficient implementation of disjoint sets algorithm

TestFastDisjSets.cpp: Test program for disjoint sets algorithm

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

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

SplayTree.h: Header file for top-down splay tree

SplayTree.cpp: Implementation for top-down splay tree

TestSplayTree.cpp: Test program for splay trees

DSL.h: Header file for deterministic skip list

DSL.cpp: Implementation for deterministic skip list

TestDSL.cpp: Test program for determinstic skip lists

RedBlackTree.h: Header file for top-down red black tree

RedBlackTree.cpp: Implementation for top-down red black tree

TestRedBlackTree.cpp: Test program for red black trees

Treap.h: Header file for treap

Treap.cpp: Implementation for treap

TestTreap.cpp: Test program for treap

AATree.h: Header file for AA-tree

AATree.cpp: Implementation for AA-tree

TestAATree.cpp: Test program for AA-trees

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

PairingHeap.h: Header file for pairing heap

PairingHeap.cpp: Implementation for pairing heap

TestPairingHeap.cpp: Test program for pairing heaps

FigA_04.cpp: Example of push_back with vectors

FigA_05.cpp: Queue implemented with STL list

FigA_06.cpp: Example of set with reverse order

Concordance1.cpp: Concordance program using STL

Concordance2.cpp: Concordance program not using STL

Graph1.cpp: Shortest path program using STL

Graph2.cpp: Shortest path program not using STL