C++ Programming: From Problem Analysis to Program Design, Eighth Edition
By D.S. Malik
Table of contents:
Preface xxxi ii
1. AN OVERVIEW Of COMPUTERS
AND PROGRAMMING LANGUAGES 1
Introduction 2
A Brief Overview of the History of Computers 2
Elements of a Computer System 4
Hardware 4
Central Processing Unit and Main Memory 4
Input/Output Devices 5
Software 5
The Language of a Computer 6
The Evolution of Programming Languages 7
Processing a c++ Program 9
Programming with the Problem
Analysis-Coding-Execution Cycle 11
Programming Methodologies 20
Structured Programming 20
Object-Oriented Programming 20
ANSI/ISO Standard C++ 22
Quick Review 22
Exercises 24
2. BASIC ELEMENTS OF C11 27
A Quick Look at a C11 Program 28
The Basics of a C11 Program 33
Comments 34
Special Symbols 35
Reserved Words (Keywords) 35
Identifiers 36
Whitespaces 37
Data Types 37
Simple Data Types 38
Floating-Point Data Types 40
Data Types, Variables, and Assignment
Statements 42
Arithmetic Operators, Operator Precedence, and Expressions 43
Order of Precedence 45
Expressions 47
Mixed Expressions 48
Type Conversion (Casting) 50
string Type 53
Variables, Assignment Statements,
and Input Statements 54
Allocating Memory with Constants and Variables 54
Putting Data into Variables 57
Assignment Statement 57
Saving and Using the Value of an Expression 60
Declaring and Initializing Variables 61
Input (Read) Statement 62
Variable Initialization 65
Increment and Decrement Operators 69
Output 71
Preprocessor Directives 78
namespace and Using cin and cout in a Program 79
Using the string Data Type in a Program 80
Creating a C11 Program 80
Debugging: Understanding and Fixing
Syntax Errors 84
Program Style and Form 87
Syntax 87
Use of Blanks 88
Use of Semicolons, Brackets, and Commas 88
Semantics 88
Naming Identifiers 89
Prompt Lines 89
Documentation 90
Form and Style 90
More on Assignment Statements 92
Programming Example: Convert Length 94
Programming Example: Make Change 98
Quick Review 102
Exercises 104
Programming Exercises 114
3. INPUT/OUTPUT 123
I/O Streams and Standard I/O Devices 124
cin and the Extraction Operator >> 125
Using Predefined Functions in a Program 130
cin and the get Function 133
cin and the ignore Function 134
The putback and peek Functions 136
The Dot Notation between I/O Stream Variables
and I/O Functions: A Precaution 139
Input Failure 139
The clear Function 142
Output and Formatting Output 143
setprecision Manipulator 144
fixed Manipulator 145
showpoint Manipulator 146
C1114 Digit Separator 149
setw 150
Additional Output Formatting Tools 152
setfill Manipulator 152
left and right Manipulators 154
Input/Output and the string Type 156
Debugging: Understanding Logic Errors
and Debugging with cout Statements 157
File Input/Output 160
Programming Example: Movie Tickets
Sale and Donation to Charity 164
Programming Example: Student Grade 170
Quick Review 173
Exercises 175
Programming Exercises 181
- CONTROL STRUCTURES I (SELECTION) 187
Control Structures 188
SELECTION: if AND if . . . else 189
Relational Operators and Simple Data Types 189
Comparing Characters 190
One-Way Selection 191
Two-Way Selection 194
int Data Type and Logical (Boolean) Expressions 198
bool Data Type and Logical (Boolean) Expressions 198
Logical (Boolean) Operators and Logical Expressions 199
Order of Precedence 201
Relational Operators and the string Type 205
Compound (Block of) Statements 207
Multiple Selections: Nested if 207
Comparing if . . . else Statements with a Series of if Statements 210
Short-Circuit Evaluation 211
Comparing Floating-Point Numbers for Equality: A Precaution 212
Associativity of Relational Operators: A Precaution 213
Avoiding Bugs by Avoiding Partially Understood
Concepts and Techniques 215
Input Failure and the if Statement 218
Confusion between the Equality Operator (==)
and the Assignment Operator (=) 221
Conditional Operator (?:) 223
Program Style and Form (Revisited): Indentation 224
Using Pseudocode to Develop, Test, and Debug a Program 224
switch Structures 227
Avoiding Bugs by Avoiding Partially Understood
Concepts and Techniques (Revisited) 234
Terminating a Program with the assert Function 236
Programming Example: Cable Company Billing 238
Quick Review 244
Exercises 245
Programming Exercises 257
- CONTROL STRUCTURES II (REPETITION) 265
Why Is Repetition Needed? 266
while Looping (Repetition) Structure 269
Designing while Loops 273
Case 1: Counter-Controlled while Loops 274
Case 2: Sentinel-Controlled while Loops 277
Case 3: Flag-Controlled while Loops 283
Case 4: EOF-Controlled while Loops 286
eof Function 287
More on Expressions in while Statements 292
Programming Example: Fibonacci Number 293
for Looping (Repetition) Structure 297
Programming Example: Classifying Numbers 305
- . .while Looping (Repetition) Structure 309
Divisibility Test by 3 and 9 311
Choosing the Right Looping Structure 313
break and continue Statements 313
Nested Control Structures 315
Avoiding Bugs by Avoiding Patches 321
Debugging Loops 324
Quick Review 324
Exercises 326
Programming Exercises 340
- USER-DEFINED FUNCTIONS 347
Predefined Functions 348
User-Defined Functions 352
Value-Returning Functions 353
Syntax: Value-Returning Function 355
Syntax: Formal Parameter List 355
Function Call 355
Syntax: Actual Parameter List 356
return Statement 356
Syntax: return Statement 356
Function Prototype 360
Syntax: Function Prototype 361
Value-Returning Functions: Some Peculiarities 362
More Examples of Value-Returning Functions 364
Flow of Compilation and Execution 375
Programming Example: Largest Number 376
Void Functions 378
Value Parameters 384
Reference Variables as Parameters 386
Calculate Grade 387
Value and Reference Parameters and Memory Allocation 390
Reference Parameters and Value-Returning Functions 399
Scope of an Identifier 399
Global Variables, Named Constants,
and Side Effects 403
Static and Automatic Variables 411
Debugging: Using Drivers and Stubs 413
Function Overloading: An Introduction 415
Functions with Default Parameters 417
Programming Example: Classify Numbers 420
Programming Example: Data Comparison 425
Quick Review 435
Exercises 438
Programming Exercises 453
- USER-DEFINED SIMPLE DATA TYPES, NAMESPACES, AND THE STRING TYPE 467
Enumeration Type 468
Declaring Variables 470
Assignment 470
Operations on Enumeration Types 471
Relational Operators 471
Input /Output of Enumeration Types 472
Functions and Enumeration Types 475
Declaring Variables When Defining the Enumeration Type 476
Anonymous Data Types 477
typedef Statement 477
Programming Example: The Game of Rock, Paper, and Scissors 478
Namespaces 487
string Type 492
Additional string Operations 496
Programming Example: Pig Latin Strings 505
Quick Review 510
Exercises 512
Programming Exercises 517
- ARRAYS AND STRINGS 521
Arrays 523
Accessing Array Components 525
Processing One-Dimensional Arrays 527
Array Index Out of Bounds 531
Array Initialization during Declaration 532
Partial Initialization of Arrays during Declaration 532
Some Restrictions on Array Processing 533
Arrays as Parameters to Functions 534
Constant Arrays as Formal Parameters 535
Base Address of an Array and Array in Computer Memory 537
Functions Cannot Return a Value of the Type Array 540
Integral Data Type and Array Indices 543
Other Ways to Declare Arrays 544
Searching an Array for a Specific Item 544
Sorting 547
Auto Declaration and Range-Based For Loops 551
C-Strings (Character Arrays) 552
String Comparison 555
Reading and Writing Strings 556
String Input 556
String Output 558
Specifying Input/Output Files at Execution Time 559
string Type and Input/Output Files 559
Parallel Arrays 560
Two- and Multidimensional Arrays 561
Accessing Array Components 563
Two-Dimensional Array Initialization during Declaration 564
Two-Dimensional Arrays and Enumeration Types 564
Initialization 567
Print 568
Input 568
Sum by Row 568
Sum by Column 568
Largest Element in Each Row and Each Column 569
Passing Two-Dimensional Arrays as Parameters to Functions 570
Arrays of Strings 573
Arrays of Strings and the string Type 573
Arrays of Strings and C-Strings (Character Arrays) 573
Another Way to Declare a Two-Dimensional Array 574
Multidimensional Arrays 575
Programming Example: Code Detection 577
Programming Example: Text Processing 583
Quick Review 590
Exercises 592
Programming Exercises 604
- RECORDS (STRUCTS) 611
Records (structs) 612
Accessing struct Members 614
Assignment 617
Comparison (Relational Operators) 618
Input/Output 618
struct Variables and Functions 619
Arrays versus structs 620
Arrays in structs 620
structs in Arrays 623
structs within a struct 624
Programming Example: Sales Data Analysis 628
Quick Review 642
Exercises 643
Programming Exercises 648
- CLASSES AND DATA ABSTRACTION 651
Classes 652
Unified Modeling Language Class Diagrams 656
Variable (Object) Declaration 656
Accessing Class Members 657
Built-in Operations on Classes 659
Assignment Operator and Classes 659
Class Scope 660
Functions and Classes 660
Reference Parameters and Class Objects (Variables) 660
Implementation of Member Functions 661
Accessor and Mutator Functions 666
Order of public and private Members of a Class 670
Constructors 671
Invoking a Constructor 673
Invoking the Default Constructor 673
Invoking a Constructor with Parameters 674
Constructors and Default Parameters 677
Classes and Constructors: A Precaution 677
In-Class Initialization of Data Members and the Default Constructor 678
Arrays of Class Objects (Variables) and Constructors 679
Destructors 681
Data Abstraction, Classes, and Abstract Data Types 682
A struct versus a class 684
Information Hiding 685
Executable Code 689
More Examples of Classes 691
Inline Functions 700
Static Members of a Class 701
Programming Example: Juice Machine 707
Quick Review 722
Exercises 724
Programming Exercises 736
- INHERITANCE AND COMPOSITION 743
Inheritance 744
Redefining (Overriding) Member Functions of the Base Class 747
Constructors of Derived and Base Classes 754
Destructors in a Derived Class 763
Multiple Inclusions of a Header File 764
C11 Stream Classes 768
Protected Members of a Class 769
Inheritance as public, protected, or private 769
(Accessing protected Members in the Derived Class) 770
Composition (Aggregation) 773
Object-Oriented Design (OOD) and
Object-Oriented Programming (OOP) 778
Identifying Classes, Objects, and Operations 780
Programming Example: Grade Report 781
Quick Review 802
Exercises 802
Programming Exercises 811
- POINTERS, CLASSES, VIRTUAL FUNCTIONS, AND ABSTRACT CLASSES 817
Pointer Data Type and Pointer Variables 818
Declaring Pointer Variables 818
Address of Operator (&) 820
Dereferencing Operator (*) 821
Classes, Structs, and Pointer Variables 826
Initializing Pointer Variables 829
Initializing Pointer Variables Using nullptr 829
Dynamic Variables 830
Operator new 830
Operator delete 831
Operations on Pointer Variables 835
Dynamic Arrays 837
Arrays and Range-Based for Loops (Revisited) 840
Functions and Pointers 841
Pointers and Function Return Values 842
Dynamic Two-Dimensional Arrays 842
Shallow versus Deep Copy and Pointers 845
Classes and Pointers: Some Peculiarities 847
Destructor 848
Assignment Operator 849
Copy Constructor 851
Inheritance, Pointers, and Virtual Functions 858
Classes and Virtual Destructors 865
Abstract Classes and Pure Virtual Functions 866
Address of Operator and Classes 874
Quick Review 876
Exercises 879
Programming Exercises 890
- OVERLOADING AND TEMPLATES 893
Why Operator Overloading Is Needed 894
Operator Overloading 895
Syntax for Operator Functions 896
Overloading an Operator: Some Restrictions 896
Pointer this 899
Friend Functions of Classes 904
Operator Functions as Member Functions
and Nonmember Functions 907
Overloading Binary Operators 910
Overloading the Stream Insertion (<<) and Extraction (>>) Operators 916
Overloading the Assignment Operator (=) 921
Overloading Unary Operators 929
Operator Overloading: Member versus Nonmember 935
Classes and Pointer Member Variables (Revisited) 936
Operator Overloading: One Final Word 936
Programming Example: clockType 936
Programming Example: Complex Numbers 945
Overloading the Array Index (Subscript) Operator ([]) 950
Programming Example: newString 952
Function Overloading 959
Templates 959
Function Templates 959
Class Templates 961
C1111 Random Number Generator 969
Quick Review 971
Exercises 973
Programming Exercises 981
- EXCEPTION HANDLING 991
Handling Exceptions within a Program 992
C11 Mechanisms of Exception Handling 996
try/catch Block 996
Using C11 Exception Classes 1003
Creating Your Own Exception Classes 1007
Rethrowing and Throwing an Exception 1016
Exception-Handling Techniques 1020
Terminate the Program 1020
Fix the Error and Continue 1020
Log the Error and Continue 1021
Stack Unwinding 1022
Quick Review 1025
Exercises 1027
Programming Exercises 1033
- RECURSION 1035
Recursive Definitions 1036
Direct and Indirect Recursion 1038
Infinite Recursion 1038
Problem Solving Using Recursion 1039
Tower of Hanoi: Analysis 1049
Recursion or Iteration? 1049
Programming Example: Converting a Number from
Binary to Decimal 1051
Programming Example: Converting a Number from Decimal to Binary 1055
Quick Review 1058
Exercises 1059
Programming Exercises 1064
- SEARCHING, SORTING,
AND THE VECTOR TYPE 1069
List Processing 1070
Searching 1070
Bubble Sort 1071
Insertion Sort 1075
Binary Search 1079
Performance of Binary Search 1082
vector Type (class) 1083
Vectors and Range-Based for Loops 1088
Initializing vector Objects during Declaration 1090
Programming Example: Election Results 1091
Quick Review 1105
Exercises 1106
Programming Exercises 1111
- LINKED LISTS 1115
Linked Lists 1116
Linked Lists: Some Properties 1117
Deletion 1123
Building a Linked List 1124
Linked List as an ADT 1129
Structure of Linked List Nodes 1130
Member Variables of the class linkedListType 1130
Linked List Iterators 1131
Print the List 1137
Length of a List 1138
Retrieve the Data of the First Node 1138
Retrieve the Data of the Last Node 1138
Begin and End 1138
Copy the List 1139
Destructor 1140
Copy Constructor 1140
Overloading the Assignment Operator 1141
Unordered Linked Lists 1141
Search the List 1142
Insert the First Node 1143
Insert the Last Node 1144
Header File of the Unordered Linked List 1149
Ordered Linked Lists 1150
Search the List 1151
Insert a Node 1152
Insert First and Insert Last 1156
Delete a Node 1157
Header File of the Ordered Linked List 1158
Print a Linked List in Reverse Order
(Recursion Revisited) 1161
print List Reverse 1163
Doubly Linked Lists 1164
Default Constructor 1167
is EmptyList 1167
Destroy the List 1167
Initialize the List 1168
Length of the List 1168
Print the List 1168
Reverse Print the List 1168
Search the List 1169
First and Last Elements 1169
Circular Linked Lists 1175
Programming Example: DVD Store 1176
Quick Review 1196
Exercises 1196
Programming Exercises 1203
- STACKS AND QUEUES 1209
Stacks 1210
Stack Operations 1212
Implementation of Stacks as Arrays 1214
Initialize Stack 1217
Empty Stack 1218
Full Stack 1218
Push 1218
Return the Top Element 1220
Pop 1220
Copy Stack 1222
Constructor and Destructor 1222
Copy Constructor 1223
Overloading the Assignment Operator (=) 1223
Stack Header File 1224
Programming Example: Highest GPA 1228
Linked Implementation of Stacks 1232
Default Constructor 1235
Empty Stack and Full Stack 1235
Initialize Stack 1236
Push 1236
Return the Top Element 1238
Pop 1238
Copy Stack 1240
Constructors and Destructors 1241
Overloading the Assignment Operator (=) 1241
Stack as Derived from the class unordered LinkedList 1244
Application of Stacks: Postfix Expressions Calculator 1245
Main Algorithm 1248
Function evaluateExpression 1248
Function evaluateOpr 1250
Function discardExp 1252
Function printResult 1252
Removing Recursion: Nonrecursive Algorithm
to Print a Linked List Backward 1255
Queues 1259
Queue Operations 1260
Implementation of Queues as Arrays 1262
Linked Implementation of Queues 1271
Queue Derived from the class unorderedLinkedListType 1276
Application of Queues: Simulation 1277
Designing a Queuing System 1278
Customer 1279
Server 1282
Server List 1285
Waiting Customers Queue 1289
Main Program 1291
Quick Review 1295
Exercises 1296
Programming Exercises 1305
APPENDIX A: RESERVED WORDS 1309
APPENDIX B: OPERATOR PRECEDENCE 1311
APPENDIX C: CHARACTER SETS 1313
ASCII (American Standard Code for Information Interchange) 1313
EBCDIC (Extended Binary Coded Decimal Interchange Code) 1314
APPENDIX D: OPERATOR OVERLOADING 1317
APPENDIX E: ADDITIONAL C11 TOPICS ONLINE
Binary (Base 2) Representation of a Nonnegative Integer E-1
Converting a Base 10 Number to a Binary Number (Base 2) E-1
Converting a Binary Number (Base 2) to Base 10 E-3
Converting a Binary Number (Base 2) to Octal (Base 8)
and Hexadecimal (Base 16) E-4
More on File Input/Output E-6
Binary Files E-6
Random File Access E-12
Naming Conventions of Header Files in
ANSI/ISO Standard C11 and Standard C11 E-20
APPENDIX F: HEADER FILES 1319
Header File cassert (assert.h) 1319
Header File cctype (ctype.h) 1320
Header File cfloat (float.h) 1321
Header File climits (limits.h) 1322
Header File cmath (math.h) 1324
Header File cstddef (stddef.h) 1325
Header File cstring (string.h) 1325
HEADER FILE string 1326
APPENDIX G: MEMORY SIZE ON A SYSTEM 1329
APPENDIX H: STANDARD TEMPLATE LIBRARY (STL) 1331
Components of the STL 1331
Container Types 1332
Sequence Containers 1332
Sequence Container: Vectors 1332
Member Functions Common to All Containers 1340
Member Functions Common to Sequence Containers 1342
copy Algorithm 1342
Sequence Container: deque 1346
Sequence Container: list 1349
Iterators 1354
IOStream Iterators 1354
Container Adapters 1355
Algorithms 1358
STL Algorithm Classification 1358
STL Algorithms 1360
Functions fill and fill_n 1361
Functions find and find_if 1362
Functions remove and replace 1363
Functions search, sort, and binary_search 1365
APPENDIX I: ANSWERS TO ODD-NUMBERED EXERCISES 1369
Chapter 1 1369
Chapter 2 1372
Chapter 3 1376
Chapter 4 1377
Chapter 5 1380
Chapter 6 1382
Chapter 7 1385
Chapter 8 1387
Chapter 9 1389
Chapter 10 1391
Chapter 11 1395
Chapter 12 1398
Chapter 13 1400
Chapter 14 1402
Chapter 15 1405
Chapter 16 1406
Chapter 17 1407
Chapter 18 1409
INDEX 1413