Oreilly Mastering Algorithms with C

【实例简介】Oreilly Mastering Algorithms with C

Mastering Algorithms with C

【实例截图】

【核心代码】

Table of Contents
Preface ..................................................................................................................... xi
I. Preliminaries .......................................................................................... 1
1. Introduction ................................................................................................ 3
An Introduction to Data Structures ................................................................. 4
An Introduction to Algorithms ........................................................................ 5
A Bit About Software Engineering .................................................................. 8
How to Use This Book .................................................................................. 10
2. Pointer Manipulation ........................................................................... 11
Pointer Fundamentals .................................................................................... 12
Storage Allocation .......................................................................................... 12
Aggregates and Pointer Arithmetic ................................................................ 15
Pointers as Parameters to Functions ............................................................. 17
Generic Pointers and Casts ............................................................................ 21
Function Pointers ........................................................................................... 23
Questions and Answers ................................................................................. 24
Related Topics ................................................................................................ 25
3. Recursion ................................................................................................... 27
Basic Recursion .............................................................................................. 28
Tail Recursion ................................................................................................. 32
Questions and Answers ................................................................................. 34
Related Topics ................................................................................................ 37
vi Table of Contents
4. Analysis of Algorithms .......................................................................... 38
Worst-Case Analysis ....................................................................................... 39
O-Notation ...................................................................................................... 40
Computational Complexity ............................................................................ 42
Analysis Example: Insertion Sort ................................................................... 45
Questions and Answers ................................................................................. 47
Related Topics ................................................................................................ 48
II. Data Structures .................................................................................. 49
5. Linked Lists ............................................................................................... 51
Description of Linked Lists ............................................................................ 52
Interface for Linked Lists ............................................................................... 53
Implementation and Analysis of Linked Lists ............................................... 56
Linked List Example: Frame Management .................................................... 65
Description of Doubly-Linked Lists ............................................................... 68
Interface for Doubly-Linked Lists .................................................................. 68
Implementation and Analysis of Doubly Linked Lists ................................. 72
Description of Circular Lists .......................................................................... 82
Interface for Circular Lists .............................................................................. 82
Implementation and Analysis of Circular Lists ............................................. 84
Circular List Example: Second-Chance Page Replacement .......................... 91
Questions and Answers ................................................................................. 94
Related Topics ................................................................................................ 96
6. Stacks and Queues ................................................................................. 98
Description of Stacks ..................................................................................... 99
Interface for Stacks ....................................................................................... 100
Implementation and Analysis of Stacks ...................................................... 102
Description of Queues ................................................................................. 105
Interface for Queues .................................................................................... 105
Implementation and Analysis of Queues .................................................... 107
Queue Example: Event Handling ................................................................ 110
Questions and Answers ............................................................................... 113
Related Topics .............................................................................................. 114
7. Sets .............................................................................................................. 115
Description of Sets ....................................................................................... 116
Interface for Sets .......................................................................................... 119
Table of Contents vii
Implementation and Analysis of Sets .......................................................... 122
Set Example: Set Covering ........................................................................... 133
Questions and Answers ............................................................................... 138
Related Topics .............................................................................................. 140
8. Hash Tables ............................................................................................. 141
Description of Chained Hash Tables .......................................................... 143
Interface for Chained Hash Tables .............................................................. 147
Implementation and Analysis of Chained Hash Tables ............................. 149
Chained Hash Table Example: Symbol Tables ........................................... 157
Description of Open-Addressed Hash Tables ............................................ 161
Interface for Open-Addressed Hash Tables ............................................... 164
Implementation and Analysis of Open Addressed Hash Tables ............... 166
Questions and Answers ............................................................................... 176
Related Topics .............................................................................................. 177
9. Trees ........................................................................................................... 178
Description of Binary Trees ......................................................................... 180
Interface for Binary Trees ............................................................................ 183
Implementation and Analysis of Binary Trees ........................................... 187
Binary Tree Example: Expression Processing ............................................ 199
Description of Binary Search Trees ............................................................ 203
Interface for Binary Search Trees ................................................................ 204
Implementation and Analysis of Binary Search Trees ............................... 206
Questions and Answers ............................................................................... 230
Related Topics .............................................................................................. 233
10. Heaps and Priority Queues .............................................................. 235
Description of Heaps ................................................................................... 236
Interface for Heaps ...................................................................................... 237
Implementation and Analysis of Heaps ...................................................... 239
Description of Priority Queues .................................................................... 250
Interface for Priority Queues ....................................................................... 251
Implementation and Analysis of Priority Queues ...................................... 252
Priority Queue Example: Parcel Sorting ..................................................... 254
Questions and Answers ............................................................................... 256
Related Topics .............................................................................................. 258
viii Table of Contents
11. Graphs ....................................................................................................... 259
Description of Graphs ................................................................................. 261
Interface for Graphs ..................................................................................... 267
Implementation and Analysis of Graphs .................................................... 270
Graph Example: Counting Network Hops ................................................. 284
Graph Example: Topological Sorting .......................................................... 290
Questions and Answers ............................................................................... 295
Related Topics .............................................................................................. 297
III. Algorithms ........................................................................................... 299
12. Sorting and Searching ........................................................................ 301
Description of Insertion Sort ....................................................................... 303
Interface for Insertion Sort ........................................................................... 303
Implementation and Analysis of Insertion Sort .......................................... 304
Description of Quicksort ............................................................................. 307
Interface for Quicksort ................................................................................. 308
Implementation and Analysis of Quicksort ................................................ 308
Quicksort Example: Directory Listings ........................................................ 314
Description of Merge Sort ............................................................................ 317
Interface for Merge Sort ............................................................................... 318
Implementation and Analysis of Merge Sort .............................................. 318
Description of Counting Sort ....................................................................... 324
Interface for Counting Sort .......................................................................... 325
Implementation and Analysis of Counting Sort .......................................... 325
Description of Radix Sort ............................................................................. 329
Interface for Radix Sort ................................................................................ 329
Implementation and Analysis of Radix Sort ............................................... 330
Description of Binary Search ....................................................................... 333
Interface for Binary Search .......................................................................... 334
Implementation and Analysis of Binary Search ......................................... 334
Binary Search Example: Spell Checking ..................................................... 337
Questions and Answers ............................................................................... 339
Related Topics .............................................................................................. 341
13. Numerical Methods .............................................................................. 343
Description of Polynomial Interpolation .................................................... 344
Interface for Polynomial Interpolation ........................................................ 348
Implementation and Analysis of Polynomial Interpolation ....................... 349
Table of Contents ix
Description of Least-Squares Estimation ..................................................... 352
Interface for Least-Squares Estimation ........................................................ 353
Implementation and Analysis of Least-Squares Estimation ........................ 354
Description of the Solution of Equations ................................................... 355
Interface for the Solution of Equations ....................................................... 360
Implementation and Analysis of the Solution of Equations ...................... 360
Questions and Answers ............................................................................... 362
Related Topics .............................................................................................. 363
14. Data Compression ................................................................................ 365
Description of Bit Operations ..................................................................... 369
Interface for Bit Operations ......................................................................... 369
Implementation and Analysis of Bit Operations ........................................ 370
Description of Huffman Coding .................................................................. 375
Interface for Huffman Coding ..................................................................... 379
Implementation and Analysis of Huffman Coding ..................................... 380
Huffman Coding Example: Optimized Networking ................................... 396
Description of LZ77 ..................................................................................... 399
Interface for LZ77 ......................................................................................... 402
Implementation and Analysis of LZ77 ........................................................ 403
Questions and Answers ............................................................................... 418
Related Topics .............................................................................................. 420
15. Data Encryption ................................................................................... 422
Description of DES ....................................................................................... 425
Interface for DES .......................................................................................... 432
Implementation and Analysis of DES ......................................................... 433
DES Example: Block Cipher Modes ............................................................ 445
Description of RSA ....................................................................................... 448
Interface for RSA .......................................................................................... 452
Implementation and Analysis of RSA .......................................................... 452
Questions and Answers ............................................................................... 456
Related Topics .............................................................................................. 458
16. Graph Algorithms ................................................................................. 460
Description of Minimum Spanning Trees ................................................... 463
Interface for Minimum Spanning Trees ...................................................... 465
Implementation and Analysis of Minimum Spanning Trees ...................... 466
Description of Shortest Paths ...................................................................... 472
Interface for Shortest Paths .......................................................................... 474
x Table of Contents
Implementation and Analysis of Shortest Paths ......................................... 475
Shortest Paths Example: Routing Tables ..................................................... 481
Description of the Traveling-Salesman Problem ........................................ 485
Interface for the Traveling-Salesman Problem ........................................... 487
Implementation and Analysis of the Traveling-Salesman Problem ........... 488
Questions and Answers ............................................................................... 493
Related Topics .............................................................................................. 495
17. Geometric Algorithms ......................................................................... 496
Description of Testing Whether Line Segments Intersect .......................... 499
Interface for Testing Whether Line Segments Intersect ............................. 502
Implementation and Analysis of Testing Whether Line
Segments Intersect ....................................................................................... 503
Description of Convex Hulls ....................................................................... 505
Interface for Convex Hulls .......................................................................... 507
Implementation and Analysis of Convex Hulls .......................................... 507
Description of Arc Length on Spherical Surfaces ....................................... 512
Interface for Arc Length on Spherical Surfaces .......................................... 515
Implementation and Analysis of Arc Length on Spherical Surfaces .......... 515
Arc Length Example: Approximating Distances on Earth .......................... 517
Questions and Answers ............................................................................... 520
Related Topics .............................................................................................. 523
Index .................................................................................................................... 525