数据结构与算法分析——Java语言描述（英文版·第3版）—

同系列书

相关图书

图书详情

装订：平装

编辑：姚蕾

开本：16(B5)

出版日期： 2013-02-27

字数：500 千字

最新版印次：1-9

最新印次时间：2025-12-25

定价：79.0

cip：2013012558

中图法分类：TP311.12；TP312

图书简介

本书是国外数据结构与算法分析方面的经典教材，使用卓越的Java编程语言作为实现工具讨论了数据结构（组织大量数据的方法）和算法分析（对算法运行时间的估计）。本书把算法分析与最有效率的Java程序的开发有机地结合起来，深入分析每种算法，内容全面、缜密严格，并细致讲解精心构造程序的方法。

章节目录

Preface v 
Chapter 1 Introduction 1 
1.1 What’s the Book About? 1 
1.2 Mathematics Review 2 
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 8 
1.4 Implementing Generic Components Pre-Java 5 12 
1.4.1 Using Object for Genericity 13 
1.4.2 Wrappers for Primitive Types 14 
1.4.3 Using Interface Types for Genericity 14 
1.4.4 Compatibility of Array Types 16 
1.5 Implementing Generic Components Using Java 5 Generics 16 
1.5.1 Simple Generic Classes and Interfaces 17 
1.5.2 Autoboxing/Unboxing 18 
1.5.3 The Diamond Operator 18 
1.5.4 Wildcards with Bounds 19 
1.5.5 Generic Static Methods 20 
1.5.6 Type Bounds 21 
1.5.7 Type Erasure 22 
1.5.8 Restrictions on Generics 23 
1.6 Function Objects 24 
Summary 26 
Exercises 26 
References 28 
Chapter 2 Algorithm Analysis 29 
2.1 Mathematical Background 29 
2.2 Model 32 
2.3 What to Analyze 33 
2.4 Running Time Calculations 35 
2.4.1 A Simple Example 36 
2.4.2 General Rules 36 
2.4.3 Solutions for the Maximum Subsequence Sum Problem 39 
2.4.4 Logarithms in the Running Time 45 
2.4.5 A Grain of Salt 49 
Summary 49 
Exercises 50 
References 55 
Chapter 3 Lists, Stacks, and Queues 57 
3.1 Abstract Data Types (ADTs) 57 
3.2 The List ADT 58 
3.2.1 Simple Array Implementation of Lists 58 
3.2.2 Simple Linked Lists 59 
3.3 Lists in the Java Collections API 61 
3.3.1 Collection Interface 61 
3.3.2 Iterator s 61 
3.3.3 The List Interface, ArrayList, and LinkedList 63 
3.3.4 Example: Using remove on a LinkedList 65 
3.3.5 ListIterators 67 
3.4 Implementation of ArrayList 67 
3.4.1 The Basic Class 68 
3.4.2 The Iterator and Java Nested and Inner Classes 71 
3.5 Implementation of LinkedList 75 
3.6 The Stack ADT 82 
3.6.1 Stack Model 82 
3.6.2 Implementation of Stacks 83 
3.6.3 Applications 84 
3.7 The Queue ADT 92 
3.7.1 Queue Model 92 
3.7.2 Array Implementation of Queues 92 
3.7.3 Applications of Queues 95 
Summary 96 
Exercises 96 
Chapter 4 Trees 101 
4.1 Preliminaries 101 
4.1.1 Implementation of Trees 102 
4.1.2 Tree Traversals with an Application 103 
4.2 Binary Trees 107 
4.2.1 Implementation 108 
4.2.2 An Example: Expression Trees 109 
4.3 The Search Tree ADT—Binary Search Trees 112 
4.3.1 contains 113 
4.3.2 findMin and findMax 115 
4.3.3 insert 116 
4.3.4 remove 118 
4.3.5 Average-Case Analysis 120 
4.4 AVL Trees 123 
4.4.1 Single Rotation 125 
4.4.2 Double Rotation 128 
4.5 Splay Trees 137 
4.5.1 A Simple Idea (That Does Not Work) 137 
4.5.2 Splaying 139 
4.6 Tree Traversals (Revisited) 145 
4.7 B-Trees 147 
4.8 Sets and Maps in the Standard Library 152 
4.8.1 Sets 152 
4.8.2 Maps 153 
4.8.3 Implementation of TreeSet and TreeMap 153 
4.8.4 An Example That Uses Several Maps 154 
Summary 160 
Exercises 160 
References 167 
Chapter 5 Hashing 171 
5.1 General Idea 171 
5.2 Hash Function 172 
5.3 Separate Chaining 174 
5.4 Hash Tables Without Linked Lists 179 
5.4.1 Linear Probing 179 
5.4.2 Quadratic Probing 181 
5.4.3 Double Hashing 183 
5.5 Rehashing 188 
5.6 Hash Tables in the Standard Library 189 
5.7 Hash Tables with Worst-Case O(1) Access 192 
5.7.1 Perfect Hashing 193 
5.7.2 Cuckoo Hashing 195 
5.7.3 Hopscotch Hashing 205 
5.8 Universal Hashing 211 
5.9 Extendible Hashing 214 
Summary 217 
Exercises 218 
References 222 
Chapter 6 Priority Queues (Heaps) 225 
6.1 Model 225 
6.2 Simple Implementations 226 
6.3 Binary Heap 226 
6.3.1 Structure Property 227 
6.3.2 Heap-Order Property 229 
6.3.3 Basic Heap Operations 229 
6.3.4 Other Heap Operations 234 
6.4 Applications of Priority Queues 238 
6.4.1 The Selection Problem 238 
6.4.2 Event Simulation 239 
6.5 d-Heaps 240 
6.6 Leftist Heaps 241 
6.6.1 Leftist Heap Property 241 
6.6.2 Leftist Heap Operations 242 
6.7 Skew Heaps 249 
6.8 Binomial Queues 252 
6.8.1 Binomial Queue Structure 252 
6.8.2 Binomial Queue Operations 253 
6.8.3 Implementation of Binomial Queues 256 
6.9 Priority Queues in the Standard Library 261 
Summary 261 
Exercises 263 
References 267 
Chapter 7 Sorting 271 
7.1 Preliminaries 271 
7.2 Insertion Sort 272 
7.2.1 The Algorithm 272 
7.2.2 Analysis of Insertion Sort 272 
7.3 A Lower Bound for Simple Sorting Algorithms 273 
7.4 Shellsort 274 
7.4.1 Worst-Case Analysis of Shellsort 276 
7.5 Heapsort 278 
7.5.1 Analysis of Heapsort 279 
7.6 Mergesort 282 
7.6.1 Analysis of Mergesort 284 
7.7 Quicksort 288 
7.7.1 Picking the Pivot 290 
7.7.2 Partitioning Strategy 292 
7.7.3 Small Arrays 294 
7.7.4 Actual Quicksort Routines 294 
7.7.5 Analysis of Quicksort 297 
7.7.6 A Linear-Expected-Time Algorithm for Selection 300 
7.8 A General Lower Bound for Sorting 302 
7.8.1 Decision Trees 302 
7.9 Decision-Tree Lower Bounds for Selection Problems 304 
7.10　 Adversary Lower Bounds 307 
7.11　 Linear-Time Sorts: Bucket Sort and Radix Sort 310 
7.12　 External Sorting 315 
7.12.1　 Why We Need New Algorithms 316 
7.12.2　 Model for External Sorting 316 
7.12.3　 The Simple Algorithm 316 
7.12.4　 Multiway Merge 317 
7.12.5　 Polyphase Merge 318 
7.12.6　 Replacement Selection 319 
Summary 321 
Exercises 321 
References 327 
Chapter 8 The Disjoint Set Class 331 
8.1 Equivalence Relations 331 
8.2 The Dynamic Equivalence Problem 332 
8.3 Basic Data Structure 333 
8.4 Smart Union Algorithms 337 
8.5 Path Compression 340 
8.6 Worst Case for Union-by-Rank and Path Compression 341 
8.6.1 Slowly Growing Functions 342 
8.6.2 An Analysis By Recursive Decomposition 343 
8.6.3 An O( M log * N ) Bound 350 
8.6.4 An O( M α(M, N) ) Bound 350 
8.7 An Application 352 
Summary 355 
Exercises 355 
References 357 
Chapter 9 Graph Algorithms 359 
9.1 Definitions 359 
9.1.1 Representation of Graphs 360 
9.2 Topological Sort 362 
9.3 Shortest-Path Algorithms 366 
9.3.1 Unweighted Shortest Paths 367 
9.3.2 Dijkstra’s Algorithm 372 
9.3.3 Graphs with Negative Edge Costs 380 
9.3.4 Acyclic Graphs 380 
9.3.5 All-Pairs Shortest Path 384 
9.3.6 Shortest-Path Example 384 
9.4 Network Flow Problems 386 
9.4.1 A Simple Maximum-Flow Algorithm 388 
9.5 Minimum Spanning Tree 393 
9.5.1 Prim’s Algorithm 394 
9.5.2 Kruskal’s Algorithm 397 
9.6 Applications of Depth-First Search 399 
9.6.1 Undirected Graphs 400 
9.6.2 Biconnectivity 402 
9.6.3 Euler Circuits 405 
9.6.4 Directed Graphs 409 
9.6.5 Finding Strong Components 411 
9.7 Introduction to NP-Completeness 412 
9.7.1 Easy vs. Hard 413 
9.7.2 The Class NP 414 
9.7.3 NP-Complete Problems 415 
Summary 417 
Exercises 417 
References 425 
Chapter 10 Algorithm Design Techniques 429 
10.1　 Greedy Algorithms 429 
10.1.1　 A Simple Scheduling Problem 430 
10.1.2　 Huffman Codes 433 
10.1.3　 Approximate Bin Packing 439 
10.2　 Divide and Conquer 448 
10.2.1　 Running Time of Divide-and-Conquer Algorithms 449 
10.2.2　 Closest-Points Problem 451 
10.2.3　 The Selection Problem 455 
10.2.4　 Theoretical Improvements for Arithmetic Problems 458 
10.3　 Dynamic Programming 462 
10.3.1　 Using a Table Instead of Recursion 463 
10.3.2　 Ordering Matrix Multiplications 466 
10.3.3　 Optimal Binary Search Tree 469 
10.3.4　 All-Pairs Shortest Path 472 
10.4　 Randomized Algorithms 474 
10.4.1　 Random Number Generators 476 
10.4.2　 Skip Lists 480 
10.4.3　 Primality Testing 483 
10.5　 Backtracking Algorithms 486 
10.5.1　 The Turnpike Reconstruction Problem 487 
10.5.2　 Games 490 
Summary 499 
Exercises 499 
References 508 
Chapter 11 Amortized Analysis 513 
11.1　 An Unrelated Puzzle 514 
11.2　 Binomial Queues 514 
11.3　 Skew Heaps 519 
11.4　 Fibonacci Heaps 522 
11.4.1　 Cutting Nodes in Leftist Heaps 522 
11.4.2　 Lazy Merging for Binomial Queues 525 
11.4.3　 The Fibonacci Heap Operations 528 
11.4.4　 Proof of the Time Bound 529 
11.5　 Splay Trees 531 
Summary 536 
Exercises 536 
References 538 
Chapter 12 Advanced Data Structures and Implementation 541 
12.1　 Top-Down Splay Trees 541 
12.2　 Red-Black Trees 549 
12.2.1　 Bottom-Up Insertion 549 
12.2.2　 Top-Down Red-Black Trees 551 
12.2.3　 Top-Down Deletion 556 
12.3　 Treaps 558 
12.4　 Suffix Arrays and Suffix Trees 560 
<span style="font-family:宋体;line-height:21.6px;white-space:normal

图书评论

图书简介
章节目录
图书评论