computer programming

profiled7dcq9
cpp_5th_edi.pdf

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.

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 [email protected]

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

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 …