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. Contributing author, Kenrick Mock, is an Associate Professor at the University of Alaska Anchorage. He has also taught at Washington State 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 (R) 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.

Table of Location of VideoNotes

Inside front cover and inside back cover

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 Programing 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

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 31

Answers to Self-Test Exercises 32

Programming Projects 35

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 54

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 Expresions 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 68

Pitfall: Whole Numbers in Division 71

More Assignment Statements 73

2.4 Simple Flow of Control 73

A Simple Branching Mechanism 74

Pitfall: Strings of Inequalities 79

Pitfall: Using = in place of == 80

Compound Statements 81

Simple Loop Mechanisms 83

Increment and Decrement Operators 86

Programming Example: Charge Card Balance 88

Pitfall: Infinite Loops 89

2.5 Program Style 92

Indenting 92

Comments 92

Naming Constants 94

Chapter Summary 97

Answers to Self-Test Exercises 97

Programming Projects 102

Chapter 3 More Flow of Control 109

3.1 Using Boolean Expresions 110

Evaluating Boolean Expressions 110

Pitfall: Boolean Expressions Convert to int Values 114

Enumeration Types (Optional) 117

3.2 Multiway Branches 118

Nested Statements 118

Programming Tip: Use Braces in Nested Statements 119

Multiway if-else Statements 121

Programming Example: State Income Tax 123

The switch Statement 126

Pitfall: Forgetting a break in a switch Statement 130

Using switch Statements for Menus 131

Blocks 133

Pitfall: Inadvertent Local Variables 136

3.3 More About C++ Loop Statements 137

The while Statements Reviewed 137

Increment and Decrement Operators Revisited 139

The for Statement 142

Pitfall: Extra Semicolon in a for Statement 147

What Kind of Loop to Use 148

Pitfall: Uninitialized Variables and Infinite Loops 150

The break Statement 151

Pitfall: The break Statement in Nested Loops 152

3.4 Designing Loops 153

Loops for Sums and Products 153

Ending a Loop 155

Nested Loops 158

Debugging Loops 160

Chapter Summary 163

Answers to Self-Test Exercises 164

Programming Projects 170

Chapter 4 Procedural Abstraction and Functions That Return a Value 177

4.1 Top-Down Design 178

4.2 Predefined Functions 179

Using Predefined Functions 179

Random Number Generation 184

Type Casting 186

Older Form of Type Casting 188

Pitfall: Integer Division Drops the Fractional Part 188

4.3 Programer-Defined Functions 189

Function Definitions 189

Functions That Return a Boolean Value 195

Alternate Form for Function Declarations 195

Pitfall: Arguments in the Wrong Order 196

Function Definition Syntax Summary 197

More About Placement of Function Definitions 198

Programming Tip: Use Function Calls in Branching Statements 199

4.4 Procedural Abstraction 200

The Black-Box Analogy 200

Programming Tip: Choosing Formal Parameter Names 203

Programming Tip: Nested Loops 204

Case Study: Buying Pizza 207

Programming Tip: Use Pseudocode 213

4.5 Scope and Local Variables 214

The Small Program Analogy 214

Programming Example: Experimental Pea Patch 217

Global Constants and Global Variables 217

Call-by-Value Formal Parameters Are Local Variables 220

Block Scope 222

Namespaces Revisited 223

Programming Example: The Factorial Function 226

4.6 Overloading Function Names 228

Introduction to Overloading 228

Programming Example: Revised Pizza-Buying Program 231

Automatic Type Conversion 234

Chapter Summary 236

Answers to Self-Test Exercises 236

Programming Projects 241

Chapter 5 Functions for All Subtasks 247

5.1 void Functions 248

Definitions of void Functions 248

Programming Example: Converting Temperatures 251

return Statements in void Functions 251

5.2 Call-By-Reference Parameters 255

A First View of Call-by-Reference 255

Call-by-Reference in Detail 258

Programming Example: The swap_values Function 263

Mixed Parameter Lists 264

Programming Tip: What Kind of Parameter to Use 265

Pitfall: Inadvertent Local Variables 266

5.3 Using Procedural Abstraction 269

Functions Calling Functions 269

Preconditions and Postconditions 271

Case Study: Supermarket Pricing 272

5.4 Testing and Debugging Functions 277

Stubs and Drivers 278

5.5 General Debugging Techniques 283

Keep an Open Mind 283

Check Common Errors 283

Localize the Error 284

The assert Macro 286

Chapter Summary 288

Answers to Self-Test Exercises 289

Programming Projects 292

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

6.1 Streams and Basic File I/O 302

Why Use Files for I/O? 303

File I/O 304

Introduction to Classes and Objects 308

Programming Tip: Check Whether a File Was Opened Successfully 310

Techniques for File I/O 312

Appending to a File (Optional) 316

File Names as Input (Optional) 317

6.2 Tools for Stream I/O 319

Formatting Output with Stream Functions 319

Manipulators 325

Streams as Arguments to Functions 328

Programming Tip: Checking for the End of a File 328

A Note on Namespaces 331

Programming Example: Cleaning Up a File Format 332

6.3 Character I/O 334

The Member Functions get and put 334

The putback Member Function (Optional) 338

Programming Example: Checking Input 339

Pitfall: Unexpected '/n' in Input 341

Programming Example: Another new_line Function 343

Default Arguments for Functions (Optional) 344

The eof Member Function 349

Programming Example: Editing a Text File 351

Predefined Character Functions 352

Pitfall: toupper and tolower Return Values 354

Chapter Summary 356

Answers to Self-Test Exercises 357

Programming Projects 364

Chapter 7 Arrays 373

7.1 Introduction to Arrays 374

Declaring and Referencing Arrays 374

Programming Tip: Use for Loops with Arrays 376

Pitfall: Array Indexes Always Start with Zero 376

Programming Tip: Use a Defined Constant for the

Size of an Array 376

Arrays in Memory 378

Pitfall: Array Index Out of Range 379

Initializing Arrays 381

7.2 Arrays in Functions 383

Indexed Variables as Function Arguments 383

Entire Arrays as Function Arguments 385

The const Parameter Modifier 388

Pitfall: Inconsistent Use of const Parameters 391

Functions That Return an Array 391

Case Study: Production Graph 392

7.3 Programing with Arrays 405

Partially Filled Arrays 405

Programming Tip: Do Not Skimp on Formal Parameters 408

Programming Example: Searching an Array 408

Programming Example: Sorting an Array 411

7.4 Multidimensional Arrays 415

Multidimensional Array Basics 416

Multidimensional Array Parameters 416

Programming Example: Two-Dimensional Grading Program 418

Pitfall: Using Commas Between Array Indexes 422

Chapter Summary 423

Answers to Self-Test Exercises 424

Programming Projects 428

Chapter 8 Strings and Vectors 441

8.1 An Array Type for Strings 443

C-String Values and C-String Variables 443

Pitfall: Using = and == with C Strings 446

Other Functions in 448

C-String Input and Output 453

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

8.2 The Standard string Clas 461

Introduction to the Standard Class string 461

I/O with the Class string 464

Programming Tip: More Versions of getline 467

Pitfall: Mixing cin >> variable; and getline 468

String Processing with the Class string 469

Programming Example: Palindrome Testing 473

Converting Between string Objects and C Strings 476

8.3 Vectors 477

Vector Basics 477

Pitfall: Using Square Brackets Beyond the Vector Size 480

Programming Tip: Vector Assignment Is Well Behaved 481

Efficiency Issues 481

Chapter Summary 483

Answers to Self-Test Exercises 484

Programming Projects 486

Chapter 9 Pointers and Dynamic Arrays 493

9.1 Pointers 494

Pointer Variables 495

Basic Memory Management 502

Pitfall: Dangling Pointers 503

Static Variables and Automatic Variables 504

Programming Tip: Define Pointer Types 504

9.2 Dynamic Arrays 507

Array Variables and Pointer Variables 507

Creating and Using Dynamic Arrays 508

Pointer Arithmetic (Optional) 514

Multidimensional Dynamic Arrays (Optional) 516

Chapter Summary 518

Answers to Self-Test Exercises 518

Programming Projects 519

Chapter 10 Defining Classes 525

10.1 Structures 526

Structures for Diverse Data 526

Pitfall: Forgetting a Semicolon in a Structure Definition 531

Structures as Function Arguments 532

Programming Tip: Use Hierarchical Structures 533

Initializing Structures 535

10.2 Classes 538

Defining Classes and Member Functions 538

Public and Private Members 543

Programming Tip: Make All Member Variables Private 551

Programming Tip: Define Accessor and Mutator Functions 551

Programming Tip: Use the Assignment Operator with Objects 553

Programming Example: BankAccount Class Version 1 554

Summary of Some Properties of Classes 558

Constructors for Initialization 560

Programming Tip: Always Include a Default Constructor 568

Pitfall: Constructors with No Arguments 569

10.3 Abstract Data Types 571

Classes to Produce Abstract Data Types 572

Programming Example: Alternative Implementation of a Class 576

10.4 Introduction to Inheritance 581

Derived Classes 582

Defining Derived Classes 583

Chapter Summary 587

Answers to Self-Test Exercises 588

Programming Projects 594

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

11.1 Friend Functions 602

Programming Example: An Equality Function 602

Friend Functions 606

Programming Tip: Define Both Accessor Functions and Friend Functions 608

Programming Tip: Use Both Member and Nonmember Functions 610

Programming Example: Money Class (Version 1) 610

Implementation of digit_to_int (Optional) 617

Pitfall: Leading Zeros in Number Constants 618

The const Parameter Modifier 620

Pitfall: Inconsistent Use of const 621

11.2 Overloading Operators 625

Overloading Operators 626

Constructors for Automatic Type Conversion 629

Overloading Unary Operators 631

Overloading >> and << 632

11.3 Arrays and Classes 642

Arrays of Classes 642

Arrays as Class Members 646

Programming Example: A Class for a Partially Filled Array 647

11.4 Classes and Dynamic Arrays 649

Programming Example: A String Variable Class 650

Destructors 653

Pitfall: Pointers as Call-by-Value Parameters 656

Copy Constructors 657

Overloading the Assignment Operator 662

Chapter Summary 665

Answers to Self-Test Exercises 665

Programming Projects 675

Chapter 12 Separate Compilation and Namespaces 685

12.1 Separate Compilation 686

ADTs Reviewed 687

Case Study: DigitalTime A Class Compiled Separately 688

Using #ifndef 697

Programming Tip: Defining Other Libraries 700

12.2 Namespaces 701

Namespaces and using Directives 701

Creating a Namespace 703

Qualifying Names 706

A Subtle Point About Namespaces (Optional) 707

Unnamed Namespaces 708

Programming Tip: Choosing a Name for a Namespace 713

Pitfall: Confusing the Global Namespace and the Unnamed Namespace 714

Chapter Summary 715

Answers to Self-Test Exercises 716

Programming Projects 718

Chapter 13 Pointers and Linked Lists 721

13.1 Nodes and Linked Lists 722

Nodes 722

Linked Lists 728

Inserting a Node at the Head of a List 729

Pitfall: Losing Nodes 732

Searching a Linked List 733

Pointers as Iterators 735

Inserting and Removing Nodes Inside a List 737

Pitfall: Using the Assignment Operator with Dynamic Data Structures 740

Variations on Linked Lists 741

Linked Lists of Classes 744

13.2 Stacks and Queues 747

Stacks 747

Programming Example: A Stack Class 748

Queues 753

Programming Example: A Queue Class 754

Chapter Summary 758

Answers to Self-Test Exercises 758

Programming Projects 761

Chapter 14 Recursion 769

14.1 Recursive Functions for Tasks 771

Case Study: Vertical Numbers 771

A Closer Look at Recursion 777

Pitfall: Infinite Recursion 779

Stacks for Recursion 780

Pitfall: Stack Overflow 782

Recursion Versus Iteration 782

14.2 Recursive Functions for Values 784

General Form for a Recursive Function That Returns a Value 784

Programming Example: Another Powers Function 784

14.3 Thinking Recursively 789

Recursive Design Techniques 789

Case Study: Binary Search An Example of Recursive Thinking 790

Programming Example: A Recursive Member Function 798

Chapter Summary 802

Answers to Self-Test Exercises 802

Programming Projects 807

Chapter 15 Inheritance 811

15.1 Inheritance Basics 812

Derived Classes 813

Constructors in Derived Classes 821

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

Pitfall: Private Member Functions Are Effectively Not Inherited 826

The protected Qualifier 826

Redefinition of Member Functions 829

Redefining Versus Overloading 832

Access to a Redefined Base Function 834

15.2 INHERITANCE DETAILS 835

Functions That Are Not Inherited 835

Assignment Operators and Copy Constructors in Derived Classes 836

Destructors in Derived Classes 837

15.3 Polymorphism 838

Late Binding 839

Virtual Functions in C++ 840

Virtual Functions and Extended Type Compatibility 845

Pitfall: The Slicing Problem 849

Pitfall: Not Using Virtual Member Functions 850

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

Programming Tip: Make Destructors Virtual 851

Chapter Summary 853

Answers to Self-Test Exercises 853

Programming Projects 857

Chapter 16 Exception Handling 867

16.1 Exception-Handling Basics 869

A Toy Example of Exception Handling 869

Defining Your Own Exception Classes 878

Multiple Throws and Catches 878

Pitfall: Catch the More Specific Exception First 882

Programming Tip: Exception Classes Can Be Trivial 883

Throwing an Exception in a Function 883

Exception Specification 885

Pitfall: Exception Specification in Derived Classes 887

16.2 Programing Techniques for Exception Handling 888

When to Throw an Exception 888

Pitfall: Uncaught Exceptions 890

Pitfall: Nested try-catch Blocks 890

Pitfall: Overuse of Exceptions 890

Exception Class Hierarchies 891

Testing for Available Memory 891

Rethrowing an Exception 892

Chapter Summary 892

Answers to Self-Test Exercises 892

Programming Projects 894

Chapter 17 Templates 899

17.1 Templates for Algorithm Abstraction 900

Templates for Functions 901

Pitfall: Compiler Complications 905

Programming Example: A Generic Sorting Function 907

Programming Tip: How to Define Templates 911

Pitfall: Using a Template with an Inappropriate Type 912

17.2 Templates for Data Abstraction 913

Syntax for Class Templates 913

Programming Example: An Array Class 916

Chapter Summary 922

Answers to Self-Test Exercises 922

Programming Projects 925

Chapter 18 Standard Template Library 931

18.1 Iterators 933

using Declarations 933

Iterator Basics 934

Pitfall: Compiler Problems 938

Kinds of Iterators 940

Constant and Mutable Iterators 944

Reverse Iterators 945

Other Kinds of Iterators 946

18.2 Containers 947

Sequential Containers 948

Pitfall: Iterators and Removing Elements 952

Programming Tip: Type Definitions in Containers 953

Container Adapters stack and queue 953

Associative Containers set and map 957

Efficiency 964

18.3 Generic Algorithms 965

Running Times and Big-O Notation 965

Container Access Running Times 970

Nonmodifying Sequence Algorithms 971

Container Modifying Algorithms 975

Set Algorithms 977

Sorting Algorithms 978

Chapter Summary 979

Answers to Self-Test Exercises 979

Programming Projects 981

Appendices

1 C++ Keywords 987

2 Precedence of Operators 988

3 The ASCII Character Set 990

4 Some Library Functions 991

5 Inline Functions 998

6 Overloading the Array Index Square Brackets 999

7 The this Pointer 1001

8 Overloading Operators as Member Operators 1004

Index 1006