C++: 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.3.1 Function-Oriented Data Structures.- 1.3.2 Object-Oriented Data Structures.- 1.3.3 A Unified Approach.- 1.3.4 Steps for Deriving an Object-Oriented Design.- 1.4 Implementing an OOP in C++.- 1.4.1 A Short Preview of Object-Oriented Programming..- 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.1.1 C++ Pointer Arithmetic and Operations.- 2.1.2 Call-by-Reference Using Pointers as Function Arguments.- 2.1.3 Pointers as Return Values of Functions.- 2.2 Structures in C++.- 2.2.1 Defining a Structure.- 2.2.2 Pointers to Structures.- 2.2.3 Accessing Structures.- 2.2.4 Initializing Structures.- 2.2.5 Structure as a Function Argument and Return Value.- 2.2.6 Pointer to a Structure as a Function Argument.- 2.2.7 Arrays of Structures.- 2.3 Unions.- 2.4 C++ Class.- 2.4.1 Defining a Member Function of a Class Outside Its Scope.- 2.4.2 Defining an Object of a Class.- 2.4.3 Accessing a Member of a Class.- 2.4.4 Friend of a Class and Inheritance.- 2.4.5 Derived Class and Multiple Inheritance.- 2.4.6 Nested Class.- 2.5 Functions in C++.- 2.5.1 Special Functions: Constructors.- 2.5.2 Special Functions: Destructors.- 2.6 Polymorphism, Virtual Functions, and Inheritance.- 2.6.1 Friend Functions and Inheritance.- 2.6.2 Overloading and Polymorphism.- 2.6.3 Overloaded Functions.- 2.6.4 Overloaded Operators.- 2.7 Dangling Pointers and Memory Leaks.- 2.7.1 Dangling Pointers.- 2.7.2 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.2.1 Declaration of Arrays in C++.- 3.2.2 Storing and Retrieving an Element in an Array.- 3.2.3 Initializing an Array.- 3.2.4 One-Dimensional Array Address Translation.- 3.2.5 Array as Function Arguments.- 3.2.6 One-Dimensional Array Object.- 3.2.7 OOP for One-Dimensional Array.- 3.3 Two-Dimensional Arrays.- 3.3.1 C++ Declaration of Two-Dimensional Arrays.- 3.3.2 Storing and Retrieving an Element in a Two-dimensional Array.- 3.3.3 Initializing a Two-Dimensional Array.- 3.3.4 Translating Address of Two-Dimensional Array Elements.- 3.3.5 Two-Dimensional Arrays as Function Arguments.- 3.3.6 Two-Dimensional Array Object.- 3.3.7 OOP Two-Dimensional Array.- 3.4 Strings.- 3.4.1 Implementing Strings Using Arrays and Pointers.- 3.4.2 Array of Array-Based Strings.- 3.4.3 Array of Pointers to Strings.- 3.4.4 String Object and Its OOP Implementation.- 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.3.1 OOP for Array-Based Linked Lists with Implicit Links.- 5.3.2 Adding an Element After a Given Element.- 5.3.3 Deleting an Element from an Array List.- 5.4 Pointer-Based Linked Lists.- 5.4.1 Non-OOP Implementation of the Singly Linked List.- 5.4.2 OOP Implementation of the Singly Linked List.- 5.4.3 Building a Singly Linked List.- 5.4.4 Inserting an Element in a Singly Linked List.- 5.4.5 Deleting an Element in a Singly Linked List.- 5.4.6 Methods of the Singly_Linked_List Class.- 5.4.7 OOP Implementation of the Doubly Linked List.- 5.4.8 Adding an Element in a Doubly Linked List.- 5.4.9 Deleting an Element in a Doubly Linked List.- 5.4.10 Methods of the Doubly_Linked_List Class.- 5.5 Circular List Objects.- 5.5.1 OOP Implementation of Singly Linked Circular Lists.- 5.5.2 Methods of the Circ_Linked_List Class.- 5.5.3 Doubly Linked Circular List and Its OOP Implementation.- 5.6 Performance Analyses of List Operations.- 5.7 OOP Application: Polynomial Objects in Single Variable.- 5.7.1 Concept of a Polynomial in Single Variable.- 5.7.2 Polynomial Objects.- 5.7.3 Object-Oriented Design and Implementation for Polynomials.- 5.8 OOP Application: Memory Management.- 5.8.1 The Free List.- 5.8.2 Free List Management by Counted Pointers.- 5.8.3 Free List Management by Garbage Collection.- 5.9 Summary.- 5.10 Exercises.- 6 Stacks and Queues.- 6.1 Stack Objects.- 6.1.1 OOP Array Implementation of a Stack Object.- 6.1.2 OOP Implementation of a Stack Using Linked Lists.- 6.1.3 Performance Analyses of Stack Operations.- 6.2 Double Stack Objects.- 6.3 OOP Application: Reverse Polish Notation Using Stacks.- 6.3.1 Postfix Evaluation.- 6.3.2 Infix to RPN Translation.- 6.4 Queue Objects.- 6.5 Implementation Specific Queue Classes.- 6.5.1 OOP Implementation of a Queue Using Array.- 6.5.2 OOP Implementation of a Queue Using Linked List.- 6.6 Circular Queue Objects.- 6.6.1 OOP Implementation of a Circular Queue Using Array.- 6.6.2 OOP Implementation of a Circular Queue Using a Linked List.- 6.6.3 Performance Analyses of Queue Operations.- 6.7 OOP Application: SCAN Disk Scheduling with Priority Queues.- 6.8 Exercises.- 7 Sorting and Searching.- 7.1 Sorting Methods.- 7.1.1 Insertion Sort for an Array List.- 7.1.2 Insertion Sort for a Linked List.- 7.1.3 Selection Sort.- 7.1.4 Bubble Sort.- 7.1.5 Quicksort.- 7.1.6 Merge Sort.- 7.1.7 Binary Tree Sort.- 7.1.8 Heap Sort.- 7.1.9 Straight Radix Sort.- 7.1.10 Radix Exchange Sort.- 7.1.11 Shell Sort.- 7.1.12 Performance Analyses of Sorting Methods.- 7.2 Searching Methods.- 7.2.1 Linear Search of an Unsorted Array.- 7.2.2 Linear Search of an Unsorted Linked List.- 7.2.3 Linear Search of a Sorted Array.- 7.2.4 Linear Search of a Sorted List.- 7.2.5 Binary Search of a Sorted Array.- 7.2.6 Interpolation Search of a Sorted Array.- 7.2.7 Fibonacci Search of a Sorted Array.- 7.2.8 Searching a Binary Search Tree.- 7.2.9 Hash Strategy for Hash Search Method.- 7.2.10 Performance Analyses of Searching Algorithms.- 7.3 Exercises.- 8 Trees and Tries.- 8.1 Fundamental Definitions and Terminology.- 8.2 M-ary Trees.- 8.3 Traversing a Tree.- 8.3.1 Traversals of Binary Trees.- 8.4 Tree Objects.- 8.5 OOP Implementation of Binary Trees.- 8.5.1 OOP Implementation of a Binary Tree Using Arrays.- 8.5.2 OOP Implementation of a Binary Tree Using Pointers.- 8.5.3 Methods of the Binary_Tree Class.- 8.6 General Trees.- 8.6.1 Strategies for Representing General Trees.- 8.6.2 General Tree: Binary Tree Implementation.- 8.6.3 General Tree Traversal.- 8.6.4 OOP Implementation of a General Tree.- 8.6.5 Methods of the General_Tree Class.- 8.7 Search Trees.- 8.7.1 Data-Comparative Search Trees Versus Radix Search Trees.- 8.8 Data-Comparative M-ary Search Trees.- 8.8.1 Inserting a Node and Building a Binary Search Tree.- 8.8.2 Deleting a Node from a BST.- 8.8.3 OOP Implementation of a Binary Search Tree Using Pointers.- 8.8.4 Methods of the Binary_Search_Tree Class.- 8.8.5 BST and Quicksort Relationship.- 8.8.6 Balance Characteristics of Comparative-Based Search Tree.- 8.8.7 AVL Trees.- 8.8.8 AVL Tree Objects.- 8.8.9 OOP Implementation of an AVL Tree Using Pointers.- 8.8.10 Insertion of a Node in an AVL Tree.- 8.8.11 Inserting a New Node into an AVL Tree.- 8.8.12 Inserting a Node and Building an AVL Tree.- 8.8.13 Creating a Node for an AVL Tree.- 8.8.14 Deleting a Node from an AVL Tree.- 8.8.15 Regaining Balance with Rotation Techniques.- 8.9 Radix Search Trees.- 8.9.1 Discrete Versus Non-Discrete Keys.- 8.9.2 Digital Search Trees.- 8.9.3 OOP Implementation of a Binary Digital Search Tree.- 8.9.4 Radix Search Tries.- 8.9.5 OOP Implementation of an M-ary Radix Search Trie.- 8.9.6 Balance Characteristics of Radix Search Trees.- 8.9.7 Hybrid Radix Search Tries.- 8.9.8 Radix Search Tries and Radix Exchange Sorting.- 8.9.9 OOP Application: Word Dictionaries Using Tries.- 8.9.10 Patricia Trees and Tries.- 8.10 Comparative-Based B-Trees for External Searching and Sorting.- 8.10.1 B-Tree Objects.- 8.10.2 Inserting a Key and Building a B-Tree.- 8.10.3 Deleting a Key from a B-Tree.- 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.2.1 Records as Points in Key-Space.- 9.2.2 Geometric Objects in Euclidean Space.- 9.3 Types of Associative Search.- 9.4 Examples of Associative Search.- 9.5 Approaches to Associative Search.- 9.5.1 ADT Inverted List.- 9.6 Multidimensional Comparative-Based Search Trees.- 9.6.1 K-Tree Objects.- 9.6.2 OOP Implementation of Quadtree.- 9.6.3 K-Tree Balance and Node Deletion.- 9.6.4 Kd-Tree Objects.- 9.6.5 OOP Implementation of 3d-Tree.- 9.6.6 Kd-Tree Balance and Node Deletion.- 9.7 Multidimensional Radix Search Tries.- 9.7.1 K-Trie Objects.- 9.7.2 Kd-Trie Objects.- 9.7.3 Implementation of K-Trie and Kd-Trie.- 9.7.4 Compact Trie Representations.- 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.2.1 Depth-First Traversals.- 10.2.2 Breadth-First Traversals.- 10.3 Graph Objects.- 10.4 Implementations of a Graph.- 10.4.1 Representing a Weighted Undirected or Directed Graph Using Adjacency Matrix.- 10.4.2 OOP Implementation of a Graph Using Adjacency Matrix.- 10.4.3 Methods of Weighted_DiGraph Class.- 10.4.4 OOP Implementation of a Graph Using Linked Adjacency Lists.- 10.4.5 Methods of the Wt_DiGraph Class.- 10.5 Spanning Trees of a Graph.- 10.5.1 Constructing a Spanning Tree Using Depth-First Traversals.- 10.5.2 Constructing a Spanning Tree Using Breadth-First Traversals.- 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.2.1 Methods of the B_Tree Class.- 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.4 3-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.