Data Structures and Other Objects Using C++

by Main, Michael; Savitch, Walter

• ISBN13: 9780321197160
• ISBN10: 032119716X
• Edition: 4th
• Format: Paperback
• Copyright: 2011-01-01
• Publisher: Addison Wesley

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