數(shù)據(jù)結(jié)構(gòu)與算法分析：C語言描述 英文版

1  Introduction    1
     1.1.  What's the Book About?    1
     1.2.  A Brief Introduction to Recursion    3
          Summary     7
          Exercises     7
          References     8

2  Algorithm Analysis    9
     2.1.  Mathematical Background    9
     2.2.  Model    12
     2.3.  What to Analyze    12
     2.4.  Running Time Calculations    14
           2.4.1.  A Simple Example    15
           2.4.2.  General Rules    15
           2.4.3.  Solutions for the Maximum Subsequence Sum Problem     18
           2.4.4.  Logarithms in the Running Time     22
           2.4.5.  Checking Your Analysis     27
           2.4.6.  A Grain of Salt     27
          Summary     28
          Exercises     29
          References     33

3  Lists, Stacks, and Queues     35
     3.1.  Abstract Data Types (ADTs)    35
     3.2.  The List AnT    36
           3.2.1.  Simple Array Implementation of Lists    37
           3.2.2.  Linked Lists    37
           3.2.3.  Programming Details    38
           3.2.4.  Common Errors    43
           3.2.5.  Doubly Linked Lists    45
           3.2.6.  Circularly Linked Lists    46
           3.2.7.  Examples    46
           3.2.8.  Cursor Implementation of Linked Lists    50
     3.3.  The Stack ADT    56
           3.3.1.  Stack Model    56
           3.3.2.  Implementation of Stacks   57
           3.3.3.  Applications       65
    3.4.  The Queue AnT               73
           3.4.1.  Queue Model       73
           3.4.2.  Array Implementation of Queues    73
           3.4.3.  Applications of Queues     78
          Summary    79
          Exercises    79
4  Trees    83
     4.1.  Preliminaries    83
           4.1.1.  Terminology      83
           4.1.2.  Tree Traversals with an Application    84
     4.2.  Binary Trees                 85
           4.2.1.  Implementation     86
           4.2.2.  Expression Trees    87
           4.2.3.  Tree Traversals     90
    4.3.  The Search Tree ADT  Binary Search Trees    97
           4.3.1. MakeEmpty   97
           4.3.2. Find         97
           4.3.3.  FindMin and FindMax    99
           4.3.4.  Insert    100
           4.3.5.  Delete   101
           4.3.6.  Average-Case Analysis 103
     4.4.  AVL Trees     106
           4.4.1.  Single Rotation     108
           4.4.2.  Double Rotation    111
     4.5.  Splay Trees    119
           4.5.1.  A Simple Idea (That Does Not Work)    12 0
           4.5.2. Splaying   12 2
     4.6.  B-Trees            128
           Summary     133
           Exercises     134
           References     141
5  Priority Queues (Heaps)    145
     5.1.  Model    145
     5.2.  Simple Implementations    146
     5.3.  Binary Heap    147
           5.3.1.  Structure Property       147
           5.3.2.  Heap Order Property     148
           5.3.3.  Basic Heap Operations    150
           5.3.4.  Other Heap Operations    154
     5.4.  Applications of Priority Queues     157
           5.4.1.  The Selection Problem    157
           5.4.2.  Event Simulation    159
     5.5.  d-Heaps    160
     5.6.  Leftist Heaps    161
           5.6.1.  Leftist Heap Property    161
           5.6.2.  Leftist Heap Operations   162
     5.7.  Skew Heaps    168
     5.8.  Binomial Queues    170
           5.8.1.  Binomial Queue Structure    170
           5.8.2.  Binomial Queue Operations    172
           5.8.3.  Implementation of Binomial Queues    173
          Summary    180
          Exercises    180
          References   184
6  Sorting   187
     6.1.  Preliminaries    187
     6.2.  Insertion Sort    188
           6.2.1.  The Algorithm    188
           6.2.2.  Analysis of Insertion Sort    189
           6.3.  A Lower Bound for Simple Sorting Algorithms    189
     6.4.  Shellsort    190
           6.4.1.  Worst-Case Analysis of Shellsort    192
     6.5.  Heapsort    194
           6.5.1.  Analysis of Heapsort    196
     6.6.  Mergesort    198
           6.6.1.  Analysis of Mergesort    200
     6.7.  Quicksort    203
           6.7.1.  Picking the Pivot    204
           6.7.2.  Partitioning Strategy   205
           6.7.3.  Small Arrays    20 8
           6.7.4.  Actual Quicksort Routines    208
           6.7.5. Analysis of Quicksort   209
           6.7.6.  A Linear-Expected-Time Algorithm for Selection    213
     6.8.  Sorting Large Structures    215
     6.9.  A General Lower Bound for Sorting    216
           6.9.1.  Decision Trees    217
     6.10.  Bucket Sort and Radix Sort    219
     6.11.  External Sorting         222
           6.11.1.  Why We Need New Algorithms    222
           6.11.2.  Model for External Sorting    222
           6.11.3.  The Simple Algorithm    222
           6.11.4.  Multiway Merge    224
           6.11.5.  Polyphase Merge     225
           6.11.6.  Replacement Selection    226
           Summary    227
           Exercises    229
7  Hashing    235
    7.1.  General Idea    235
    7.2.  Hash Function    237
    7.3.  Separate Chaining    239
    7.4.  Open Addressing      244
          7.4.1.  Linear Probing     244
          7.4.2.  Quadratic Probing  247
          7.4.3.  Double Hashing    251
    7.5.  Rehashing    252
    7.6.  Extendible Hashing    255
         Summary    258
         Exercises    259
         References    262

8  The Disjoint Set AnT    265
     8.1.  Equivalence Relations    265
     8.2.  The Dynamic Equivalence Problem    266
     8.3.  Basic Data Structure    267
     8.4.  Smart Union Algorithms    271
     8.5.  Path Compression    273
     8.6.  Worst Case for Union-by-Rank and Path Compression    275
           8.6.1.  Analysis of the Union/Find Algorithm    275
     8.7.  An Application    281
          Summary    281
          Exercises    282
          References    283

9  Graph Algorithms    285
     9.1.  Definitions    285
           9.1.1.  Representation of Graphs    286
     9.2.  Topological Sort    288
     9.3.  Shortest-Path Algorithms    292
           9.3.1.  Unweighted Shortest Paths    293
           9.3.2.  Dijkstra's Algorithm    297
           9.3.3.  Graphs with Negative Edge Costs    306
           9.3.4.  Acyclic Graphs   307
           9.3.5. All-Pairs Shortest Path    310
     9.4.  Network Flow Problems   310
           9.4.1.  A Simple Maximum-Flow Algorithm    311
     9.5.  Minimum Spanning Tree    315
           9.5.1.  Prim's Algorithm    316
           9.5.2.  Kruskal's Algorithm    318
     9.6.  Applications of Depth-First Search    3:21
           9.6.1.  Undirected Graphs    322
           9.6.2.  Biconnectivity    324
           9.6.3.  Euler Circuits    328
           9.6.4.  Directed Graphs    331
           9.6.5.  Finding Strong Components    333
     9.7.  Introduction to NP-Completeness    334
           9.7.2.  The Class NP    336
           9.7.3.  NP-Complete Problems    337
           Summary    339
           Exercises    339
           References    345

10  Algorithm Design Techniques    349
     10.1.  Greedy Algorithms    349
           10.1.1.  A Simple Scheduling Problem    350
           10.1.2.  Huffman Codes    353
           10.1.3.  Approximate Bin Packing    359
     10.2.  Divide and Conquer    367
            10.2.1.  Running Time of Divide and Conquer Algorithms    368
           10.2.2.  Closest-Points Problem    370
           10.2.3.  The Selection Problem    375
           10.2.4.  Theoretical Improvements for Arithmetic Problems    378
     10.3.  Dynamic Programming    382
           10.3.1.  Using a Table Instead of Recursion    382
           10.3.2.  Ordering Matrix Multiplications    385
           10.3.3.  Optimal Binary Search Tree    389
           10.3.4.  All-Pairs Shortest Path    392
     10.4.  Randomized Algorithms    394
           10.4.1.  Random Number Generators    396
           10.4.2. Skip Lists   399
           10.4.3.  Primality Testing    401
     10.5.  Backtracking Algorithms    403
           10.5.1.  The Turnpike Reconstruction Problem    405
           10.5.2.  Games    407
            Summary    415
            Exercises    417
            References     424

ll  Amortized Analysis    429
     11.1.  An Unrelated Puzzle    430
     11.2.  Binomial Queues    430
     11.3.  Skew Heaps    435
     11.4.  Fibonacci Heaps    437
           11.4.1.  Cutting Nodes in Leftist Heaps    430
           11.4.2.  Lazy Merging for Binomial Queues    441
           11.4.3.  The Fibonacci Heap Operations    444
           11.4.4.  Proof of the Time Bound    445
     11.5.  Splay Trees    447
           Summary    451
           Exercises    452
           References   453

12  Advanced Data Structures and Implementation    455
      12.1.  Top-Down Splay Trees    455
      12.2.  Red Black Trees    459
           12.2.1.  Bottom-Up Insertion    464
           12.2.2.  Top-Down Red Black Trees    465
           12.2.3.  Top-Down Deletion    467
     12.3.  Deterministic Skip Lists    471
     12.4.  &A-Trees    478
     12.5.  Treaps    484
     12.6.  k-d Trees    487
     12.7.  Pairing Heaps    490
           Summary    496
           Exercises    497
           References    499