1Overview of Programming and Problem Solving 1
1.1 Overview of Programming 2
How Do We Write a Program? 2
1.2 What is a Programming Language? 6
1.3 What is a Computer? 11
1.4 Problem-Solving Techniques 14
Ask Questions 15
Look For Things That Are Familiar 15
Solve by Analogy 15
Means-Ends Analysis 16
Divide and Conquer 17
The Building-Block Approach 18
Merging Solutions 18
Mental Blocks: The Fear of Starting 19
Algorithmic Problem Solving 19
Summary 20
Quick Check 21
Exam Preparation Exercises 21
Programming Warm-Up Exercises 23
2C++ Syntax and Semantics, and the Program Development Process 25
2.1 The Elements of C++ Programs 26
Syntax and Semantics 28
Syntax Templates 30
Naming Program Elements: Identiers 32
Data and Data Types 33
Data Storage 34
The char Data Type 34
The string Data Type 34
Naming Elements: Declarations 35
Taking Action: Executable Statements 40
Beyond Minimalism: Adding Comments to a Program 44
2.2 Program Construction 45
Blocks （Compound Statements） 47
The C++ Preprocessor 49
An Introduction to Namespaces 50
2.3 More About Output 52
Creating Blank Lines 52
Inserting Blanks Within a Line 53
Programming Example 54
Testing and Debugging 59
Summary 60
Quick Check 60
Exam Preparation Exercises 62
Programming Warm-Up Exercises 64
Programming Problems 66
Programming Example Follow-Up 67
3Numeric Types, Expressions, and Output 70
Integral Types 70
Floating-Point Types 71
3.2 Declarations for Numeric Types 71
Named Constant Declarations 72
Variable Declarations 73
3.3 Simple Arithmetic Expressions 73
Arithmetic Operators 73
Increment and Decrement Operators 76
3.4 Compound Arithmetic Expressions 77
Precedence Rules 77
Type Coercion and Type Casting 79
3.5 Function Calls and Library Functions 82
Value-Returning Functions 82
Library Functions 84
Void Functions 85
3.6 Formatting the Output 86
3.7 Additional string Operations 92
The length and size Functions 92
The find Function 94
The substr Function 95
Programming Example 97
Testing and Debugging 100
Summary 100
Quick Check 101
Exam Preparation Exercises 102
Programming Warm-Up Exercises 104
Programming Problems 105
Programming Example Follow-Up 107
4Program Input and the Software Design Process 109
4.1 Getting Data into Programs 110
Input Streams and the Extraction Operator （＞＞） 110
The Reading Marker and the Newline Character 113
Reading Character Data with the get Function 114
Skipping Characters with the ignore Function 116
Reading String Data 117
4.2 Interactive Input/Output 118
4.3 Noninteractive Input/Output 120
4.4 File Input and Output 121
Files 121
Using Files 122
An Example Program Using Files 125
Run-Time Input of File Names 127
4.5 Input Failure 128
4.6 Software Design Methodologies 130
4.7 What Are Objects 131
4.8 Object-Oriented Design 132
4.9 Functional Decomposition 133
Modules 135
Programming Example 137
Testing and Debugging 141
Testing and Debugging Hints 142
Summary 143
Quick Check 144
Exam Preparation Exercises 144
Programming Warm-Up Exercises 147
Programming Problems 149
Programming Example Follow-Up 151
5Conditions, Logical Expressions, and Selection Control Structures 153
5.1 Flow of Control 154
Selection 155
5.2 Conditions and Logical Expressions 155
The bool Data Type 156
Logical Expressions 156
Precedence of Operators 163
Relational Operators with Floating-Point Types 164
5.3 The If Statement 165
The If-Then-Else Statement 165
Blocks （Compound Statements） 168
The If-Then Statement 169
A Common Mistake 170
5.4 Nested If Statements 171
The Dangling else 174
5.5 Testing the State of an I/O System 175
Programming Example 177
Testing and Debugging 182
Testing in the Problem-Solving Phase: The Algorithm Walk-Through 182
Testing in the Implementation Phase 185
Tests Performed Automatically During Compilation and Execution 189
Testing and Debugging Hints 189
Summary 191
Quick Check 191
Exam Preparation Exercises 192
Programming Warm-Up Exercises 194
Programming Problems 196
Programming Example Follow-Up 199
6Looping 201
6.1 The While Statement 202
6.2 Phases of Loop Execution 203
6.3 Loops Using the While Statement 204
Count-Controlled Loops 204
Event-Controlled Loops 205
Looping Subtasks 209
6.4 How to Design Loops 211
Designing the Flow of Control 212
Designing the Process Within the loop 213
The Loop Exit 213
6.5 Nested Logic 214
Designing Nested Loops 215
Programming Example 216
Testing and Debugging 224
Loop-Testing Strategy 224
Testing and Debugging Hints 225
Summary 226
Quick Check 227
Exam Preparation Exercises 228
Programming Warm-Up Exercises 231
Programming Problems 233
Programming Example Follow Up 236
7Functions 237
7.1 Functional Decomposition with Void Functions 238
Writing Modules as Void Functions 238
7.2 An Overview of User-Defined Functions 241
Flow of Control in Function Calls 242
Function Parameters 242
7.3 Syntax and Semantics of Void Functions 244
Function Call （Invocation） 244
Function Declarations and Definitions 244
Local Variables 246
The Return Statement 247
Header Files 248
7.4 Parameters 249
Value Parameters 249
Reference Parameters 251
Matching Arguments with Parameters 251
7.5 Designing Functions 254
Writing Assertions as Program Comments 256
Documenting the Direction of Data Flow 257
Programming Example 260
Testing and Debugging 264
The assert Library Function 265
Testing and Debugging Hints 267
Summary 268
Quick Check 268
Exam Preparation Exercises 269
Programming Warm-Up Exercises 271
Programming Problems 273
Programming Example Follow-Up 277
8Scope, Lifetime, and More on Functions 279
8.1 Scope of Identifiers 280
Scope Rules 282
Variable Declarations and Definitions 285
Namespaces 286
8.2 Lifetime of a Variable 289
Initializations in Declarations 290
8.3 Interface Design 291
Side Effects 291
Global Constants 293
8.4 Value-Returning Functions 293
Boolean Functions 296
Interface Design and Side Effects 298
When to Use Value-Returning Functions 298
Programming Example 300
Testing and Debugging 307
Stubs and Drivers 308
Testing and Debugging Hints 308
Summary 309
Quick Check 310
Exam Preparation Exercises 311
Programming Warm-Up Exercises 313
Programming Problems 315
Programming Example Follow-Up 318
9Additional Control Structures 319
9.1 The Switch Statement 320
9.2 The Do-While Statement 324
9.3 The For Statement 325
9.4 The Break and Continue Statements 329
9.5 Guidelines for Choosing a Looping Statement 332
Programming Example 333
Testing and Debugging 338
Testing and Debugging Hints 338
Summary 339
Quick Check 339
Exam Preparation Exercises 340
Programming Warm-Up Exercises 342
Programming Problems 343
Programming Example Follow-Up 346
10Simple Data Types: Built-In and User-Defined 347
10.1 Built-In Simple Types 348
Integral Types 350
Floating-Point Types 351
10.2 Additional C++ Operators 352
Assignment Operators and Assignment Expressions 354
Increment and Decrement Operators 354
Bitwise Operators 355
The Cast Operation 356
The sizeof Operator 356
The ?: Operator 357
Operator Precedence 357
10.3 Working With Character Data 359
Character Sets 359
C++ char Constants 360
Programming Techniques 361
10.4 More on Floating-Point Numbers 367
Representation of Floating-Point Numbers 368
Arithmeticwith Floating-Point Numbers 370
10.5 User-Defined Simple Types 373
The Typedef Statement 373
Enumeration Types 373
Named and Anonymous Data Types 379
User-Written Header Files 379
10.6 More on Type Coercion 380
Type Coercion in Arithmetic and Relational Expressions 381
Type Coercion in Assignments, Argument Passing, and Return of a Functional Value 382
Programming Example 383
Testing and Debugging 390
Floating-Point Data 390
Coping with Input Errors 391
Testing and Debugging Hints 391
Summary 392
Quick Check 393
Exam Preparation Exercises 394
Programming Warm-Up Exercises 395
Programming Problems 396
Programming Example Follow-Up 399
11Structured Types, Data Abstraction, and Classes 401
11.1 Structured Data Types 402
11.2 Records （Structs） 403
Accessing Individual Components 405
Aggregate Operations on Structs 406
Hierarchical Records 408
11.3 Unions 410
11.4 Data Abstraction 411
11.5 Abstract Data Types 411
11.6 C++ Classes 414
Classes, Class Objects, and Class Members 416
Built-In Operations on Class Objects 416
Class Scope 419
Information Hiding 419
11.7 Specification and Implementation Files 421
The Specification File 421
The Implementation File 423
Compiling and Linking a Multifile Program 428
11.8 Guaranteed Initialization with Class Constructors 430
Invoking a Constructor 431
Revised Specication and Implementation Files for Time 432
Guidelines for Using Class Constructors 436
Programming Example 437
Testing and Debugging 444
Testing and Debugging Hints 447
Summary 448
Quick Check 449
Exam Preparation Exercises 450
Programming Warm-Up Exercises 452
Programming Problems 453
Programming Example Follow-Up 456
12Arrays 457
12.1 One-Dimensional Arrays 458
Declaring Arrays 460
Accessing Individual Components 460
Out-of-Bounds Array Indexes 462
Initializing Arrays in Declarations 464
Examples of Declaring and Accessing Arrays 464
Passing Arrays as Arguments 469
Assertions About Arrays 471
Using Typedef with Arrays 471
12.2 Arrays of Records and Objects 471
Arrays of Records 472
Arrays of Class Objects 473
12.3 Special Kinds of Array Processing 474
Subarray Processing 474
Indexes with Semantic Content 475
12.4 Two-Dimensional Arrays 475
12.5 Processing Two-Dimensional Arrays 478
Sum the Rows 479
Sum the Columns 481
Initialize the Array 481
Print the Array 483
12.6 Passing Two-Dimensional Arrays as Arguments 484
12.7 Another Way of Defining Two-Dimensional Arrays 486
12.8 Multidimensional Arrays 488
Programming Example 491
Testing and Debugging 498
One-Dimensional Arrays 498
Multidimensional Arrays 499
Testing and Debugging Hints 500
Summary 501
Quick Check 502
Exam Preparation Exercises 503
Programming Warm-Up Exercises 506
Programming Problems 508
Programming Example Follow-Up 510
13Array-Based Lists 511
13.1 The List as an Abstract Data Type 512
13.2 Unsorted Lists 519
Basic Operations 519
Insertion and Deletion 522
Sequential Search 523
lterators 526
Sorting 528
13.3 Sorted Lists 531
Basic Operations 534
Insertion 534
Sequential Search 537
Binary Search 537
Deletion 543
13.4 Understanding Character Strings 544
Initializing C Strings 547
C String Input and Output 547
C String Library Routines 550
Programming Example 552
Testing and Debugging 559
Testing and Debugging Hints 560
Summary 560
Quick Check 561
Exam Preparation Exercises 561
Programming Warm-Up Exercises 562
Programming Problems 564
Programming Example Follow-Up 565
14Object-Oriented Software Development 567
14.1 Object-Oriented Programming 568
14.2 Objects 568
14.3 Inheritance 573
Deriving One Class from Another 574
Specification of the ExtTime Class 576
Implementation of the ExtTime Class 579
Avoiding Multiple Inclusion of Header Files 583
14.4 Composition 584
Design of an Entry Class 584
Constructor lnitializer 590
14.5 Dynamic Binding and Virtual Functions 591
The Slicing Problem 592
Virtual Functions 594
14.6 Object-Oriented Design 596
Step 1: Identify the Objects and Operations 596
Step 2: Determine the Relationships Among Objects 597
Step 3: Design the Driver 597
14.7 Implementing the Design 597
Programming Example 598
Testing and Debugging 608
Testing and Debugging Hints 609
Summary 610
Quick Check 610
Exam Preparation Exercises 611
Programming Warm-Up Exercises 614
Programming Problems 616
Programming Example Follow-Up 618
15Recursion 619
15.1 What Is Recursion 620
15.2 Recursive Algorithms with Sample Variables 624
15.3 Towers of Hanoi 626
15.4 Recursive Algorithms with Structured Variables 631
15.5 Recursion or Iteration? 632
Testing and Debugging 634
Testing and Debugging Hints 634
Summary 635
Quick Check 635
Exam Preparation Exercises 635
Programming Warm-Up Exercises 637
Programming Problems 640
Glossary 643
Answers to Selected Exercises 651
Appendices 683
Index 705