Problem solving c++ 9th edition pdf

Human Resources

Location of Videonotes in the text

Chapter 10 Class Scope, Public and Private Members, p. 565 Default Initialization of Member Variables, p. 587 Separate Interface and Implementation, p. 592 Solution to Practice Program 10.1, p. 611

Chapter 11 const Confusion, p. 639 Arrays of Classes using Dynamic Arrays, p. 671 Overloading = and == for a Class, p. 680 Solution to Programming Project 11.12, p. 701

Chapter 12 Avoiding Multiple Definitions, p. 715 Solution to Practice Program 12.3, p. 736

Chapter 13 Walkthrough of Linked Lists of Classes, p. 762 Solution to Programming Project 13.6, p. 783 Solution to Programming Project 13.9, p. 785

Chapter 14 Recursion and the Stack, p. 801 Solution to Practice Program 14.4, p. 827 Solution to Practice Program 14.4 , p. 828

Chapter 15 Inheritance Example, p. 858 Solution to Practice Program 15.3, p. 882 Solution to Programming Project 15.1, p. 884 Solution to Programming Project 15.10, p. 889

Chapter 16 The STL Exception Class, p. 917 Solution to Practice Program 16.1, p. 920 Solution to Programming Project 16.3, p. 922

Chapter 17 Issues Compiling Programs with Templates, p. 931 Solution to Programming Project 17.7, p. 955

Chapter 18 C++11 and Containers, p. 990 Solution to Practice Program 18.2, p. 1007 Solution to Programming Project 18.6, p. 1010

(Continued from Inside Front Cover)

Problem Solving with C++ ninth edition

This page intentionally left blank

Boston Columbus Indianapolis New York San Francisco Upper Saddle River Amsterdam Cape Town Dubai London Madrid Milan Munich Paris Montreal Toronto

Delhi Mexico City São Paulo Sydney Hong Kong Seoul Singapore Taipei Tokyo

Problem Solving with C++

Walter Savitch University of California, san Diego

Contributor

Kenrick mock University of alaska, anChorage

ninth edition

Editorial Director: Marcia Horton Acquisitions Editor: Matt Goldstein Program Manager: Kayla Smith-Tarbox Editorial Assistant: Kelsey Loanes Marketing Coordinator: Kathryn Ferranti Production Director: Erin Gregg Managing Editor: Scott Disanno Senior Operations Supervisor: Vincent Scelta Operations Specialist: Linda Sager Cover Designer: Joyce Wells Permissions Manager: Timothy Nicholls Image Permissions Manager: Karen Sanatar Media Producer: Renata Butera Media Project Manager: Wanda Rockwell Full-Service Vendor: Hardik Popli, Cenveo® Publisher Services Composition: Cenveo Publisher Services Printer/Binder: Courier/Westford Cover Printer: Lehigh-Phoenix Color/Hagerstown

Credits and acknowledgments borrowed from other sources and reproduced, with permission, in this textbook appear on appropriate page within text.

Microsoft® and Windows® are registered trademarks of the Microsoft Corporation in the U.S.A. and other coun- tries. Screen shots and icons reprinted with permission from the Microsoft Corporation. This book is not spon- sored or endorsed by or affiliated with the Microsoft Corporation.

Copyright © 2015, 2012, 2009, 2007, 2005, 2003 Pearson Education, Inc. All rights reserved. Manufactured in the United States of America. This publication is protected by Copyright, and permission should be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. To obtain permission(s) to use material from this work, please submit a written request to Pearson Education, Inc., Permissions Department, 501 Boylston Street, Suite 900, Boston, Massachusetts 02116.

Many of the designations by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and the publisher was aware of a trademark claim, the designations have been printed in initial caps or all caps.

Library of Congress Cataloging-in-Publication Data

Savitch, Walter J., 1943- Problem solving with C++ / Walter Savitch ; contributor, Kenrick Mock. -- Ninth edition. pages cm Includes index. ISBN-13: 978-0-13-359174-3 (alkaline paper) ISBN-10: 0-13-359174-3 (alkaline paper) 1. C++ (Computer program language) 2. Problem solving. I. Mock, Kenrick. II. Title. QA76.73.C153S29 2014 005.13'3--dc23 2013048487

10 9 8 7 6 5 4 3 2 1—CW—15 14 13 12 11 ISBN 10: 0-13-359174-3 www.pearsonhighered.com ISBN 13: 978-0-13-359174-3

www.pearsonhighered.com
v

Preface

This book is meant to be used in a first course in programming and computer science using the C++ language. It assumes no previous programming experi- ence and no mathematics beyond high school algebra.

If you have used the previous edition of this book, you should read the following section that explains the changes to this ninth edition and then you can skip the rest of this preface. If you are new to this book, the rest of this preface will give you an overview of the book.

Changes to the Ninth Edition This ninth edition presents the same programming philosophy as the eighth edition. All of the material from the eighth edition remains, but with the fol- lowing enhancements:

■ End-of-chapter programs are now split into Practice Programs and Program- ming Projects. Practice Programs require a direct application of concepts presented in the chapter and solutions are usually short. Practice Programs are appropriate for laboratory exercises. Programming Projects require ad- ditional problem solving and solutions are generally longer than Practice Programs. Programming Projects are appropriate for homework problems.

■ Introduction to C++11 in the context of C++98. Examples of C++11 content includes new integer types, the auto type, raw string literals, strong enumera- tions, nullptr, ranged for loop, conversion between strings and integers, member initializers, and constructor delegation.

■ Additional material on sorting, secure programming (e.g., overflow, array out of bounds), and inheritance.

■ Correction of errata. ■ Twenty-one new Practice Programs and ten new Programming Projects. ■ Ten new VideoNotes for a total of sixty-four VideoNotes. These VideoNotes

walk students through the process of both problem solving and coding to help reinforce key programming concepts. An icon appears in the margin of the book when a VideoNote is available regarding the topic covered in the text.

If you are an instructor already using the eighth edition, you can continue to teach your course almost without change.

Flexibility in Topic Ordering This book was written to allow instructors wide latitude in reordering the material. To illustrate this flexibility, we suggest two alternative ways to order

vi Preface

the topics. There is no loss of continuity when the book is read in either of these ways. To ensure this continuity when you rearrange material, you may need to move sections rather than entire chapters. However, only large sec- tions in convenient locations are moved. To help customize a particular order for any class’s needs, the end of this preface contains a dependency chart, and each chapter has a “Prerequisites” section that explains what material needs to be covered before each section in that chapter.

Reordering 1: Earlier Classes

To effectively design classes, a student needs some basic tools such as control structures and function definitions. This basic material is covered in Chapters 1 through 6. After completing Chapter 6, students can begin to write their own classes. One possible reordering of chapters that allows for such early coverage of classes is the following:

Basics: Chapters 1, 2, 3, 4, 5, and 6. This material covers all control struc- tures, function definitions, and basic file I/O. Chapter 3, which covers ad- ditional control structures, could be deferred if you wish to cover classes as early as possible.

Classes and namespaces: Chapter 10, Sections 11.1 and 11.2 of Chapter 11, and Chapter 12. This material covers defining classes, friends, overloaded operators, and namespaces.

Arrays, strings and vectors: Chapters 7 and 8

Pointers and dynamic arrays: Chapter 9

Arrays in classes: Sections 11.3 and 11.4 of Chapter 11

Inheritance: Chapter 15

Recursion: Chapter 14 (Alternately, recursion may be moved to later in the course.)

Pointers and linked lists: Chapter 13

Any subset of the following chapters may also be used:

Exception handling: Chapter 16

Templates: Chapter 17

Standard Template Library: Chapter 18

Reordering 2: Classes Slightly Later but Still Early

This version covers all control structures and the basic material on arrays be- fore doing classes, but classes are covered later than the previous ordering and slightly earlier than the default ordering.

Basics: Chapters 1, 2, 3, 4, 5, and 6. This material covers all control struc- tures, function definitions, and the basic file I/O.

Preface vii

Arrays and strings: Chapter 7, Sections 8.1 and 8.2 of Chapter 8

Classes and namespaces: Chapter 10, Sections 11.1 and 11.2 of Chapter 11, and Chapter 12. This material covers defining classes, friends, overloaded operators, and namespaces.

Pointers and dynamic arrays: Chapter 9

Arrays in classes: Sections 11.3 and 11.4 of Chapter 11

Inheritance: Chapter 15

Recursion: Chapter 14. (Alternately, recursion may be moved to later in the course.)

Vectors: Chapter 8.3

Pointers and linked lists: Chapter 13

Any subset of the following chapters may also be used:

Exception handling: Chapter 16

Templates: Chapter 17

Standard Template Library: Chapter 18

Accessibility to Students

It is not enough for a book to present the right topics in the right order. It is not even enough for it to be clear and correct when read by an instructor or other experienced programmer. The material needs to be presented in a way that is accessible to beginning students. In this introductory textbook, I have endeav- ored to write in a way that students find clear and friendly. Reports from the many students who have used the earlier editions of this book confirm that this style makes the material clear and often even enjoyable to students.

ANSI/ISO C++ Standard

This edition is fully compatible with compilers that meet the latest ANSI/ISO C++ standard. At the time of this writing the latest standard is C++11.

Advanced Topics

Many “advanced topics” are becoming part of a standard CS1 course. Even if they are not part of a course, it is good to have them available in the text as enrichment material. This book offers a number of advanced topics that can be integrated into a course or left as enrichment topics. It gives thorough cov- erage of C++ templates, inheritance (including virtual functions), exception handling, and the STL (Standard Template Library). Although this book uses libraries and teaches students the importance of libraries, it does not require any nonstandard libraries. This book uses only libraries that are provided with essentially all C++ implementations.

viii Preface

Dependency Chart

The dependency chart on the next page shows possible orderings of chapters and subsections. A line joining two boxes means that the upper box must be covered before the lower box. Any ordering that is consistent with this partial ordering can be read without loss of continuity. If a box contains a section number or numbers, then the box refers only to those sections and not to the entire chapter.

Summary Boxes

Each major point is summarized in a boxed section. These boxed sections are spread throughout each chapter.

Self-Test Exercises

Each chapter contains numerous Self-Test Exercises at strategic points. Com- plete answers for all the Self-Test Exercises are given at the end of each chapter.

VideoNotes

VideoNotes are designed for teaching students key programming concepts and techniques. These short step-by-step videos demonstrate how to solve problems from design through coding. VideoNotes allow for self-paced instruction with easy navigation including the ability to select, play, rewind, fast-forward, and stop within each VideoNote exercise.

Online Practice and Assessment with MyProgrammingLab

MyProgrammingLab helps students fully grasp the logic, semantics, and syn- tax of programming. Through practice exercises and immediate, personalized feedback, MyProgrammingLab improves the programming competence of be- ginning students who often struggle with the basic concepts and paradigms of popular high-level programming languages.

A self-study and homework tool, a MyProgrammingLab course consists of hundreds of small practice problems organized around the structure of this textbook. For students, the system automatically detects errors in the logic and syntax of their code submissions and offers targeted hints that enable students to figure out what went wrong—and why. For instructors, a comprehensive gradebook tracks correct and incorrect answers and stores the code inputted by students for review.

MyProgrammingLab is offered to users of this book in partnership with Turing’s Craft, the makers of the CodeLab interactive programming exer- cise system. For a full demonstration, to see feedback from instructors and students, or to get started using MyProgrammingLab in your course, visit www.myprogramminglab.com.

VideoNote

www.myprogramminglab.com
Preface ix

DISPLAY P.1 Dependency Chart

*Chapter 16 contains occasional references to derived classes, but those references can be omitted

Chapter 1 Introduction

Chapter 2 C++ Basics

Chapter 3 More Flow of Control

Chapter 6 I/O Streams

Chapter 7 Arrays 7.1–7.3

Chapter 14 Recursion

Chapter 10 Classes 1

Chapter 11 Classes 2 11.1–11.2

Chapter 7 7.4 Multi-

Dimensional Arrays

Chapter 15 Inheritance

*Chapter 16 Exception Handling

Chapter 12 Separate

Compilation & Namespaces

Chapter 11 11.3 Classes &

Arrays

Chapter 11 11.4 Classes &

Dynamic Arrays

Chapter 17 Templates

Chapter 18 STL

Chapter 9 Pointers and

Dynamic Arrays

Chapter 8 Strings and

Vectors

Chapter 13 Pointers and Linked Lists

Chapter 4 Functions 1

Chapter 5 Functions 2

x Preface

Support Material

There is support material available to all users of this book and additional material available only to qualified instructors.

Materials Available to All Users of this Book

■ Source Code from the book ■ PowerPoint slides ■ VideoNotes

To access these materials, go to: www.pearsonhighered.com/savitch

Resources Available to Qualified Instructors Only

Visit Pearson Education’s instructor resource center at www.pearsonhighered .com/irc to access the following instructor resources:

■ Instructor’s Resource Guide—including chapter-by-chapter teaching hints, quiz questions with solutions, and solutions to many programming projects

■ Test Bank and Test Generator ■ PowerPoint Lectures—including programs and art from the text ■ Lab Manual

Integrated Development Environment (IDE) Resource Kits

Instructors who adopt this text can order it for students with a kit containing five popular C++ IDEs (Microsoft® Visual Studio 2013 Express Edition, Dev C++, NetBeans, Eclipse, and CodeLite) and access to a Web site containing written and video tutorials for getting started in each IDE. For ordering infor- mation, please contact your campus Pearson Education representative.

Contact Us

Your comments, suggestions, questions, and corrections are always welcome. Please e-mail them to savitch.programming.cpp@gmail.com

Acknowledgments

Numerous individuals and groups have provided me with suggestions, discus- sions, and other help in preparing this textbook. Much of the first edition of this book was written while I was visiting the Computer Science Department at the University of Colorado in Boulder. The remainder of the writing on the first edition and the work on subsequent editions was done in the Computer Science and Engineering Department at the University of California, San Diego (UCSD). I am grateful to these institutions for providing a conducive environ- ment for teaching this material and writing this book.

www.pearsonhighered.com/savitch
www.pearsonhighered.com/irc
www.pearsonhighered.com/irc
Preface xi

I extend a special thanks to all the individuals who have contributed critiques or programming projects for this or earlier editions and drafts of this book. In alphabetical order, they are: Alex Feldman, Amber Settle, Andrew Burt, Andrew Haas, Anne Marchant, Barney MacCabe, Bob Holloway, Bob Matthews, Brian R. King, Bruce Johnston, Carol Roberts, Charles Dowling, Claire Bono, Cynthia Martincic, David Feinstein, David Teague, Dennis Heckman, Donald Needham, Doug Cosman, Dung Nguyen, Edward Carr, Eitan M. Gurari, Ethan Munson, Firooz Khosraviyani, Frank Moore, Gilliean Lee, Huzefa Kagdi, James Stepleton, Jeff Roach, Jeffrey Watson, Jennifer Perkins, Jerry Weltman, Joe Faletti, Joel Cohen, John J. Westman, John Marsaglia, John Russo, Joseph Allen, Joseph D. Oldham, Jerrold Grossman, Jesse Morehouse, Karla Chaveau, Ken Rockwood, Larry Johnson, Len Garrett, Linda F. Wilson, Mal Gunasekera, Marianne Lepp, Matt Johnson, Michael Keenan, Michael Main, Michal Sramka, Naomi Shapiro, Nat Martin, Noah Aydin, Nisar Hundewale, Paul J. Kaiser, Paul Kube, Paulo Franca, Richard Borie, Scot Drysdale, Scott Strong, Sheila Foster, Steve Mahaney, Susanne Sherba, Thomas Judson, Walter A. Manrique, Wei Lian Chen, and Wojciech Komornicki.

I extend a special thanks to the many instructors who used early editions of this book. Their comments provided some of the most helpful reviewing that the book received.

Finally, I thank Kenrick Mock who implemented the changes in this edition. He had the almost impossible task of pleasing me, my editor, and his own sensibilities, and he did a superb job of it.

Walter Savitch

This page intentionally left blank

Through the power of practice and immediate personalized

feedback, MyProgrammingLab improves your performance.

Learn more at www.myprogramminglab.com

get with the programming

To improving results

www.myprogramminglab.com
xiv

Brief Contents

Table of Location of VideoNotes Inside front cover and inside back cover

Chapter 1 Introduction to Computers and C++ Programming 1

Chapter 2 C++ Basics 39

Chapter 3 More Flow of Control 111

Chapter 4 Procedural Abstraction and Functions That Return a Value 181

Chapter 5 Functions for All Subtasks 251

Chapter 6 I/O Streams as an Introduction to Objects and Classes 305

Chapter 7 Arrays 377

Chapter 8 Strings and Vectors 451

Chapter 9 Pointers and Dynamic Arrays 507

Chapter 10 Defining Classes 541

Chapter 11 Friends, Overloaded Operators, and Arrays in Classes 619

Brief contents xv

Chapter 12 Separate Compilation and Namespaces 703

Chapter 13 Pointers and Linked Lists 739

Chapter 14 Recursion 789

Chapter 15 Inheritance 833

Chapter 16 Exception Handling 893

Chapter 17 Templates 925

Chapter 18 Standard Template Library 957

Appendices 1 C++ Keywords 1015 2 Precedence of Operators 1016 3 The ASCII Character Set 1018 4 Some Library Functions 1019 5 Inline Functions 1026 6 Overloading the Array Index

Square Brackets 1027

7 The this Pointer 1029 8 Overloading Operators as Member

Operators 1032

Index 1034

xvi

Contents

Table of Location of VideoNotes Inside front cover and inside back cover

Chapter 1 Introduction to Computers and C++ Programming 1

1.1 COMPuTER SYSTEMS 2

Hardware 2

Software 7

High-Level Languages 8

Compilers 9

History Note 12

1.2 PROgRAMMINg AND PROBLEM-SOLVINg 12

Algorithms 12

Program Design 15

Object-Oriented Programming 16

The Software Life Cycle 17

1.3 INTRODuCTION TO C++ 18

Origins of the C++ Language 18

A Sample C++ Program 19

Pitfall: Using the Wrong Slash in \n 23

Programming Tip: Input and Output Syntax 23

Layout of a Simple C++ Program 24

Pitfall: Putting a Space Before the include File Name 26

Compiling and Running a C++ Program 26

Pitfall: Compiling a C++11 program 27

Programming Tip: Getting Your Program to Run 27

1.4 TESTINg AND DEBuggINg 29

Kinds of Program Errors 30

Pitfall: Assuming Your Program Is Correct 31

contents xvii

Chapter Summary 32

Answers to Self-Test Exercises 33

Practice Programs 35

Programming Projects 36

Chapter 2 C++ Basics 39

2.1 VARIABLES AND ASSIgNMENTS 40

Variables 40

Names: Identifiers 42

Variable Declarations 44

Assignment Statements 45

Pitfall: Uninitialized Variables 47

Programming Tip: Use Meaningful Names 49

2.2 INPuT AND OuTPuT 50

Output Using cout 50

Include Directives and Namespaces 52

Escape Sequences 53

Programming Tip: End Each Program with a \n or endl 55

Formatting for Numbers with a Decimal Point 55

Input Using cin 56

Designing Input and Output 58

Programming Tip: Line Breaks in I/O 58

2.3 DATA TYPES AND ExPRESSIONS 60

The Types int and double 60

Other Number Types 62

C++11 Types 63

The Type char 64

The Type bool 66

Introduction to the Class string 66

Type Compatibilities 68

Arithmetic Operators and Expressions 69

Pitfall: Whole Numbers in Division 72

More Assignment Statements 74

2.4 SIMPLE FLOw OF CONTROL 74

A Simple Branching Mechanism 75

Pitfall: Strings of Inequalities 80

Pitfall: Using = in place of == 81

Compound Statements 82

xviii contents

Simple Loop Mechanisms 84

Increment and Decrement Operators 87

Programming Example: Charge Card Balance 89

Pitfall: Infinite Loops 90

2.5 PROgRAM STYLE 93

Indenting 93

Comments 93

Naming Constants 95

Chapter Summary 98

Answers to Self-Test Exercises 98

Practice Programs 103

Programming Projects 105

Chapter 3 More Flow of Control 111

3.1 uSINg BOOLEAN ExPRESSIONS 112

Evaluating Boolean Expressions 112

Pitfall: Boolean Expressions Convert to int Values 116

Enumeration Types (Optional) 119

3.2 MuLTIwAY BRANCHES 120

Nested Statements 120

Programming Tip: Use Braces in Nested Statements 121

Multiway if-else Statements 123

Programming Example: State Income Tax 125

The switch Statement 128

Pitfall: Forgetting a break in a switch Statement 132

Using switch Statements for Menus 133

Blocks 135

Pitfall: Inadvertent Local Variables 138

3.3 MORE ABOuT C++ LOOP STATEMENTS 139

The while Statements Reviewed 139

Increment and Decrement Operators Revisited 141

The for Statement 144

Pitfall: Extra Semicolon in a for Statement 149

What Kind of Loop to Use 150

Pitfall: Uninitialized Variables and Infinite Loops 152

The break Statement 153

Pitfall: The break Statement in Nested Loops 154

contents xix

3.4 DESIgNINg LOOPS 155

Loops for Sums and Products 155

Ending a Loop 157

Nested Loops 160

Debugging Loops 162

Chapter Summary 165

Answers to Self-Test Exercises 166

Practice Programs 172

Programming Projects 174

Chapter 4 Procedural Abstraction and Functions That Return a Value 181

4.1 TOP-DOwN DESIgN 182

4.2 PREDEFINED FuNCTIONS 183

Using Predefined Functions 183

Random Number Generation 188

Type Casting 190

Older Form of Type Casting 192

Pitfall: Integer Division Drops the Fractional Part 192

4.3 PROgRAMMER-DEFINED FuNCTIONS 193

Function Definitions 193

Functions That Return a Boolean Value 199

Alternate Form for Function Declarations 199

Pitfall: Arguments in the Wrong Order 200

Function Definition–Syntax Summary 201

More About Placement of Function Definitions 202

Programming Tip: Use Function Calls in Branching Statements 203

4.4 PROCEDuRAL ABSTRACTION 204

The Black-Box Analogy 204

Programming Tip: Choosing Formal Parameter Names 207

Programming Tip: Nested Loops 208

Case Study: Buying Pizza 211

Programming Tip: Use Pseudocode 217

4.5 SCOPE AND LOCAL VARIABLES 218

The Small Program Analogy 218

Programming Example: Experimental Pea Patch 221

xx contents

Global Constants and Global Variables 221

Call-by-Value Formal Parameters Are Local Variables 224

Block Scope 226

Namespaces Revisited 227

Programming Example: The Factorial Function 230

4.6 OVERLOADINg FuNCTION NAMES 232

Introduction to Overloading 232

Programming Example: Revised Pizza-Buying Program 235

Automatic Type Conversion 238

Chapter Summary 240

Answers to Self-Test Exercises 240

Practice Programs 245

Programming Projects 247

Chapter 5 Functions for All Subtasks 251

5.1 void FuNCTIONS 252

Definitions of void Functions 252

Programming Example: Converting Temperatures 255

return Statements in void Functions 255

5.2 CALL-BY-REFERENCE PARAMETERS 259

A First View of Call-by-Reference 259

Call-by-Reference in Detail 262

Programming Example: The swap_values Function 267

Mixed Parameter Lists 268

Programming Tip: What Kind of Parameter to Use 269

Pitfall: Inadvertent Local Variables 270

5.3 uSINg PROCEDuRAL ABSTRACTION 273

Functions Calling Functions 273

Preconditions and Postconditions 275

Case Study: Supermarket Pricing 276

5.4 TESTINg AND DEBuggINg FuNCTIONS 281

Stubs and Drivers 282

5.5 gENERAL DEBuggINg TECHNIquES 287

Keep an Open Mind 287

Check Common Errors 287

contents xxi

Localize the Error 288

The assert Macro 290

Chapter Summary 292

Answers to Self-Test Exercises 293

Practice Programs 296

Programming Projects 299

Chapter 6 I/O Streams as an Introduction to Objects and Classes 305

6.1 STREAMS AND BASIC FILE I/O 306

Why Use Files for I/O? 307

File I/O 308

Introduction to Classes and Objects 312

Programming Tip: Check Whether a File Was Opened

Successfully 314

Techniques for File I/O 316

Appending to a File (Optional) 320

File Names as Input (Optional) 321

6.2 TOOLS FOR STREAM I/O 323

Formatting Output with Stream Functions 323

Manipulators 329

Streams as Arguments to Functions 332

Programming Tip: Checking for the End of a File 332

A Note on Namespaces 335

Programming Example: Cleaning Up a File Format 336

6.3 CHARACTER I/O 338

The Member Functions get and put 338

The putback Member Function (Optional) 342

Programming Example: Checking Input 343

Pitfall: Unexpected '\n' in Input 345

Programming Example: Another new_line Function 347

Default Arguments for Functions (Optional) 348

The eof Member Function 353

Programming Example: Editing a Text File 355

Predefined Character Functions 356

Pitfall: toupper and tolower Return Values 358

xxii contents

Chapter Summary 360

Answers to Self-Test Exercises 361

Practice Programs 368

Programming Projects 370

Chapter 7 Arrays 377

7.1 INTRODuCTION TO ARRAYS 378

Declaring and Referencing Arrays 378

Programming Tip: Use for Loops with Arrays 380

Pitfall: Array Indexes Always Start with Zero 380

Programming Tip: Use a Defined Constant for the

Size of an Array 380

Arrays in Memory 382

Pitfall: Array Index Out of Range 383

Initializing Arrays 386

Programming Tip: C++11 Range-Based for Statement 386

7.2 ARRAYS IN FuNCTIONS 389

Indexed Variables as Function Arguments 389

Entire Arrays as Function Arguments 391

The const Parameter Modifier 394

Pitfall: Inconsistent Use of const Parameters 397

Functions That Return an Array 397

Case Study: Production Graph 398

7.3 PROgRAMMINg wITH ARRAYS 411

Partially Filled Arrays 411

Programming Tip: Do Not Skimp on Formal Parameters 414

Programming Example: Searching an Array 414

Programming Example: Sorting an Array 417

Programming Example: Bubble Sort 421

7.4 MuLTIDIMENSIONAL ARRAYS 424

Multidimensional Array Basics 425

Multidimensional Array Parameters 425

Programming Example: Two-Dimensional

Grading Program 427

Pitfall: Using Commas Between Array Indexes 431

contents xxiii

Chapter Summary 432

Answers to Self-Test Exercises 433

Practice Programs 437

Programming Projects 439

Chapter 8 Strings and Vectors 451

8.1 AN ARRAY TYPE FOR STRINgS 453

C-String Values and C-String Variables 453

Pitfall: Using = and == with C Strings 456

Other Functions in 458

Pitfall: Copying past the end of a C-string using strcpy 461

C-String Input and Output 464

C-String-to-Number Conversions and Robust Input 466

8.2 THE STANDARD string CLASS 472

Introduction to the Standard Class string 472

I/O with the Class string 475

Programming Tip: More Versions of getline 478

Pitfall: Mixing cin >> variable; and getline 479

String Processing with the Class string 480

Programming Example: Palindrome Testing 484

Converting Between string Objects and C Strings 487

Converting Between Strings and Numbers 488

8.3 VECTORS 489

Vector Basics 489

Pitfall: Using Square Brackets Beyond the Vector Size 492

Programming Tip: Vector Assignment Is Well Behaved 493

Efficiency Issues 493

Chapter Summary 495

Answers to Self-Test Exercises 495

Practice Programs 497

Programming Projects 498

Chapter 9 Pointers and Dynamic Arrays 507

9.1 POINTERS 508

Pointer Variables 509

Basic Memory Management 516

xxiv contents

Pitfall: Dangling Pointers 517

Static Variables and Automatic Variables 518

Programming Tip: Define Pointer Types 518

9.2 DYNAMIC ARRAYS 521

Array Variables and Pointer Variables 521

Creating and Using Dynamic Arrays 522

Pointer Arithmetic (Optional) 528

Multidimensional Dynamic Arrays (Optional) 530

Chapter Summary 532

Answers to Self-Test Exercises 532

Practice Programs 533

Programming Projects 534

Chapter 10 Defining Classes 541

10.1 STRuCTuRES 542

Structures for Diverse Data 542

Pitfall: Forgetting a Semicolon in a Structure Definition 547

Structures as Function Arguments 548

Programming Tip: Use Hierarchical Structures 549

Initializing Structures 551

10.2 CLASSES 554

Defining Classes and Member Functions 554

Public and Private Members 559

Programming Tip: Make All Member Variables Private 567

Programming Tip: Define Accessor and Mutator Functions 567

Programming Tip: Use the Assignment Operator

with Objects 569

Programming Example: BankAccount Class—Version 1 570

Summary of Some Properties of Classes 574

Constructors for Initialization 576

Programming Tip: Always Include a Default Constructor 584

Pitfall: Constructors with No Arguments 585

Member Initializers and Constructor Delegation in C++11 587

10.3 ABSTRACT DATA TYPES 588

Classes to Produce Abstract Data Types 589

Programming Example: Alternative Implementation of a Class 593

contents xxv

10.4 INTRODuCTION TO INHERITANCE 598

Derived Classes 599

Defining Derived Classes 600

Chapter Summary 604

Answers to Self-Test Exercises 605

Practice Programs 611

Programming Projects 612

Chapter 11 Friends, Overloaded Operators, and Arrays in Classes 619

11.1 FRIEND FuNCTIONS 620

Programming Example: An Equality Function 620

Friend Functions 624

Programming Tip: Define Both Accessor Functions and Friend

Functions 626

Programming Tip: Use Both Member and Nonmember

Functions 628

Programming Example: Money Class (Version 1) 628

Implementation of digit_to_int (Optional) 635

Pitfall: Leading Zeros in Number Constants 636

The const Parameter Modifier 638

Pitfall: Inconsistent Use of const 639

11.2 OVERLOADINg OPERATORS 643

Overloading Operators 644

Constructors for Automatic Type Conversion 647

Overloading Unary Operators 649

Overloading >> and << 650

11.3 ARRAYS AND CLASSES 660

Arrays of Classes 660

Arrays as Class Members 664

Programming Example: A Class for a Partially Filled Array 665

11.4 CLASSES AND DYNAMIC ARRAYS 667

Programming Example: A String Variable Class 668

Destructors 671

Pitfall: Pointers as Call-by-Value Parameters 674

xxvi contents

Copy Constructors 675

Overloading the Assignment Operator 680

Chapter Summary 683

Answers to Self-Test Exercises 683

Practice Programs 693

Programming Projects 694

Chapter 12 Separate Compilation and Namespaces 703

12.1 SEPARATE COMPILATION 704

ADTs Reviewed 705

Case Study: DigitalTime —A Class Compiled Separately 706

Using #ifndef 715

Programming Tip: Defining Other Libraries 718

12.2 NAMESPACES 719

Namespaces and using Directives 719

Creating a Namespace 721

Qualifying Names 724

A Subtle Point About Namespaces (Optional) 725

Unnamed Namespaces 726

Programming Tip: Choosing a Name for a Namespace 731

Pitfall: Confusing the Global Namespace and the Unnamed

Namespace 732

Chapter Summary 733

Answers to Self-Test Exercises 734

Practice Programs 736

Programming Projects 738

Chapter 13 Pointers and Linked Lists 739

13.1 NODES AND LINKED LISTS 740

Nodes 740

nullptr 745

Linked Lists 746

Inserting a Node at the Head of a List 747

Pitfall: Losing Nodes 750

Searching a Linked List 751

contents xxvii

Pointers as Iterators 755

Inserting and Removing Nodes Inside a List 755

Pitfall: Using the Assignment Operator with Dynamic

Data Structures 757

Variations on Linked Lists 760

Linked Lists of Classes 762

13.2 STACKS AND quEuES 765

Stacks 765

Programming Example: A Stack Class 766

Queues 771

Programming Example: A Queue Class 772

Chapter Summary 776

Answers to Self-Test Exercises 776

Practice Programs 779

Programming Projects 780

Chapter 14 Recursion 789

14.1 RECuRSIVE FuNCTIONS FOR TASKS 791

Case Study: Vertical Numbers 791

A Closer Look at Recursion 797

Pitfall: Infinite Recursion 799

Stacks for Recursion 800

Pitfall: Stack Overflow 802

Recursion Versus Iteration 802

14.2 RECuRSIVE FuNCTIONS FOR VALuES 804

General Form for a Recursive Function That Returns a Value 804

Programming Example: Another Powers Function 804

14.3 THINKINg RECuRSIVELY 809

Recursive Design Techniques 809

Case Study: Binary Search—An Example of Recursive Thinking 810

Programming Example: A Recursive Member Function 818

Chapter Summary 822

Answers to Self-Test Exercises 822

Practice Programs 827

Programming Projects 827

xxviii contents

Chapter 15 Inheritance 833

15.1 INHERITANCE BASICS 834

Derived Classes 837

Constructors in Derived Classes 845

Pitfall: Use of Private Member Variables from the Base Class 848

Pitfall: Private Member Functions Are Effectively Not Inherited 850

The protected Qualifier 850

Redefinition of Member Functions 853

Redefining Versus Overloading 856

Access to a Redefined Base Function 858

15.2 INHERITANCE DETAILS 859

Functions That Are Not Inherited 859

Assignment Operators and Copy Constructors in Derived Classes 860

Destructors in Derived Classes 861

15.3 POLYMORPHISM 862

Late Binding 863

Virtual Functions in C++ 864

Virtual Functions and Extended Type Compatibility 869

Pitfall: The Slicing Problem 873

Pitfall: Not Using Virtual Member Functions 874

Pitfall: Attempting to Compile Class Definitions Without

Definitions for Every Virtual Member Function 875

Programming Tip: Make Destructors Virtual 875

Chapter Summary 877

Answers to Self-Test Exercises 877

Practice Programs 881

Programming Projects 884

Chapter 16 Exception Handling 893

16.1 ExCEPTION-HANDLINg BASICS 895

A Toy Example of Exception Handling 895

Defining Your Own Exception Classes 904

Multiple Throws and Catches 904

Pitfall: Catch the More Specific Exception First 908

Programming Tip: Exception Classes Can Be Trivial 909

Throwing an Exception in a Function 909

contents xxix

Exception Specification 911

Pitfall: Exception Specification in Derived Classes 913

16.2 PROgRAMMINg TECHNIquES FOR ExCEPTION HANDLINg 914

When to Throw an Exception 914

Pitfall: Uncaught Exceptions 916

Pitfall: Nested try-catch Blocks 916

Pitfall: Overuse of Exceptions 916

Exception Class Hierarchies 917

Testing for Available Memory 917

Rethrowing an Exception 918

Chapter Summary 918

Answers to Self-Test Exercises 918

Practice Programs 920

Programming Projects 921

Chapter 17 Templates 925

17.1 TEMPLATES FOR ALgORITHM ABSTRACTION 926

Templates for Functions 927

Pitfall: Compiler Complications 931

Programming Example: A Generic Sorting Function 933

Programming Tip: How to Define Templates 937

Pitfall: Using a Template with an Inappropriate Type 938

17.2 TEMPLATES FOR DATA ABSTRACTION 939

Syntax for Class Templates 939

Programming Example: An Array Class 942

Chapter Summary 949

Answers to Self-Test Exercises 949

Practice Programs 953

Programming Projects 953

Chapter 18 Standard Template Library 957

18.1 ITERATORS 959

using Declarations 959

Iterator Basics 960

xxx contents

Programming Tip: Use auto to Simplify Variable Declarations 964

Pitfall: Compiler Problems 964

Kinds of Iterators 966

Constant and Mutable Iterators 970

Reverse Iterators 971

Other Kinds of Iterators 972

18.2 CONTAINERS 973

Sequential Containers 974

Pitfall: Iterators and Removing Elements 978

Programming Tip: Type Definitions in Containers 979

Container Adapters stack and queue 979

Associative Containers set and map 983

Programming Tip: Use Initialization, Ranged For,

and auto with Containers 990

Efficiency 990

18.3 gENERIC ALgORITHMS 991

Running Times and Big-O Notation 992

Container Access Running Times 995

Nonmodifying Sequence Algorithms 997

Container Modifying Algorithms 1001

Set Algorithms 1003

Sorting Algorithms 1004

Chapter Summary 1005

Answers to Self-Test Exercises 1005

Practice Programs 1007

Programming Projects 1008

APPENDICES

1 C++ Keywords 1015

2 Precedence of Operators 1016

3 The ASCII Character Set 1018

4 Some Library Functions 1019

5 Inline Functions 1026

6 Overloading the Array Index Square Brackets 1027

7 The this Pointer 1029

8 Overloading Operators as Member Operators 1032

INDEx 1034

Introduction to Computers and

C++ Programming

1.1 Computer SyStemS 2 Hardware 2 Software 7 High-Level Languages 8 Compilers 9 History Note 12

1.2 proGrAmmING AND proBLem-SoLVING 12

Algorithms 12 Program Design 15 Object-Oriented Programming 16 The Software Life Cycle 17

1.3 INtroDuCtIoN to C++ 18 Origins of the C++ Language 18 A Sample C++ Program 19

Pitfall: Using the Wrong Slash in \n 23 Programming Tip: Input and Output

Syntax 23 Layout of a Simple C++ Program 24 Pitfall: Putting a Space Before the include

File Name 26 Compiling and Running a C++ Program 26 Pitfall: Compiling a C++11 Program 27 Programming Tip: Getting Your Program

to Run 27

1.4 teStING AND DeBuGGING 29 Kinds of Program Errors 30 Pitfall: Assuming Your Program Is Correct 31

1

Chapter Summary 32 Answers to Self-test exercises 33

practice programs 35 programming projects 36

IntroductIon

In this chapter we describe the basic components of a computer, as well as the basic technique for designing and writing a program. We then show you a sample C++ program and describe how it works.

1.1 computer SyStemS A set of instructions for a computer to follow is called a program. The collection of programs used by a computer is referred to as the software for that computer. The actual physical machines that make up a computer installation are referred to as hardware. As we will see, the hardware for a computer is conceptually very simple. However, computers now come with a large array of software to aid in the task of programming. This software includes editors, translators, and managers of various sorts. The resulting environment is a complicated and powerful system. In this book we are concerned almost exclusively with software, but a brief overview of how the hardware is organized will be useful.

Hardware

There are three main classes of computers: PCs, workstations, and mainframes. A PC (personal computer) is a relatively small computer designed to be used by one person at a time. Most home computers are PCs, but PCs are also widely used in business, industry, and science. A workstation is essentially a larger and more powerful PC. You can think of it as an “industrial-strength” PC. A mainframe is an even larger computer that typically requires some support staff and generally is shared by more than one user. The distinctions between PCs, workstations, and mainframes are not precise, but the terms are commonly used and do convey some very general information about a computer.

A network consists of a number of computers connected so that they may share resources such as printers and may share information. A network might contain a number of workstations and one or more mainframes, as well as shared devices such as printers.

For our purposes in learning programming, it will not matter whether you are working on a PC, a mainframe, or a workstation. The basic configuration of the computer, as we will view it, is the same for all three types of computers.

2

The whole of the development and operation of analysis are now capable of being executed by machinery. . . . As soon as an Analytical Engine exists, it will necessarily guide the future course of science.

CHArles BABBAge (1792–1871)

1.1 Computer Systems 3

The hardware for most computer systems is organized as shown in Display 1.1. The computer can be thought of as having five main components: the input device(s), the output device(s), the processor (also called the CPU, for central processing unit), the main memory, and the secondary memory. The processor, main memory, and secondary memory are normally housed in a single cabinet. The processor and main memory form the heart of a computer and can be thought of as an integrated unit. Other components connect to the main memory and operate under the direction of the processor. The arrows in Display 1.1 indicate the direction of information flow.

An input device is any device that allows a person to communicate information to the computer. Your primary input devices are likely to be a keyboard and a mouse.

An output device is anything that allows the computer to communicate information to you. The most common output device is a display screen, referred to as a monitor. Quite often, there is more than one output device. For example, in addition to the monitor, your computer probably is connected to a printer for producing output on paper. The keyboard and monitor are sometimes thought of as a single unit called a terminal.

Display 1.1 Main Components of a Computer

Main memory

Processor (CPU)

Secondary memory

Input device(s)

Output device(s)

4 CHAPTER 1 / Introduction to Computers and C++ Programming

In order to store input and to have the equivalent of scratch paper for performing calculations, computers are provided with memory. The program that the computer executes is also stored in this memory. A computer has two forms of memory, called main memory and secondary memory. The program that is being executed is kept in main memory, and main memory is, as the name implies, the most important memory. Main memory consists of a long list of numbered locations called memory locations; the number of memory locations varies from one computer to another, ranging from a few thousand to many millions, and sometimes even into the billions. each memory location contains a string of 0s and 1s. The contents of these locations can change. Hence, you can think of each memory location as a tiny blackboard on which the computer can write and erase. In most computers, all memory locations contain the same number of zero/one digits. A digit that can assume only the values 0 or 1 is called a binary digit or a bit. The memory locations in most computers contain eight bits (or some multiple of eight bits). An eight- bit portion of memory is called a byte, so we can refer to these numbered memory locations as bytes. To rephrase the situation, you can think of the computer’s main memory as a long list of numbered memory locations called bytes. The number that identifies a byte is called its address. A data item, such as a number or a letter, can be stored in one of these bytes, and the address of the byte is then used to find the data item when it is needed.

If the computer needs to deal with a data item (such as a large number) that is too large to fit in a single byte, it will use several adjacent bytes to hold the data item. In this case, the entire chunk of memory that holds the data item is still called a memory location. The address of the first of the bytes that make up this memory location is used as the address for this larger memory location. Thus, as a practical matter, you can think of the computer’s main memory as a long list of memory locations of varying sizes. The size of each of these locations is expressed in bytes and the address of the first byte is used as the address (name) of that memory location. Display 1.2 shows a picture of a hypothetical computer’s main memory. The sizes of the memory locations are not fixed, but can change when a new program is run on the computer.

Bytes and Addresses

The fact that the information in a computer’s memory is represented as 0s and 1s need not be of great concern to you when programming in C++

Main memory is divided into numbered locations called bytes. The number associated with a byte is called its address. A group of consecutive bytes is used as the location for a data item, such as a number or letter. The address of the first byte in the group is used as the address of this larger memory location.

1.1 Computer Systems 5

(or in most other programming languages). There is, however, one point about this use of 0s and 1s that will concern us as soon as we start to write programs. The computer needs to interpret these strings of 0s and 1s as numbers, letters, instructions, or other types of information. The computer performs these interpretations automatically according to certain coding schemes. A different code is used for each different type of item that is stored in the computer’s memory: one code for letters, another for whole numbers, another for fractions, another for instructions, and so on. For example, in one commonly used set of codes, 01000001 is the code for the letter A and also for the number 65. In order to know what the string 01000001 in a particular location stands for, the computer must keep track of which code is currently being used for that location. Fortunately, the programmer seldom needs to be concerned with such codes and can safely reason as though the locations actually contained letters, numbers, or whatever is desired.

Display 1.2 Memory locations and Bytes

byte 1 byte 2 byte 3 byte 4 byte 5 byte 6 byte 7 byte 8 byte 9

3 byte location with address 1

2 byte location with address 4

1 byte location with address 6

3 byte location with address 7

Why eight?

A byte is a memory location that can hold eight bits. What is so special about eight? Why not ten bits? There are two reasons why eight is special. First, eight is a power of 2. (8 is 23.) Since computers use bits, which have only two possible values, powers of 2 are more convenient than powers of 10. Second, it turns out that eight bits (one byte) are required to code a single character (such as a letter or other keyboard symbol).

6 CHAPTER 1 / Introduction to Computers and C++ Programming

The memory we have been discussing up until now is the main memory. Without its main memory, a computer can do nothing. However, main memory is only used while the computer is actually following the instructions in a program. The computer also has another form of memory called secondary memory or secondary storage. (The words memory and storage are exact synonyms in this context.) Secondary memory is the memory that is used for keeping a permanent record of information after (and before) the computer is used. some alternative terms that are commonly used to refer to secondary memory are auxiliary memory, auxiliary storage, external memory, and external storage.

Information in secondary storage is kept in units called files, which can be as large or as small as you like. A program, for example, is stored in a file in secondary storage and copied into main memory when the program is run. You can store a program, a letter, an inventory list, or any other unit of information in a file.

several different kinds of secondary memory can be attached to a single computer. The most common forms of secondary memory are hard disks, diskettes, CDs, DVDs, and removable flash memory drives. (Diskettes are also sometimes referred to as floppy disks.) CDs (compact discs) used on computers are basically the same as those used to record and play music, while DVDs (digital video discs) are the same as those used to play videos. CDs and DVDs for computers can be read-only so that your computer can read, but cannot change, the data on the disc; CDs and DVDs for computers can also be read/ write, which can have their data changed by the computer. Hard disks are fixed in place and are normally not removed from the disk drive. Diskettes and CDs can be easily removed from the disk drive and carried to another computer. Diskettes and CDs have the advantages of being inexpensive and portable, but hard disks hold more data and operate faster. Flash drives have largely replaced diskettes today and store data using a type of memory called flash memory. Unlike main memory, flash memory does not require power to maintain the information stored on the device. Other forms of secondary memory are also available, but this list covers most forms that you are likely to encounter.

Main memory is often referred to as RAM or random access memory. It is called random access because the computer can immediately access the data in any memory location. secondary memory often requires sequential access, which means that the computer must look through all (or at least very many) memory locations until it finds the item it needs.

The processor (also known as the central processing unit, or CPU) is the “brain” of the computer. When a computer is advertised, the computer company tells you what chip it contains. The chip is the processor. The processor follows the instructions in a program and performs the calculations specified by the program. The processor is, however, a very simple brain. All it can do is follow a set of simple instructions provided by the programmer. Typical processor instructions say things like “Interpret the 0s and 1s as numbers, and then add the number in memory location 37 to the number in memory location 59, and

1.1 Computer Systems 7

put the answer in location 43,” or “read a letter of input, convert it to its code as a string of 0s and 1s, and place it in memory location 1298.” The processor can add, subtract, multiply, and divide and can move things from one memory location to another. It can interpret strings of 0s and 1s as letters and send the letters to an output device. The processor also has some primitive ability to rearrange the order of instructions. Processor instructions vary somewhat from one computer to another. The processor of a modern computer can have as many as several hundred available instructions. However, these instructions are typically all about as simple as those we have just described.

Software

You do not normally talk directly to the computer, but communicate with it through an operating system. The operating system allocates the computer’s resources to the different tasks that the computer must accomplish. The operating system is actually a program, but it is perhaps better to think of it as your chief servant. It is in charge of all your other servant programs, and it delivers your requests to them. If you want to run a program, you tell the operating system the name of the file that contains it, and the operating system runs the program. If you want to edit a file, you tell the operating system the name of the file and it starts up the editor to work on that file. To most users, the operating system is the computer. Most users never see the computer without its operating system. The names of some common operating systems are UNIX, DOS, Linux, Windows, Mac OS, iOS, and Android.

A program is a set of instructions for a computer to follow. As shown in Display 1.3, the input to a computer can be thought of as consisting of two parts, a program and some data. The computer follows the instructions in the program and in that way performs some process. The data is what we conceptualize as the input to the program. For example, if the program adds two numbers, then the two numbers are the data. In other words, the data is the input to the program, and both the program and the data are input to the computer (usually via the operating system). Whenever we give a computer

Display 1.3 simple View of Running a program

Program

Computer

Data

Output

8 CHAPTER 1 / Introduction to Computers and C++ Programming

both a program to follow and some data for the program, we are said to be running the program on the data, and the computer is said to execute the program on the data. The word data also has a much more general meaning than the one we have just given it. In its most general sense, it means any information available to the computer. The word is commonly used in both the narrow sense and the more general sense.

High-Level Languages

There are many languages for writing programs. In this text we will discuss the C++ programming language and use it to write our programs. C++ is a high-level language, as are most of the other programming languages you are likely to have heard of, such as C, C#, Java, Python, PHP, Pascal, Visual Basic, FOrTrAN, COBOl, lisp, scheme, and Ada. High-level languages resemble human languages in many ways. They are designed to be easy for human beings to write programs in and to be easy for human beings to read. A high-level language, such as C++, contains instructions that are much more complicated than the simple instructions a computer’s processor (CPU) is capable of following.

The kind of language a computer can understand is called a low- level language. The exact details of low-level languages differ from one kind of computer to another. A typical low-level instruction might be the following:

ADD X Y Z

This instruction might mean “Add the number in the memory location called X to the number in the memory location called Y, and place the result in the memory location called Z.” The above sample instruction is written in what is called assembly language. Although assembly language is almost the same as the language understood by the computer, it must undergo one simple translation before the computer can understand it. In order to get a computer to follow an assembly language instruction, the words need to be translated into strings of 0s and 1s. For example, the word ADD might translate to 0110, the X might translate to 1001, the Y to 1010, and the Z to 1011. The version of the instruction above that the computer ultimately follows would then be:

0110 1001 1010 1011

Assembly language instructions and their translation into 0s and 1s differ from machine to machine.

Programs written in the form of 0s and 1s are said to be written in machine language, because that is the version of the program that the computer (the machine) actually reads and follows. Assembly language and machine language are almost the same thing, and the distinction between them will not be important to us. The important distinction is that between

1.1 Computer Systems 9

The complete process of translating and running a C++ program is a bit more complicated than what we show in Display 1.4. Any C++ program you write will use some operations (such as input and output routines) that have already been programmed for you. These items that are already programmed for you (like input and output routines) are already compiled and have their object code waiting to be combined with your program’s object code to produce a complete machine-language program that can be run on the computer. Another program, called a linker, combines the object code for these program pieces with the object code that the compiler produced

machine language and high-level languages like C++: Any high-level language program must be translated into machine language before the computer can understand and follow the program.

Compilers

A program that translates a high-level language like C++ to a machine language is called a compiler. A compiler is thus a somewhat peculiar sort of program, in that its input or data is some other program, and its output is yet another program. To avoid confusion, the input program is usually called the source program or source code, and the translated version produced by the compiler is called the object program or object code. The word code is frequently used to mean a program or a part of a program, and this usage is particularly common when referring to object programs. Now, suppose you want to run a C++ program that you have written. In order to get the computer to follow your C++ instructions, proceed as follows. First, run the compiler using your C++ program as data. Notice that in this case, your C++ program is not being treated as a set of instructions. To the compiler, your C++ program is just a long string of characters. The output will be another long string of characters, which is the machine-language equivalent of your C++ program. Next, run this machine-language program on what we normally think of as the data for the C++ program. The output will be what we normally conceptualize as the output of the C++ program. The basic process is easier to visualize if you have two computers available, as diagrammed in Display 1.4. In reality, the entire process is accomplished by using one computer two times.

Compiler

A compiler is a program that translates a high-level language program, such as a C++ program, into a machine-language program that the computer can directly understand and execute.

10 CHAPTER 1 / Introduction to Computers and C++ Programming

from your C++ program. The interaction of the compiler and the linker are diagrammed in Display 1.5. In routine cases, many systems will do this linking for you automatically. Thus, you may not need to worry about linking in many cases.

Linking

Display 1.4 Compiling and Running a C++ program (Basic Outline)

C++ program Data for C++ program

Compiler

Computer

Machine- language

Computer

Output of C++ program

The object code for your C++ program must be combined with the object code for routines (such as input and output routines) that your program uses. This process of combining object code is called linking and is done by a program called a linker. For simple programs, linking may be done for you automatically.

1.1 Computer Systems 11

SeLf-teSt exerCISeS

1. What are the five main components of a computer?

2. What would be the data for a program to add two numbers?

3. What would be the data for a program that assigns letter grades to students in a class?

4. What is the difference between a machine-language program and a high- level language program?

5. What is the role of a compiler?

6. What is a source program? What is an object program?

7. What is an operating system?

8. What purpose does the operating system serve?

Display 1.5 preparing a C++ program for Running

Complete machine- language code ready to run

Object code for C++ program

Object code for other routines

C++ program

Compiler

Linker

12 CHAPTER 1 / Introduction to Computers and C++ Programming

9. Name the operating system that runs on the computer you use to prepare programs for this course.

10. What is linking?

11. Find out whether linking is done automatically by the compiler you use for this course.

1.2 programmIng and problem-SolvIng The Analytical Engine has no pretensions whatever to originate anything. It can do whatever we know how to order it to perform. It can follow analysis; but it has no power of anticipating any analytical relations or truths. Its prov- ince is to assist us in making available what we are already acquainted with.

ADA AUGUSTA, Countess of Lovelace (1815–1852)

In this section we describe some general principles that you can use to design and write programs. These principles are not particular to C++. They apply no matter what programming language you are using.

Algorithms

When learning your first programming language, it is easy to get the impression that the hard part of solving a problem on a computer is translating your ideas into the specific language that will be fed into the computer. This definitely is not the case. The most difficult part of solving a problem on a computer is discovering the method of solution. After you come up with a method of solution, it is routine to translate your method into the required language, be it C++ or some other programming language. It is therefore helpful to temporarily ignore the programming language and to concentrate instead on for- mulating the steps of the solution and writing them down in plain english, as if the instructions were to be given to a human being rather than a computer. A sequence of instructions expressed in this way is frequently referred to as an algorithm.

A sequence of precise instructions which leads to a solution is called an algorithm. some approximately equivalent words are recipe, method,

HIStory Note Charles Babbage, Ada Augusta

The first truly programmable computer was designed by Charles Babbage, an English mathematician and physical scientist. Babbage began the project sometime before 1822 and worked on it for the rest of his life. Although he never completed the construction of his machine, the design was a conceptual milestone in the history of computing. Much of what we know about Charles Babbage and his computer design comes from the writings of his colleague Ada Augusta, the Countess of Lovelace and the daughter of the poet Byron. Ada Augusta is frequently given the title of the first computer programmer. Her comments, quoted in the opening of the this section, still apply to the process of solving problems on a computer. Computers are not magic and do not, at least as yet, have the ability to formulate sophisticated solutions to all the problems we encounter. Computers simply do what the programmer orders them to do. The solutions to problems are carried out by the computer, but the solutions are formulated by the programmer. Our discussion of computer programming begins with a discussion of how a programmer formulates these solutions.

1.2 Programming and Problem-Solving 13

directions, procedure, and routine. The instructions may be expressed in a programming language or a human language. Our algorithms will be expressed in english and in the programming language C++. A computer program is simply an algorithm expressed in a language that a computer can understand. Thus, the term algorithm is more general than the term program. However, when we say that a sequence of instructions is an algorithm, we usually mean that the instructions are expressed in english, since if they were expressed in a programming language we would use the more specific term program. An example may help to clarify the concept.

Display 1.6 contains an algorithm expressed in english. The algorithm determines the number of times a specified name occurs on a list of names. If the list contains the winners of each of last season’s football games and the name is that of your favorite team, then the algorithm determines how many games your team won. The algorithm is short and simple but is otherwise very typical of the algorithms with which we will be dealing.

Ada Augusta, Countess of Lovelace and the first computer programmer

A model of Babbage’s computer

Charles Babbage

14 CHAPTER 1 / Introduction to Computers and C++ Programming

The instructions numbered 1 through 5 in our sample algorithm are meant to be carried out in the order they are listed. Unless otherwise specified, we will always assume that the instructions of an algorithm are carried out in the order in which they are given (written down). Most interesting algorithms do, however, specify some change of order, usually a repeating of some instruction again and again such as in instruction 4 of our sample algorithm.

The word algorithm has a long history. It derives from the name al- Khowarizmi, a ninth-century Persian mathematician and astronomer. He wrote a famous textbook on the manipulation of numbers and equations. The book was entitled Kitab al-jabr w’almuqabala, which can be translated as Rules for Reuniting and Reducing. The similar-sounding word algebra was derived from the Arabic word al-jabr, which appears in the title of the book and which is often translated as reuniting or restoring. The meanings of the words algebra and algorithm used to be much more intimately related than they are today. Indeed, until modern times, the word algorithm usually referred only to algebraic rules for solving numerical equations. Today, the word algorithm can be applied to a wide variety of kinds of instructions for manipulating symbolic as well as numeric data. The properties that qualify a set of instructions as an algorithm now are determined by the nature of the instructions rather than by the things manipulated by the instructions. To qualify as an algorithm, a set of instructions must completely and unambiguously specify the steps to be taken and the order in which they are taken. The person or machine carrying out the algorithm does exactly what the algorithm says, neither more nor less.

Display 1.6 an algorithm

Algorithm that determines how many times a name occurs in a list of names:

1. Get the list of names. 2. Get the name being checked. 3. Set a counter to zero. 4. Do the following for each name on the list: Compare the name on the list to the name being checked, and if the names are the same, then add one to the counter. 5. Announce that the answer is the number indicated by the counter.

Algorithm

An algorithm is a sequence of precise instructions that leads to a solution.

1.2 Programming and Problem-Solving 15

Program Design

Designing a program is often a difficult task. There is no complete set of rules, no algorithm to tell you how to write programs. Program design is a creative process. still, there is the outline of a plan to follow. The outline is given in diagrammatic form in Display 1.7. As indicated there, the entire program design process can be divided into two phases, the problem-solving phase and the implementation phase. The result of the problem-solving phase is an algorithm, expressed in english, for solving the problem. To produce a program in a programming language such as C++, the algorithm is translated into the programming language. Producing the final program from the algorithm is called the implementation phase.

The first step is to be certain that the task—what you want your program to do—is completely and precisely specified. Do not take this step lightly. If you do not know exactly what you want as the output of your program, you may be surprised at what your program produces. Be certain that you know what the input to the program will be and exactly what information is supposed to be in the output, as well as what form that information should be in. For example, if the program is a bank accounting program, you must know not only the interest rate but also whether interest is to be compounded annually, monthly, daily, or whatever. If the program is supposed to write poetry, you need to determine whether the poems can be in free verse or must be in iambic pentameter or some other meter.

Many novice programmers do not understand the need to design an algorithm before writing a program in a programming language, such as C++, and so they try to short-circuit the process by omitting the problem- solving phase entirely, or by reducing it to just the problem-definition part. This seems reasonable. Why not “go for the mark” and save time? The answer is that it does not save time! experience has shown that the two-phase process will produce a correctly working program faster. The two-phase process simplifies the algorithm design phase by isolating it from the detailed rules of a programming language such as C++. The result is that the algorithm design process becomes much less intricate and much less prone to error. For even a modest-size program, it can represent the difference between a half day of careful work and several frustrating days of looking for mistakes in a poorly understood program.

The implementation phase is not a trivial step. There are details to be concerned about, and occasionally some of these details can be subtle, but it is much simpler than you might at first think. Once you become familiar with C++ or any other programming language, the translation of an algorithm from english into the programming language becomes a routine task.

As indicated in Display 1.7, testing takes place in both phases. Before the program is written, the algorithm is tested, and if the algorithm is found to be deficient, then the algorithm is redesigned. That desktop testing is performed by mentally going through the algorithm and executing the steps yourself.

16 CHAPTER 1 / Introduction to Computers and C++ Programming

For large algorithms this will require a pencil and paper. The C++ program is tested by compiling it and running it on some sample input data. The compiler will give error messages for certain kinds of errors. To find other types of errors, you must somehow check to see whether the output is correct.

The process diagrammed in Display 1.7 is an idealized picture of the program design process. It is the basic picture you should have in mind, but reality is sometimes more complicated. In reality, mistakes and deficiencies are discovered at unexpected times, and you may have to back up and redo an earlier step. For example, as shown in Display 1.7, testing the algorithm might reveal that the definition of the problem was incomplete. In such a case you must back up and reformulate the definition. Occasionally, deficiencies in the definition or algorithm may not be observed until a program is tested. In that case you must back up and modify the problem definition or algorithm and all that follows them in the design process.

Object-Oriented Programming

The program design process that we outlined in the previous section represents a program as an algorithm (set of instructions) for manipulating some data. That is a correct view, but not always the most productive view. Modern programs are usually designed using a method known as object- oriented programming, or OOP. In OOP, a program is viewed as a collection

Display 1.7 program Design process

Translating to C++

Testing

Start

Working program

Desktop testing

Algorithm design

Problem definition

Problem-solving phase

Implementation phase

1.2 Programming and Problem-Solving 17

of interacting objects. The methodology is easiest to understand when the program is a simulation program. For example, for a program to simulate a highway interchange, the objects might represent the automobiles and the lanes of the highway. each object has algorithms that describe how it should behave in different situations. Programming in the OOP style consists of designing the objects and the algorithms they use. When programming in the OOP framework, the term Algorithm design in Display 1.7 would be replaced with the phrase Designing the objects and their algorithms.

The main characteristics of OOP are encapsulation, inheritance, and polymorphism. encapsulation is usually described as a form of information hiding or abstraction. That description is correct, but perhaps an easier- to-understand characterization is to say that encapsulation is a form of simplification of the descriptions of objects. Inheritance has to do with writing reusable program code. Polymorphism refers to a way that a single name can have multiple meanings in the context of inheritance. Having made those statements, we must admit that they hold little meaning for readers who have not heard of OOP before. However, we will describe all these terms in detail later in this book. C++ accommodates OOP by providing classes, a kind of data type combining both data and algorithms.

The Software Life Cycle

Designers of large software systems, such as compilers and operating systems, divide the software development process into six phases collectively known as the software life cycle. The six phases of this life cycle are:

1. Analysis and specification of the task (problem definition)

2. Design of the software (object and algorithm design)

3. Implementation (coding)

4. Testing

5. Maintenance and evolution of the system

6. Obsolescence

We did not mention the last two phases in our discussion of program design because they take place after the program is finished and put into service. However, they should always be kept in mind. You will not be able to add improvements or corrections to your program unless you design it to be easy to read and easy to change. Designing programs so that they can be easily modified is an important topic that we will discuss in detail when we have developed a bit more background and a few more programming techniques. The meaning of obsolescence is obvious, but it is not always easy to accept. When a program is not working as it should and cannot be fixed with a reasonable amount of effort, it should be discarded and replaced with a completely new program.

18 CHAPTER 1 / Introduction to Computers and C++ Programming

SeLf-teSt exerCISeS

12. An algorithm is approximately the same thing as a recipe, but some kinds of steps that would be allowed in a recipe are not allowed in an algorithm. Which steps in the following recipe would be allowed in an algorithm?

Place 2 teaspoons of sugar in mixing bowl. Add 1 egg to mixing bowl. Add 1 cup of milk to mixing bowl. Add 1 ounce of rum, if you are not driving. Add vanilla extract to taste. Beat until smooth. Pour into a pretty glass. Sprinkle with nutmeg.

13. What is the first step you should take when creating a program?