1Overview of Programming and Problem Solving 1
1.1 Overview of Programming 2
What Is Programming? 2
How Do We Write a Program? 2
1.2 What Is a Programming Language? 7
1.3 What Is a Computer? 11
1.4 Ethics and Responsibilities in the Computing Profession 15
Software Piracy 15
Privacy of Data 16
Use of Computer Resources 16
Software Engineering 17
1.5 Problem-Solving Techniques 17
Ask Questions 18
Look for Things That Are Familiar 19
Solve by Analogy 19
Means-Ends Analysis 19
Divide and Conquer 20
The Building-Block Approach 20
Merging Solutions 21
Mental Blocks: The Fear of Starting 22
Algorithmic Problem Solving 22
Summary 22
2C++Syntax and Semantics, and the Program Development Process 25
2.1 The Elements of C++ Programs 26
C++ Program Structure 26
Syntax and Semantics 28
Syntax Templates 30
Naming Program Elements: Identifiers 31
Data and Data Types 33
Naming Elements: Declarations 34
Taking Action: Executable Statements 38
Beyond Minimalism: Adding Comments to a Program 43
2.2 Program Construction 44
Blocks （Compound Statements） 46
The C++Preprocessor 47
An Introduction to Namespaces 49
2.3 More About Output 50
Creating Blank Lines 50
Inserting Blanks Within a Line 51
Programming Example: Contest Letter 53
Testing and Debugging 57
Summary 59
Quick Check 59
Exam Preparation Exercises 62
Programming Wann-up Exercises 65
Programming Problems 67
3Numeric Types, Expressions, and Output 69
3.1 Overview of C++Data Types 70
3.2 Numeric Data Types 70
Integral Types 71
Floating-Point Types 72
3.3 Declarations for Numeric Types 73
Named Constant Declarations 73
Variable Declarations 74
3.4 Simple Arithmetic Expressions 74
Arithmetic Operators 75
Increment and Decrement Operators 78
3.5 Compound Arithmetic Expressions 78
Precedence Rules 79
Type Coercion and Type Casting 80
3.6 Function Calls and Library Functions 83
Value-Retuming Functions 83
Library Functions 85
Void Functions 86
3.7 Formatting the Output 87
Integers and Strings 87
Floating-Point Numbers 90
3.8 Additional string Operations 94
The length and size Functions 94
The find Function 95
The substr Function 97
Programming Example: Map Measurements 99
Testing and Debugging 102
Summary 103
Quick Check 103
Exam Preparation Exercises 106
Programming Warm-up Exercises 109
Programming Problems 113
4Program Input and the Software Design Process 115
4.1 Getting Data into Programs 116
Input Streams and the Extraction Operator （>>） 116
The Reading Marker and the Newline Character 119
Reading Character Data with the get Function 120
Skipping Characters with the ignore Function 122
Reading String Data 123
4.2 Interactive Input/Output 125
4.3 Noninteractive Input/Output 126
4.4 File Input and Output 127
Files 127
Using Files 127
An Example Program Using Files 130
Run-Time Input of File Names 133
4.5 Input Failure 134
4.6 Software Design Methodologies 135
4.7 What Are Objects? 136
4.8 Object-Oriented Design 138
4.9 Functional Decomposition 138
Modules 140
A Perspective on Design 141
Programming Example: Stretching a Canvas 142
Testing and Debugging 147
Testing and Debugging Hints 148
Summary 149
Quick Check 150
Exam Preparation Exercises 151
Programming Warm-up Exercises 153
Programming Problems 155
5Conditions, Logical Expressions, and Selection Control Structures 157
5.1 Flow of Control 158
Selection 159
5.2 Conditions and Logical Expressions 159
The bool Data Type 159
Logical Expressions 160
Precedence of Operators 166
Relational Operators with Floating-Point Types 167
5.3 The If Statement 168
The If-Then-Else Form 169
Blocks （Compound Statements） 170
The If-Then Form 172
A Common Mistake 173
5.4 Nested If Statements 174
The Dangling else 176
5.5 Testing the State of an I/O Stream 178
Programming Example: Warning Notices 180
Testing and Debugging 183
Testing in the Problem-Solving Phase: The Algorithm Walk-Through 184
Testing in the Implementation Phase 186
The Test Plan 191
Tests Performed Automatically During Compilation and Execution 192
Testing and Debugging Hints 193
Summary 195
Quick Check 195
Exam Preparation Exercises 196
Programming Warm-up Exercises 199
Programming Problems 202
6Looping 205
6.1 The While Statement 206
6.2 Phases of Loop Execution 208
6.3 Loops Using the While Statement 208
Count-Controlled Loops 209
Event-Controlled Loops 209
Looping Subtasks 212
6.4 How to Design Loops 214
Designing the Flow of Control 215
Designing the Process Within the Loop 216
The Loop Exit 217
6.5 Nested Logic 217
Designing Nested Loops 219
Programming Example: Average Income by Gender 220
Testing and Debugging 223
Loop-Testing Strategy 223
Test Plans Involving Loops 224
Testing and Debugging Hints 225
Summary 227
Quick Check 227
Exam Preparation Exercises 228
Programming Warm-up Exercises 231
Programming Problems 232
7Functions 235
7.1 Functional Decomposition with Void Functions 236
Writing Modules as Void Functions 236
7.2 An Overview of User-Defined Functions 239
Flow of Control in Function Calls 239
Function Parameters 240
7.3 Syntax and Semantics of Void Functions 241
Function Call （Invocation） 241
Function Declarations and Denitions 242
Local Variables 244
The Return Statement 245
Header Files 246
7.4 Parameters 247
Value Parameters 248
Reference Parameters 249
7.5 Designing Functions 250
Writing Assertions as Program Comments 252
Documenting the Direction of Data Flow 254
Programming Example: Comparison of Furniture-Store Sales 257
Testing and Debugging 263
The assert Library Function 265
Testing and Debugging Hints 266
Summary 267
Quick Check 268
Exam Preparation Exercises 269
Programming Warm-up Exercises 275
Programming Problems 277
8Scope, Lifetime, and More on Functions 281
8.1 Scope of Identifiers 282
Scope Rules 284
Variable Declarations and Definitions 287
Namespaces 288
8.2 Lifetime of a Variable 291
Initializations in Declarations 292
8.3 Interface Design 293
Side Effects 294
Global Constants 294
8.4 Value-Returning Functions 295
Boolean Functions 299
Interface Design for Value-Retuming Functions 300
When to Use Value-Retuming Functions 300
Programming Example: Starship Weight and Balance 302
Testing and Debugging 310
Stubs and Drivers 310
Testing and Debugging Hints 311
Summary 312
Quick Check 312
Exam Preparation Exercises 313
Programming Warm-up Exercises 317
Programming Problems 319
9Additional Control Structures 323
9.1 The Switch Statement 324
9.2 The Do-While Statement 327
9.3 The For Statement 330
9.4 The Break and Continue Statements 332
9.5 Guidelines for Choosing a Looping Statement 335
Programming Example: Monthly Rainfall Averages 336
Testing and Debugging 340
Testing and Debugging Hints 340
Summary 341
Quick Check 341
Exam Preparation Exercises 342
Programming Warm-up Exercises 344
Programming Problems 346
10Simple Data Types: Built-In and User-Defined 349
10.1 Built-In Simple Types 350
Integral Types 352
Floating-Point Types 353
10.2 Additional C+++ Operators 354
Assignment Operators and Assignment Expressions 356
Increment and Decrement Operators 357
Bitwise Operators 358
The Cast Operation 358
The sizeof Operator 358
The ? : Operator 359
Operator Precedence 359
10.3 Working with Character Data 360
Character Sets 361
C++ char Constants 362
Programming Techniques 363
10.4 More on Floating-Point Numbers 367
Representation of Floating-Point Numbers 367
Arithmetic with Floating-Point Numbers 370
10.5 User-Defined Simple Types 372
The Typedef Statement 372
Enumeration Types 373
Named and Anonymous Data Types 379
User-Written Header Files 380
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 Function Value 382
Programming Example: Rock, Paper, Scissors 384
Testing and Debugging 391
Floating-Point Data 391
Coping with Input Errors 391
Testing and Debugging Hints 392
Summary 393
Quick Check 393
Exam Preparation Exercises 395
Programming Warm-up Exercises 397
Programming Problems 398
11Structured Types, Data Abstraction, and Classes 401
11.1 Simple Versus Structured Data Types 402
11.2 Records （C++ Structs） 403
Accessing Individual Components 405
Aggregate Operations on Structs 407
More About Struct Declarations 409
Hierarchical Records 409
11.3 Unions 412
11.4 Data Abstraction 413
11.5 Abstract Data Types 415
11.6 C++ Classes 417
Classes, Class Objects, and Class Members 419
Built-in Operations on Class Objects 421
Class Scope 423
Information Hiding 423
11.7 Specification and Implementation Files 425
The Specification File 425
The Implementation File 427
Compiling and Linking a Multifile Program 431
11.8 Guaranteed Initialization with Class Constructors 434
Invoking a Constructor 435
Revised Specification and Implementation Files for TimeType 436
Guidelines for Using Class Constructors 438
Programming Example: Manipulating Dates 440
Programming Example: Birthday Calls 449
Testing and Debugging 456
Testing and Debugging Hints 459
Summary 460
Quick Check 461
Exam Preparation Exercises 464
Programming Warm-up Exercises 468
Programming Problems 470
12Arrays 475
12.1 One-Dimensional Arrays 476
Declaring Arrays 478
Accessing Individual Components 479
Out-of-Bounds Array Indexes 481
Initializing Arrays in Declarations 482
（Lack of） Aggregate Array Operations 483
Examples of Declaring and Accessing Arrays 484
Passing Arrays as Arguments 487
Assertions About Arrays 489
Using Typedef with Arrays 490
12.2 Arrays of Records and Class Objects 490
Arrays of Records 491
Arrays of Class Objects 492
12.3 Special Kinds of Array Processing 493
Subarray Processing 493
Indexes with Semantic Content 494
12.4 Two-Dimensional Arrays 494
12.5 Processing Two-Dimensional Arrays 498
Sum the Rows 499
Sum the Columns 500
Initialize the Array 501
Print the Array 502
12.6 Passing Two-Dimensional Arrays as Arguments 503
12.7 Another Way of Defining Two-Dimensional Arrays 505
12.8 Multidimensional Arrays 507
Programming Example: Comparison of Two Lists 510
Programming Example: City Council Election 515
Testing and Debugging 523
One-Dimensional Arrays 523
Complex Structures 524
Multidimensional Arrays 525
Testing and Debugging Hints 526
Summary 527
Quick Check 528
Exam Preparation Exercises 531
Programming Warm-up Exercises 536
Programming Problems 539
13Array-Based Lists 545
13.1 The List as an Abstract Data Type 546
13.2 Unsorted Lists 550
Basic Operations 550
Insertion and Deletion 552
Sequential Search 554
Sorting 555
13.3 Sorted Lists 558
Basic Operations 561
Insertion 561
Sequential Search 564
Binary Search 565
Deletion 570
13.4 Understanding Character Strings 572
Initializing C Strings 574
C String Input and Output 575
C String Library Routines 579
String Class or C Strings? 580
Programming Example: Exam Attendance 581
Testing and Debugging 587
Testing and Debugging Hints 588
Summary 588
Quick Check 589
Exam Preparation Exercises 590
Programming Warm-up Exercises 592
Programming Problems 594
14Object-Oriented Software Development 597
14.1 Object-Oriented Programming 598
14.2 Objects 600
14.3 Inheritance 601
Deriving One Class from Another 602
Specification of the ExtTime Class 606
Implementation of the ExtTime Class 608
Avoiding Multiple Inclusion of Header Files 612
14.4 Composition 613
Design of a TimeCard Class 613
Implementation of the TimeCard Class 614
14.5 Dynamic Binding and Virtual Functions 617
The Slicing Problem 618
Virtual Functions 620
14.6 Object-Oriented Design 622
Step 1: ldentify the Objects and Operations 622
Step 2: Determine the Relationships Among Objects 623
Step 3: Design the Driver 624
14.7 Implementing the Design 625
Programming Example: Time Card Lookup 626
Testing and Debugging 645
Testing and Debugging Hints 645
Summary 647
Quick Check 647
Exam Preparation Exercises 650
Programming Warm-up Exercises 651
Programming Problems 653
15Recursion 655
15.1 What Is Recursion? 656
15.2 Towers of Hanoi 660
15.3 Recursive Algorithms with Structured Variables 665
15.4 Recursion or Iteration? 666
Testing and Debugging 668
Testing and Debugging Hints 668
Summary 669
Quick Check 669
Exam Preparation Exercises 669
Programming Warm-up Exercises 671
Programming Problems 672
Appendix A Reserved Words 673
Appendix B Operator Precedence 673
Appendix C A Selection of Standard Library Routines 675
Appendix D Using This Book with a Prestandard Version of C＋＋ 684
Appendix E Character Sets 689
Appendix F Program Style, Formatting, and Documentation 692
Glossary 699
Answers to Selected Exercises 707
Index 729