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. Kenrick Mock is an Associate Professor at the University of Alaska–Anchorage. He has also taught at Washington Stat University, Portland State University, and the University of California–Davis. He teaches undergraduate computer science courses across the curriculum including introductory C++, Java™, Visual Basic® for non-programmers, algorithms, computer security, and artificial intelligence. With the Coastal Marine Institute at UAA, he helped develop a computer system to aid in research about Alaska sea ice and the atmosphere. Before becoming a teacher, Mock was a research scientist and software engineer at Intel™. He received a PhD in computer science from UC Davis.

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 17

The Software Life Cycle 17

1.3 INTRODUCTION TO C++ 19

Origins of the C++ Language 19

A Sample C++ Program 20

Pitfall: Using the Wrong Slash in /n 24

Programming Tip: Input and Output Syntax 24

Layout of a Simple C++ Program 24

Pitfall: Putting a Space before the include File Name 26

Compiling and Running a C++ Program 27

Programming Tip: Getting Your Program to Run 27

1.4 TESTING AND DEBUGGING 30

Kinds of Program Errors 30

Pitfall: Assuming Your Program Is Correct 31

Chapter Summary 32

Answers to Self-Test Exercises 33

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

The Type char 63

The Type bool 64

Introduction to the Class string 65

Type Compatibilities 66

Arithmetic Operators and Expressions 69

Pitfall: Whole Numbers in Division 71

More Assignment Statements 73

2.4 SIMPLE FLOW OF CONTROL 74

A Simple Branching Mechanism 74

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 94

Naming Constants 96

Chapter Summary 98

Answers to Self-Test Exercises 99

Programming Projects 104

 

Chapter 3 More Flow of Control 111

3.1 USING 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 129

Pitfall: Forgetting a break in a switch Statement 133

Using switch Statements for Menus 134

Blocks 134

Pitfall: Inadvertent Local Variables 139

3.3 MORE ABOUT C++ LOOP STATEMENTS 140

The while Statements Reviewed 141

Increment and Decrement Operators Revisited 142

The for Statement 145

Pitfall: Extra Semicolon in a for Statement 150

What Kind of Loop to Use 151

Pitfall: Uninitialized Variables and Infinite Loops 153

The break Statement 153

Pitfall: The break Statement in Nested Loops 155

3.4 DESIGNING LOOPS 156

Loops for Sums and Products 156

Ending a Loop 157

Nested Loops 161

Debugging Loops 163

Chapter Summary 166

Answers to Self-Test Exercises 167

Programming Projects 173

 

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

Type Casting 188

Older Form of Type Casting 190

Pitfall: Integer Division Drops the Fractional Part 191

4.3 PROGRAMMER-DEFINED FUNCTIONS 192

Function Definitions 192

Functions That Return a Boolean Value 196

Alternate Form for Function Declarations 199

Pitfall: Arguments in the Wrong Order 199

Function Definition—Syntax Summary 201

More About Placement of Function Definitions 202

Programming Tip: Use Function Calls in Branching Statements 202

4.4 PROCEDURAL ABSTRACTION 204

The Black Box Analogy 204

Programming Tip: Choosing Formal Parameter Names 206

Programming Tip: Nested Loops 208

Case Study: Buying Pizza 211

Programming Tip: Use Pseudocode 217

4.5 LOCAL VARIABLES 218

The Small Program Analogy 218

Programming Example: Experimental Pea Patch 220

Global Constants and Global Variables 221

Call-by-Value Formal Parameters Are Local Variables 224

Namespaces Revisited 226

Programming Example: The Factorial Function 229

4.6 OVERLOADING FUNCTION NAMES 230

Introduction to Overloading 231

Programming Example: Revised Pizza-Buying Program 233

Automatic Type Conversion 236

Chapter Summary 239

Answers to Self-Test Exercises 239

Programming Projects 244

 

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 266

Mixed Parameter Lists 268

Programming Tip: What Kind of Parameter to Use 268

Pitfall: Inadvertent Local Variables 270

5.3 USING PROCEDURAL ABSTRACTION 272

Functions Calling Functions 273

Preconditions and Postconditions 273

Case Study: Supermarket Pricing 274

5.4 TESTING AND DEBUGGING FUNCTIONS 282

Stubs and Drivers 282

5.5 GENERAL DEBUGGING TECHNIQUES 287

Keep an Open Mind 287

Check Common Errors 288

Localize the Error 288

The assert macro 291

Chapter Summary 292

Answers to Self-Test Exercises 293

Programming Projects 297

 

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 313

Techniques for File I/O 316

Appending to a File (Optional) 320

File Names as Input (Optional) 320

6.2 TOOLS FOR STREAM I/O 323

Formatting Output with Stream Functions 323

Manipulators 328

Streams as Arguments to Functions 332

Programming Tip: Checking for the End of a File 332

A Note on Namespaces 336

Programming Example: Cleaning Up a File Format 337

6.3 CHARACTER I/O 338

The Member Functions get and put 339

The putback Member Function (Optional) 342

Programming Example: Checking Input 343

Pitfall: Unexpected '/n' in Input 346

The eof Member Function 349

Programming Example: Editing a Text File 352

Predefined Character Functions 352

Pitfall: toupper and tolower Return Values 355

Chapter Summary 357

Answers to Self-Test Exercises 359

Programming Projects 364

 

Chapter 7 Arrays 375

7.1 INTRODUCTION TO ARRAYS 376

Declaring and Referencing Arrays 376

Programming Tip: Use for Loops with Arrays 378

Pitfall: Array Indexes Always Start with Zero 378

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

Arrays in Memory 380

Pitfall: Array Index Out of Range 381

Initializing Arrays 383

7.2 ARRAYS IN FUNCTIONS 385

Indexed Variables as Function Arguments 385

Entire Arrays as Function Arguments 388

The const Parameter Modifier 391

Pitfall: Inconsistent Use of const Parameters 393

Functions That Return an Array 394

Case Study: Production Graph 394

7.3 PROGRAMMING WITH ARRAYS 408

Partially Filled Arrays 408

Programming Tip: Do Not Skimp on Formal Parameters 411

Programming Example: Searching an Array 412

Programming Example: Sorting an Array 414

7.4 MULTIDIMENSIONAL ARRAYS 419

Multidimensional Array Basics 420

Multidimensional Array Parameters 420

Programming Example: Two-Dimensional Grading Program 422

Pitfall: Using Commas Between Array Indexes 427

Chapter Summary 427

Answers to Self-Test Exercises 428

Programming Projects 433

 

Chapter 8 Strings and Vectors 445

8.1 AN ARRAY TYPE FOR STRINGS 447

C-String Values and C-String Variables 447

Pitfall: Using = and == with C Strings 451

Other Functions in 453

C-String Input and Output 457

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

8.2 THE STANDARD string CLASS 465

Introduction to the Standard Class string 465

I/O with the Class string 468

Programming Tip: More Versions of getline 472

Pitfall: Mixing cin >> variable; and getline 472

String Processing with the Class string 474

Programming Example: Palindrome Testing 476

Converting between string Objects and C Strings 481

8.3 VECTORS 482

Vector Basics 482

Pitfall: Using Square Brackets Beyond the Vector Size 484

Programming Tip: Vector Assignment Is Well Behaved 486

Efficiency Issues 487

Chapter Summary 488

Answers to Self-Test Exercises 489

Programming Projects 491

 

Chapter 9 Pointers and Dynamic Arrays 499

9.1 POINTERS 500

Pointer Variables 501

Basic Memory Management 508

Pitfall: Dangling Pointers 509

Static Variables and Automatic Variables 510

Programming Tip: Define Pointer Types 510

9.2 DYNAMIC ARRAYS 513

Array Variables and Pointer Variables 513

Creating and Using Dynamic Arrays 513

Pointer Arithmetic (Optional) 519

Multidimensional Dynamic Arrays (Optional) 521

Chapter Summary 523

Answers to Self-Test Exercises 523

Programming Projects 524

 

Chapter 10 Defining Classes 529

10.1 STRUCTURES 530

Structures for Diverse Data 530

Pitfall: Forgetting a Semicolon in a Structure Definition 535

Structures as Function Arguments 536

Programming Tip: Use Hierarchical Structures 537

Initializing Structures 539

10.2 CLASSES 542

Defining Classes and Member Functions 542

Public and Private Members 547

Programming Tip: Make All Member Variables Private 555

Programming Tip: Define Accessor and Mutator Functions 555

Programming Tip: Use the Assignment Operator with Objects 557

Programming Example: BankAccount Class–Version 1 557

Summary of Some Properties of Classes 562

Constructors for Initialization 564

Programming Tip: Always Include a Default Constructor 572

Pitfall: Constructors with No Arguments 573

10.3 ABSTRACT DATA TYPES 575

Classes to Produce Abstract Data Types 576

Programming Example: Alternative Implementation of a Class 580

10.4 INTRODUCTION TO INHERITANCE 584

Inheritance Among Stream Classes 585

Programming Example: Another new_line Function 588

Default Arguments for Functions (Optional) 589

Defining Derived Classes 591

Chapter Summary 594

Answers to Self-Test Exercises 595

Programming Projects 603

 

Chapter 11 Friends, Overloaded Operators, and

Arrays in Classes 609

11.1 FRIEND FUNCTIONS 610

Programming Example: An Equality Function 610

Friend Functions 614

Programming Tip: Define Both Accessor Functions and Friend

Functions 616

Programming Tip: Use Both Member and Nonmember Functions 618

Programming Example: Money Class (Version 1) 618

Implementation of digit_to_int (Optional) 625

Pitfall: Leading Zeros in Number Constants 626

The const Parameter Modifier 628

Pitfall: Inconsistent Use of const 630

11.2 OVERLOADING OPERATORS 633

Overloading Operators 634

Constructors for Automatic Type Conversion 638

Overloading Unary Operators 640

Overloading >> and << 640

11.3 ARRAYS AND CLASSES 651

Arrays of Classes 651

Arrays as Class Members 655

Programming Example: A Class for a Partially Filled Array 656

11.4 CLASSES AND DYNAMIC ARRAYS 659

Programming Example: A String Variable Class 659

Destructors 663

Pitfall: Pointers as Call-by-Value Parameters 665

Copy Constructors 667

Overloading the Assignment Operator 672

Chapter Summary 675

Answers to Self-Test Exercises 676

Programming Projects 686

 

Chapter 12 Separate Compilation and Namespaces 695

12.1 SEPARATE COMPILATION 696

ADTs Reviewed 697

Case Study: DigitalTime–A Class Compiled Separately 698

Using #ifndef 707

Programming Tip: Defining Other Libraries 710

12.2 NAMESPACES 712

Namespaces and using Directives 712

Creating a Namespace 714

Qualifying Names 717

A Subtle Point About Namespaces (Optional) 718

Unnamed Namespaces 719

Programming Tip: Choosing a Name for a Namespace 722

Pitfall: Confusing the Global Namespace and the Unnamed

Namespace 724

Chapter Summary 727

Answers to Self-Test Exercises 727

Programming Projects 729

 

Chapter 13 Pointers and Linked Lists 733

13.1 NODES AND LINKED LISTS 734

Nodes 734

Linked Lists 740

Inserting a Node at the Head of a List 741

Pitfall: Losing Nodes 744

Searching a Linked List 745

Pointers as Iterators 749

Inserting and Removing Nodes Inside a List 749

Pitfall: Using the Assignment Operator with Dynamic

Data Structures 752

Variations on Linked Lists 754

Linked Lists of Classes 756

13.2 STACKS AND QUEUES 760

Stacks 760

Programming Example: A Stack Class 761

Queues 766

Programming Example: A Queue Class 767

Chapter Summary 771

Answers to Self-Test Exercises 772

Programming Projects 775

 

Chapter 14 Recursion 781

14.1 RECURSIVE FUNCTIONS FOR TASKS 783

Case Study: Vertical Numbers 783

A Closer Look at Recursion 790

Pitfall: Infinite Recursion 791

Stacks for Recursion 793

Pitfall: Stack Overflow 794

Recursion Versus Iteration 795

14.2 RECURSIVE FUNCTIONS FOR VALUES 796

General Form for a Recursive Function That Returns a Value 796

Programming Example: Another Powers Function 797

14.3 THINKING RECURSIVELY 801

Recursive Design Techniques 801

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

Programming Example: A Recursive Member Function 810

Chapter Summary 815

Answers to Self-Test Exercises 815

Programming Projects 820

 

Chapter 15 Inheritance 825

15.1 INHERITANCE BASICS 826

Derived Classes 827

Constructors in Derived Classes 835

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

Pitfall: Private Member Functions Are Effectively Not Inherited 840

The protected Qualifier 840

Redefinition of Member Functions 843

Redefining Versus Overloading 847

Access to a Redefined Base Function 848

15.2 INHERITANCE DETAILS 849

Functions That Are Not Inherited 850

Assignment Operators and Copy Constructors in Derived Classes 850

Destructors in Derived Classes 851

15.3 POLYMORPHISM 853

Late Binding 853

Virtual Functions in C++ 854

Virtual Functions and Extended Type Compatibility 860

Pitfall: The Slicing Problem 864

Pitfall: Not Using Virtual Member Functions 864

Pitfall: Attempting to Compile Class Definitions Without Definitions for

Every Virtual Member Function 865

Programming Tip: Make Destructors Virtual 866

Chapter Summary 867

Answers to Self-Test Exercises 868

Programming Projects 872

 

Chapter 16 Exception Handling 881

16.1 EXCEPTION-HANDLING BASICS 883

A Toy Example of Exception Handling 883

Defining Your Own Exception Classes 892

Multiple Throws and Catches 892

Pitfall: Catch the More Specific Exception First 896

Programming Tip: Exception Classes Can Be Trivial 897

Throwing an Exception in a Function 898

Exception Specification 898

Pitfall: Exception Specification in Derived Classes 902

16.2 PROGRAMMING TECHNIQUES FOR

EXCEPTION HANDLING 903

When to Throw an Exception 903

Pitfall: Uncaught Exceptions 905

Pitfall: Nested try-catch Blocks 905

Pitfall: Overuse of Exceptions 905

Exception Class Hierarchies 906

Testing for Available Memory 906

Rethrowing an Exception 907

Chapter Summary 907

Answers to Self-Test Exercises 907

Programming Projects 909

 

Chapter 17 Templates 913

17.1 TEMPLATES FOR ALGORITHM ABSTRACTION 914

Templates for Functions 915

Pitfall: Compiler Complications 919

Programming Example: A Generic Sorting Function 921

Programming Tip: How to Define Templates 925

Pitfall: Using a Template with an Inappropriate Type 926

17.2 TEMPLATES FOR DATA ABSTRACTION 927

Syntax for Class Templates 927

Programming Example: An Array Class 930

Chapter Summary 936

Answers to Self-Test Exercises 936

Programming Projects 939

 

Chapter 18 Standard Template Library 943

18.1 ITERATORS 945

Using Declarations 945

Iterator Basics 946

Pitfall: Compiler Problems 951

Kinds of Iterators 952

Constant and Mutable Iterators 956

Reverse Iterators 957

Other Kinds of Iterators 959

18.2 CONTAINERS 960

Sequential Containers 960

Pitfall: Iterators and Removing Elements 965

Programming Tip: Type Definitions in Containers 965

Container Adapters stack and queue 966

Associative Containers set and map 970

Efficiency 976

18.3 GENERIC ALGORITHMS 977

Running Times and Big-O Notation 978

Container Access Running Times 982

Nonmodifying Sequence Algorithms 983

Container Modifying Algorithms 989

Set Algorithms 989

Sorting Algorithms 991

Chapter Summary 991

Answers to Self-Test Exercises 992

Programming Projects 994

 

APPENDICES

1 C++ Keywords 999

2 Precedence of Operators 1000

3 The ASCII Character Set 1002

4 Some Library Functions 1003

5 Inline Functions 1011

6 Overloading the Array Index Square Brackets 1012

7 The this Pointer 1014

8 Overloading Operators as Member Operators 1017

INDEX 1019