Problem Solving with C++

Cover......Page 1
Title......Page 5
Copyright......Page 6
Contents......Page 17
Chapter 1 Introduction to Computers and C++ Programming......Page 33
  Hardware......Page 34
  Software......Page 39
  High-Level Languages......Page 40
  Compilers......Page 41
  Algorithms......Page 44
  Program Design......Page 47
  Object-Oriented Programming......Page 48
  The Software Life Cycle......Page 49
  Origins of the C++ Language......Page 50
  A Sample C++ Program......Page 51
  Programming Tip: Input and Output Syntax......Page 55
  Layout of a Simple C++ Program......Page 56
  Compiling and Running a C++ Program......Page 58
  Programming Tip: Getting Your Program to Run......Page 59
 1.4 Testing and Debugging......Page 61
  Kinds of Program Errors......Page 62
  Pitfall: Assuming Your Program Is Correct......Page 63
  Chapter Summary......Page 64
  Answers to Self-Test Exercises......Page 65
  Practice Programs......Page 67
  Programming Projects......Page 68
Chapter 2 C++ Basics......Page 71
  Variables......Page 72
  Names: Identifiers......Page 74
  Variable Declarations......Page 76
  Assignment Statements......Page 77
  Pitfall: Uninitialized Variables......Page 79
  Programming Tip: Use Meaningful Names......Page 81
  Output Using cout......Page 82
  Include Directives and Namespaces......Page 84
  Escape Sequences......Page 85
  Formatting for Numbers with a Decimal Point......Page 87
  Input Using cin......Page 88
  Programming Tip: Line Breaks in I/O......Page 90
  The Types int and double......Page 92
  Other Number Types......Page 94
  C++11 Types......Page 95
  The Type char......Page 96
  Introduction to the Class string......Page 98
  Type Compatibilities......Page 100
  Arithmetic Operators and Expressions......Page 101
  Pitfall: Whole Numbers in Division......Page 104
 2.4 Simple Flow of Control......Page 106
  A Simple Branching Mechanism......Page 107
  Pitfall: Strings of Inequalities......Page 112
  Pitfall: Using = in place of ==......Page 113
  Compound Statements......Page 114
  Simple Loop Mechanisms......Page 116
  Increment and Decrement Operators......Page 119
  Programming Example: Charge Card Balance......Page 121
  Pitfall: Infinite Loops......Page 122
  Comments......Page 125
  Naming Constants......Page 127
  Answers to Self-Test Exercises......Page 130
  Practice Programs......Page 135
  Programming Projects......Page 137
Chapter 3 More Flow of Control......Page 143
  Evaluating Boolean Expressions......Page 144
  Pitfall: Boolean Expressions Convert to int Values......Page 148
  Enumeration Types (Optional)......Page 151
  Nested Statements......Page 152
  Programming Tip: Use Braces in Nested Statements......Page 153
  Multiway if-else Statements......Page 155
  Programming Example: State Income Tax......Page 157
  The switch Statement......Page 160
  Pitfall: Forgetting a break in a switch Statement......Page 164
  Using switch Statements for Menus......Page 165
  Blocks......Page 167
  Pitfall: Inadvertent Local Variables......Page 170
  The while Statements Reviewed......Page 171
  Increment and Decrement Operators Revisited......Page 173
  The for Statement......Page 176
  Pitfall: Extra Semicolon in a for Statement......Page 181
  What Kind of Loop to Use......Page 182
  Pitfall: Uninitialized Variables and Infinite Loops......Page 184
  Pitfall: The break Statement in Nested Loops......Page 186
  Loops for Sums and Products......Page 187
  Ending a Loop......Page 189
  Nested Loops......Page 192
  Debugging Loops......Page 194
  Chapter Summary......Page 197
  Answers to Self-Test Exercises......Page 198
  Practice Programs......Page 204
  Programming Projects......Page 206
Chapter 4 Procedural Abstraction and FunctionsThat Return a Value......Page 213
 4.1 Top-Down Design......Page 214
  Using Predefined Functions......Page 215
  Random Number Generation......Page 220
  Type Casting......Page 222
  Pitfall: Integer Division Drops the Fractional Part......Page 224
  Function Definitions......Page 225
  Alternate Form for Function Declarations......Page 231
  Pitfall: Arguments in the Wrong Order......Page 232
  Function Definition–Syntax Summary......Page 233
  More About Placement of Function Definitions......Page 234
  Programming Tip: Use Function Calls in Branching Statements......Page 235
  The Black-Box Analogy......Page 236
  Programming Tip: Choosing Formal Parameter Names......Page 239
  Programming Tip: Nested Loops......Page 240
  Case Study: Buying Pizza......Page 243
  Programming Tip: Use Pseudocode......Page 249
  The Small Program Analogy......Page 250
  Global Constants and Global Variables......Page 253
  Call-by-Value Formal Parameters Are Local Variables......Page 256
  Block Scope......Page 258
  Namespaces Revisited......Page 259
  Programming Example: The Factorial Function......Page 262
  Introduction to Overloading......Page 264
  Programming Example: Revised Pizza-Buying Program......Page 267
  Automatic Type Conversion......Page 270
  Answers to Self-Test Exercises......Page 272
  Practice Programs......Page 277
  Programming Projects......Page 279
Chapter 5 Functions for All Subtasks......Page 283
  Definitions of void Functions......Page 284
  return Statements in void Functions......Page 287
  A First View of Call-by-Reference......Page 291
  Call-by-Reference in Detail......Page 294
  Programming Example: The swap_values Function......Page 299
  Mixed Parameter Lists......Page 300
  Programming Tip: What Kind of Parameter to Use......Page 301
  Pitfall: Inadvertent Local Variables......Page 302
  Functions Calling Functions......Page 305
  Preconditions and Postconditions......Page 307
  Case Study: Supermarket Pricing......Page 308
 5.4 Testing and Debugging Functions......Page 313
  Stubs and Drivers......Page 314
  Check Common Errors......Page 319
  Localize the Error......Page 320
  The assert Macro......Page 322
  Chapter Summary......Page 324
  Answers to Self-Test Exercises......Page 325
  Practice Programs......Page 328
  Programming Projects......Page 331
Chapter 6 I/O Streams as an Introduction to Objects and Classes......Page 337
 6.1 Streams and Basic File I/O......Page 338
  Why Use Files for I/O?......Page 339
  File I/O......Page 340
  Introduction to Classes and Objects......Page 344
  Programming Tip: Check Whether a File Was Opened Successfully......Page 346
  Techniques for File I/O......Page 348
  Appending to a File (Optional)......Page 352
  File Names as Input (Optional)......Page 353
  Formatting Output with Stream Functions......Page 355
  Manipulators......Page 361
  Programming Tip: Checking for the End of a File......Page 364
  A Note on Namespaces......Page 367
  Programming Example: Cleaning Up a File Format......Page 368
  The Member Functions get and put......Page 370
  The putback Member Function (Optional)......Page 374
  Programming Example: Checking Input......Page 375
  Pitfall: Unexpected '\n' in Input......Page 377
  Programming Example: Another new_line Function......Page 379
  Default Arguments for Functions (Optional)......Page 380
  The eof Member Function......Page 385
  Programming Example: Editing a Text File......Page 387
  Predefined Character Functions......Page 388
  Pitfall: toupper and to lower Return Values......Page 390
  Chapter Summary......Page 392
  Answers to Self-Test Exercises......Page 393
  Practice Programs......Page 400
  Programming Projects......Page 402
Chapter 7 Arrays......Page 409
  Declaring and Referencing Arrays......Page 410
  Programming Tip: Use a Defined Constant for the Size of an Array......Page 412
  Arrays in Memory......Page 414
  Pitfall: Array Index Out of Range......Page 415
  Programming Tip: C++11 Range-Based for Statement......Page 418
  Indexed Variables as Function Arguments......Page 421
  Entire Arrays as Function Arguments......Page 423
  The const Parameter Modifier......Page 426
  Functions That Return an Array......Page 429
  Case Study: Production Graph......Page 430
  Partially Filled Arrays......Page 443
  Programming Example: Searching an Array......Page 446
  Programming Example: Sorting an Array......Page 449
  Programming Example: Bubble Sort......Page 453
 7.4 Multidimensional Arrays......Page 456
  Multidimensional Array Basics......Page 457
  Programming Example: Two-Dimensional Grading Program......Page 459
  Pitfall: Using Commas Between Array Indexes......Page 463
  Chapter Summary......Page 464
  Answers to Self-Test Exercises......Page 465
  Practice Programs......Page 469
  Programming Projects......Page 471
Chapter 8 Strings and Vectors......Page 483
  C-String Values and C-String Variables......Page 485
  Pitfall: Using = and == with C Strings......Page 488
  Other Functions in ......Page 490
  Pitfall: Copying past the end of a C-string using strcpy......Page 493
  C-String Input and Output......Page 496
  C-String-to-Number Conversions and Robust Input......Page 498
  Introduction to the Standard Class string......Page 504
  I/O with the Class string......Page 507
  Programming Tip: More Versions of getline......Page 510
  Pitfall: Mixing cin >> variable; and getline......Page 511
  String Processing with the Class string......Page 512
  Programming Example: Palindrome Testing......Page 516
  Converting Between string Objects and C Strings......Page 519
  Converting Between Strings and Numbers......Page 520
  Vector Basics......Page 521
  Pitfall: Using Square Brackets Beyond the Vector Size......Page 524
  Efficiency Issues......Page 525
  Answers to Self-Test Exercises......Page 527
  Practice Programs......Page 529
  Programming Projects......Page 530
Chapter 9 Pointers and Dynamic Arrays......Page 539
 9.1 Pointers......Page 540
  Pointer Variables......Page 541
  Basic Memory Management......Page 548
  Pitfall: Dangling Pointers......Page 549
  Programming Tip: Define Pointer Types......Page 550
  Array Variables and Pointer Variables......Page 553
  Creating and Using Dynamic Arrays......Page 554
  Pointer Arithmetic (Optional)......Page 560
  Multidimensional Dynamic Arrays (Optional)......Page 562
  Answers to Self-Test Exercises......Page 564
  Practice Programs......Page 565
  Programming Projects......Page 566
Chapter 10 Defining Classes......Page 573
  Structures for Diverse Data......Page 574
  Pitfall: Forgetting a Semicolon in a Structure Definition......Page 579
  Structures as Function Arguments......Page 580
  Programming Tip: Use Hierarchical Structures......Page 581
  Initializing Structures......Page 583
  Defining Classes and Member Functions......Page 586
  Public and Private Members......Page 591
  Programming Tip: Define Accessor and Mutator Functions......Page 599
  Programming Tip: Use the Assignment Operator with Objects......Page 601
  Programming Example: BankAccount Class—Version 1......Page 602
  Summary of Some Properties of Classes......Page 606
  Constructors for Initialization......Page 608
  Programming Tip: Always Include a Default Constructor......Page 616
  Pitfall: Constructors with No Arguments......Page 617
  Member Initializers and Constructor Delegation in C++11......Page 619
 10.3 Abstract Data Types......Page 620
  Classes to Produce Abstract Data Types......Page 621
  Programming Example: Alternative Implementation of a Class......Page 625
 10.4 Introduction to Inheritance......Page 630
  Derived Classes......Page 631
  Defining Derived Classes......Page 632
  Chapter Summary......Page 636
  Answers to Self-Test Exercises......Page 637
  Practice Programs......Page 643
  Programming Projects......Page 644
Chapter 11 Friends, Overloaded Operators, and Arrays in Classes......Page 651
  Programming Example: An Equality Function......Page 652
  Friend Functions......Page 656
  Programming Tip: Define Both Accessor Functions and Friend Functions......Page 658
  Programming Example: Money Class (Version 1)......Page 660
  Implementation of digit_to_int (Optional)......Page 667
  Pitfall: Leading Zeros in Number Constants......Page 668
  The const Parameter Modifier......Page 670
  Pitfall: Inconsistent Use of const......Page 671
 11.2 Overloading Operators......Page 675
  Overloading Operators......Page 676
  Constructors for Automatic Type Conversion......Page 679
  Overloading Unary Operators......Page 681
  Overloading >> and <<......Page 682
  Arrays of Classes......Page 692
  Arrays as Class Members......Page 696
  Programming Example: A Class for a Partially Filled Array......Page 697
 11.4 Clases and Dynamic Arrays......Page 699
  Programming Example: A String Variable Class......Page 700
  Destructors......Page 703
  Pitfall: Pointers as Call-by-Value Parameters......Page 706
  Copy Constructors......Page 707
  Overloading the Assignment Operator......Page 712
  Answers to Self-Test Exercises......Page 715
  Practice Programs......Page 725
  Programming Projects......Page 726
Chapter 12 Separate Compilation and Namespaces......Page 735
 12.1 Separate Compilation......Page 736
  ADTs Reviewed......Page 737
  Case Study: DigitalTime —A Class Compiled Separately......Page 738
  Using #ifndef......Page 747
  Programming Tip: Defining Other Libraries......Page 750
  Namespaces and using Directives......Page 751
  Creating a Namespace......Page 753
  Qualifying Names......Page 756
  A Subtle Point About Namespaces (Optional)......Page 757
  Unnamed Namespaces......Page 758
  Programming Tip: Choosing a Name for a Namespace......Page 763
  Pitfall: Confusing the Global Namespace and the Unnamed Namespace......Page 764
  Chapter Summary......Page 765
  Answers to Self-Test Exercises......Page 766
  Practice Programs......Page 768
  Programming Projects......Page 770
Chapter 13 Pointers and Linked Lists......Page 771
  Nodes......Page 772
  nullptr......Page 777
  Linked Lists......Page 778
  Inserting a Node at the Head of a List......Page 779
  Pitfall: Losing Nodes......Page 782
  Searching a Linked List......Page 783
  Inserting and Removing Nodes Inside a List......Page 787
  Pitfall: Using the Assignment Operator with Dynamic Data Structures......Page 789
  Variations on Linked Lists......Page 792
  Linked Lists of Classes......Page 794
  Stacks......Page 797
  Programming Example: A Stack Class......Page 798
  Queues......Page 803
  Programming Example: A Queue Class......Page 804
  Answers to Self-Test Exercises......Page 808
  Practice Programs......Page 811
  Programming Projects......Page 812
Chapter 14 Recursion......Page 821
  Case Study: Vertical Numbers......Page 823
  A Closer Look at Recursion......Page 829
  Pitfall: Infinite Recursion......Page 831
  Stacks for Recursion......Page 832
  Recursion Versus Iteration......Page 834
  Programming Example: Another Powers Function......Page 836
  Recursive Design Techniques......Page 841
  Case Study: Binary Search—An Example of Recursive Thinking......Page 842
  Programming Example: A Recursive Member Function......Page 850
  Answers to Self-Test Exercises......Page 854
  Programming Projects......Page 859
Chapter 15 Inheritance......Page 865
 15.1 Inheritance Basics......Page 866
  Derived Classes......Page 869
  Constructors in Derived Classes......Page 877
  Pitfall: Use of Private Member Variables from the Base Class......Page 880
  The protected Qualifier......Page 882
  Redefinition of Member Functions......Page 885
  Redefining Versus Overloading......Page 888
  Access to a Redefined Base Function......Page 890
  Functions That Are Not Inherited......Page 891
  Assignment Operators and Copy Constructors in Derived Classes......Page 892
  Destructors in Derived Classes......Page 893
 15.3 Polymorphism......Page 894
  Late Binding......Page 895
  Virtual Functions in C++......Page 896
  Virtual Functions and Extended Type Compatibility......Page 901
  Pitfall: The Slicing Problem......Page 905
  Pitfall: Not Using Virtual Member Functions......Page 906
  Programming Tip: Make Destructors Virtual......Page 907
  Answers to Self-Test Exercises......Page 909
  Practice Programs......Page 913
  Programming Projects......Page 916
Chapter 16 Exception Handling......Page 925
  A Toy Example of Exception Handling......Page 927
  Multiple Throws and Catches......Page 936
  Pitfall: Catch the More Specific Exception First......Page 940
  Throwing an Exception in a Function......Page 941
  Exception Specification......Page 943
  Pitfall: Exception Specification in Derived Classes......Page 945
  When to Throw an Exception......Page 946
  Pitfall: Overuse of Exceptions......Page 948
  Testing for Available Memory......Page 949
  Answers to Self-Test Exercises......Page 950
  Practice Programs......Page 952
  Programming Projects......Page 953
Chapter 17 Templates......Page 957
 17.1 Templates for Algorithm Abstraction......Page 958
  Templates for Functions......Page 959
  Pitfall: Compiler Complications......Page 963
  Programming Example: A Generic Sorting Function......Page 965
  Programming Tip: How to Define Templates......Page 969
  Pitfall: Using a Template with an Inappropriate Type......Page 970
  Syntax for Class Templates......Page 971
  Programming Example: An Array Class......Page 974
  Answers to Self-Test Exercises......Page 981
  Programming Projects......Page 985
Chapter 18 Standard Template Library......Page 30
 18.1 Iterators......Page 989
  using Declarations......Page 991
  Iterator Basics......Page 992
  Pitfall: Compiler Problems......Page 996
  Kinds of Iterators......Page 998
  Constant and Mutable Iterators......Page 1002
  Reverse Iterators......Page 1003
  Other Kinds of Iterators......Page 1004
 18.2 Containers......Page 1005
  Sequential Containers......Page 1006
  Pitfall: Iterators and Removing Elements......Page 1010
  Container Adapters stack and queue......Page 1011
  Associative Containers set and map......Page 1015
  Efficiency......Page 1022
 18.3 Generic Algorithms......Page 1023
  Running Times and Big-O Notation......Page 1024
  Container Access Running Times......Page 1027
  Nonmodifying Sequence Algorithms......Page 1029
  Container Modifying Algorithms......Page 1033
  Set Algorithms......Page 1035
  Sorting Algorithms......Page 1036
  Answers to Self-Test Exercises......Page 1037
  Practice Programs......Page 1039
  Programming Projects......Page 1040
 1 C++ Keywords......Page 1047
 2 Precedence of Operators......Page 1048
 3 The ASCII Character Set......Page 1050
 4 Some Library Functions......Page 1051
 5 Inline Functions......Page 1058
 6 Overloading the Array Index Square Brackets......Page 1059
 7 The this Pointer......Page 1061
 8 Overloading Operators as Member Operators......Page 1064
 SYMBOLS......Page 1066
 A......Page 1067
 B......Page 1068
 C......Page 1069
 D......Page 1072
 E......Page 1073
 F......Page 1074
 I......Page 1076
 L......Page 1078
 N......Page 1079
 O......Page 1080
 P......Page 1081
 S......Page 1083
 U......Page 1085
 Z......Page 1086
Credits......Page 1087