Secure Data Structures and Algorithms with C++: Walls and Mirrors, 8th edition
Published by Pearson (March 19, 2024) © 2025
  • Frank M. Carrano
  • Timothy M. Henry

Title overview

For courses in C++ data structures.

Fundamental concepts for C++ programmers

From designing video games to robotic-controlled surgery software and beyond, knowledge of data structures is essential to student success. 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, code uses 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.

Hallmark features of this title

  • A unique walls and mirrors approach reflects 2 fundamental problem-solving techniques that appear throughout. Data abstraction isolates and hides the implementation details of a module from the rest of the program (walls); Recursion is a repetitive technique that solves a problem by solving exactly the same but smaller problems (mirrors).
  • An important and unique feature, Security Notes, emphasizes aspects of safe and secure programming.
  • Programming Tips offer suggestions to improve or facilitate programming, and are highlighted as soon as they become relevant; Notes present or summarize important ideas within the narrative.
  • Essential learning aids include numerous Examples to illuminate new concepts; Margin Notes that mark key content or review material; and Chapter Summaries that conclude each chapter with a list of key ideas summarizing what was presented.
  • Exercises and Programming Problems at the end of each chapter offer additional problem-solving practice. Checkpoint Questions throughout reinforce the concept just presented. Solutions to these questions are available online.
  • VideoNotes: Online video tutorials provide visual and audio support to the topics throughout the book.

New and updated features of this title

  • Updated C++ code follows professional conventions using exceptions rather than return values to signal unusual situations, safe and secure coding techniques, and C++20 features where applicable.
  • Reorganized material divides chapters into 4 sections: The Foundation introduces key concepts used throughout (abstract data types, array-based and link-based ADT implementations, recursion, and algorithm efficiency). ADTs and Algorithms for Position-Oriented Access covers design and implementation of stacks, queues, deques, and lists. ADTs and Algorithms for Value-Oriented Access explores sorting algorithms and the design and implementation of sorted ADTs, trees, binary search trees, heaps, and priority queues. Advanced ADTs and Algorithms concludes the text.
  • Expanded coverage is offered on topics including TimSort (used in both Python and Java) and Introspection Sort (intro sort), used in C++; hashing with checksum and cryptographic hashes; backtracking and other recursive algorithms.
  • Expanded pedagogy includes added examples throughout the text’s first half, using a simulation of an amusement park; refined terminology and presentation to aid comprehension; revised figures and added color to improve clarity; and replacement of technologically dated examples.
  • Added material includes more Notes, Security Notes, and Programming Tips along with new checkpoint questions, exercises, and programming problems throughout.
  • ADT Dictionary is renamed to the ADT Map to better match C++ containers.

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)

Loading...Loading...Loading...