| |
| |
| |
| Data Abstraction: The Walls | |
| |
| |
| |
| Object-Oriented Concepts | |
| |
| |
| |
| Object-Oriented Analysis and Design | |
| |
| |
| |
| Aspects of an Object-Oriented Solution | |
| |
| |
| |
| Achieving a Better Solution | |
| |
| |
| |
| Cohesion | |
| |
| |
| |
| Coupling | |
| |
| |
| |
| Specifications | |
| |
| |
| |
| Operation Contracts | |
| |
| |
| |
| Unusual Conditions | |
| |
| |
| |
| Abstraction | |
| |
| |
| |
| Information Hiding | |
| |
| |
| |
| Minimal and Complete Interfaces | |
| |
| |
| |
| Abstract Data Types | |
| |
| |
| |
| Designing an ADT | |
| |
| |
| |
| ADTs that suggest other ADTs | |
| |
| |
| |
| The ADT Bag | |
| |
| |
| |
| Identifying Behaviors | |
| |
| |
| |
| Specifying Data and Operations | |
| |
| |
| |
| An Interface Template for the ADT | |
| |
| |
| |
| Using the ADT Bag | |
| |
| |
| C++ Interlude 1 C++ Classes | |
| |
| |
| |
| A Problem to Solve | |
| |
| |
| |
| Private Data Fields | |
| |
| |
| |
| Constructors and Destructor | |
| |
| |
| |
| Methods | |
| |
| |
| |
| Preventing Compiler Errors | |
| |
| |
| |
| Implementing a Solution | |
| |
| |
| |
| Templates | |
| |
| |
| |
| Inheritance | |
| |
| |
| |
| Base Classes and Derived Classes | |
| |
| |
| |
| Overriding Base Class Methods | |
| |
| |
| |
| Virtual Methods and Abstract Classes | |
| |
| |
| |
| Virtual Methods | |
| |
| |
| |
| Abstract Classes | |
| |
| |
| |
| Recursion: The Mirrors | |
| |
| |
| |
| Recursive Solutions | |
| |
| |
| |
| Recursion That Returns a Value | |
| |
| |
| |
| A Recursive Valued Function: The Factorial of n | |
| |
| |
| |
| The Box Trace | |
| |
| |
| |
| Recursion That Performs an Action | |
| |
| |
| |
| A Recursive void Function: Writing a String Backward | |
| |
| |
| |
| Recursion with Arrays | |
| |
| |
| |
| Writing an Array's Entries in Backward Order | |
| |
| |
| |
| The Binary Search | |
| |
| |
| |
| Finding the Largest Value in an Array | |
| |
| |
| |
| Finding the kth Smallest Value of an Array | |
| |
| |
| |
| Organizing Data | |
| |
| |
| |
| The Towers of Hanoi | |
| |
| |
| |
| More Examples | |
| |
| |
| |
| The Fibonacci Sequence (Multiplying Rabbits) | |
| |
| |
| |
| Organizing a Parade | |
| |
| |
| |
| Choosing k Out of n Things | |
| |
| |
| |
| Recursion and Efficiency | |
| |
| |
| |
| Array-Based Implementations | |
| |
| |
| |
| The Approach | |
| |
| |
| |
| Core Methods | |
| |
| |
| |
| Using Fixed-Size Arrays | |
| |
| |
| |
| An Array-Based Implementation of the ADT Bag | |
| |
| |
| |
| The Header File | |
| |
| |
| |
| Defining the Core Methods | |
| |
| |
| |
| Testing the Core Methods | |
| |
| |
| |
| Implementing More Methods | |
| |
| |
| |
| Methods That Remove Entries | |
| |
| |
| |
| Testing | |
| |
| |
| |
| Using Recursion in the Implementation | |
| |
| |
| C++ Interlude 2 Pointers, Polymorphism, and Memory Allocation | |
| |
| |
| |
| Memory Allocation for Variables and Early Binding of Methods | |
| |
| |
| |
| A Problem to Solve | |
| |
| |
| |
| Pointers and the Program Free Store | |
| |
| |
| |
| Deallocating Memory | |
| |
| |
| |
| Avoiding Memory Leaks | |
| |
| |
| |
| Avoiding Dangling Pointers | |
| |
| |
| |
| Virtual Methods and Polymorphism | |
| |
| |
| |
| Dynamic Allocation of Arrays | |
| |
| |
| |
| A Resizable Array-Based Bag | |
| |
| |
| |
| Link-Based Implementations | |
| |
| |
| |
| Preliminaries | |
| |
| |
| |
| The Class Node | |
| |
| |
| |
| A Link-Based Implementation of the ADT Bag | |
| |
| |
| |
| The Header File | |
| |
| |
| |
| Defining the Core Methods | |
| |
| |
| |
| Implementing More Methods | |
| |
| |
| |
| Using Recursion in Link-Based Implementations | |
| |
| |
| |
| Recursive Definitions of Methods in LinkedBag | |
| |
| |
| |
| Comparing Array-Based and Link-Based Implementations | |
| |
| |
| |
| Recursion as a Problem-Solving Technique | |
| |
| |
| |
| Defining Languages | |
| |
| |
| |
| The Basics of Grammars | |
| |
| |
| |
| Two Simple Languages | |
| |
| |
| |
| Algebraic Expressions | |
| |
| |
| |
| Kinds of Algebraic Expressions | |
| |
| |
| |
| Prefix Expressions | |
| |
| |
| |
| Postfix Expressions | |
| |
| |
| |
| Fully Parenthesized Expressions | |
| |
| |
| |
| Backtracking | |
| |
| |
| |
| Searching for an Airline Route | |
| |
| |
| |
| The Eight Queens Problem | |
| |
| |
| |
| The Relationship Between Recursion and Mathematical Induction | |
| |
| |
| |
| The Correctness of the Recursive Factorial Function | |
| |
| |
| |
| The Cost of Towers of Hanoi | |
| |
| |
| |
| Stacks | |
| |
| |
| |
| The Abstract Data Type Stack | |
| |
| |
| |
| Developing an ADT During the Design of a Solution | |
| |
| |
| |
| Specifications for the ADT Stack | |
| |
| |
| |
| Simple Uses of a Stack | |
| |
| |
| |
| Checking for Balanced Braces | |
| |
| |
| |
| Recognizing Strings in a Language | |
| |
| |
| |
| Using Stacks with Algebraic Expressions | |
| |
| |
| |
| Evaluating Postfix Expressions | |
| |
| |
| |
| Converting Infix Expressions to Equivalent Postfix Expressions | |
| |
| |
| |
| Using a Stack to Search a Flight Map | |
| |
| |
| |
| The Relationship Between Stacks and Recursion | |
| |
| |
| C++ Interlude 3 Exceptions | |
| |
| |
| |
| Background | |
| |
| |
| |
| A Problem to Solve | |
| |
| |
| |
| Assertions | |
| |
| |
| |
| Throwing Exceptions | |
| |
| |
| |
| Handling Exceptions | |
| |
| |
| |
| Multiple catch Blocks | |
| |
| |
| |
| Uncaught Exceptions | |
| |
| |
| |
| Programmer-Defined Exception Classes | |
| |
| |
| |
| Stack Implementations | |
| |
| |
| |
| An Array-Based Implementation | |
| |
| |
| |
| A Linked Implementation | |
| |
| |
| |
| Comparing Implementations | |
| |
| |
| |
| Lists | |
| |
| |
| |
| Specifying the Abstract Data Type List | |
| |
| |
| |
| Using the List Operations | |
| |
| |
| |
| Specifications of the ADT List Using Exceptions | |
| |
| |
| |
| List Implementations | |
| |
| |
| |
| An Array-Based Implementation of the ADT List | |
| |
| |
| |
| The Header File | |
| |
| |
| |
| The Implementation File | |
| |
| |
| |
| A Linked Implementation of the ADT List | |
| |
| |
| |
| The Header File | |
| |
| |
| |
| The Implementation File | |
| |
| |
| |
| Using Recursion To Process a Linked Chain | |
| |
| |
| |
| Comparing Implementations | |
| |
| |
| |
| Algorithm Efficiency | |
| |
| |
| |
| What Is a Good Solution? | |
| |
| |
| |
| Measuring the Efficiency of Algorithms | |
| |
| |
| |
| The Execution Time of Algorithms | |
| |
| |
| |
| Algorithm Growth Rates | |
| |
| |
| |
| Order-of-Magnitude Analysis and Big O Notation | |
| |
| |
| |
| Keeping Your Perspective | |
| |
| |
| |
| The Efficiency of Searching Algorithms | |
| |
| |
| |
| Sorting Algorithms and Their Efficiency | |
| |
| |
| |
| Basic Sorting Algorithms | |
| |
| |
| |
| Selection Sort | |
| |
| |
| |
| Bubble Sort | |
| |
| |
| |
| Insertion Sort | |
| |
| |
| |
| Faster Sorting Algorithms | |
| |
| |
| |
| Merge Sort | |
| |
| |
| |
| Quick Sort | |
| |
| |
| |
| Radix Sort | |
| |
| |
| |
| A Comparison of Sorting Algorithms | |
| |
| |
| |
| The Standard Template Library: Sorting Algorithms | |
| |
| |
| C++ Interlude 4 Class Relationships and Reuse | |
| |
| |
| |
| Inheritance Revisited | |
| |
| |
| |
| Public, Private, and Protected Sections of a Class | |
| |
| |
| |
| Public, Private, and Protected Inheritance | |
| |
| |
| |
| Is-a and As-a Relationships | |
| |
| |
| |
| Containment: Has-a Relationships | |
| |
| |
| |
| Abstract Base Classes Revisited | |
| |
| |
| |
| Sorted Lists and Their Implementations | |
| |
| |
| |
| Specifying the ADT Sorted List | |
| |
| |
| |
| An Interface Template for the ADT Sorted List | |
| |
| |
| |
| Using the Sorted List Operations | |
| |
| |
| |
| A Link-Based Implementation | |
| |
| |
| |
| The Header File | |
| |
| |
| |
| The Implementation File | |
| |
| |
| |
| The Efficiency of the Link-Based Implementation | |
| |
| |
| |
| Implementations That Use the ADT List | |
| |
| |
| |
| Composition | |
| |
| |
| |
| Public Inheritance | |
| |
| |
| |
| Private Inheritance | |
| |
| |
| |
| Queues and Priority Queues | |
| |
| |
| |
| The ADT Queue | |
| |
| |
| |
| Simple Applications of a Queue | |
| |
| |
| |
| Reading a String of Characters | |
| |
| |
| |
| Recognizing Palindromes | |
| |
| |
| |
| The ADT Priority Queue | |
| |
| |
| |
| Tracking Your Assignments | |
| |
| |
| |
| Application: Simulation | |
| |
| |
| |
| Position-Oriented and Value-Oriented ADTs | |
| |
| |
| |
| Queue Implementations | |
| |
| |
| |
| Implementations of the ADT Queue | |
| |
| |
| |
| An Implementation That Uses the ADT List | |
| |
| |
| |
| A Link-Based Implementation | |
| |
| |
| |
| An Array-Based Implementation | |
| |
| |
| |
| Comparing Implementations | |
| |
| |
| |
| An Implementation of the ADT Priority Queue | |
| |
| |
| C++ Interlude 5 Overloaded Operators and Friend Classes | |
| |
| |
| Overloading Operators | |
| |
| |
| Overloading the Stream Operators << and >> | |
| |
| |
| Friend Classes and Data Member Access | |
| |
| |
| |
| Trees | |
| |
| |
| |
| Terminology | |
| |
| |
| |
| Kinds of Trees | |
| |
| |
| |
| The Height of Trees | |
| |
| |
| |
| Full, Complete, and Balanced Binary Trees | |
| |
| |
| |
| The Maximum and Minimum Heights of a Binary Tree | |
| |
| |
| |
| The ADT Binary Tree | |
| |
| |
| |
| Binary Tree Operations | |
| |
| |
| |
| An Interface Template for the ADT Binary Tree | |
| |
| |
| |
| Traversals of a Binary Tree | |
| |
| |
| |
| The ADT Binary Search Tree | |
| |
| |
| |
| Binary Search Tree Operations | |
| |
| |
| |
| An Interface Template for the ADT Binary Tree | |
| |
| |
| |
| Searching a Binary Search Tree | |
| |
| |
| |
| Creating a Binary Search Tree | |
| |
| |
| |
| Traversals of a Binary Search Tree | |
| |
| |
| |
| Tree Implementations | |
| |
| |
| |
| Implementations of the ADT Binary Tree | |
| |
| |
| |
| A Link-Based Implementation | |
| |
| |
| |
| An Array-Based Implementation | |
| |
| |
| |
| Efficiency of Implementations | |
| |
| |
| |
| An Implementation of the ADT Binary Search Tree | |
| |
| |
| |
| Algorithms for Insertion, Deletion, and Traversal | |
| |
| |
| |
| A Link-Based Implementation | |
| |
| |
| |
| Efficiency of the Implementation | |
| |
| |
| |
| Saving a Binary Search Tree in a File | |
| |
| |
| C++ Interlude 6 Iterators | |
| |
| |
| Iterator Introduction | |
| |
| |
| A List Iterator and Its Use | |
| |
| |
| A BST Tree Iterator and Its Use | |
| |
| |
| |
| Heaps | |
| |
| |
| An Array-Based Implementation | |
| |
| |
| A Heap as a Priority QueueThe Heap Sort | |
| |
| |
| |
| Dictionaries and Their Implementations | |
| |
| |
| Dictionaries and Key-Value Pairs | |
| |
| |
| Linear (Array and Linked) and Hierarchical (Tree) Implementations | |
| |
| |
| Hash Functions | |
| |
| |
| Resolving Collisions | |
| |
| |
| A Hashing Implementation | |
| |
| |
| The Efficiency of Hashing | |
| |
| |
| |
| Balanced Search Trees | |
| |
| |
| AVL Trees | |
| |
| |
| 2-3 Trees | |
| |
| |
| 2-3-4 Trees | |
| |
| |
| Red-Black Trees | |
| |
| |
| |
| Graphs | |
| |
| |
| |
| Terminology | |
| |
| |
| |
| Graphs as ADTs | |
| |
| |
| |
| Implementing Graphs | |
| |
| |
| |
| Graph Traversals | |
| |
| |
| |
| Depth-First Search | |
| |
| |
| |
| Breadth-First Search | |
| |
| |
| |
| Applications of Graphs | |
| |
| |
| |
| Topological Sorting | |
| |
| |
| |
| Spanning Trees | |
| |
| |
| |
| Minimum Spanning Trees | |
| |
| |
| |
| Shortest Paths | |
| |
| |
| |
| Circuits | |
| |
| |
| |
| Some Difficult Problems | |
| |
| |
| |
| Processing Data in External Storage | |
| |
| |
| |
| A Look at External Storage | |
| |
| |
| |
| A Sorting Data in an External File | |
| |
| |
| |
| External Searches | |
| |
| |
| |
| Indexing an External File | |
| |
| |
| |
| External Hashing | |
| |
| |
| |
| B-Trees | |
| |
| |
| |
| Traversals | |
| |
| |
| |
| Multiple Indexing | |
| |
| |
| C++ Interlude 7 The Standard Template Library | |
| |
| |
| Introduction to Templates and the STL | |
| |
| |
| Generalizing the ADT Node and List | |
| |
| |
| |
| Review of C++ Fundamentals | |
| |
| |
| |
| Important Themes in Programming (currently Section 1.3) | |
| |
| |
| |
| The Unified Modeling Language (currently in section 1.1) | |
| |
| |
| |
| The Software Life Cycle (currently section 1.1) | |
| |
| |
| |
| Mathematical Induction (currently Appendix D) | |
| |
| |
| |
| Algorithm Verification (currently in section 1.2) | |
| |
| |
| |
| Files | |
| |
| |
| |
| C++ Header Files and Standard Functions (currently Appendix C) | |
| |
| |
| |
| C++ Standard Template Library (currently Appendix E) | |
| |
| |
| |
| C++ Documentation Systems (currently Appendix F) | |
| |
| |
| |
| ASCII Character Codes (currently Appendix B) | |
| |
| |
| |
| A Comparison of C++ and Java | |
| |
| |
| |
| A Comparison of C++ and Python | |