Programming and Problem Solving with C++: Comprehensive: Comprehensive Edition

Cover
Title Page
Copyright
Contents
Preface
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
Ask Questions
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
Summary
Quick Check Answers
Exam Preparation Exercises
Programming Warm-Up Exercises
Case Study Follow-Up
Line Number
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
Summary
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
Integral 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
Void 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
Summary
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
Files
Using Files
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
Modules
Implementing the Design
A Perspective on Design
Problem-Solving Case Study: Displaying a Name in Multiple Formats
Testing and Debugging
Summary
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
Selection
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
The Test Plan
Tests Performed Automatically During Compilation and Execution
Summary
Quick Check Answers
Exam Preparation Exercises
Programming Warm-Up Exercises
Programming Problems
Case Study Follow-Up
6 Looping
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
The Loop Exit
6.5 Nested Logic
Designing Nested Loops
Problem-Solving Case Study: Recording Studio Design
Testing and Debugging
Loop-Testing Strategy
Test Plans Involving Loops
Summary
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
Summary
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
Summary
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
Scope Rules
Variable Declarations and Definitions
Namespaces
9.2 Lifetime of a Variable
Initializations in Declarations
Software Maintenance Case Study: Debug a Simple Program
9.3 Interface Design
Side Effects
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
Summary
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
Numeric Types
Characters
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
Summary
Quick Check Answers
Exam Preparation Exercises
Programming Warm-Up Exercises
Programming Problems
Case Study Follow-Up
11 Arrays
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 Rows
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
Summary
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
Class Scope
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
Encapsulation
Abstraction
Designing for Modifiability and Reuse
Mutability
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
Summary
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
Iterators
Software Maintenance Case Study: Enhancing Class List with a Sort
13.4 Sorted Lists
Basic Operations
Insertion
Sequential Search
Binary Search
Deletion
13.5 Sorted List of Classes
IsThere
Insert and Delete
13.6 More on UML Diagrams
Problem-Solving Case Study: Calculating Exam Statistics Revisited
Testing and Debugging
Summary
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
Destructor
Shallow Versus Deep Copying
Copy-Constructor
14.6 Sorted Linked List
Insert(20)
Insert(60) (pick up with loop)
Insert(100)
Deleting from a Linked List
Delete(30)
Delete(50)
Problem-Solving Case Study: Creating a Sorted List of Entry Objects
Testing and Debugging
Summary
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
An Analogy
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
Brainstorming
Filtering
Scenario Exploration
Responsibility Algorithms
A Final Word
15.5 Implementing a Design
Problem-Solving Case Study: Creating an Appointment Calendar
Testing and Debugging
Summary
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
Using *this
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
Summary
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
Stacks
Queues
Priority Queues
17.3 Bidirectional Linear Structures
Bidirectional Lists
Deques
17.4 An Introduction to the STL
Iterators
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
Binary Trees
Hash Tables
17.6 Associative Containers
The set Template
The map Template
Problem-Solving Case Study: Creating a Deck of Cards
Testing and Debugging
Summary
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
Summary
Quick Check Answers
Exam Preparation Exercises
Programming Warm-Up Exercises
Programming Problems
Case Study Follow-Up
Appendices
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
Index