本书通过C程序的实现，着重阐述了抽象数据类型的概念，并对算法的效率、性能和运行时间进行了分析。讨论了算法设计技巧，当前流行的论题和新的数据结构，以及高级数据结构及其实现。

本书曾被评为20世纪顶尖的30部计算机著作之一，作者在数据结构和算法分析方面卓有建树，他的数据结构和算法分析的著作尤其畅销，并受到广泛好评，已被世界500余所大学选作教材。
在本书中，作者精炼并强化了他对算法和数据结构方面创新的处理方法。通过C程序的实现，着重阐述了抽象数据类型的概念，并对算法的效率、性能和运行时间进行了分析。
本书特色
着重讨论了算法设计技巧，包括贪婪算法、分治算法、动态规划、随机化算法以及回溯算法。
系统介绍了当前流行的论题和新的数据结构，如斐波那契堆、斜堆、二项队列、跳跃表和伸展树。
详细讨论了摊还分析，考查书中介绍的一些高级数据结构。
增加了高级数据结构及其实现的内容，包括红黑树、自顶向下伸展树、treap树、k-d树、配对堆等。
整合了堆排序平均情况分析的一些新结果。
作者简介
Mark Allen Weiss　1987年在普林斯顿大学获得计算机科学博士学位，师从Robert Sedgewick，现任美国佛罗里达国际大学计算与信息科学学院教授。他曾担任全美AP(Advanced Placement)考试计算机学科委员会主席。其主要研究方向是数据结构、算法和教育学。

计算机\数据结构

本书曾被评为20世纪顶尖的30部计算机著作之一，作者在数据结构和算法分析方面卓有建树，他的数据结构和算法分析的著作尤其畅销，并受到广泛好评，已被世界500余所大学选作教材。
　　在本书中，作者精炼并强化了他对算法和数据结构方面创新的处理方法。通过C程序的实现，着重阐述了抽象数据类型的概念，并对算法的效率、性能和运行时间进行了分析。
　　本书特色
　　●着重讨论算法设计技巧，包括贪婪算法、分治算法、动态规划、随机化算法以及回溯算法。
　　●系统介绍当前流行的论题和新的数据结构，如斐波那契堆、斜堆、二项队列、跳跃表和伸展树。
　　●详细讨论了摊还分析，考查书中介绍的一些高级数据结构。
　　●增加了高级数据结构及其实现的内容，包括红黑树、自顶向下伸展树、treap树、k-d树、配对堆等。
　　●整合了堆排序平均情况分析的一些新结果。

（美）Mark Allen Weiss 著：Mark Allen Weiss 1987年在普林斯顿大学获得计算机科学博士学位，师从Robert Sedgewick，现任美国佛罗里达国际大学计算与信息科学学院教授。他曾担任全美AP(Advanced Placement)考试计算机学科委员会的主席(2000-2004年)。其主要研究方向是数据结构、算法和教育学。

Introduction 1
1.1. Whats the Book About 1
1.2. Mathematics Review 3
1.2.1. Exponents 3
1.2.2. Logarithms 3
1.2.3. Series 4
1.2.4. Modular Arithmetic 5
1.2.5. The P Word 6
1.3. A Brief Introduction to Recursion
Summary 12
Exercises 12
References 13

2 Algorithm Analysis 15
2.1. Mathematical Background 15
2.2. Model 18
2.3. What to Analyze 18
2.4. Running Tune Calculations 20
2.4.1. A Simple Example 21
2.4.2. General Rules 21
2.4.3. Solutions for the Maximum Subsequence Sum Problem 24
2.4.4. Logarithms in the Running Tune 28
2.4.5. Checking Your Analysis 33
2.4.6. A Grain of Salt 33
Summary 34
Exercises 35
References 39

3 Lists, Stacks, and Queues 41
3.1. Abstract Data Types (AnTs) 41
3.2. The List ADT 42
3.2.1. Simple Array Implementation of Lists 43
3.2.2. Linked Lists 43
3.2.3. Programming Details 44
3.2.4. Common Errors 49
3.2.5. Doubly Linked Lists 51
3.2.6. Circularly Unked Lists 52
3.2.7. Examples 52
3.2.8. Cursor Implementation of Linked Lists 57
3.3. The Stack ADT 62
3.3.1. Stack Model 62
3.3.2. Implementation of Stacks 63
3.3.3. Applications 71
3.4. The Queue ADT 79
3.4.1. Queue Model 79
3.4.2. Array Implementation of Queues 79
3.4.3. Applications of Queues 84
Summary 85
Exercises 85

4 Trees 89
4.1. Preliminaries 89
4.1.1. Implementation of Trees 90
4.1.2. Tree Traversals with an Application 91
4.2. Binary Trees 95
4.2.1. Implementation 96
4.2.2. Expression Trees 97
4.3. The Search Tree ADT-Binary Search Trees 100
4.3.1. MakeEmpty 101
4.3.2. Find 101
4.3.3. FindMin and FindMax 103
4.3.4. Insert 104
4.3.5. Delete 105
4.3.6. Average-Case Analysis 107
4.4. AvI Trees 110
4.4.1. Single Rotation 112
4.4.2. Double Rotation 115
4.5. Splay Trees 123
4.5.1. A Simple Idea (That Does Not Work) 124
4.5.2. Splaying 126
4.6. Tree Traversals (Revisited) 132
4.7. B-Trees 133
Summary 138
Exercises 139
References 146

5 Hashing 149
5.1. General Idea 149
5.2. Hash Function 150
5.3. Separate Chaining 152
5.4. Open Addressing 157
5.4.1. Linear Probing 157
5.4.2. Quadratic Probing 160
5.4.3. Double Hashing 164
5.5. Rehashing 165
5.6. Extendible Hashing 168
Summary 171
Exercises 172
References 175

6 Priority Queues (Heaps) 177
6.1. Model 177
6.2. Simple Implementations 178
6.3. Binary Heap 179
6.3.1. Strocture Property 179
6.3.2. Heap Order Property 180
6.3.3. Basic Heap Operations 182
6.3.4. Other Heap Operations 186
6.4. Applications of Priority Queues 189
6.4.1. The Selection Problem 189
6.4.2. Event Simulation 191
6.5. d-Heaps 192
6.6. Leftist Heaps 193
6.6.1. Leftist Heap Properly 193
6.6.2. Leftist Heap Operations 194
6.7. Skew Heaps 200
6.8. Binomial Queues 202
6.8.1. Binomial Queue Structure 202
6.8.2. Binomial Queue Operations 204
6.8.3. Implementation of Binomial Queues 205
Summary 212
Exercises 212
References 216

7 Sorting 219
7.1. Preliminaries 219
7.2. Insertion Sort 220
7.2.1. The Algorithm 220
7.2.2. Analysis of Insertion Sort 221
7.3. A Lower Bound for Simple Sorting Algorithms 221
7.4. SheUsort 222
7.4.1. Worst-Case Analysis of Shellsort 224
7.5. Heapsort 226
7.5.1. Analysis of Heapsort 228
7.6. Mergesort 230
7.6.1. Analysis of Mergesort 232
7.7. Quicksort 235
7.7.1. Picking the Pivot 236
7.7.2. Partitioning Strategy 237
7.7.3. Small Arrays 240
7.7.4. Actual Quicksort Routines 240
7.7.5. Analysis of Quicksort 241
7.7.6. A Linear-Expected-Time Algorithm for Selection 245
7.8. Sorting Large Structures 247
7.9. A General Lower Bound for Sorting 247
7.9.1. Decision Trees 247
7.10. Bucket Sort 250
7.11. External Sorting 250
7.11.1. Why We Need New Algorithms 251
7.11.2. Model for External Sorting 251
……
8 The Disjoint Set ADT
9 Graph Algorithms
10 Algorithm Design Techniques
11 Amortized Analysis
12 Advanced Data Structures and Implementation