本书是数据结构和算法分析方面的经典教材, 通过C程序的实现, 着重阐述了抽象数据类型 (ADT ) 的概念, 并对算法的效率、性能和运行时间进行了分析。

作者Mark Allen Weiss在数据结构与算法分析方面卓有建树，他在此方面的著作尤其畅销，并受到广泛好评。他的Data Structures and Algorithm Analysis曾被评为20世纪优秀的30疗计算机著作之一，本书是此书的C语言版。他在数据结构与算法分析方面的系列著作已被国际上500余所大学用做教材。
本书根 

Mark Allen Weiss，美国佛罗里达国际大学计算机学院教授，普林斯顿大学汁算机科学博士，他目前是AP（Advanced Placemenl）考试汁算机学科委员会的主席。除本书外，他还撰写了Data Structures and Problem Solving Using Java（中文版第3版即将山人民邮电出版社出版）等著作。

Adapters Foreword
Preface

1 Introduction 1
1.1. Whats 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 Analysistt103
4.4. AVL Trees tttttt106
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. Dijkstras 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. Prims Algorithm 316
9.5.2. Kruskals 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