Programming and Problem Solving with C++, Comprehensive, Sixth Edition

1 Overview of Programming and Problem Solving

1.1 Overview of Programming

What Is Programming?

How Do We Write a Program?

What Is an Algorithm?

What Is a Programming Language?

1.2 How Does a Computer Run a Program?

What Kinds of Instructions Can Be Written in a Programming Language?

What Is Software Maintenance?

Software Maintenance Case Study: An Introduction to Software Maintenance

1.3 What’s Inside the Computer?

1.4 Ethics and Responsibilities in the Computing Profession

Software Piracy

Privacy of Data

Use of Computer Resources

Software Engineering

1.5 Problem-Solving Techniques

Look for Things That Are Familiar

Solve by Analogy

Means-Ends Analysis

Divide and Conquer

The Building-Block Approach

Merging Solutions

Mental Blocks: The Fear of Starting

Algorithmic Problem Solving

Problem-Solving Case Study: Leap Year Algorithm

Quick Check Answers

Exam Preparation Exercises

Programming Warm-Up Exercises

Case Study Follow-Up

2 C++ Syntax and Semantics, and the Program Development Process

2.1 The Elements of C++ Programs

C++ Program Structure

Syntax and Semantics

Syntax Templates

Naming Program Elements: Identifiers

Data and Data Types

Naming Elements: Declarations

Taking Action: Executable Statements

Beyond Minimalism: Adding Comments to a Program

2.2 Program Construction

Blocks (Compound Statements)

The C++ Preprocessor

Software Maintenance Case Study: Adding Titles to Names

2.3 More About Output

Creating Blank Lines

Inserting Blanks Within a Line

Special Characters

2.4 Program Entry, Correction, and Execution

Entering a Program

Compiling and Running a Program

Problem-Solving Case Study: Printing a Chessboard

Testing and Debugging

Quick Check Answers

Exam Preparation Exercises

Programming Warm-Up Exercises

Programming Problems

Case Study Follow-Up

3 Numeric Types, Expressions, and Output

3.1 Overview of C++ Data Types

3.2 Numeric Data Types

Floating-Point Types

3.3 Declarations for Numeric Types

Named Constant Declarations

Variable Declarations

3.4 Simple Arithmetic Expressions

Arithmetic Operators

Increment and Decrement Operators

3.5 Compound Arithmetic Expressions

Precedence Rules

Type Coercion and Type Casting

Software Maintenance Case Study: Precedence Error

3.6 Function Calls and Library Functions

Value-Returning Functions

Library Functions

3.7 Formatting Output

Integers and Strings

Floating-Point Numbers

3.8 Additional string Operations

The length and size Functions

The find Function

The substr Function

Accessing Characters Within a String: The at Function

Converting to Lowercase and Uppercase

Problem-Solving Case Study: Mortgage Payment Calculator

Testing and Debugging

Quick Check Answers

Exam Preparation Exercises

Programming Warm-Up Exercises

Programming Problems

Case Study Follow-Up

4 Program Input and the Software Design Process

4.1 Getting Data into Programs

Input Streams and the Extraction Operator (>>)

The Reading Marker and the Newline Character

Reading Character Data with the get Function

Skipping Characters with the ignore Function

Reading String Data

4.2 Interactive Input/Output

4.3 Noninteractive Input/Output

4.4 File Input and Output

Software Maintenance Case Study: Adding File Input/Output to a Program

Run-Time Input of File Names

4.5 Input Failure

4.6 Software Design Methodologies

4.7 Functional Decomposition

Implementing the Design

A Perspective on Design

Problem-Solving Case Study: Displaying a Name in Multiple Formats

Testing and Debugging

Quick Check Answers

Exam Preparation Exercises

Programming Warm-Up Exercises

Programming Problems

Case Study Follow-Up

5 Conditions, Logical Expressions, and Selection Control Structures

5.1 Flow of Control

5.2 Conditions and Logical Expressions

The bool Data Type

Logical Expressions

5.3 The If Statement

The If-Then-Else Form

Blocks (Compound Statements)

The If-Then Form

A Common Mistake

Software Maintenance Case Study: Incorrect Output

5.4 Nested If Statements

The Dangling else

5.5 Logical Operators

Precedence of Operators

Relational Operators with Floating-Point Types

5.6 Testing the State of an I/O Stream

Problem-Solving Case Study: BMI Calculator

Testing and Debugging

Testing in the Problem-Solving Phase: The Algorithm Walk-Through

Testing in the Implementation Phase

Tests Performed Automatically During Compilation and Execution

Quick Check Answers

Exam Preparation Exercises

Programming Warm-Up Exercises

Programming Problems

Case Study Follow-Up

6.1 The While Statement

6.2 Phases of Loop Execution

6.3 Loops Using the While Statement

Count-Controlled Loops

Event-Controlled Loops

Looping Subtasks

Software Maintenance Case Study: Make a Program General

6.4 How to Design Loops

Designing the Flow of Control

Designing the Process Within the Loop

6.5 Nested Logic

Designing Nested Loops

Problem-Solving Case Study: Recording Studio Design

Testing and Debugging

Loop-Testing Strategy

Test Plans Involving Loops

Quick Check Answers

Exam Preparation Exercises

Programming Warm-Up Exercises

Programming Problems

Case Study Follow-Up

7 Additional Control Structures

7.1 The Switch Statement

7.2 The Do-While Statement

7.3 The For Statement

Software Maintenance Case Study: Changing a Loop Implementation

7.4 The Break and Continue Statements

7.5 Guidelines for Choosing a Looping Statement

7.6 Additional C++ Operators

Assignment Operators and Assignment Expressions

Increment and Decrement Operators

Bitwise Operators

The Cast Operation

The sizeof Operator

The ?: Operator

Operator Precedence

Type Coercion in Arithmetic and Relational Expressions

Problem-Solving Case Study: The Rich Uncle

Testing and Debugging

Quick Check Answers

Exam Preparation Exercises

Programming Warm-Up Exercises

Programming Problems

Case Study Follow-Up

8 Functions

8.1 Functional Decomposition with Void Functions

When to Use Functions

Why Do Modules Need an Interface Design?

Designing Interfaces

Writing Modules as Void Functions

8.2 An Overview of User-Defined Functions

Flow of Control in Function Calls

Function Parameters

8.3 Syntax and Semantics of Void Functions

Function Call (Invocation)

Function Declarations and Definitions

Local Variables

The Return Statement

8.4 Parameters

Value Parameters

Reference Parameters

Software Maintenance Case Study: Refactoring a Program

Using Expressions with Parameters

A Last Word of Caution About Argument and Parameter Lists

Writing Assertions as Function Documentation

Problem-Solving Case Study: Lawn Care Company Billing

Testing and Debugging

The assert Library Function

Quick Check Answers

Exam Preparation Exercises

Programming Warm-Up Exercises

Programming Problems

Case Study Follow-Up

9 Scope, Lifetime, and More on Functions

9.1 Scope of Identifiers

Variable Declarations and Definitions

9.2 Lifetime of a Variable

Initializations in Declarations

Software Maintenance Case Study: Debug a Simple Program

9.3 Interface Design

Global Constants

9.4 Value-Returning Functions

Complete Example

Boolean Functions

Interface Design and Side Effects

When to Use Value-Returning Functions

9.5 Type Coercion in Assignments, Argument Passing, and Return of a Function Value

Problem-Solving Case Study: Health Profile

Testing and Debugging

Stubs and Drivers

Quick Check Answers

Exam Preparation Exercises

Programming Warm-Up Exercises

Programming Problems

Case Study Follow-Up

10 User-Defined Data Types

10.1 Built-In Simple Types

10.2 User-Defined Simple Types

The Typedef Statement

Enumeration Types

Named and Anonymous Data Types

10.3 Simple Versus Structured Data Types

10.4 Records (Structs)

Accessing Individual Components

Aggregate Operations on Structs

More About Struct Declarations

Binding Like Items

Software Maintenance Case Study: Changing a Loop Implementation

10.5 Hierarchical Records

10.6 Unions

10.7 Pointers

Pointer Variables

Pointers Expressions

10.8 Reference Types

Problem-Solving Case Study: Stylistical Analysis of Text

Testing and Debugging

Coping with Input Errors

Debugging with Pointers

Quick Check Answers

Exam Preparation Exercises

Programming Warm-Up Exercises

Programming Problems

Case Study Follow-Up

11.1 One-Dimensional Arrays

Declaring Arrays

Accessing Individual Components

Out-of-Bounds Array Indexes

Initializing Arrays in Declarations

(Lack of) Aggregate Array Operations

Examples of Declaring and Accessing Arrays

Passing Arrays as Arguments

Commenting Arrays

Software Maintenance Case Study: Modularizing a Program

Using Typedef with Arrays

Pointer Expressions and Arrays

C-Style Strings

Strings as Arrays

C String Operations

Converting C Strings to C++ Strings

Which String Representation to Use

11.2 Arrays of Records

Arrays of Records

11.3 Special Kinds of Array Processing

Subarray Processing

Indexes with Semantic Content

11.4 Two-Dimensional Arrays

11.5 Passing Two-Dimensional Arrays as Arguments

11.6 Processing Two-Dimensional Arrays

Sum the Columns Revised

Sum the Columns

Initialize the Array

Print the Array

11.7 Another Way of Defining Two-Dimensional Arrays

11.8 Multidimensional Arrays

Problem-Solving Case Study: Calculating Exam Statistics

Problem-Solving Case Study: Favorite Rock Group

Testing and Debugging

One-Dimensional Arrays

Complex Structures

Multidimensional Arrays

Quick Check Answers

Exam Preparation Exercises

Programming Warm-Up Exercises

Programming Problems

Case Study Follow-Up

12 Classes and Abstraction

12.1 Abstract Data Types

12.2 C++ Classes

Implementing the Member Functions

Classes, Objects, and Members

Built-in Operations on Objects

12.3 Information Hiding

User-Written Header Files

Specification and Implementation Files

Compiling and Linking a Multifile Program

12.4 What Is an Object?

12.5 Class Design Principles

Designing for Modifiability and Reuse

Software Maintenance Case Study: Comparing Two TimeOfDay Objects

12.6 The Name ADT

Specification of the ADT

Implementation File

12.7 Composition

Design of an Entry Class

12.8 UML Diagrams

Diagramming a Class

Diagramming Composition of Classes

Problem-Solving Case Study: Create an Array of Name Objects

Testing and Debugging

Quick Check Answers

Exam Preparation Exercises

Programming Warm-Up Exercises

Programming Problems

Case Study Follow-Up

13 Array-Based Lists

13.1 What Is a List?

13.2 The List as an Abstract Data Type

Refining Responsibilities

Data Representation

Example Program

13.3 Implementation of List ADT

Basic Operations

Insertion and Deletion

Sequential Search

Software Maintenance Case Study: Enhancing Class List with a Sort

13.4 Sorted Lists

Basic Operations

Sequential Search

13.5 Sorted List of Classes

Insert and Delete

13.6 More on UML Diagrams

Problem-Solving Case Study: Calculating Exam Statistics Revisited

Testing and Debugging

Quick Check Answers

Exam Preparation Exercises

Programming Warm-Up Exercises

Programming Problems

Case Study Follow-Up

14 Dynamic Data and Linked Lists

14.1 Dynamic Data

Allocating Dynamic Data

Deleting Dynamic Data

Constants and Dynamic Data

14.2 Sequential Versus Linked Structures

14.3 Creating a Dynamic Linked List: A Walk-Through Example

14.4 Dynamic Implementation of ADT List

Creating an Empty Linked List

Inserting into a Linked List

Traversals of a Linked List

Deleting from a Linked List

Resetting the List

Getting the Next Item

Testing for the Full Linked List

Searching the List

14.5 Destructors and Copy Constructors

Shallow Versus Deep Copying

Copy-Constructor

14.6 Sorted Linked List

Insert(60) (pick up with loop)

Deleting from a Linked List

Problem-Solving Case Study: Creating a Sorted List of Entry Objects

Testing and Debugging

Quick Check Answers

Exam Preparation Exercises

Programming Warm-Up Exercises

Programming Problems

Case Study Follow-Up

15 Inheritance, Polymorphism, and Object-Oriented Design

15.1 Object-Oriented Programming

15.2 Inheritance

Inheritance and the Object-Oriented Design Process

Deriving One Class from Another Class

Specification of the ExpandedEntry Class

Implementation of the ExpandedEntry Class

Constructor Execution Order

Software Maintenance Case Study: Extending TimeOfDay with Support for a Time Zone

15.3 Dynamic Binding and Virtual Functions

The Slicing Problem

Virtual Functions

15.4 Object-Oriented Design

Scenario Exploration

Responsibility Algorithms

15.5 Implementing a Design

Problem-Solving Case Study: Creating an Appointment Calendar

Testing and Debugging

Quick Check Answers

Exam Preparation Exercises

Programming Warm-Up Exercises

Programming Problems

Case Study Follow-Up

16 Templates, Operator Overloading, and Exceptions

16.1 Template Classes

Defining a Class Template

Instantiating a Class Template

Another Way of Implementing Incoming Parameters: const References

Organization of Program Code

A Word of Caution

16.2 Generic Functions

Function Overloading

Defining a Function Template Outside a Class

Instantiating a Function Template

16.3 Operator Overloading

16.4 Exceptions

The throw Statement

The try-catch Statement

Nonlocal Exception Handlers

Rethrowing an Exception

Standard Exceptions

Software Maintenance Case Study: Adding Exceptions to the Date Class

Problem-Solving Case Study: Starship Weight and Balance

Testing and Debugging

Quick Check Answers

Exam Preparation Exercises

Programming Warm-Up Exercises

Programming Problems

Case Study Follow-Up

17 Introduction to Data Structures Using the Standard Template Library

17.1 Abstract Data Structures versus Implementations

17.2 Additional Linear Structures

Priority Queues

17.3 Bidirectional Linear Structures

Bidirectional Lists

17.4 An Introduction to the STL

The vector Template

The list Template

The stack Template

The queue Template

The priority_queue Template

The deque Template

Software Maintenance Case Study: Appointment Calendar Using STL List

17.5 Nonlinear Structures

17.6 Associative Containers

The set Template

The map Template

Problem-Solving Case Study: Creating a Deck of Cards

Testing and Debugging

Quick Check Answers

Exam Preparation Exercises

Programming Warm-Up Exercises

Programming Problems

Case Study Follow-Up

18 Recursion

18.1 What Is Recursion?

18.2 Recursive Algorithms with Simple Variables

18.3 Towers of Hanoi

18.4 Recursive Algorithms with Structured Variables

Software Maintenance Case Study: Substituting Binary Search for Linear Search

18.5 Recursion Using Pointer Variables

Printing a Dynamic Linked List in Reverse Order

Copying a Dynamic Linked List

18.6 Recursion or Iteration?

Problem-Solving Case Study: Quicksort

Testing and Debugging

Quick Check Answers

Exam Preparation Exercises

Programming Warm-Up Exercises

Programming Problems

Case Study Follow-Up

Appendix A: Reserved Words

Appendix B: Operator Precedence

Appendix C: A Selection of Standard Library Routines

Appendix D: Using This Book with a Prestandard Version of C++

Appendix E: Character Sets

Appendix F: Program Style, Formatting, and Documentation

Appendix G: More on Floating-Point Numbers

Appendix H: Using C Strings

Appendix I: C++ char Constants