C++, Softcover reprint of the original 1st ed. 1994 Object-Oriented Data Structures

This book provides a broad coverage of fundamental and advanced con­ cepts of data structures and algorithms. The material presented includes a treatment of elementary data structures such as arrays, lists, stacks, and trees, as well as newer structures that have emerged to support the process­ ing of multidimensional or spatial data files. These newer structures and algorithms have received increasing attention in recent years in conjunc­ tion with the rapid growth in computer-aided design, computer graphics, and related fields in which multidimensional data structures are of great interest. Our main objective is to mesh the underlying concepts with application examples that are of practical use and are timely in their implementations. To this end, we have used mainly the Abstract Data Structure (or Abstract Data Type (ADT)) approach to define structures for data and operations. Object-oriented programming (OOP) methodologies are employed to im­ plement these ADT concepts. In OOP, data and operations for an ADT are combined into a single entity (object). ADTs are used to specifiy the objects-arrays, stacks, queues, trees, and graphs. OOP allows the pro­ grammer to more closely mimic the real-world applications. This OOP is more structured and modular than previous attempts. OOP has become de facto state-of-the-art in the 1990s.

1 Concepts of Function-Oriented and Object-Oriented Data Structures.- 1.1 Data Types, Data Objects, and Related Terminologies.- 1.2 Definition of Abstract Data Structures.- 1.3 Object-Oriented Design and the ADT.- 1.4 Implementing an OOP in C++.- 1.5 Example Databases.- 1.6 Big Oh Notation.- 1.7 Exercises.- 2 Pointers, Structures, Classes, Functions, Overloaded Functions, and Overlodaded Operators in C++.- 2.1 C++ Pointers.- 2.2 Structures in C++.- 2.3 Unions.- 2.4 C++ Class.- 2.5 Functions in C++.- 2.6 Polymorphism, Virtual Functions, and Inheritance.- 2.7 Dangling Pointers and Memory Leaks.- 2.8 OOP Application: Complex Numbers.- 2.9 Exercises.- 3 Arrays and Strings.- 3.1 Array Objects.- 3.2 One-Dimensional Arrays.- 3.3 Two-Dimensional Arrays.- 3.4 Strings.- 3.5 OOP Application: An Object-Oriented Database.- 3.6 Exercises.- 4 Recursion.- 4.1 Concept of Recursion.- 4.2 Divide-and-Conquer and Recursion.- 4.3 Recursive and Nonrecursive Functions in C++.- 4.4 Recursion and Trace of C++ Stack.- 4.5 OOP Application: The Towers of Hanoi.- 4.6 OOP Application: Nonattacking N-Queens.- 4.7 Key Points for Using Recursion.- 4.8 Exercises.- 5 Lists.- 5.1 List Objects.- 5.2 Implementation Specific Linked List Classes.- 5.3 Array-Based Linked Lists.- 5.4 Pointer-Based Linked Lists.- 5.5 Circular List Objects.- 5.6 Performance Analyses of List Operations.- 5.7 OOP Application: Polynomial Objects in Single Variable.- 5.8 OOP Application: Memory Management.- 5.9 Summary.- 5.10 Exercises.- 6 Stacks and Queues.- 6.1 Stack Objects.- 6.2 Double Stack Objects.- 6.3 OOP Application: Reverse Polish Notation Using Stacks.- 6.4 Queue Objects.- 6.5 Implementation Specific Queue Classes.- 6.6 Circular Queue Objects.- 6.7 OOP Application: SCAN Disk Scheduling with Priority Queues.- 6.8 Exercises.-7 Sorting and Searching.- 7.1 Sorting Methods.- 7.2 Searching Methods.- 7.3 Exercises.- 8 Trees and Tries.- 8.1 Fundamental Definitions and Terminology.- 8.2 M-ary Trees.- 8.3 Traversing a Tree.- 8.4 Tree Objects.- 8.5 OOP Implementation of Binary Trees.- 8.6 General Trees.- 8.7 Search Trees.- 8.8 Data-Comparative M-ary Search Trees.- 8.9 Radix Search Trees.- 8.10 Comparative-Based B-Trees for External Searching and Sorting.- 8.11 Performance Analysis of Tree Operations.- 8.12 Exercises.- 9 Multidimensional Search Trees and Search Tries.- 9.1 Extending the Single-Key Model.- 9.2 Geometric Formulation of Associative Search.- 9.3 Types of Associative Search.- 9.4 Examples of Associative Search.- 9.5 Approaches to Associative Search.- 9.6 Multidimensional Comparative-Based Search Trees.- 9.7 Multidimensional Radix Search Tries.- 9.8 Multidimensional Structures for External Search.- 9.9 Summary: A Taxonomy of Trees and Tries.- 9.10 Exercises.- 10 Graphs and Digraphs.- 10.1 Fundamental Definitions and Terminologies.- 10.2 Graph Traversals.- 10.3 Graph Objects.- 10.4 Implementations of a Graph.- 10.5 Spanning Trees of a Graph.- 10.6 OOP Application: Determining the Shortest Path in a Weighted Digraph Using Dijkstra’s Algorithm.- 10.7 Exercises.- 11 An Object-Oriented Database with B-Trees.- 11.1 Specification of People Database System.- 11.2 OOP Implementation of Simple People Database Using B-Trees.- 11.3 Object-Oriented People Database Program.- 11.4 Limitations of Implementation.- 11.5 Exercises.- 12 Applications in Image Processing, Computer Graphics, and Computer-Aided Design.- 12.1 2-D Digital Image Compression with a Quadtrie Object.- 12.2 Computer-Aided VLSI Design Verification with a 4D-Tree Object.- 12.3 3-D Ray-Tracing Acceleration with an Octrie Object.- 12.43-D Hidden Surface Removal with a BSP Tree Object.- 12.5 Exercises.- A C++ Fundamentals.- A.l C++Key Words.- A.2 C++ Special Characters.- A.3 Allowed Overloaded Operators in C++.- A.4 C++ Built-in Data Types.- A.5 Statement Formats of Some C++ Keywords.- A.6 A Sample C++ Program.- A.7 C++ Preprocessor Directives.- A.8 Creating Executables for C++ Programs.- B Assorted Library Functions for Handling Strings.- C Example Databases.- C.l PEOPLE and GEOMETRY Databases.- C.l.l PEOPLE_ID.- C.l.2 PEOPLE_2D.- C.l.3 PEOPLE_3D.- C.1.4 GEOMETRY_2D.- C.l.5 GEOMETRY_3D.- References.