| |
| |
| Preface | |
| |
| |
| Introduction | |
| |
| |
| Abstract Data Types | |
| |
| |
| ADT Format | |
| |
| |
| C++ Classes and Abstract Types | |
| |
| |
| Encapsulation and Information Hiding | |
| |
| |
| Message Passing | |
| |
| |
| Objects in C++ Applications | |
| |
| |
| Application: The Circle Class | |
| |
| |
| Object Design | |
| |
| |
| Objects and Composition | |
| |
| |
| C++ Geometric Classes | |
| |
| |
| Objects and Inheritance | |
| |
| |
| Inheritance in Programming | |
| |
| |
| Ordered Lists and Inheritance | |
| |
| |
| Software Reusability | |
| |
| |
| SeqList and OrderedList Class Specifications | |
| |
| |
| Applications with Class Inheritance | |
| |
| |
| Object-Oriented Program Design | |
| |
| |
| Problem Analysis/Program Definition | |
| |
| |
| Design | |
| |
| |
| Coding | |
| |
| |
| Testing | |
| |
| |
| Program Design Illustration: A Dice Graph | |
| |
| |
| Program Testing and Maintenance | |
| |
| |
| Object Testing | |
| |
| |
| Control Module Testing | |
| |
| |
| Program Maintenance and Documentation | |
| |
| |
| The C++ Programming Language | |
| |
| |
| Abstract Base Classes and Polymorphism | |
| |
| |
| Polymorphism and Dynamic Binding | |
| |
| |
| Written Exercises | |
| |
| |
| Basic Data Types | |
| |
| |
| Integer Types | |
| |
| |
| Computer Storage of Integers | |
| |
| |
| Data in Memory | |
| |
| |
| C++ Representation of Integers | |
| |
| |
| Character Types | |
| |
| |
| ASCII Characters | |
| |
| |
| Real Data Types | |
| |
| |
| Real Number Representations | |
| |
| |
| Enumerated Types | |
| |
| |
| Implementing C++ Enumerated Types | |
| |
| |
| Pointers | |
| |
| |
| Pointer ADT | |
| |
| |
| Pointer Values | |
| |
| |
| The Array Type | |
| |
| |
| The Built-In C++ Array Type | |
| |
| |
| Storage of One-Dimensional Arrays | |
| |
| |
| Array Bounds | |
| |
| |
| Two-Dimensional Arrays | |
| |
| |
| Storage of Two-Dimensional Arrays | |
| |
| |
| String Literals and Variables | |
| |
| |
| C++ Strings | |
| |
| |
| Application: Reversing Names | |
| |
| |
| Records | |
| |
| |
| C++ Structures | |
| |
| |
| Files | |
| |
| |
| C++ Stream Hierarchy | |
| |
| |
| Array and Record Applications | |
| |
| |
| Sequential Search | |
| |
| |
| Exchange Sort | |
| |
| |
| Counting C++ Reserved Words | |
| |
| |
| Written Exercises | |
| |
| |
| Programming Exercises | |
| |
| |
| Abstract Data Types and Classes | |
| |
| |
| The User Type Class | |
| |
| |
| Class Declaration | |
| |
| |
| Constructor | |
| |
| |
| Object Declaration | |
| |
| |
| Class Implementation | |
| |
| |
| Implementing a Constructor | |
| |
| |
| Building Objects | |
| |
| |
| Sample Classes | |
| |
| |
| The Temperature Class | |
| |
| |
| The Random Number Class | |
| |
| |
| Objects and Information Passing | |
| |
| |
| An Object as a Return Value | |
| |
| |
| An Object as a Function Parameter | |
| |
| |
| Arrays of Objects | |
| |
| |
| The Default Constructor | |
| |
| |
| Multiple Constructors | |
| |
| |
| Case Study: Triangular Matrices | |
| |
| |
| Upper Triangular Matrix Properties | |
| |
| |
| Written Exercises | |
| |
| |
| Programming Exercises | |
| |
| |
| Collection Classes | |
| |
| |
| Describing Linear Collections | |
| |
| |
| Direct Access Collections | |
| |
| |
| Sequential Access Collections | |
| |
| |
| Generalized Indexing | |
| |
| |
| Describing Nonlinear Collections | |
| |
| |
| Group Collections | |
| |
| |
| Analysis of Algorithms | |
| |
| |
| Performance Criteria | |
| |
| |
| Common Orders of Magnitude | |
| |
| |
| The Sequential and Binary Search | |
| |
| |
| Binary Search | |
| |
| |
| The Basic Sequential List Class | |
| |
| |
| List Modification Methods | |
| |
| |
| Written Exercises | |
| |
| |
| Programming Exercises | |
| |
| |
| Stacks and Queues | |
| |
| |
| Stacks | |
| |
| |
| The Stack Class | |
| |
| |
| Expression Evaluation | |
| |
| |
| Postfix Evaluation | |
| |
| |
| Application: A Postfix Calculator | |
| |
| |
| Queues | |
| |
| |
| The Queue Class | |
| |
| |
| Priority Queues | |
| |
| |
| A Priority Queue Class | |
| |
| |
| Case Study: Event-Driven Simulation | |
| |
| |
| Written Exercises | |
| |
| |
| Programming Exercises | |
| |
| |
| Abstract Operators | |
| |
| |
| Describing Operator Overloading | |
| |
| |
| Client-Defined External Functions | |
| |
| |
| Class Members | |
| |
| |
| Friend Functions | |
| |
| |
| Rational Number System | |
| |
| |
| Representing Rational Numbers | |
| |
| |
| Rational Number Arithmetic | |
| |
| |
| Rational Number Conversion | |
| |
| |
| The Rational Class | |
| |
| |
| Rational Operators as Member Functions | |
| |
| |
| Implementing the Rational Operators | |
| |
| |
| The Rational Stream Operators as Friends | |
| |
| |
| Implementing Rational Stream Operators | |
| |
| |
| Converting Rational Numbers | |
| |
| |
| Conversion to Object Type | |
| |
| |
| Conversion from Object Type | |
| |
| |
| Using Rational Numbers | |
| |
| |
| Written Exercises | |
| |
| |
| Programming Exercises | |
| |
| |
| Generic Data Types | |
| |
| |
| Template Functions | |
| |
| |
| Template-Based Sort | |
| |
| |
| Template Classes | |
| |
| |
| Defining a Template Class | |
| |
| |
| Declaring Template Class Objects | |
| |
| |
| Defining Template Class Methods | |
| |
| |
| Template List Classes | |
| |
| |
| Infix Expression Evaluation | |
| |
| |
| Written Exercises | |
| |
| |
| Programming Exercises | |
| |
| |
| Classes and Dynamic Memory | |
| |
| |
| Pointers and Dynamic Data Structures | |
| |
| |
| The Memory Allocation Operator New | |
| |
| |
| Dynamic Array Allocation | |
| |
| |
| The Memory Deallocation Operator Delete | |
| |
| |
| Dynamically Allocated Objects | |
| |
| |
| Deallocating Object Data: The Destructor | |
| |
| |
| Assignment and Initialization | |
| |
| |
| Assignment Issues | |
| |
| |
| Overloading the Assignment Operator | |
| |
| |
| The This Pointer | |
| |
| |
| Initialization Issues | |
| |
| |
| Creating a Copy Constructor | |
| |
| |
| Safe Arrays | |
| |
| |
| The Array Class | |
| |
| |
| Memory Allocation for the Array Class | |
| |
| |
| Array Bounds Checking and the Overloaded [] Operator | |
| |
| |
| Converting an Object to a Pointer | |
| |
| |
| Using the Array Class | |
| |
| |
| A String Class | |
| |
| |
| String Class Implementation | |
| |
| |
| Pattern Matching | |
| |
| |
| The Find Process | |
| |
| |
| Pattern Matching Algorithm | |
| |
| |
| Analysis of the Pattern Matching Algorithm | |
| |
| |
| Integral Sets | |
| |
| |
| Sets of Integral Types | |
| |
| |
| C++ Bit Handling Operators | |
| |
| |
| Representing Set Elements | |
| |
| |
| The Sieve of Eratosthenes | |
| |
| |
| Set Class Implementation | |
| |
| |
| Written Exercises | |
| |
| |
| Programming Exercises | |
| |
| |
| Linked Lists | |
| |
| |
| Describing a Linked List | |
| |
| |
| Chapter Overview | |
| |
| |
| The Node Class | |
| |
| |
| Declaring a Node Type | |
| |
| |
| Implementing the Node Class | |
| |
| |
| Building Linked Lists | |
| |
| |
| Creating a Node | |
| |
| |
| Inserting a Node: InsertFront | |
| |
| |
| Traversing a Linked List | |
| |
| |
| Inserting a Node: InsertRear | |
| |
| |
| Application: Student Graduation List | |
| |
| |
| Creating an Ordered List | |
| |
| |
| Application: Sorting with Linked Lists | |
| |
| |
| Designing a Linked List Class | |
| |
| |
| Linked List Data Members | |
| |
| |
| Linked List Operations | |
| |
| |
| The LinkedList Class | |
| |
| |
| Implementing the LinkedList Class | |
| |
| |
| Implementing Collections with Linked Lists | |
| |
| |
| Linked Queues | |
| |
| |
| Implementing Queue Methods | |
| |
| |
| Linked SeqList Class | |
| |
| |
| Implementing SeqList Data Access Methods | |
| |
| |
| Application: Comparing SeqList Implementations | |
| |
| |
| Case Study: A Print Spooler | |
| |
| |
| Implementing the Spooler Update Method | |
| |
| |
| Spooler Evaluation Methods | |
| |
| |
| Circular Lists | |
| |
| |
| Circular Node Class Implementation | |
| |
| |
| Application: Solving the Josephus Problem | |
| |
| |
| Doubly Linked Lists | |
| |
| |
| Application: Doubly Linked List Sort | |
| |
| |
| DNode Class Implementation | |
| |
| |
| Case Study: Window Management | |
| |
| |
| The Window List | |
| |
| |
| WindowList Class Implementation | |
| |
| |
| Written Exercises | |
| |
| |
| Programming Exercises | |
| |
| |
| Recursion | |
| |
| |
| The Concept of Recursion | |
| |
| |
| Recursive Definitions | |
| |
| |
| Recursive Problems | |
| |
| |
| Designing Recursive Functions | |
| |
| |
| Recursive Code and the Runtime Stack | |
| |
| |
| The Runtime Stack | |
| |
| |
| Problem-Solving with Recursion | |
| |
| |
| Binary Search | |
| |
| |
| Combinatorics: The Committee Problem | |
| |
| |
| Combinatorics: Permutations | |
| |
| |
| Maze Handling | |
| |
| |
| Maze Class Implementation | |
| |
| |
| Evaluating Recursion | |
| |
| |
| Written Exercises | |
| |
| |
| Programming Exercises | |
| |
| |
| Trees | |
| |
| |
| Tree Terminology | |
| |
| |
| Binary Trees | |
| |
| |
| Binary Tree Structure | |
| |
| |
| Designing a TreeNode Class | |
| |
| |
| Building a Binary Tree | |
| |
| |
| Designing TreeNode Functions | |
| |
| |
| Recursive Tree Traversals | |
| |
| |
| Using Tree Scan Algorithms | |
| |
| |
| Application: Visiting Tree Nodes | |
| |
| |
| Application: Tree Print | |
| |
| |
| Application: Copying and Deleting Trees | |
| |
| |
| Application: Upright Tree Printing | |
| |
| |
| Binary Search Trees | |
| |
| |
| The Key in a Binary Search Tree Node | |
| |
| |
| Operations on a Binary Search Tree | |
| |
| |
| Declaring a Binary Search Tree ADT | |
| |
| |
| Using Binary Search Trees | |
| |
| |
| Duplicate Nodes | |
| |
| |
| The BinSTree Implementation | |
| |
| |
| List Operations | |
| |
| |
| Case Study: Concordance | |
| |
| |
| Written Exercises | |
| |
| |
| Programming Exercises | |
| |
| |
| Inheritance and Abstract Classes | |
| |
| |
| A View of Inheritance | |
| |
| |
| Class Inheritance Terminology | |
| |
| |
| Inheritance in C++ | |
| |
| |
| Constructors and Derived Classes | |
| |
| |
| What Cannot Be Inherited | |
| |
| |
| Polymorphism and Virtual Functions | |
| |
| |
| Demonstrating Polymorphism | |
| |
| |
| Application: Geometric Figures and Virtual Methods | |
| |
| |
| Virtual Methods and the Destructor | |
| |
| |
| Abstract Base Classes | |
| |
| |
| Abstract Base Class--List | |
| |
| |
| Deriving SeqList from Abstract Base Class List | |
| |
| |
| Iterators | |
| |
| |
| The Iterator Abstract Base Class | |
| |
| |
| Deriving List Iterators | |
| |
| |
| Building the SeqList Iterator | |
| |
| |
| Array Iterator | |
| |
| |
| Application: Merging Sorted Runs | |
| |
| |
| ArrayIterator Implementation | |
| |
| |
| Ordered Lists | |
| |
| |
| OrderedList Class Implementation | |
| |
| |
| Heterogeneous Lists | |
| |
| |
| Heterogeneous Arrays | |
| |
| |
| Heterogeneous Linked Lists | |
| |
| |
| Written Exercises | |
| |
| |
| Programming Exercises | |
| |
| |
| Advanced Nonlinear Structures | |
| |
| |
| Array-Based Binary Trees | |
| |
| |
| Application: The Tournament Sort | |
| |
| |
| Heaps | |
| |
| |
| The Heap as a List | |
| |
| |
| The Heap Class | |
| |
| |
| Implementing the Heap Class | |
| |
| |
| Application: Heap Sort | |
| |
| |
| Priority Queues | |
| |
| |
| Application: Long Runs | |
| |
| |
| AVL Trees | |
| |
| |
| AVL Tree Nodes | |
| |
| |
| The AVL Tree Class | |
| |
| |
| Memory Allocation for the AVLTree | |
| |
| |
| Evaluating AVL Trees | |
| |
| |
| Tree Iterators | |
| |
| |
| The Inorder Iterator | |
| |
| |
| InorderIterator Class Implementation | |
| |
| |
| Application: TreeSort | |
| |
| |
| Graphs | |
| |
| |
| Connected Components | |
| |
| |
| The Graph Class | |
| |
| |
| Declaring a Graph ADT | |
| |
| |
| Graph Class Implementation | |
| |
| |
| Graph Traversals | |
| |
| |
| Applications | |
| |
| |
| Reachability and Warshall's Algorithm | |
| |
| |
| Written Exercises | |
| |
| |
| Programming Exercises | |
| |
| |
| Organizing Collections | |
| |
| |
| Basic Array Sorting Algorithms | |
| |
| |
| The Selection Sort | |
| |
| |
| The Bubble Sort | |
| |
| |
| The Insertion Sort | |
| |
| |
| QuickSort | |
| |
| |
| QuickSort Description | |
| |
| |
| QuickSort Algorithm | |
| |
| |
| Comparison of Array Sort Algorithms | |
| |
| |
| Hashing | |
| |
| |
| Keys and a Hash Function | |
| |
| |
| Hashing Functions | |
| |
| |
| Other Hash Methods | |
| |
| |
| Collision Resolution | |
| |
| |
| Hash Table Class | |
| |
| |
| Application: String Frequency | |
| |
| |
| HashTable Class Implementation | |
| |
| |
| HashTableIterator Class Implementation | |
| |
| |
| The Performance of Searching Methods | |
| |
| |
| Binary Files and External Data Operations | |
| |
| |
| Binary Files | |
| |
| |
| The BinFile Class | |
| |
| |
| External File Searching | |
| |
| |
| External File Sort | |
| |
| |
| Long Run MergeSort | |
| |
| |
| Dictionaries | |
| |
| |
| Written Exercises | |
| |
| |
| Programming Exercises | |
| |
| |
| Answers to Selected Exercises | |
| |
| |
| Bibliography | |
| |
| |
| Index | |