Chapter 1 Review of C++ 1
1.1 THE STANDARD C++PROGRAMMING LANGUAGE 1
1.2 CONDITIONALS 3
1.3 OPERATORS 5
1.4 ITERATION 6
1.5 FUNCTIONS 8
1.6 STRINGS 10
1.7 FILES 12
2.1 POINTERS 25
Chapter 2 Pointers and Arrays 25
2.2 DERIVED TYPES 26
2.3 REFERENCES 27
2.4 PASSING BY REFERENCE 27
2.5 NULL POINTER EXCEPTIONS 29
2.6 THE new AND delete OPERATORS 29
2.7 ARRAYS 31
2.8 DYNAMIC ARRAYS 32
2.9 PASSING AN ARRAY TO A FUNCTION 32
2.10 MULTIDIMENSIONAL ARRAYS 33
3.1 A Point CLASS 47
Chapter 3 Classes 47
3.2 INSTANCESIMPLICIT ARGUMENTS,AND THE this POINTER 49
3.3 COMPILING CLASSES AND THEIR CLIENT PROGRAMS 50
3.4 FRIEND FUNCTIONS 53
3.5 A Line CLASS 54
3.6 A CLASS FOR RANDOM NUMBERS 56
3.7 STATIC MEMBERS 57
3.8 COMPOSITION 59
3.9 INHERITANCE 61
4.1 THE FACTORIAL FUNCTION 76
Chapter 4 Recursion 76
4.2 TRACING A RECURSIVE CALL 77
4.3 THE FIBONACCI SEQUENCE 77
4.4 BINOMIAL COEFFICIENTS 78
4.5 THE EUCLIDEAN ALGORITHM 79
4.6 INDUCTIVE PROOF OF CORRECTNESS 80
4.7 COMPLEXITY ANALYSIS OF RECURSIVE ALGORIHMS 81
4.8 DYNAMIC PROGRAMMING 82
4.9 THE TOWERS OF HANOI 82
4.10 MUTUAL RECURSION 84
5.2 USING stack OBJECTS 92
Chapter 5 Stacks 92
5.1 THE stack INTERFACE 92
5.3 APPLICATIONS OF STACKS 93
5.4 REMOVING RECURSION 96
5.5 CONTIGUOUS IMPLEMENTATION 97
5.6 LINKED IMPLEMENTATION 100
Chapter 6 Queues 110
6.1 THE queue INTERFACE 110
6.2 USING queue OBJECTS 110
6.3 APPLICATIONS OF QUEUES 112
6.4 CONTIGUOUS IMPLEMENTATION 115
6.5 LINKED IMPLEMENTATION 118
Chapter 7 Lists 127
7.1 THE list INTERFACE 127
7.2 USING list OBJECTS 128
7.3 ITERATORS 129
7.4 APPLICATIONS 130
7.5 CIRCULAR LISTS 134
7.6 ORDERED LISTS 136
7.7 AN UNBOUNDED Integer CLASS 137
7.8 IMPLEMENTION OF THE List CLASS 142
Chapter 8 Tables 155
8.1 THE STANDARD pair TYPE 155
8.2 APPLICATIONSUSINGTHE map CLASSTEMPLATE 157
8.3 HASH TABLES 161
8.4 HASH FUNCTIONS 165
8.5 SEPARATE CHAINING 167
Chapter 9 Trees 174
9.1 TREE TERMINOLOGY 174
9.2 DECISION TREES AND TRANSITION DIAGRAMS 176
9.3 TREE TRAVERSAL ALGORITHMS 178
9.4 A Tree CLASS INTERFACE 180
9.5 IMPLEMENTATION OF THE Tree CLASS 182
Chapter 10 Binary Trees 200
10.1 DEFINITIONS 200
10.2 COUNTING BINARY TREES 201
10.3 FULL BINARY TREES 202
10.4 IDENTITY,EQUALITY,AND ISOMORPHISM 203
10.5 COMPLETE BINARY TREES 204
10.6 TREE TRAVERSALS 206
10.7 EXPRESSION TREES 208
10.9 A BinaryTree CLASS INTERFACE 210
10.8 FORESTS 210
10.10 IMPLEMENTATION OF THE BinaryTree CLASS 213
Chapter 11 Search Trees 224
11.1 BINARY SEARCH TREES 224
11.2 IMPLEMENTATION OF BINARY SEARCH TREES 225
11.3 PERFORMANCE CHARACTERISTICS OF BINARY SEARCH TREES 228
11.4 AVL TREES 228
12.2 THE NATURAL MAPPING 235
Chapter 12 Heaps and Priority Queues 235
12.1 HEAPS 235
12.3 INSERTION INTO A HEAP 236
12.4 REMOVAL FROM A HEAP 237
12.5 PRIORITY QUEUES 238
12.6 USING priority_queue OBJECTS 238
12.7 USING A HEAP TO IMPLEMENT A PriorityQueue CLASS TEMPLATE 239
12.8 APPLICATIONS OF PRIORITY QUEUES 241
13.1 PRELIMINARIES 248
13.2 THE BUBBLE SORT 248
Chapter 13 Sorting 248
13 3 THE SELECTION SORT 250
13.4 THE INSERTION SORT 251
13.5 THE MERGE SORT 252
13.6 THE QUICK SORT 255
13.7 HEAPS 256
13.8 THE HEAP SORT 257
13.9 THE SHELL SORT 261
13.10 THE SPEED LIMIT FOR EXCHANGE SORTS 262
Appendix A References 268
B.2 LOGARITHMS 275
Appendix B Essential Mathematics 275
B.1 THE FLOOR AND CEILING FUNCTIONS 275
B.3 THE FIRST PRINCIPLE OF MATHEMATICAL INDUCTION 276
B.4 THE SECOND PRINCIPLE OF MATHEMATICAL INDUCTION 277
B.5 GEOMETRIC SERIES 278
B.6 SUMMATION FORMULAS 278
B.7 ASYMPTOTIC COMPLEXITY CLASSES 279
B.8 HARMONIC NUMBERS 279
B.9 STIRLING'S FORMULA 281
B.10 FIBONACCI NUMBERS 281
B.11 THE GOLDEN MEAN 282
B.12 THE EUCLIDEAN ALGORITHM 283
Appendix C Standard Container Classes 285
C.1 THE vector CLASS TEMPLATE 285
C.2 THE deque CLASS TEMPLATE 290
C.3 THE stack CLASS TEMPLATE 290
C.4 THE queue CLASS TEMPLATE 291
C.5 THE priority_queue CLASS TEMPLATE 291
C.6 THE list CLASS TEMPLATE 292
C.7 THE map CLASS TEMPLATE 294
C.8 THE set CLASS TEMPLATE 296
Appendix D Generic Algorithms 299
Appendix E Example Classes 328
E.1 A BinaryTree CLASS 328
E.2 A BinarySearchTree CLASS 335
E.3 A Card CLASS 336
E.4 A Concordance CLASS 339
E.5 A Date CLASS 340
E.6 A Deck CLASS 347
E.7 A Hand CLASS 348
E.9 A HashTable CLASS TEMPLATE 349
E.8 A Hash FUNCTION STRUCTURE TEMPLATE 349
E.10 A Line CLASS 351
E.11 A List CLASS TEMPLATE 353
E.12 A Matrix CLASS TEMPLATE 358
E.13 AN OrderedList CLASS 360
E.14 A Peraon CLASS 361
E.15 A Point CLASS 363
E.16 A Polynomial CLASS 367
E.17 A PriorityQueue CLASS TEMPLATE 372
E.18 A Purse CLASS 374
E.19 A Queue CLASS 376
E.20 A Random CLASS 377
E.21 A RandomLine CLASS 378
E.22 A RandomPoint CLASS 378
E.23 A Ratio CLASS 379
E.24 A Rational CLASS 381
E.25 A SelforganizingList CLASS 384
E.26 A StackCLASS TEMPLATE 384
E.27 A Tree CLASS 386
Index 399