C++ PROGRAMMING:
FROM PROBLEM ANALYSIS TO PROGRAM DESIGN
FOURTH EDITION
D.S. MALIK
Australia  Brazil  Japan  Korea  Mexico  Singapore  Spain  United Kingdom  United States
C++ Programming: From Problem Analysis
to Program Design, Fourth Edition
by D.S. Malik
Senior Product Manager: Alyssa Pratt
Acquisitions Editor: Amy Jollymore
Content Product Manager: Jill Braiewa
Marketing Manager: Bryant Chrzan
Editorial Assistant: Patrick Frank
Print Buyer: Julio Esperas
Cover Designer: Lisa Kuhn, Curio Press, LLC
Compositor: Integra
Art Director: Marissa Falco
Validation: Green Pen Quality Assurance
Proofreader: Green Pen Quality Assurance
Indexer: Liz Cunningham
Printed in Canada
123456714131211100908
ª 2009 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.

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 offic e at:
international.cengage.com/region
Cengage Learning products are represented in Canada
by Nelson Education, Ltd.
For your lifelong learning solutions, visit
course.cengage.com
Visit our corporate website at cengage.com
TO
My Daughter
Shelly Malik

PREFACE xxvii
1. An Overview of Computers and Programming Languages 1
2. Basic Elements of C++ 29
3. Input/Output 115
4. Control Structures I (Selection) 167
5. Control Structures II (Repetition) 231
6. User-Defined Functions I 307
7. User-Defined Functions II 345
8. User-Defined Simple Data Types, Namespaces,
and the
string
Type 415
9. Arrays and Strings 469
10. Applications of Arrays (Searching and Sorting)
and the

A Brief Overview of the History of Computers 2
Elements of a Computer System 3
Hardware 4
Central Processing Unit 4
Main Memory 5
Secondary Storage 6
Input /Output Devices 6
Software 6
The Language of a Computer 6
The Evolution of Programming Languages 8
AC++Program 10
Processing a C++ Program 12
Programming with the Problem
Analysis–Coding–Execution Cycle 14
Programming Methodologies 22
Structured Programming 22
Object-Oriented Programming 22
ANSI/ISO Standard C++ 24
Quick Review 24
Exercises 26
1
TABLE OF CONTENTS
BASIC ELEMENTS OF C++ 29
The Basics of a C++ Program 30
Comments 32
Special Symbols 32
Reserved Words (Keywords) 33
Identifiers 33
Whitespaces 34
Data Types 34

Program Style and Form 83
Syntax 83
2
Use of Blanks 84
viii | C++ Programming: From Problem Analysis to Program Design, Fourth Edition
Use of Semicolons, Brackets, and Commas 84
Semantics 84
Naming Identifiers 84
Prompt Lines 85
Documentation 86
Form and Style 86
More on Assignment Statements 88
Programming Example: Convert Length 99
Programming Example: Make Change 93
Quick Review 97
Exercises 99
Programming Exercises 107
INPUT/OUTPUT 115
I/O Streams and Standard I/O Devices 116
cin
and the Extraction Operator
>>
117
Using Predefined Functions in a Program 123
cin
and the
get
Function 125
cin
and the

Input/Output and the
string
Type 145
Table of Contents | ix
File Input/Output 146
Programming Example: Movie Ticket Sale and
Donation to Charity 150
Programming Example: Student Grade 155
Quick Review 158
Exercises 160
Programming Exercises 163
CONTROL STRUCTURES I (SELECTION) 167
Control Structures 168
Relational Operators 169
Relational Operators and Simple Data Types 171
Comparing Floating-point Numbers for equality 171
Comparing Characters 172
Relational Operators and the
string
Type 173
Logical (Boolean) Operators and Logical Expressions 175
Order of Precedence 177
Short-Circuit Evaluation 181
int Data Type and Logical (Boolean) Expressions 182
bool Data Type and Logical (Boolean) Expressions 183
Selection: if and if else 184
One-Way Selection 185
Two-Way Selection 187
Compound (Block of) Statements 191
Multiple Selections: Nested if 192

Programming Example: Checking
Account Balance 250
Programming Example: Fibonacci Number 259
for Looping (Repetition) Structure 264
Programming Example: Classifying Numbers 270
do while Looping (Repetition) Structure 274
Choosing the Right Looping Structure 278
break and continue Statements 278
Nested Control Structures 281
Quick Review 288
Exercises 290
Programming Exercises 300
5
Table of Contents | xi
USER-DEFINED FUNCTIONS I 307
Predefined Functions 308
User-Defined Functions 311
Value-Returning Functions 312
Syntax: Value-Returning Functions 314
Syntax: Formal Parameter List 314
Function Call 314
Syntax: Actual Parameter List 314
return Statement 315
Syntax: return Statement 315
Function Prototype 318
Syntax: Function Prototype 319
Flow of Execution 325
Programming Example: Largest Number 326
Programming Example: Cable Company 327
Quick Review 333

Input /Output of Enumeration Types 420
Functions and Enumeration Types 422
Declaring Variables When Defining the Enumeration Type 424
Anonymous Data Types 424
typedef
Statement 425
Programming Example: The Game of Rock, Paper,
and Scissors 426
Namespaces 437
string
Type 442
Additional
string
Operations 446
length
Function 446
size
Function 448
find
Function 449
substr
Function 452
swap
Function 454
Programming Example: Pig Latin Strings 454
8
Quick Review 460
Table of Contents | xiii
Exercises 463
Programming Exercises 466

Input 507
Sum by Row 508
Sum by Column 508
9
xiv | C++ Programming: From Problem Analysis to Program Design, Fourth Edition
Largest Element in Each Row and Each Column 508
Reversing Diagonal 509
Passing Two-Dimensional Arrays as Parameters to Functions 511
Arrays of Strings 514
Arrays of Strings and the
string
Type 514
Arrays of Strings and
C
-Strings (Character Arrays) 515
Another Way to Declare a Two-Dimensional Array 516
Multidimensional Arrays 517
Programming Example: Code Detection 518
Programming Example: Text Processing 525
Quick Review 532
Exercises 534
Programming Exercises 539
APPLICATIONS OF ARRAYS (SEARCHING
AND SORTING) AND THE
vector
TYPE 545
List Processing 546
Searching 546
Bubble Sort 551
Selection Sort 555

Variable (Object) Declaration 646
Accessing Class Members 647
Built-in Operations on Classes 648
Assignment Operator and Classes 649
Class Scope 650
Functions and Classes 650
Reference Parameters and Class Objects (Variables) 650
Implementation of Member Functions 651
Accessor and Mutator Functions 656
Order of public and private Members of a Class 661
Constructors 662
Invoking a Constructor 664
Invoking the Default Constructor 664
Invoking a Constructor with Parameters 665
Constructors and Default Parameters 668
11
12
xvi | C++ Programming: From Problem Analysis to Program Design, Fourth Edition
Classes and Constructors: A Precaution 670
Arrays of Class Objects (Variables) and Constructors 671
Destructors 673
Data Abstraction, Classes, and Abstract Data Types 674
A struct versus a class 676
Information Hiding 677
Executable Code 681
Static Members of a Class 685
Programming Example: Candy Machine 691
Quick Review 706
Exercises 708
Programming Exercises 713

Operations on Pointer Variables 801
Dynamic Arrays 803
Functions and Pointers 806
Pointers and Function Return Values 806
Dynamic Two-Dimensional Arrays 807
Shallow versus Deep Copy and Pointers 810
Classes and Pointers: Some Peculiarities 812
Destructor 813
Assignment Operator 814
Copy Constructor 816
Inheritance, Pointers, and Virtual Functions 823
Classes and Virtual Destructors 830
Abstract Classes and Pure Virtual Functions 830
Address of Operator and Classes 838
Quick Review 841
Exercises 844
Programming Exercises 851
14
xviii | C++ Programming: From Problem Analysis to Program Design, Fourth Edition
OVERLOADING AND TEMPLATES 853
Why Operator Overloading Is Needed 854
Operator Overloading 855
Syntax for Operator Functions 856
Overloading an Operator: Some Restrictions 856
Pointer this 857
Friend Functions of Classes 862
Operator Functions as Member Functions
and Nonmember Functions 865
Overloading Binary Operators 868
Overloading the Stream Insertion (

15
16
Table of Contents | xix
try
/
catch
Block 948
Using C++ Exception Classes 955
Creating Your Own Exception Classes 959
Rethrowing and Throwing an Exception 965
Exception Handling Techniques 970
Terminate the Program 970
Fix the Error and Continue 970
Log the Error and Continue 972
Stack Unwinding 972
Quick Review 976
Exercises 978
Programming Exercises 980
RECURSION 981
Recursive Definitions 982
Direct and Indirect Recursion 985
Infinite Recursion 985
Problem Solving Using Recursion 986
Tower of Hanoi: Analysis 997
Recursion or Iteration? 998
Programming Example: Converting a Number from
Binary to Decimal 999
Programming Example: Converting a Number from
Decimal to Binary 1004
Quick Review 1008

Search the List 1056
Insert a Node 1056
Insert First and Insert Last 1061
Delete a Node 1062
Header File of the Ordered Linked List 1063
Print a Linked List in Reverse Order
(Recursion Revisited) 1066
Doubly Linked Lists 1069
Default Constructor 1072
isEmptyList
1072
Destroy the List 1072
Initialize the List 1073
Length of the List 1073
Print the List 1073
Reverse Print the List 1073
Search the List 1074
First and Last Elements 1074
Table of Contents | xxi
Circular Linked Lists 1080
Programming Example: Video Store 1081
Quick Review 1101
Exercises 1101
Programming Exercises 1105
STACKS AND QUEUES 1111
Stacks 1112
Stack Operations 1114
Implementation of Stacks as Arrays 1116
Initialize Stack 1119
Empty Stack 1120

Application of Stacks: Postfix Expressions Calculator 1148
Main Algorithm 1153
Function
evaluateExpression
1153
Function
evaluateOpr
1155
Function
discardExp
1157
Function
printResult
1157
Removing Recursion: Nonrecursive Algorithm to Print a
Linked List Backward 1160
Queues 1167
Queue Operations 1167
Implementation of Queues as Arrays 1169
Linked Implementation of Queues 1180
Queue Derived from the class
unorderedLinkedListType
1185
Application of Queues: Simulation 1186
Designing a Queuing System 1187
Customer 1188
Server 1191
Server List 1194
Waiting Customers Queue 1199
Main Program 1201

) 1251
Header File
cctype
(
ctype.h
) 1252
Header File
cfloat
(
float.h
) 1253
Header File
climits
(
limits.h
) 1254
Header File
cmath
(
math.h
) 1256
Header File
cstddef
(
stddef.h
) 1257
Header File
cstring
(
string.h

fill_n
1295
Functions
find
and
find_if
1298
Functions
remove
and
replace
1299
Functions
search
,
sort
, and
binary_search
1301
APPENDIX I: ANSWERS TO ODD-NUMBERED
EXERCISES 1305
Chapter 1 1305
Chapter 2 1308
Chapter 3 1310
Chapter 4 1310
Table of Contents | xxv