Problem Solving with C++

Walter Savitch is Professor Emeritus of Computer Science at the University of California—San Diego. He received his PhD in mathematics from the University of California—Berkeley in 1969. Since that time he has been on the faculty of the University of California—San Diego (UCSD). He served as director of the UCSD Interdisciplinary PhD program in cognitive science for over ten years. He has served as a visiting researcher at the computer science departments of the University of Washington in Seattle and at the University of Colorado in Boulder, and has been a visiting scholar at the Centrum voor Wiskunde en Informatica in Amsterdam.

Chapter 1 Introduction to Computers and C++ Programming 1

1.1 Computer Systems 2

Hardware 2

Software 7

High-Level Languages 8

Compilers 9

History Note 12

1.2 Programming and Problem-Solving 12

Algorithms 12

Program Design 15

Object-Oriented Programming 16

The Software Life Cycle 17

1.3 Introduction to C++ 18

Origins of the C++ Language 18

A Sample C++ Program 19

Pitfall: Using the Wrong Slash in /n 23

Programming Tip: Input and Output Syntax 23

Layout of a Simple C++ Program 24

Pitfall: Putting a Space Before the include File Name 26

Compiling and Running a C++ Program 26

Pitfall: Compiling a C++11 program 27

Programming Tip: Getting Your Program to Run 27

1.4 Testing and Debugging 29

Kinds of Program Errors 30

Pitfall: Assuming Your Program Is Correct 31

Chapter Summary 32

Answers to Self-Test Exercises 33

Practice Programs 35

Programming Projects 36

 

Chapter 2 C++ Basics 39

2.1 Variables and Assignments 40

Variables 40

Names: Identifiers 42

Variable Declarations 44

Assignment Statements 45

Pitfall: Uninitialized Variables 47

Programming Tip: Use Meaningful Names 49

2.2 Input and Output 50

Output Using cout 50

Include Directives and Namespaces 52

Escape Sequences 53

Programming Tip: End Each Program with a /n or endl 55

Formatting for Numbers with a Decimal Point 55

Input Using cin 56

Designing Input and Output 58

Programming Tip: Line Breaks in I/O 58

2.3 Data Types and Expressions 60

The Types int and double 60

Other Number Types 62

C++11 Types 63

The Type char 64

The Type bool 66

Introduction to the Class string 66

Type Compatibilities 68

Arithmetic Operators and Expressions 69

Pitfall: Whole Numbers in Division 72

More Assignment Statements 74

2.4 Simple Flow of Control 74

A Simple Branching Mechanism 75

Pitfall: Strings of Inequalities 80

Pitfall: Using = in place of == 81

Compound Statements 82

Simple Loop Mechanisms 84

Increment and Decrement Operators 87

Programming Example: Charge Card Balance 89

Pitfall: Infinite Loops 90

2.5 Program Style 93

Indenting 93

Comments 93

Naming Constants 95

Chapter Summary 98

Answers to Self-Test Exercises 98

Practice Programs 103

Programming Projects 105

 

Chapter 3 More Flow of Control 111

3.1 Usin g Boolean Expressions 112

Evaluating Boolean Expressions 112

Pitfall: Boolean Expressions Convert to int Values 116

Enumeration Types (Optional) 119

3.2 Multiway Branches 120

Nested Statements 120

Programming Tip: Use Braces in Nested Statements 121

Multiway if-else Statements 123

Programming Example: State Income Tax 125

The switch Statement 128

Pitfall: Forgetting a break in a switch Statement 132

Using switch Statements for Menus 133

Blocks 135

Pitfall: Inadvertent Local Variables 138

3.3 More About C++ Loop Statements 139

The while Statements Reviewed 139

Increment and Decrement Operators Revisited 141

The for Statement 144

Pitfall: Extra Semicolon in a for Statement 149

What Kind of Loop to Use 150

Pitfall: Uninitialized Variables and Infinite Loops 152

The break Statement 153

Pitfall: The break Statement in Nested Loops 154

3.4 Designing Loops 155

Loops for Sums and Products 155

Ending a Loop 157

Nested Loops 160

Debugging Loops 162

Chapter Summary 165

Answers to Self-Test Exercises 166

Practice Programs 172

Programming Projects 174

 

Chapter 4 Procedural Abstraction and Functions That Return a Value 181

4.1 Top-Down Design 182

4.2 Predefined Functions 183

Using Predefined Functions 183

Random Number Generation 188

Type Casting 190

Older Form of Type Casting 192

Pitfall: Integer Division Drops the Fractional Part 192

4.3 Programmer-Defined Functions 193

Function Definitions 193

Functions That Return a Boolean Value 199

Alternate Form for Function Declarations 199

Pitfall: Arguments in the Wrong Order 200

Function Definition—Syntax Summary 201

More About Placement of Function Definitions 202

Programming Tip: Use Function Calls in Branching Statements 203

4.4 Procedural Abstraction 204

The Black-Box Analogy 204

Programming Tip: Choosing Formal Parameter Names 207

Programming Tip: Nested Loops 208

Case Study: Buying Pizza 211

Programming Tip: Use Pseudocode 217

4.5 Scope and Local Variables 218

The Small Program Analogy 218

Programming Example: Experimental Pea Patch 221

Global Constants and Global Variables 221

Call-by-Value Formal Parameters Are Local Variables 224

Block Scope 226

Namespaces Revisited 227

Programming Example: The Factorial Function 230

4.6 Overloading Function Names 232

Introduction to Overloading 232

Programming Example: Revised Pizza-Buying Program 235

Automatic Type Conversion 238

Chapter Summary 240

Answers to Self-Test Exercises 240

Practice Programs 245

Programming Projects 247

 

Chapter 5 Functions for All Subtasks 251

5.1 void Functions 252

Definitions of void Functions 252

Programming Example: Converting Temperatures 255

return Statements in void Functions 255

5.2 Call-By-Reference Parameters 259

A First View of Call-by-Reference 259

Call-by-Reference in Detail 262

Programming Example: The swap_values Function 267

Mixed Parameter Lists 268

Programming Tip: What Kind of Parameter to Use 269

Pitfall: Inadvertent Local Variables 270

5.3 Using Procedural Abstraction 273

Functions Calling Functions 273

Preconditions and Postconditions 275

Case Study: Supermarket Pricing 276

5.4 Testing and Debugging Functions 281

Stubs and Drivers 282

5.5 General Debugging Techniques 287

Keep an Open Mind 287

Check Common Errors 287

Localize the Error 288

The assert Macro 290

Chapter Summary 292

Answers to Self-Test Exercises 293

Practice Programs 296

Programming Projects 299

 

Chapter 6 I/O Streams as an Introduction to Objects and Classes 305

6.1 Streams and Basic File I/O 306

Why Use Files for I/O? 307

File I/O 308

Introduction to Classes and Objects 312

Programming Tip: Check Whether a File Was Opened Successfully 314

Techniques for File I/O 316

Appending to a File (Optional) 320

File Names as Input (Optional) 321

6.2 Tools for Stream I/O 323

Formatting Output with Stream Functions 323

Manipulators 329

Streams as Arguments to Functions 332

Programming Tip: Checking for the End of a File 332

A Note on Namespaces 335

Programming Example: Cleaning Up a File Format 336

6.3 Character I/O 338

The Member Functions get and put 338

The putback Member Function (Optional) 342

Programming Example: Checking Input 343

Pitfall: Unexpected '/n' in Input 345

Programming Example: Another new_line Function 347

Default Arguments for Functions (Optional) 348

The eof Member Function 353

Programming Example: Editing a Text File 355

Predefined Character Functions 356

Pitfall: toupper and tolower Return Values 358

Chapter Summary 360

Answers to Self-Test Exercises 361

Practice Programs 368

Programming Projects 370

 

Chapter 7 Arrays 377

7.1 Introduction to Arrays 378

Declaring and Referencing Arrays 378

Programming Tip: Use for Loops with Arrays 380

Pitfall: Array Indexes Always Start with Zero 380

Programming Tip: Use a Defined Constant for the Size of an Array 380

Arrays in Memory 382

Pitfall: Array Index Out of Range 383

Initializing Arrays 386

Programming Tip: C++11 Range-Based for Statement 386

7.2 Arrays in Functions 389

Indexed Variables as Function Arguments 389

Entire Arrays as Function Arguments 391

The const Parameter Modifier 394

Pitfall: Inconsistent Use of const Parameters 397

Functions That Return an Array 397

Case Study: Production Graph 398

7.3 Programming with Arrays 411

Partially Filled Arrays 411

Programming Tip: Do Not Skimp on Formal Parameters 414

Programming Example: Searching an Array 414

Programming Example: Sorting an Array 417

Programming Example: Bubble Sort 421

7.4 Multidimensional Arrays 424

Multidimensional Array Basics 425

Multidimensional Array Parameters 425

Programming Example: Two-Dimensional

Grading Program 427

Pitfall: Using Commas Between Array Indexes 431

Chapter Summary 432

Answers to Self-Test Exercises 433

Practice Programs 437

Programming Projects 439

 

Chapter 8 Strings and Vectors 451

8.1 An Array Type for Strings 453

C-String Values and C-String Variables 453

Pitfall: Using = and == with C Strings 456

Other Functions in 458

Pitfall: Copying past the end of a C-string using strcpy 461

C-String Input and Output 464

C-String-to-Number Conversions and Robust Input 466

8.2 The Standard string Class 472

Introduction to the Standard Class string 472

I/O with the Class string 475

Programming Tip: More Versions of getline 478

Pitfall: Mixing cin >> variable; and getline 479

String Processing with the Class string 480

Programming Example: Palindrome Testing 484

Converting Between string Objects and C Strings 487

Converting Between Strings and Numbers 488

8.3 Vectors 489

Vector Basics 489

Pitfall: Using Square Brackets Beyond the Vector Size 492

Programming Tip: Vector Assignment Is Well Behaved 493

Efficiency Issues 493

Chapter Summary 495

Answers to Self-Test Exercises 495

Practice Programs 497

Programming Projects 498

 

Chapter 9 Pointers and Dynamic Arrays 507

9.1 Pointers 508

Pointer Variables 509

Basic Memory Management 516

Pitfall: Dangling Pointers 517

Static Variables and Automatic Variables 518

Programming Tip: Define Pointer Types 518

9.2 Dynamic Arrays 521

Array Variables and Pointer Variables 521

Creating and Using Dynamic Arrays 522

Pointer Arithmetic (Optional) 528

Multidimensional Dynamic Arrays (Optional) 530

Chapter Summary 532

Answers to Self-Test Exercises 532

Practice Programs 533

Programming Projects 534

 

Chapter 10 Defining Classes 541

10.1 Structures 542

Structures for Diverse Data 542

Pitfall: Forgetting a Semicolon in a Structure Definition 547

Structures as Function Arguments 548

Programming Tip: Use Hierarchical Structures 549

Initializing Structures 551

10.2 Classes 554

Defining Classes and Member Functions 554

Public and Private Members 559

Programming Tip: Make All Member Variables Private 567

Programming Tip: Define Accessor and Mutator Functions 567

Programming Tip: Use the Assignment Operator with Objects 569

Programming Example: BankAccount Class–Version 1 570

Summary of Some Properties of Classes 574

Constructors for Initialization 576

Programming Tip: Always Include a Default Constructor 584

Pitfall: Constructors with No Arguments 585

Member Initializers and Constructor Delegation in C++11 587

10.3 Abstract Data Types 588

Classes to Produce Abstract Data Types 589

Programming Example: Alternative Implementation of a Class 593

10.4 Introduction to Inheritance 598

Derived Classes 599

Defining Derived Classes 600

Chapter Summary 604

Answers to Self-Test Exercises 605

Practice Programs 611

Programming Projects 612

 

Chapter 11 Friends, Overloaded Operators, and Arrays in Classes 619

11.1 Friend Functions 620

Programming Example: An Equality Function 620

Friend Functions 624

Programming Tip: Define Both Accessor Functions and Friend Functions 626

Programming Tip: Use Both Member and Nonmember Functions 628

Programming Example: Money Class (Version 1) 628

Implementation of digit_to_int (Optional) 635

Pitfall: Leading Zeros in Number Constants 636

The const Parameter Modifier 638

Pitfall: Inconsistent Use of const 639

11.2 Overloading Operators 643

Overloading Operators 644

Constructors for Automatic Type Conversion 647

Overloading Unary Operators 649

Overloading >> and << 650

11.3 Arrays and Classes 660

Arrays of Classes 660

Arrays as Class Members 664

Programming Example: A Class for a Partially Filled Array 665

11.4 Classes and Dynamic Arrays 667

Programming Example: A String Variable Class 668

Destructors 671

Pitfall: Pointers as Call-by-Value Parameters 674

Copy Constructors 675

Overloading the Assignment Operator 680

Chapter Summary 683

Answers to Self-Test Exercises 683

Practice Programs 693

Programming Projects 694

 

Chapter 12 Separate Compilation and Namespaces 703

12.1 Separate Compilation 704

ADTs Reviewed 705

Case Study: DigitalTime –A Class Compiled Separately 706

Using #ifndef 715

Programming Tip: Defining Other Libraries 718

12.2 Namespaces 719

Namespaces and using Directives 719

Creating a Namespace 721

Qualifying Names 724

A Subtle Point About Namespaces (Optional) 725

Unnamed Namespaces 726

Programming Tip: Choosing a Name for a Namespace 731

Pitfall: Confusing the Global Namespace and the Unnamed Namespace 732

Chapter Summary 733

Answers to Self-Test Exercises 734

Practice Programs 736

Programming Projects 738

 

Chapter 13 Pointers and Linked Lists 739

13.1 Nodes and Linked Lists 740

Nodes 740

nullptr 745

Linked Lists 746

Inserting a Node at the Head of a List 747

Pitfall: Losing Nodes 750

Searching a Linked List 751

Pointers as Iterators 755

Inserting and Removing Nodes Inside a List 755

Pitfall: Using the Assignment Operator with Dynamic Data Structures 757

Variations on Linked Lists 760

Linked Lists of Classes 762

13.2 Stacks and Queues 765

Stacks 765

Programming Example: A Stack Class 766

Queues 771

Programming Example: A Queue Class 772

Chapter Summary 776

Answers to Self-Test Exercises 776

Practice Programs 779

Programming Projects 780

 

Chapter 14 Recursion 789

14.1 Recursive Functions for Tasks 791

Case Study: Vertical Numbers 791

A Closer Look at Recursion 797

Pitfall: Infinite Recursion 799

Stacks for Recursion 800

Pitfall: Stack Overflow 802

Recursion Versus Iteration 802

14.2 Recursive Functions for Values 804

General Form for a Recursive Function That Returns a Value 804

Programming Example: Another Powers Function 804

14.3 Thinking Recursively 809

Recursive Design Techniques 809

Case Study: Binary Search–An Example of Recursive Thinking 810

Programming Example: A Recursive Member Function 818

Chapter Summary 822

Answers to Self-Test Exercises 822

Practice Programs 827

Programming Projects 827

 

Chapter 15 Inheritance 833

15.1 Inheritance Basics 834

Derived Classes 837

Constructors in Derived Classes 845

Pitfall: Use of Private Member Variables from the Base Class 848

Pitfall: Private Member Functions Are Effectively Not Inherited 850

The protected Qualifier 850

Redefinition of Member Functions 853

Redefining Versus Overloading 856

Access to a Redefined Base Function 858

15.2 INHERITANCE DETAILS 859

Functions That Are Not Inherited 859

Assignment Operators and Copy Constructors in Derived Classes 860

Destructors in Derived Classes 861

15.3 Polymorphism 862

Late Binding 863

Virtual Functions in C++ 864

Virtual Functions and Extended Type Compatibility 869

Pitfall: The Slicing Problem 873

Pitfall: Not Using Virtual Member Functions 874

Pitfall: Attempting to Compile Class Definitions Without Definitions for Every Virtual Member Function 875

Programming Tip: Make Destructors Virtual 875

Chapter Summary 877

Answers to Self-Test Exercises 877

Practice Programs 881

Programming Projects 884

 

Chapter 16 Exception Handling 893

16.1 Exception-Handling Basics 895

A Toy Example of Exception Handling 895

Defining Your Own Exception Classes 904

Multiple Throws and Catches 904

Pitfall: Catch the More Specific Exception First 908

Programming Tip: Exception Classes Can Be Trivial 909

Throwing an Exception in a Function 909

Exception Specification 911

Pitfall: Exception Specification in Derived Classes 913

16.2 Programming Techniques for

Exception Handling 914

When to Throw an Exception 914

Pitfall: Uncaught Exceptions 916

Pitfall: Nested try-catch Blocks 916

Pitfall: Overuse of Exceptions 916

Exception Class Hierarchies 917

Testing for Available Memory 917

Rethrowing an Exception 918

Chapter Summary 918

Answers to Self-Test Exercises 918

Practice Programs 920

Programming Projects 921

 

Chapter 17 Templates 925

17.1 Templates for Algorithm Abstraction 926

Templates for Functions 927

Pitfall: Compiler Complications 931

Programming Example: A Generic Sorting Function 933

Programming Tip: How to Define Templates 937

Pitfall: Using a Template with an Inappropriate Type 938

17.2 Templates for Data Abstraction 939

Syntax for Class Templates 939

Programming Example: An Array Class 942

Chapter Summary 949

Answers to Self-Test Exercises 949

Practice Programs 953

Programming Projects 953

 

Chapter 18 Standard Template Library 957

18.1 Iterators 959

using Declarations 959

Iterator Basics 960

Programming Tip: Use auto to Simplify Variable Declarations 964

Pitfall: Compiler Problems 964

Kinds of Iterators 966

Constant and Mutable Iterators 970

Reverse Iterators 971

Other Kinds of Iterators 972

18.2 Containers 973

Sequential Containers 974

Pitfall: Iterators and Removing Elements 978

Programming Tip: Type Definitions in Containers 979

Container Adapters stack and queue 979

Associative Containers set and map 983

Programming Tip: Use Initialization, Ranged For, and auto with Containers 990

Efficiency 990

18.3 Generic Algorithms 991

Running Times and Big-O Notation 992

Container Access Running Times 995

Nonmodifying Sequence Algorithms 997

Container Modifying Algorithms 1001

Set Algorithms 1003

Sorting Algorithms 1004

Chapter Summary 1005

Answers to Self-Test Exercises 1005

Practice Programs 1007

Programming Projects 1008

 

Appendices

1 C++ Keywords 1015

2 Precedence of Operators 1016

3 The ASCII Character Set 1018

4 Some Library Functions 1019

5 Inline Functions 1026

6 Overloading the Array Index Square Brackets 1027

7 The this Pointer 1029

8 Overloading Operators as Member Operators 1032

Index 1034