Like all Schaum's Outline Series books, this is intended to be used primarily for self study,preferably in conjunction with a regular course in data structures using the C++ programming language.
　　 The book includes over 200 examples and problems. The author firmly believes that the principles of data structures can be learned from a well-constructed collection of examples with complete explanations. This book is designed to provide that support.
　　 Source code for all the examples and problems in this book may be downloaded from the author's Web sites: http : //www. richmond. edu/-hubbard, http : //www. jhubbard.net,or http : / /www. projectEuclid . net. These sites also contain any corrections and addenda for the book.

Like all Schaum's Outline Series books, this is intended to be used primarily for self study,preferably in conjunction with a regular course in data structures using the C++ programming language.
　　 The book includes over 200 examples and problems. The author firmly believes that the principles of data structures can be learned from a well-constructed collection of examples with complete explanations. This book is designed to provide that support.
　　 Source code for all the examples and problems in this book may be downloaded from the author's Web sites: http : //www. richmond. edu/-hubbard, http : //www. jhubbard.net,or http : / /www. projectEuclid . net. These sites also contain any corrections and addenda for the book.
　　 I wish to thank all my friends, colleagues, students, and the McGraw-Hill staff who have helped me with the critical review of this manuscript. Special thanks to my wife,Anita Hubbard for her advice, encouragement, and supply of creative problems for this book. Many of the original ideas used here are hers.
　　 JOHN R. HUBBARD
　　 Richmond, Virginia

Chapter I 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 MEMBERS
3.S COMPOSITION
3.9 INHERITANCE
Chapter 4 Recursion
4.1 THE FACTORIAL FUNCCTON
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.l THE stack INTERFACE
5.2 USING stack OBJECTS
5.3 APPLICAUONS OF STACKS
5.4 REMOVING RECURSION
5 .5 CONTIGUOUS IMPLEMENTATION
5 .6 LINKED IMPLEMENTAUON
Chapter 6 Queues
6.I 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.I THE list INTERFACE
7.2 USING list OBJECTS
7.3 ITWRATORS
7.4 APPLICARIONS
7.5 CIRCULAR LISTS
7.6 ORDERED LISTS
7.7 AN UNBOUNDED Integer CLASS
7.8 IMPLEMENITON OF THE List CLASS
Chapter 8 Tables
8.l THE STANDARD pair TYPE
8.2 APPLICAUONS USING THE map CLASS TEMPLATE
8.3 HASH TABLES
8.4 HASH FUNCNONS
8.5 SEPARATE CHAININO
Chapter 9 Trees
9.1TREE TERMINOLOGY
9.2 DECISION TREES AND TRANSITION DIAGRAMS
9.3 TREE TRAVERS AL ALGORITHMS
9.4 A Tree CLASS INTERFACE
9.5 IMPLEMENTATION OF THE Tree CLASS
Chapter 10 Binary Trees
1O.l DEFTNITIONS
IO.2 COUNTING BINARY TREES
IO.3 FULL BINARY TREES
IO.4 IDENTITY, EQUALITY, AND ISOMORPHISM
IO.5 COMPLETE BINARY TREES
IO.6 TREE TRAVERSALS
IO.7 EXPRESSION TREES
IO.8 FORESTS
IO.9 A BinaryTree CLASS INTERFACE
IO.IO IMPLEMENTATION OF THE BinaryTree CLASS
Chapter II Search Tree
1l.l BINARY SEARCH TREES
1l.2 IMPLEMENTATION OF BINARY SEARCH TREES
l1.3 PERFORMANCE CHARACTERISTICS OF BINARY SEARCH TREES
11.4 AVL TREES
Chapter 12 Heaps and Priority Queues
12.I HEAPS
12.2 THE NATURAL MAPPING
12.3 INSERUON INTO A HEAP
12.4 REMOVAL FROM A HEAP
12.5 PRIORITY Queues
I2.e USING priority queue OBJECTS
12.7 USING A HEAP TO IMPLEMENT A PriorityQueue CLASS TEMPLATE
12.8 APPLICATIONS OF PRIORITY Queues
Chapter 13 Sorting
13.l 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 THE SHELL SORT
13. IOTHE SPEED LIMIT FOR EXCHANGE SORTS
Appendix A References
Appendix B Essential Mathematies
B.l THE FLOOR AND CEILING FUNCTIONS
B.2 LOGARUHMS
B.3 THE FIRST PRINCIPLE OF MATHEMATICAL INDUCTION
B.4 THE SECOND PRINCIPLE OF MATHEMATICAL INDUCUON
B .5 GEOMETRIC SERIES
B.6 SUMMATION FORMULAS
B.7 ASYMPTOTIC COMPLEXITY CLASSES
B.S HARMONIC NUMBERS
B.9 STIRLING' S FORMULA
B.IO NBONACCI NUMBERS
B.lI THE GOLDEN MEAN
B.12 THE EUCLIDEAN ALGORITHM
Appendix C Standard Container Classes
C.l 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 Briority_queue CLASS TEMPLATE
C.6 THE list CLASS TEMPLATE
C.7 THE map CLASS TEMPLATE
C.8 THE set CLASS TEMPLATE
Appendix D Generic Algerithms
Appendix E Example Classes
E.l 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 HasgTable CLASS TEMPLATE
E.IO A Line CLASS
E.ll 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 Pelynomial 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