C++ Programming

Cover......Page 1
Brief Contents......Page 7
Table of Contents......Page 9
Preface......Page 35
Features of the Book......Page 42
Supplemental Resources......Page 49
Acknowledgments......Page 50
Chapter 1: AN OVERVIEW OF COMPUTERS AND PROGRAMMING LANGUAGES......Page 51
A Brief Overview of the History of Computers......Page 52
Central Processing Unit and Main Memory......Page 54
Software......Page 55
The Language of a Computer......Page 56
The Evolution of Programming Languages......Page 57
Processing a C11 Program......Page 59
Programming with the Problem Analysis–Coding–Execution Cycle......Page 61
Object-Oriented Programming......Page 70
Quick Review......Page 72
Exercises......Page 74
Chapter 2: BASIC ELEMENTS OF C++......Page 77
A Quick Look at a C11 Program......Page 78
The Basics of a C11 Program......Page 83
Comments......Page 84
Reserved Words (Keywords)......Page 85
Identifiers......Page 86
Data Types......Page 87
Simple Data Types......Page 88
Floating-Point Data Types......Page 90
Data Types, Variables, and Assignment Statements......Page 92
Arithmetic Operators, Operator Precedence, and Expressions......Page 93
Order of Precedence......Page 95
Expressions......Page 97
Mixed Expressions......Page 98
Type Conversion (Casting)......Page 100
string Type......Page 103
Allocating Memory with Constants and Variables......Page 104
Assignment Statement......Page 107
Saving and Using the Value of an Expression......Page 110
Declaring and Initializing Variables......Page 111
Input (Read) Statement......Page 112
Variable Initialization......Page 115
Increment and Decrement Operators......Page 119
Output......Page 121
Preprocessor Directives......Page 128
namespace and Using cin and cout in a Program......Page 129
Creating a C11 Program......Page 130
Debugging: Understanding and Fixing Syntax Errors......Page 134
Syntax......Page 137
Semantics......Page 138
Prompt Lines......Page 139
Form and Style......Page 140
More on Assignment Statements......Page 142
Programming Example: Convert Length......Page 144
Programming Example: Make Change......Page 148
Quick Review......Page 152
Exercises......Page 154
Programming Exercises......Page 164
Chapter 3: INPUT/OUTPUT......Page 173
I/O Streams and Standard I/O Devices......Page 174
cin and the Extraction Operator >>......Page 175
Using Predefined Functions in a Program......Page 180
cin and the get Function......Page 183
cin and the ignore Function......Page 184
The putback and peek Functions......Page 186
Input Failure......Page 189
The clear Function......Page 192
Output and Formatting Output......Page 193
setprecision Manipulator......Page 194
fixed Manipulator......Page 195
showpoint Manipulator......Page 196
C++14 Digit Separator......Page 199
setw......Page 200
setfill Manipulator......Page 202
left and right Manipulators......Page 204
Input/Output and the string Type......Page 206
Debugging: Understanding Logic Errors and Debugging with cout Statements......Page 207
File Input/Output......Page 210
Programming Example: Movie TicketsSale and Donation to Charity......Page 214
Programming Example: Student Grade......Page 220
Quick Review......Page 223
Exercises......Page 225
Programming Exercises......Page 231
Chapter 4: CONTROL STRUCTURES I (SELECTION)......Page 237
Control Structures......Page 238
Relational Operators and Simple Data Types......Page 239
Comparing Characters......Page 240
One-Way Selection......Page 241
Two-Way Selection......Page 244
bool Data Type and Logical (Boolean) Expressions......Page 248
Logical (Boolean) Operators and Logical Expressions......Page 249
Order of Precedence......Page 251
Relational Operators and the string Type......Page 255
Multiple Selections: Nested if......Page 257
Comparing if...else Statements with a Series of if Statements......Page 260
Short-Circuit Evaluation......Page 261
Comparing Floating-Point Numbers for Equality: A Precaution......Page 262
Associativity of Relational Operators: A Precaution......Page 263
Avoiding Bugs by Avoiding Partially Understood Concepts and Techniques......Page 265
Input Failure and the if Statement......Page 268
Confusion between the Equality Operator (==) and the Assignment Oper-ator (=)......Page 271
Conditional Operator (:)......Page 273
Using Pseudocode to Develop, Test, and Debug a Program......Page 274
switch Structures......Page 277
Avoiding Bugs by Avoiding Partially Understood Concepts and Techniques (Revisited)......Page 284
Terminating a Program with the assert Function......Page 286
Programming Example: Cable Company Billing......Page 288
Quick Review......Page 294
Exercises......Page 295
Programming Exercises......Page 307
Chapter 5: CONTROL STRUCTURES II (REPETITION)......Page 315
Why Is Repetition Needed......Page 316
while Looping (Repetition) Structure......Page 319
Designing while Loops......Page 323
Case 1: Counter-Controlled while Loops......Page 324
Case 2: Sentinel-Controlled while Loops......Page 327
Case 3: Flag-Controlled while Loops......Page 333
Case 4: EOF-Controlled while Loops......Page 336
eof Function......Page 337
More on Expressions in while Statements......Page 342
Programming Example: Fibonacci Number......Page 343
for Looping (Repetition) Structure......Page 347
Programming Example: Classifying Numbers......Page 355
do...while Looping (Repetition) Structure......Page 359
Divisibility Test by 3 and 9......Page 361
break and continue Statements......Page 363
Nested Control Structures......Page 365
Avoiding Bugs by Avoiding Patches......Page 371
Quick Review......Page 374
Exercises......Page 376
Programming Exercises......Page 390
Chapter 6: USER-DEFINED FUNCTIONS......Page 397
Predefined Functions......Page 398
User-Defined Functions......Page 402
Value-Returning Functions......Page 403
Function Call......Page 405
Syntax: return Statement......Page 406
Function Prototype......Page 410
Syntax: Function Prototype......Page 411
Value-Returning Functions: Some Peculiarities......Page 412
More Examples of Value-Returning Functions......Page 414
Flow of Compilation and Execution......Page 425
Programming Example: Largest Number......Page 426
Void Functions......Page 428
Value Parameters......Page 434
Reference Variables as Parameters......Page 436
Calculate Grade......Page 437
Value and Reference Parameters and Memory Allocation......Page 440
Scope of an Identifier......Page 449
Global Variables, Named Constants, and Side Effects......Page 453
Static and Automatic Variables......Page 461
Debugging: Using Drivers and Stubs......Page 463
Function Overloading: An Introduction......Page 465
Functions with Default Parameters......Page 467
Programming Example: Classify Numbers......Page 470
Programming Example: Data Comparison......Page 475
Quick Review......Page 485
Exercises......Page 488
Programming Exercises......Page 503
Chapter 7: USER-DEFINED SIMPLE DATA TYPES, NAMESPACES, AND THE STRING TYPE......Page 517
Enumeration Type......Page 518
Assignment......Page 520
Relational Operators......Page 521
Input /Output of Enumeration Types......Page 522
Functions and Enumeration Types......Page 525
Declaring Variables When Defining the Enumeration Type......Page 526
typedef Statement......Page 527
Programming Example: The Game of Rock, Paper, and Scissors......Page 528
Namespaces......Page 537
string Type......Page 542
Additional string Operations......Page 546
Programming Example: Pig Latin Strings......Page 555
Quick Review......Page 560
Exercises......Page 562
Programming Exercises......Page 567
Chapter 8: ARRAYS AND STRINGS......Page 571
Arrays......Page 573
Accessing Array Components......Page 575
Processing One-Dimensional Arrays......Page 577
Array Index Out of Bounds......Page 581
Partial Initialization of Arrays during Declaration......Page 582
Some Restrictions on Array Processing......Page 583
Arrays as Parameters to Functions......Page 584
Constant Arrays as Formal Parameters......Page 585
Base Address of an Array and Array in Computer Memory......Page 587
Functions Cannot Return a Value of the Type Array......Page 590
Integral Data Type and Array Indices......Page 593
Searching an Array for a Specific Item......Page 594
Sorting......Page 597
Auto Declaration and Range-Based For Loops......Page 601
C-Strings (Character Arrays)......Page 602
String Comparison......Page 605
String Input......Page 606
String Output......Page 608
string Type and Input/Output Files......Page 609
Parallel Arrays......Page 610
Two- and Multidimensional Arrays......Page 611
Accessing Array Components......Page 613
Two-Dimensional Arrays and Enumeration Types......Page 614
Initialization......Page 617
Sum by Column......Page 618
Largest Element in Each Row and Each Column......Page 619
Passing Two-Dimensional Arrays as Parameters to Functions......Page 620
Arrays of Strings and C-Strings (Character Arrays)......Page 623
Another Way to Declare a Two-Dimensional Array......Page 624
Multidimensional Arrays......Page 625
Programming Example: Code Detection......Page 627
Programming Example: Text Processing......Page 633
Quick Review......Page 640
Exercises......Page 642
Programming Exercises......Page 654
Chapter 9: RECORDS (STRUCTS)......Page 661
Records (structs)......Page 662
Accessing struct Members......Page 664
Assignment......Page 667
Input/Output......Page 668
struct Variables and Functions......Page 669
Arrays in structs......Page 670
structs in Arrays......Page 673
structs within a struct......Page 674
Programming Example: Sales Data Analysis......Page 678
Quick Review......Page 692
Exercises......Page 693
Programming Exercises......Page 698
Chapter 10: CLASSES AND DATA ABSTRACTION......Page 701
Classes......Page 702
Variable (Object) Declaration......Page 706
Accessing Class Members......Page 707
Assignment Operator and Classes......Page 709
Reference Parameters and Class Objects (Variables)......Page 710
Implementation of Member Functions......Page 711
Accessor and Mutator Functions......Page 716
Order of public and private Members of a Class......Page 720
Constructors......Page 721
Invoking the Default Constructor......Page 723
Invoking a Constructor with Parameters......Page 724
Classes and Constructors: A Precaution......Page 727
In-line Initialization of Data Members and the Default Constructor......Page 728
Arrays of Class Objects (Variables) and Constructors......Page 729
Destructors......Page 731
Data Abstraction, Classes, and Abstract Data Types......Page 732
A struct versus a class......Page 734
Information Hiding......Page 735
Executable Code......Page 739
More Examples of Classes......Page 741
Inline Functions......Page 750
Static Members of a Class......Page 751
Programming Example: Juice Machine......Page 757
Quick Review......Page 772
Exercises......Page 774
Programming Exercises......Page 786
Chapter 11: INHERITANCE AND COMPOSITION......Page 793
Inheritance......Page 794
Redefining (Overriding) Member Functions of the Base Class......Page 797
Constructors of Derived and Base Classes......Page 804
Destructors in a Derived Class......Page 813
Multiple Inclusions of a Header File......Page 814
C11 Stream Classes......Page 818
Inheritance as public, protected, or private......Page 819
(Accessing protected Members in the Derived Class)......Page 820
Composition (Aggregation)......Page 823
Object-Oriented Design (OOD) and Object-Oriented Programming (OOP)......Page 828
Identifying Classes, Objects, and Operations......Page 830
Programming Example: Grade Report......Page 831
Exercises......Page 852
Programming Exercises......Page 861
Chapter 12: POINTERS, CLASSES, VIRTUAL FUNCTIONS, ABSTRACT CLASSES, AND LISTS......Page 867
Declaring Pointer Variables......Page 868
Address of Operator (&)......Page 870
Dereferencing Operator (*)......Page 871
Classes, Structs, and Pointer Variables......Page 876
Initializing Pointer Variables Using nullptr......Page 879
Operator new......Page 880
Operator delete......Page 881
Operations on Pointer Variables......Page 885
Dynamic Arrays......Page 887
Arrays and Range-Based for Loops (Revisited)......Page 890
Functions and Pointers......Page 891
Dynamic Two-Dimensional Arrays......Page 892
Shallow versus Deep Copy and Pointers......Page 895
Classes and Pointers: Some Peculiarities......Page 897
Destructor......Page 898
Assignment Operator......Page 899
Copy Constructor......Page 901
Inheritance, Pointers, and Virtual Functions......Page 908
Classes and Virtual Destructors......Page 915
Abstract Classes and Pure Virtual Functions......Page 916
Array-Based Lists......Page 924
Unordered Lists......Page 931
Ordered Lists......Page 936
Address of Operator and Classes......Page 937
Quick Review......Page 939
Exercises......Page 942
Programming Exercises......Page 953
Chapter 13: OVERLOADING AND TEMPLATES......Page 957
Why Operator Overloading Is Needed......Page 958
Operator Overloading......Page 959
Overloading an Operator: Some Restrictions......Page 960
Pointer this......Page 963
Friend Functions of Classes......Page 968
Operator Functions as Member Functions and Nonmember Functions......Page 971
Overloading Binary Operators......Page 974
Overloading the Stream Insertion (<<) and Extraction (>>) Operators......Page 980
Overloading the Assignment Operator (=)......Page 985
Overloading Unary Operators......Page 993
Operator Overloading: Member versus Nonmember......Page 999
Programming Example: clockType......Page 1000
Programming Example: Complex Numbers......Page 1009
Overloading the Array Index (Subscript) Operator ([])......Page 1014
Programming Example: newString......Page 1016
Function Templates......Page 1023
Class Templates......Page 1025
Array-Based Lists (Revisited)......Page 1028
C1111 Random Number Generator......Page 1035
Quick Review......Page 1037
Exercises......Page 1039
Programming Exercises......Page 1046
Chapter 14: EXCEPTION HANDLING......Page 1057
Handling Exceptions within a Program......Page 1058
try/catch Block......Page 1062
Using C11 Exception Classes......Page 1069
Creating Your Own Exception Classes......Page 1073
Rethrowing and Throwing an Exception......Page 1082
Fix the Error and Continue......Page 1086
Log the Error and Continue......Page 1087
Stack Unwinding......Page 1088
Quick Review......Page 1091
Exercises......Page 1093
Programming Exercises......Page 1099
Chapter 15: RECURSION......Page 1101
Recursive Definitions......Page 1102
Infinite Recursion......Page 1104
Problem Solving Using Recursion......Page 1105
Recursion or Iteration......Page 1115
Programming Example: Converting a Number from Binary to Decimal......Page 1117
Programming Example: Converting a Number from Decimal to Binary......Page 1121
Quick Review......Page 1124
Exercises......Page 1125
Programming Exercises......Page 1130
Chapter 16: LINKED LISTS......Page 1135
Linked Lists......Page 1136
Linked Lists: Some Properties......Page 1137
Deletion......Page 1143
Building a Linked List......Page 1144
Linked List as an ADT......Page 1149
Member Variables of the class linkedListType......Page 1150
Linked List Iterators......Page 1151
Print the List......Page 1157
Begin and End......Page 1158
Copy the List......Page 1159
Copy Constructor......Page 1160
Unordered Linked Lists......Page 1161
Search the List......Page 1162
Insert the First Node......Page 1163
Insert the Last Node......Page 1164
Header File of the Unordered Linked List......Page 1169
Ordered Linked Lists......Page 1170
Search the List......Page 1171
Insert a Node......Page 1172
Insert First and Insert Last......Page 1176
Delete a Node......Page 1177
Header File of the Ordered Linked List......Page 1178
Print a Linked List in Reverse Order (Recursion Revisited)......Page 1181
printListReverse......Page 1183
Doubly Linked Lists......Page 1184
Destroy the List......Page 1187
Reverse Print the List......Page 1188
First and Last Elements......Page 1189
Circular Linked Lists......Page 1195
Programming Example: DVD Store......Page 1196
Exercises......Page 1216
Programming Exercises......Page 1223
Chapter 17: STACKS AND QUEUES......Page 1229
Stacks......Page 1230
Stack Operations......Page 1232
Implementation of Stacks as Arrays......Page 1234
Initialize Stack......Page 1237
Push......Page 1238
Pop......Page 1240
Constructor and Destructor......Page 1242
Overloading the Assignment Operator (=)......Page 1243
Stack Header File......Page 1244
Programming Example: Highest GPA......Page 1248
Linked Implementation of Stacks......Page 1252
Empty Stack and Full Stack......Page 1255
Push......Page 1256
Pop......Page 1258
Copy Stack......Page 1260
Overloading the Assignment Operator (=)......Page 1261
Stack as Derived from the class unorderedLinkedList......Page 1264
Application of Stacks: Postfix Expressions Calculator......Page 1265
Function evaluateExpression......Page 1268
Function evaluateOpr......Page 1270
Function printResult......Page 1272
Removing Recursion: Nonrecursive Algorithm to Print a Linked List Backward......Page 1275
Queues......Page 1279
Queue Operations......Page 1280
Implementation of Queues as Arrays......Page 1282
Linked Implementation of Queues......Page 1291
Queue Derived from the class unorderedLinkedListType......Page 1296
Application of Queues: Simulation......Page 1297
Designing a Queuing System......Page 1298
Customer......Page 1299
Server......Page 1302
Server List......Page 1305
Waiting Customers Queue......Page 1309
Main Program......Page 1311
Quick Review......Page 1315
Exercises......Page 1316
Programming Exercises......Page 1325
Chapter18: SEARCHING AND SORTING ALGORITHMS......Page 1329
Search Algorithms......Page 1330
Sequential Search......Page 1331
Binary Search......Page 1333
Performance of Binary Search......Page 1338
Asymptotic Notation: Big-O Notation......Page 1339
Sorting a List: Bubble Sort......Page 1347
Analysis: Bubble Sort......Page 1351
Bubble Sort Algorithm and the class unorderedArrayListType......Page 1352
Selection Sort: Array-Based Lists......Page 1353
Insertion Sort: Array-Based Lists......Page 1355
Analysis: Insertion Sort......Page 1359
Lower Bound on Comparison-Based Sort Algorithms......Page 1360
Quick Sort: Array-Based Lists......Page 1361
Analysis: Quick Sort......Page 1367
Merge Sort: Linked List–Based Lists......Page 1368
Divide......Page 1370
Merge......Page 1372
Analysis: Merge Sort......Page 1375
Programming Example: Election Results......Page 1378
Quick Review......Page 1399
Exercises......Page 1400
Programming Exercises......Page 1406
Chapter19: BINARY TREES......Page 1411
Binary Trees......Page 1412
Copy Tree......Page 1417
Binary Tree Traversal......Page 1418
Implementing Binary Trees......Page 1423
Binary Search Trees......Page 1431
Binary Search Tree: Analysis......Page 1442
Nonrecursive Inorder Traversal......Page 1443
Nonrecursive Preorder Traversal......Page 1445
Nonrecursive Postorder Traversal......Page 1446
Binary Tree Traversal Algorithms and Functions as Parameters......Page 1447
Programming Example: DVD Store (Revisited)......Page 1451
Quick Review......Page 1459
Exercises......Page 1460
Programming Exercises......Page 1464
Chapter20: GRAPHS......Page 1467
Introduction......Page 1468
Graph Definitions and Notations......Page 1469
Adjacency Matrix......Page 1472
Operations on Graphs......Page 1473
Graphs as ADTs......Page 1474
Depth First Traversal......Page 1478
Breadth First Traversal......Page 1480
Shortest Path Algorithm......Page 1482
Shortest Path......Page 1484
Minimal Spanning Tree......Page 1490
Quick Review......Page 1497
Exercises......Page 1499
Programming Exercises......Page 1502
Chapter 21: STANDARD TEMPLATE LIBRARY (STL)......Page 1505
Components of the STL......Page 1506
Sequence Container: vector......Page 1507
Member Functions Common to All Containers......Page 1516
Member Functions Common to Sequence Containers......Page 1518
The copy Algorithm......Page 1519
Range-Based for Loops......Page 1522
Initializing vector Objects during Declaration......Page 1525
Sequence Container: deque......Page 1526
Sequence Container: list......Page 1530
Types of Iterators......Page 1537
Associative Containers......Page 1543
Declaring set or multiset Associative Containers......Page 1544
Item Insertion and Deletion from set/multiset......Page 1546
Stack......Page 1550
Queue......Page 1552
Containers, Associated Header Files, and Iterator Support......Page 1553
Algorithms......Page 1554
STL Algorithm Classification......Page 1555
Function Objects......Page 1557
Insert Iterator......Page 1563
The Functions fill and fill_n......Page 1565
The Functions generate and generate_n......Page 1567
The Functions find, find_if, find_end, and find_first_of......Page 1569
The Functions remove, remove_if, remove_copy,and remove_copy_if......Page 1574
The Functions replace, replace_if, replace_copy, and replace_copy_if......Page 1577
The Functions swap, iter_swap, and swap_ranges......Page 1581
The Functions search, search_n, sort, and binary_search......Page 1584
The Functions adjacent_find, merge, and inplace_merge......Page 1588
The Functions reverse, reverse_copy, rotate, and rotate_copy......Page 1592
The Functions count, count_if, max, max_element, min, min_element, and random_shuffle......Page 1595
The Functions for_each and transform......Page 1599
The Functions includes, set_intersection, set_union, set_difference, and set_symmetric_difference......Page 1602
The Functions accumulate, adjacent_difference, inner_product, and partial_sum......Page 1610
Quick Review......Page 1615
Exercises......Page 1619
Programming Exercises......Page 1624
APPENDIX A: Reserved Words......Page 1625
APPENDIX B: Operator Precedence......Page 1627
ASCII (American Standard Code for Information Interchange)......Page 1629
EBCDIC (Extended Binary Coded Decimal Interchange Code)......Page 1630
APPENDIX D: OPERATOR OVERLOADING......Page 1633
Converting a Base 10 Number to a Binary Number (Base 2)......Page 1635
Converting a Binary Number (Base 2) to Base 10......Page 1637
Converting a Binary Number (Base 2) to Octal (Base 8) and Hexadecimal (Base 16)......Page 1638
Binary Files......Page 1640
Random File Access......Page 1646
Naming Conventions of Header Files in ANSI/ISO Standard C++ and Standard C++......Page 1654
Header File cassert (assert.h)......Page 1657
Header File cctype (ctype.h)......Page 1658
Header File cfloat (float.h)......Page 1659
Header File climits (limits.h)......Page 1660
Header File cmath (math.h)......Page 1662
Header File cstring (string.h)......Page 1663
APPENDIX G: MEMORY SIZE ON A SYSTEM......Page 1667
APPENDIX H: REFERENCES......Page 1669
Chapter 1......Page 1671
Chapter 2......Page 1674
Chapter 3......Page 1678
Chapter 4......Page 1679
Chapter 5......Page 1682
Chapter 6......Page 1684
Chapter 7......Page 1687
Chapter 8......Page 1689
Chapter 9......Page 1691
Chapter 10......Page 1693
Chapter 11......Page 1697
Chapter 12......Page 1700
Chapter 13......Page 1702
Chapter 14......Page 1704
Chapter 15......Page 1707
Chapter 16......Page 1708
Chapter 17......Page 1709
Chapter 18......Page 1712
Chapter 19......Page 1714
Chapter 20......Page 1716
Chapter 21......Page 1718
INDEX......Page 1719