## Table of Contents

1: Introduction to Computers, Programs, and C++

1: Objectives

1.1: Introduction

1.2: What Is a Computer?

1.3: Programming Languages

1.4: Operating Systems

1.5: History of C++

1.6: A Simple C++ Program

1.7: C++ Program-Development Cycle

1.8: Programming Style and Documentation

1.9: Programming Errors

Key Terms: Chapter 1

Chapter Summary: Chapter 1

Programming Exercises From the Book: Chapter 1

2: Elementary Programming

2: Objectives

2.1: Introduction

2.2: Writing a Simple Program

2.3: Reading Input from the Keyboard

2.4: Identifiers

2.5: Variables

2.6: Assignment Statements and Assignment Expressions

2.7: Named Constants

2.8: Numeric Data Types and Operations

2.9: Evaluating Expressions and Operator Precedence

2.10: Case Study: Displaying the Current Time

2.11: Augmented Assignment Operators

2.12: Increment and Decrement Operators

2.13: Numeric Type Conversions

2.14: Software Development Process

2.15: Case Study: Counting Monetary Units

2.16: Common Errors

Key Terms: Chapter 2

Chapter Summary: Chapter 2

Programming Exercises From the Book: Chapter 2

3: Selections

3: Objectives

3.1: Introduction

3.2: The bool Data Type

3.3: if Statements

3.4: Two-Way if-else Statements

3.5: Nested if and Multi-Way if-else Statements

3.6: Common Errors and Pitfalls

3.7: Case Study: Computing Body Mass Index

3.8: Case Study: Computing Taxes

3.9: Generating Random Numbers

3.10: Logical Operators

3.11: Case Study: Determining Leap Year

3.12: Case Study: Lottery

3.13: switch Statements

3.14: Conditional Operators

3.15: Operator Precedence and Associativity

3.16: Debugging

Key Terms: Chapter 3

Chapter Summary: Chapter 3

Programming Exercises From the Book: Chapter 3

4: Mathematical Functions, Characters, and Strings

4: Objectives

4.1: Introduction

4.2: Mathematical Functions

4.3: Character Data Type and Operations

4.4: Case Study: Generating Random Characters

4.5: Case Study: Guessing Birthdays

4.6: Character Functions

4.7: Case Study: Converting a Hexadecimal Digit to a Decimal Value

4.8: The string Type

4.9: Case Study: Revising the Lottery Program Using Strings

4.10: Formatting Console Output

4.11: Simple File Input and Output

Key Terms: Chapter 4

Chapter Summary: Chapter 4

Programming Exercises From the Book: Chapter 4

5: Loops

5: Objectives

5.1: Introduction

5.2: The while Loop

5.3: Case Study: Guessing Numbers

5.4: Loop Design Strategies

5.5: Controlling a Loop with User Confirmation

5.6: Input and Output Redirections and Read All Data from a File

5.7: The do-while Loop

5.8: The for Loop

5.9: Which Loop to Use?

5.10: Nested Loops

5.11: Minimizing Numeric Errors

5.12: Case Studies

5.13: Keywords break and continue

5.14: Case Study: Checking Palindromes

5.15: Case Study: Displaying Prime Numbers

Key Terms: Chapter 5

Chapter Summary: Chapter 5

Programming Exercises From the Book: Chapter 5

6: Functions

6: Objectives

6.1: Introduction

6.2: Defining a Function

6.3: Calling a Function

6.4: void Functions

6.5: Passing Arguments by Value

6.6: Modularizing Code

6.7: Overloading Functions

6.8: Function Prototypes

6.9: Default Arguments

6.10: Inline Functions

6.11: Local, Global, and Static Local Variables

6.12: Passing Arguments by Reference

6.13: Constant Reference Parameters

6.14: Case Study: Converting Hexadecimals to Decimals

6.15: Function Abstraction and Stepwise Refinement

Key Terms: Chapter 6

Chapter Summary: Chapter 6

Programming Exercises From the Book: Chapter 6

7: Single-Dimensional Arrays and C-Strings

7: Objectives

7.1: Introduction

7.2: Array Basics

7.3: Case Study: Analyzing Numbers

7.4: Case Study: Deck of Cards

7.5: Passing Arrays to Functions

7.6: Preventing Changes of Array Arguments in Functions

7.7: Returning Arrays from Functions

7.8: Case Study: Counting the Occurrences of Each Letter

7.9: Searching Arrays

7.10: Sorting Arrays

7.11: C-Strings

7.12: Converting Numbers to Strings

Key Terms: Chapter 7

Chapter Summary: Chapter 7

Programming Exercises From the Book: Chapter 7

8: Multidimensional Arrays

8: Objectives

8.1: Introduction

8.2: Declaring Two-Dimensional Arrays

8.3: Processing Two-Dimensional Arrays

8.4: Passing Two-Dimensional Arrays to Functions

8.5: Case Study: Grading a Multiple-Choice Test

8.6: Case Study: Finding a Closest Pair

8.7: Case Study: Sudoku

8.8: Multidimensional Arrays

Key Terms: Chapter 8

Chapter Summary: Chapter 8

Programming Exercises From the Book: Chapter 8

9: Objects and Classes

9: Objectives

9.1: Introduction

9.2: Defining Classes for Objects

9.3: Example: Defining Classes and Creating Objects

9.4: Constructors

9.5: Constructing and Using Objects

9.6: Separating Class Definition from Implementation

9.7: Preventing Multiple Inclusions

9.8: Inline Functions in Classes

9.9: Data Field Encapsulation

9.10: The Scope of Variables

9.11: Class Abstraction and Encapsulation

Key Terms: Chapter 9

Chapter Summary: Chapter 9

Programming Exercises From the Book: Chapter 9

10: Object-Oriented Thinking

10: Objectives

10.1: Introduction

10.2: The string Class

10.3: Passing Objects to Functions

10.4: Array of Objects

10.5: Instance and Static Members

10.6: Constant Member Functions

10.7: Thinking in Objects

10.8: Class Relationships

10.9: Case Study: The StackOfIntegers Class

10.10: Constructor Initializer Lists

10.11: Class Design Guidelines

Key Terms: Chapter 10

Chapter Summary: Chapter 10

Programming Exercises From the Book: Chapter 10

11: Pointers and Dynamic Memory Management

11: Objectives

11.1: Introduction

11.2: Pointer Basics

11.3: Defining Synonymous Types Using the typedef Keyword

11.4: Using const with Pointers

11.5: Arrays and Pointers

11.6: Passing Pointer Arguments in a Function Call

11.7: Returning a Pointer from Functions

11.8: Useful Array Functions

11.9: Dynamic Persistent Memory Allocation

11.10: Creating and Accessing Dynamic Objects

11.11: The this Pointer

11.12: Destructors

11.13: Case Study: The Course Class

11.14: Copy Constructors

11.15: Customizing Copy Constructors

Key Terms: Chapter 11

Chapter Summary: Chapter 11

Chapter 11 Programming Project

Programming Exercises From the Book: Chapter 11

12: Templates, Vectors, and Stacks

12: Objectives

12.1: Introduction

12.2: Templates Basics

12.3: Example: A Generic Sort

12.4: Class Templates

12.5: Improving the Stack Class

12.6: The C++ vector Class

12.7: Insertion and Deletion and Other Functions for a Vector

12.8: Replacing Arrays Using the vector Class

12.9: Case Study: Evaluating Expressions

12.10: Using Smart Pointers for Automatic Object Destruction

Key Terms: Chapter 12

Chapter Summary: Chapter 12

Programming Exercises From the Book: Chapter 12

13: File Input and Output

13: Objectives

13.1: Introduction

13.2: Text I/O

13.3: Formatting Output

13.4: Functions: getline, get, and put

13.5: fstream and File Open Modes

13.6: Testing Stream States

13.7: Binary I/O

13.8: Random Access File

13.9: Updating Files

Key Terms: Chapter 13

Chapter Summary: Chapter 13

Programming Exercises From the Book: Chapter 13

14: Operator Overloading

14: Objectives

14.1: Introduction

14.2: The Rational Class

14.3: Operator Functions

14.4: Overloading the Subscript Operator []

14.5: Overloading Augmented Assignment Operators

14.6: Overloading the Unary Operators

14.7: Overloading the ++ and —— Operators

14.8: friend Functions and friend Classes

14.9: Overloading the << and >> Operators

14.10: Automatic Type Conversions

14.11: Defining Nonmember Functions for Overloading Operators

14.12: The Rational Class with Overloaded Function Operators

14.13: Overloading the = Operators

Key Terms: Chapter 14

Chapter Summary: Chapter 14

Chapter 14 Programming Project

Programming Exercises From the Book: Chapter 14

15: Inheritance and Polymorphism

15: Objectives

15.1: Introduction

15.2: Base Classes and Derived Classes

15.3: Generic Programming

15.4: Constructors and Destructors

15.5: Redefining Functions

15.6: Polymorphism

15.7: Virtual Functions and Dynamic Binding

15.8: The C+11 override and final Keywords

15.9: The protected Keyword

15.10: Abstract Classes and Pure Virtual Functions

15.11: Casting: static_cast versus dynamic_cast

Key Terms: Chapter 15

Chapter Summary: Chapter 15

Chapter 15: Programing Project

Programming Exercises From the Book: Chapter 15

16: Exception Handling

16: Objectives

16.1: Introduction

16.2: Exception-Handling Overview

16.3: Exception Classes

16.4: Custom Exception Classes

16.5: Multiple Catches

16.6: Exception Propagation

16.7: Rethrowing Exceptions

16.8: Exception Specification

16.9: When to Use Exceptions

Key Terms: Chapter 16

Chapter Summary: Chapter 16

Programming Exercises From the Book: Chapter 16

17: Recursion

17: Objectives

17.1: Introduction

17.2: Example: Factorials

17.3: Case Study: Fibonacci Numbers

17.4: Problem Solving Using Recursion

17.5: Recursive Helper Functions

17.6: Towers of Hanoi

17.7: Eight Queens

17.8: Recursion versus Iteration

17.9: Tail Recursion

Key Terms: Chapter 17

Chapter Summary: Chapter 17

Programming Exercises From the Book: Chapter 17

18: Developing Efficient Algorithms

18: Objectives

18.1: Introduction

18.2: Measuring Algorithm Efficiency Using Big O Notation

18.3: Examples: Determining Big O

18.4: Analyzing Algorithm Time Complexity

18.5: Finding Fibonacci Numbers Using Dynamic Programming

18.6: Finding Greatest Common Divisors Using Euclid’s Algorithm

18.7: Efficient Algorithms for Finding Prime Numbers

18.8: Finding the Closest Pair of Points Using Divide-and-Conquer

18.9: Solving the Eight Queens Problem Using Backtracking

18.10: Case Studies: Finding a Convex Hull

Key Terms: Chapter 18

Chapter Summary: Chapter 18

Chapter 18 Programing Project 1

Chapter 18 Programing Project 2

Chapter 18 Programing Project 3

Programming Exercises From the Book: Chapter 18

19: Sorting

19: Objectives

19.1: Introduction

19.2: Insertion Sort

19.3: Bubble Sort

19.4: Merge Sort

19.5: Quick Sort

19.6: Heap Sort

19.7: Bucket Sort and Radix Sort

19.8: External Sort

Key Terms: Chapter 19

Chapter Summary: Chapter 19

Chapter 19 Programing Project

Programming Exercises From the Book: Chapter 19

20: Linked Lists, Queues, and Priority Queues

20: Objectives

20.1: Introduction

20.2: Nodes

20.3: The LinkedList Class

20.4: Implementing LinkedList

20.5: Iterators

20.6: C+11 Foreach Loop

20.7: Variations of Linked Lists

20.8: Queues

20.9: Priority Queues

Key Terms: Chapter 20

Chapter Summary: Chapter 20

Programming Exercises From the Book: Chapter 20

21: Binary Search Trees

21: Objectives

21.1: Introduction

21.2: Binary Search Trees

21.3: Deleting Elements in a BST

21.4: Iterators for BST

Key Terms: Chapter 21

Chapter Summary: Chapter 21

Programming Exercises From the Book: Chapter 21

22: STL Containers

22: Objectives

22.1: Introduction

22.2: STL Basics

22.3: STL Iterators

22.4: C+11 Auto-Type Inference

22.5: Sequence Containers

22.6: Associative Containers

22.7: Container Adapters

Key Terms: Chapter 22

Chapter Summary: Chapter 22

Programming Exercises From the Book: Chapter 22

23: STL Algorithms

23: Objectives

23.1: Introduction

23.2: Types of Algorithms

23.3: copy, copy_if, and copy_n

23.4: fill and fill_n

23.5: Passing Functions as Parameters

23.6: generate and generate_n

23.7: remove, remove_if, remove_copy, and remove_copy_if

23.8: replace, replace_if, replace_copy, and replace_copy_if

23.9: find, find_if, find_end, and find_first_of

23.10: search and search_n

23.11: sort and binary_search

23.12: adjacent_find, merge, and inplace_merge

23.13: reverse and reverse_copy

23.14: rotate and rotate_copy

23.15: swap, iter_swap, and swap_ranges

23.16: count and count_if

23.17: max_element and min_element

23.18: random_shuffle

23.19: for_each and transform

23.20: includes, set_union, set_difference, set_intersection, and set_symmetric_difference

23.21: accumulate, adjacent_difference, inner_product, and partial_sum

23.22: Lambda Expressions

23.23: New C++11 STL Algorithms

Key Terms: Chapter 23

Chapter Summary: Chapter 23

Programming Exercises From the Book: Chapter 23

24: Hashing

24: Objectives

24.1: Introduction

24.2: What Is Hashing?

24.3: Hash Functions and Hash Codes

24.4: Handling Collisions Using Open Addressing

24.5: Handling Collisions Using Separate Chaining

24.6: Load Factor and Rehashing

24.7: Implementing a Map Using Hashing

24.8: Implementing Set Using Hashing

Key Terms: Chapter 24

Chapter Summary: Chapter 24

Programming Exercises From the Book: Chapter 24

25: AVL Trees

25: Objectives

25.1: Introduction

25.2: Rebalancing Trees

25.3: Designing Classes for AVL Trees

25.4: Overriding the insert Function

25.5: Implementing Rotations

25.6: Implementing the remove Function

25.7: The AVLTree Class

25.8: Testing the AVLTree Class

25.9: AVL Tree Time Complexity Analysis

Key Terms: Chapter 25

Chapter Summary: Chapter 25

Programming Exercises From the Book: Chapter 25

26: Graphs and Applications

26: Objectives

26.1: Introduction

26.2: Basic Graph Terminologies

26.3: Representing Graphs

26.4: The Graph Class

26.5: Graph Traversals

26.6: Depth-First Search

26.7: Breadth-First Search

26.8: Case Study: The Nine Tail Problem

Key Terms: Chapter 26

Chapter Summary: Chapter 26

Programming Exercises From the Book: Chapter 26

27: Weighted Graphs and Applications

27: Objectives

27.1: Introduction

27.2: Representing Weighted Graphs

27.3: The WeightedGraph Class

27.4: Minimum Spanning Trees

27.5: Finding Shortest Paths

27.6: Case Study: The Weighted Nine Tail Problem

Key Terms: Chapter 27

Chapter Summary: Chapter 27

Programming Exercises From the Book: Chapter 27

Appendix A: C++ Keywords

Appendix B: The ASCII Character Set

Appendix C: Operator Precedence Chart

Appendix D: Number Systems

D.1: Introduction

D.2: Conversions Between Binary and Decimal Numbers

D.3: Conversions Between Hexadecimal and Decimal Numbers

D.4: Conversions Between Binary and Hexadecimal Numbers

Appendix E: Bitwise Operations

Appendix F: Using Command-Line Arguments

Appendix G: Enumerated Types

Appendix H: Regular Expressions

Symbol Index

Supplemental Materials

Solutions

Software Downloads

Errata

Part I: General Supplements

Part II: IDE Supplements

Part III: C++ Preprocessor

Part IV: Advanced C++ Topics

Part V: Legacy Topics

Part VI: Case Studies

Part VII: C++ Resources