作者Robert Sedgewick and Kevin Wayne Princeton University
Preface . . . . . . . . . . . . . . . . . . . . . . . . .viii
1 Fundamentals . . . . . . . . . . . . . . . . . . . . . .3
1.1 Basic Programming Model 8
1.2 Data Abstraction 64
1.3 Bags, Queues, and Stacks 120
1.4 Analysis of Algorithms 172
1.5 Case Study: Union-Find 216
2 Sorting . . . . . . . . . . . . . . . . . . . . . . . 243
2.1 Elementary Sorts 244
2.2 Mergesort 270
2.3 Quicksort 288
2.4 Priority Queues 308
2.5 Applications 336
3 Searching . . . . . . . . . . . . . . . . . . . . . . 361
3.1 Symbol Tables 362
3.2 Binary Search Trees 396
3.3 Balanced Search Trees 424
3.4 Hash Tables 458
3.5 Applications 486
CONTENTS
vii
4 Graphs . . . . . . . . . . . . . . . . . . . . . . . 515
4.1 Undirected Graphs 518
4.2 Directed Graphs 566
4.3 Minimum Spanning Trees 604
4.4 Shortest Paths 638
5 Strings . . . . . . . . . . . . . . . . . . . . . . . 695
5.1 String Sorts 702
5.2 Tries 730
5.3 Substring Search 758
5.4 Regular Expressions 788
5.5 Data Compression 810
6 Context . . . . . . . . . . . . . . . . . . . . . . . 853
Index . . . . . . . . . . . . . . . . . . . . . . . . . 933
Algorithms . . . . . . . . . . . . . . . . . . . . . . 954
Clients . . . . . . . . . . . . . . . . . . . . . . . . 955
