Data Structures and Other Objects Using C++,9780321197160

Data Structures and Other Objects Using C++

by ;
Edition: 4th
ISBN13: 9780321197160
ISBN10: 032119716X
Format: Paperback
Pub. Date: 2011-01-01
Publisher(s): Addison Wesley
Upgraded Edition: Click here!
  • Free Shipping Icon

    This Item Qualifies for Free Shipping!*

    *Excludes marketplace orders.

List Price: $121.80

Buy Used

In stock
$87.00
Add to Cart

Rent Textbook

Select for Price
Add to Cart
There was a problem. Please try again later.

New Textbook

We're Sorry
Sold Out

eTextbook

We're Sorry
Not Available

Buy from our Marketplace starting at $5.50

How Marketplace Works:

  • This item is offered by an independent seller and not shipped from our warehouse
  • Item details like edition and cover design may differ from our description; see seller's comments before ordering.
  • Sellers much confirm and ship within two business days; otherwise, the order will be cancelled and refunded.
  • Marketplace purchases cannot be returned to eCampus.com. Contact the seller directly for inquiries; if no response within two days, contact customer service.
  • Additional shipping costs apply to Marketplace purchases. Review shipping costs at checkout.

Summary

This book successfully balances the introduction of object-oriented concepts with data structures in C++. KEN TOPICS:Provides interfaces for the principal example classes, which are compliant with the ANSI/ISO C++ Standard Library classes. Thorough coverage of the role of the const keyword in the C++ Standard Library. Covers C++ features such as namespaces, static member constants, typename keyword, and inheritance. Thorough review of C++ syntax and OOP concepts, making book accessible for programmers at various levels. The book also gives readers a firm grasp of key concepts and allows programmers experienced in another language to adjust easily. A solid foundation in building and using abstract data types is also provided, along with an assortment of advanced topics such as B-trees for project building and graphs. This book is designed for novice programmers who have learned the concepts of objects and classes and want to move on to the data structures topics of recursion and data abstraction.

Table of Contents

The Phases of Software Development
1(32)
Specification, Design, Implementation
3(12)
Design Concept: Decomposing the Problem
4(2)
Preconditions and Postconditions
6(2)
Using Functions Provided by Other Programmers
8(1)
Implementation Issues for the ANSI/ISO C++ Standard
8(1)
C++ Feature: The Standard Library and the Standard Namespace
9(2)
Programming Tip: Use Declared Constants
11(1)
Programming Tip: Use Assert to Check a Precondition
12(2)
Programming Tip: Use Exit_Success in a Main Program
14(1)
C++ Feature: Exception Handling
14(1)
Self-Test Exercises for Section 1.1
14(1)
Running Time Analysis
15(11)
The Stair-Counting Problem
15(6)
Big-O Notation
21(2)
Time Analysis of C++ Functions
23(2)
Worst-Case, Average-Case, and Best-Case Analyses
25(1)
Self-Test Exercises for Section 1.2
25(1)
Testing and Debugging
26(7)
Choosing Test Data
26(1)
Boundary Values
27(1)
Fully Exercising Code
28(1)
Debugging
28(1)
Programming Tip: How to Debug
28(1)
Self-Test Exercises for Section 1.3
29(1)
Chapter Summary
30(1)
Solutions to Self-Test Exercises
31(2)
Abstract Data Types and C++ Classes
33(62)
Classes and Members
34(11)
Programming Example: The Throttle Class
34(5)
Using a Class
39(1)
A Small Demonstration Program for the Throttle Class
40(2)
Implementing Member Functions
42(2)
Member Functions May Activate Other Members
44(1)
Programming Tip: Style for Boolean Variables
44(1)
Self-Test Exercises for Section 2.1
45(1)
Constructors
45(6)
The Throttle's Constructor
46(3)
What Happens If You Write a Class with No Constructors?
49(1)
Programming Tip: Always Provide Constructors
49(1)
Revising the Throttle's Member Functions
49(1)
Inline Member Functions
49(1)
Programming Tip: When to Use an Inline Member Function
50(1)
Self-Test Exercises for Section 2.2
51(1)
Using a Namespace, Header File, and Implementation File
51(12)
Creating a Namespace
51(1)
The Header File
52(4)
Describing the Value Semantics of a Class Within the Header File
56(1)
Programming Tip: Document the Value Semantics
57(1)
The Implementation File
57(2)
Using the Items in a Namespace
59(1)
Pitfall: Never Put a Using Statement Actually in a Header File
60(2)
Self-Test Exercises for Section 2.3
62(1)
Classes and Parameters
63(11)
Programming Example: The Point Class
63(2)
Default Arguments
65(1)
Programming Tip: A Default Constructor Can Be Provided by Using Default Arguments
66(1)
Parameters
67(3)
Pitfall: Using a Wrong Argument Type for a Reference Parameter
70(3)
Programming Tip: Use const Consistently
73(1)
When the Type of a Function's Return Value Is a Class
73(1)
Self-Test Exercises for Section 2.4
74(1)
Operator Overloading
74(21)
Overloading Binary Comparison Operators
75(1)
Overloading Binary Arithmetic Operators
76(1)
Overloading Output and Input Operators
77(3)
Friend Functions
80(1)
Programming Tip: When to Use a Friend Function
81(1)
The Point Class---Putting Things Together
82(3)
Summary of Operator Overloading
85(1)
Self-Test Exercises for Section 2.5
85(1)
Chapter Summary
86(1)
Solutions to Self-Test Exercises
87(2)
Programming Projects
89(6)
Container Classes
95(50)
The Bag Class
96(27)
The Bag Class---Specification
97(1)
C++ Feature: Typedef Statements Within a Class Definition
98(1)
C++ Feature: The std::size_t Data Type
99(5)
Older Compilers Do Not Support Initialization of Static Member Constants
104(1)
The Bag Class---Documentation
104(2)
Documenting the Value Semantics
106(1)
The Bag Class---Demonstration Program
106(2)
The Bag Class---Design
108(1)
Pitfall: The value_type Must Have a Default Constructor
109(1)
The Invariant of a Class
109(1)
The Bag Class---Implementation
110(1)
Pitfall: Needing to Use the Full Type Name bag::size_type
111(1)
Programming Tip: Make Assertions Meaningful
111(4)
C++ Feature: The Copy Function from the C++ Standard Library
115(1)
The Bag Class---Putting the Pieces Together
116(1)
Programming Tip: Document the Class Invariant in the Implementation File
116(4)
The Bag Class---Testing
120(1)
Pitfall: An Object Can Be an Argument to Its Own Member Function
120(1)
The Bag Class---Analysis
121(1)
Self-Test Exercises for Section 3.1
122(1)
Programming Project: The Sequence Class
123(9)
The Sequence Class---Specification
123(3)
The Sequence Class---Documentation
126(1)
The Sequence Class---Design
126(1)
The Sequence Class---Pseudocode for the Implementation
127(4)
Self-Test Exercises for Section 3.2
131(1)
Interactive Test Programs
132(13)
C++ Feature: Converting Input to Uppercase Letters
133(4)
C++ Feature: The Switch Statement
137(1)
Self-Test Exercises for Section 3.3
137(1)
Chapter Summary
138(1)
Solutions to Self-Test Exercises
138(2)
Programming Projects
140(5)
Pointers and Dynamic Arrays
145(66)
Pointers and Dynamic Memory
146(11)
Pointer Variables
147(2)
Using the Assignment Operator with Pointers
149(1)
Dynamic Variables and the new Operator
150(1)
Using new to Allocate Dynamic Arrays
151(3)
The Heap and the bad_alloc Exception
154(1)
The delete Operator
154(1)
Programming Tip: Define Pointer Types
155(1)
Self-Test Exercises for Section 4.1
156(1)
Pointers and Arrays as Parameters
157(10)
Self-Test Exercises for Section 4.2
164(3)
The Bag Class with a Dynamic Array
167(19)
Pointer Member Variables
167(1)
Member Functions Allocate Dynamic Memory as Needed
168(4)
Programming Tip: Provide Documentation About Possible Dynamic Memory Failure
172(1)
Value Semantics
172(3)
The Destructor
175(1)
The Revised Bag Class---Class Definition
176(2)
The Revised Bag Class---Implementation
178(1)
Programming Tip: How to Check for Self-Assignment
179(3)
Programming Tip: How to Allocate Memory in a Member Function
182(1)
The Revised Bag Class---Putting the Pieces Together
183(2)
Self-Test Exercises for Section 4.3
185(1)
Prescription for a Dynamic Class
186(2)
Four Rules
186(1)
Special Importance of the Copy Constructor
186(1)
Pitfall: Using Dynamic Memory Requires a Destructor, a Copy Constructor, and an Overloaded Assignment Operator
187(1)
Self-Test Exercises for Section 4.4
188(1)
Programming Project: The String Class
188(15)
Null-Terminated Strings
188(1)
Initializing a String Variable
189(1)
The Empty String
189(1)
Reading and Writing String Variables
190(1)
Pitfall: Using = and == with Strings
190(1)
The strcpy Function
190(1)
The strcat Function
191(1)
Pitfall: Dangers of strcpy, strcat, and Reading Strings
191(1)
The strlen Function
192(1)
The strcmp Function
192(1)
The String Class---Specification
192(2)
Constructor for the String Class
194(1)
Overloading the operator [ ]
195(1)
Some Further Overloading
195(1)
Other Operations for the String Class
196(1)
The String Class---Design
196(1)
The String Class---Implementation
197(2)
Demonstration Program for the String Class
199(2)
Chaining the Output Operator
201(1)
Declaring Constant Objects
201(1)
Constructor-Generated Conversions
201(1)
Using Overloaded Operations in Expressions
202(1)
Our String Class versus the C++ Library String Class
202(1)
Self-Test Exercises for Section 4.5
202(1)
Programming Project: The Polynomial
203(8)
Chapter Summary
207(1)
Solutions to Self-Test Exercises
207(2)
Programming Projects
209(2)
Linked Lists
211(67)
A Fundamental Node Class for Linked Lists
212(10)
Declaring a Class for Nodes
212(1)
Using a Typedef Statement with Linked-List Nodes
213(1)
Head Pointers, Tail Pointers
214(1)
The Null Pointer
215(1)
The Meaning of a Null Head Pointer or Tail Pointer
215(1)
The Node Constructor
215(1)
The Node Member Functions
216(1)
The Member Selection Operator
217(2)
Programming Tip: A Rule for a Node's Constant Member Functions
219(2)
Pitfall: Dereferencing the Null Pointer
221(1)
Self-Test Exercises for Section 5.1
221(1)
A Linked-List Toolkit
222(28)
Linked-List Toolkit---Header File
223(1)
Computing the Length of a Linked List
223(3)
Programming Tip: How to Traverse a Linked List
226(1)
Pitfall: Forgetting to Test the Empty List
227(1)
Parameters for Linked Lists
227(2)
Inserting a New Node at the Head of a Linked List
229(2)
Inserting a New Node That Is Not at the Head
231(3)
Pitfall: Unintended Calls to delete and new
234(3)
Finding a Node by Its Position in a Linked List
237(1)
Copying a Linked List
238(3)
Removing a Node at the Head of a Linked List
241(1)
Removing a Node That Is Not at the Head
242(1)
Clearing a Linked List
243(1)
Linked-List Toolkit---Putting the Pieces Together
244(1)
Using the Linked-List Toolkit
245(4)
Self-Test Exercises for Section 5.2
249(1)
The Bag Class with a Linked List
250(16)
Our Third Bag---Specification
250(1)
Our Third Bag---Class Definition
250(1)
How to Make the Bag value_type Match the Node value_type
251(3)
Following the Rules for Dynamic Memory Usage in a Class
254(1)
The Third Bag Class---Implementation
255(1)
Pitfall: The Assignment Operator Causes Trouble with Linked Lists
256(2)
Programming Tip: How to Choose Between Approaches
258(4)
The Third Bag Class---Putting the Pieces Together
262(1)
Self-Test Exercises for Section 5.3
263(3)
Programming Project: The Sequence Class with a Linked List
266(2)
The Revised Sequence Class---Design Suggestions
266(1)
The Revised Sequence Class---Value Semantics
267(1)
Self-Test Exercises for Section 5.4
268(1)
Dynamic Arrays vs Linked Lists vs Doubly Linked Lists
268(10)
Making the Decision
270(1)
Self-Test Exercises for Section 5.5
270(1)
Chapter Summary
271(1)
Solutions to Self-Test Exercises
271(4)
Programming Projects
275(3)
Software Development with Templates, Iterators, and the STL
278(70)
Template Functions
279(10)
Syntax for a Template Function
281(1)
Programming Tip: Capitalize the Name of a Template Parameter
281(1)
Using a Template Function
282(1)
Pitfall: Failed Unification Errors
282(2)
A Template Function to Swap Two Values
284(1)
C++ Feature: Swap, Max, and Min Functions
284(1)
Parameter Matching for Template Functions
284(1)
A Template Function to Find the Biggest Item in an Array
285(2)
Pitfall: Mismatches for Template Function Arguments
287(1)
A Template Function to Insert an Item into a Sorted Array
287(2)
Self-Test Exercises for Section 6.1
289(1)
Template Classes
289(12)
Syntax for a Template Class
289(2)
Programming Tip: Use the Name Item and the typename Keyword
291(1)
Pitfall: Do Not Place Using Directives in a Template Implementation
292(1)
More About the Template Implementation File
292(5)
Parameter Matching for Member Functions of Template Classes
297(1)
Using the Template Class
297(3)
Details of the Story-Writing Program
300(1)
Self-Test Exercises for Section 6.2
300(1)
Standard Template Classes and Their Iterators
301(12)
The Multiset Template Class
301(1)
Some Multiset Members
302(1)
Iterators and the [...) Pattern
302(2)
Pitfall: Do Not Access an Iterator's Item after Reaching end( )
304(1)
Testing Iterators for Equality
305(1)
Other Multiset Operations
306(1)
Set Algorithms
306(1)
Invalid Iterators
307(1)
Pitfall: Changing a Container Object Can Invalidate Its Iterators
308(1)
Standard Categories of Iterators
309(1)
Iterators for Arrays
310(1)
The Standard Template Library List Class
311(1)
Self-Test Exercises for Section 6.3
312(1)
The Node Template Class
313(11)
Functions That Return a Reference Type
314(1)
What Happens When a Reference Return Value Is Copied Elsewhere
315(1)
The Data Member Function Now Requires Two Versions
316(1)
Header and Implementation Files for the New Node
316(1)
Self-Test Exercises for Section 6.4
316(8)
An Iterator for Linked Lists
324(9)
The Node Iterator
324(2)
The Node Iterator Is Derived from std::iterator
326(1)
Pitfall: std::iterator Might Not Exist
327(1)
The Node Iterator's Private Member Variable
327(1)
Node Iterator---Constructor
327(1)
Node Iterator---The * Operator
327(1)
Node Iterator---Two Versions of the ++ Operator
328(2)
Programming Tip: ++p Is More Efficient Than p++
330(1)
Iterators for Constant Collections
330(2)
Programming Tip: When to Use a Const Iterator
332(1)
Self-Test Exercises for Section 6.5
332(1)
Linked-List Version of the Bag Template Class with an Iterator
333(15)
How to Provide an Iterator for a Container Class That You Write
333(1)
The Bag Iterator
334(1)
Why the Iterator Is Defined Inside the Bag
335(1)
Self-Test Exercises for Section 6.6
335(8)
Chapter Summary and Summary of the Five Bags
343(1)
Solutions to Self-Test Exercises
344(2)
Programming Projects
346(2)
Stacks
348(41)
Introduction to Stacks and the STL Stack
349(4)
The Standard Library Stack Class
350(1)
Programming Example: Reversing a Word
351(1)
Self-Test Exercises for Section 7.1
352(1)
Stack Applications
353(12)
Programming Example: Balanced Parentheses
353(2)
Programming Example: Evaluating Arithmetic Expressions
355(1)
Evaluating Arithmetic Expressions---Specification
355(1)
Evaluating Arithmetic Expressions---Design
356(6)
Evaluating Arithmetic Expressions---Implementation
362(1)
Functions Used in the Calculator Program
363(1)
Evaluating Arithmetic Expressions---Testing and Analysis
363(1)
Evaluating Arithmetic Expressions---Enhancements
364(1)
Self-Test Exercises for Section 7.2
364(1)
Implementations of the Stack Class
365(8)
Array Implementation of a Stack
365(4)
Linked-List Implementation of a Stack
369(1)
The Koenig Lookup
370(1)
Self-Test Exercises for Section 7.3
370(3)
More Complex Stack Applications
373(16)
Evaluating Postfix Expressions
373(2)
Translating Infix to Postfix Notation
375(2)
Using Precedence Rules in the Infix Expression
377(2)
Correctness of the Conversion from Infix to Postfix
379(4)
Self-Test Exercises for Section 7.4
383(1)
Chapter Summary
383(1)
Solutions to Self-Test Exercises
383(2)
Programming Projects
385(4)
Queues
389(42)
Introduction to Queues and the STL Queue
390(4)
The Standard Library Queue Class
391(1)
Uses for Queues
391(2)
Self-Test Exercises for Section 8.1
393(1)
Queue Applications
394(15)
Programming Example: Recognizing Palindromes
394(2)
Self-Test Exercises for Middle of Section 8.2
396(1)
Programming Example: Car Wash Simulation
397(1)
Car Wash Simulation---Specification
397(1)
Car Wash Simulation---Design
398(3)
Car Wash Simulation---Implementing the Car Wash Classes
401(5)
Car Wash Simulation---Implementing the Simulation Function
406(1)
Self-Test Exercises for Section 8.2
407(2)
Implementations of the Queue Class
409(13)
Array Implementation of a Queue
409(3)
Programming Tip: Use Small Helper Functions to Improve Clarity
412(2)
Discussion of the Circular Array Implementation of a Queue
414(2)
Linked-List Implementation of a Queue
416(3)
Programming Tip: Make Note of ``Don't Care'' Situations
419(1)
Pitfall: Which End Is Which
419(3)
Self-Test Exercises for Section 8.3
422(1)
Priority Queues
422(2)
How the Priorities Are Specified
423(1)
The Standard Library Priority Queue Class
423(1)
Priority Queue Class---Implementation Ideas
423(1)
Self-Test Exercises for Section 8.4
424(1)
Reference Return Values for the Stack, Queue, and Priority Queue Classes
424(7)
Chapter Summary
426(1)
Solutions to Self-Test Exercises
426(1)
Programming Projects
427(4)
Recursive Thinking
431(38)
Recursive Functions
432(10)
A First Example of Recursive Thinking
432(2)
Tracing Recursive Calls
434(2)
Programming Example: An Extension of write_vertical
436(1)
A Closer Look at Recursion
437(3)
General Form of a Successful Recursive Function
440(1)
Self-Test Exercises for Section 9.1
441(1)
Studies of Recursion: Fractals and Mazes
442(14)
Programming Example: Generating Random Fractals
442(1)
A Function for Generating Random Fractals---Specification
443(2)
Design and Implementation of the Fractal Function
445(1)
How the Random Fractals Are Displayed
446(2)
Programming Example: Traversing a Maze
448(1)
Traversing a Maze---Specification
448(2)
Traversing a Maze---Design
450(1)
Traversing a Maze---Implementation
451(2)
The Recursive Pattern of Exhaustive Search with Backtracking
453(1)
Programming Example: The Teddy Bear Game
454(1)
Pitfall: Forgetting to Use the Return Value from a Recursive Call
454(1)
Self-Test Exercises for Section 9.2
455(1)
Reasoning About Recursion
456(13)
How to Ensure That There Is No Infinite Recursion
458(3)
Inductive Reasoning About the Correctness of a Recursive Function
461(1)
Self-Test Exercises for Section 9.3
462(1)
Chapter Summary
463(1)
Solutions to Self-Test Exercises
463(2)
Programming Projects
465(4)
Trees
469(65)
Introduction to Trees
470(5)
Binary Trees
470(3)
Binary Taxonomy Trees
473(1)
General Trees
474(1)
Self-Test Exercises for Section 10.1
475(1)
Tree Representations
475(5)
Array Representation of Complete Binary Trees
475(3)
Representing a Binary Tree with a Class for Nodes
478(2)
Self-Test Exercises for Section 10.2
480(1)
Binary Tree Nodes
480(15)
Pitfall: Not Connecting All the Links
483(1)
Programming Example: Animal Guessing
484(2)
Animal Guessing Program---Design and Implementation
486(5)
Animal Guessing Program---Improvements
491(4)
Self-Test Exercises for Section 10.3
495(1)
Tree Traversals
495(18)
Traversals of Binary Trees
495(5)
Printing the Data from a Tree's Node
500(1)
The Problem with Our Traversals
501(1)
A Parameter Can Be a Function
502(2)
A Template Version of the Apply Function
504(1)
More Generality for the Apply Template Function
505(1)
Template Functions for Tree Traversals
506(1)
Self-Test Exercises for Section 10.4
507(6)
Binary Search Trees
513(21)
The Binary Search Tree Storage Rules
513(4)
Our Sixth Bag---Class Definition
517(1)
Our Sixth Bag---Implementation of Some Simple Functions
517(1)
Counting the Occurrences of an Item in a Binary Search Tree
518(1)
Inserting a New Item into a Binary Search Tree
519(1)
Removing an Item from a Binary Search Tree
520(4)
The Union Operators for Binary Search Trees
524(2)
Time Analysis and an Iterator
526(1)
Self-Test Exercises for Section 10.5
526(1)
Chapter Summary
526(1)
Solutions to Self-Test Exercises
527(2)
Programming Projects
529(5)
Tree Projects
534(41)
Heaps
535(6)
The Heap Storage Rules
535(1)
The Priority Queue ADT with Heaps
536(1)
Adding an Entry to a Heap
537(1)
Removing an Entry from a Heap
538(3)
Self-Test Exercises for Section 11.1
541(1)
B-Trees
541(25)
The Problem of Unbalanced Trees
541(1)
The B-Tree Rules
542(1)
An Example B-Tree
543(1)
The Set ADT with B-Trees
544(5)
Searching for an Item in a B-Tree
549(2)
Inserting an Item into a B-Tree
551(1)
The Loose Insertion into a B-Tree
551(3)
A Private Member Function to Fix an Excess in a Child
554(1)
Back to the Insert Member Function
555(2)
Employing Top-Down Design
557(1)
Removing an Item from a B-Tree
557(1)
The Loose Erase from a B-Tree
558(2)
A Private Member Function to Fix a Shortage in a Child
560(3)
Removing the Biggest Item from a B-Tree
563(1)
Programming Tip: Write and Test Small Pieces
563(1)
Programming Tip: Consider Using the STL Vector
564(1)
External B-Trees
564(1)
Self-Test Exercises for Section 11.2
565(1)
Trees, Logs, and Time Analysis
566(9)
Time Analysis for Binary Search Trees
567(1)
Time Analysis for Heaps
567(2)
Logarithms
569(1)
Logarithmic Algorithms
570(1)
Self-Test Exercises for Section 11.3
571(1)
Chapter Summary
571(1)
Solutions to Self-Test Exercises
572(2)
Programming Projects
574(1)
Searching
575(47)
Serial Search and Binary Search
576(14)
Serial Search
576(1)
Serial Search---Analysis
576(2)
Binary Search
578(1)
Binary Search---Design
579(2)
Pitfall: Common Indexing Errors in Binary Search Implementations
581(1)
Binary Search---Analysis
582(4)
Standard Library Search Functions
586(1)
Functions for Sorted Ranges
586(2)
Functions for Unsorted Ranges
588(1)
The STL search Function
588(2)
Self-Test Exercises for Section 12.1
590(1)
Open-Address Hashing
590(17)
Introduction to Hashing
590(3)
The Table Class---Specification
593(2)
The Table Class---Design
595(3)
Programming Tip: Using size_t Can Indicate a Value's Purpose
598(1)
The Table ADT---Implementation
598(6)
C++ Feature: Inline Functions in the Implementation File
604(1)
Choosing a Hash Function to Reduce Collisions
604(1)
Double Hashing to Reduce Clustering
605(1)
Self-Test Exercises for Section 12.2
606(1)
Chained Hashing
607(2)
Self-Test Exercises for Section 12.3
609(1)
Time Analysis of Hashing
609(3)
The Load Factor of a Hash Table
609(3)
Self-Test Exercises for Section 12.4
612(1)
Programming Project: A Table Class with STL Vectors
612(4)
A New Table Class
612(1)
Using Vectors in the New Table
613(1)
Template Parameters That Are Constants
613(1)
Template Parameters That Are Functions
613(1)
Implementing the New Table Class
614(1)
Self-Test Exercises for Section 12.5
615(1)
Maps and Multimaps from the STL
616(6)
Chapter Summary
617(1)
Solutions to Self-Test Exercises
617(3)
Programming Projects
620(2)
Sorting
622(51)
Quadratic Sorting Algorithms
623(12)
Selectionsort---Specification
623(1)
Selectionsort---Design
623(2)
Selectionsort---Implementation
625(2)
Selectionsort---Analysis
627(2)
Programming Tip: Rough Estimates Suffice for Big-O
629(1)
Insertionsort
629(4)
Insertionsort---Analysis
633(2)
Self-Test Exercises for Section 13.1
635(1)
Recursive Sorting Algorithms
635(20)
Divide-and-Conquer Using Recursion
635(1)
C++ Feature: Specifying a Subarray with Pointer Arithmetic
636(2)
Mergesort
638(1)
The Merge Function
639(5)
Dynamic Memory Usage in Mergesort
644(1)
Mergesort---Analysis
644(2)
Mergesort for Files
646(1)
Quicksort
646(2)
The Partition Function
648(4)
Quicksort---Analysis
652(2)
Quicksort---Choosing a Good Pivot Element
654(1)
Self-Test Exercises for Section 13.2
654(1)
An O(n log n) Algorithm Using a Heap
655(10)
Heapsort
655(5)
Making the Heap
660(3)
Reheapification Downward
663(1)
Heapsort---Analysis
664(1)
Self-Test Exercises for Section 13.3
665(1)
Sorting with Library Functions and Random Acesss Iterators
665(8)
The Original C qsort Function
665(1)
The STL Sort Function
666(1)
Writing a Sort Function That Uses Iterators
667(1)
Chapter Summary
668(1)
Solutions to Self-Test Exercises
669(1)
Programming Projects
670(3)
Derived Classes and Inheritance
673(49)
Derived Classes
674(8)
How to Declare a Derived Class
676(1)
The Automatic Constructors of a Derived Class
677(1)
Using a Derived Class
678(2)
The Automatic Assignment Operator for a Derived Class
680(1)
The Automatic Destructor of a Derived Class
680(1)
Overriding Inherited Member Functions
681(1)
Programming Tip: Make the Overriding Function Call the Original
682(1)
Self-Test Exercises for Section 14.1
682(1)
Simulation of an Ecosystem
682(20)
Implementing Part of the Organism Object Hierarchy
683(1)
The Organism Class
683(3)
The Animal Class: A Derived Class with New Private Member Variables
686(1)
How to Provide a New Constructor for a Derived Class
686(2)
The Other Animal Member Functions
688(4)
Self-Test Exercises for Middle of Section 14.2
692(1)
The Herbivore Class
693(2)
The Pond Life Simulation Program
695(5)
Pondlife---Implementation Details
700(1)
Using the Pond Model
700(1)
Dynamic Memory Usage
701(1)
Self-Test Exercises for Section 14.2
702(1)
Virtual Member Functions and a Game Class
702(20)
Introduction to the Game Class
702(4)
Protected Members
706(1)
Virtual Member Functions
706(2)
Virtual Destructors
708(1)
The Protected Virtual Member Functions of the Game Class
708(1)
A Derived Class to Play Connect Four
709(1)
The Private Member Variables of the Connect Four Class
709(2)
The Connect Four Constructor and Restart Function
711(1)
Three Connect Four Functions That Deal with the Game's Status
711(1)
Three Connect Four Functions That Deal with Moves
712(1)
The Clone Function
713(1)
Writing Your Own Derived Games from the Game Class
714(1)
The Game Class's Play Algorithm with Minimax
714(2)
Self-Test Exercises for Section 14.3
716(2)
Chapter Summary
718(1)
Further Reading
718(1)
Solutions to Self-Test Exercises
718(3)
Programming Projects
721(1)
Graphs
722(87)
Graph Definitions
723(7)
Undirected Graphs
723(1)
Programming Example: Undirected State Graphs
724(3)
Directed Graphs
727(1)
More Graph Terminology
728(1)
Airline Routes Example
729(1)
Self-Test Exercises for Section 15.1
729(1)
Graph Implementations
730(13)
Representing Graphs with an Adjacency Matrix
730(1)
Using a Two-Dimensional Array to Store an Adjacency Matrix
731(1)
Representing Graphs with Edge Lists
731(1)
Representing Graphs with Edge Sets
732(1)
Which Representation Is Best?
733(1)
Programming Example: Labeled Graph Class
733(1)
Member Functions to Add Vertices and Edges
734(1)
Labeled Graph Class---Overloading the Subscript Operator
735(1)
A Const Version of the Subscript Operator
736(1)
Labeled Graph Class---Neighbors Function
737(1)
Labeled Graph Class---Implementation
737(1)
Self-Test Exercises for Section 15.2
738(5)
Graph Traversals
743(10)
Depth-First Search
744(3)
Breadth-First Search
747(2)
Depth-First Search---Implementation
749(2)
Breadth-First Search---Implementation
751(1)
Self-Test Exercises for Section 15.3
751(2)
Path Algorithms
753(18)
Determining Whether a Path Exists
753(1)
Graphs with Weighted Edges
754(1)
Shortest-Distance Algorithm
755(10)
Shortest-Path Algorithm
765(1)
Self-Test Exercises for Section 15.4
766(1)
Chapter Summary
767(1)
Solutions to Self-Test Exercises
767(1)
Programming Projects
768(3)
Appendixes
A. ASCII Character Set
771(1)
B. Further Big-O Notation
772(2)
C. Precedence of Operators
774(1)
D. Command Line Compiling and Linking
775(3)
E. Dealing with Older Compilers
778(2)
F. Input and Output in C++
780(8)
G. Selected Library Functions
788(3)
H. Brief Reference for the Standard Template Classes
791(8)
I. A Toolkit of Useful Functions
799(3)
J. Fundamental Style Guide
802(1)
K. Downloading the GNU Compiler and Software
803(1)
L. Exception Handling
804(5)
Index 809

An electronic version of this book is available through VitalSource.

This book is viewable on PC, Mac, iPhone, iPad, iPod Touch, and most smartphones.

By purchasing, you will be able to view this book online, as well as download it, for the chosen number of days.

Digital License

You are licensing a digital product for a set duration. Durations are set forth in the product description, with "Lifetime" typically meaning five (5) years of online access and permanent download to a supported device. All licenses are non-transferable.

More details can be found here.

A downloadable version of this book is available through the eCampus Reader or compatible Adobe readers.

Applications are available on iOS, Android, PC, Mac, and Windows Mobile platforms.

Please view the compatibility matrix prior to purchase.