Beginning Data Structures in C++

Beginning Data Structures in C++ begins with a short analysis of functional abstraction which serves as a review of basic C++ programming operations especially array and structure processing actions. This includes Top-down design, stub testing and testing oracles. In fact, every example in Beginning Data Structures in C++ has an associated testing oracle to solidify how programs can be fully tested. User header files and multi-source files are used throughout the book. Next, Beginning Data Structures in C++ presents pointers and dynamic memory allocation in depth, since these operations form the foundation of data structure implementations. Recursive functions are also discussed, but adds a powerful sample program that illustrates a superb use for recursion. Beginning Data Structures in C++ presents the concepts of data abstraction along with with many illustrations of the different types. Key emphasis is on growable arrays or vectors, abstract data types (classes), linked lists, stacks and queues. The idea of a growable array is illustrated using structures as a "record" type data structure. Variant record implemented using unions are illustrated with solid examples. Two chapters of Beginning Data Structures in C++ present classes and their construction and use (abstract data types). However, the emphasis of class design is upon those elements that are required for data structure implementation and simple ADTs. No attempt has been made to turn this into an OOP primer. With an understanding of classes, the next series of chapters explore single and double linked lists, stacks and queues in great detail with many examples. A key principle is making reusable containers classes using only basic C++ OOP facilities. (Templates are considered an advanced data structures topic covered in CSIII.) Next, Beginning Data Structures in C++ discusses in depth binary file processing techniques including Inquiry and Update programs, relative record method, remainder method and ISAM methods. Hashing techniques are covered as they relate to direct file processing. Trees are covered including binary trees and binary searchable trees. The programming example illustrates how to construct a binary search tree for an ISAM data base. The last chapter of Beginning Data Structures in C++ discusses the broad topic of sorting algorithms including straight selection, bubble, Quicksort, Heapsort and Shellsort. A benchmark program is also presented along with methods for timing and random number generation.