C++ Plus Data Structures, 6th Edition

C++ Plus Data Structures, 6th Edition

by Nell Dale, Chip Weems, Tim Richards
Released August 2016
Publisher(s): Jones & Bartlett Learning
ISBN: 9781284089196

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

Nell Dale’s C++ Plus Data Structures, Sixth Edition explores the specifications, applications, and implementations of abstract data types. Topics covered include modularization, data encapsulation, information hiding, object-oriented decomposition, algorithm analysis, and more.

Table of contents

  1. Cover Page
  2. Title Page
  3. Copyright Page
  4. Contents
  5. Preface
  6. 1 Software Engineering Principles
    1. 1.1 The Software Process
      1. Software Life Cycles
      2. A Programmer’s Toolboxes
      3. Goals of Quality Software
      4. Specification: Understanding the Problem
      5. Writing Detailed Specification
    2. 1.2 Program Design
      1. Abstraction
      2. Information Hiding
      3. Stepwise Refinement
      4. Visual Tools
    3. 1.3 Design Approaches 17
      1. Top-Down Design
      2. Object-Oriented Design
    4. 1.4 Verification of Software Correctness
      1. Origin of Bugs
      2. Designing for Correctness
      3. Program Testing
      4. Testing C++ Data Structures
      5. Practical Considerations
      6. Case Study: Fraction Class
    5. Summary
      1. Exercises
  7. 2 Data Design and Implementation
    1. 2.1 Different Views of Data
      1. What Do We Mean by Data?
      2. Data Abstraction
      3. Data Structures
      4. Abstract Data Type Operator Categories
    2. 2.2 Abstraction and Built-In Types
      1. Records
      2. One-Dimensional Arrays
      3. Two-Dimensional Arrays
    3. 2.3 Higher-Level Abstraction and the C++ Class Type
      1. Class Specification
      2. Class Implementation
      3. Member Functions with Object Parameters
      4. Difference Between Classes and Structs
    4. 2.4 Object-Oriented Programming
      1. Concepts
      2. C++ Constructs for OOP
    5. 2.5 Constructs for Program Verification
      1. Exceptions
      2. Namespaces
    6. 2.6 Comparison of Algorithms
      1. Big-O
      2. Common Orders of Magnitude
      3. Example 1: Sum of Consecutive Integers
      4. Example 2: Finding a Number in a Phone Book
      5. Case Study: User-Defined Date ADT
    7. Summary
      1. Exercises
  8. 3 ADT Unsorted List
    1. 3.1 Lists
    2. 3.2 Abstract Data Type Unsorted List
      1. Logical Level
      2. Abstract Data Type Operations
      3. Generic Data Types
      4. Application Level
      5. Implementation Level
    3. 3.3 Pointer Types
      1. Logical Level
      2. Application Level
      3. Implementation Level
    4. 3.4 Implementing Class UnsortedType as a Linked Structure
      1. Linked Structures
      2. Class UnsortedType
      3. Function PutItem
      4. Constructor
      5. Observer Operations
      6. Function MakeEmpty
      7. Function GetItem
      8. Function DeleteItem
      9. Functions ResetList and GetNextItem
      10. Class Destructors
    5. 3.5 Comparing Unsorted List Implementations
      1. Case Study: Creating a Deck of Playing Cards
    6. Summary
      1. Exercises
  9. 4 ADT Sorted List
    1. 4.1 Abstract Data Type Sorted List
      1. Logical Level
      2. Application Level
      3. Implementation Level
    2. 4.2 Dynamically Allocated Arrays
    3. 4.3 Implementing the Sorted List as a Linked Structure
      1. Function GetItem
      2. Function PutItem
      3. Function DeleteItem
      4. Code
      5. Comparing Sorted List Implementations
    4. 4.4 Comparison of Unsorted and Sorted List ADT Algorithms
    5. 4.5 Bounded and Unbounded ADTs
    6. 4.6 Object-Oriented Design Methodology
      1. Brainstorming
      2. Filtering
      3. Scenarios
      4. Responsibility Algorithms
      5. Final Word
      6. Case Study: Evaluating Card Hands
    7. Summary
      1. Exercises
  10. 5 ADTs Stack and Queue
    1. 5.1 Stacks
      1. Logical Level
      2. Application Level
      3. Implementation Level
      4. Alternate Array-Based Implementation
    2. 5.2 Implementing a Stack as a Linked Structure
      1. Function Push
      2. Function Pop
      3. Function Top
      4. Other Stack Functions
      5. Comparing Stack Implementations
    3. 5.3 Queues
      1. Logical Level
      2. Application Level
      3. Implementation Level
      4. Counted Queue
    4. 5.4 Implementing a Queue as a Linked Structure
      1. Function Enqueue
      2. Function Dequeue
      3. A Circular Linked Queue Design
      4. Comparing Queue Implementations
      5. Case Study: Simulating a Solitaire Game
    5. Summary
      1. Exercises
  11. 6 Lists Plus
    1. 6.1 More About Generics: C++ Templates
    2. 6.2 Circular Linked Lists
      1. Finding a List Item
      2. Inserting Items into a Circular List
      3. Deleting Items from a Circular List
    3. 6.3 Doubly Linked Lists
      1. Finding an Item in a Doubly Linked List
      2. Operations on a Doubly Linked List
    4. 6.4 Linked Lists with Headers and Trailers
    5. 6.5 Copy Structures
      1. Shallow Versus Deep Copies
      2. Class Copy Constructors
      3. Copy Function
      4. Overloading Operators
    6. 6.6 A Linked List as an Array of Records
      1. Why Use an Array?
      2. How Is an Array Used?
    7. 6.7 Polymorphism with Virtual Functions
    8. 6.8 A Specialized List ADT
      1. Test Plan
    9. 6.9 Range-Based Iteration
      1. Case Study: Implementing a Large Integer ADT
    10. Summary
      1. Exercises
  12. 7 Programming with Recursion
    1. 7.1 What Is Recursion?
    2. 7.2 The Classic Example of Recursion
    3. 7.3 Programming Recursively
      1. Coding the Factorial Function
    4. 7.4 Verifying Recursive Functions
      1. Three-Question Method
    5. 7.5 Writing Recursive Functions
      1. Writing a Boolean Function
    6. 7.6 Using Recursion to Simplify Solutions
    7. 7.7 Recursive Linked List Processing
    8. 7.8 A Recursive Version of Binary Search
    9. 7.9 Recursive Versions of PutItem and DeleteItem
      1. Function PutItem
      2. Function DeleteItem
    10. 7.10 How Recursion Works
      1. Static Storage Allocation
      2. Dynamic Storage Allocation
    11. 7.11 Tracing the Execution of Recursive Function Insert
    12. 7.12 Recursive Quick Sort
    13. 7.13 Debugging Recursive Routines
    14. 7.14 Removing Recursion
      1. Iteration
      2. Stacking
    15. 7.15 Deciding Whether to Use a Recursive Solution
      1. Case Study: Escaping from a Maze
    16. Summary
      1. Exercises
  13. 8 Binary Search Trees
    1. 8.1 Searching
      1. Linear Searching
      2. High-Probability Ordering
      3. Key Ordering
      4. Binary Searching
    2. 8.2 Trees
    3. 8.3 Logical Level
    4. 8.4 Application Level
    5. 8.5 Implementation Level
    6. 8.6 Recursive Binary Search Tree Operations
      1. Functions IsFull and IsEmpty
      2. Function GetLength
      3. Function GetItem
      4. Function PutItem
      5. Function DeleteItem
      6. Function Print
      7. The Class Constructor and Destructor
      8. Copying a Tree
      9. More About Traversals
      10. Functions ResetTree and GetNextItem
    7. 8.7 Iterative Insertion and Deletion
      1. Searching a Binary Search Tree
      2. Function PutItem
      3. Function DeleteItem
      4. Test Plan
      5. Recursion or Iteration?
    8. 8.8 Comparing Binary Search Trees and Linear Lists
      1. Big-O Comparisons
      2. Case Study: Building an Index
    9. Summary
      1. Exercises
  14. 9 Heaps, Priority Queues, and Heap Sort
    1. 9.1 ADT Priority Queue
      1. Logical Level
      2. Application Level
      3. Implementation Level
    2. 9.2 A Nonlinked Representation of Binary Trees
    3. 9.3 Heaps
      1. Logical Level
      2. Application Level
      3. Implementation Level
      4. Application Level Revisited
      5. Heaps Versus Other Priority Queue Representations
    4. 9.4 Heap Sort
    5. Summary
      1. Exercises
  15. 10 Trees Plus
    1. 10.1 AVL Trees
      1. Single Rotations on AVL Trees
      2. Generalizing Single Rotations on AVL Trees
      3. Double Rotations on AVL Trees
      4. Generalizing Double Rotations on AVL Trees
      5. Application Level
      6. Logical Level
      7. Implementation Level
    2. 10.2 Red-Black Trees
      1. Inserting into Red-Black Trees
      2. Implementing Recoloring for Red-Black Trees
      3. Red-Black Tree Summary
    3. 10.3 B-Trees
    4. Summary
      1. Exercises
  16. 11 Sets, Maps, and Hashing
    1. 11.1 Sets
      1. Logical Level
      2. Application Level
      3. Implementation Level
    2. 11.2 Maps
      1. Logical Level
      2. Application Level
      3. Implementation Level
    3. 11.3 Hashing
      1. Collisions
      2. Choosing a Good Hash Function
      3. Complexity
    4. Summary
      1. Exercises
  17. 12 Sorting
    1. 12.1 Sorting Revisited
    2. 12.2 Straight Selection Sort
    3. 12.3 Bubble Sort
    4. 12.4 Insertion Sort
    5. 12.5 O(N log2 N) Sorts
      1. Merge Sort
      2. Quick Sort
      3. Heap Sort
      4. Testing
    6. 12.6 Efficiency and Other Considerations
      1. When N Is Small
      2. Eliminating Calls to Functions
      3. Programmer Time
      4. Space Considerations
      5. Keys and Stability
      6. Sorting with Pointers
      7. Caching
    7. 12.7 Radix Sort
      1. Analyzing the Radix Sort
    8. 12.8 Parallel Merge Sort
    9. Summary
      1. Exercises
  18. 13 Graphs
    1. 13.1 Graphs
      1. Logical Level
      2. Application Level
      3. Implementation Level
    2. Summary
      1. Exercises
  19. Appendix A Reserved Words
  20. Appendix B Operator Precedence
  21. Appendix C A Selection of Standard Library Routines
  22. Appendix D American Standard Code for Information Interchange (ASCII) Character Sets
  23. Appendix E The Standard Template Library (STL)
  24. Glossary
  25. Index

Product information

  • Title: C++ Plus Data Structures, 6th Edition
  • Author(s): Nell Dale, Chip Weems, Tim Richards
  • Release date: August 2016
  • Publisher(s): Jones & Bartlett Learning
  • ISBN: 9781284089196