| |
| |
| Preface | |
| |
| |
| Chapter Dependency Chart | |
| |
| |
| |
| Problem-Solving Techniques | |
| |
| |
| |
| Principles of Programming and Software Engineering | |
| |
| |
| |
| Software Engineering and Object-Oriented Design | |
| |
| |
| An Examination of Problem Solving | |
| |
| |
| Aspects of an Object-Oriented Solution | |
| |
| |
| Abstraction and Information Hiding | |
| |
| |
| Principles of Object-Oriented Programming | |
| |
| |
| Object-Oriented Analysis and Design | |
| |
| |
| Applying the UML to OOA/D | |
| |
| |
| The Software Life Cycle | |
| |
| |
| Iterative and Evolutionary Development | |
| |
| |
| Rational Unified Process Development Phases | |
| |
| |
| What About the Waterfall Method of Development? | |
| |
| |
| |
| Achieving a Better Solution | |
| |
| |
| Evaluation of Designs and Solutions | |
| |
| |
| Operation Contracts | |
| |
| |
| Verification | |
| |
| |
| What Is a Good Solution? | |
| |
| |
| |
| Key Issues in Programming | |
| |
| |
| Modularity | |
| |
| |
| Style | |
| |
| |
| Modifiability | |
| |
| |
| Ease of Use | |
| |
| |
| Fail-Safe Programming | |
| |
| |
| Debugging | |
| |
| |
| Testing | |
| |
| |
| |
| Recursion: The Mirrors | |
| |
| |
| |
| Recursive Solutions | |
| |
| |
| A Recursive Valued Function: The Factorial of n | |
| |
| |
| A Recursive void Function: Writing a String Backward | |
| |
| |
| |
| Counting Things | |
| |
| |
| Multiplying Rabbits (The Fibonacci Sequence) | |
| |
| |
| Organizing a Parade | |
| |
| |
| Mr. Spock's Dilemma (Choosing k Out of n Things) | |
| |
| |
| |
| Searching an Array | |
| |
| |
| Finding the Largest Item in an Array | |
| |
| |
| Binary Search | |
| |
| |
| Finding the kth Smallest Item of an Array | |
| |
| |
| |
| Organizing Data | |
| |
| |
| The Towers of Hanoi | |
| |
| |
| |
| Recursion and Efficiency | |
| |
| |
| |
| Data Abstraction: The Walls | |
| |
| |
| |
| Abstract Data Types | |
| |
| |
| |
| Specifying ADTs | |
| |
| |
| The ADT List | |
| |
| |
| The ADT Sorted List | |
| |
| |
| Designing an ADT | |
| |
| |
| Axioms (Optional) | |
| |
| |
| |
| Implementing ADTs | |
| |
| |
| C++ Classes | |
| |
| |
| C++ Namespaces | |
| |
| |
| An Array-Based Implementation of the ADT List | |
| |
| |
| C++ Exceptions | |
| |
| |
| An Implementation of the ADT List Using Exceptions | |
| |
| |
| |
| Linked Lists | |
| |
| |
| |
| Preliminaries | |
| |
| |
| Pointers | |
| |
| |
| Dynamic Allocation of Arrays | |
| |
| |
| Pointer-Based Linked Lists | |
| |
| |
| |
| Programming with Linked Lists | |
| |
| |
| Displaying the Contents of a Linked List | |
| |
| |
| Deleting a Specified Node from a Linked List | |
| |
| |
| Inserting a Node into a Specified Position of a Linked List | |
| |
| |
| A Pointer-Based Implementation of the ADT List | |
| |
| |
| Comparing Array-Based and Pointer-Based Implementations | |
| |
| |
| Saving and Restoring a Linked List by Using a File | |
| |
| |
| Passing a Linked List to a Method | |
| |
| |
| Processing Linked Lists Recursively | |
| |
| |
| Objects as Linked List Data | |
| |
| |
| |
| Variations of the Linked List | |
| |
| |
| Circular Linked Lists | |
| |
| |
| Dummy Head Nodes | |
| |
| |
| Doubly Linked Lists | |
| |
| |
| |
| Application: Maintaining an Inventory | |
| |
| |
| |
| The C++ Standard Template Library | |
| |
| |
| Containers | |
| |
| |
| Iterators | |
| |
| |
| The Standard Template Library Class list | |
| |
| |
| |
| Recursion as a Problem-Solving Technique | |
| |
| |
| |
| Backtracking | |
| |
| |
| The Eight Queens Problem | |
| |
| |
| Implementing Eight Queens Using the STL Class vector | |
| |
| |
| |
| Defining Languages | |
| |
| |
| The Basics of Grammars | |
| |
| |
| Two Simple Languages | |
| |
| |
| Algebraic Expressions | |
| |
| |
| |
| The Relationship Between Recursion and Mathematical Induction | |
| |
| |
| The Correctness of the Recursive Factorial Function | |
| |
| |
| The Cost of Towers of Hanoi | |
| |
| |
| |
| Problem Solving with Abstract Data Types | |
| |
| |
| |
| Stacks | |
| |
| |
| |
| The Abstract Data Type Stack | |
| |
| |
| Developing an ADT During the Design of a Solution | |
| |
| |
| |
| Simple Applications of the ADT Stack | |
| |
| |
| Checking for Balanced Braces | |
| |
| |
| Recognizing Strings in a Language | |
| |
| |
| |
| Implementations of the ADT Stack | |
| |
| |
| An Array-Based Implementation of the ADT Stack | |
| |
| |
| A Pointer-Based Implementation of the ADT Stack | |
| |
| |
| An Implementation That Uses the ADT List | |
| |
| |
| Comparing Implementations | |
| |
| |
| The Standard Template Library Class stack | |
| |
| |
| |
| Application: Algebraic Expressions | |
| |
| |
| Evaluating Postfix Expressions | |
| |
| |
| Converting Infix Expressions to Equivalent Postfix Expressions | |
| |
| |
| |
| Application: A Search Problem | |
| |
| |
| A Nonrecursive Solution That Uses a Stack | |
| |
| |
| A Recursive Solution | |
| |
| |
| |
| The Relationship Between Stacks and Recursion | |
| |
| |
| |
| Queues | |
| |
| |
| |
| The Abstract Data Type Queue | |
| |
| |
| |
| Simple Applications of the ADT Queue | |
| |
| |
| Reading a String of Characters | |
| |
| |
| Recognizing Palindromes | |
| |
| |
| |
| Implementations of the ADT Queue | |
| |
| |
| A Pointer-Based Implementation | |
| |
| |
| An Array-Based Implementation | |
| |
| |
| An Implementation That Uses the ADT List | |
| |
| |
| The Standard Template Library Class queue | |
| |
| |
| Comparing Implementations | |
| |
| |
| |
| A Summary of Position-Oriented ADTs | |
| |
| |
| |
| Application: Simulation | |
| |
| |
| |
| Advanced C++ Topics | |
| |
| |
| |
| Inheritance Revisited | |
| |
| |
| Public, Private, and Protected Inheritance | |
| |
| |
| Is-a, Has-a, and As-a Relationships | |
| |
| |
| |
| Virtual Methods and Late Binding | |
| |
| |
| Abstract Base Classes | |
| |
| |
| |
| Friends | |
| |
| |
| |
| The ADTs List and Sorted List Revisited | |
| |
| |
| Implementations of the ADT Sorted List That Use the ADT List | |
| |
| |
| |
| Class Templates | |
| |
| |
| |
| Overloaded Operators | |
| |
| |
| |
| Iterators | |
| |
| |
| Implementing the ADT List Using Iterators | |
| |
| |
| |
| Algorithm Efficiency and Sorting | |
| |
| |
| |
| 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 | |
| |
| |
| Selection Sort | |
| |
| |
| Bubble Sort | |
| |
| |
| Insertion Sort | |
| |
| |
| Mergesort | |
| |
| |
| Quicksort | |
| |
| |
| Radix Sort | |
| |
| |
| A Comparison of Sorting Algorithms | |
| |
| |
| The Standard Template LibrarySorting Algorithms | |
| |
| |
| |
| Trees | |
| |
| |
| |
| Terminology | |
| |
| |
| |
| The ADT Binary Tree | |
| |
| |
| Traversals of a Binary Tree | |
| |
| |
| Possible Representations of a Binary Tree | |
| |
| |
| A Pointer-Based Implementation of the ADT Binary Tree | |
| |
| |
| |
| The ADT Binary Search Tree | |
| |
| |
| Algorithms for the ADT Binary Search Tree Operations | |
| |
| |
| A Pointer-Based Implementation of the ADT Binary Search Tree | |
| |
| |
| The Efficiency of Binary Search Tree Operations | |
| |
| |
| Treesort | |
| |
| |
| Saving a Binary Search Tree in a File | |
| |
| |
| The STL Search Algorithms | |
| |
| |
| |
| General Trees | |
| |
| |
| |
| Tables and Priority Queues | |
| |
| |
| |
| The ADT Table | |
| |
| |
| Selecting an Implementation | |
| |
| |
| A Sorted Array-Based Implementation of the ADT Table | |
| |
| |
| A Binary Search Tree Implementation of the ADT Table | |
| |
| |
| |
| The ADT Priority Queue: A Variation of the ADT Table | |
| |
| |
| Heaps | |
| |
| |
| A Heap Implementation of the ADT Priority Queue | |
| |
| |
| Heapsort | |
| |
| |
| |
| Tables and Priority Queues in the STL | |
| |
| |
| The STL Associative Containers | |
| |
| |
| The STL priority_queue Class and Heap Algorithms | |
| |
| |
| |
| Advanced Implementations of Tables | |
| |
| |
| |
| Balanced Search Trees | |
| |
| |
| 2-3 Trees | |
| |
| |
| 2-3-4 Trees | |
| |
| |
| Red-Black Trees | |
| |
| |
| AVL Trees | |
| |
| |
| |
| Hashing | |
| |
| |
| Hash Functions | |
| |
| |
| Resolving Collisions | |
| |
| |
| The Efficiency of Hashing | |
| |
| |
| What Constitutes a Good Hash Function? | |
| |
| |
| Table Traversal: An Inefficient Operation Under Hashing | |
| |
| |
| Implementing a HashMap Class Using the STL | |
| |
| |
| |
| Data with Multiple Organizations | |
| |
| |
| |
| Graphs | |
| |
| |
| |
| Terminology | |
| |
| |
| |
| Graphs as ADTs | |
| |
| |
| Implementing Graphs | |
| |
| |
| Implementing a Graph Class Using the STL | |
| |
| |
| |
| Graph Traversals | |
| |
| |
| Depth-First Search | |
| |
| |
| Breadth-First Search | |
| |
| |
| Implementing a BFS Class Using the STL | |
| |
| |
| |
| 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 | |
| |
| |
| |
| Sorting Data in an External File | |
| |
| |
| |
| External Tables | |
| |
| |
| Indexing an External File | |
| |
| |
| External Hashing | |
| |
| |
| B-Trees | |
| |
| |
| Traversals | |
| |
| |
| Multiple Indexing | |
| |
| |
| |
| Review of C++ Fundamentals | |
| |
| |
| |
| ASCII Character Codes | |
| |
| |
| |
| C++ Header Files and Standard Functions | |
| |
| |
| |
| Mathematical Induction | |
| |
| |
| |
| Standard Template Library | |
| |
| |
| |
| C++ Documentation Systems | |
| |
| |
| Glossary | |
| |
| |
| Answers to Self-Test Exercises | |
| |
| |
| Index | |