Secure Data Structures and Algorithms with C++: Walls and Mirrors, 8th edition

The Foundation

• 1. Data Abstraction: The Walls
  • 1.1 Object-Oriented Problem Solving
  • 1.2 Achieving a Better Solution
  • 1.3 Specifying the Solution
  • 1.4 Abstract Data Types
• C++ Interlude 1: C++ Classes
• 2. Bags
  • 2.1 The ADT Bag
  • 2.2 The ADT NoDuplicatesBag
• 3. Array-Based Implementations
  • 3.1 The Approach
  • 3.2 An Array-Based Implementation of the ADT Bag
  • 3.3 Implementing the ADT NoDuplicatesBag
  • 3.4 Other Considerations
• C++ Interlude 2: Memory Allocation, Pointers, and Polymorphism
• 4. Link-Based Implementations
  • 4.1 Preliminaries
  • 4.2 A Link-Based Implementation of the ADT Bag
  • 4.3 Testing Multiple ADT Implementations
  • 4.4 Comparing Array-Based and Link-Based Implementations
• 5. Recursion: The Mirrors
  • 5.1 Recursive Solutions
  • 5.2 Recursion That Returns a Value
  • 5.3 Recursion That Performs an Action
  • 5.4 Recursion with Arrays
• 6. Recursion as a Problem-Solving Technique
  • 6.1 Simplifying Complex Problems
  • 6.2 Defining Languages
  • 6.3 Algebraic Expressions
  • 6.4 Recursion and the ADT Bag
  • 6.5 Recursion and Efficiency
• 7. Algorithm Efficiency
  • 7.1 What Is a Good Solution?
  • 7.2 Measuring the Efficiency of Algorithms

ADTs and Algorithms for Position-Oriented Access

• 8. Stacks
  • 8.1 The Abstract Data Type Stack
  • 8.2 Simple Uses of a Stack
  • 8.3 Using Stacks to Evaluate Postfix Expressions
  • 8.4 Stacks and Recursion
  • 8.5 The Relationship Between Stacks and Recursion
• C++ Interlude 3: Exceptions
• 9. Stack Implementation
  • 9.1 An Array-Based Stack Implementation
  • 9.2 A Link-Based Stack Implementation
  • 9.3 Stack Implementations That Use Exceptions
• 10. Queues and Decks
  • 10.1 The ADT Queue
  • 10.2 Applications of the ADT Queue
  • 10.3 The ADT Deque
  • 10.4 Simple Applications of the ADT Deque
• C++ Interlude 4: Safe Memory Management Using Smart Pointers
• 11. Queue and Deque Implementations
  • 11.1 Implementations of the ADT Queue
  • 11.2 A Linked-Based Implementation of the ADT Deque
  • 11.3 Comparing Implementations
• 12. Lists
  • 12.1 Specifying the ADT List
  • 12.2 Using the List Operations
  • 12.3 An Interface Template for the ADT List
• 13. List Implementations
  • 13.1 An Array-Based Implementation of the ADT List
  • 13.2 A Link-Based Implementation of the ADT List
  • 13.3 Comparing Implementations

ADTs and Algorithms for Value-Oriented Access

• 14. Basic Sorting Algorithms and Their Efficiency
  • 14.1 Sorting Algorithms
  • 14.2 The Selection Sort
  • 14.3 The Bubble Sort
  • 14.4 The Insertion Sort
  • 14.5 Insertion Sort of a Linked Chain
  • 14.6 The Shell Sort
  • 14.7 The Radix Sort
• 15. Advanced Sorting Algorithms
  • 15.1 The Merge Sort
  • 15.2 The Timsort
  • 15.3 The Quick Sort
  • 15.4 A Comparison of Sorting Algorithms
• C++ Interlude 5: Class Relationships and Reuse
• 16. Sorted Lists and Their Implementations
  • 16.1 Position-Oriented and Value-Oriented ADTs
  • 16.2 Specifying the ADT SortedList
  • 16.3 A Link-Based Implementation
  • 16.4 Implementations That Use the ADT List
  • 16.5 Efficiencies and Trade-Offs
• 17. Trees
  • 17.1 Terminology
  • 17.2 The ADT BinaryTree
• C++ Interlude 6: Overloaded Operators and Friend Access
• 18. Tree Implementations
  • 18.1 The Nodes in a Binary Tree
  • 18.2 A Link-Based Implementation of the ADT BinaryTree
  • 18.3 General Tree Implementations
• 19. Binary Search Trees
  • 19.1 Introduction
  • 19.2 The ADT BinarySearchTree
  • 19.3 AVL Trees
• 20. Implementing a Binary Search Tree
  • 20.1 C++ Definitions for the Operations of the ADT BinarySearchTree
  • 20.2 Saving a Binary Search Tree in a File
  • 20.3 Tree Sort
• 21. Priority Queues and Heaps
  • 21.1 The ADT PriorityQueue
  • 21.2 Priority Queue Application: Simulation
  • 21.3 The ADT Heap
• 22. Heap and Priority Queue Implementations
  • 22.1 An Array-Based Implementation of a Heap
  • 22.2 A Heap Implementation of the ADT PriorityQueue
  • 22.3 Heap Sort
  • 22.4 Introspection Sort

Advanced ADTs and Algorithms

• C++ Interlude 7: Iterators
• 23. Maps and Their Implementations
  • 23.1 The ADT Map
  • 23.2 Possible Implementations of the ADT Map
  • 23.3 Selecting an Implementation
• 24. Hashing as a Map Implementation
  • 24.1 What Is Hashing?
  • 24.2 Hash Functions
  • 24.3 Resolving Collisions
  • 24.4 The Efficiency of Hashing
  • 24.5 What Constitutes a Good Hash Function?
  • 24.6 An Implementation of the ADT Map Using Hashing and Separate Chaining
  • 24.7 Other Uses of Hashing in Computer Science
• 25. 2-3 Trees
  • 25.1 Reprise: Binary Search Trees
  • 25.2 The ADT SearchTree
  • 25.3 2-3 Trees
  • 25.4 Traversing a 2-3 Tree
  • 25.5 Searching a 2-3 Tree
  • 25.6 Adding Data to a 2-3 Tree
  • 25.7 Removing Data from a 2-3 Tree
• 26. Advanced Search Trees
  • 26.1 2-3-4 Trees
  • 26.2 Red-Black Trees
• 27. Graphs
  • 27.1 Terminology
  • 27.2 Graphs as ADTs
  • 27.3 Graph Traversals
• 28. Applications of Graphs
  • 28.1 Topological Sorting
  • 28.2 Spanning Trees
  • 28.3 Shortest Paths
  • 28.4 Circuits
  • 28.5 Some Difficult Problems
• 29. Processing Data in External Shortage
  • 29.1 A Look at External Storage
  • 29.2 Sorting Data in an External File
  • 29.3 Basic Data Management Operations
  • 29.4 Indexing an External File
  • 29.5 External Hashing
  • 29.6 B-Trees
  • 29.7 Multiple Indexing
• C++ Interlude 8: The C++ Standard Library

Appendices

• A. Review of C++ Fundamentals
• B. C++ File Fundamentals
• C. C++ Documentation Systems
• D. ASCII Character Codes
• E. Important Themes in Secure Programming
• F. The Unified Modeling Language
• G. Mathematical Induction
• H. Algorithm Verification
• I. C++ for Java Programmers
• J. C++ for Python Programmers

Index

Glossary (online)

Answers to Checkpoint Questions (online)