The Tomes of Delphi Algorithms and Data Structures

Contents
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x
Chapter 1 What is an Algorithm? . . . . . . . . . . . . . . . . . . . . . . . . 1
What is an Algorithm? . . . . . . . . . . . . . . . . . . . . . . . . . 1
Analysis of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 3
The Big-Oh Notation . . . . . . . . . . . . . . . . . . . . . . . . . 6
Best, Average, and Worst Cases . . . . . . . . . . . . . . . . . 8
Algorithms and the Platform . . . . . . . . . . . . . . . . . . . . . . 8
Virtual Memory and Paging . . . . . . . . . . . . . . . . . . . . . 9
Thrashing . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Locality of Reference . . . . . . . . . . . . . . . . . . . . . 11
The CPU Cache . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Data Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Space Versus Time Tradeoffs . . . . . . . . . . . . . . . . . . . . 14
Long Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Use const . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Be Wary of Automatic Conversions . . . . . . . . . . . . . . . . . 17
Debugging and Testing . . . . . . . . . . . . . . . . . . . . . . . . 18
Assertions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Logging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Tracing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Coverage Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 23
Unit Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Chapter 2 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Array Types in Delphi . . . . . . . . . . . . . . . . . . . . . . . . . 28
Standard Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Dynamic Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
New-style Dynamic Arrays . . . . . . . . . . . . . . . . . . . . . 40
TList Class, an Array of Pointers. . . . . . . . . . . . . . . . . . . . 41
Overview of the TList Class. . . . . . . . . . . . . . . . . . . . . 41
TtdObjectList Class . . . . . . . . . . . . . . . . . . . . . . . . . 43
vArrays on Disk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Chapter 3 Linked Lists, Stacks, and Queues . . . . . . . . . . . . . . . . . 63
Singly Linked Lists. . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Linked List Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . 65
Creating a Singly Linked List . . . . . . . . . . . . . . . . . . . . 65
Inserting into and Deleting from a Singly Linked List . . . . . . . 65
Traversing a Linked List . . . . . . . . . . . . . . . . . . . . . . 68
Efficiency Considerations . . . . . . . . . . . . . . . . . . . . . . 69
Using a Head Node . . . . . . . . . . . . . . . . . . . . . . 69
Using a Node Manager . . . . . . . . . . . . . . . . . . . . 70
The Singly Linked List Class . . . . . . . . . . . . . . . . . . . . 76
Doubly Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . 84
Inserting and Deleting from a Doubly Linked List . . . . . . . . . 85
Efficiency Considerations . . . . . . . . . . . . . . . . . . . . . . 88
Using Head and Tail Nodes . . . . . . . . . . . . . . . . . . 88
Using a Node Manager . . . . . . . . . . . . . . . . . . . . 88
The Doubly Linked List Class . . . . . . . . . . . . . . . . . . . . 88
Benefits and Drawbacks of Linked Lists . . . . . . . . . . . . . . . . 96
Stacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
Stacks Using Linked Lists . . . . . . . . . . . . . . . . . . . . . . 97
Stacks Using Arrays . . . . . . . . . . . . . . . . . . . . . . . . 100
Example of Using a Stack . . . . . . . . . . . . . . . . . . . . . 103
Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
Queues Using Linked Lists . . . . . . . . . . . . . . . . . . . . 106
Queues Using Arrays . . . . . . . . . . . . . . . . . . . . . . . 109
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
Chapter 4 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
Compare Routines . . . . . . . . . . . . . . . . . . . . . . . . . . 115
Sequential Search . . . . . . . . . . . . . . . . . . . . . . . . . . 118
Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
Inserting into Sorted Containers . . . . . . . . . . . . . . . . . 129
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
Chapter 5 Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
Sorting Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 133
Shuffling a TList . . . . . . . . . . . . . . . . . . . . . . . . . . 136
Sort Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
Slowest Sorts . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
Bubble Sort. . . . . . . . . . . . . . . . . . . . . . . . . . 138
vi
ContentsShaker Sort. . . . . . . . . . . . . . . . . . . . . . . . . . 140
Selection Sort . . . . . . . . . . . . . . . . . . . . . . . . 142
Insertion Sort. . . . . . . . . . . . . . . . . . . . . . . . . 144
Fast Sorts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
Shell Sort. . . . . . . . . . . . . . . . . . . . . . . . . . . 147
Comb Sort . . . . . . . . . . . . . . . . . . . . . . . . . . 150
Fastest Sorts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . 152
Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
Merge Sort with Linked Lists . . . . . . . . . . . . . . . . . . . 176
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
Chapter 6 Randomized Algorithms . . . . . . . . . . . . . . . . . . . . . 183
Random Number Generation . . . . . . . . . . . . . . . . . . . . 184
Chi-Squared Tests . . . . . . . . . . . . . . . . . . . . . . . . . 185
Middle-Square Method . . . . . . . . . . . . . . . . . . . . . . 188
Linear Congruential Method . . . . . . . . . . . . . . . . . . . 189
Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
The Uniformity Test . . . . . . . . . . . . . . . . . . . . . 195
The Gap Test . . . . . . . . . . . . . . . . . . . . . . . . . 195
The Poker Test . . . . . . . . . . . . . . . . . . . . . . . . 197
The Coupon Collector’s Test . . . . . . . . . . . . . . . . . 198
Results of Applying Tests . . . . . . . . . . . . . . . . . . . . . 200
Combining Generators . . . . . . . . . . . . . . . . . . . . 201
Additive Generators . . . . . . . . . . . . . . . . . . . . . 203
Shuffling Generators . . . . . . . . . . . . . . . . . . . . . 205
Summary of Generator Algorithms . . . . . . . . . . . . . . . . 207
Other Random Number Distributions . . . . . . . . . . . . . . . . 208
Skip Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
Searching through a Skip List . . . . . . . . . . . . . . . . . . . 211
Insertion into a Skip List . . . . . . . . . . . . . . . . . . . . . 215
Deletion from a Skip List . . . . . . . . . . . . . . . . . . . . . 218
Full Skip List Class Implementation. . . . . . . . . . . . . . . . 219
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
Chapter 7 Hashing and Hash Tables . . . . . . . . . . . . . . . . . . . . . 227
Hash Functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
Simple Hash Function for Strings . . . . . . . . . . . . . . . . . 230
The PJW Hash Functions . . . . . . . . . . . . . . . . . . . . . 230
Collision Resolution with Linear Probing . . . . . . . . . . . . . . 232
Advantages and Disadvantages of Linear Probing . . . . . . . . 233
Deleting Items from a Linear Probe Hash Table . . . . . . . . . 235
The Linear Probe Hash Table Class . . . . . . . . . . . . . . . . 237
Other Open-Addressing Schemes . . . . . . . . . . . . . . . . . . 245
Quadratic Probing . . . . . . . . . . . . . . . . . . . . . . . . . 246

Pseudorandom Probing . . . . . . . . . . . . . . . . . . . . . . 246
Double Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . 247
Collision Resolution through Chaining . . . . . . . . . . . . . . . 247
Advantages and Disadvantages of Chaining . . . . . . . . . . . 248
The Chained Hash Table Class . . . . . . . . . . . . . . . . . . 249
Collision Resolution through Bucketing . . . . . . . . . . . . . . . 259
Hash Tables on Disk . . . . . . . . . . . . . . . . . . . . . . . . . 260
Extendible Hashing . . . . . . . . . . . . . . . . . . . . . . . . 261
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
Chapter 8 Binary Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
Creating a Binary Tree . . . . . . . . . . . . . . . . . . . . . . . . 279
Insertion and Deletion with a Binary Tree . . . . . . . . . . . . . . 279
Navigating through a Binary Tree . . . . . . . . . . . . . . . . . . 281
Pre-order, In-order, and Post-order Traversals . . . . . . . . . . 282
Level-order Traversals . . . . . . . . . . . . . . . . . . . . . . . 288
Class Implementation of a Binary Tree . . . . . . . . . . . . . . . 289
Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . 295
Insertion with a Binary Search Tree. . . . . . . . . . . . . . . . 298
Deletion from a Binary Search Tree . . . . . . . . . . . . . . . . 300
Class Implementation of a Binary Search Tree . . . . . . . . . . 303
Binary Search Tree Rearrangements . . . . . . . . . . . . . . . 304
Splay Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
Class Implementation of a Splay Tree. . . . . . . . . . . . . . . 309
Red-Black Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . 312
Insertion into a Red-Black Tree . . . . . . . . . . . . . . . . . . 314
Deletion from a Red-Black Tree . . . . . . . . . . . . . . . . . . 319
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
Chapter 9 Priority Queues and Heapsort . . . . . . . . . . . . . . . . . . 331
The Priority Queue . . . . . . . . . . . . . . . . . . . . . . . . . . 331
First Simple Implementation . . . . . . . . . . . . . . . . . . . 332
Second Simple Implementation . . . . . . . . . . . . . . . . . . 335
The Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
Insertion into a Heap . . . . . . . . . . . . . . . . . . . . . . . 338
Deletion from a Heap . . . . . . . . . . . . . . . . . . . . . . . 338
Implementation of a Priority Queue with a Heap. . . . . . . . . 340
Heapsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
Floyd’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 345
Completing Heapsort . . . . . . . . . . . . . . . . . . . . . . . 346
Extending the Priority Queue . . . . . . . . . . . . . . . . . . . . 348
Re-establishing the Heap Property . . . . . . . . . . . . . . . . 349
Finding an Arbitrary Item in the Heap . . . . . . . . . . . . . . 350
Implementation of the Extended Priority Queue . . . . . . . . . 350
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
Chapter 10 State Machines and Regular Expressions . . . . . . . . . . . . 357
State Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
Using State Machines: Parsing . . . . . . . . . . . . . . . . . . 357
Parsing Comma-Delimited Files . . . . . . . . . . . . . . . 363
Deterministic and Non-deterministic State Machines. . . . . . . 366
Regular Expressions . . . . . . . . . . . . . . . . . . . . . . . . . 378
Using Regular Expressions . . . . . . . . . . . . . . . . . . . . 380
Parsing Regular Expressions . . . . . . . . . . . . . . . . . 380
Compiling Regular Expressions . . . . . . . . . . . . . . . 387
Matching Strings to Regular Expressions. . . . . . . . . . . 399
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
Chapter 11 Data Compression . . . . . . . . . . . . . . . . . . . . . . . . 409
Representations of Data . . . . . . . . . . . . . . . . . . . . . . . 409
Data Compression . . . . . . . . . . . . . . . . . . . . . . . . . . 410
Types of Compression . . . . . . . . . . . . . . . . . . . . . . . 410
Bit Streams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
Minimum Redundancy Compression. . . . . . . . . . . . . . . . . 415
Shannon-Fano Encoding . . . . . . . . . . . . . . . . . . . . . 416
Huffman Encoding . . . . . . . . . . . . . . . . . . . . . . . . 421
Splay Tree Encoding. . . . . . . . . . . . . . . . . . . . . . . . 435
Dictionary Compression . . . . . . . . . . . . . . . . . . . . . . . 445
LZ77 Compression Description . . . . . . . . . . . . . . . . . . 445
Encoding Literals Versus Distance/Length Pairs . . . . . . . 448
LZ77 Decompression . . . . . . . . . . . . . . . . . . . . . 449
LZ77 Compression . . . . . . . . . . . . . . . . . . . . . . 456
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467
Chapter 12 Advanced Topics. . . . . . . . . . . . . . . . . . . . . . . . . . 469
Readers-Writers Algorithm . . . . . . . . . . . . . . . . . . . . . . 469
Producers-Consumers Algorithm. . . . . . . . . . . . . . . . . . . 478
Single Producer, Single Consumer Model . . . . . . . . . . . . . 478
Single Producer, Multiple Consumer Model. . . . . . . . . . . . 486
Finding Differences between Two Files . . . . . . . . . . . . . . . 496
Calculating the LCS of Two Strings . . . . . . . . . . . . . . . . 497
Calculating the LCS of Two Text Files. . . . . . . . . . . . . . . 511
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514
Epilogue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 516
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518


Another Delphi Books
Another The Core of CS Books
Download