Data structures & other objects using C++
By: Michael Main, Walter Savitch
Contributors: Savitch, Walter J., 1943-
Edition: 2nd ed.
Publisher: Addison Wesley Longman
Published: 2001
Place of publication: Boston, MA
Language: eng
Number of pages: 783
Subjects: C++ (Computer program language); Data structures (Computer science); Object-oriented programming (Computer science)
Other titles: Data structures and other objects using C++
Description: "The second edition continues to provided students with the fundamentals of data structures. It also teaches how to use the C++ Standard Library container classes through: revised interfaces for the principal example classes, which are compliant with the ANSI/ISO C++ Standard Library classes; optional material on Standard Library iterators; thorough coverage of the role of the const keyword in the C++ Standard Library; coverage of new C++ features such as namespaces, static member constants, and the typename keyword; extended coverage of inheritance; and extensive pedagogical features such as programming tips and pitfalls, exercises, and new programming projects."--Jacket.
Notes: Includes bibliographical references and index.
Table of contents: label: 1
title: The Phases of Software Development
pagenum: 1; label: 1.1
title: Specification, Design, Implementation
pagenum: 3; title: Design Technique: Decomposing the Problem
pagenum: 4; title: Preconditions and Postconditions
pagenum: 5; title: Using Functions Provided by Other Programmers
pagenum: 8; title: Implementation Issues for the ANSI/ISO C++ Standard
pagenum: 10; title: C++ Feature: The Standard Library and the Standard Namespace
pagenum: 10; title: Programming Tip: Use Declared Constants
pagenum: 11; title: Programming Tip: Use Assert to Check a Precondition
pagenum: 12; title: Programming Tip: Use EXIT_SUCCESS in a Main Program
pagenum: 13; title: Self-Test Exercises
pagenum: 13; label: 1.2
title: Running Time Analysis
pagenum: 14; title: The Stair-Counting Problem
pagenum: 14; title: Big-O Notation
pagenum: 19; title: Time Analysis of C++ Functions
pagenum: 22; title: Worst-Case, Average-Case, and Best-Case Analyses
pagenum: 24; title: Self-Test Exercises
pagenum: 24; label: 1.3
title: Testing and Debugging
pagenum: 24; title: Choosing Test Data
pagenum: 25; title: Boundary Values
pagenum: 25; title: Fully Exercising Code
pagenum: 26; title: Debugging
pagenum: 26; title: Programming Tip: How to Debug
pagenum: 27; title: Self-Test Exercises
pagenum: 27; title: Chapter Summary
pagenum: 28; title: Solutions to Self-Test Exercises
pagenum: 29; label: 2
title: Abstract Data Types and C++ Classes
pagenum: 30; label: 2.1
title: Classes and Members
pagenum: 31; title: The Throttle Class
pagenum: 31; title: Using a Class
pagenum: 36; title: A Small Demonstration Program for the Throttle Class
pagenum: 37; title: Implementing Member Functions
pagenum: 39; title: Member Functions May Activate Other Members
pagenum: 41; title: Programming Tip: Style for Boolean Values
pagenum: 42; title: Self-Test Exercises
pagenum: 42; label: 2.2
title: Constructors
pagenum: 42; title: The Throttle's Constructor
pagenum: 43; title: What Happens If You Write a Class with No Constructors?
pagenum: 46; title: Programming Tip: Always Provide Constructors
pagenum: 46; title: Revising the Throttle's Member Functions
pagenum: 46; title: Inline Member Functions
pagenum: 47; title: Programming Tip: When to Use an Inline Member Function
pagenum: 48; title: Self-Test Exercises
pagenum: 48; label: 2.3
title: Using a Namespace, Header File, and Implementation File
pagenum: 48; title: Creating a Namespace
pagenum: 48; title: The Header File
pagenum: 49; title: Describing the Value Semantics of a Class within the Header File
pagenum: 53; title: Programming Tip: Document the Value Semantics
pagenum: 54; title: The Implementation File
pagenum: 54; title: Using the Items in a Namespace
pagenum: 56; title: Pitfall: Never Put a Using Statement Actually in a Header File
pagenum: 57; title: Self-Test Exercises
pagenum: 59; label: 2.4
title: Classes and Parameters
pagenum: 60; title: The Point Class
pagenum: 60; title: Default Arguments
pagenum: 62; title: Programming Tip: A Default Constructor Can Be Provided by Using Default Arguments
pagenum: 63; title: Parameters
pagenum: 64; title: Pitfall: Using a Wrong Argument Type for a Reference Parameter
pagenum: 67; title: Programming Tip: Use const Consistently
pagenum: 70; title: When the Type of a Function's Return Value is a Class
pagenum: 70; title: Self-Test Exercises
pagenum: 71; label: 2.5
title: Operator Overloading
pagenum: 71; title: Overloading Binary Comparison Operators
pagenum: 72; title: Overloading Binary Arithmetic Operators
pagenum: 73; title: Overloading Output and Input Operators
pagenum: 74; title: Friend Functions
pagenum: 77; title: Programming Tip: When to Use a Friend Function
pagenum: 78; title: The Point Class—Putting Things Together
pagenum: 79; title: Summary of Operator Overloading
pagenum: 82; title: Self-Test Exercises
pagenum: 82; title: Chapter Summary
pagenum: 83; title: Solutions to Self-Test Exercises
pagenum: 84; title: Programming Projects
pagenum: 85; label: 3
title: Container Classes
pagenum: 91; label: 3.1
title: The Bag Class
pagenum: 92; title: The Bag Class—Specification
pagenum: 92; title: C++ Feature: Typedef Statements within a Class Definition
pagenum: 94; title: C++ Feature: The std::size_t Data Type
pagenum: 94; title: Older Compilers Do Not Support Initialization of Static Member Constants
pagenum: 99; title: The Bag Class—Documentation
pagenum: 100; title: Documenting the Value Semantics
pagenum: 100; title: The Bag Class—Demonstration Program
pagenum: 102; title: The Bag Class—Design
pagenum: 104; title: Pitfall: The value_type Type Must Have a Default Constructor
pagenum: 105; title: The Invariant of a Class
pagenum: 105; title: The Bag Class—Implementation
pagenum: 106; title: Pitfall: When to Use the Full Type Name bag::size_type
pagenum: 107; title: Programming Tip: Make Assertions Meaningful
pagenum: 107; title: C++ Feature: The copy Function from the C++ Standard Library
pagenum: 111; title: The Bag Class—Putting the Pieces Together
pagenum: 112; title: Programming Tip: Document the Class Invariant in the Implementation File
pagenum: 112; title: The Bag Class—Testing
pagenum: 112; title: Pitfall: An Object Can Be an Argument to Its Own Member Function
pagenum: 116; title: The Bag Class—Analysis
pagenum: 117; title: Self-Test Exercises
pagenum: 118; label: 3.2
title: Programming Project: The Sequence Class
pagenum: 119; title: The Sequence Class—Specification
pagenum: 119; title: The Sequence Class—Documentation
pagenum: 122; title: The Sequence Class—Design
pagenum: 122; title: The Sequence Class—Pseudocode for the Implementation
pagenum: 123; title: Self-Test Exercises
pagenum: 128; label: 3.3
title: Interactive Test Programs
pagenum: 128; title: C++ Feature: Converting Input to Uppercase Letters
pagenum: 129; title: C++ Feature: The Switch Statement
pagenum: 133; title: Self-Test Exercises
pagenum: 133; title: Chapter Summary
pagenum: 134; title: Solutions to Self-Test Exercises
pagenum: 134; title: Programming Projects
pagenum: 136; label: 4
title: Pointers and Dynamic Arrays
pagenum: 140; label: 4.1
title: Pointers and Dynamic Memory
pagenum: 141; title: Pointer Variables
pagenum: 141; title: Using the Assignment Operator with Pointers
pagenum: 144; title: Dynamic Variables and the new Operator
pagenum: 145; title: Using new to Allocate Dynamic Arrays
pagenum: 146; title: The Heap and the bad_alloc Exception
pagenum: 149; title: The delete Operator
pagenum: 149; title: Programming Tip: Define Pointer Types
pagenum: 150; title: Self-Test Exercises
pagenum: 151; label: 4.2
title: Pointers and Arrays as Parameters
pagenum: 152; title: Programming Example: Using a Dynamic Array
pagenum: 159; title: Self-Test Exercises
pagenum: 159; label: 4.3
title: The Bag Class with a Dynamic Array
pagenum: 162; title: Pointer Member Variables
pagenum: 162; title: Member Functions Allocate Dynamic Memory as Needed
pagenum: 163; title: Programming Tip: Provide Documentation about Possible Dynamic Memory Failure
pagenum: 167; title: Value Semantics
pagenum: 167; title: The Destructor
pagenum: 170; title: The Revised Bag Class—Class Definition
pagenum: 171; title: The Revised Bag Class—Implementation
pagenum: 173; title: Programming Tip: How to Check for Self-Assignment
pagenum: 174; title: Programming Tip: How to Allocate Memory in a Member Function
pagenum: 177; title: The Revised Bag Class—Putting the Pieces Together
pagenum: 178; title: Self-Test Exercises
pagenum: 180; label: 4.4
title: Prescription for a Dynamic Class
pagenum: 181; title: Four Rules
pagenum: 181; title: Special Importance of the Copy Constructor
pagenum: 181; title: Pitfall: Using Dynamic Memory Requires a Destructor, a Copy Constructor, and an Overloaded Assignment Operator
pagenum: 182; title: Self-Test Exercises
pagenum: 182; label: 4.5
title: Programming Project: The String Class
pagenum: 183; title: Null-Terminated Strings
pagenum: 183; title: Initializing a String Variable
pagenum: 184; title: The Empty String
pagenum: 184; title: Reading and Writing String Variables
pagenum: 184; title: Pitfall: Using = and == with Strings
pagenum: 185; title: The strcpy Function
pagenum: 185; title: The strcat Function
pagenum: 186; title: Pitfall: Dangers of strcpy, strcat, and Reading Strings
pagenum: 186; title: The strlen Function
pagenum: 186; title: The strcmp Function
pagenum: 187; title: The String Class—Specification
pagenum: 187; title: Constructor for the String Class
pagenum: 189; title: Overloading the Operator ()
pagenum: 190; title: Some Further Overloading
pagenum: 190; title: Other Operations for the String Class
pagenum: 191; title: The String Class—Design
pagenum: 191; title: The String Class—Implementation
pagenum: 192; title: Demonstration Program for the String Class
pagenum: 194; title: Chaining the Output Operator
pagenum: 196; title: Declaring Constant Objects
pagenum: 196; title: Constructor-Generated Conversions
pagenum: 196; title: Using Overloaded Operations in Expressions
pagenum: 197; title: Our String Class versus the C++ Library String Class
pagenum: 197; title: Self-Test Exercises
pagenum: 198; label: 4.6
title: Programming Project: The Polynomial
pagenum: 198; title: Chapter Summary
pagenum: 202; title: Solutions to Self-Test Exercises
pagenum: 202; title: Programming Projects
pagenum: 204; label: 5
title: Linked Lists
pagenum: 205; label: 5.1
title: A Fundamental Node Class for Linked Lists
pagenum: 206; title: Declaring a Class for Nodes
pagenum: 206; title: Using a Typedef Statement with Linked List Nodes
pagenum: 207; title: Head Pointers, Tail Pointers
pagenum: 207; title: The Null Pointer
pagenum: 208; title: The Meaning of a Null Head Pointer or Tail Pointer
pagenum: 209; title: The Node Constructor
pagenum: 209; title: The Node Member Functions
pagenum: 211; title: The Member Selection Operator
pagenum: 211; title: The const Keyword with a Pointer to a Node, and the Need for Two Versions of Some Member Functions
pagenum: 212; title: Programming Tip: A Rule for a Node's Constant Member Functions
pagenum: 213; title: Pitfall: Dereferencing the Null Pointer
pagenum: 214; title: Self-Test Exercises
pagenum: 215; label: 5.2
title: A Linked List Toolkit
pagenum: 215; title: Linked List Toolkit—Header File
pagenum: 216; title: Computing the Length of a Linked List
pagenum: 217; title: Programming Tip: How to Traverse a Linked List
pagenum: 220; title: Pitfall: Forgetting to Test the Empty List
pagenum: 220; title: Parameters for Linked Lists
pagenum: 221; title: Inserting a New Node at the Head of a Linked List
pagenum: 222; title: Inserting a New Node That Is Not at the Head
pagenum: 225; title: Pitfall: Unintended Calls to delete and new
pagenum: 227; title: Finding a Node by Its Position in a Linked List
pagenum: 230; title: Copying a Linked List
pagenum: 231; title: Removing a Node at the Head of a Linked List
pagenum: 235; title: Removing a Node That Is Not at the Head
pagenum: 235; title: Clearing a Linked List
pagenum: 237; title: Linked List Toolkit—Putting the Pieces Together
pagenum: 238; title: Using the Linked List Toolkit
pagenum: 238; title: Self-Test Exercises
pagenum: 238; label: 5.3
title: The Bag Class with a Linked List
pagenum: 243; title: Our Third Bag—Specification
pagenum: 243; title: Our Third Bag—Class Definition
pagenum: 243; title: How to Make the Bag value_type Match the Node value_type
pagenum: 244; title: Following the Rules for Dynamic Memory Usage in a Class
pagenum: 247; title: The Third Bag Class—Implementation
pagenum: 248; title: Pitfall: The Assignment Operator Causes Trouble with Linked Lists
pagenum: 249; title: Programming Tip: How to Choose Between Different Approaches
pagenum: 251; title: The Third Bag Class—Putting the Pieces Together
pagenum: 255; title: Self-Test Exercises
pagenum: 256; label: 5.4
title: Programming Project: The Sequence Class with a Linked List
pagenum: 259; title: The Revised Sequence Class—Design Suggestions
pagenum: 259; title: The Revised Sequence Class—Value Semantics
pagenum: 260; title: Self-Test Exercises
pagenum: 261; label: 5.5
title: Dynamic Arrays vs Linked Lists vs Doubly Linked Lists
pagenum: 261; title: Making the Decision
pagenum: 263; title: Self-Test Exercises
pagenum: 263; title: Chapter Summary
pagenum: 264; title: Solutions to Self-Test Exercises
pagenum: 264; title: Programming Projects
pagenum: 267; label: 6
title: Software Development with Templates, Iterators, and the Standard Library
pagenum: 270; label: 6.1
title: Template Functions
pagenum: 271; title: Syntax for a Template Function
pagenum: 272; title: Programming Tip: Capitalize the Name of a Template Parameter
pagenum: 273; title: Using a Template Function
pagenum: 273; title: Pitfall: Failed Unification Errors
pagenum: 274; title: A Template Function to Swap Two Values
pagenum: 274; title: C++ Feature: swap, max and min Functions
pagenum: 276; title: Parameter Matching for Template Functions
pagenum: 276; title: A Template Function to Find the Biggest Item in an Array
pagenum: 277; title: Pitfall: Mismatches for Template Function Arguments
pagenum: 278; title: A Template Function to Insert an Item into a Sorted Array
pagenum: 279; title: Self-Test Exercises
pagenum: 280; label: 6.2
title: Template Classes
pagenum: 281; title: Syntax for a Template Class
pagenum: 281; title: Programming Tip: Use the name Item and the typename Keyword
pagenum: 282; title: Pitfall: Do Not Place Using Directives in a Template Implementation
pagenum: 283; title: More about the Template Implementation File
pagenum: 283; title: Parameter Matching for Member Functions of Template Classes
pagenum: 288; title: Using the Template Class
pagenum: 288; title: Details of the Story-Writing Program
pagenum: 289; title: Self-Test Exercises
pagenum: 292; label: 6.3
title: Standard Template Classes and Their Iterators
pagenum: 292; title: The Multiset Template Class
pagenum: 292; title: Some Multiset Members
pagenum: 293; title: Iterators and the ( ... ) Pattern
pagenum: 293; title: Pitfall: Do Not Access an Iterator's Item after Reaching end()
pagenum: 295; title: Testing Iterators for Equality
pagenum: 296; title: Other Multiset Operations
pagenum: 297; title: Invalid Iterators
pagenum: 297; title: Pitfall: Changing a Container Object Can Invalidate Its Iterators
pagenum: 297; title: Const Iterators
pagenum: 298; title: Standard Categories of Iterators
pagenum: 299; title: Iterators for Arrays
pagenum: 300; title: Self-Test Exercises
pagenum: 300; label: 6.4
title: The Node Template Class
pagenum: 301; title: Functions That Return a Reference Type
pagenum: 302; title: What Happens When a Reference Return Value Is Copied Elsewhere
pagenum: 304; title: The Data Member Function Now Requires Two Versions
pagenum: 304; title: Header and Implementation Files for the New Node
pagenum: 305; title: Self-Test Exercises
pagenum: 305; label: 6.5
title: An Iterator for Linked Lists
pagenum: 313; title: The Node Iterator
pagenum: 313; title: The Node Iterator Is Derived from std::iterator
pagenum: 315; title: Pitfall: std::iterator Might Not Exist
pagenum: 316; title: The Node Iterator's Private Member Variable
pagenum: 316; title: Node Iterator—Constructor
pagenum: 316; title: Node Iterator—The * Operator
pagenum: 316; title: Node Iterator—Two Versions of the ++ Operator
pagenum: 317; title: Programming Tip: "++p" Is More Efficient Than "p++"
pagenum: 319; title: Iterators for Constant Collections
pagenum: 319; title: Programming Tip: When to Use a Const Iterator
pagenum: 321; title: Self-Test Exercises
pagenum: 321; label: 6.6
title: Linked List Version of the Bag Template Class with an Iterator
pagenum: 322; title: How to Provide an Iterator for a Container Class That You Write
pagenum: 322; title: The Bag Iterator
pagenum: 323; title: Why the Iterator Is Defined Inside the Bag
pagenum: 324; title: Self-Test Exercises
pagenum: 324; title: Chapter Summary and Summary of the Five Bags
pagenum: 332; title: Solutions to Self-Test Exercises
pagenum: 333; title: Programming Projects
pagenum: 335; label: 7
title: Stacks
pagenum: 337; label: 7.1
title: Introduction to Stacks and the STL stack
pagenum: 337; title: The Standard Library stack Class
pagenum: 339; title: Programming Example: Reversing a Word
pagenum: 340; title: Self-Test Exercises
pagenum: 341; label: 7.2
title: Stack Applications
pagenum: 342; title: Programming Example: Balanced Parentheses
pagenum: 342; title: Programming Example: Evaluating Arithmetic Expressions
pagenum: 344; title: Evaluating Arithmetic Expressions—Specification
pagenum: 344; title: Evaluating Arithmetic Expressions—Design
pagenum: 345; title: Evaluating Arithmetic Expressions—Implementation
pagenum: 351; title: Functions Used in the Calculator Program
pagenum: 352; title: Evaluating Arithmetic Expressions—Testing and Analysis
pagenum: 352; title: Evaluating Arithmetic Expressions—Enhancements
pagenum: 353; title: Self-Test Exercises
pagenum: 354; label: 7.3
title: Implementations of the stack Class
pagenum: 354; title: Array Implementation of a Stack
pagenum: 354; title: Linked List Implementation of a Stack
pagenum: 358; title: The Koenig Lookup
pagenum: 359; title: Self-Test Exercises
pagenum: 359; label: 7.4
title: More Complex Stack Applications
pagenum: 362; title: Evaluating Postfix Expressions
pagenum: 362; title: Translating Infix to Postfix Notation
pagenum: 364; title: Using Precedence Rules in the Infix Expression
pagenum: 366; title: Correctness of the Conversion from Infix to Postfix
pagenum: 368; title: Self-Test Exercises
pagenum: 372; title: Chapter Summary
pagenum: 372; title: Solutions to Self-Test Exercises
pagenum: 372; title: Programming Projects
pagenum: 374; label: 8
title: Queues
pagenum: 377; label: 8.1
title: Introduction to Queues and the STL queue
pagenum: 377; title: The Standard Library queue Class
pagenum: 379; title: Uses for Queues
pagenum: 380; title: Self-Test Exercises
pagenum: 381; label: 8.2
title: Queue Applications
pagenum: 381; title: Programming Example: Recognizing Palindromes
pagenum: 381; title: Self-Test Exercises
pagenum: 384; title: Programming Example: Car Wash Simulation
pagenum: 384; title: Car Wash Simulation—Specification
pagenum: 385; title: Car Wash Simulation—Design
pagenum: 385; title: Car Wash Simulation—Implementing the Car Wash Classes
pagenum: 389; title: Car Wash Simulation—Implementing the Simulation Function
pagenum: 394; title: Self-Test Exercises
pagenum: 395; label: 8.3
title: Implementations of the Queue Class
pagenum: 397; title: Array Implementation of a Queue
pagenum: 397; title: Programming Tip: Use Small Helper Functions to Improve Clarity
pagenum: 400; title: Discussion of the Circular Array Implementation of a Queue
pagenum: 402; title: Linked List Implementation of a Queue
pagenum: 404; title: Programming Tip: Make Note of "Don't Care" Situations
pagenum: 407; title: Pitfall: Forgetting Which End Is Which
pagenum: 407; title: Self-Test Exercises
pagenum: 410; label: 8.4
title: Priority Queues
pagenum: 410; title: How the Priorities Are Specified
pagenum: 411; title: The Standard Library priority_queue Class
pagenum: 411; title: Priority Queue Class—Implementation Ideas
pagenum: 411; title: Self-Test Exercises
pagenum: 412; label: 8.5
title: Reference Return Values for the Stack, Queue, and Priority Queue Classes
pagenum: 412; title: Chapter Summary
pagenum: 414; title: Solutions to Self-Test Exercises
pagenum: 414; title: Programming Projects
pagenum: 415; label: 9
title: Recursive Thinking
pagenum: 418; label: 9.1
title: Recursive Functions
pagenum: 419; title: A First Example of Recursive Thinking
pagenum: 419; title: Tracing Recursive Calls
pagenum: 421; title: Programming Example: An Extension of write_vertical
pagenum: 422; title: A Closer Look at Recursion
pagenum: 423; title: General Form of a Successful Recursive Function
pagenum: 427; title: Self-Test Exercises
pagenum: 428; label: 9.2
title: Studies of Recursion: Fractals and Mazes
pagenum: 429; title: Programming Example: Generating Random Fractals
pagenum: 429; title: A Function for Generating Random Fractals—Specification
pagenum: 430; title: Design and Implementation of the Fractal Function
pagenum: 432; title: How the Random Fractals Are Displayed
pagenum: 433; title: Programming Example: Traversing a Maze
pagenum: 435; title: Traversing a Maze—Specification
pagenum: 435; title: Traversing a Maze—Design
pagenum: 437; title: Traversing a Maze—Implementation
pagenum: 438; title: Self-Test Exercises
pagenum: 439; label: 9.3
title: Reasoning about Recursion
pagenum: 441; title: How to Ensure That There is No Infinite Recursion
pagenum: 443; title: Inductive Reasoning about the Correctness of a Recursive Function
pagenum: 446; title: Self-Test Exercises
pagenum: 448; title: Chapter Summary
pagenum: 448; title: Solutions to Self-Test Exercises
pagenum: 448; title: Programming Projects
pagenum: 450; label: 10
title: Trees
pagenum: 453; label: 10.1
title: Introduction to Trees
pagenum: 454; title: Binary Trees
pagenum: 454; title: Binary Taxonomy Trees
pagenum: 457; title: General Trees
pagenum: 458; title: Self-Test Exercises
pagenum: 459; label: 10.2
title: Tree Representations
pagenum: 459; title: Array Representation of Complete Binary Trees
pagenum: 459; title: Representing a Binary Tree with a Class for Nodes
pagenum: 462; title: Self-Test Exercises
pagenum: 464; label: 10.3
title: Binary Tree Nodes
pagenum: 464; title: Pitfall: Not Connecting All the Links
pagenum: 467; title: Programming Example: Animal Guessing
pagenum: 468; title: Animal Guessing Program—Design and Implementation
pagenum: 470; title: Animal Guessing Program—Improvements
pagenum: 479; title: Self-Test Exercises
pagenum: 479; label: 10.4
title: Tree Traversals
pagenum: 479; title: Traversals of Binary Trees
pagenum: 479; title: A Useful Backward In-Order Traversal
pagenum: 484; title: Programming Tip: Quick and Easy Printing of a Tree
pagenum: 485; title: The Problem with Our Traversals
pagenum: 486; title: A Parameter Can Be a Function
pagenum: 486; title: A Template Version of the apply Function
pagenum: 488; title: More Generality for the apply Template Function
pagenum: 489; title: Template Functions for Tree Traversals
pagenum: 490; title: Self-Test Exercises
pagenum: 491; label: 10.5
title: Binary Search Trees
pagenum: 497; title: The Binary Search Tree Storage Rules
pagenum: 497; title: Our Sixth Bag—Class Definition
pagenum: 501; title: Our Sixth Bag—Implementation of Some Simple Functions
pagenum: 501; title: Counting the Occurrences of an Item in a Binary Search Tree
pagenum: 502; title: Inserting a New Item into a Binary Search Tree
pagenum: 503; title: Removing an Item from a Binary Search Tree
pagenum: 504; title: The Union Operators for Binary Search Trees
pagenum: 508; title: Time Analysis and an Iterator
pagenum: 510; title: Self-Test Exercises
pagenum: 510; title: Chapter Summary
pagenum: 510; title: Solutions to Self-Test Exercises
pagenum: 511; title: Programming Projects
pagenum: 513; label: 11
title: Tree Projects
pagenum: 517; label: 11.1
title: Heaps
pagenum: 518; title: The Heap Storage Rules
pagenum: 518; title: The Priority Queue ADT with Heaps
pagenum: 519; title: Adding an Entry to a Heap
pagenum: 519; title: Removing an Entry from a Heap
pagenum: 521; title: Self-Test Exercises
pagenum: 524; label: 11.2
title: B-Trees
pagenum: 524; title: The Problem of Unbalanced Trees
pagenum: 524; title: The B-Tree Rules
pagenum: 525; title: An Example B-Tree
pagenum: 526; title: The Set ADT with B-Trees
pagenum: 527; title: Searching for an Item in a B-Tree
pagenum: 532; title: Inserting an Item into a B-Tree
pagenum: 534; title: The Loose Insertion into a B-Tree
pagenum: 534; title: A Private Member Function to Fix an Excess in a Child
pagenum: 537; title: Back to the Insert Member Function
pagenum: 538; title: Employing Top-Down Design
pagenum: 540; title: Removing an Item from a B-Tree
pagenum: 540; title: The Loose Erase from a B-Tree
pagenum: 541; title: A Private Member Function to Fix a Shortage in a Child
pagenum: 543; title: Removing the Biggest Item from a B-Tree
pagenum: 546; title: Programming Tip: Write and Test Small Pieces
pagenum: 546; title: External B-Trees
pagenum: 547; title: Self-Test Exercises
pagenum: 548; label: 11.3
title: Trees, Logs, and Time Analysis
pagenum: 549; title: Time Analysis for Binary Search Trees
pagenum: 549; title: Time Analysis for Heaps
pagenum: 550; title: Logarithms
pagenum: 553; title: Logarithmic Algorithms
pagenum: 554; title: Self-Test Exercises
pagenum: 554; title: Chapter Summary
pagenum: 554; title: Solutions to Self-Test Exercises
pagenum: 555; title: Programming Projects
pagenum: 557; label: 12
title: Searching
pagenum: 558; label: 12.1
title: Serial Search and Binary Search
pagenum: 559; title: Serial Search
pagenum: 559; title: Serial Search—Analysis
pagenum: 559; title: Binary Search
pagenum: 561; title: Binary Search—Design
pagenum: 562; title: Pitfall: Common Indexing Errors in Binary Search Implementations
pagenum: 563; title: Binary Search—Analysis
pagenum: 565; title: Self-Test Exercises
pagenum: 569; label: 12.2
title: Open-Address Hashing
pagenum: 569; title: Introduction to Hashing
pagenum: 570; title: The Table Class—Specification
pagenum: 572; title: The Table Class—Design
pagenum: 574; title: Programming Tip: Using size_t Can Indicate a Value's Purpose
pagenum: 577; title: The Table ADT—Implementation
pagenum: 578; title: C++ Feature: Inline Functions in the Implementation File
pagenum: 583; title: Choosing a Hash Function to Reduce Collisions
pagenum: 583; title: Double Hashing to Reduce Clustering
pagenum: 584; title: Self-Test Exercises
pagenum: 585; label: 12.3
title: Chained Hashing
pagenum: 586; title: Self-Test Exercises
pagenum: 588; label: 12.4
title: Time Analysis of Hashing
pagenum: 588; title: The Load Factor of a Hash Table
pagenum: 588; title: Self-Test Exercises
pagenum: 591; title: Chapter Summary
pagenum: 591; title: Solutions to Self-Test Exercises
pagenum: 592; title: Programming Projects
pagenum: 594; label: 13
title: Sorting
pagenum: 595; label: 13.1
title: Quadratic Sorting Algorithms
pagenum: 596; title: Selectionsort—Specification
pagenum: 596; title: Selectionsort—Design
pagenum: 596; title: Selectionsort—Implementation
pagenum: 598; title: Selectionsort—Analysis
pagenum: 600; title: Programming Tip: Rough Estimates Suffice for Big-O
pagenum: 602; title: Insertionsort
pagenum: 602; title: Insertionsort—Analysis
pagenum: 606; title: Self-Test Exercises
pagenum: 608; label: 13.2
title: Recursive Sorting Algorithms
pagenum: 608; title: Divide-and-Conquer Using Recursion
pagenum: 608; title: C++ Feature: Specifying a Subarray with Pointer Arithmetic
pagenum: 609; title: Mergesort
pagenum: 611; title: The Merge Function
pagenum: 613; title: Dynamic Memory Usage in Mergesort
pagenum: 618; title: Mergesort—Analysis
pagenum: 618; title: Mergesort for Files
pagenum: 620; title: Quicksort
pagenum: 620; title: The Partition Function
pagenum: 623; title: Quicksort—Analysis
pagenum: 626; title: Quicksort—Choosing a Good Pivot Element
pagenum: 628; title: Self-Test Exercises
pagenum: 628; label: 13.3
title: An O(n log n) Algorithm Using a Heap
pagenum: 629; title: Heapsort
pagenum: 629; title: Making the Heap
pagenum: 636; title: Reheapification Downward
pagenum: 637; title: Heapsort—Analysis
pagenum: 638; title: Self-Test Exercises
pagenum: 640; label: 13.4
title: Standard Library Sorting Functions
pagenum: 640; title: The C++ sort Function
pagenum: 640; title: The Original C Version of qsort
pagenum: 640; title: Chapter Summary
pagenum: 642; title: Solutions to Self-Test Exercises
pagenum: 642; title: Programming Projects
pagenum: 643; label: 14
title: Derived Classes and Inheritance
pagenum: 646; label: 14.1
title: Derived Classes
pagenum: 646; title: How to Declare a Derived Class
pagenum: 649; title: The Automatic Constructors of a Derived Class
pagenum: 650; title: Using a Derived Class
pagenum: 651; title: The Automatic Assignment Operator for a Derived Class
pagenum: 652; title: The Automatic Destructor of a Derived Class
pagenum: 653; title: Overriding Inherited Member Functions
pagenum: 653; title: Programming Tip: Make the Overriding Function Call the Original
pagenum: 654; title: Self-Test Exercises
pagenum: 655; label: 14.2
title: Simulation of an Ecosystem
pagenum: 655; title: Implementing Part of the Organism Object Hierarchy
pagenum: 656; title: The Organism Class
pagenum: 656; title: The Animal Class: A Derived Class with New Private Member Variables
pagenum: 659; title: How to Provide a New Constructor for a Derived Class
pagenum: 659; title: The Other Animal Member Functions
pagenum: 661; title: Self-Test Exercises
pagenum: 665; title: The Herbivore Class
pagenum: 666; title: The Pond Life Simulation Program
pagenum: 668; title: Pondlife—Implementation Details
pagenum: 673; title: Using the Pond Model
pagenum: 673; title: Dynamic Memory Usage
pagenum: 674; title: Self-Test Exercises
pagenum: 675; label: 14.3
title: Virtual Member Functions and a Game Class
pagenum: 675; title: Introduction to the Game Class
pagenum: 675; title: Protected Members
pagenum: 679; title: Virtual Member Functions
pagenum: 679; title: Virtual Destructors
pagenum: 681; title: The Protected Virtual Member Functions of the Game Class
pagenum: 681; title: A Derived Class to Play Connect Four
pagenum: 682; title: The Private Member Variables of the Connect Four Class
pagenum: 682; title: The Connect Four Constructor and Restart Function
pagenum: 684; title: Three Connect Four Functions That Deal with the Game's Status
pagenum: 684; title: Three Connect Four Functions That Deal with Moves
pagenum: 686; title: The Clone Function
pagenum: 686; title: Writing Your Own Derived Games from the Game Class
pagenum: 687; title: The Game Class's Play Algorithm with Minimax
pagenum: 688; title: Self-Test Exercises
pagenum: 691; title: Chapter Summary
pagenum: 691; title: Further Reading
pagenum: 691; title: Solutions to Self-Test Exercises
pagenum: 692; title: Programming Projects
pagenum: 694; label: 15
title: Graphs
pagenum: 695; label: 15.1
title: Graph Definitions
pagenum: 695; title: Undirected Graphs
pagenum: 696; title: Programming Example: Undirected State Graphs
pagenum: 697; title: Directed Graphs
pagenum: 700; title: More Graph Terminology
pagenum: 701; title: Airline Routes Example
pagenum: 702; title: Self-Test Exercises
pagenum: 702; label: 15.2
title: Graph Implementations
pagenum: 703; title: Representing Graphs with an Adjacency Matrix
pagenum: 703; title: Using a Two-Dimensional Array to Store an Adjacency Matrix
pagenum: 704; title: Representing Graphs with Edge Lists
pagenum: 704; title: Representing Graphs with Edge Sets
pagenum: 705; title: Which Representation Is Best?
pagenum: 706; title: Programming Example: Labeled Graph Class
pagenum: 706; title: Member Functions to Add Vertices and Edges
pagenum: 707; title: Labeled Graph Class—Overloading the Subscript Operator
pagenum: 708; title: A Const Version of the Subscript Operator
pagenum: 709; title: Labeled Graph Class—neighbors Function
pagenum: 710; title: Labeled Graph Class—Implementation
pagenum: 710; title: Self-Test Exercises
pagenum: 711; label: 15.3
title: Graph Traversals
pagenum: 716; title: Depth-First Search
pagenum: 717; title: Breadth-First Search
pagenum: 720; title: Depth-First Search—Implementation
pagenum: 722; title: Breadth-First Search—Implementation
pagenum: 724; title: Self-Test Exercises
pagenum: 724; label: 15.4
title: Path Algorithms
pagenum: 726; title: Determining Whether a Path Exists
pagenum: 726; title: Graphs with Weighted Edges
pagenum: 727; title: Shortest Distance Algorithm
pagenum: 728; title: Shortest Path Algorithm
pagenum: 738; title: Self-Test Exercises
pagenum: 739; title: Chapter Summary
pagenum: 740; title: Solutions to Self-Test Exercises
pagenum: 740; title: Programming Projects
pagenum: 741; label: Appendix A
title: ASCII Character Set
pagenum: 745; label: Appendix B
title: Further Big-O Notation
pagenum: 746; label: Appendix C
title: Precedence of Operators
pagenum: 748; label: Appendix D
title: Compiling, Linking, and Running Programs
pagenum: 749; label: Appendix E
title: Dealing with Older Compilers
pagenum: 752; label: Appendix F
title: Input and Output in C++
pagenum: 754; label: Appendix G
title: Selected Library Functions
pagenum: 762; label: Appendix H
title: Brief Reference for the Standard Template Classes
pagenum: 765; label: Appendix I
title: A Toolkit of Useful Functions
pagenum: 772; label: Appendix J
title: Fundamental Style Guide
pagenum: 775; label: Appendix K
title: Downloading the GNU Compiler and Software
pagenum: 776; title: Index
pagenum: 777