Problem Solving, Abstraction, and Design Using C++

Contents
Chapter zero: Computer Science as a Career Path
Chapter one: Introduction to Computers, Problem Solving, and Programming
1.1 Overview of Computers
Early Computers
Categories of Computers
Sharing Computer Resources
1.2 Computer Hardware
Memory
Main Memory
Secondary Memory
Central Processing Unit
Input/Output Devices
Computer Networks
The World Wide Web
1.3 Computer Software
Operating System
Application Software
Programming Languages
Object-Oriented Programming
1.4 Processing a High-Level Language Program
Executing a Program
1.5 The Software Development Method
Caution: Failure Is Part of the Process
1.6 Applying the Software Development Method
CASE STUDY: Converting Miles to Kilometers
1.7 Professional Ethics for Computer Programmers
Privacy and Misuse of Data
Computer Hacking
Plagiarism and Software Piracy
Misuse of a Computer Resource
Chapter Review
Quick-Check Exercises
Review Questions
Answers to Quick-Check Exercises
Bjarne Stroustrup
Chapter two: Overview of C++
2.1 C++ Language Elements
Comments
Compiler Directive #include
Namespace std
Function main
Declaration Statements
Executable Statements
2.2 Reserved Words and Identifiers
Reserved Words
Identifiers
Uppercase and Lowercase Letters
2.3 Data Types and Declarations
Data Types
string Class
Purpose of Data Types
Declarations
Constant Declarations
2.4 Executable Statements
Programs in Memory
Assignment Statements
Input/Output Operations
Input Statements
Program Output
The return Statement
2.5 General Form of a C++ Program
Comments in Programs
2.6 Arithmetic Expressions
Operators / and %
Data Type of a Mixed-Type Expression
Mixed-Type Assignment Statement
Expressions with Multiple Operators
Writing Mathematical Formulas in C++
CASE STUDY: Supermarket Coin Processor
2.7 Interactive Mode, Batch Mode, and Data Files
Input Redirection
Output Redirection
2.8 Common Programming Errors
Syntax Errors
Run-Time Errors
Undetected Errors
Logic Errors
Chapter Review
Quick-Check Exercises
Review Questions
Programming Projects
Answers to Quick-Check Exercises
Josée Lajoie
Chapter three: Top-Down Design with Functions and Classes
3.1 Building Programs from Existing Information
CASE STUDY: Finding the Area and Circumference of a Circle
CASE STUDY: Computing the Weight of a Batch of Flat Washers
3.2 Library Functions
C++ Library Functions
A Look Ahead
3.3 Top-Down Design and Structure Charts
CASE STUDY: Drawing Simple Figures
3.4 Functions without Arguments
Function Prototypes
Function Definitions
Placement of Functions in a Program
Order of Execution of Functions
Advantages of Using Function Subprograms
3.5 Functions with Input Arguments
void Functions with Input Arguments
Functions with Input Arguments and a Single Result
Functions with Multiple Arguments
Argument/Parameter List Correspondence
The Function Data Area
Testing Functions Using Drivers
3.6 Scope of Names
3.7 Extending C++ through Classes:Using Class string
The string Class
Declaring string Objects
Reading and Displaying string Objects
String Assignment and Concatenation
Operator Overloading
Dot Notation: Calling Functions length and at
Member Functions for Word-Processing Operations
Assigning a Substring to a string Object
3.8 Introduction to Computer Graphics (Optional)
Composition of a Window
Some Common Graphics Functions
Background Color and Foreground Color
Drawing Rectangles
Drawing Circles, Ellipses, and Arcs
Pie Slices and Filled Ellipses
Adding Text to Drawings
3.9 Common Programming Errors
Separately Testing Function Subprograms
Chapter Review
Quick-Check Exercises
Review Questions
Programming Projects
Graphics Projects
Answers to Quick-Check Exercises
Mark Hall
Chapter four: Selection Structures: if and switch Statements
4.1 Control Structures
4.2 Logical Expressions
Logical Expressions Using Relational and Equality Operators
Logical Expressions Using Logical Operators
Operator Precedence
Writing Conditions in C++
Comparing Characters and Strings
Boolean Assignment
Writing bool Values
Using Integers to Represent Logical Values
4.3 Introduction to the if Control Statement
if Statement with Two Alternatives
if Statement with Dependent Statement
if Statement Conditions with Characters and Strings
Format of the if Statement
4.4 if Statements with Compound Alternatives
Tracing an if Statement
4.5 Decision Steps in Algorithms
CASE STUDY: Payroll Problem with Functions
A Reminder about Identifier Scope
Adding Data Flow Information to Structure Charts
Commentary—The Software Development Method
4.6 Checking the Correctness of an Algorithm
4.7 Nested if Statements and Multiple-Alternative Decisions
Comparison of Nested if Statements and a Sequence of if Statements
Writing a Nested if as a Multiple-Alternative Decision
Order of Conditions
Short-Circuit Evaluation of Logical Expressions
4.8 The switch Control Statement
Proper Use of break
Comparison of Nested if Statements and the switch Statement
Using a switch Statement to Select Alternative Functions
4.9 Common Programming Errors
Chapter Review
Quick-Check Exercises
Review Questions
Programming Projects
Answers to Quick-Check Exercises
Chapter five: Repetition and Loop Statements
5.1 Counting Loops and the while Statement
The while Statement
Syntax of the while Statement
5.2 Accumulating a Sum or Product in a Loop
Multiplying a List of Numbers
Compound Assignment Operators
5.3 The for Statement
Increment and Decrement Operators
Increments and Decrements Other than One
Displaying a Table of Values
5.4 Conditional Loops
A Loop with a Decreasing Loop Control Variable
CASE STUDY: Monitoring Oil Supply
Zero Iteration Loops
More General Conditional Loops
5.5 Loop Design and Loop Patterns
Sentinel-Controlled Loops
Calculating an Average
Flag-Controlled Loops
5.6 The do-while Statement
5.7 Review of while, for, and do-while Loops
5.8 Nested Loops
5.9 Debugging and Testing Programs
Using a Debugger
Debugging without a Debugger
Off-by-One Errors
Testing
5.10 Loops in Graphics Programs (Optional)
Animation
5.11 Common Programming Errors
Chapter Review
Quick-Check Exercises
Review Questions
Programming Projects
Graphics Projects
Answers to Quick-Check Exercises
Mike Weisert
Chapter six: Modular Programming
6.1 Value and Reference Parameters
Call-by-Value and Call-by-Reference Parameters
void Functions Can Return Results
When to Use a Reference or a Value Parameter
Comparison of Value and Reference Parameters
Protection Afforded by Value Parameters
Argument/Parameter List Correspondence Revisited
6.2 Functions with Output and Input Parameters
6.3 Stepwise Design with Function
CASE STUDY: General Sum and Average Problem
Multiple Declarations of Identifiers in a Program
6.4 Using Objects with Functions
6.5 Debugging and Testing a Program System
Top-Down Testing and Stubs
Bottom-Up Testing and Drivers
Debugging Tips for Program Systems
Identifier Scope and Watch Window Variables
Black-Box versus White-Box Testing
6.6 Recursive Functions (Optional)
6.7 Common Programming Errors
Chapter Review
Quick-Check Exercises
Review Questions
Programming Projects
Answers to Quick-Check Exercises
Robert Sebesta
Chapter seven: Simple Data Types
7.1 Constants Revisited
The #define Compiler Directive
7.2 Internal Representations of Numeric Data Types
Fixed-Point and Floating-Point Data Types
Integer Types
Floating-Point Types
Types of Numeric Literals
Value Ranges for Integer and Floating-Point Types
Numerical Inaccuracies
Mixing Types: Promotions
Type Conversions
Type Casting
7.3 Character Data and Functions
Some Useful Character Functions
7.4 Type bool Data and Logical Expressions
Complementing Logical Expressions
Type bool Functions
Input and Output of Type bool Data
7.5 Enumeration Types
Characters as Enumerator Values
Comparisons Involving Enumeration Types
Distinctions among Integral Types
Reading and Writing Enumeration Type Values
Placement of Enumeration Type Declarations
Enumeration Types as Cast Operators
7.6 Iterative Approximations
Function Parameters
CASE STUDY: Bisection Method for Finding Roots
7.7 Using Type char Data to Control a Graphics Program (Optional)
Generating Random Numbers
Seeding the Random Number Generator
7.8 Common Programming Errors
Chapter Review
Quick-Check Exercises
Review Questions
Programming Projects
Graphics Projects
Answers to Quick-Check Exercises
Chapter eight: Streams and Files
8.1 The Standard Input/Output Streams
Reading One Character at a Time
8.2 External Files
Interactive versus Batch Processing
Directory Names for External Files
Attaching Streams to External Files
Function copyLine
More on the Newline Character
Using getline with a File Stream
8.3 Using External Files for Communication between Programs
CASE STUDY: Preparing a Payroll File
8.4 More on Reading String Data
Using ignore to Advance Past the Newline Character
8.5 Input/Output Manipulators
8.6 Common Programming Errors
Chapter Review
Quick-Check Exercises
Review Questions
Programming Projects
Answers to Quick-Check Exercises
Anita Borg
Chapter nine: Data Structures:Arrays and Structs
9.1 The Array Data Type
Array Declaration
Array Initialization
Array Subscripts
9.2 Sequential Access to Array Elements
Strings and Arrays of Characters
9.3 Array Arguments
Array Elements as Arguments
Passing an Array Argument
9.4 Reading Part of an Array
9.5 Searching and Sorting Arrays
Finding the Smallest Value in an Array
Array Search
Sorting an Array in Ascending Order
9.6 Analyzing Algorithms: Big-O Notation
Analysis of a Search Algorithm
Analysis of a Sort Algorithm
9.7 Multidimensional Arrays
Declaring Two-Dimensional Arrays
Initializing Two-Dimensional Arrays
Nested Loops for Processing Two-Dimensional Arrays
Two-Dimensional Arrays as Function Arguments
Arrays with Several Dimensions
9.8 The Struct Data Type
Declaring a Struct Type and Struct Variables
Accessing Members of a Struct
9.9 Structs as Operands and Arguments
Struct Copy or Assignment
Passing a Struct as an Argument
Reading a Struct
A Struct as a Function Result
Efficiency of Reference Arguments
9.10 Arrays of Structs
9.11 Strings as Arrays of Characters (Optional)
Declaring and Initializing an Array of Characters
Reading and Writing Character Arrays
Some Useful Functions for Character Arrays
9.12 Graphics Programs with Arrays (Optional)
Drawing a Polygon
Drawing a Grid
9.13 Common Programming Errors
Chapter Review
Quick-Check Exercises
Review Questions
Programming Projects
Answers to Quick-Check Exercises
Chapter ten: User-Defined Classes
10.1 Class Definition and Use
The counter Class
Class Definition for the counter Class
Compiler Directives in File counter.h
Using the counter Class
Compiler Directives in File CounterTest.cpp
10.2 Class Implementation
Constructors
Accessor and Modifier Functions
Compiler Directives in File counter.cpp
10.3 Summary of Rules for Use of Classes and Objects
Objects as Class Instances
Public versus Private Access
Syntax for Class and Member Function Definitions
Comparing Structs and Classes
Project Files and Separate Compilation
Combining Arrays, Structs, and Classes
Function Overloading and Polymorphism
10.4 Classes as Operands and Arguments
10.5 A Fraction Class
Design of fraction Class
Using Class fraction
Implementation File for Class fraction
10.6 A Circle Class
Design of circle Class
Using Class circle
Implementation File for Class circle
10.7 A Simple String Class
Design of Class simpleString
Definition of Class simpleString
Testing Member Functions of Class simpleString
Implementation File for Class simpleString
10.8 A Savings Account Class
CASE STUDY: Using the Savings Account Class
10.9 Common Programming Errors
Chapter Review
Quick-Check Exercises
Review Questions
Programming Projects
Answers to Quick-Check Exercises
Timothy Budd
Chapter eleven: Data Abstraction and Object-Oriented Design
11.1 Template Classes
Definition of a Template Class
Implementation of a Template Class
Compiler Instructions to Support Separate Compilation
11.2 The Indexed List Abstract Data type
Need for an Indexed List Class
Analysis and Design of an Indexed List Class
Using the indexList Class
11.3 Implementing the Indexed List Class
11.4 Illustrating Object-Oriented Design
Object-Oriented Design Methodology
CASE STUDY: An Address Book for an Email Provider
11.5 Operator Overloading and Friends
Operator Overloading
Friends
11.6 The vector Class
Vectors and Arrays
Vector Functions
Accessing a Vector through an Iterator
Standard Algorithms
Using a vector in the Email Address Book Case Study
11.7 Common Programming Errors
Chapter Review
Quick-Check Exercises
Review Questions
Programming Projects
Answers to Quick-Check Exercises
John Lakos
Chapter twelve: Recursion
12.1 The Nature of Recursion
Properties of Recursive Problems and Solutions
12.2 Tracing Recursive Functions
Tracing a Recursive Function
Displaying Characters in Reverse Order
Stack for Function Calls
Implementation of Argument Stacks in C++
12.3 Recursive Mathematical Functions
12.4 Recursive Functions with Array Arguments
CASE STUDY: Binary Search
12.5 Problem Solving with Recursion
CASE STUDY: The Towers of Hanoi
Comparison of Iteration and Recursive Functions
12.6 Common Programming Errors
Chapter Review
Quick-Check Exercises
Review Questions
Programming Projects
Answers to Quick-Check Exercises
Marshall Cline
Chapter thirteen: Pointers and Dynamic Data Structures
13.1 Pointers and the new Operator
Accessing Data with Pointers
Pointer Operations
Pointers with Arrays
Pointers to Structs
13.2 Manipulating the Heap
Effect of the new Operator on the Heap
Returning Cells to the Heap
13.3 Linked Lists and the list Class
Declaring Nodes
Connecting Nodes
Inserting a Node in a List
Insertion at the Head of a List
Insertion at the End of a List
Deleting a Node
Traversing a List
Circular Lists and Two-Way Lists (Optional)
The list Class
13.4 The Stack Abstract Data Type
The C++ stack Class
Implementing a stack Template Class
Implementing the Stack Operators
Testing the Stack ADT
13.5 The Queue Abstract Data Type
The C++ queue Class
Implementing a Queue ADT
13.6 Binary Trees
Binary Search Tree
Searching a Binary Search Tree
Building a Binary Search Tree
Displaying a Binary Search Tree
13.7 Binary Search Tree Abstract Data Type
Design of Binary Tree Class
Implementation of Binary Tree Class
13.8 Efficiency of a Binary Search Tree
13.9 Common Programming Errors
Syntax Errors
Run-Time Errors
Chapter Review
Quick-Check Exercises
Review Questions
Programming Projects
Answers to Quick-Check Exercises
Chapter fourteen: Multiprocessing Using Processes and Threads
14.1 Multitasking
Linear versus Parallel Programming
Multitasking as Time Sharing
Preemptive Multitasking
Time Slices and Parallelism
Concurrent Programming
14.2 Processes
Creating a Process
Waiting for a Process
Executing Another Program from a Process
14.3 Interprocess Communications and Pipes
Pipes
Using Pipes
Interprocess Communications Using Standard Input
Illustrating Communication between a Parent and a Child Process
14.4 Threads
Creating a Thread
Thread Synchronization
Mutual Exclusion Locking
Deadlocks
CASE STUDY: Threads Illustrated
14.5 Common Programming Errors
Chapter Review
Review of C++ Constructs
Quick-Check Exercises
Review Questions
Programming Projects
Answers to Quick-Check Exercises
Index
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Z