Table of Contents

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.

Promotional Information

Springer Book Archives