Pearson+

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

  • Frank M. Carrano
  • , Timothy M. Henry

  • Find it fast
    Find it fast

    Quickly navigate your eTextbook with search

  • Stay organized
    Stay organized

    Access all your eTextbooks in one place

  • Easily continue access
    Easily continue access

    Keep learning with auto-renew

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.

Published by Pearson (July 2nd 2024) - Copyright © 2025

ISBN-13: 9780138122805

Subject: Programming - Intermediate/Advanced

Category: C++ Data Structures

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)