Data Structures and Algorithms in C++, 2nd Edition

1 A C++ Primer 1

1.1 Basic C++ Programming Elements 2

1.1.1 A Simple C++ Program 2

1.1.2 Fundamental Types 4

1.1.3 Pointers, Arrays, and Structures 7

1.1.4 Named Constants, Scope, and Namespaces 13

1.2 Expressions 16

1.2.1 Changing Types through Casting 20

1.3 Control Flow 23

1.4 Functions 26

1.4.1 Argument Passing 28

1.4.2 Overloading and Inlining 30

1.5 Classes 32

1.5.1 Class Structure 33

1.5.2 Constructors and Destructors 37

1.5.3 Classes and Memory Allocation 40

1.5.4 Class Friends and Class Members 43

1.5.5 The Standard Template Library 45

1.6 C++ Program and File Organization 47

1.6.1 An Example Program 48

1.7 Writing a C++ Program53

1.7.1 Design 54

1.7.2 Pseudo-Code 54

1.7.3 Coding 55

1.7.4 Testing and Debugging 57

1.8 Exercises 60

2 Object-Oriented Design 65

2.1 Goals, Principles, and Patterns 66

2.1.1 Object-Oriented Design Goals 66

2.1.2 Object-Oriented Design Principles 67

2.1.3 Design Patterns 70

2.2 Inheritance and Polymorphism 71

2.2.1 Inheritance in C++ 71

2.2.2 Polymorphism 78

2.2.3 Examples of Inheritance in C++ 79

2.2.4 Multiple Inheritance and Class Casting 84

2.2.5 Interfaces and Abstract Classes 87

2.3 Templates 90

2.3.1 Function Templates 90

2.3.2 Class Templates 91

2.4 Exceptions 93

2.4.1 Exception Objects 93

2.4.2 Throwing and Catching Exceptions 94

2.4.3 Exception Specification 96

2.5 Exercises 98

3 Arrays, Linked Lists, and Recursion 103

3.1 Using Arrays 104

3.1.1 Storing Game Entries in an Array 104

3.1.2 Sorting an Array 109

3.1.3 Two-Dimensional Arrays and Positional Games 111

3.2 Singly Linked Lists 117

3.2.1 Implementing a Singly Linked List 117

3.2.2 Insertion to the Front of a Singly Linked List 119

3.2.3 Removal from the Front of a Singly Linked List 119

3.2.4 Implementing a Generic Singly Linked List 121

3.3 Doubly Linked Lists 123

3.3.1 Insertion into a Doubly Linked List 123

3.3.2 Removal from a Doubly Linked List 124

3.3.3 A C++ Implementation 125

3.4 Circularly Linked Lists and List Reversal 129

3.4.1 Circularly Linked Lists 129

3.4.2 Reversing a Linked List 133

3.5 Recursion 134

3.5.1 Linear Recursion 140

3.5.2 Binary Recursion 144

3.5.3 Multiple Recursion 147

3.6 Exercises 149

4 Analysis Tools 153

4.1 The Seven Functions Used in This Book 154

4.1.1 The Constant Function 154

4.1.2 The Logarithm Function 154

4.1.3 The Linear Function 156

4.1.4 The N-Log-N Function 156

4.1.5 The Quadratic Function 156

4.1.6 The Cubic Function and Other Polynomials 158

4.1.7 The Exponential Function 159

4.1.8 Comparing Growth Rates 161

4.2 Analysis of Algorithms 162

4.2.1 Experimental Studies 163

4.2.2 Primitive Operations 164

4.2.3 Asymptotic Notation 166

4.2.4 Asymptotic Analysis 170

4.2.5 Using the Big-Oh Notation 172

4.2.6 A Recursive Algorithm for Computing Powers 176

4.2.7 Some More Examples of Algorithm Analysis 177

4.3 Simple Justification Techniques 181

4.3.1 By Example 181

4.3.2 The “Contra” Attack 181

4.3.3 Induction and Loop Invariants 182

4.4 Exercises 185

5 Stacks, Queues, and Deques 193

5.1 Stacks 194

5.1.1 The Stack Abstract Data Type 195

5.1.2 The STL Stack 196

5.1.3 A C++ Stack Interface 196

5.1.4 A Simple Array-Based Stack Implementation 198

5.1.5 Implementing a Stack with a Generic Linked List 202

5.1.6 Reversing a Vector Using a Stack 203

5.1.7 Matching Parentheses and HTML Tags 204

5.2 Queues 208

5.2.1 The Queue Abstract Data Type 208

5.2.2 The STL Queue 209

5.2.3 A C++ Queue Interface 210

5.2.4 A Simple Array-Based Implementation 211

5.2.5 Implementing a Queue with a Circularly Linked List 213

5.3 Double-Ended Queues 217

5.3.1 The Deque Abstract Data Type 217

5.3.2 The STL Deque 218

5.3.3 Implementing a Deque with a Doubly Linked List 218

5.3.4 Adapters and the Adapter Design Pattern 220

5.4 Exercises 223

6 List and Iterator ADTs 227

6.1 Vectors 228

6.1.1 The Vector Abstract Data Type 228

6.1.2 A Simple Array-Based Implementation 229

6.1.3 An Extendable Array Implementation 231

6.1.4 STL Vectors 236

6.2 Lists 238

6.2.1 Node-Based Operations and Iterators 238

6.2.2 The List Abstract Data Type 240

6.2.3 Doubly Linked List Implementation 242

6.2.4 STL Lists 247

6.2.5 STL Containers and Iterators 248

6.3 Sequences 255

6.3.1 The Sequence Abstract Data Type 255

6.3.2 Implementing a Sequence with a Doubly Linked List .255

6.3.3 Implementing a Sequence with an Array 257

6.4 Case Study: Bubble-Sort on a Sequence 259

6.4.1 The Bubble-Sort Algorithm 259

6.4.2 A Sequence-Based Analysis of Bubble-Sort 260

6.5 Exercises 262

7 Trees 267

7.1 General Trees 268

7.1.1 Tree Definitions and Properties 269

7.1.2 Tree Functions 272

7.1.3 A C++ Tree Interface 273

7.1.4 A Linked Structure for General Trees 274

7.2 Tree Traversal Algorithms 275

7.2.1 Depth and Height 275

7.2.2 Preorder Traversal 278

7.2.3 Postorder Traversal 281

7.3 Binary Trees 284

7.3.1 The Binary Tree ADT 285

7.3.2 A C++ Binary Tree Interface 286

7.3.3 Properties of Binary Trees 287

7.3.4 A Linked Structure for Binary Trees 289

7.3.5 A Vector-Based Structure for Binary Trees 295

7.3.6 Traversals of a Binary Tree 297

7.3.7 The Template Function Pattern 303

7.3.8 Representing General Trees with Binary Trees 309

7.4 Exercises 310

8 Heaps and Priority Queues 321

8.1 The Priority Queue Abstract Data Type 322

8.1.1 Keys, Priorities, and Total Order Relations 322

8.1.2 Comparators 324

8.1.3 The Priority Queue ADT 327

8.1.4 A C++ Priority Queue Interface 328

8.1.5 Sorting with a Priority Queue 329

8.1.6 The STL priority queue Class 330

8.2 Implementing a Priority Queue with a List 331

8.2.1 A C++ Priority Queue Implementation using a List 333

8.2.2 Selection-Sort and Insertion-Sort 335

8.3 Heaps 337

8.3.1 The Heap Data Structure 337

8.3.2 Complete Binary Trees and Their Representation 340

8.3.3 Implementing a Priority Queue with a Heap 344

8.3.4 C++ Implementation 349

8.3.5 Heap-Sort 351

8.3.6 Bottom-Up Heap Construction ⋆ 353

8.4 Adaptable Priority Queues 357

8.4.1 A List-Based Implementation 358

8.4.2 Location-Aware Entries 360

8.5 Exercises 361

9 Hash Tables, Maps, and Skip Lists 367

9.1 Maps 368

9.1.1 The Map ADT 369

9.1.2 A C++ Map Interface 371

9.1.3 The STL map Class 372

9.1.4 A Simple List-Based Map Implementation 374

9.2 Hash Tables 375

9.2.1 Bucket Arrays 375

9.2.2 Hash Functions 376

9.2.3 Hash Codes 376

9.2.4 Compression Functions 380

9.2.5 Collision-Handling Schemes 382

9.2.6 Load Factors and Rehashing 386

9.2.7 A C++ Hash Table Implementation 387

9.3 Ordered Maps 394

9.3.1 Ordered Search Tables and Binary Search 395

9.3.2 Two Applications of Ordered Maps 399

9.4 Skip Lists 402

9.4.1 Search and Update Operations in a Skip List 404

9.4.2 A Probabilistic Analysis of Skip Lists ⋆ 408

9.5 Dictionaries 411

9.5.1 The Dictionary ADT 411

9.5.2 A C++ Dictionary Implementation 413

9.5.3 Implementations with Location-Aware Entries 415

9.6 Exercises 417

10 Search Trees 423

10.1 Binary Search Trees 424

10.1.1 Searching 426

10.1.2 Update Operations 428

10.1.3 C++ Implementation of a Binary Search Tree 432

10.2 AVL Trees438

10.2.1 Update Operations 440

10.2.2 C++ Implementation of an AVL Tree 446

10.3 Splay Trees 450

10.3.1 Splaying 450

10.3.2 When to Splay 454

10.3.3 Amortized Analysis of Splaying ⋆456

10.4 (2,4) Trees 461

10.4.1 Multi-Way Search Trees 461

10.4.2 Update Operations for (2,4) Trees 467

10.5 Red-Black Trees473

10.5.1 Update Operations 475

10.5.2 C++ Implementation of a Red-Black Tree 488

10.6 Exercises 492

11 Sorting, Sets, and Selection 499

11.1 Merge-Sort500

11.1.1 Divide-and-Conquer 500

11.1.2 Merging Arrays and Lists 505

11.1.3 The Running Time of Merge-Sort 508

11.1.4 C++ Implementations of Merge-Sort 509

11.1.5 Merge-Sort and Recurrence Equations ⋆ 511

11.2 Quick-Sort 513

11.2.1 Randomized Quick-Sort 521

11.2.2 C++ Implementations and Optimizations 523

11.3 Studying Sorting through an Algorithmic Lens 526

11.3.1 A Lower Bound for Sorting 526

11.3.2 Linear-Time Sorting: Bucket-Sort and Radix-Sort 528

11.3.3 Comparing Sorting Algorithms 531

11.4 Sets and Union/Find Structures 533

11.4.1 The Set ADT 533

11.4.2 Mergable Sets and the Template Method Pattern 534

11.4.3 Partitions with Union-Find Operations 538

11.5 Selection 542

11.5.1 Prune-and-Search 542

11.5.2 Randomized Quick-Select 543

11.5.3 Analyzing Randomized Quick-Select 544

11.6 Exercises 545

12 Strings and Dynamic Programming 553

12.1 String Operations 554

12.1.1 The STL String Class 555

12.2 Dynamic Programming 557

12.2.1 Matrix Chain-Product 557

12.2.2 DNA and Text Sequence Alignment 560

12.3 Pattern Matching Algorithms 564

12.3.1 Brute Force 564

12.3.2 The Boyer-Moore Algorithm 566

12.3.3 The Knuth-Morris-Pratt Algorithm 570

12.4 Text Compression and the Greedy Method 575

12.4.1 The Huffman-Coding Algorithm 576

12.4.2 The Greedy Method 577

12.5 Tries 578

12.5.1 Standard Tries 578

12.5.2 Compressed Tries 582

12.5.3 Suffix Tries 584

12.5.4 Search Engines 586

12.6 Exercises 587

13 Graph Algorithms 593

13.1 Graphs 594

13.1.1 The Graph ADT 599

13.2 Data Structures for Graphs 600

13.2.1 The Edge List Structure 600

13.2.2 The Adjacency List Structure 603

13.2.3 The Adjacency Matrix Structure 605

13.3 Graph Traversals 607

13.3.1 Depth-First Search 607

13.3.2 Implementing Depth-First Search 611

13.3.3 A Generic DFS Implementation in C++ 613

13.3.4 Polymorphic Objects and Decorator Values ⋆ 621

13.3.5 Breadth-First Search 623

13.4 Directed Graphs 626

13.4.1 Traversing a Digraph 628

13.4.2 Transitive Closure 630

13.4.3 Directed Acyclic Graphs 633

13.5 Shortest Paths 637

13.5.1 Weighted Graphs 637

13.5.2 Dijkstra’s Algorithm 639

13.6 Minimum Spanning Trees 645

13.6.1 Kruskal’s Algorithm 647

13.6.2 The Prim-Jarn´ık Algorithm 651

13.7 Exercises 654

14 Memory Management and B-Trees 665

14.1 Memory Management 666

14.1.1 Memory Allocation in C++ 669

14.1.2 Garbage Collection 671

14.2 External Memory and Caching 673

14.2.1 The Memory Hierarchy 673

14.2.2 Caching Strategies 674

14.3 External Searching and B-Trees679

14.3.1 (a,b) Trees 680

14.3.2 B-Trees 682

14.4 External-Memory Sorting 683

14.4.1 Multi-Way Merging 684

14.5 Exercises 685

A Useful Mathematical Facts 689

Bibliography 697

Index 702