Chapter 1 Object-Oriented Programming Using C++ 1
1.1 Abstract Data Types 1
1.2 Encapsulation 1
1.3 Inheritance 5
1.4 Pointers 8
1.4.1 Pointers and Arrays 10
1.4.2 Pointers and Copy Constructors 12
1.4.3 Pointers and Destructors 14
1.4.4 Pointers and Reference Variables 15
1.4.5 Pointers to Functions 17
1.5 Polymorphism 18
1.6 C++ and Object-Oriented Programming 20
1.7 The Standard Template Library 21
1.7.1 Containers 21
1.7.2 Iterators 21
1.7.3 Algorithms 22
1.7.4 Function Objects 22
1.8 Vectors in the Standard Template Library 24
1.9 Data Structures and Object-Oriented Programming 31
1.10 Case Study： Random Access File 31
1.11 Exercises 42
1.12 Programming Assignments 44
Chapter 2 Complexity Analysis 47
2.1 Computational and Asymptotic Complexity 47
2.2 Big-O Notation 48
2.3 Properties of Big-O Notation 50
2.4 Ω and Θ Notations 51
2.5 Possible Problems 52
2.6 Examples of Complexities 52
2.7 Finding Asymptotic Complexity： Examples 54
2.8 The Best， Average， and Worst Cases 56
2.9 Amortized Complexity 59
2.10 Exercises 62
Chapter 3 Llinked Lis+s 67
3.1 Singly Linked Lists 67
3.1.1 Insertion 72
3.1.2 Deletion 74
3.1.3 Search 79
3.2 Doubly Linked Lists 79
3.3 Circular Lists 83
3.4 Skip Lists 85
3.5 Self-Organizing Lists 89
3.6 Sparse Tables 93
3.7 Lists in the Standard Template Library 96
3.8 Deques in the Standard Template Library 99
3.9 Concluding Remarks 103
3.10 Case Study： A Library 104
3.11 Exercises 113
3.12 Programming Assignments 115
Chapter 4 Stacks and Queues 119
4.1 Stacks 119
4.2 Queues 126
4.3 Priority Queues 132
4.4 Stacks in the Standard Template Library 133
4.5 Queues in the Standard Template Library 134
4.6 Priority Queues in the Standard Template Library 135
4.7 Case Study： Exiting a Maze 137
4.8 Exercises 142
4.9 Programming Assignments 144
Chapter 5 Recursion 147
5.1 Recursive Definitions 147
5.2 Function Calls and Recursion Implementation 149
5.3 Anatomy of a Recursive Call 151
5.4 Tail Recursion 154
5.5 Nontail Recursion 155
5.6 Indirect Recursion 160
5.7 Nested Recursion 162
5.8 Excessive Recursion 162
5.9 Backtracking 165
5.10 Concluding Remarks 172
5.11 Case Study： A Recursive Descent Interpreter 173
5.12 Exercises 180
5.13 Programming Assignments 182
Chapter 6 Binary Trees 187
6.1 Trees， Binary Trees， and Binary Search Trees 187
6.2 Implementing Binary Trees 191
6.3 Searching a Binary Search Tree 193
6.4 Tree Traversal 195
6.4.1 Breadth-First Traversal 196
6.4.2 Depth-First Traversal 197
6.4.3 Stackless Depth-First Traversal 203
6.5 Insertion 208
6.6 Deletion 211
6.6.1 Deletion by Merging 212
6.6.2 Deletion by Copying 215
6.7 Balancing a Tree 217
6.7.1 The DSW Algorithm 219
6.7.2 A VL Trees 222
6.8 Self-Adjusting Trees 226
6.8.1 Self-Restructuring Trees 226
6.8.2 Splaying 228
6.9 Heaps 232
6.9.1 Heaps as Priority Queues 233
6.9.2 Organizing Arrays as Heaps 235
6.10 Polish Notation and Expression Trees 238
6.11 Case Study： Computing Word Frequencies 242
6.12 Exercises 249
6.13 Programming Assignments 252
Chapter 7 Multiway Trees 257
7.1 The Family of B-Trees 257
7.1.1 B-Trees 259
7.1.2 B-Trees 267
7.1.3 B+-Trees 268
7.1.4 Prefiix B+-Trees 270
7.1.5 Bit-Trees 272
7.1.6 R-Trees 273
7.1.7 2-4 Trees 275
7.1.8 Sets and Multisets in the Standard Template Library 281
7.1.9 Maps and Multimaps in the Standard Template Library 286
7.2 Tries 290
7.3 Concluding Remarks 297
7.4 Case Study： Spell Checker 297
7.5 Exercises 307
7.6 Programming Assignments 308
Chapter 8 Graphs 313
8.1 Graph Representation 314
8.2 Graph Traversals 316
8.3 Shortest Paths 319
8.4 Cycle Detection 327
8.5 Spanning Trees 329
8.5.1 Boruvka’s Algorithm 330
8.5.2 Kruskal’s Algorithm 332
8.5.3 Jarnik-Prim’s Algorithm 333
8.5.4 Dijkstra’s Method 333
8.6 Connectivity 334
8.6.1 Connectivity in Undirected Graphs 334
8.6.2 Connectivity in Directed Graphs 336
8.7 Topological Sort 338
8.8 Networks 340
8.8.1 Maximum Flows 340
8.8.2 Maximum Flows of Minimum Cost 349
8.9 Matching 353
8.9.1 Assignment Problem 357
8.9.2 Matching in Nonbipartite Graphs 359
8.10 Eulerian and Hamiltonian Graphs 361
8.10.1 Eulerian Graphs 361
8.10.2 HamiltonianGraphs 362
8.11 Case Study： Distinct Representatives 365
8.12 Exercises 375
8.13 Programming Assignments 377
Chapter 9 Sorting 381
9.1 Elementary Sorting Algorithms 382
9.1.1 Insertion Sort 382
9.1.2 Selection Sort 384
9.1.3 Bubble Sort 386
9.2 Decision Trees 388
9.3 Effiicient Sorting Algorithms 391
9.3.1 Shell Sort 391
9.3.2 Heap Sort 394
9.3.3 Quicksort 397
9.3.4 Mergesort 402
9.3.5 Radix Sort 405
9.4 Sorting in the Standard Template Library 409
9.5 Concluding Remarks 412
9.6 Case Study： Adding Polynomials 413
9.7 Exercises 420
9.8 Programming Assignments 421
Chapter 10 Hashing 425
10.1 Hash Functions 425
10.1.1 Division 426
10.1.2 Folding 426
10.1.3 Mid-Square Function 427
10.1.4 Extraction 427
10.1.5 Radix Transformation 427
10.2 Collision Resolution 427
10.2.1 Open Addressing 428
10.2.2 Chaining 433
10.2.3 Bucket Addressing 435
10.3 Deletion 436
10.4 Perfect Hash Functions 437
10.4.1 Cichelli’s Method 437
10.4.2 The FHCD Algorithm 439
10.5 Hash Functions for Extendible Files 441
10.5.1 Extendible Hashing 442
10.5.2 Linear Hashing 444
10.6 Case Study：Hashing with Buckets 446
10.7 Exercises 454
10.8 Programming Assignments 455
Chapter 11 Data Compression 459
11.1 Conditions for Data Compression 459
11.2 Huffman Coding 461
11.3 Shannon-Fano Code 473
11.4 Run-Length Encoding 473
11.5 Ziv-Lempel Code 475
11.6 Case Study： Huffman Method with Run-Length Encoding 477
11.7 Exercises 487
11.8 Programming Assignments 488
Chapter 12 Memory Management 491
12.1 The Sequential-Fit Methods 492
12.2 The Nonsequential-Fit Methods 493
12.3 Garbage Collection 500
12.3.1 Mark-and-Sweep 501
12.3.2 Copying Methods 507
12.3.3 incremental Garbage Collection 509
12.4 Concluding Remarks 515
12.5 Case Study： An In-Place Garbage Collector 516
12.6 Exercises 523
12.7 Programming Assignments 524
Appendix A Computing Big-O 529
Appendix B Algorithms in the Standard Template Library 535