C++ Object-oriented Data Structures

Description

This book provides a broad coverage of fundamental and advanced concepts of data structures and algorithms. Its aim is to provide readers with a modern synthesis of concepts with examples of applications that find practical use. Throughout, C++ is used to illustrate the construction and use of abstract data types and to demonstrate object-oriented implementations. As a result, it will make a superb textbook for students taking courses in data structures and software engineering as well as for software professionals. Readers are assumed to have a basic working familiaritiy with C and C++, but is otherwise self-contained. Read more... Abstract: This book provides a broad coverage of fundamental and advanced concepts of data structures and algorithms. Its aim is to provide readers with a modern synthesis of concepts with examples of applications that find practical use. Throughout, C++ is used to illustrate the construction and use of abstract data types and to demonstrate object-oriented implementations. As a result, it will make a superb textbook for students taking courses in data structures and software engineering as well as for software professionals. Readers are assumed to have a basic working familiaritiy with C and C++, but is otherwise self-contained Content: 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.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.