Starting Out with C++: From Control Structures through Objects

Contents

Preface xiii

CHAPTER 1 Introduction to Computers and Programming 1

1.1 Why Program? 1

1.2 Computer Systems: Hardware and Software 3

1.3 Programs and Programming Languages 8

1.4 What Is a Program Made of? 13

1.5 Input, Processing, and Output 17

1.6 The Programming Process 18

1.7 Procedural and Object-Oriented Programming 22

CHAPTER 2 Introduction to C++ 27

2.1 The Parts of a C++ Program 27

2.2 The cout Object 31

2.3 The #include Directive 36

2.4 Variables and Literals 37

2.5 Identifiers 41

2.6 Integer Data Types 42

2.7 The char Data Type 47

2.8 The C++ string Class 51

2.9 Floating-Point Data Types 53

2.10 The bool Data Type 56

2.11 Determining the Size of a Data Type 57

2.12 Variable Assignments and Initialization 58

2.13 Scope 59

2.14 Arithmetic Operators 60

2.15 Comments 68

2.16 Named Constants 70

2.17 Programming Style 72

2.18 If You Plan to Continue in Computer Science: Standard and Prestandard C++ 74

CHAPTER 3 Expressions and Interactivity 85

3.1 The cin Object 85

3.2 Mathematical Expressions 91

3.3 When You Mix Apples and Oranges: Type Conversion 100

3.4 Overflow and Underflow 102

3.5 Type Casting 103

3.6 Multiple Assignment and Combined Assignment 107

3.7 Formatting Output 111

3.8 Working with Characters and string Objects 120

3.9 More Mathematical Library Functions 127

3.10 Focus on Debugging: Hand Tracing a Program 130

3.11 Focus on Problem Solving: A Case Study 132

CHAPTER 4 Making Decisions 149

4.1 Relational Operators 149

4.2 The if Statement 154

4.3 Expanding the if Statement 162

4.4 The if/else Statement 166

4.5 Nested if Statements 169

4.6 The if/else if Statement 176

4.7 Flags 181

4.8 Logical Operators 182

4.9 Checking Numeric Ranges with Logical Operators 189

4.10 Menus 190

4.11 Focus on Software Engineering: Validating User Input 193

4.12 Comparing Characters and Strings 195

4.13 The Conditional Operator 199

4.14 The switch Statement 202

4.15 More About Blocks and Scope 211

CHAPTER 5 Loops and Files 227

5.1 The Increment and Decrement Operators 227

5.2 Introduction to Loops: The while Loop 232

5.3 Using the while Loop for Input Validation 239

5.4 Counters 241

5.5 The do-while Loop 242

5.6 The for Loop 247

5.7 Keeping a Running Total 257

5.8 Sentinels 260

5.9 Focus on Software Engineering: Deciding Which Loop to Use 261

5.10 Nested Loops 262

5.11 Using Files for Data Storage 265

5.12 Optional Topics: Breaking and Continuing a Loop 285

CHAPTER 6 Functions 301

6.1 Focus on Software Engineering: Modular Programming 301

6.2 Defining and Calling Functions 303

6.3 Function Prototypes 311

6.4 Sending Data into a Function 313

6.5 Passing Data by Value 318

6.6 Focus on Software Engineering: Using Functions in a Menu-Driven Program 320

6.7 The return Statement 324

6.8 Returning a Value from a Function 326

6.9 Returning a Boolean Value 334

6.10 Local and Global Variables 336

6.11 Static Local Variables 344

6.12 Default Arguments 347

6.13 Using Reference Variables as Parameters 350

6.14 Overloading Functions 356

6.15 The exit() Function 360

6.16 Stubs and Drivers 363

CHAPTER 7 Arrays 377

7.1 Arrays Hold Multiple Values 377

7.2 Accessing Array Elements 379

7.3 No Bounds Checking in C++ 386

7.4 Array Initialization 389

7.5 Processing Array Contents 394

7.6 Focus on Software Engineering: Using Parallel Arrays 402

7.7 Arrays as Function Arguments 405

7.8 Two-Dimensional Arrays 416

7.9 Arrays with Three or More Dimensions 423

7.10 Focus on Problem Solving and Program Design: A Case Study 424

7.11 If You Plan to Continue in Computer Science: Introduction to the STL vector 427

CHAPTER 8 Searching and Sorting Arrays 451

8.1 Focus on Software Engineering: Introduction to Search Algorithms 451

8.2 Focus on Problem Solving and Program Design: A Case Study 458

8.3 Focus on Software Engineering: Introduction to Sorting Algorithms 464

8.4 Focus on Problem Solving and Program Design: A Case Study 472

8.5 If You Plan to Continue in Computer Science: Sorting and Searching vectors 480

CHAPTER 9 Pointers 491

9.1 Getting the Address of a Variable 491

9.2 Pointer Variables 493

9.3 The Relationship Between Arrays and Pointers 500

9.4 Pointer Arithmetic 504

9.5 Initializing Pointers 506

9.6 Comparing Pointers 507

9.7 Pointers as Function Parameters 509

9.8 Focus on Software Engineering: Dynamic Memory Allocation 518

9.9 Focus on Software Engineering: Returning Pointers from Functions 522

9.10 Focus on Problem Solving and Program Design: A Case Study 529

CHAPTER 10 Characters, C-Strings, and More About the string Class 541

10.1 Character Testing 541

10.2 Character Case Conversion 545

10.3 C-Strings 548

10.4 Library Functions for Working with C-Strings 552

10.5 C-String/Numeric Conversion Functions 563

10.6 Focus on Software Engineering: Writing Your Own C-String-Handling Functions 568

10.7 More About the C++ string Class 574

10.8 Focus on Problem Solving and Program Design: A Case Study 584

CHAPTER 11 Structured Data 593

11.1 Abstract Data Types 593

11.2 Focus on Software Engineering: Combining Data into Structures 595

11.3 Accessing Structure Members 598

11.4 Initializing a Structure 602

11.5 Arrays of Structures 605

11.6 Focus on Software Engineering: Nested Structures 608

11.7 Structures as Function Arguments 612

11.8 Returning a Structure from a Function 615

11.9 Pointers to Structures 618

11.10 Focus on Software Engineering: When to Use ., When to Use ->, and When to Use * 621

11.11 Unions 623

11.12 Enumerated Data Types 627

CHAPTER 12 Advanced File Operations 651

12.1 File Operations 651

12.2 File Output Formatting 658

12.3 Passing File Stream Objects to Functions 660

12.4 More Detailed Error Testing 662

12.5 Member Functions for Reading and Writing Files 665

12.6 Focus on Software Engineering: Working with Multiple Files 672

12.7 Binary Files 674

12.8 Creating Records with Structures 679

12.9 Random-Access Files 683

12.10 Opening a File for Both Input and Output 691

CHAPTER 13 Introduction to Classes 705

13.1 Procedural and Object-Oriented Programming 705

13.2 Introduction to Classes 712

13.3 Defining an Instance of a Class 717

13.4 Why Have Private Members? 728

13.5 Focus on Software Engineering: Separating Class Specification from Implementation 729

13.6 Inline Member Functions 735

13.7 Constructors 738

13.8 Passing Arguments to Constructors 742

13.9 Destructors 750

13.10 Overloading Constructors 754

13.11 Private Member Functions 758

13.12 Arrays of Objects 759

13.13 Focus on Problem Solving and Program Design: An OOP Case Study 763

13.14 Focus on Object-Oriented Programming: Creating an Abstract Array Data Type 770

13.15 Focus on Object-Oriented Design: The Unified Modeling Language (UML) 774

13.16 Focus on Object-Oriented Design: Finding the Classes and Their Responsibilities 777

CHAPTER 14 More About Classes 799

14.1 Instance and Static Members 799

14.2 Friends of Classes 807

14.3 Memberwise Assignment 812

14.4 Copy Constructors 813

14.5 Operator Overloading 819

14.6 Object Conversion 846

14.7 Aggregation 849

14.8 Focus on Object-Oriented Design: Class Collaborations 853

CHAPTER 15 Inheritance, Polymorphism, and Virtual Functions 869

15.1 What Is Inheritance? 869

15.2 Protected Members and Class Access 878

15.3 Constructors and Destructors in Base and Derived Classes 884

15.4 Redefining Base Class Functions 896

15.5 Class Hierarchies 901

15.6 Polymorphism and Virtual Member Functions 907

15.7 Abstract Base Classes and Pure Virtual Functions 921

15.8 Multiple Inheritance 928

CHAPTER 16 Exceptions, Templates, and the Standard Template Library (STL) 947

16.1 Exceptions 947

16.2 Function Templates 966

16.3 Focus on Software Engineering: Where to Start When Defining Templates 972

16.4 Class Templates 973

16.5 Introduction to the Standard Template Library (STL) 983

CHAPTER 17 Linked Lists 1003

17.1 Introduction to the Linked List ADT 1003

17.2 Linked List Operations 1005

17.3 A Linked List Template 1022

17.4 Variations of the Linked List 1034

17.5 The STL list Container 1035

CHAPTER 18 Stacks and Queues 1043

18.1 Introduction to the Stack ADT 1043

18.2 Dynamic Stacks 1060

18.3 The STL stack Container 1071

18.4 Introduction to the Queue ADT 1073

18.5 Dynamic Queues 1085

18.6 The STL deque and queue Containers 1092

CHAPTER 19 Recursion 1101

19.1 Introduction to Recursion 1101

19.2 Solving Problems with Recursion 1106

19.3 Focus on Problem Solving and Program Design: The Recursive gcd Function 1113

19.4 Focus on Problem Solving and Program Design: Solving Recursively Defined Problems 1114

19.5 Focus on Problem Solving and Program Design: Recursive Linked List Operations 1116

19.6 Focus on Problem Solving and Program Design: A Recursive Binary Search Function 1119

19.7 The Towers of Hanoi 1122

19.8 Focus on Problem Solving and Program Design: The QuickSort Algorithm 1125

19.9 Exhaustive Algorithms 1130

19.10 Focus on Software Engineering: Recursion vs. Iteration 1132

CHAPTER 20 Binary Trees 1137

20.1 Definition and Applications of Binary Trees 1137

20.2 Binary Search Tree Operations 1140

20.3 Template Considerations for Binary Search Trees 1157

Appendix A: Getting Started with Alice 1167

Appendix B: The ASCII Character Set 1195

Appendix C: Operator Precedence and Associativity 1197

Quick References 1199

Index 1201

Online

The following appendices are available at www.pearsonhighered.com/gaddis.

Appendix D: Introduction to Flowcharting

Appendix E: Using UML in Class Design

Appendix F: Namespaces

Appendix G: Writing Managed C++ Code for the .NET Framework

Appendix H: Passing Command Line Arguments

Appendix I: Header File and Library Function Reference

Appendix J: Binary Numbers and Bitwise Operations

Appendix K: Multi-Source File Programs

Appendix L: Stream Member Functions for Formatting

Appendix M: Introduction to Microsoft Visual C++ 2010 Express Edition

Appendix N: Answers to Checkpoints

Appendix O: Solutions to Odd-Numbered Review Questions