Secure Data Structures and Algorithms with C++: Walls and Mirrors -- Rental Edition, 8th Edition

About

Features

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.

Description

Whether youre 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.

This print textbook is available for students to rent for their classes. The Pearson print rental program provides students with affordable access to learning materials, so they come to class ready to succeed.

Sample Content

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.2An Array-Based Implementation of the ADT Bag
  • 3.3Implementing 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)

Updates

Submit Errata