1 Overview 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 Thchniques 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
Merging Soutions 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
2 C+++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:ldentifiers 32
Data and Data Types 33
The char Data Type 34
The string Data Type 34
Naming Elements:Declarations 35
Taking Action:Executable Statements 40
2.2 Program Construction 45
Blocks(Compound Statements) 47
The C+++Preprocessor 49
2.3 More About Output 52
Creating Blanks Lines 52
lnserting Blanks Within a Line 53
Programming Example 54
Testing and Debugging 59
Summary 60
Quick Check 60
Exam Preapration Exercises 62
Programming Warm-Up Exercises 64
Programming pROBLEMS 66
Programming Example Follow-Up 67
3 Numeric Types,Expressions,and Output 70
Intergral Types 70
Floating-Point Types 71
3.2 Declarations for Numeric Types 71
Named Constant Declarations 72
Variable Declarations 73
3.3 Simple Arithmertic Expressions 73
Arithmetic Operators 73
lncrement and Decrement Operators 76
3.4 Compound Arithmetic Expressions 77
preccedence Rules 77
Type Coercion and Type Casting 79
3.5 Function Calls and Library Functions 82
Value-Retuning 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
Using Files 122
An Example Program Using Files 125
Run-Time lnput of File Names 127
4.5 lnput 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
Exam Preparation Exercises 144
Programming Warm-Up Exercises 147
Programming Problems 149
Programming Example Follow-Up 151
5 Conditions,Logical Expressions,and Selection Control Structures 153
5.1 Flow of Control 154
Selction 155
5.2 Conditions and Logical Expressions 155
The bool Date Type 156
Logrcal Expressions 156
Preccdence of Operators 163
Relational Operators with Floating-Point Types 164
5.3 The lf Statement 165
The lf-Then-Else Statement 165
Blocks(Compound Statements) 168
The lf-Then Statement 169
A Common Mistake 170
5.4 Nested lf Statements 171
The Dangling ELSE 174
5.5 Testing the State of an l/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
Summary 191
Quick Check 191
Exam Preparation Exercises 192
Programming Warm-Up Exercises 194
Programming problems 196
Programming Example Follow-Up 199
6 Looping 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 Desigh 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
7 Functions 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 Synatx and Semantics of Void Functions 244
Function Call(Invocation) 244
Function Declarations and Definitions 244
Local Variables 246
The Reburn 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 Dierction of Date 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
8 Scope,Lifetime,and More on Functions 279
8.1 Scope of ldentifiers 280
Scope Rules 282
Variable Declarations and Derinitions 285
Namespaces 286
8.2 Lifetime of a Variable 289
lnitializations 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
9 Additional 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
10 Simple Data Types:Bult-ln and User-Defined 347
10.1 Built-in Simple Types 348
Integral Types 350
Floating-Poing Tyers 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 Hnmbers 368
Arithmetic with 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,Araument Passing,and Return of a Functional Value 382
Programming Example 383
Testing and Debugging 390
Floating-Point Data 390
Coping with lnput Errors 391
Testing and Debugging Hints 391
Summary 392
Quick Check 393
Exam Preparation Exercises 394
Programming Warm-Up Excrcises 395
Programming Problems 396
Programming Example Follow-Up 399
11 Structured 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
Class,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
Complilng and Linking a Multifile Program 428
11.8 Guaranteed Initialization with Class Constructors 430
Invoking a Constructor 431
Revised Specification and Implementation Filles for Time 432
Guiedlines 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
12 Arrays 457
12.1 One-Dimensional Arrays 458
Declaring Arrays 460
Accessing lndividual Components 460
Out-of-Bounds Array lndexes 462
lnitializing 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
linedxes 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
lnitialize 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 Multidemensional 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
13 Array-Based LISTS 511
13.1 The List as an Abstract Data Type 512
13.2 Unsorted Lists 519
Basic Operations 519
lnsertion and Deletion 522
Sequential Search 523
lterators 526
Sorting 529
13.3 Sorted Lists 531
Basic Operations 534
lnsertion 534
Sequential Search 537
Binary Search 537
Deletion 543
13.4 Understanding Character Strings 544
lntializing C Strings 547
C String lnput 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
14 Object-Oriented Software Developement 567
14.1 Object-Oriented Programming 568
14.2 Objects 568
14.3 lINHERITANCE 573
Deriving One Class from Another 574
Specification of the ExtTime Class 576
lmplemnetation of the ExtTime Class 579
Avoiding Multiple lnclusion of Header Files 583
14.4 Composition 584
Design of and Entry Class 584
Constructor lnitializer 590
14.5 Dynamic Binding and Vitual Functions 591
The Slicing Problem 592
Virtual Functions 594
14.6 Object-Oriented Desgn 596
Step1:ldentify the Objects and Operations 596
Step2:Determine the Relationships Among Objects 597
Step3:Design the Driver 597
14.7 lmplementing the Design 597
Programming Example 598
Testing and Debugging 608
Testing and Debugging Hints 609
Summaryt 610
Quick Check 610
Exam Preparation Exercises 611
Programming Warm-Up Exercises 614
Programming Problems 616
Programming Example Follow-Up 618
15 Recursion 619
15.1 What is Recursion 620
15.2 Recursive Algorithms with Sample Variables 625
15.3 Towers of Hanoi 626
15.4 Recursive Algorthms with Structured Variables 631
15.5 Recursion or lteration? 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
Inedx 705