Big C++: Late Objects. 3 Ed

Cover....1

Title Page....3

Copyright....4

Preface....5

Contents....19

Chapter 1 Introduction....33

1.1 What Is Programming?....34

1.2 The Anatomy of a Computer....35

1.3 Machine Code and Programming Languages....37

1.4 Becoming Familiar with YourProgramming Environment....39

1.5 Analyzing Your First Program....43

1.6 Errors....46

1.7 Problem Solving: Algorithm Design....48

1.7.1 The Algorithm Concept....48

1.7.2 An Algorithm for Solving an Investment Problem....49

1.7.3 Pseudocode....50

1.7.4 From Algorithms to Programs....51

Review Exercises....57

Practice Exercises....60

Programming Projects....62

Chapter 2 Fundamental Data Types....65

2.1 Variables....66

2.1.1 Variable Definitions....66

2.1.2 Number Types....68

2.1.3 Variable Names....69

2.1.4 The Assignment Statement....70

2.1.5 Constants....71

2.1.6 Comments....71

2.2 Arithmetic....76

2.2.1 Arithmetic Operators....76

2.2.2 Increment and Decrement....76

2.2.3 Integer Division and Remainder....76

2.2.4 Converting Floating-Point Numbers to Integers....77

2.2.5 Powers and Roots....78

2.3 Input and Output....84

2.3.1 Input....84

2.3.2 Formatted Output....85

2.4 Problem Solving: First Do It By Hand....87

2.5 Strings....91

2.5.1 The string Type....91

2.5.2 Concatenation....92

2.5.3 String Input....92

2.5.4 String Functions....92

Review Exercises....99

Practice Exercises....102

Programming Projects....105

Worked Example 2.1....111

Worked Example 2.2....113

Chapter 3 Decisions....115

3.1 The if Statement....116

3.2 Comparing Numbers and Strings....122

3.3 Multiple Alternatives....129

3.4 Nested Branches....132

3.5 Problem Solving: Flowcharts....137

3.6 Problem Solving: Test Cases....139

3.7 Boolean Variables and Operators....141

3.8 Application: Input Validation....146

Review Exercises....151

Practice Exercises....156

Programming Projects....158

Worked Example 3.1....167

Chapter 4 Loops....169

4.1 The while Loop....170

4.2 Problem Solving: Hand-Tracing....177

4.3 The for Loop....180

4.4 The do Loop....185

4.5 Processing Input....186

4.5.1 Sentinel Values....186

4.5.2 Reading Until Input Fails....188

4.6 Problem Solving: Storyboards....191

4.7 Common Loop Algorithms....193

4.7.1 Sum and Average Value....193

4.7.2 Counting Matches....194

4.7.3 Finding the First Match....194

4.7.4 Prompting Until a Match is Found....195

4.7.5 Maximum and Minimum....195

4.7.6 Comparing Adjacent Values....196

4.8 Nested Loops....200

4.9 Problem Solving: Solve a SimplerProblem First....204

4.10 Random Numbers and Simulations....208

4.10.1 Generating Random Numbers....208

4.10.2 Simulating Die Tosses....209

4.10.3 The Monte Carlo Method....210

Review Exercises....215

Practice Exercises....220

Programming Projects....223

Worked Example 4.1....233

Worked Example 4.2....236

Chapter 5 Functions....239

5.1 Functions as Black Boxes....240

5.2 Implementing Functions....241

5.3 Parameter Passing....244

5.4 Return Values....246

5.5 Functions Without Return Values....251

5.6 Problem Solving: Reusable Functions....252

5.7 Problem Solving: Stepwise Refinement....254

5.8 Variable Scope and Global Variables....261

5.9 Reference Parameters....263

5.10 Recursive Functions (Optional)....268

Review Exercises....277

Practice Exercises....281

Programming Projects....284

Worked Example 5.1....291

Worked Example 5.2....297

Worked Example 5.3....304

Chapter 6 Arrays and Vectors....309

6.1 Arrays....310

6.1.1 Defining Arrays....310

6.1.2 Accessing Array Elements....312

6.1.3 Partially Filled Arrays....313

6.2 Common Array Algorithms....315

6.2.1 Filling....316

6.2.2 Copying....316

6.2.3 Sum and Average Value....316

6.2.4 Maximum and Minimum....317

6.2.5 Element Separators....317

6.2.6 Counting Matches....317

6.2.7 Linear Search....318

6.2.8 Removing an Element....318

6.2.9 Inserting an Element....319

6.2.10 Swapping Elements....320

6.2.11 Reading Input....321

6.3 Arrays and Functions....324

6.4 Problem Solving: Adapting Algorithms....328

6.5 Problem Solving: Discovering Algorithms byManipulating Physical Objects....333

6.6 Two-Dimensional Arrays....336

6.6.1 Defining Two-Dimensional Arrays....337

6.6.2 Accessing Elements....337

6.6.3 Locating Neighboring Elements....338

6.6.4 Computing Row and Column Totals....338

6.6.5 Two-Dimensional Array Parameters....340

6.7 Vectors....343

6.7.1 Defining Vectors....344

6.7.2 Growing and Shrinking Vectors....345

6.7.3 Vectors and Functions....346

6.7.4 Vector Algorithms....346

6.7.5 Two-Dimensional Vectors....348

Review Exercises....353

Practice Exercises....356

Programming Projects....360

Worked Example 6.1....369

Worked Example 6.2....373

Chapter 7 Pointers and Structures....377

7.1 Defining and Using Pointers....378

7.1.1 Defining Pointers....378

7.1.2 Accessing Variables Through Pointers....379

7.1.3 Initializing Pointers....381

7.2 Arrays and Pointers....384

7.2.1 Arrays as Pointers....384

7.2.2 Pointer Arithmetic....384

7.2.3 Array Parameter Variables Are Pointers....386

7.3 C and C++ Strings....389

7.3.1 The char Type....389

7.3.2 C Strings....390

7.3.3 Character Arrays....391

7.3.4 Converting Between C and C++ Strings....391

7.3.5 C++ Strings and the [] Operator....392

7.4 Dynamic Memory Allocation....394

7.5 Arrays and Vectors of Pointers....397

7.6 Problem Solving: Draw a Picture....400

7.7 Structures....404

7.7.1 Structured Types....404

7.7.2 Structure Assignment and Comparison....405

7.7.3 Functions and Structures....406

7.7.4 Arrays of Structures....406

7.7.5 Structures with Array Members....407

7.7.6 Nested Structures....407

7.8 Pointers and Structures....408

7.8.1 Pointers to Structures....408

7.8.2 Structures with Pointer Members....409

Review Exercises....413

Practice Exercises....417

Programming Projects....419

Worked Example 7.1....423

Chapter 8 Streams....427

8.1 Reading and Writing Text Files....428

8.1.1 Opening a Stream....428

8.1.2 Reading from a File....429

8.1.3 Writing to a File....430

8.1.4 A File Processing Example....430

8.2 Reading Text Input....433

8.2.1 Reading Words....433

8.2.2 Reading Characters....434

8.2.3 Reading Lines....435

8.3 Writing Text Output....438

8.4 Parsing and Formatting Strings....441

8.5 Command Line Arguments....442

8.6 Random Access and Binary Files....449

8.6.1 Random Access....449

8.6.2 Binary Files....450

8.6.3 Processing Image Files....450

Review Exercises....457

Practice Exercises....458

Programming Projects....459

Worked Example 8.1....467

Chapter 9 Classes....471

9.1 Object-Oriented Programming....472

9.2 Implementing a Simple Class....474

9.3 Specifying the Public Interface of a Class....476

9.4 Designing the Data Representation....479

9.5 Member Functions....481

9.5.1 Implementing Member Functions....481

9.5.2 Implicit and Explicit Parameters....481

9.5.3 Calling a Member Function from a Member Function....483

9.6 Constructors....486

9.7 Problem Solving: Tracing Objects....490

9.8 Problem Solving: Discovering Classes....497

9.9 Separate Compilation....500

9.10 Pointers to Objects....504

9.10.1 Dynamically Allocating Objects....504

9.10.2 The -> Operator....505

9.10.3 The this Pointer....506

9.11 Problem Solving: Patterns for Object Data....506

9.11.1 Keeping a Total....506

9.11.2 Counting Events....507

9.11.3 Collecting Values....508

9.11.4 Managing Properties of an Object....508

9.11.5 Modeling Objects with Distinct States....509

9.11.6 Describing the Position of an Object....510

Review Exercises....515

Practice Exercises....517

Programming Projects....519

Worked Example 9.1....525

Chapter 10 Inheritance....529

10.1 Inheritance Hierarchies....530

10.2 Implementing Derived Classes....534

10.3 Overriding Member Functions....539

10.4 Virtual Functions and Polymorphism....542

10.4.1 The Slicing Problem....542

10.4.2 Pointers to Base and Derived Classes....543

10.4.3 Virtual Functions....544

10.4.4 Polymorphism....545

Review Exercises....559

Practice Exercises....562

Programming Projects....563

Worked Example 10.1....567

Chapter 11 Recursion....573

11.1 Triangle Numbers....574

11.2 Recursive Helper Functions....582

11.3 The Efficiency of Recursion....583

11.4 Permutations....587

11.5 Mutual Recursion....590

11.6 Backtracking....593

Review Exercises....603

Practice Exercises....604

Programming Projects....607

Worked Example 11.1....613

Worked Example 11.2....615

Chapter 12 Sorting and Searching....621

12.1 Selection Sort....622

12.2 Profiling the Selection Sort Algorithm....624

12.3 Analyzing the Performance of the Selection Sort Algorithm....625

12.4 Merge Sort....629

12.5 Analyzing the Merge Sort Algorithm....633

12.6 Searching....636

12.6.1 Linear Search....636

12.6.2 Binary Search....638

12.7 Problem Solving: Estimating the RunningTime of an Algorithm....641

12.7.1 Linear Time....641

12.7.2 Quadratic Time....643

12.7.3 The Triangle Pattern....643

12.7.4 Logarithmic Time....645

Review Exercises....649

Practice Exercises....652

Programming Projects....653

Worked Example 12.1....657

Chapter 13 Advanced C++....663

13.1 Operator Overloading....664

13.1.1 Operator Functions....664

13.1.2 Overloading Comparison Operators....667

13.1.3 Input and Output....667

13.1.4 Operator Members....668

13.2 Automatic Memory Management....672

13.2.1 Constructors That Allocate Memory....672

13.2.2 Destructors....674

13.2.3 Overloading the Assignment Operator....675

13.2.4 Copy Constructors....679

13.3 Templates....688

13.3.1 Function Templates....689

13.3.2 Class Templates....690

Review Exercises....695

Practice Exercises....698

Programming Projects....701

Worked Example 13.1....705

Worked Example 13.2....713

Chapter 14 Linked Lists, Stacks, and Queues....721

14.1 Using Linked Lists....722

14.2 Implementing Linked Lists....727

14.2.1 The Classes for Lists, Nodes, and Iterators....727

14.2.2 Implementing Iterators....728

14.2.3 Implementing Insertion and Removal....730

14.3 The Efficiency of List, Array, and VectorOperations....740

14.4 Stacks and Queues....743

14.5 Implementing Stacks and Queues....747

14.5.1 Stacks as Linked Lists....747

14.5.2 Stacks as Arrays....750

14.5.3 Queues as Linked Lists....750

14.5.4 Queues as Circular Arrays....751

14.6 Stack and Queue Applications....752

14.6.1 Balancing Parentheses....752

14.6.2 Evaluating Reverse Polish Expressions....753

14.6.3 Evaluating Algebraic Expressions....755

14.6.4 Backtracking....758

Review Exercises....762

Practice Exercises....766

Programming Projects....768

Worked Example 14.1....773

Chapter 15 Sets, Maps, and Hash Tables....785

15.1 Sets....786

15.2 Maps....789

15.3 Implementing a Hash Table....794

15.3.1 Hash Codes....794

15.3.2 Hash Tables....795

15.3.3 Finding an Element....797

15.3.4 Adding and Removing Elements....798

15.3.5 Iterating over a Hash Table....798

Review Exercises....809

Practice Exercises....809

Programming Projects....811

Worked Example 15.1....813

Chapter 16 Tree Structures....817

16.1 Basic Tree Concepts....818

16.2 Binary Trees....822

16.2.1 Binary Tree Examples....822

16.2.2 Balanced Trees....824

16.2.3 A Binary Tree Implementation....825

16.3 Binary Search Trees....826

16.3.1 The Binary Search Property....827

16.3.2 Insertion....828

16.3.3 Removal....830

16.3.4 Efficiency of the Operations....831

16.4 Tree Traversal....836

16.4.1 Inorder Traversal....837

16.4.2 Preorder and Postorder Traversals....838

16.4.3 The Visitor Pattern....839

16.4.4 Depth-First and Breadth-First Search....840

16.4.5 Tree Iterators....841

16.5 Red-Black Trees....842

16.5.1 Basic Properties of Red-Black Trees....842

16.5.2 Insertion....844

16.5.3 Removal....846

Review Exercises....851

Practice Exercises....852

Programming Projects....854

Worked Example 16.1....857

Worked Example 16.2....865

Chapter 17 Priority Queues and Heaps....901

17.1 Priority Queues....902

17.2 Heaps....905

17.3 The Heapsort Algorithm....915

Review Exercises....921

Practice Exercises....921

Programming Projects....922

Worked Example 17.1....925

Appendix A Reserved Word Summary....937

Appendix B Operator Summary....939

Appendix C Character Codes....941

Appendix D C++ Library Summary....944

Appendix E C++ Language Coding Guidelines....948

Appendix F Number Systems....955

Glossary....963

Index....971

Credits....1001

EULA....1004

This book is an introduction to C++ and computer programming that focuses on the essentials—and on effective learning. The book is designed to serve a wide range of student interests and abilities and is suitable for a first course in programming for computer scientists, engineers, and students in other disciplines. No prior programming experience is required, and only a modest amount of high school algebra is needed.