Data Structures and Other Objects Using C++

Michael Main is an Associate Professor of Computer Science at the University of Colorado at Boulder. As a chairman of the undergraduate committee, he participated in the University's development and implementation of the Bachelor's of Science degree in Computer Science. Recognized as gifted teacher of undergraduates, he has incorporated many of his innovative teaching techniques into his Addison-Wesley textbooks. Walt Savitch is a Professor of Computer Science at the University of California at San Diego, where he has been one of the main designers of the computer science curriculum. A well-known and respected author, he has written widely on complexity theory and on computational linguistics, and published a textbook on computability theory. 0201702975AB04062001

(Most chapters contains "Chapter Summary", "Self-Test Exercises", "Solutions to Self-Test Exercises" and "Programming Projects".)

1. The Phases of Software Development 1.


Specification, Design, Implementation.



Design Technique: Decomposing the Problem.



Preconditions and Postconditions.



Using Functions Provided by Other Programmers.



Implementation Issues for the ANSI/ISO C++ Standard.



C++ Feature: The Standard Library and the Standard Namespace.



Programming Tip: Use Declared Constants.



Programming Tip: Use Assert to Check a Precondition.



Programming Tip: Use EXIT_SUCCESS in a Main Program.



Running Time Analysis.



The Stair-Counting Problem.



Big-O Notation.



Time Analysis of C++ Functions.



Worst-case, Average-case, and Best-case Analyses.



Testing and Debugging.



Choosing Test Data.



Boundary Values.



Fully Exercising Code.



Debugging.



Programming Tip: How to Debug?



2. Abstract Data Types and C++ Classes.


Classes and Members.



The Throttle Class.



Using a Class.



A Small Demonstration Program for the Throttle Class.



Implementing Member Functions.



Member Functions May Activate Other Members.



Programming Tip: Style for Boolean Values.



Constructors.



The Throttle's Constructor.



What Happens If You Write a Class with No Constructors?



Programming Tip: Always Provide Constructors.



Revising the Throttle's Member Functions.



Inline Member Functions.



Programming Tip: When to Use an Inline Member Function.



Using a Namespace, Header File, and Implementation File.



Creating a Namespace.



The Header File.



Describing the Value Semantics of a Class within the Header File.



Programming Tip: Document the Value Semantics.



The Implementation File.



Using the Items in a Namespace.



Pitfall: Never Put a Using Statement Actually in a Header File.



Classes and Parameters.



The Point Class.



Default Arguments.



Programming Tip: A Default Constructor Can Be Provided by Using Default Arguments.



Parameters.



Pitfall: Using a Wrong Argument Type for a Reference Parameter.



Programming Tip: Use const Consistently.



When the Type of a Function's Return Value is a Class.



Operator Overloading.



Overloading Binary Comparison Operators.



Overloading Binary Arithmetic Operators.



Overloading Output and Input Operators.



Friend Functions.



Programming Tip: When to Use a Friend Function.



The Point Class—Putting Things Together.



Summary of Operator Overloading.



3. Container Classes.


The Bag Class.



The Bag Class—Specification.



C++ Feature: Typedef Statements within a Class Definition.



C++ Feature: The std:: size_t Data Type.



Older Compilers Do Not Support Initialization of Static Member Constants.



The Bag Class—Documentation.



Documenting the Value Semantics.



The Bag Class—Demonstration Program.



The Bag Class—Design.



Pitfall: The value_type Type Must Have a Default Constructor.



The Invariant of an Class.



The Bag Class—Implementation.



Pitfall: When to Use the Full Type Name bag::size_type.



Programming Tip: Make Assertions Meaningful.



C++ Feature: The Copy Function from the C++ Standard Library.



The Bag Class—Putting the Pieces Together.



Programming Tip: Document the Class Invariant in the Implementation File.



The Bag Class—Testing.



Pitfall: An Object Can Be an Argument to Its Own Member Function.



The Bag Class—Analysis.



Programming Project: The Sequence Class.



The Sequence Class—Specification.



The Sequence Class—Documentation.



The Sequence Class—Design.



The Sequence Class—Pseudocode for the Implementation.



Interactive Test Programs.



C++ Feature: Converting Input to Uppercase Letters.



C++ Feature: The Switch Statement.



4. Pointers and Dynamic Arrays.


Pointers and Dynamic Memory.



Pointer Variables.



Using the Assignment Operator with Pointers.



Dynamic Variables and the New Operator.



Using New to Allocate Dynamic Arrays.



The Heap and the Bad_alloc Exception.



The delete Operator.



Programming Tip: Define Pointer Types.



Pointers and Arrays as Parameters.



Programming Tip: Using a Dynamic Array.



The Bag Class with a Dynamic Array.



Pointer Member Variables.



Member Functions Allocate Dynamic Memory as Needed.



Programming Tip: Provide Documentation about Possible Dynamic Memory Failure.



Value Semantics.



The Destructor.



The Revised Bag Class—Class Definition.



The Revised Bag Class—Implementation.



Programming Tip: How to Check for Self-Assignment.



Programming Tip: How to Allocate Memory in a Member Function.



The Revised Bag Class—Putting the Pieces Together.



Prescription for a Dynamic Class.



Four Rules.



Special Importance of the Copy Constructor.



Pitfall: Using Dynamic Memory Requires a Destructor, a Copy Constructor, and an Overloaded Assignment Operator.



Programming Project: The String Class.



Null-Terminated Strings.



Initializing a String Variable.



The Empty String.



Reading and Writing String Variables.



Pitfall: Using = and == with Strings.



The strcpy Function.



The strcat Function.



Pitfall: Dangers of strcpy, strcat, and Reading Strings.



The strlen Function.



The strcmp Function.



The String Class—Specification.



Constructor for the String Class.



Overloading the operator[ ].



Some Further Overloading.



Other Operations for the String Class.



The String Class—Design.



The String Class—Implementation.



Demonstration Program for the String Class.



Chaining the Output Operator.



Declaring Constant Objects.



Constructor-Generated Conversions.



Using Overloaded Operations in Expressions.



Our String Class Versus the C++ Library String Class.



Programming Project: The Polynomial.



5. Linked Lists.


A Fundamental Node Class for Linked Lists.



Declaring a Class for Nodes.



Using a Typedef Statement with Linked List Nodes.



Head Pointers, Tail Pointers.



The Null Pointer.



The Meaning of a Null Head Pointer or Tail Pointer.



The Node Constructor.



The Node Member Functions.



The Member Selection Operator.



The Const Keyword with a Pointer to a Node, and the Need for Two Versions of Some Member Functions.



Programming Tip: A Rule for a Node's Constant Member Functions.



Pitfall: Dereferencing the Null Pointer.



A Linked List Toolkit.



Linked List Toolkit—Header File.



Computing the Length of a Linked List.



Programming Tip: How to Traverse a Linked List.



Pitfall: Forgetting to Test the Empty List.



Parameters for Linked Lists.



Inserting a New Node at the Head of a Linked List.



Inserting a New Node That is Not at the Head.



Pitfall: Unintended Calls to delete and new.



Finding a Node by Its Position in a Linked List.



Copying a Linked List.



Removing a Node at the Head of a Linked List.



Removing a Node That Is Not at the Head.



Clearing a Linked List.



Linked List Toolkit—Putting the Pieces Together.



Using the Linked List Toolkit.



The Bag Class with a Linked List.



Our Third Bag—Specification.



Our Third Bag—Class Definition.



How to Make the Bag value_type Match the Node value_type.



Following the Rules for Dynamic Memory Usage in a Class.



The Third Bag Class—Implementation.



Pitfall: The Assignment Operator Causes Trouble with Linked Lists.



Programming Tip: How to Choose Between Different Approaches.



The Third Bag Class—Putting the Pieces Together.



Programming Project: The Sequence Class with a Linked List.



The Revised Sequence Class—Design Suggestions.



The Revised Sequence Class—Value Semantics.



Dynamic Arrays vs. Linked Lists vs. Doubly Linked lists.



Making the Decision.



6. Software Development with Templates, Iterators, and the Standard Library.


Template Functions.



Syntax for a Template Function.



Programming Tip: Capitalize the Name of a Template Parameter.



Using a Template Function.



Pitfall: Failed Unification Errors.



A Template Function to Swap Two Values.



C++ Feature: Swap, Max and Min Functions.



Parameter Matching for Template Functions.



A Template Function to Find the Biggest Item in an Array.



Pitfall: Mismatches for Template Function Arguments.



A Template Function to Insert an Item into a Sorted Array.



Template Classes.



Syntax for a Template Class.



Programming Tip: Use the name Item and the Typename Keyword.



Pitfall: Do Not Place Using Directives in a Template Implementation.



More about the Template Implementation File.



Parameter Matching for Member Functions of Template Classes.



Using the Template Class.



Details of the Story-Writing Program.



The Standard Template Classes and Their Iterators.



The Multiset Template Class.



Some Multiset Members.



Iterators and the [...) Pattern.



Pitfall: Do Not Access an Iterator's Item after Reaching end().



Testing Iterators for Equality.



Other Multiset Operations.



Invalid Iterators.



Pitfall: Changing a Container Object Can Invalidate Its Iterators.



Const Iterators.



Standard Categories of Iterators.



Iterators for Arrays.



The Node Template Class.



Functions That Return a Reference Type.



What Happens When a Reference Return Value is Copied Elsewhere.



The Data Member Function Now Requires Two Versions.



Header and Implementation Files for the New Node.



An Iterator for Linked Lists.



The Node Iterator.



The Node Iterator is Derived from std::iterator.



Pitfall: Std::iterator Might Not Exist.



The Node Iterator's Private Member Variable.



Node Iterator—Constructor.



Node lterator—The *Operator.



Node Iterator—Two Versions of the ++ Operator.



Programming Tip: "++p" Is More Efficient Than "p++".



Iterators for Constant Collections.



Programming Tip: When to Use a Const Iterator.



Linked List Version of the Bag Template Class with an Iterator.



How to Provide an Iterator for a Container Class That You Write.



The Bag Iterator.



Why the Iterator Is Defined Inside the Bag.



7. Stacks.


Introduction to Stacks and the STL Stack.



The Standard Library Stack Class.



Programming Example: Reversing a Word.



Stack Applications.



Programming Example: Balanced Parentheses.



Programming Example: Evaluating Arithmetic Expressions.



Evaluating Arithmetic Expressions—Specification.



Evaluating Arithmetic Expressions—Design.



Evaluating Arithmetic Expressions—Implementation.



Functions Used in the Calculator Program.



Evaluating Arithmetic Expressions—Testing and Analysis.



Evaluating Arithmetic Expressions—Enhancements.



Implementations of the Stack Class.



Array Implementation of a Stack.



Linked List Implementation of a Stack.



The Koenig Lookup.



More Complex Stack. Applications.



Evaluating Postfix Expressions.



Translating Infix to Postfix Notation.



Using Precedence Rules in the Infix Expression.



Correctness of the Conversion from Infix to Postfix.



8. Queues.


Introduction to Queues and the STL Queue..



The Standard Library Queue Class.



Uses for Queues.



Queue Applications.



Programming Example: Recognizing Palindromes.



Programming Example: Car Wash Simulation.



Car Wash Simulation—Specification.



Car Wash Simulation—Design.



Car Wash Simulation—Implementing the Car Wash Classes.



Car Wash Simulation—Implementing the Simulation Function.



Implementations of the Queue Class.



Array Implementation of a Queue.



Programming Tip: Use Small Helper Functions to Improve Clarity.



Discussion of the Circular Array Implementation of a Queue.



Linked List Implementation of a Queue.



Programming Tip: Make Note of "Don't Care" Situations.



Pitfall: Forgetting Which End Is Which.



Priority Queues.



How the Priorities Are Specified.



The Standard Library Priority Queue Class.



Priority Queue Class—Implementation Ideas.



Reference Return Values for the Stack, Queue, and Priority Queue Classes.



9. Recursive Thinking.


Recursive Functions.



A First Example of Recursive Thinking.



Tracing Recursive Calls.



Programming Example: An Extension of write_vertical.



A Closer Look at Recursion.



General Form of a Successful Recursive Function.



Studies of Recursion: Fractals and Mazes.



Programming Example: Generating Random Fractals.



A Function for Generating Random Fractals—Specification.



Design and Implementation of the Fractal Function.



How the Random Fractals Are Displayed.



Programming Example: Traversing a Maze.



Traversing a Maze—Specification.



Traversing a Maze—Design.



Traversing a Maze—Implementation.



Reasoning about Recursion.



How to Ensure That There is No Infinite Recursion.



Inductive Reasoning about the Correctness of a Recursive Function.



10. Trees.


Introduction to Trees.



Binary Trees.



Binary Taxonomy Trees.



General Trees.



Tree Representations.



Array Representation of Complete Binary Trees.



Representing a Binary Tree with a Class for Nodes.



Binary Tree Nodes.



Pitfall: Not Connecting All the Links.



Programming Example: Animal Guessing.



Animal Guessing Program—Design and Implementation.



Animal Guessing Program—Improvements.



Tree Traversals.



Traversals of Binary Trees.



A Useful Backward In-Order Traversal.



Programming Tip: Quick and Easy Printing of a Tree.



The Problem with Our Traversals.



A Parameter Can Be a Function.



A Template Version of the apply Function.



More Generality for the apply Template Function.



Template Functions for Tree Traversals.



Binary Search Trees.



The Binary Search Tree Storage Rules.



Our Sixth Bag—Class Definition.



Our Sixth Bag—Implementation of Some Simple Functions.



Counting the Occurrences of an Item in a Binary Search Tree.



Inserting a New Item into a Binary Search Tree.



Removing an Item from a Binary Search Tree.



The Union Operators for Binary Search Trees.



Time Analysis and an Internal Iterator.



11. Tree Projects.


Heaps.



The Heap Storage Rules.



The Priority Queue ADT with Heaps.



Adding an Entry to a Heap.



Removing an Entry from a Heap.



B-Trees.



The Problem of Unbalanced Trees.



The B-tree Rules.



An Example B-Tree.



The Set ADT with B-trees.



Searching for an Item In a B-tree.



Inserting an Item into a B-tree.



The Loose Insertion into a B-tree.



A Private Member Function to Fix an Excess in a Child.



Back to the Insert Member Function.



Employing Top-Down Design.



Removing an Item from a B-tree.



The Loose Erase from a B-tree.



A Private Member Function to Fix a Shortage in a Child.



Removing the Biggest Item from a B-tree.



Programming Tip: Write and Test Small Pieces.



External B-trees.



Trees, Logs, and Time Analysis.



Time Analysis for Binary Search Trees.



Time Analysis for Heaps.



Logarithms.



Logarithmic Algorithms.



12. Searching.


Serial Search and Binary Search.



Serial Search.



Serial Search—Analysis.



Binary Search.



Binary Search—Design.



Pitfall: Common Indexing Errors in Binary Search Implementations.



Binary Search—Analysis.



0pen-Address Hashing.



Introduction to Hashing.



The Table Class—Specification.



The Table Class—Design.



Programming Tip: Using Size_t Can Indicate a Value's Purpose.



The Table ADT-Implementation.



C++Feature: Inline Functions in the Implementation File.



Choosing a Hash Function to Reduce Collisions.



Double Hashing to Reduce Clustering.



Chained Hashing.



Time Analysis of Hashing.



The Load Factor of a Hash Table.



13. Sorting.


Quadratic Sorting Algorithms.



Selectionsort—Specification.



Selectionsort— Design.



Selectionsort—Implementation.



Selectionsort—Analysis.



Programming Tip: Rough Estimates Suffice for Big-O.



Insertionsort.



Insertionsort—Analysis.



Recursive Sorting Algorithms.



Divide-and-Conquer Using Recursion.



C++ Feature: Specifying a Subarray with Pointer Arithmetic.



Mergesort.



The Merge Function.



Dynamic Memory Usage in Mergesort.



Mergesort—Analysis.



Mergesort for Files.



Quicksort.



The Partition Function.



Quicksort—Analysis.



Quicksort—Choosing a Good Pivot Element.



An O(n log n) Algorithm Using a Heap.



Heapsort.



Making the Heap.



Reheapification Downward.



Heapsort—Analysis.



A Standard Library Sorting Functions.



The C++ Sort Function.



The Original C Version of qsort.



14.Derived Classes and Inheritance.


Derived Classes.



How to Declare a Derived Class.



The Automatic Constructors of a Derived Class.



Using a Derived Class.



The Automatic Assignment Operator for a Derived Class.



The Automatic Destructor of a Derived Class.



Overriding Inherited Member Functions.



Programming Tip: Make the Overriding Function Call the Original.



Simulation of an Ecosystem.



Implementing Part of the Organism Object Hierarchy.



The Organism Class.



The Animal Class: A Derived Class with New Private Member Variables.



How to Provide a New Constructor for a Derived Class.



The Other Animal Member Functions.



The Herbivore Class.



The Pond Life Simulation Program.



Pondlife—Implementation Details.



Using the Pond Model.



Dynamic Memory Usage.



Virtual Member Functions and a Game Glass.



Introduction to the Game Class.



Protected Members.



Virtual Member Functions.



Virtual Destructors.



The Protected Virtual Member Functions of the Game Engine.



A Derived Class to Play Connect Four.



The Private Member Variables of the Connect Four Class.



The Connect Four Constructor and Restart Function.



Three Connect Four Functions That Deal with the Game's Status.



Three Connect Four Functions That Deal with Moves.



The Clone Function.



Writing Your Own Derived Games from the Game Class.



The Game Class Play Algorithm with Minimax.



Further Reading.



15. Graphs.


Graph Definitions.



Undirected Graphs.



Programming Example: Undirected State Graphs.



Directed Graphs.



More Graph Terminology.



Airline Routes Example.



Graph Implementations.



Representing Graphs with an Adjacency Matrix.



Using a Two-Dimensional Array to Store an Adjacency Matrix.



Representing Graphs with Edge Lists.



Representing Graphs with Edge Sets.



Which Representation is Best?



Programming Example: Labeled Graph Class.



Member Functions to Add Vertices and Edges.



Labeled Graph Class—Overloading the Subscript Operator.



A Const Version of the Subscript Operator.



Labeled Graph Class—Neighbors Function.



Labeled Graph ADT—Implementation.



Graph Traversals.



Depth-First Search.



Breadth-First Search.



Depth-First Search—Implementation.



Breadth-First Search—Implementation.



Path Algorithms.



Determining Whether a Path Exists.



Graphs with Weighted Edges.



Shortest Distance Algorithm.



Shortest Path Algorithm.



Appendix A. ASCI CHARACTER SET.


Appendix B. FURTHER BIG-O NOTATION.


Appendix C. PRECEDENCE OF OPERATORS.


Appendix D. COMPILING, LINKING, AND RUNNING PROGRAMS.


Appendix E. DEALING WITH OLDER COMPILERS.


Appendix F. INPUT AND OUTPUT IN C++.


Appendix G. SELECTED LIBRARY FUNCTIONS.


Appendix H. BRIEF REFERENCE FOR THE STANDARD TEMPLATE CLASSES.


Appendix I. A TOOLKIT OF USEFUL FUNCTIONS.


Appendix J. FUNDAMENTAL STYLE GUIDE.


Appendix K. DOWNLOADING THE GNU COMPILER AND SOFTWARE.


Index.