Data structures and other objects using c++

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.
The Standard Library and the Standard Namespace.
Use Assert to Check a Precondition.
Use Const Declarations.
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.
How to Debug.

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.
Style for Boolean Values.
Constructors.
The Throttle's Constructor.
What Happens If You Write a Class with No Constructors?
Always Provide Constructors.
Programming Tip: Revising the Throttle's Member Functions.
Programming Tip: Inline Member Functions.
When to Use an Inline Member Function.
Programming Tip: Self-Test Exercises.
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.
Document the Value Semantics.
The Implementation File.
Using a Namespace.
Never Put a Using Statement Actually in a Header File.
Classes and Parameters.
The Point Class.
Default Arguments.
A Default Constructor Can Be Provided by Using Default Arguments.
Parameters.
Using a Wrong Argument Type for a Reference Parameter.
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.
When to Use a Friend Function.
The Point Class—Putting Things Together.
Summary of Operator Overloading.

The Bag Class.
The Bag Class—Specification.
Typedef Statements within a Class Definition.
The std:: si ze_t Data Type.
Static Member Constants.
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.
The value_type Type Must Have a Default Constructor.
The Invariant of an Class.
The Bag Class—Implementation.
When to Use the Full Type Name bag::size_type.
Make Assertions Meaningful.
The Copy Function from the C++ Standard Library.
The Bag Class—Putting the Pieces Together.
Document the Class Invariant in the Implementation File.
The Bag Class—Testing.
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 ClassDocumentation.
The Sequence Class—Design.
The Sequence Class—Pseudocode for the Implementation.
Interactive Test Programs.
Converting Input to Upper-Case Letters.
The Switch Statement.

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_al l oC Exception.
The de1ete Operator.
Define Pointer Types.
Programming Tip:Self-Test Exercises.
Pointers and Arrays as Parameters.
Using a Dynamic Array.
The Bag Class with a Dynamic Array.
Pointer Member Variables.
Member Functions Allocate Dynamic Memory as Needed.
Provide Documentation about Possible Dynamic Memory Failure.
Value Semantics.
The Destructor.
The Revised Bag Class—Class Definition.
The Revised Bag Class—Implementation.
How to Check for Self-Assignment.
How to Allocate Memory in a Member Function.
The Revised Bag Class—Putting the Pieces Together.
SelfTest Exercises.
A Prescription for a Dynamic Class.
Four Rules.
Special Importance of the Copy Constructor.
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.
Using = and == with Strings.
The strcpy Function.
The strcat Function.
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.

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.
Pointers to Constant Nodes.
A Rule for a Node's Const Member Functions.
Providing Both a Const Version and a Non-const Version of a Function.
Dereferencing the Null Pointer.
A Linked List Toolkit.
Linked List Toolkit—Header File.
Computing the Length of a Linked List.
How to Traverse a Linked List.
Forgetting to Test the Empty List.
Parameters for Linked Lists.
Inserting a New Node That Is Not at the Head.
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.
The Assignment Operator Causes Trouble with Linked Lists.
How to Choose Between Different Approaches.
The Third Bag Class—Putting the Pieces Together.
A 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.

Template Functions.
Syntax for a Template Function.
Capitalize the Name of a Template Parameter.
Using a Template Function.
Failed Unification Errors.
A Template Function to Swap Two Values.
Swap, Max and Min Functions.
Parameter Matching for Template Functions.
A Template Function to Find the Biggest Item in an Array.
Mismatches for Template Function Arguments.
A Template Function to Insert an Item into a Sorted Array.
Template Classes.
Syntax for a Template Class.
Do Not Place Using Directives in a Template Implementation.
Use the name Item and the Typename Keyword.
More about the Template Implementation File.
Parameter Matching for Member Functions of Template Classes.
Implement the typedef Version First.
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.
Do Not Access an Iterator's Item after Reaching end().
Testing Iterators for Equality.
Other Multiset Operations.
Invalid Iterators.
Changing a Container Object Can Invalidate Its Iterators.
Const Iterators.
Standard Categories of Iterators.
Iterators for Arrays.
The Node Template Class with an Iterator.
Use Item instead of node :: value_type.
Functions That Return a Reference Type.
What Happens When a Reference Return Value is Copied Elsewhere.
The Data Member Function Now Requres 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.
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.
"++p" Is More Efficient Than "p++".
Iterators for Constant Collections.
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.

Introduction to Stacks.
The Standard Library Stack Class.
Reversing a Word.
Stack Applications.
Balanced Parentheses.
Evaluating Arithmetic Expressions.
Evaluating Arithmetic Expressions—Specification.
Evaluating Arithmetic Expressions—Design.
Evaluating Arithmetic ExpressionsImplementation.
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.
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.

Introduction to Queues.
The Standard Library Queue Class.
Uses for Queues.
Queue Applications.
Recognizing Palindromes.
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.
Use Small Helper Functions to Improve Clarity.
Discussion of the Circular Array Implementation of a Queue.
Linked List Implementation of a Queue.
Make Note of "Don't Care" Situations.
Forgetting Which End Is Which.
Priority Queues.
How the Priorities Are Specified.
The Standard Library Priority Queue Class.
Priority Queue ClassImplementation Ideas.
Reference Return Values for the Stack, Queue, and Priority Queue Classes.

Recursive Functions.
A First Example of Recursive Thinking.
Tracing Recursive Calls.
An Extension of write_vertical.
A Closer Look at Recursion.
General Form of a Successful Recursive Function.
Studies of Recursion: Fractals and Mazes.
Generating Random Fractals.
A Function for Generating Random Fractals—Specification.
Design and Implementation of the Fractal Function.
How the Random Fractals Are Displayed.
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.

Introduction to Trees.
Binary Trees.
Binary Taxonomy Trees.
General Trees.
Tree Representations.
Array Representation of Complete Binary Trees.
Representing a Binary Tree with a Struct for Nodes.
Binary Tree Nodes.
Not Connecting All the Links.
Animal Guessing.
Animal Guessing Program—Design and Implementation.
Animal Guessing Program—Improvements.
Tree Traversals.
Traversals of Binary Trees.
A Useful Backward In-Order Traversal.
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.

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.
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.

Serial Search and Binary Search.
Serial Search.
Serial Search—Analysis.
Binary Search.
Binary Search—Design.
Common Indexing Errors in Binary Search Implementations.
Binary Search—Analysis.
0pen-Address Hashing.
Introduction to Hashing.
The Table Class—Specification.
The Table Class—Design.
Using Si ze_type Can Indicate a Value's Purpose.
The Table ADT-Implementation.
Inline Functions in the Implementation File.
Choosing a Hash Function to Reduce Collisions.
Double Hashing to Reduce Clustering.
Chained Hashing.
Analysis of Hashing.
The Load Factor of a Hash Table.

Quadratic Sorting Algorithms.
Selectionsort—Specification.
Selectionsort Design.
Selectionsort—Implementation.
Selectionsort—Analysis.
Rough Estimates Suffice for Big-O.
Insertionsort.
Insertionsort—Analysis.
Recursive Sorting Algorithms.
Divide-and-Conquer Using Recursion.
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.

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.
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.
Heap Warnings.
Virtual Methods and a Game Engine.
Introduction to the Game Engine.
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 Engine.
The Game Engine's Play Algorithm with Minimax.
Further Reading.

Graph Definitions.
Undirected Graphs.
Undirected State Graphs.
Directed Graphs.
More Graph Terminology.
Airline Routes Example.
SelfTest Exercises.
Graph Implementations.
Representing Graphs with an Adjacency Matrix.
Using a TwoDimensional Array to Store an Adjacency Matrix.
Representing Graphs with Edge Lists.
Representing Graphs with Edge Sets.
Which Representation 1s Best?
Labeled Graph Class.
Member Functions to Add Vertices and Edges.
Labeled Graph Class—Overloading the Subscript Operator.
Labeled Graph Class—Neighbors Function.
Labeled Graph ADT-Implementation.
Graph Traversals.
Depth-First Search.
Breadth-First Search.
Depth-First Search—Implementation.
BreadthFirst Search—Implementation.
Path Algorithms.
Determining Whether a Path Exists.
Graphs with Weighted Edges.
Shortest Distance Algorithm.
Shortest Path Algorithm.