Malik c++ programming exercises solutions

C++ PROGRAMMING: PROGRAM DESIGN INCLUDING DATA STRUCTURES

FIFTH EDITION

D.S. MALIK

Australia � Brazil � Japan � Korea � Mexico � Singapore � Spain � United Kingdom � United States

This is an electronic version of the print textbook. Due to electronic rights restrictions, some third party content may be suppressed. Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. The publisher reserves the right to remove content from this title at any time if subsequent rights restrictions require it. For valuable information on pricing, previous editions, changes to current editions, and alternate formats, please visit www.cengage.com/highered to search by ISBN#, author, title, or keyword for materials in your areas of interest.

www.cengage.com/highered
C++ Programming: Program Design Including Data Structures, Fifth Edition D.S. Malik

Executive Editor: Marie Lee

Acquisitions Editor: Amy Jollymore

Senior Product Manager: Alyssa Pratt

Editorial Assistant: Zina Kresin

Content Project Manager: Matthew Hutchinson

Art Director: Faith Brosnan

Print Buyer: Julio Esperas

Proofreader: GreenPen QA

Indexer: Elizabeth Cunningham

Cover Designer: Roycroft Design/ www.roycroftdesign.com

Cover Photo: Contemporary Building ª Steve Hix/Somos Images/Corbis

Compositor: Integra

ª 2011 Course Technology, Cengage Learning

ALL RIGHTS RESERVED. No part of this work covered by the copyright herein may be reproduced, transmitted, stored or used in any form or by any means graphic, electronic, or mechanical, including but not limited to photocopying, recording, scanning, digitizing, taping, Web distribution, information networks, or information storage and retrieval systems, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without the prior written permission of the publisher.

For product information and technology assistance, contact us at Cengage Learning Customer & Sales Support, 1-800-354-9706 For permission to use material from this text or product, submit

all requests online at www.cengage.com/permissions

Further permissions questions can be emailed to permissionrequest@cengage.com

Library of Congress Control Number: 2010921540

ISBN-13: 978-0-538-79809-2

ISBN-10: 0-538-79809-2

Course Technology 20 Channel Center Street Boston, MA 02210 USA

Some of the product names and company names used in this book have been used for identification purposes only and may be trademarks or registered trademarks of their respective manufacturers and sellers.

Any fictional data related to persons or companies or URLs used throughout this book is intended for instructional purposes only. At the time this book was printed, any such data was fictional and not belonging to any real persons or companies.

Course Technology, a part of Cengage Learning, reserves the right to revise this publication and make changes from time to time in its content without notice.

The programs in this book are for instructional purposes only. They have been tested with care, but are not guaranteed for any particular intent beyond educational purposes. The author and the publisher do not offer any warranties or representations, nor do they accept any liabilities with respect to the programs.

Cengage Learning is a leading provider of customized learning solutions with office locations around the globe, including Singapore, the United Kingdom, Australia, Mexico, Brazil and Japan. Locate your local office at: www.cengage.com/global

Cengage Learning products are represented in Canada by Nelson Education, Ltd.

To learn more about Course Technology, visit www.cengage.com/coursetechnology

Purchase any of our products at your local college store or at our preferred online store www.CengageBrain.com

TO

My Parents

Printed in the United States of America 1 2 3 4 5 6 7 16 15 14 13 12 11 10

www.cengage.com/permissions
www.roycroftdesign.com
www.cengage.com/global
www.cengage.com/coursetechnology
www.CengageBrain.com
PREFACE xxv

1. An Overview of Computers and Programming Languages 1

2. Basic Elements of C++ 27

3. Input/Output 117

4. Control Structures I (Selection) 175

5. Control Structures II (Repetition) 247

6. User-Defined Functions I 319

7. User-Defined Functions II 361

8. User-Defined Simple Data Types, Namespaces,

and the string Type 433

9. Arrays and Strings 485

10. Records (structs) 563

11. Classes and Data Abstraction 601

12. Inheritance and Composition 675

13. Pointers, Classes, Virtual Functions, Abstract Classes, and Lists 745

14. Overloading and Templates 827

15. Exception Handling 919

16. Recursion 959

17. Linked Lists 991

18. Stacks and Queues 1083

BRIEF CONTENTS

19. Searching and Sorting Algorithms 1183

20. Binary Trees 1265

21. Graphs 1321

22. Standard Template Library (STL) 1361

APPENDIX A Reserved Words 1477

APPENDIX B Operator Precedence 1479

APPENDIX C Character Sets 1481

APPENDIX D Operator Overloading 1485

APPENDIX E Additional C++ Topics 1487

APPENDIX F Header Files 1509

APPENDIX G Memory Size on a System and Random

Number Generator 1519

APPENDIX H References 1521

APPENDIX I Answers to Odd-Numbered Exercises 1523

INDEX 1555

iv | C++ Programming: Program Design Including Data Structures, Fifth Edition

TABLE OF CONTENTS

Preface xxv

AN OVERVIEW OF COMPUTERS AND PROGRAMMING

LANGUAGES 1

Introduction 2

A Brief Overview of the History of Computers 2

Elements of a Computer System 3

Hardware 4

Central Processing Unit and Main Memory 4

Input /Output Devices 5

Software 6

The Language of a Computer 6

The Evolution of Programming Languages 8

Processing a C++ Program 10

Programming with the Problem Analysis–Coding–Execution Cycle 12

Programming Methodologies 20

Structured Programming 20

Object-Oriented Programming 20

ANSI/ISO Standard C++ 22

Quick Review 22

Exercises 23

BASIC ELEMENTS OF C++ 27

A C++ Program 28

The Basics of a C++ Program 31

Comments 32

Special Symbols 32

1

2

Reserved Words (Keywords) 33

Identifiers 33

Whitespaces 34

Data Types 35

Simple Data Types 35

Floating-Point Data Types 38

Arithmetic Operators and Operator Precedence 39

Order of Precedence 43

Expressions 44

Mixed Expressions 45

Type Conversion (Casting) 47

string Type 49

Input 50

Allocating Memory with Constants and Variables 50

Putting Data into Variables 53

Assignment Statement 53

Saving and Using the Value of an Expression 56

Declaring and Initializing Variables 57

Input (Read) Statement 58

Variable Initialization 61

Increment and Decrement Operators 65

Output 67

Preprocessor Directives 75

namespace and Using cin and cout in a Program 76

Using the string Data Type in a Program 76

Creating a C++ Program 77

Debugging: Understanding and Fixing Syntax Errors 80

Program Style and Form 84

Syntax 84

Use of Blanks 85

Use of Semicolons, Brackets, and Commas 85

Semantics 85

Naming Identifiers 85

Prompt Lines 86

Documentation 87

Form and Style 87

More on Assignment Statements 89

Programming Example: Convert Length 91

vi | C++ Programming: Program Design Including Data Structures, Fifth Edition

Programming Example: Make Change 94

Quick Review 98

Exercises 100

Programming Exercises 109

INPUT/OUTPUT 117

I/O Streams and Standard I/O Devices 118

cin and the Extraction Operator >> 119

Using Predefined Functions in a Program 124

cin and the get Function 127

cin and the ignore Function 128

The putback and peek Functions 130

The Dot Notation between I/O Stream Variables

and I/O Functions: A Precaution 132

Input Failure 133

The clear Function 135

Output and Formatting Output 137

setprecision Manipulator 137

fixed Manipulator 138

showpoint Manipulator 139

setw 142

Additional Output Formatting Tools 144

setfill Manipulator 144

left and right Manipulators 146

Input/Output and the string Type 148

Debugging: Understanding Logic Errors

and Debugging with cout Statements 149

File Input/Output 152

Programming Example: Movie Tickets Sale and Donation to Charity 156

Programming Example: Student Grade 162

Quick Review 165

Exercises 166

Programming Exercises 170

CONTROL STRUCTURES I (SELECTION) 175

Control Structures 176

Relational Operators 177

Relational Operators and Simple Data Types 178

3

4

Table of Contents | vii

Comparing Characters 179

Relational Operators and the string Type 180

Logical (Boolean) Operators and Logical Expressions 182

Order of Precedence 184

int Data Type and Logical (Boolean) Expressions 187

bool Data Type and Logical (Boolean) Expressions 188

Selection: if and if...else 188

One-Way Selection 189

Two-Way Selection 191

Compound (Block of) Statements 195

Multiple Selections: Nested if 195

Comparing if...else Statements with a Series of if Statements 198

Short-Circuit Evaluation 199

Comparing Floating-Point Numbers for Equality: A Precaution 200

Associativity of Relational Operators: A Precaution 201

Avoiding Bugs by Avoiding Partially Understood

Concepts and Techniques 203

Input Failure and the if Statement 206

Confusion between the Equality Operator (==) and

the Assignment Operator (=) 209

Conditional Operator (?:) 211

Program Style and Form (Revisited): Indentation 211

Using Pseudocode to Develop, Test, and Debug a Program 212

switch Structures 215

Avoiding Bugs by Avoiding Partially Understood Concepts

and Techniques (Revisited) 221

Terminating a Program with the assert Function 223

Programming Example: Cable Company Billing 225

Quick Review 231

Exercises 232

Programming Exercises 241

CONTROL STRUCTURES II (REPETITION) 247

Why Is Repetition Needed? 248

while Looping (Repetition) Structure 249

Designing while Loops 251

Case 1: Counter-Controlled while Loops 252

Case 2: Sentinel-Controlled while Loops 255

5

viii | C++ Programming: Program Design Including Data Structures, Fifth Edition

Case 3: Flag-Controlled while Loops 259

Case 4: EOF-Controlled while Loops 263

eof Function 263

More on Expressions in while Statements 268

Programming Example: Fibonacci Number 269

for Looping (Repetition) Structure 273

Programming Example: Classifying Numbers 281

do...while Looping (Repetition) Structure 284

Choosing the Right Looping Structure 289

break and continue Statements 289

Nested Control Structures 291

Avoiding Bugs by Avoiding Patches 296

Debugging Loops 299

Quick Review 300

Exercises 301

Programming Exercises 313

USER-DEFINED FUNCTIONS I 319

Predefined Functions 320

User-Defined Functions 324

Value-Returning Functions 324

Syntax: Value-Returning Functions 326

Syntax: Formal Parameter List 326

Function Call 326

Syntax: Actual Parameter List 327

return Statement 327

Syntax: return Statement 327

Function Prototype 331

Syntax: Function Prototype 332

Value-Returning Functions: Some Peculiarity 333

More Examples of Value-Returning Functions 335

Flow of Execution 340

Programming Example: Largest Number 341

Programming Example: Cable Company 343

Quick Review 349

Exercises 350

Programming Exercises 356

6

Table of Contents | ix

USER-DEFINED FUNCTIONS II 361

Void Functions 362

Value Parameters 367

Reference Variables as Parameters 368

Calculate Grade 369

Value and Reference Parameters and Memory Allocation 372

Reference Parameters and Value-Returning Functions 382

Scope of an Identifier 382

Global Variables, Named Constants, and Side Effects 386

Static and Automatic Variables 391

Debugging: Using Drivers and Stubs 392

Function Overloading: An Introduction 395

Functions with Default Parameters 396

Programming Example: Classify Numbers 399

Programming Example: Data Comparison 404

Quick Review 414

Exercises 416

Programming Exercises 424

USER-DEFINED SIMPLE DATA TYPES, NAMESPACES,

AND THE string TYPE 433

Enumeration Type 434

Declaring Variables 436

Assignment 436

Operations on Enumeration Types 437

Relational Operators 437

Input /Output of Enumeration Types 438

Functions and Enumeration Types 440

Declaring Variables When Defining the Enumeration Type 442

Anonymous Data Types 442

typedef Statement 443

Programming Example: The Game of Rock, Paper, and Scissors 444

Namespaces 452

string Type 458

Additional string Operations 461

Programming Example: Pig Latin Strings 471

7

8

x | C++ Programming: Program Design Including Data Structures, Fifth Edition

Quick Review 475

Exercises 477

Programming Exercises 481

ARRAYS AND STRINGS 485

Arrays 487

Accessing Array Components 488

Processing One-Dimensional Arrays 491

Array Index Out of Bounds 494

Array Initialization During Declaration 495

Partial Initialization of Arrays During Declaration 496

Some Restrictions on Array Processing 496

Arrays as Parameters to Functions 497

Constant Arrays as Formal Parameters 498

Base Address of an Array and Array in Computer Memory 501

Functions Cannot Return a Value of the Type Array 503

Integral Data Type and Array Indices 506

Other Ways to Declare Arrays 507

Searching an Array for a Specific Item 507

C-Strings (Character Arrays) 510

String Comparison 512

Reading and Writing Strings 514

String Input 514

String Output 515

Specifying Input/Output Files at Execution Time 516

string Type and Input/Output Files 516

Parallel Arrays 517

Two- and Multidimensional Arrays 518

Accessing Array Components 520

Two-Dimensional Array Initialization During Declaration 521

Two-Dimensional Arrays and Enumeration Types 521

Initialization 524

Print 525

Input 525

Sum by Row 525

Sum by Column 526

Largest Element in Each Row and Each Column 526

Passing Two-Dimensional Arrays as Parameters to Functions 527

9

Table of Contents | xi

Arrays of Strings 530

Arrays of Strings and the string Type 530

Arrays of Strings and C-Strings (Character Arrays) 530

Another Way to Declare a Two-Dimensional Array 531

Multidimensional Arrays 532

Programming Example: Code Detection 534

Programming Example: Text Processing 540

Quick Review 547

Exercises 548

Programming Exercises 558

RECORDS (structS) 563

Records (structs) 564

Accessing struct Members 566

Assignment 568

Comparison (Relational Operators) 569

Input /Output 570

struct Variables and Functions 570

Arrays versus structs 571

Arrays in structs 572

structs in Arrays 574

structs within a struct 576

Programming Example: Sales Data Analysis 580

Quick Review 594

Exercises 594

Programming Exercises 597

CLASSES AND DATA ABSTRACTION 601

Classes 602

Unified Modeling Language Class Diagrams 606

Variable (Object) Declaration 606

Accessing Class Members 607

Built-in Operations on Classes 608

Assignment Operator and Classes 609

Class Scope 609

Functions and Classes 610

Reference Parameters and Class Objects (Variables) 610

10

11

xii | C++ Programming: Program Design Including Data Structures, Fifth Edition

Implementation of Member Functions 611

Accessor and Mutator Functions 616

Order of public and private Members of a Class 619

Constructors 621

Invoking a Constructor 623

Invoking the Default Constructor 623

Invoking a Constructor with Parameters 623

Constructors and Default Parameters 626

Classes and Constructors: A Precaution 626

Arrays of Class Objects (Variables) and Constructors 627

Destructors 629

Data Abstraction, Classes, and Abstract Data Types 630

A struct Versus a class 632

Information Hiding 633

Executable Code 637

Static Members of a Class 643

Programming Example: Candy Machine 649

Quick Review 663

Exercises 665

Programming Exercises 670

INHERITANCE AND COMPOSITION 675

Inheritance 676

Redefining (Overriding) Member Functions

of the Base Class 679

Constructors of Derived and Base Classes 686

Destructors in a Derived Class 694

Multiple Inclusions of a Header File 695

C++ Stream Classes 696

Protected Members of a Class 698

Inheritance as public, protected, or private 698

Composition (Aggregation) 702

Object-Oriented Design (OOD) and Object-Oriented Programming (OOP) 707

Identifying Classes, Objects, and Operations 709

Programming Example: Grade Report 710

Quick Review 731

Exercises 732

Programming Exercises 739

12

Table of Contents | xiii

POINTERS, CLASSES, VIRTUAL FUNCTIONS,

ABSTRACT CLASSES, AND LISTS 745

Pointer Data Type and Pointer Variables 746

Declaring Pointer Variables 746

Address of Operator (&) 747

Dereferencing Operator (*) 748

Classes, Structs, and Pointer Variables 752

Initializing Pointer Variables 755

Dynamic Variables 755

Operator new 756

Operator delete 757

Operations on Pointer Variables 759

Dynamic Arrays 761

Functions and Pointers 764

Pointers and Function Return Values 764

Dynamic Two-Dimensional Arrays 765

Shallow versus Deep Copy and Pointers 768

Classes and Pointers: Some Peculiarities 770

Destructor 770

Assignment Operator 772

Copy Constructor 773

Inheritance, Pointers, and Virtual Functions 780

Classes and Virtual Destructors 787

Abstract Classes and Pure Virtual Functions 787

Array Based Lists 796

Unordered Lists 803

Ordered Lists 807

Address of Operator and Classes 809

Quick Review 812

Exercises 815

Programming Exercises 822

OVERLOADING AND TEMPLATES 827

Why Operator Overloading Is Needed 828

Operator Overloading 829

Syntax for Operator Functions 830

13

14

xiv | C++ Programming: Program Design Including Data Structures, Fifth Edition

Overloading an Operator: Some Restrictions 830

Pointer this 831

Friend Functions of Classes 836

Operator Functions as Member Functions and

Nonmember Functions 839

Overloading Binary Operators 842

Overloading the Stream Insertion (<<) and

Extraction (>>) Operators 848

Overloading the Assignment Operator (=) 853

Overloading Unary Operators 861

Operator Overloading: Member versus Nonmember 867

Classes and Pointer Member Variables (Revisited) 868

Operator Overloading: One Final Word 868

Programming Example: Clock Type 868

Programming Example: Complex Numbers 877

Overloading the Array Index (Subscript) Operator ([]) 882

Programming Example: newString 884

Function Overloading 890

Templates 891

Function Templates 891

Class Templates 893

Array-Based Lists (Revisited) 896

Quick Review 902

Exercises 905

Programming Exercises 910

EXCEPTION HANDLING 919

Handling Exceptions within a Program 920

C++ Mechanisms of Exception Handling 924

try/catch Block 924

Using C++ Exception Classes 931

Creating Your Own Exception Classes 935

Rethrowing and Throwing an Exception 941

Exception-Handling Techniques 946

Terminate the Program 946

Fix the Error and Continue 946

Log the Error and Continue 948

15

Table of Contents | xv

Stack Unwinding 948

Quick Review 952

Exercises 954

Programming Exercises 957

RECURSION 959

Recursive Definitions 960

Direct and Indirect Recursion 963

Infinite Recursion 963

Problem Solving Using Recursion 964

Tower of Hanoi: Analysis 973

Recursion or Iteration? 974

Programming Example: Converting a Number from

Binary to Decimal 975

Programming Example: Converting a Number from

Decimal to Binary 979

Quick Review 982

Exercises 983

Programming Exercises 986

LINKED LISTS 991

Linked Lists 992

Linked Lists: Some Properties 993

Deletion 999

Building a Linked List 1000

Linked List as an ADT 1005

Structure of Linked List Nodes 1006

Member Variables of the class linkedListType 1006

Linked List Iterators 1007

Print the List 1013

Length of a List 1013

Retrieve the Data of the First Node 1014

Retrieve the Data of the Last Node 1014

Begin and End 1014

Copy the List 1015

Destructor 1016

Copy Constructor 1016

Overloading the Assignment Operator 1017

16

17

xvi | C++ Programming: Program Design Including Data Structures, Fifth Edition

Unordered Linked Lists 1017

Search the List 1018

Insert the First Node 1019

Insert the Last Node 1020

Header File of the Unordered Linked List 1025

Ordered Linked Lists 1026

Search the List 1027

Insert a Node 1028

Insert First and Insert Last 1032

Delete a Node 1033

Header File of the Ordered Linked List 1034

Print a Linked List in Reverse Order

(Recursion Revisited) 1037

printListReverse 1039

Doubly Linked Lists 1040

Default Constructor 1043

isEmptyList 1043

Destroy the List 1043

Initialize the List 1044

Length of the List 1044

Print the List 1044

Reverse Print the List 1044

Search the List 1045

First and Last Elements 1045

Circular Linked Lists 1051

Programming Example: Video Store 1052

Quick Review 1072

Exercises 1072

Programming Exercises 1077

STACKS AND QUEUES 1083

Stacks 1084

Stack Operations 1086

Implementation of Stacks as Arrays 1088

Initialize Stack 1091

Empty Stack 1092

Full Stack 1092

18

Table of Contents | xvii

Push 1092

Return the Top Element 1094

Pop 1094

Copy Stack 1096

Constructor and Destructor 1096

Copy Constructor 1097

Overloading the Assignment Operator (=) 1097

Stack Header File 1098

Programming Example: Highest GPA 1102

Linked Implementation of Stacks 1106

Default Constructor 1109

Empty Stack and Full Stack 1109

Initialize Stack 1110

Push 1110

Return the Top Element 1112

Pop 1112

Copy Stack 1114

Constructors and Destructors 1115

Overloading the Assignment Operator (=) 1115

Stack as Derived from the class

unorderedLinkedList 1118

Application of Stacks: Postfix Expressions Calculator 1119

Main Algorithm 1122

Function evaluateExpression 1122

Function evaluateOpr 1124

Function discardExp 1126

Function printResult 1126

Removing Recursion: Nonrecursive Algorithm to

Print a Linked List Backward 1129

Queues 1133

Queue Operations 1134

Implementation of Queues as Arrays 1136

Linked Implementation of Queues 1145

Queue Derived from the class

unorderedLinkedListType 1150

Application of Queues: Simulation 1151

Designing a Queuing System 1152

Customer 1153

Server 1156

xviii | C++ Programming: Program Design Including Data Structures, Fifth Edition

Server List 1159

Waiting Customers Queue 1164

Main Program 1166

Quick Review 1171

Exercises 1172

Programming Exercises 1178

SEARCHING AND SORTING ALGORITHMS 1183

Searching and Sorting Algorithms 1184

Search Algorithms 1184

Sequential Search 1185

Binary Search 1187

Performance of Binary Search 1192

Binary Search Algorithm and the class orderedArrayListType 1193

Asymptotic Notation: Big-O Notation 1194

Lower Bound on Comparison-Based Search Algorithms 1202

Sorting Algorithms 1202

Sorting a List: Bubble Sort 1202

Analysis: Bubble Sort 1206

Bubble Sort Algorithm and the class unorderedArrayListType 1207

Selection Sort: Array-Based Lists 1208

Analysis: Selection Sort 1211

Insertion Sort: Array-Based Lists 1212

Analysis: Insertion Sort 1216

Lower Bound on Comparison-Based Sort Algorithms 1216

Quick Sort: Array-Based Lists 1218

Analysis: Quick Sort 1224

Merge Sort: Linked List-Based Lists 1225

Divide 1227

Merge 1229

Analysis: Merge Sort 1232

Programming Example: Election Results 1235

Quick Review 1256

Exercises 1257

Programming Exercises 1260

19

Table of Contents | xix

BINARY TREES 1265

Binary Trees 1266

Copy Tree 1271

Binary Tree Traversal 1272

Implementing Binary Trees 1276

Binary Search Trees 1285

Binary Search Tree: Analysis 1296

Nonrecursive Binary Tree Traversal Algorithms 1297

Nonrecursive Inorder Traversal 1297

Nonrecursive Preorder Traversal 1299

Nonrecursive Postorder Traversal 1300

Binary Tree Traversal and Functions as Parameters 1301

Programming Example: Video Store (Revisited) 1305

Quick Review 1314

Exercises 1316

Programming Exercises 1318

GRAPHS 1321

Introduction 1322

Graph Definitions and Notations 1323

Graph Representation 1326

Adjacency Matrix 1326

Adjacency Lists 1327

Operations on Graphs 1328

Graphs as ADTs 1329

Graph Traversals 1333

Depth First Traversal 1333

Breadth First Traversal 1335

Shortest Path Algorithm 1337

Shortest Path 1339

Minimal Spanning Tree 1345

Quick Review 1355

Exercises 1357

Programming Exercises 1360

20

21

xx | C++ Programming: Program Design Including Data Structures, Fifth Edition

STANDARD TEMPLATE LIBRARY (STL) 1361

Components of the STL 1362

Container Types 1363

Sequence Containers 1363

Sequence Container: vector 1363

Member Functions Common to All Containers 1372

Member Functions Common to Sequence Containers 1374

The copy Algorithm 1375

Sequence Container: deque 1379

Sequence Container: list 1383

Iterators 1390

Types of Iterators 1390

Stream Iterators 1396

Associative Containers 1396

Associative Containers: set and multiset 1397

Declaring set or multiset Associative Containers 1397

Item Insertion and Deletion from set/multiset 1399

Container Adapters 1403

Stack 1403

Queue 1405

Containers, Associated Header Files, and Iterator Support 1406

Algorithms 1407

STL Algorithm Classification 1408

Function Objects 1410

Insert Iterator 1416

STL Algorithms 1418

The Functions fill and fill_n 1418

The Functions generate and generate_n 1420

The Functions find, find_if, find_end, and

find_first_of 1422

The Functions remove, remove_if,

remove_copy, and remove_copy_if 1427

The Functions replace, replace_if,

replace_copy, and replace_copy_if 1430

The Functions swap, iter_swap, and swap_ranges 1434

The Functions search, search_n, sort, and binary_search 1437

The Functions adjacent_find, merge, and

inplace_merge 1441

22

Table of Contents | xxi

The Functions reverse, reverse_copy,

rotate, and rotate_copy 1445

The Functions count, count_if, max, max_element,

min, min_element, and random_shuffle 1448

The Functions for_each and transform 1452

The Functions includes, set_intersection, set_union,

set_difference, and set_symmetric_difference 1455

The Functions accumulate, adjacent_difference,

inner_product, and partial_sum 1463

Quick Review 1468

Exercises 1472

Programming Exercises 1475

APPENDIX A: RESERVED WORDS 1477

APPENDIX B: OPERATOR PRECEDENCE 1479

APPENDIX C: CHARACTER SETS 1481

ASCII (American Standard Code for Information Interchange) 1481

EBCDIC (Extended Binary Coded Decimal Interchange Code) 1482

APPENDIX D: OPERATOR OVERLOADING 1485

APPENDIX E: ADDITIONAL C++ TOPICS 1487

Binary (Base 2) Representation of a Nonnegative Integer 1487

Converting a Base 10 Number to a Binary Number

(Base 2) 1487

Converting a Binary Number (Base 2) to Base 10 1489

Converting a Binary Number (Base 2) to Octal (Base 8)

and Hexadecimal (Base 16) 1490

More on File Input/Output 1492

Binary Files 1492

Random File Access 1498

Naming Conventions of Header Files in ANSI/ISO

Standard C++ and Standard C++ 1506

xxii | C++ Programming: Program Design Including Data Structures, Fifth Edition

APPENDIX F: HEADER FILES 1509

Header File cassert (assert.h) 1509

Header File cctype (ctype.h) 1510

Header File cfloat (float.h) 1511

Header File climits (limits.h) 1512

Header File cmath (math.h) 1514

Header File cstddef (stddef.h) 1515

Header File cstring (string.h) 1515

APPENDIX G: MEMORY SIZE ON A SYSTEM

AND RANDOM NUMBER GENERATOR 1519

Random Number Generator 1520

APPENDIX H: REFERENCES 1521

APPENDIX I: ANSWERS TO ODD-NUMBERED

EXERCISES 1523

Chapter 1 1523

Chapter 2 1526

Chapter 3 1528

Chapter 4 1529

Chapter 5 1531

Chapter 6 1533

Chapter 7 1534

Chapter 8 1535

Chapter 9 1536

Chapter 10 1538

Chapter 11 1539

Chapter 12 1541

Chapter 13 1543

Chapter 14 1544

Chapter 15 1545

Table of Contents | xxiii

Chapter 16 1546

Chapter 17 1547

Chapter 18 1548

Chapter 19 1550

Chapter 20 1551

Chapter 21 1553

Chapter 22 1554

INDEX 1555

xxiv | C++ Programming: Program Design Including Data Structures, Fifth Edition

WELCOME TO THE FIFTH EDITION OF C++ Programming: Program Design Including Data

Structures. Designed for a two semester (CS1 and CS2) C++ course, this text will provide

a breath of fresh air to you and your students. The CS1 and CS2 courses serve as the cornerstone

of the Computer Science curriculum. My primary goal is to motivate and excite all

introductory programming students, regardless of their level. Motivation breeds excite-

ment for learning. Motivation and excitement are critical factors that lead to the success

of the programming student. This text is a culmination and development of my classroom

notes throughout more than fifty semesters of teaching successful programming to

Computer Science students.

C++ Programming: Program Design Including Data Structures started as a collection of brief

examples, exercises, and lengthy programming examples to supplement the books that were

in use at our university. It soon turned into a collection large enough to develop into a text.

The approach taken in this book is, in fact, driven by the students’ demand for clarity and readability.

The material was written and rewritten until the students felt comfortable with it. Most of the

examples in this book resulted from student interaction in the classroom.

As with any profession, practice is essential. Cooking students practice their recipes. Budding

violinists practice their scales. New programmers must practice solving problems and writing

code. This is not a C++ cookbook. We do not simply list the C++ syntax followed by an

example; we dissect the ‘‘why’’ behind all the concepts. The crucial question of ‘‘why?’’ is

answered for every topic when first introduced. This technique offers a bridge to learning

C++. Students must understand the ‘‘why?’’ in order to be motivated to learn.

Traditionally, a C++ programming neophyte needed a working knowledge of another

programming language. This book assumes no prior programming experience. However,

some adequate mathematics background such as college algebra is required.

PREFACE

Warning: This text can be expected to create a serious reduction in the demand for program-

ming help during your office hours. Other side effects include significantly diminished student

dependency on others while learning to program.

Changes in the Fifth Edition The fifth edition contains more than 50 new programming exercises and more than 150 new

exercises. Chapters 2 through 7 include a programming exercise which contains a solution to

a problem; however, the statements are in the incorrect order. So the student is asked to

rewrite the program with statements in the correct order. This will allow students to learn

how to read and debug programs written by someone else. Another major change in this

edition is the inclusion of debugging sections in Chapters 2 through 7. In these sections, a

program with errors is included. The program is compiled, and syntax errors, if any, are

shown. We then show how to interpret the syntax errors and correct them. Some sections

also show how to find and correct logical errors. This edition also includes various new

examples, such as Examples 5-8, 7-8, 12-6, and 12-8. Various sections in Chapters 4, 5, 6, and

7 have been rewritten. Chapter 8 includes additional string functions, and the virtual func-

tions section in Chapter 14 has been rewritten with new examples.

Approach The programming language C++, which evolved from C, is no longer considered an

industry-only language. Numerous colleges and universities use C++ for their first program-

ming language course. C++ is a combination of structured programming and object-oriented

programming, and this book addresses both types.

This book is intended for a two-semester course, CS1 and CS2, in Computer Science. The

first 11 or 12 chapters can be covered in the first course and the remaining in the second

course.

In July 1998, ANSI/ISO Standard C++ was officially approved. This book focuses on ANSI/

ISO Standard C++. Even though the syntax of Standard C++ and ANSI/ISO Standard C++

is very similar, Chapter 8 discusses some of the features of ANSI/ISO Standard C++ that are

not available in Standard C++.

Chapter 1 briefly reviews the history of computers and programming languages. The reader can

quickly skim through this chapter and become familiar with some of the hardware components

and the software parts of the computer. This chapter contains a section on processing a C++

program. This chapter also describes structured and object-oriented programming.

Chapter 2 discusses the basic elements of C++. After completing this chapter, students

become familiar with the basics of C++ and are ready to write programs that are complicated

enough to do some computations. Input/output is fundamental to any programming lan-

guage. It is introduced early, in Chapter 3, and is covered in detail.

Chapters 4 and 5 introduce control structures to alter the sequential flow of execution.

Chapters 6 and 7 study user-defined functions. It is recommended that readers with no prior

programming background spend extra time on Chapters 6 and 7. Several examples are

provided to help readers understand the concepts of parameter passing and the scope of an

identifier.

xxvi | C++ Programming: Program Design Including Data Structures, Fifth Edition

Chapter 8 discusses the user-defined simple data type (enumeration type), the namespace mechanism of ANSI/ISO Standard C++, and the string type. The earlier versions of C did

not include the enumeration type. Enumeration types have very limited use; their main

purpose is to make the program readable. This book is organized such that readers can skip

the section on enumeration types during the first reading without experiencing any discon-

tinuity, and then later go through this section.

Chapter 9 discusses arrays in detail. Chapter 10 introduces records (structs). The introduc- tion of structs in this book is similar to C structs. This chapter is optional; it is not a prerequisite for any of the remaining chapters.

Chapter 11 begins the study of object-oriented programming (OOP) and introduces classes.

The first half of this chapter shows how classes are defined and used in a program. The second

half of the chapter introduces abstract data types (ADTs). This chapter shows how classes in

C++ are a natural way to implement ADTs. Chapter 12 continues with the fundamentals of

object-oriented design (OOD) and OOP, and discusses inheritance and composition. It

explains how classes in C++ provide a natural mechanism for OOD and how C++ supports

OOP. Chapter 12 also discusses how to find the objects in a given problem.

Chapter 13 studies pointers in detail. After introducing pointers and how to use them in a

program, this chapter highlights the peculiarities of classes with pointer data members and

how to avoid them. Moreover, this chapter also discusses how to create and work with

dynamic two-dimensional arrays. Chapter 13 also discusses abstract classes and a type of

polymorphism accomplished via virtual functions.

Chapter 14 continues the study of OOD and OOP. In particular, it studies polymorphism

in C++. Chapter 14 specifically discusses two types of polymorphism—overloading and

templates.

Chapter 15 discusses exception handling in detail. Chapter 16 introduces and discusses

recursion. This is a stand-alone chapter, so it can be studied anytime after Chapter 10.

Chapters 17 and 18 are devoted to the study of data structures. Discussed in detail are linked

lists in Chapter 17 and stacks and queues in Chapter 18. The programming code developed in

these chapters is generic. These chapters effectively use the fundamentals of OOD.

Chapter 19 discusses various searching and sorting algorithms. In addition to showing how

these algorithms work, it also provides relevant analysis and results concerning the perfor-

mance of the algorithms. The algorithm analysis allows the user to decide which algorithm to

use in a particular application. This chapter also includes several sorting algorithms. The

instructor can decide which algorithms to cover.

Chapter 20 provides an introduction to binary trees. Various traversal algorithms, as well as the

basic properties of binary trees, are discussed and illustrated. Special binary trees, called binary

search trees, are introduced. Searching, as well as item insertion and deletion from a binary search

tree, are described and illustrated. Chapter 20 also discusses nonrecursive binary tree traversal

algorithms. Furthermore, to enhance the flexibility of traversal algorithms, it shows how to

construct and pass functions as parameters to other functions. This chapter also discusses AVL

Preface | xxvii

(height balanced) trees in detail. Due to text length considerations, discussion on AVL trees is

provided as a separate section and is available on the Web site accompanying this book.

Graph algorithms are discussed in Chapter 21. After introducing the basic graph theory

terminology, the representation of graphs in computer memory is discussed. This chapter

also discusses graph traversal algorithms, the shortest path algorithm, and the minimal span-

ning tree algorithm. Topological sort is also discussed in this chapter and is available on the

Web site accompanying this book.

C++ is equipped with a powerful library—the Standard Template Library (STL)—of data

structures and algorithms that can be used effectively in a wide variety of applications. Chapter

22 describes the STL in detail. After introducing the three basic components of the STL, it

shows how sequence containers are used in a program. Special containers, such as stack and

queue, are also discussed. The latter half of this chapter shows how various STL algorithms

can be used in a program. This chapter is fairly long; depending on the availability of time, the

instructor can at least cover the sequence containers, iterators, the classes stack and queue,

and certain algorithms.

Appendix A lists the reserved words in C++. Appendix B shows the precedence and

associativity of the C++ operators. Appendix C lists the ASCII (American Standard Code

for Information Interchange) and EBCDIC (Extended Binary Coded Decimal Interchange

Code) character sets. Appendix D lists the C++ operators that can be overloaded.

Appendix E has three objectives. First, we discuss how to convert a number from decimal to

binary and binary to decimal. We then discuss binary and random access files in detail. Finally,

we describe the naming conventions of the header files in both ANSI/ISO Standard C++ and

Standard C++. Appendix F discusses some of the most widely used library routines, and

includes the names of the standard C++ header files. The programs in Appendix G show

how to print the memory size for the built-in data types on your system as well as how to use a

random number generator. Appendix H gives selected references for further study. Appendix I

provides the answers to odd-numbered exercises in the book.

xxviii | C++ Programming: Program Design Including Data Structures, Fifth Edition

How to Use the Book This book can be used in various ways. Figure 1 shows the dependency of the chapters.

Chapter 1

Chapter 2

Chapter 3

Chapter 4

Chapter 5

Chapter 6

Chapter 7

Chapter 8 Chapter 9*

Chapter 19

Chapter 10 Chapter 11

Chapter 12 Chapter 13

Chapter 14

Chapter 15

Chapter 16

Chapter 17

Chapter 18

Chapter 20* Chapter 21

Chapter 22

FIGURE 1 Chapter dependency diagram

Preface | xxix

In Figure 1, dotted lines mean that the preceding chapter is used in one of the sections of the

chapter and is not necessarily a prerequisite for the next chapter. For example, Chapter 9

covers arrays in detail. In Chapters 10 and 11, we show the relationship between arrays and

structs and arrays and classes, respectively. However, if Chapter 11 is studied before Chapter 9, then the section dealing with arrays in Chapter 11 can be skipped without any

discontinuation. This particular section can be studied after studying Chapter 9.

It is recommended that the first seven chapters be covered sequentially. After covering the

first seven chapters, if the reader is interested in learning OOD and OOP early, then Chapter

11 can be studied right after Chapter 7. Chapter 8 can be studied anytime after Chapter 7.

After studying the first seven chapters in sequence, some of the approaches are:

1. Study chapters in the sequence: 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22.

2. Study chapters in the sequence: 9, 11, 13, 14, 12, 16, 17, 18, 15, 19, 20, 21, 22.

3. Study chapters in the sequence: 11, 9, 13, 14, 12, 16, 17, 18, 15, 19, 20, 21, 22.

As the chapter dependency diagram shows, Chapters 18 and 19 can be covered in any sequence.

However, typically, Chapters 18 and 19 are studied in sequence. Ideally, one should study

Chapters 17, 18, 19, and 20 in sequence. Chapters 21 and 22 can be studied in any sequence.

xxx | C++ Programming: Program Design Including Data Structures, Fifth Edition

FEATURES OF THE BOOK

Four-color interior

design shows

accurate C++

code and related

comments.

More than 400

visual

diagrams, both

extensive and

exhaustive,

illustrate difficult

concepts.

Numbered Examples

illustrate the key

concepts with their

relevant code. The

programming code in

these examples is

followed by a Sample

Run. An explanation

then follows that

describes what each

line in the code does.

Exercises further

reinforce learning

and ensure that

students have, in

fact, mastered the

material.

Programming Examples are

programs featured at the

end of each chapter.

Programming Examples are

where everything in the

chapter comes together.

They are highlighted with

an icon in the margin like

the one shown here. These

examples teach problem

solving skills and include

the concrete stages of

input, output, problem

analysis and algorithm

design, class design, and a

program listing All

programs are designed to

be methodical, consistent,

and user-friendly. Each

Programming Example

starts with a problem

analysis that is followed by

the algorithm design and/or

class design. Every step of

the algorithm is coded in

C++. In addition to helping

students learn problem

solving techniques, these

detailed programs show the

student how to implement

concepts in an actual C++

program. We strongly

recommend that students

study the Programming

Examples carefully in order to learn C++ effectively. Students typically learn much from completely worked-out

programs. Further, programming examples reduce considerably the students’ need for help outside the classroom and

bolster the students’ self-confidence.

Programming

Exercises challenge

students to write

C++ programs with

a specified

outcome.

The following supplemental materials are available when this book is used in a classroom

setting. All instructor materials as outlined below are available at the Companion Site for the

text at www.cengage.com.

Electronic Instructor’s Manual The Instructor’s Manual that accompanies this textbook includes:

• Additional instructional material to assist in class preparation, including suggestions for lecture topics.

• Solutions to all the end-of-chapter materials, including the Programming Exercises.

ExamView�

This textbook is accompanied by ExamView, a powerful testing software package that allows

instructors to create and administer printed, computer (LAN-based), and Internet exams.

ExamView includes hundreds of questions that correspond to the topics covered in this text,

enabling students to generate detailed study guides that include page references for further

review. These computer-based and Internet testing components allow students to take exams

at their computers, and save the instructor time because each exam is graded automatically.

PowerPoint Presentations This book comes with Microsoft PowerPoint slides for each chapter. These are included as a

teaching aid for classroom presentations, either to make available to students on the network

for chapter review, or to be printed for classroom distribution. Instructors can add their own

slides for additional topics that they introduce to the class. The PowerPoint slides for the book

are also available on the Instructor Resources CD.

Distance Learning Cengage Learning is proud to present online courses in WebCT and Blackboard to provide

the most complete and dynamic learning experience possible. For more information on how

SUPPLEMENTAL RESOURCES

www.cengage.com
to bring distance learning to your course, contact your local Cengage Learning sales

representative.

Source Code The source code, in ANSI/ISO Standard C++, is available at the Companion Site for the text

at www.cengage.com/coursetechnology, and is also available on the Instructor Resources

CD-ROM. The input files needed to run some of the programs are also included with the

source code.

Solution Files The solution files for all programming exercises, in ANSI/ISO C++, are available at the

Companion Site for the text at www.cengage.com/coursetechnology and are also available on

the Instructor Resources CD-ROM. The input files needed to run some of the programming

exercises are also included with the solution files.

xxxviii | C++ Programming: Program Design Including Data Structures, Fifth Edition

www.cengage.com/coursetechnology
www.cengage.com/coursetechnology
There are many people that I must thank who, one way or another, contributed to the success

of this book. First, I would like to thank all the students who, during the preparation, were

spontaneous in telling me if certain portions needed to be reworded for better understanding

and clearer reading. Next, I would like to thank those who e-mailed numerous comments

to improve upon the third edition. I am thankful to Professors S.C. Cheng, Randall Crist, and

Vasant Raval for constantly supporting this project. I am also very grateful to the reviewers

who reviewed earlier versions of this book and offered many critical suggestions on how to

improve it.

I owe a great deal to the following reviewers who patiently read each page of every chapter of

the current version and made critical comments to improve the book: Stefano Basagni,

Northeastern University; Jeff Ringenberg, University of Michigan; Colleen van Lent, Uni-

versity of Michigan; Tuan Vo, Mt. San Antonio College; Kerstin Voigt, California State

University, San Bernardino; Lan Yang, Cal Poly Pomona. The reviewers will recognize that

their criticisms have not been overlooked and, in fact, made this a better book.

Next, I express thanks to Amy Jollymore, Acquisitions Editor, for recognizing the importance

and uniqueness of this project. All this would not have been possible without the careful

planning of Senior Product Manager Alyssa Pratt. I extend my sincere thanks to Alyssa, as well

as to Content Project Manager Matthew Hutchinson. I also thank Tintu Thomas of Integra

Software Services for assisting us in keeping the project on schedule. I would like to thank

Chris Scriver and Serge Palladino of Course Technology for patiently and carefully testing the

code and discovering typos and errors.

This book is dedicated to my parents, who I thank for their blessings.

Finally, I am thankful for the support of my wife Sadhana and especially my daughter Shelly.

They cheered me up whenever I was overwhelmed during the writing of this book. I welcome

any comments concerning the text. Comments may be forwarded to the following e-mail

address: malik@creighton.edu.

D. S. Malik

ACKNOWLEDGEMENTS

This page intentionally left blank

AN OVERVIEW OF COMPUTERS AND PROGRAMMING LANGUAGES

IN THIS CHAPTER , YOU WILL :

. Learn about different types of computers

. Explore the hardware and software components of a computer system

. Learn about the language of a computer

. Learn about the evolution of programming languages

. Examine high-level programming languages

. Discover what a compiler is and what it does

. Examine a C++ program

. Explore how a C++ program is processed

. Learn what an algorithm is and explore problem-solving techniques

. Become aware of structured design and object-oriented design programming methodologies

. Become aware of Standard C++ and ANSI/ISO Standard C++

1C H A P T E R

Introduction Terms such as ‘‘the Internet,’’ which were unfamiliar just 20 years ago are now common. Students in elementary school regularly ‘‘surf ’’ the Internet and use computers to design their classroom projects. Many people use the Internet to look for information and to commu- nicate with others. This is all made possible by the availability of different software, also known as computer programs. Without software, a computer is useless. Software is devel- oped by using programming languages. The programming language C++ is especially well suited for developing software to accomplish specific tasks. Our main objective is to help you learn how to write programs in the C++ programming language. Before you begin programming, it is useful to understand some of the basic terminology and different components of a computer. We begin with an overview of the history of computers.

A Brief Overview of the History of Computers The first device known to carry out calculations was the abacus. The abacus was invented in Asia but was used in ancient Babylon, China, and throughout Europe until the late middle ages. The abacus uses a system of sliding beads in a rack for addition and subtraction. In 1642, the French philosopher and mathematician Blaise Pascal invented the calculating device called the Pascaline. It had eight movable dials on wheels and could calculate sums up to eight figures long. Both the abacus and Pascaline could perform only addition and subtrac- tion operations. Later in the 17th century, Gottfried von Leibniz invented a device that was able to add, subtract, multiply, and divide. In 1819, Joseph Jacquard, a French weaver, discovered that the weaving instructions for his looms could be stored on cards with holes punched in them. While the cards moved through the loom in sequence, needles passed through the holes and picked up threads of the correct color and texture. A weaver could rearrange the cards and change the pattern being woven. In essence, the cards programmed a loom to produce patterns in cloth. The weaving industry may seem to have little in common with the computer industry. However, the idea of storing information by punching holes on a card proved to be of great importance in the later development of computers.

In the early and mid-1800s, Charles Babbage, an English mathematician and physical scientist, designed two calculating machines—the difference engine and the analytical engine. The difference engine could perform complex operations such as squaring numbers automatically. Babbage built a prototype of the difference engine, but the actual device was never produced. The analytical engine’s design included input device, data storage, a control unit that allowed processing instructions in any sequence, and output devices. However, the designs remained in blueprint stage. Most of Babbage’s work is known through the writings of his colleague Ada Augusta, Countess of Lovelace. Augusta is considered the first computer programmer.

At the end of the 19th century, U.S. Census officials needed help in accurately tabulating the census data. Herman Hollerith invented a calculating machine that ran on electricity and used punched cards to store data. Hollerith’s machine was immensely successful. Hollerith founded the Tabulating Machine Company, which later became the computer and technology corporation known as IBM.

2 | Chapter 1: An Overview of Computers and Programming Languages

1 The first computer-like machine was the Mark I. It was built, in 1944, jointly by IBM and Harvard University under the leadership of Howard Aiken. Punched cards were used to feed data into the machine. The Mark I was 52 feet long, weighed 50 tons, and had 750,000 parts. In 1946, the ENIAC (Electronic Numerical Integrator and Calculator) was built at the University of Pennsylvania. It contained 18,000 vacuum tubes and weighed some 30 tons.

The computers that we know today use the design rules given by John von Neumann in the late 1940s. His design included components such as an arithmetic logic unit, a control unit, memory, and input/output devices. These components are described in the next section. Von Neumann’s computer design makes it possible to store the programming instructions and the data in the same memory space. In 1951, the UNIVAC (Universal Automatic Computer) was built and sold to the U.S. Census Bureau.

In 1956, the invention of transistors resulted in smaller, faster, more reliable, and more energy-efficient computers. This era also saw the emergence of the software development industry, with the introduction of FORTRAN and COBOL, two early programming languages. In the next major technological advancement, transistors were replaced by tiny integrated circuits, or ‘‘chips.’’ Chips are smaller and cheaper than transistors and can contain thousands of circuits on a single chip. They give computers tremendous processing speed.

In 1970, the microprocessor, an entire CPU on a single chip, was invented. In 1977, Stephen Wozniak and Steven Jobs designed and built the first Apple computer in their garage. In 1981, IBM introduced its personal computer (PC). In the 1980s, clones of the IBM PC made the personal computer even more affordable. By the mid-1990s, people from many walks of life were able to afford them. Computers continue to become faster and less expensive as technology advances.

Modern-day computers are powerful, reliable, and easy to use. They can accept spoken-word instructions and imitate human reasoning through artificial intelligence. Expert systems assist doctors in making diagnoses. Mobile computing applications are growing significantly. Using handheld devices, delivery drivers can access global positioning satellites (GPS) to verify customer locations for pickups and deliveries. Cell phones permit you to check your e-mail, make airline reservations, see how stocks are performing, and access your bank accounts.

Although there are several categories of computers, such as mainframe, midsize, and micro, all computers share some basic elements, described in the next section.

Elements of a Computer System A computer is an electronic device capable of performing commands. The basic commands that a computer performs are input (get data), output (display result), storage, and perfor- mance of arithmetic and logical operations.

In today’s market, personal computers are sold with descriptions such as a Pentium 4 Processor 2.80 GHz, 1 GB RAM, 250 GB HD, VX750 19" Silver Flat CRT Color Monitor, preloaded with software such as an operating system, games, encyclopedias, and application software such as word processors or money management programs. These descriptions represent two categories: hardware and software. Items such as ‘‘Pentium 4

Elements of a Computer System | 3