C++

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.