C++ Plus Data Structures
Publisher: Jones & Bartlett Learning, LLC
Published: 2016
Language: eng
Number of pages: 838
ISBN-13: 9781284089189
Subjects: C plus plus (computer program language)
Table of contents: title: Preface
pagenum: xi; label: 1
title: Software Engineering Principles
pagenum: 1; label: 1.1
title: The Software Process
pagenum: 2; title: Software Life Cycles
pagenum: 3; title: A Programmer's Toolboxes
pagenum: 5; title: Goals of Quality Software
pagenum: 6; title: Specification: Understanding the Problem
pagenum: 9; title: Writing Detailed Specification
pagenum: 10; label: 1.2
title: Program Design
pagenum: 11; title: Abstraction
pagenum: 11; title: Information Hiding
pagenum: 13; title: Stepwise Refinement
pagenum: 14; title: Visual Tools
pagenum: 15; label: 1.3
title: Design Approaches
pagenum: 17; title: Top-Down Design
pagenum: 17; title: Object-Oriented Design
pagenum: 19; label: 1.4
title: Verification of Software Correctness
pagenum: 22; title: Origin of Bugs
pagenum: 23; title: Designing for Correctness
pagenum: 31; title: Program Testing
pagenum: 37; title: Testing C++ Data Structures
pagenum: 48; title: Practical Considerations
pagenum: 52; title: Case Study: Fraction Class
pagenum: 54; title: Summary
pagenum: 62; title: Exercises
pagenum: 63; label: 2
title: Data Design and Implementation
pagenum: 67; label: 2.1
title: Different Views of Data
pagenum: 68; title: What Do We Mean by Data?
pagenum: 68; title: Data Abstraction
pagenum: 68; title: Data Structures
pagenum: 70; title: Abstract Data Type Operator Categories
pagenum: 75; label: 2.2
title: Abstraction and Built-In Types
pagenum: 76; title: Records
pagenum: 77; title: One-Dimensional Arrays
pagenum: 81; title: Two-Dimensional Arrays
pagenum: 86; label: 2.3
title: Higher-Level Abstraction and the C++ Class Type
pagenum: 89; title: Class Specification
pagenum: 90; title: Class Implementation
pagenum: 92; title: Member Functions with Object Parameters
pagenum: 93; title: Difference Between Classes and Structs
pagenum: 95; label: 2.4
title: Object-Oriented Programming
pagenum: 95; title: Concepts
pagenum: 95; title: C++ Constructs for OOP
pagenum: 97; label: 2.5
title: Constructs for Program Verification
pagenum: 99; title: Exceptions
pagenum: 100; title: Namespaces
pagenum: 102; label: 2.6
title: Comparison of Algorithms
pagenum: 104; title: Big-O
pagenum: 106; title: Common Orders of Magnitude
pagenum: 107; title: Example 1: Sum of Consecutive Integers
pagenum: 108; title: Example 2: Finding a Number in a Phone Book
pagenum: 111; title: Case Study: User-Defined Date ADT
pagenum: 115; title: Summary
pagenum: 127; title: Exercises
pagenum: 128; label: 3
title: ADT Unsorted List
pagenum: 133; label: 3.1
title: Lists
pagenum: 134; label: 3.2
title: Abstract Data Type Unsorted List
pagenum: 135; title: Logical Level
pagenum: 135; title: Abstract Data Type Operations
pagenum: 135; title: Generic Data Types
pagenum: 137; title: Application Level
pagenum: 141; title: Implementation Level
pagenum: 143; label: 3.3
title: Pointer Types
pagenum: 160; title: Logical Level
pagenum: 160; title: Application Level
pagenum: 166; title: Implementation Level
pagenum: 167; label: 3.4
title: Implementing Class UnsortedType as a Linked Structure
pagenum: 167; title: Linked Structures
pagenum: 168; title: Class UnsortedType
pagenum: 174; title: Function PutItem
pagenum: 175; title: Constructor
pagenum: 177; title: Observer Operations
pagenum: 178; title: Function MakeEmpty
pagenum: 179; title: Function GetItem
pagenum: 179; title: Function DeleteItem
pagenum: 181; title: Functions ResetList and GetNextItem
pagenum: 183; title: Class Destructors
pagenum: 188; label: 3.5
title: Comparing Unsorted List Implementations
pagenum: 189; title: Case Study: Creating a Deck of Playing Cards
pagenum: 190; title: Summary
pagenum: 204; title: Exercises
pagenum: 205; label: 4
title: ADT Sorted List
pagenum: 213; label: 4.1
title: Abstract Data Type Sorted List
pagenum: 214; title: Logical Level
pagenum: 214; title: Application Level
pagenum: 216; title: Implementation Level
pagenum: 216; label: 4.2
title: Dynamically Allocated Arrays
pagenum: 229; label: 4.3
title: Implementing the Sorted List as a Linked Structure
pagenum: 231; title: Function GetItem
pagenum: 231; title: Function PutItem
pagenum: 234; title: Function DeleteItem
pagenum: 238; title: Code
pagenum: 239; title: Comparing Sorted List Implementations
pagenum: 243; label: 4.4
title: Comparison of Unsorted and Sorted List ADT Algorithms
pagenum: 246; label: 4.5
title: Bounded and Unbounded ADTs
pagenum: 247; label: 4.6
title: Object-Oriented Design Methodology
pagenum: 248; title: Brainstorming
pagenum: 248; title: Filtering
pagenum: 249; title: Scenarios
pagenum: 250; title: Responsibility Algorithms
pagenum: 251; title: Final Word
pagenum: 251; title: Case Study: Evaluating Card Hands
pagenum: 252; title: Summary
pagenum: 273; title: Exercises
pagenum: 273; label: 5
title: ADTs Stack and Queue
pagenum: 277; label: 5.1
title: Stacks
pagenum: 278; title: Logical Level
pagenum: 278; title: Application Level
pagenum: 281; title: Implementation Level
pagenum: 285; title: Alternate Array-Based Implementation
pagenum: 290; label: 5.2
title: Implementing a Stack as a Linked Structure
pagenum: 293; title: Function Push
pagenum: 294; title: Function Pop
pagenum: 295; title: Function Top
pagenum: 297; title: Other Stack Functions
pagenum: 297; title: Comparing Stack Implementations
pagenum: 299; label: 5.3
title: Queues
pagenum: 300; title: Logical Level
pagenum: 300; title: Application Level
pagenum: 304; title: Implementation Level
pagenum: 307; title: Counted Queue
pagenum: 315; label: 5.4
title: Implementing a Queue as a Linked Structure
pagenum: 320; title: Function Enqueue
pagenum: 320; title: Function Dequeue
pagenum: 322; title: A Circular Linked Queue Design
pagenum: 326; title: Comparing Queue Implementations
pagenum: 327; title: Case Study: Simulating a Solitaire Game
pagenum: 329; title: Summary
pagenum: 340; title: Exercises
pagenum: 341; label: 6
title: Lists Plus
pagenum: 355; label: 6.1
title: More About Generics: C++ Templates
pagenum: 356; label: 6.2
title: Circular Linked Lists
pagenum: 360; title: Finding a List Item
pagenum: 362; title: Inserting Items into a Circular List
pagenum: 366; title: Deleting Items from a Circular List
pagenum: 369; label: 6.3
title: Doubly Linked Lists
pagenum: 371; title: Finding an Item in a Doubly Linked List
pagenum: 372; title: Operations on a Doubly Linked List
pagenum: 373; label: 6.4
title: Linked Lists with Headers and Trailers
pagenum: 375; label: 6.5
title: Copy Structures
pagenum: 376; title: Shallow Versus Deep Copies
pagenum: 378; title: Class Copy Constructors
pagenum: 378; title: Copy Function
pagenum: 381; title: Overloading Operators
pagenum: 383; label: 6.6
title: A Linked List as an Array of Records
pagenum: 387; title: Why Use an Array?
pagenum: 388; title: How Is an Array Used?
pagenum: 389; label: 6.7
title: Polymorphism with Virtual Functions
pagenum: 396; label: 6.8
title: A Specialized List ADT
pagenum: 401; title: Test Plan
pagenum: 406; label: 6.9
title: Range-Based Iteration
pagenum: 407; title: Case Study: Implementing a Large Integer ADT
pagenum: 413; title: Summary
pagenum: 426; title: Exercises
pagenum: 426; label: 7
title: Programming with Recursion
pagenum: 435; label: 7.1
title: What Is Recursion?
pagenum: 436; label: 7.2
title: The Classic Example of Recursion
pagenum: 437; label: 7.3
title: Programming Recursively
pagenum: 440; title: Coding the Factorial Function
pagenum: 441; label: 7.4
title: Verifying Recursive Functions
pagenum: 443; title: Three-Question Method
pagenum: 443; label: 7.5
title: Writing Recursive Functions
pagenum: 444; title: Writing a Boolean Function
pagenum: 444; label: 7.6
title: Using Recursion to Simplify Solutions
pagenum: 447; label: 7.7
title: Recursive Linked List Processing
pagenum: 448; label: 7.8
title: A Recursive Version of Binary Search
pagenum: 452; label: 7.9
title: Recursive Versions of PutItem and DeleteItem
pagenum: 454; title: Function PutItem
pagenum: 454; title: Function DeleteItem
pagenum: 455; label: 7.10
title: How Recursion Works
pagenum: 456; title: Static Storage Allocation
pagenum: 456; title: Dynamic Storage Allocation
pagenum: 459; label: 7.11
title: Tracing the Execution of Recursive Function Insert
pagenum: 465; label: 7.12
title: Recursive Quick Sort
pagenum: 468; label: 7.13
title: Debugging Recursive Routines
pagenum: 475; label: 7.14
title: Removing Recursion
pagenum: 476; title: Iteration
pagenum: 476; title: Stacking
pagenum: 477; label: 7.15
title: Deciding Whether to Use a Recursive Solution
pagenum: 479; title: Case Study: Escaping from a Maze
pagenum: 481; title: Summary
pagenum: 494; title: Exercises
pagenum: 495; label: 8
title: Binary Search Trees
pagenum: 503; label: 8.1
title: Searching
pagenum: 504; title: Linear Searching
pagenum: 505; title: High-Probability Ordering
pagenum: 505; title: Key Ordering
pagenum: 506; title: Binary Searching
pagenum: 507; label: 8.2
title: Trees
pagenum: 507; label: 8.3
title: Logical Level
pagenum: 512; label: 8.4
title: Application Level
pagenum: 514; label: 8.5
title: Implementation Level
pagenum: 514; label: 8.6
title: Recursive Binary Search Tree Operations
pagenum: 515; title: Functions IsFull and IsEmpty
pagenum: 516; title: Function GetLength
pagenum: 516; title: Function GetItem
pagenum: 519; title: Function PutItem
pagenum: 522; title: Function DeleteItem
pagenum: 526; title: Function Print
pagenum: 533; title: The Class Constructor and Destructor
pagenum: 534; title: Copying a Tree
pagenum: 535; title: More About Traversals
pagenum: 540; title: Functions ResetTree and GetNextItem
pagenum: 542; label: 8.7
title: Iterative Insertion and Deletion
pagenum: 545; title: Searching a Binary Search Tree
pagenum: 545; title: Function PutItem
pagenum: 548; title: Function DeleteItem
pagenum: 551; title: Test Plan
pagenum: 552; title: Recursion or Iteration?
pagenum: 553; label: 8.8
title: Comparing Binary Search Trees and Linear Lists
pagenum: 553; title: Big-O Comparisons
pagenum: 554; title: Case Study: Building an Index
pagenum: 556; title: Summary
pagenum: 564; title: Exercises
pagenum: 564; label: 9
title: Heaps, Priority Queues, and Heap Sort
pagenum: 573; label: 9.1
title: ADT Priority Queue
pagenum: 574; title: Logical Level
pagenum: 574; title: Application Level
pagenum: 575; title: Implementation Level
pagenum: 576; label: 9.2
title: A Nonlinked Representation of Binary Trees
pagenum: 577; label: 9.3
title: Heaps
pagenum: 580; title: Logical Level
pagenum: 580; title: Application Level
pagenum: 584; title: Implementation Level
pagenum: 584; title: Application Level Revisited
pagenum: 589; title: Heaps Versus Other Priority Queue Representations
pagenum: 592; label: 9.4
title: Heap Sort
pagenum: 593; title: Summary
pagenum: 598; title: Exercises
pagenum: 599; label: 10
title: Trees Plus
pagenum: 607; label: 10.1
title: AVL Trees
pagenum: 608; title: Single Rotations on AVL Trees
pagenum: 609; title: Generalizing Single Rotations on AVL Trees
pagenum: 611; title: Double Rotations on AVL Trees
pagenum: 613; title: Generalizing Double Rotations on AVL Trees
pagenum: 616; title: Application Level
pagenum: 618; title: Logical Level
pagenum: 618; title: Implementation Level
pagenum: 619; label: 10.2
title: Red-Black Trees
pagenum: 625; title: Inserting into Red-Black Trees
pagenum: 626; title: Implementing Recoloring for Red-Black Trees
pagenum: 630; title: Red-Black Tree Summary
pagenum: 634; label: 10.3
title: B-Trees
pagenum: 634; title: Summary
pagenum: 638; title: Exercises
pagenum: 638; label: 11
title: Sets, Maps, and Hashing
pagenum: 641; label: 11.1
title: Sets
pagenum: 642; title: Logical Level
pagenum: 642; title: Application Level
pagenum: 646; title: Implementation Level
pagenum: 646; label: 11.2
title: Maps
pagenum: 650; title: Logical Level
pagenum: 651; title: Application Level
pagenum: 652; title: Implementation Level
pagenum: 653; label: 11.3
title: Hashing
pagenum: 654; title: Collisions
pagenum: 657; title: Choosing a Good Hash Function
pagenum: 665; title: Complexity
pagenum: 669; title: Summary
pagenum: 669; title: Exercises
pagenum: 670; label: 12
title: Sorting
pagenum: 673; label: 12.1
title: Sorting Revisited
pagenum: 674; label: 12.2
title: Straight Selection Sort
pagenum: 675; label: 12.3
title: Bubble Sort
pagenum: 679; label: 12.4
title: Insertion Sort
pagenum: 683; label: 12.5
title: O (N log2 N) Sorts
pagenum: 686; title: Merge Sort
pagenum: 687; title: Quick Sort
pagenum: 694; title: Heap Sort
pagenum: 695; title: Testing
pagenum: 695; label: 12.6
title: Efficiency and Other Considerations
pagenum: 696; title: When N Is Small
pagenum: 696; title: Eliminating Calls to Functions
pagenum: 696; title: Programmer Time
pagenum: 697; title: Space Considerations
pagenum: 697; title: Keys and Stability
pagenum: 698; title: Sorting with Pointers
pagenum: 699; title: Caching
pagenum: 700; label: 12.7
title: Radix Sort
pagenum: 701; title: Analyzing the Radix Sort
pagenum: 705; label: 12.8
title: Parallel Merge Sort
pagenum: 705; title: Summary
pagenum: 713; title: Exercises
pagenum: 715; label: 13
title: Graphs
pagenum: 721; label: 13.1
title: Graphs
pagenum: 722; title: Logical Level
pagenum: 722; title: Application Level
pagenum: 728; title: Implementation Level
pagenum: 739; title: Summary
pagenum: 746; title: Exercises
pagenum: 746; label: Appendix A
title: Reserved Words
pagenum: 751; label: Appendix B
title: Operator Precedence
pagenum: 751; label: Appendix C
title: A Selection of Standard Library Routines
pagenum: 753; label: Appendix D
title: American Standard Code for Information Interchange (ASCII) Character Sets
pagenum: 763; label: Appendix E
title: The Standard Template Library (STL)
pagenum: 764; title: Glossary
pagenum: 809; title: Index
pagenum: 815