Data structures and algorithms in C++

Cover......Page 1
Title Page......Page 5
Copyright......Page 6
Preface......Page 9
Contents......Page 17
1 A C++ Primer......Page 25
1.1 Basic C++ Programming Elements......Page 26
14.2.1 The Memory Hierarchy......Page 0
1.1.2 Fundamental Types......Page 28
1.1.3 Pointers, Arrays, and Structures......Page 31
1.1.4 Named Constants, Scope, and Namespaces......Page 37
1.2 Expressions......Page 40
1.2.1 Changing Types through Casting......Page 44
1.3 Control Flow......Page 47
1.4 Functions......Page 50
1.4.1 Argument Passing......Page 52
1.4.2 Overloading and Inlining......Page 54
1.5 Classes......Page 56
1.5.1 Class Structure......Page 57
1.5.2 Constructors and Destructors......Page 61
1.5.3 Classes and Memory Allocation......Page 64
1.5.4 Class Friends and Class Members......Page 67
1.5.5 The Standard Template Library......Page 69
1.6 C++ Program and File Organization......Page 71
1.6.1 An Example Program......Page 72
1.7 Writing a C++ Program......Page 77
1.7.1 Design......Page 78
1.7.3 Coding......Page 79
1.7.4 Testing and Debugging......Page 81
1.8 Exercises......Page 84
2 Object-Oriented Design......Page 89
2.1 Goals, Principles, and Patterns......Page 90
2.1.2 Object-Oriented Design Principles......Page 91
2.1.3 Design Patterns......Page 94
2.2 Inheritance and Polymorphism......Page 95
2.2.2 Polymorphism......Page 102
2.2.3 Examples of Inheritance in C++......Page 103
2.2.4 Multiple Inheritance and Class Casting......Page 108
2.2.5 Interfaces and Abstract Classes......Page 111
2.3 Templates......Page 114
2.3.2 Class Templates......Page 115
2.4 Exceptions......Page 117
2.4.2 Throwing and Catching Exceptions......Page 118
2.4.3 Exception Specification......Page 120
2.5 Exercises......Page 122
3 Arrays, Linked Lists, and Recursion......Page 127
3.1 Using Arrays......Page 128
3.1.2 Sorting an Array......Page 133
3.1.3 Two-Dimensional Arrays and Positional Games......Page 135
3.2 Singly Linked Lists......Page 141
3.2.2 Insertion to the Front of a Singly Linked List......Page 143
3.2.4 Implementing a Generic Singly Linked List......Page 145
3.3 Doubly Linked Lists......Page 147
3.3.2 Removal from a Doubly Linked List......Page 148
3.3.3 A C++ Implementation......Page 149
3.4 Circularly Linked Lists and List Reversal......Page 153
3.4.2 Reversing a Linked List......Page 157
3.5 Recursion......Page 158
3.5.1 Linear Recursion......Page 164
3.5.2 Binary Recursion......Page 168
3.5.3 Multiple Recursion......Page 171
3.6 Exercises......Page 173
4 Analysis Tools......Page 177
4.1 The Seven Functions Used in This Book......Page 178
4.1.3 The Linear Function......Page 180
4.1.6 The Cubic Function and Other Polynomials......Page 182
4.1.7 The Exponential Function......Page 183
4.1.8 Comparing Growth Rates......Page 185
4.2 Analysis of Algorithms......Page 186
4.2.1 Experimental Studies......Page 187
4.2.2 Primitive Operations......Page 188
4.2.3 Asymptotic Notation......Page 190
4.2.4 Asymptotic Analysis......Page 194
4.2.5 Using the Big-Oh Notation......Page 196
4.2.6 A Recursive Algorithm for Computing Powers......Page 200
4.2.7 Some More Examples of Algorithm Analysis......Page 201
4.3 Simple Justification Techniques......Page 205
4.3.3 Induction and Loop Invariants......Page 206
4.4 Exercises......Page 209
5 Stacks, Queues, and Deques......Page 217
5.1 Stacks......Page 218
5.1.1 The Stack Abstract Data Type......Page 219
5.1.2 The STL Stack......Page 220
5.1.4 A Simple Array-Based Stack Implementation......Page 222
5.1.5 Implementing a Stack with a Generic Linked List......Page 226
5.1.6 Reversing a Vector Using a Stack......Page 227
5.1.7 Matching Parentheses and HTML Tags......Page 228
5.2 Queues......Page 232
5.2.2 The STL Queue......Page 233
5.2.3 A C++ Queue Interface......Page 234
5.2.4 A Simple Array-Based Implementation......Page 235
5.2.5 Implementing a Queue with a Circularly Linked List......Page 237
5.3 Double-Ended Queues......Page 241
5.3.2 The STL Deque......Page 242
5.3.4 Adapters and the Adapter Design Pattern......Page 244
5.4 Exercises......Page 247
6 List and Iterator ADTs......Page 251
6.1 Vectors......Page 252
6.1.2 A Simple Array-Based Implementation......Page 253
6.1.3 An Extendable Array Implementation......Page 255
6.1.4 STL Vectors......Page 260
6.2 Lists......Page 262
6.2.2 The List Abstract Data Type......Page 264
6.2.3 Doubly Linked List Implementation......Page 266
6.2.4 STL Lists......Page 271
6.2.5 STL Containers and Iterators......Page 272
6.3 Sequences......Page 279
6.3.3 Implementing a Sequence with an Array......Page 281
6.4 Case Study: Bubble-Sort on a Sequence......Page 283
6.4.2 A Sequence-Based Analysis of Bubble-Sort......Page 284
6.5 Exercises......Page 286
7 Trees......Page 291
7.1 General Trees......Page 292
7.1.1 Tree Definitions and Properties......Page 293
7.1.2 Tree Functions......Page 296
7.1.3 A C++ Tree Interface......Page 297
7.1.4 A Linked Structure for General Trees......Page 298
7.2 Tree Traversal Algorithms......Page 299
7.2.2 Preorder Traversal......Page 302
7.2.3 Postorder Traversal......Page 305
7.3 Binary Trees......Page 308
7.3.1 The Binary Tree ADT......Page 309
7.3.2 A C++ Binary Tree Interface......Page 310
7.3.3 Properties of Binary Trees......Page 311
7.3.4 A Linked Structure for Binary Trees......Page 313
7.3.5 A Vector-Based Structure for Binary Trees......Page 319
7.3.6 Traversals of a Binary Tree......Page 321
7.3.7 The Template Function Pattern......Page 327
7.3.8 Representing General Trees with Binary Trees......Page 333
7.4 Exercises......Page 334
8 Heaps and Priority Queues......Page 345
8.1 The Priority Queue Abstract Data Type......Page 346
8.1.2 Comparators......Page 348
8.1.3 The Priority Queue ADT......Page 351
8.1.4 A C++ Priority Queue Interface......Page 352
8.1.5 Sorting with a Priority Queue......Page 353
8.1.6 The STL priority_queue Class......Page 354
8.2 Implementing a Priority Queue with a List......Page 355
8.2.1 A C++ Priority Queue Implementation using a List......Page 357
8.2.2 Selection-Sort and Insertion-Sort......Page 359
8.3 Heaps......Page 361
8.3.2 Complete Binary Trees and Their Representation......Page 364
8.3.3 Implementing a Priority Queue with a Heap......Page 368
8.3.4 C++ Implementation......Page 373
8.3.5 Heap-Sort......Page 375
8.3.6 Bottom-Up Heap Construction......Page 377
8.4 Adaptable Priority Queues......Page 381
8.4.1 A List-Based Implementation......Page 382
8.4.2 Location-Aware Entries......Page 384
8.5 Exercises......Page 385
9 Hash Tables, Maps, and Skip Lists......Page 391
9.1 Maps......Page 392
9.1.1 The Map ADT......Page 393
9.1.2 A C++ Map Interface......Page 395
9.1.3 The STL map Class......Page 396
9.1.4 A Simple List-Based Map Implementation......Page 398
9.2 Hash Tables......Page 399
9.2.2 Hash Functions......Page 400
9.2.4 Compression Functions......Page 404
9.2.5 Collision-Handling Schemes......Page 406
9.2.6 Load Factors and Rehashing......Page 410
9.2.7 A C++ Hash Table Implementation......Page 411
9.3 Ordered Maps......Page 418
9.3.1 Ordered Search Tables and Binary Search......Page 419
9.3.2 Two Applications of Ordered Maps......Page 423
9.4 Skip Lists......Page 426
9.4.1 Search and Update Operations in a Skip List......Page 428
9.4.2 A Probabilistic Analysis of Skip Lists......Page 432
9.5 Dictionaries......Page 435
9.5.2 A C++ Dictionary Implementation......Page 437
9.5.3 Implementations with Location-Aware Entries......Page 439
9.6 Exercises......Page 441
10 Search Trees......Page 447
10.1 Binary Search Trees......Page 448
10.1.1 Searching......Page 450
10.1.2 Update Operations......Page 452
10.1.3 C++ Implementation of a Binary Search Tree......Page 456
10.2 AVL Trees......Page 462
10.2.1 Update Operations......Page 464
10.2.2 C++ Implementation of an AVL Tree......Page 470
10.3 Splay Trees......Page 474
10.3.2 When to Splay......Page 478
10.3.3 Amortized Analysis of Splaying......Page 480
10.4 (2,4) Trees......Page 485
10.4.2 Update Operations for (2,4) Tree......Page 491
10.5 Red-Black Trees......Page 497
10.5.1 Update Operations......Page 499
10.5.2 C++ Implementation of a Red-Black Tree......Page 512
10.6 Exercises......Page 516
11 Sorting, Sets, and Selection......Page 523
11.1 Merge-Sort......Page 524
11.1.2 Merging Arrays and Lists......Page 529
11.1.3 The Running Time of Merge-Sort......Page 532
11.1.4 C++ Implementations of Merge-Sort......Page 533
11.1.5 Merge-Sort and Recurrence Equations......Page 535
11.2 Quick-Sort......Page 537
11.2.1 Randomized Quick-Sort......Page 545
11.2.2 C++Implementations and Optimizations......Page 547
11.3 Studying Sorting through an Algorithmic Lens......Page 550
11.3.2 Linear-Time Sorting: Bucket-Sort and Radix-Sort......Page 552
11.3.3 Comparing Sorting Algorithms......Page 555
11.4 Sets and Union/Find Structures......Page 557
11.4.2 Mergable Sets and the Template Method Pattern......Page 558
11.4.3 Partitions with Union-Find Operations......Page 562
11.5 Selection......Page 566
11.5.2 Randomized Quick-Select......Page 567
11.5.3 Analyzing Randomized Quick-Select......Page 568
11.6 Exercises......Page 569
12 Strings and Dynamic Programming......Page 577
12.1 String Operations......Page 578
12.1.1 The STL String Class......Page 579
12.2 Dynamic Programming......Page 581
12.2.2 DNA and Text Sequence Alignment......Page 584
12.3 Pattern Matching Algorithms......Page 588
12.3.2 The Boyer-Moore Algorithm......Page 590
12.3.3 The Knuth-Morris-Pratt Algorithm......Page 594
12.4 Text Compression and the Greedy Method......Page 599
12.4.1 The Huffman-Coding Algorithm......Page 600
12.4.2 The Greedy Method......Page 601
12.5 Tries......Page 602
12.5.2 Compressed Tries......Page 606
12.5.3 Suffix Tries......Page 608
12.5.4 Search Engines......Page 610
12.6 Exercises......Page 611
13 Graph Algorithms......Page 617
13.1 Graphs......Page 618
13.1.1 The Graph ADT......Page 623
13.2 Data Structures for Graphs......Page 624
13.2.2 The Adjacency List Structure......Page 627
13.2.3 The Adjacency Matrix Structure......Page 629
13.3 Graph Traversals......Page 631
13.3.2 Implementing Depth-First Search......Page 635
13.3.3 A Generic DFS Implementation in C++......Page 637
13.3.4 Polymorphic Objects and Decorator Values......Page 645
13.3.5 Breadth-First Search......Page 647
13.4 Directed Graphs......Page 650
13.4.1 Traversing a Digraph......Page 652
13.4.2 Transitive Closure......Page 654
13.4.3 Directed Acyclic Graphs......Page 657
13.5 Shortest Paths......Page 661
13.5.2 Dijkstra’s Algorithm......Page 663
13.6 Minimum Spanning Trees......Page 669
13.6.1 Kruskal’s Algorithm......Page 671
13.6.2 The Prim-Jarnik Algorithm......Page 675
13.7 Exercises......Page 678
14 Memory Management and B-Trees......Page 689
14.1 Memory Management......Page 690
14.1.1 Memory Allocation in C++......Page 693
14.1.2 Garbage Collection......Page 695
14.2 External Memory and Caching......Page 697
14.2.2 Caching Strategies......Page 698
14.3 External Searching and B-Trees......Page 703
14.3.1 (a,b) Trees......Page 704
14.3.2 B-Trees......Page 706
14.4 External-Memory Sorting......Page 707
14.4.1 Multi-Way Merging......Page 708
14.5 Exercises......Page 709
A Useful Mathematical Facts......Page 713
Bibliography......Page 721
Index......Page 726