Mark Allen Weiss教授撰写的数据结构与算法分析方面的著作曾被评为20世纪最佳的30部计算机著作之一，已经成为公认的经典之作，被全球数百所大学采用为教材，广受好评。

本书反映了Weiss教授在数据结构和算法分析教学实践方面的最新成果。书中从实践需要出发，采用主流的面向对象编程语言Java，在讲述了基本数据结构和算法之后，先通过几个贴近实际的实例讲授学生如何使用现成的数据结构来解决问题，有利于提高学生抽象思维能力，然后再透彻讲解Java集合类对各种数据结构的实现。既降低了学习难度，又增加了趣味性。

与此同时，本书仍然继承了Weiss著作数学严密、覆盖全面。选材精当、结构安排灵活以及习题丰富的优秀传统，适合读者自学和各种方式的课堂教学。

本书从讲解什么是数据结构开始，延伸至高级数据结构和算法分析，强调数据结构和问题求解技术。本书的目的是从抽象思维和问题求解的观点提供对数据结构的实用介绍，试图包含有关数据结构、算法分析及其Java实现的所有重要的细节。作者采用了独特的方法将数据结构分成说明和实现两部分，并充分利用了已有的数据结构库(Java集合类API)。本书分为4个部分：第一部分讨论适合大多数应用的集合类API的一个子集，并覆盖基本的算法分析技术、递归和排序算法；第二部分包含了一组集合类API的应用实例；第三部分讨论数据结构的实现；第四部分描述了高级的数据结构，如伸展树、偶堆和不相交集数据结构。

本书适合作为本科生数据结构课程或研究生算法分析课程的教材。教师可以灵活地选择本书的内容，选择最适合对应课程的内容授课。

part one　Algorithms and Building Blocks

chapter 1　algorithm analysis　3

1.1　what is algorithm analysis?　4

1.2　examples of algorithm running times　7

1.3　the maximum contiguous subsequence sum problem　8

1.3.1　the obvious O(N3) algorithm　9

1.3.2　an improved O(N2) algorithm　12

1.3.3　a linear algorithm　13

1.4　general big-oh rules　14

1.5　the logarithm　19

1.6　static searching problem　21

1.6.1　sequential search　21

1.6.2　binary search　21

1.6.3　interpolation search　24

1.7　checking an algorithm analysis　25

1.8　limitations of big-oh analysis　26

summary　27

key concepts　27

common errors　28

on the internet　28

exercises　29

references　34

chapter 2　the collections api　37

2.1　introduction　38

2.2　the iterator pattern　39

2.2.1　basic iterator design　40

2.2.2　inheritance-based iterators and factories　41

2.3　collections api: containers and iterators　43

2.3.1　the Collection interface　43

2.3.2　Iterator interface　46

2.4　generic algorithms　48

2.4.1　Comparator function objects　49

2.4.2　the Collections class　49

2.4.3　binary search　52

2.4.4　sorting　52

2.5　the List interface　52

2.5.1　the ListIterator interface　54

2.5.2　LinkedList class　55

2.6　stacks and queues　58

2.6.1　stacks　58

2.6.2　stacks and computer languages　59

2.6.3　queues　60

2.6.4　stacks and queues in the collections api　60

2.7　sets　61

2.7.1　the TreeSet class　62

2.7.2　the HashSet class　63

2.8　maps　68

2.9　priority queues　70

summary　73

key concepts　74

common errors　75

on the internet　75

exercises　76

references　79

chapter 3　recursion　81

3.1　what is recursion?　81

3.2　background: proofs by mathematical induction　82

3.3　basic recursion　84

3.3.1　printing numbers in any base　86

3.3.2　why it works　88

3.3.3　how it works　89

3.3.4　too much recursion can be dangerous　90

3.3.5　preview of trees　91

3.3.6　additional examples　92

3.4　numerical applications　96

3.4.1　modular arithmetic　97

3.4.2　modular exponentiation　98

3.4.3　greatest common divisor and multiplicative inverses　99

3.4.4　the rsa cryptosystem　101

3.5　divide-and-conquer algorithms　103

3.5.1　the maximum contiguous subsequence sum problem　104

3.5.2　analysis of a basic divide-and-conquer recurrence　107

3.5.3　a general upper bound for divide-and-conquer running times　110

3.6　dynamic programming　112

3.7　backtracking　116

summary　119

key concepts　120

common errors　121

on the internet　121

exercises　122

references　126

chapter 4　sorting algorithms　127

4.1　why is sorting important?　128

4.2　preliminaries　129

4.3　analysis of the insertion sort and other simple sorts　129

4.4　shellsort　132

4.4.1　performance of shellsort　134

4.5　mergesort　135

4.5.1　linear-time merging of sorted arrays　136

4.5.2　the mergesort algorithm　137

4.6　quicksort　139

4.6.1　the quicksort algorithm　140

4.6.2　analysis of quicksort　142

4.6.3　picking the pivot　145

4.6.4　a partitioning strategy　146

4.6.5　keys equal to the pivot　148

4.6.6　median-of-three partitioning　148

4.6.7　small arrays　149

4.6.8　java quicksort routine　150

4.7　quickselect　152

4.8　a lower bound for sorting　154

summary　155

key concepts　155

common errors　156

on the internet　156

exercises　156

references　160

chapter 5　randomization　161

5.1　why do we need random numbers?　161

5.2　random number generators　162

5.3　nonuniform random numbers　167

5.4　generating a random permutation　169

5.5　randomized algorithms　170

5.6　randomized primality testing　173

summary　176

key concepts　176

common errors　177

on the internet　178

exercises　178

references　180

part two　Applicat ions

chapter 6　fun and games　183

6.1　word search puzzles　183

6.1.1　theory　184

6.1.2　java implementation　185

6.2　the game of tic-tac-toe　189

6.2.1　alpha-beta pruning　189

6.2.2　transposition tables　192

6.2.3　computer chess　197

summary　198

key concepts　198

common errors　198

on the internet　198

exercises　199

references　200

chapter 7　stacks and compilers　201

7.1　balanced-symbol checker　201

7.1.1　basic algorithm　202

7.1.2　implementation　203

7.2 a　simple calculator　212

7.2.1　postfix machines　213

7.2.2　infix to postfix conversion　213

7.2.3　implementation　216

7.2.4　expression trees　222

summary　224

key concepts　225

common errors　225

on the internet　225

exercises　226

references　227

chapter 8　utilities　229

8.1　file compression　229

8.1.1　prefix codes　230

8.1.2　huffman's algorithm　232

8.1.3　implementation　235

8.2 a　cross-reference generator　248

8.2.1　basic ideas　248

8.2.2　java implementation　248

summary　252

key concepts　252

common errors　253

on the internet　253

exercises　253

references　256

chapter 9　simulation　257

9.1　the josephus problem　257

9.1.1　the simple solution　258

9.1.2　a more efficient algorithm　260

9.2　event-driven simulation　261

9.2.1　basic ideas　261

9.2.2　example: a modem bank simulation　263

summary　270

key concepts　270

common errors　271

on the internet　271

exercises　271

chapter 10　graphs and paths　273

10.1　definitions　273

10.1.1　representation　275

10.2　unweighted shortest-path problem　285

10.2.1　theory　286

10.2.2　java implementation　289

10.3　positive-weighted, shortest-path problem　289

10.3.1　theory: dijkstra's algorithm　290

10.3.2　java implementation　294

10.4　negative-weighted, shortest-path problem　296

10.4.1　theory　296

10.4.2　java implementation　297

10.5　path problems in acyclic graphs　297

10.5.1　topological sorting　297

10.5.2　theory of the acyclic shortest-path algorithm　299

10.5.3　java implementation　301

10.5.4　an application: critical-path analysis　303

summary　305

key concepts　306

common errors　307

on the internet　307

exercises　308

references　311

part three　Implementat ions

chapter 11　inner classes and implementation of ArrayList　315

11.1　iterators and nested classes　315

11.2　iterators and inner classes　318

11.3　the AbstractCollection class　321

11.4　StringBuilder　322

11.5　implementation of ArrayList with an iterator　325

summary　330

key concepts　331

common errors　331

on the internet　331

exercises　331

chapter 12　stacks and queues　335

12.1　dynamic array implementations　335

12.1.1　stacks　335

12.1.2　queues　339

12.2　linked list implementations　344

12.2.1　stacks　345

12.2.2　queues　347

12.3　comparison of the two methods　351

12.4　the java.util.Stack class　351

12.5　double-ended queues　351

summary　353

key concepts　353

common errors　353

on the internet　353

exercises　353

chapter 13　linked lists　355

13.1　basic ideas　355

13.1.1　header nodes　357

13.1.2　iterator classes　358

13.2　java implementation　359

13.3　doubly linked lists and circularly linked lists　365

13.4　sorted linked lists　367

13.5　implementing the collections api LinkedList class　369

summary　379

key concepts　379

common errors　380

on the internet　380

exercises　380

chapter 14　trees　385

14.1　general trees　385

14.1.1　definitions　385

14.1.2　implementation　387

14.1.3　an application: file systems　387

14.2　binary trees　391

14.3　recursion and trees　397

14.4　tree traversal: iterator classes　399

14.4.1　postorder traversal　403

14.4.2　inorder traversal　406

14.4.3　preorder traversal　408

14.4.4　level-order traversals　408

summary　411

key concepts　412

common errors　412

on the internet　413

exercises　413

chapter 15　binary search trees　417

15.1　basic ideas　417

15.1.1　the operations　418

15.1.2　java implementation　419

15.2　order statistics　426

15.2.1　java implementation　427

15.3　analysis of binary search tree operations　431

15.4　avl trees　434

15.4.1　properties　434

15.4.2　single rotation　437

15.4.3　double rotation　439

15.4.4　summary of avl insertion　441

15.5　red-black trees　442

15.5.1　bottom-up insertion　443

15.5.2　top-down red-black trees　444

15.5.3　java implementation　446

15.5.4　top-down deletion　450

15.6　aa-trees　454

15.6.1　insertion　455

15.6.2　deletion　457

15.6.3　java implementation　458

15.7　implementing the collections api TreeSet and TreeMap classes　463

15.8　b-trees　479

summary　485

key concepts　486

common errors　487

on the internet　487

exercises　488

references　490

chapter 16　hash tables　493

16.1　basic ideas　493

16.2　hash function　494

16.3　linear probing　497

16.3.1　naive analysis of linear probing　498

16.3.2　what really happens: primary clustering　499

16.3.3　analysis of the find operation　500

16.4　quadratic probing　502

16.4.1　java implementation　505

16.4.2　analysis of quadratic probing　510

16.5　separate chaining hashing　514

16.6　hash tables versus binary search trees　514

16.7　hashing applications　515

summary　515

key concepts　516

common errors　516

on the internet　517

exercises　517

references　519

chapter 17　a priority queue: the binary heap　521

17.1　basic ideas　521

17.1.1　structure property　522

17.1.2　heap-order property　523

17.1.3　allowed operations　524

17.2　implementation of the basic operations　527

17.2.1　insertion　527

17.2.2　the deleteMin operation　529

17.3　the buildHeap operation: linear-time heap construction　531

17.4　advanced operations: decreaseKey and merge　535

17.5　internal sorting: heapsort　535

17.6　external sorting　538

17.6.1　why we need new algorithms　538

17.6.2　model for external sorting　539

17.6.3　the simple algorithm　539

17.6.4　multiway merge　541

17.6.5　polyphase merge　542

17.6.6　replacement selection　543

summary　544

key concepts　545

common errors　545

on the internet　546

exercises　546

references　549

part four　Advanced Data Struct ures

chapter 18　splay trees　553

18.1　self-adjustment and amortized analysis　553

18.1.1　amortized time bounds　554

18.1.2　a simple self-adjusting strategy (that does not work)　555

18.2　the basic bottom-up splay tree　557

18.3　basic splay tree operations　559

18.4　analysis of bottom-up splaying　560

18.4.1　proof of the splaying bound　562

18.5　top-down splay trees　565

18.6　implementation of top-down splay trees　567

18.7　comparison of the splay tree with other search trees　573

summary　573

key concepts　574

common errors　574

on the internet　574

exercises　575

references　576

chapter 19　merging priority queues　577

19.1　the skew heap　577

19.1.1　merging is fundamental　577

19.1.2　simplistic merging of heap-ordered trees　578

19.1.3　the skew heap: a simple modification　579

19.1.4　analysis of the skew heap　580

19.2　the pairing heap　582

19.2.1　pairing heap operations　582

19.2.2　implementation of the pairing heap　583

19.2.3　application: dijkstra's shortest weighted path algorithm　591

summary　592

key concepts　592

common errors　593

on the internet　593

exercises　593

references　594

chapter 20　the disjoint set class　595

20.1　equivalence relations　595

20.2　dynamic equivalence and applications　596

20.2.1　application: generating mazes　597

20.2.2　application: minimum spanning trees　599

20.2.3　application: the nearest common ancestor problem　602

20.3　the quick-find algorithm　605

20.4　the quick-union algorithm　606

20.4.1　smart union algorithms　607

20.4.2　path compression　609

20.5　java implementation　610

20.6　worst case for union-by-rank and path compression　610

20.6.1　analysis of the union/find algorithm　613

summary　619

key concepts　619

common errors　620

on the internet　620

exercises　621

references　623

appendix A　operators　625

appendix B　bitwise operators　627