| |
| |
| Software Engineering | |
| |
| |
| Problem Analysis and Specification | |
| |
| |
| Design | |
| |
| |
| Coding | |
| |
| |
| Testing, Execution, and Debugging | |
| |
| |
| Maintenance | |
| |
| |
| Programming Pointers | |
| |
| |
| ADT Tips | |
| |
| |
| Programming Problems | |
| |
| |
| Introduction to Data Structures and Abstract Data Types--C-Style Types | |
| |
| |
| Data Structures, Abstract Data Types, and Implementations | |
| |
| |
| Simple Data Types | |
| |
| |
| Arrays | |
| |
| |
| Structures | |
| |
| |
| Procedural Programming | |
| |
| |
| Programming Pointers | |
| |
| |
| ADT Tips | |
| |
| |
| Programming Problems | |
| |
| |
| More About Data Structures and ADTs--C++ Types | |
| |
| |
| Classes | |
| |
| |
| Example of a User-Defined Type: A Time Class | |
| |
| |
| Strings as ADTs | |
| |
| |
| The C++ string Type | |
| |
| |
| An Example: Text Editing | |
| |
| |
| Data Encryption (optional) | |
| |
| |
| Pattern Matching (optional) | |
| |
| |
| Programming Pointers | |
| |
| |
| ADT Tips | |
| |
| |
| Programming Problems | |
| |
| |
| Stacks | |
| |
| |
| Introduction to Stacks | |
| |
| |
| Designing and Building a Stack Class | |
| |
| |
| Two Applications of Stacks: Function Calls, Reverse Polish Notation | |
| |
| |
| Programming Pointers | |
| |
| |
| ADT Tips | |
| |
| |
| Programming Problems | |
| |
| |
| Queues | |
| |
| |
| Introduction to Queues | |
| |
| |
| Array-Based Implementation of Queues | |
| |
| |
| Application of Queues: Information Center Simulation | |
| |
| |
| Programming Pointers | |
| |
| |
| ADT Tips | |
| |
| |
| Programming Problems | |
| |
| |
| Improving ADTs--Part 1: Templates and Standard Containers | |
| |
| |
| Introduction: The Evolution of Reuseability and Genericity | |
| |
| |
| Function Genericity--Overloading and Templates | |
| |
| |
| Class Genericity--Templates | |
| |
| |
| The vector Container | |
| |
| |
| Multidimensional vectors | |
| |
| |
| Other Standard Containers--deque, stack, and queue | |
| |
| |
| Bitsets (Optional) | |
| |
| |
| Valarrays (Optional) | |
| |
| |
| Programming Pointers | |
| |
| |
| ADT Tips | |
| |
| |
| Programming Problems | |
| |
| |
| Improving ADTs--Part 2: Recursion, Algorithm Analysis, and Standard Algorithms | |
| |
| |
| Recusion | |
| |
| |
| More Examples of Recursion: Towers of Hanoi; Parsing | |
| |
| |
| Implementing Recursion | |
| |
| |
| Algorithm Efficiency | |
| |
| |
| Standard Algorithms in C++ | |
| |
| |
| Proving Algorithms Correct | |
| |
| |
| Programming Pointers | |
| |
| |
| ADT Tips | |
| |
| |
| Programming Problems | |
| |
| |
| Lists | |
| |
| |
| Sequential Storage Implementation of Lists | |
| |
| |
| Introduction to Linked Lists | |
| |
| |
| An Array-Based Implementation of Linked Lists (optional) | |
| |
| |
| Pointers in C++ | |
| |
| |
| Run-Time Allocation and Deallocation | |
| |
| |
| A Pointer-Based Implementation of Linked Lists in C++ | |
| |
| |
| The standard list Class Template | |
| |
| |
| Programming Pointers | |
| |
| |
| ADT Tips | |
| |
| |
| Programming Problems | |
| |
| |
| Other Linked Structures | |
| |
| |
| Some Variants of Singly-Linked Lists | |
| |
| |
| Linked Implementation of Sparse Polynomials | |
| |
| |
| Hash Tables | |
| |
| |
| Doubly-Linked Lists and the Standard C++ list | |
| |
| |
| Other Multiply-Linked Lists | |
| |
| |
| Programming Pointers | |
| |
| |
| ADT Tips | |
| |
| |
| Programming Problems | |
| |
| |
| Binary Trees | |
| |
| |
| Review of Linear Search and Binary Search | |
| |
| |
| Introduction to Binary Trees | |
| |
| |
| Binary Search Trees | |
| |
| |
| Binary Trees as Recursive Data Structures | |
| |
| |
| Application of Binary Trees: Huffman Codes | |
| |
| |
| Programming Pointers | |
| |
| |
| ADT Tips | |
| |
| |
| Programming Problems | |
| |
| |
| Sorting | |
| |
| |
| Some O(n[superscript 2]) Sorting Schemes | |
| |
| |
| Heaps and Heapsort | |
| |
| |
| Quicksort | |
| |
| |
| Mergesort | |
| |
| |
| Programming Pointers | |
| |
| |
| ADT Tips | |
| |
| |
| Programming Problems | |
| |
| |
| OOP and ADTs | |
| |
| |
| A Brief History and Overview of OOP and ADTs | |
| |
| |
| Inheritance and Object-Oriented Design | |
| |
| |
| Polymorphism, Virtual Functions, and ADTs | |
| |
| |
| Heterogeneous Data Structures | |
| |
| |
| Programming Pointers | |
| |
| |
| ADT Tips | |
| |
| |
| Programming Problems | |
| |
| |
| Trees | |
| |
| |
| Threaded Binary Search Trees | |
| |
| |
| Tree Balancing: AVL Trees | |
| |
| |
| 2-3-4 Trees, Red-Black Trees, B-Trees, and Other Trees | |
| |
| |
| Associative Containers in STL--maps (optional) | |
| |
| |
| Programming Pointers | |
| |
| |
| ADT Tips | |
| |
| |
| Programming Problems | |
| |
| |
| Graphs and Digraphs | |
| |
| |
| Directed Graphs | |
| |
| |
| Searching and Traversing Digraphs | |
| |
| |
| Graphs | |
| |
| |
| Programming Pointers | |
| |
| |
| ADT Tips | |
| |
| |
| Programming Problems | |
| |
| |
| Appendixes | |
| |
| |
| ASCII Character Set | |
| |
| |
| Number Systems | |
| |
| |
| Basic C++ | |
| |
| |
| Other C++ Features | |
| |
| |
| Answers to Quick Quizzes | |
| |
| |
| Index | |