数据结构与算法分析：C语言描述（英文版·第2版）——图灵原版计算机科学系列 (2009 年度畅销榜NO.1933 )

本书是数据结构和算法分析方面的经典教材。第2版更加精炼并强化了本书创新的对算法和数据结构的讲授方法。通过C程序的实现，着重阐述了抽象数据类型（ADT）的概念，并对算法的效率、性能和运行时间进行了分析。本书适合作为本科数据结构课程或研究生第一年算法分析课程的教材。第1~9章为大多数本科一学期数据结构课程提供了足够的材料。多学时课程可讲授第10章。研究生的算法分析课程可以使用第6~12章的内容。

Adapter''s Foreword\r\nPreface\r\n\r\n1 Introduction 1\r\n 1.1. What''s the Book About? 1\r\n 1.2. A Brief Introduction to Recursion 3\r\n Summary 7\r\n Exercises 7\r\n References 8\r\n\r\n\r\n2 Algorithm Analysis 9\r\n 2.1. Mathematical Background 9\r\n 2.2. Model 12\r\n 2.3. What to Analyze 12\r\n 2.4. Running Time Calculations 14\r\n 2.4.1. A Simple Example 15\r\n 2.4.2. General Rules 15\r\n 2.4.3. Solutions for the Maximum Subsequence Sum Problem 18\r\n 2.4.4. Logarithms in the Running Time 22\r\n 2.4.5. Checking Your Analysis 27\r\n 2.4.6. A Grain of Salt 27\r\n Summary 28\r\n Exercises 29\r\n References 33\r\n\r\n\r\n3 Lists, Stacks, and Queues 35\r\n 3.1. Abstract Data Types (ADTs) 35\r\n 3.2. The List AnT 36\r\n 3.2.1. Simple Array Implementation of Lists 37\r\n 3.2.2. Linked Lists 37\r\n 3.2.3. Programming Details 38\r\n 3.2.4. Common Errors 43\r\n 3.2.5. Doubly Linked Lists 45\r\n 3.2.6. Circularly Linked Lists 46\r\n 3.2.7. Examples 46\r\n 3.2.8. Cursor Implementation of Linked Lists 50\r\n 3.3. The Stack ADT 56\r\n 3.3.1. Stack Model 56\r\n 3.3.2. Implementation of Stacks 57\r\n 3.3.3. Applications 65\r\n 3.4. The Queue AnT 73\r\n 3.4.1. Queue Model 73\r\n 3.4.2. Array Implementation of Queues 73\r\n 3.4.3. Applications of Queues 78\r\n Summary 79\r\n Exercises 79\r\n4 Trees 83\r\n 4.1. Preliminaries 83\r\n 4.1.1. Terminology 83\r\n 4.1.2. Tree Traversals with an Application 84\r\n 4.2. Binary Trees 85\r\n 4.2.1. Implementation 86\r\n 4.2.2. Expression Trees 87\r\n 4.2.3. Tree Traversals 90\r\n 4.3. The Search Tree ADT Binary Search Trees 97\r\n 4.3.1. MakeEmpty 97\r\n 4.3.2. Find 97\r\n 4.3.3. FindMin and FindMax 99\r\n 4.3.4. Insert 100\r\n 4.3.5. Delete 101\r\n 4.3.6. Average-Case Analysis 103\r\n 4.4. AVL Trees 106\r\n 4.4.1. Single Rotation 108\r\n 4.4.2. Double Rotation 111\r\n 4.5. Splay Trees 119\r\n 4.5.1. A Simple Idea (That Does Not Work) 12 0\r\n 4.5.2. Splaying 12 2\r\n 4.6. B-Trees 128\r\n Summary 133\r\n Exercises 134\r\n References 141\r\n5 Priority Queues (Heaps) 145\r\n 5.1. Model 145\r\n 5.2. Simple Implementations 146\r\n 5.3. Binary Heap 147\r\n 5.3.1. Structure Property 147\r\n 5.3.2. Heap Order Property 148\r\n 5.3.3. Basic Heap Operations 150\r\n 5.3.4. Other Heap Operations 154\r\n 5.4. Applications of Priority Queues 157\r\n 5.4.1. The Selection Problem 157\r\n 5.4.2. Event Simulation 159\r\n 5.5. d-Heaps 160\r\n 5.6. Leftist Heaps 161\r\n 5.6.1. Leftist Heap Property 161\r\n 5.6.2. Leftist Heap Operations 162\r\n 5.7. Skew Heaps 168\r\n 5.8. Binomial Queues 170\r\n 5.8.1. Binomial Queue Structure 170\r\n 5.8.2. Binomial Queue Operations 172\r\n 5.8.3. Implementation of Binomial Queues 173\r\n Summary 180\r\n Exercises 180\r\n References 184\r\n6 Sorting 187\r\n 6.1. Preliminaries 187\r\n 6.2. Insertion Sort 188\r\n 6.2.1. The Algorithm 188\r\n 6.2.2. Analysis of Insertion Sort 189\r\n 6.3. A Lower Bound for Simple Sorting Algorithms 189\r\n 6.4. Shellsort 190\r\n 6.4.1. Worst-Case Analysis of Shellsort 192\r\n 6.5. Heapsort 194\r\n 6.5.1. Analysis of Heapsort 196\r\n 6.6. Mergesort 198\r\n 6.6.1. Analysis of Mergesort 200\r\n 6.7. Quicksort 203\r\n 6.7.1. Picking the Pivot 204\r\n 6.7.2. Partitioning Strategy 205\r\n 6.7.3. Small Arrays 20 8\r\n 6.7.4. Actual Quicksort Routines 208\r\n 6.7.5. Analysis of Quicksort 209\r\n 6.7.6. A Linear-Expected-Time Algorithm for Selection 213\r\n 6.8. Sorting Large Structures 215\r\n 6.9. A General Lower Bound for Sorting 216\r\n 6.9.1. Decision Trees 217\r\n 6.10. Bucket Sort and Radix Sort 219\r\n 6.11. External Sorting 222\r\n 6.11.1. Why We Need New Algorithms 222\r\n 6.11.2. Model for External Sorting 222\r\n 6.11.3. The Simple Algorithm 222\r\n 6.11.4. Multiway Merge 224\r\n 6.11.5. Polyphase Merge 225\r\n 6.11.6. Replacement Selection 226\r\n Summary 227\r\n Exercises 229\r\n\r\n7 Hashing 235\r\n 7.1. General Idea 235\r\n 7.2. Hash Function 237\r\n 7.3. Separate Chaining 239\r\n 7.4. Open Addressing 244\r\n 7.4.1. Linear Probing 244\r\n 7.4.2. Quadratic Probing 247\r\n 7.4.3. Double Hashing 251\r\n 7.5. Rehashing 252\r\n 7.6. Extendible Hashing 255\r\n Summary 258\r\n Exercises 259\r\n References 262\r\n\r\n\r\n8 The Disjoint Set AnT 265\r\n 8.1. Equivalence Relations 265\r\n 8.2. The Dynamic Equivalence Problem 266\r\n 8.3. Basic Data Structure 267\r\n 8.4. Smart Union Algorithms 271\r\n 8.5. Path Compression 273\r\n 8.6. Worst Case for Union-by-Rank and Path Compression 275\r\n 8.6.1. Analysis of the Union/Find Algorithm 275\r\n 8.7. An Application 281\r\n Summary 281\r\n Exercises 282\r\n References 283\r\n\r\n\r\n9 Graph Algorithms 285\r\n 9.1. Definitions 285\r\n 9.1.1. Representation of Graphs 286\r\n 9.2. Topological Sort 288\r\n 9.3. Shortest-Path Algorithms 292\r\n 9.3.1. Unweighted Shortest Paths 293\r\n 9.3.2. Dijkstra''s Algorithm 297\r\n 9.3.3. Graphs with Negative Edge Costs 306\r\n 9.3.4. Acyclic Graphs 307\r\n 9.3.5. All-Pairs Shortest Path 310\r\n 9.4. Network Flow Problems 310\r\n 9.4.1. A Simple Maximum-Flow Algorithm 311\r\n 9.5. Minimum Spanning Tree 315\r\n 9.5.1. Prim''s Algorithm 316\r\n 9.5.2. Kruskal''s Algorithm 318\r\n 9.6. Applications of Depth-First Search 3:21\r\n 9.6.1. Undirected Graphs 322\r\n 9.6.2. Biconnectivity 324\r\n 9.6.3. Euler Circuits 328\r\n 9.6.4. Directed Graphs 331\r\n 9.6.5. Finding Strong Components 333\r\n 9.7. Introduction to NP-Completeness 334\r\n 9.7.2. The Class NP 336\r\n 9.7.3. NP-Complete Problems 337\r\n Summary 339\r\n Exercises 339\r\n References 345\r\n\r\n\r\n10 Algorithm Design Techniques 349\r\n 10.1. Greedy Algorithms 349\r\n 10.1.1. A Simple Scheduling Problem 350\r\n 10.1.2. Huffman Codes 353\r\n 10.1.3. Approximate Bin Packing 359\r\n 10.2. Divide and Conquer 367\r\n 10.2.1. Running Time of Divide and Conquer Algorithms 368\r\n 10.2.2. Closest-Points Problem 370\r\n 10.2.3. The Selection Problem 375\r\n 10.2.4. Theoretical Improvements for Arithmetic Problems 378\r\n 10.3. Dynamic Programming 382\r\n 10.3.1. Using a Table Instead of Recursion 382\r\n 10.3.2. Ordering Matrix Multiplications 385\r\n 10.3.3. Optimal Binary Search Tree 389\r\n 10.3.4. All-Pairs Shortest Path 392\r\n 10.4. Randomized Algorithms 394\r\n 10.4.1. Random Number Generators 396\r\n 10.4.2. Skip Lists 399\r\n 10.4.3. Primality Testing 401\r\n 10.5. Backtracking Algorithms 403\r\n 10.5.1. The Turnpike Reconstruction Problem 405\r\n 10.5.2. Games 407\r\n Summary 415\r\n Exercises 417\r\n References 424\r\n\r\n\r\nll Amortized Analysis 429\r\n 11.1. An Unrelated Puzzle 430\r\n 11.2. Binomial Queues 430\r\n 11.3. Skew Heaps 435\r\n 11.4. Fibonacci Heaps 437\r\n 11.4.1. Cutting Nodes in Leftist Heaps 430\r\n 11.4.2. Lazy Merging for Binomial Queues 441\r\n 11.4.3. The Fibonacci Heap Operations 444\r\n 11.4.4. Proof of the Time Bound 445\r\n 11.5. Splay Trees 447\r\n Summary 451\r\n Exercises 452\r\n References 453\r\n\r\n\r\n12 Advanced Data Structures and Implementation 455\r\n 12.1. Top-Down Splay Trees 455\r\n 12.2. Red Black Trees 459\r\n 12.2.1. Bottom-Up Insertion 464\r\n 12.2.2. Top-Down Red Black Trees 465\r\n 12.2.3. Top-Down Deletion 467\r\n 12.3. Deterministic Skip Lists 471\r\n 12.4. &A-Trees 478\r\n 12.5. Treaps 484\r\n 12.6. k-d Trees 487\r\n 12.7. Pairing Heaps 490\r\n Summary 496\r\n Exercises 497\r\n References 499

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