Secure Data Structures and Algorithms with C++: Walls and Mirrors

Whether you’re interested in designing video games or software for robotic-controlled surgery, the study of data structures is vital. Secure Data Structures & Algorithms with C++ takes a unique walls and mirrors approach, presenting problem-solving techniques related to data abstraction (walls) and the efficient access and manipulation of data via recursion (mirrors). It emphasizes core data structures and object-oriented programming techniques for a strong foundation in data abstraction. In the 8th Edition, C++ code now uses exceptions and C++20 features, such as smart pointers, while following safe and secure coding techniques aligning with SEI CERT Coding Standards. Material is reorganized, with chapters divided into 4 sections; new and refined examples and figures appear throughout; and much more.

Table of Contents:
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)