Entire Site

Safari Books Online

    Start Reading
    C++ Plus Data Structures, 6th Edition

    • C++ Plus Data Structures, 6th Edition

    • By: Dale

    • Publisher: Jones & Bartlett Learning

    • Pub. Date:

    • Print ISBN-13: 978-1-284-08918-9

    • Web ISBN-13: 978-1-284-08919-6

    • Pages in Print Edition: 838

    • Subscriber Rating: 0 out of 5 rating0 [0 Ratings]

    6ebooken
    Subscriber Reviews • Browse Similar Topics

    Overview

    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.

    Subscriber Reviews

    Average Rating: 0 out of 5 rating Based on 0 Ratings

    No Subscribers have provided a review for this book.

    Table of Contents

     

    View Sample

    Cover Page

    View Sample

    Title Page

    View Sample

    Copyright Page

    View Sample

    Contents

    View Sample

    Preface

    View Sample

    1 Software Engineering Principles

    View Sample
    1.1 The Software Process
    View Sample

    Software Life Cycles

    View Sample

    A Programmer’s Toolboxes

    View Sample

    Goals of Quality Software

    View Sample

    Specification: Understanding the Problem

    View Sample

    Writing Detailed Specification

    View Sample
    1.2 Program Design
    View Sample

    Abstraction

    View Sample

    Information Hiding

    View Sample

    Stepwise Refinement

    View Sample

    Visual Tools

    View Sample
    1.3 Design Approaches 17
    View Sample

    Top-Down Design

    View Sample

    Object-Oriented Design

    View Sample
    1.4 Verification of Software Correctness
    View Sample

    Origin of Bugs

    View Sample

    Designing for Correctness

    View Sample

    Program Testing

    View Sample

    Testing C++ Data Structures

    View Sample

    Practical Considerations

    View Sample

    Case Study: Fraction Class

    View Sample

    Summary

    View Sample

    2 Data Design and Implementation

    View Sample
    2.1 Different Views of Data
    View Sample

    What Do We Mean by Data?

    View Sample

    Data Abstraction

    View Sample

    Data Structures

    View Sample

    Abstract Data Type Operator Categories

    View Sample
    2.2 Abstraction and Built-In Types
    View Sample

    Records

    View Sample

    One-Dimensional Arrays

    View Sample

    Two-Dimensional Arrays

    View Sample
    2.3 Higher-Level Abstraction and the C++ Class Type
    View Sample

    Class Specification

    View Sample

    Class Implementation

    View Sample

    Member Functions with Object Parameters

    View Sample

    Difference Between Classes and Structs

    View Sample
    2.4 Object-Oriented Programming
    View Sample

    Concepts

    View Sample

    C++ Constructs for OOP

    View Sample
    2.5 Constructs for Program Verification
    View Sample

    Exceptions

    View Sample

    Namespaces

    View Sample
    2.6 Comparison of Algorithms
    View Sample

    Big-O

    View Sample

    Common Orders of Magnitude

    View Sample

    Example 1: Sum of Consecutive Integers

    View Sample

    Example 2: Finding a Number in a Phone Book

    View Sample

    Case Study: User-Defined Date ADT

    View Sample
    Summary
    View Sample

    Exercises

    View Sample
    3 ADT Unsorted List
    View Sample

    3.1 Lists

    View Sample
    3.2 Abstract Data Type Unsorted List
    View Sample

    Logical Level

    View Sample

    Abstract Data Type Operations

    View Sample

    Generic Data Types

    View Sample

    Application Level

    View Sample

    Implementation Level

    View Sample
    3.3 Pointer Types
    View Sample

    Logical Level

    View Sample

    Application Level

    View Sample

    Implementation Level

    View Sample
    3.4 Implementing Class UnsortedType as a Linked Structure
    View Sample

    Linked Structures

    View Sample

    Class UnsortedType

    View Sample

    Function PutItem

    View Sample

    Constructor

    View Sample

    Observer Operations

    View Sample

    Function MakeEmpty

    View Sample

    Function GetItem

    View Sample

    Function DeleteItem

    View Sample

    Functions ResetList and GetNextItem

    View Sample

    Class Destructors

    View Sample
    3.5 Comparing Unsorted List Implementations
    View Sample

    Case Study: Creating a Deck of Playing Cards

    View Sample
    Summary
    View Sample

    Exercises

    View Sample

    4 ADT Sorted List

    View Sample
    4.1 Abstract Data Type Sorted List
    View Sample

    Logical Level

    View Sample

    Application Level

    View Sample

    Implementation Level

    View Sample

    4.2 Dynamically Allocated Arrays

    View Sample
    4.3 Implementing the Sorted List as a Linked Structure
    View Sample

    Function GetItem

    View Sample

    Function PutItem

    View Sample

    Function DeleteItem

    View Sample

    Code

    View Sample

    Comparing Sorted List Implementations

    View Sample

    4.4 Comparison of Unsorted and Sorted List ADT Algorithms

    View Sample

    4.5 Bounded and Unbounded ADTs

    View Sample
    4.6 Object-Oriented Design Methodology
    View Sample

    Brainstorming

    View Sample

    Filtering

    View Sample

    Scenarios

    View Sample

    Responsibility Algorithms

    View Sample

    Final Word

    View Sample

    Case Study: Evaluating Card Hands

    View Sample

    Summary

    View Sample

    5 ADTs Stack and Queue

    View Sample
    5.1 Stacks
    View Sample

    Logical Level

    View Sample

    Application Level

    View Sample

    Implementation Level

    View Sample

    Alternate Array-Based Implementation

    View Sample
    5.2 Implementing a Stack as a Linked Structure
    View Sample

    Function Push

    View Sample

    Function Pop

    View Sample

    Function Top

    View Sample

    Other Stack Functions

    View Sample

    Comparing Stack Implementations

    View Sample
    5.3 Queues
    View Sample

    Logical Level

    View Sample

    Application Level

    View Sample

    Implementation Level

    View Sample

    Counted Queue

    View Sample
    5.4 Implementing a Queue as a Linked Structure
    View Sample

    Function Enqueue

    View Sample

    Function Dequeue

    View Sample

    A Circular Linked Queue Design

    View Sample

    Comparing Queue Implementations

    View Sample

    Case Study: Simulating a Solitaire Game

    View Sample
    Summary
    View Sample

    Exercises

    View Sample
    6 Lists Plus
    View Sample

    6.1 More About Generics: C++ Templates

    View Sample
    6.2 Circular Linked Lists
    View Sample

    Finding a List Item

    View Sample

    Inserting Items into a Circular List

    View Sample

    Deleting Items from a Circular List

    View Sample

    6.3 Doubly Linked Lists

    View Sample

    6.4 Linked Lists with Headers and Trailers

    View Sample
    6.5 Copy Structures
    View Sample

    Shallow Versus Deep Copies

    View Sample

    Class Copy Constructors

    View Sample

    Copy Function

    View Sample

    Overloading Operators

    View Sample
    6.6 A Linked List as an Array of Records
    View Sample

    Why Use an Array?

    View Sample

    How Is an Array Used?

    View Sample

    6.7 Polymorphism with Virtual Functions

    View Sample

    6.8 A Specialized List ADT

    View Sample
    6.9 Range-Based Iteration
    View Sample

    Case Study: Implementing a Large Integer ADT

    View Sample
    Summary
    View Sample

    Exercises

    View Sample
    7 Programming with Recursion
    View Sample

    7.1 What Is Recursion?

    View Sample

    7.2 The Classic Example of Recursion

    View Sample

    7.3 Programming Recursively

    View Sample

    7.4 Verifying Recursive Functions

    View Sample

    7.5 Writing Recursive Functions

    View Sample

    7.6 Using Recursion to Simplify Solutions

    View Sample

    7.7 Recursive Linked List Processing

    View Sample

    7.8 A Recursive Version of Binary Search

    View Sample

    7.9 Recursive Versions of PutItem and DeleteItem

    View Sample
    7.10 How Recursion Works
    View Sample

    Static Storage Allocation

    View Sample

    Dynamic Storage Allocation

    View Sample

    7.11 Tracing the Execution of Recursive Function Insert

    View Sample

    7.12 Recursive Quick Sort

    View Sample

    7.13 Debugging Recursive Routines

    View Sample

    7.14 Removing Recursion

    View Sample
    7.15 Deciding Whether to Use a Recursive Solution
    View Sample

    Case Study: Escaping from a Maze

    View Sample
    Summary
    View Sample

    Exercises

    View Sample

    8 Binary Search Trees

    View Sample
    8.1 Searching
    View Sample

    Linear Searching

    View Sample

    High-Probability Ordering

    View Sample

    Key Ordering

    View Sample

    Binary Searching

    View Sample

    8.2 Trees

    View Sample

    8.3 Logical Level

    View Sample

    8.4 Application Level

    View Sample

    8.5 Implementation Level

    View Sample
    8.6 Recursive Binary Search Tree Operations
    View Sample

    Functions IsFull and IsEmpty

    View Sample

    Function GetLength

    View Sample

    Function GetItem

    View Sample

    Function PutItem

    View Sample

    Function DeleteItem

    View Sample

    Function Print

    View Sample

    The Class Constructor and Destructor

    View Sample

    Copying a Tree

    View Sample

    More About Traversals

    View Sample

    Functions ResetTree and GetNextItem

    View Sample
    8.7 Iterative Insertion and Deletion
    View Sample

    Searching a Binary Search Tree

    View Sample

    Function PutItem

    View Sample

    Function DeleteItem

    View Sample

    Test Plan

    View Sample

    Recursion or Iteration?

    View Sample
    8.8 Comparing Binary Search Trees and Linear Lists
    View Sample

    Big-O Comparisons

    View Sample

    Case Study: Building an Index

    View Sample
    Summary
    View Sample

    Exercises

    View Sample
    9 Heaps, Priority Queues, and Heap Sort
    View Sample

    9.1 ADT Priority Queue

    View Sample

    9.2 A Nonlinked Representation of Binary Trees

    View Sample
    9.3 Heaps
    View Sample

    Logical Level

    View Sample

    Application Level

    View Sample

    Implementation Level

    View Sample

    Application Level Revisited

    View Sample

    Heaps Versus Other Priority Queue Representations

    View Sample

    9.4 Heap Sort

    View Sample

    Summary

    View Sample

    10 Trees Plus

    View Sample
    10.1 AVL Trees
    View Sample

    Single Rotations on AVL Trees

    View Sample

    Generalizing Single Rotations on AVL Trees

    View Sample

    Double Rotations on AVL Trees

    View Sample

    Generalizing Double Rotations on AVL Trees

    View Sample

    Application Level

    View Sample

    Logical Level

    View Sample

    Implementation Level

    View Sample
    10.2 Red-Black Trees
    View Sample

    Inserting into Red-Black Trees

    View Sample

    Implementing Recoloring for Red-Black Trees

    View Sample

    Red-Black Tree Summary

    View Sample

    10.3 B-Trees

    View Sample

    Summary

    View Sample

    11 Sets, Maps, and Hashing

    View Sample
    11.1 Sets
    View Sample

    Logical Level

    View Sample

    Application Level

    View Sample

    Implementation Level

    View Sample
    11.2 Maps
    View Sample

    Logical Level

    View Sample

    Application Level

    View Sample

    Implementation Level

    View Sample
    11.3 Hashing
    View Sample

    Collisions

    View Sample

    Choosing a Good Hash Function

    View Sample

    Complexity

    View Sample

    Summary

    View Sample
    12 Sorting
    View Sample

    12.1 Sorting Revisited

    View Sample

    12.2 Straight Selection Sort

    View Sample

    12.3 Bubble Sort

    View Sample

    12.4 Insertion Sort

    View Sample
    12.5 O(N log2 N) Sorts
    View Sample

    Merge Sort

    View Sample

    Quick Sort

    View Sample

    Heap Sort

    View Sample

    Testing

    View Sample
    12.6 Efficiency and Other Considerations
    View Sample

    When N Is Small

    View Sample

    Eliminating Calls to Functions

    View Sample

    Programmer Time

    View Sample

    Space Considerations

    View Sample

    Keys and Stability

    View Sample

    Sorting with Pointers

    View Sample

    Caching

    View Sample

    12.7 Radix Sort

    View Sample

    12.8 Parallel Merge Sort

    View Sample
    Summary
    View Sample

    Exercises

    View Sample

    13 Graphs

    View Sample
    13.1 Graphs
    View Sample

    Logical Level

    View Sample

    Application Level

    View Sample

    Implementation Level

    View Sample

    Summary

    View Sample

    Appendix A Reserved Words

    View Sample

    Appendix B Operator Precedence

    View Sample

    Appendix C A Selection of Standard Library Routines

    View Sample

    Appendix D American Standard Code for Information Interchange (ASCII) Character Sets

    View Sample

    Appendix E The Standard Template Library (STL)

    View Sample

    Glossary

    View Sample

    Index