Chapter 1 Review of C++

1.1 THE STANDARD C++ PROGRAMMING LANGUAGE
1.2 CONDITIONALS
1.3 OPERATORS
1.4 ITERATION
1.5 FUNCTIONS
1.6 STRINGS
1.7 FILES

Chapter 2 Pointers and Arrays

2.1 POINTERS
2.2 DERIVED TYPES
2.3 REFERENCES
2.4 PASSING BY REFERENCE
2.5 NULL POINTER EXCEPTIONS
2.6 THE new AND delete OPERATORS
2.7 ARRAYS
2.8 DYNAMIC ARRAYS
2.9 PASSING AN ARRAY TO A FUNCTION
2.10 MULTIDIMENSIONAL ARRAYS

Chapter 3 Classes

3.1 A point CLASS
3.2 INSTANCES,IMPLICIT ARGUMENTS,AND THE this POINTER
3.3 COMPILING CLASSES AND THEIR CLIENT PROGRAMS
3.4 FRIEND FUNCTIONS
3.5 A Line CLASS
3.6 A CLASS FOR RANDOM NUMBERS
3.7 STATIC MEMEBRS
3.8 COMPOSITION
3.9 INHERITANCE

Chapter 4 Recursion

4.1 THE FACTORIAL FUNCTION
4.2 TRACING A RECURSIVE CALL
4.3 THE FIBONACCI SEQUENCE
4.4 BINOMIAL COEFFICIENTS
4.5 THE EUCLIDEAN ALGORITHM
4.6 INDUCTIVE PROOF OF CORRECTNESS
4.7 COMPLEXITY ANALYSIS OF RECURSIVE ALGORITHMS
4.8 DYNAMIC PROGRAMMING
4.9 THE TOWERS OF HANOI
4.10 MUTUAL RECURSION

Chapter 5 Stacks

5.1 THE stack INTERFACE
5.2 USING stack OBJECTS
5.3 APPLICATIONS OF STACKS
5.4 REMOVING RECURSION
5.5 CONTIGUOUS IMPLEMENTATION
5.6 LINKED IMPLEMENTATION

Chapter 6 Queues

6.1 THE queue INTERFACE
6.2 USING queue OBJECTS
6.3 APPLICATIONS OF QUEUES
6.4 CONTIGUOUS IMPLEMENTATION
6.5 LINKED IMPLEMENTATION

Chapter 7 Lists

7.1 THE list INTERFACE
7.2 UNSING list OBJECTS
7.3 ITERATORS
7.4 APPLICATIONS
7.5 CIRCULAR LISTS
7.6 ORDERED LISTS
7.7 AN UNBOUNDED Integer CLASS
7.8 IMPLENENTION OF THE List CLASS

Chapter 8 Tables

8.1 THE STANDARD pair TYPE
8.2 APPLICATIONS USING THE map CLASS TEMPLATE
8.3 HASH TABLES
8.4 HASH FUNCTIONS
8.5 SEPARATE CHAINING

Chapter 9 Trees

9.1 TREE TERMINOLOGY
9.2 DECISION TREES AND TRANSITION DIAGRAMS
9.3 TREE TRAVERSAL ALGORITHMS
9.4 A Tree CLASS INTERFACE
9.5 IMPLEMENTATION OF THE Tree CLASS

Chapter 10 Trees

10.1 DEFINITIONS
10.2 COUNTING BINARY TREES
10.3 FULL BINARY TREES
10.4 IDENTITY,EQUALITY,AND ISOMORPHISM
10.5 COMPLETE BINARY TREES
10.6 TREE TRAVERSALS
10.7 EXPRESSION TREES
10.8 FORESTS
10.9 A BinaryTree CLASS INTERFACE
10.10 IMPLEMENTATION OF THE BinaryTree CLASS

Chapter 11 Search Trees

11.1 BINARY SEARCH TREES
11.2 IMPLEMENTATION OF BINARY SEARCH TREES
11.3 PERFORMANCE CHARACTERISTICS OF BINARY SEARCH TREES
11.4 AVL TREES

Chapter 12 Heaps and Priority Queues

12.1 HEAPS
12.2 THE NATURAL MAPPING
12.3 INSERTION INTO A HEAP
12.4 REMOVAL FROM A HEAP
12.5 PRIORITY QUEUES
12.6 USING priority_queue OBJECTS
12.7 USING A HEAP TO IMPLEMENT A PriorityQueue CLASS TEMPLATE
12.8 APPLICATIONS OF PRIORITY QUEUES

Chapter 13 Soring

13.1 PRELIMINARIES
13.2 THE BUBBLE SORT
13.3 THE SELECTION SORT
13.4 THE INSERTION SORT
13.5 THE MERGE SORT
13.6 THE QUICK SORT
13.7 HEAPS
13.8 THE HEAP SORT
13.9 HTE SHELL SORT
13.10 THE SPEED LIMIT FOR EXCHANGE SORTS

Appendix A References
Appendix B Essential Mathematics

B.1 THE FLOOR AND CEILING FUNCTIONS
B.2 LOGARITHMS
B.3 THE FIRST PRINCIPLE OF MATHEMATICAL INDUCTION
B.4 THE SECOND PRINCIPLE OF MATHEMATICAL INDUCTION
B.5 GEOMETRIC SERIES
B.6 SUMMATION FORMULAS
B.7 ASYMPTOTIC COMPLEXITY CLASSES
B.8 HARMONIC NUMBERS
B.9 STIRLING'S FORMULA
B.10 FIBONACCI NUMBERS
B.11 THE GOLDEN MEAN
B.12 THE EUCLIDEAN ALGORITHM

Appendix C Standard Container Classes

C.1 THE vector CLASS TEMPLATE
C.2 THE deque CLASS TEMPLATE
C.3 THE stack CLASS TEMPLATE
C.4 THE queue CLASS TEMPLATE
C.5 THE priority_queue CLASS TEMPLATE
C.6 THE list CLASS TEMPLATE
C.7 THE map CLASS TEMPLATE
C.8 THE set CLASS TEMPLATE

Appendix E Example Classes

E.1 A BinaryTree CLASS
E.2 A BinarySearchTree CLASS
E.3 A Card CLASS
E.4 A Concordance CLASS
E.5 A Date CLASS
E.6 A Deck CLASS
E.7 A Hand CLASS
E.8 A Hash FUNCTION STRUCTURE TEMPLATE
E.9 A HashTable CLASS TEMPLATE
E.10 A Line CLASS
E.11 A List CLASS TEMPLATE
E.12 A Matrix CLASS TEMPLATE
E.13 AN OrderedList CLASS
E.14 A Person CLASS
E.15 A Point CLASS
E.16 A Polynomial CLASS
E.17 A PriorityQueue CLASS TEMPLATE
E.18 A Purse CLASS
E.19 A Queue CLASS
E.20 A Random CLASS
E.21 A RandomLine CLASS
E.22 A RandomPoint CLASS
E.23 A Ratio CLASS
E.24 A Rational CLASS
E.25 A SelfOrganizingList CLASS
E.26 A Stack CLASS TEMPLATE
E.27 A Tree CLASS

Index