数据结构与问题求解 Java语言版 英文版PDF电子书下载

part one Tour of Java 3

Chapter 1 Primitive java 3

1.1 the general environment 4

1.2 the first program 5

1.2.1 comments 5

1.2.2 main 6

1.2.3 terminal output 6

1.3 primitive types 6

1.3.1 the primitive types 6

1.3.2 constants 7

1.3.3 declaration and initialization of primitive types 7

1.3.4 terminal input and output 8

1.4 basic operators 8

1.4.1 assignment operators 9

1.4.2 binary arithmetic operators 10

1.4.3 unary operators 10

1.4.4 type conversions 10

1.5 conditional statements 11

1.5.1 relational and equality operators 11

1.5.2 logical operators 12

1.5.3 the if statement 13

1.5.4 the while statement 14

1.5.5 the for statement 14

1.5.6 the do statement 15

1.5.7 break and continue 16

1.5.8 the switch statement 17

1.5.9 the conditional operator 17

1.6 methods 18

1.6.1 overloading of method names 19

1.6.2 storage classes 20

summary 20

key concepts 20

common errors 22

on the internet 23

exercises 23

references 25

Chapter 2 reference types 27

2.1 what is a reference? 27

2.2 basics of objects and references 30

2.2.1 the dot operator(.) 30

2.2.2 declaration of objects 30

2.2.3 garbage collection 31

2.2.4 the meaning of= 32

2.2.5 parameter passing 33

2.2.6 the meaning of== 33

2.2.7 no operator overloading for objects 34

2.3 strings 35

2.3.1 basics of string manipulation 35

2.3.2 string concatenation 35

2.3.3 comparing strings 36

2.3.4 other String methods 36

2.3.5 converting other types to strings 37

2.4 arrays 37

2.4.1 declaration,assignment,and methods 38

2.4.2 dynamic array expansion 40

2.4.3 ArrayList 42

2.4.4 multidimensional arrays 45

2.4.5 command-line arguments 45

2.4.6 enhanced for loop 46

2.5 exception handling 47

2.5.1 processing exceptions 48

2.5.2 the finally clause 48

2.5.3 common exceptions 49

2.5.4 the throw and throws clauses 51

2.6 input and output 51

2.6.1 basic stream operations 52

2.6.2 the Scanner type 53

2.6.3 sequential files 56

summary 59

key concepts 60

common errors 61

on the internet 62

exercises 62

references 68

Chapter 3 objects and classes 69

3.1 what is object-oriented programming? 69

3.2 a simple example 71

3.3 javadoc 73

3.4 basic methods 76

3.4.1 constructors 76

3.4.2 mutators and accessors 76

3.4.3 output and toString 78

3.4.4 equals 78

3.4.5 main 78

3.5 example:using java.math.BigInteger 78

3.6 additional constructs 79

3.6.1 the this reference 81

3.6.2 the this shorthand for constructors 82

3.6.3 the instanceof operator 82

3.6.4 instance members versus static members 83

3.6.5 static fields and methods 83

3.6.6 static initializers 86

3.7 example:implementing a BigRational class 86

3.8 packages 90

3.8.1 the import directive 91

3.8.2 the package statement 93

3.8.3 the CLASSPATH environment variable 94

3.8.4 package visibility rules 95

3.9 a design pattern:composite(pair) 95

summary 96

key concepts 97

common errors 100

on the internet 100

exercises 101

references 107

Chapter 4 inheritance 109

4.1 what is inheritance? 110

4.1.1 creating new classes 110

4.1.2 type compatibility 115

4.1.3 dynamic dispatch and polymorphism 116

4.1.4 inheritance hierarchies 117

4.1.5 visibility rules 117

4.1.6 the constructor and super 118

4.1.7 final methods and classes 119

4.1.8 overriding a method 121

4.1.9 type compatibility revisited 121

4.1.10 compatibility of array types 124

4.1.11 covariant return types 124

4.2 designing hierarchies 125

4.2.1 abstract methods and classes 126

4.2.2 designing for the future 130

4.3 multiple inheritance 131

4.4 the interface 134

4.4.1 specifying an interface 134

4.4.2 implementing an interface 135

4.4.3 multiple interfaces 135

4.4.4 interfaces are abstract classes 136

4.5 fundamental inheritance in java 136

4.5.1 the Object class 136

4.5.2 the hierarchy of exceptions 137

4.5.3 i/o:the decorator pattern 138

4.6 implementing generic components using inheritance 142

4.6.1 using Object for genericity 142

4.6.2 wrappers for primitive types 143

4.6.3 autoboxing/unboxing 145

4.6.4 adapters:changing an interface 146

4.6.5 using interface types for genericity 147

4.7 implementing generic components using java 5 generics 150

4.7.1 simple generic classes and interfaces 150

4.7.2 wildcards with bounds 151

4.7.3 generic static methods 152

4.7.4 type bounds 153

4.7.5 type erasure 154

4.7.6 restrictions on generics 154

4.8 the functor(function objects) 157

4.8.1 nested classes 161

4.8.2 local classes 161

4.8.3 anonymous classes 163

4.8.4 nested classes and generics 164

4.9 dynamic dispatch details 164

summary 168

key concepts 168

common errors 171

on the internet 171

exercises 173

references 183

part two Algorithms and Building BlocksChapter 5 algorithm analysis 187

5.1 what is algorithm analysis? 188

5.2 examples of algorithm running times 192

5.3 the maximum contiguous subsequence sum problem 193

5.3.1 the obvious O(N3)algorithm 194

5.3.2 an improved O(N2)algorithm 197

5.3.3 a linear algorithm 197

5.4 general big-oh rules 201

5.5 the logarithm 205

5.6 static searching problem 207

5.6.1 sequential search 207

5.6.2 binary search 208

5.6.3 interpolation search 211

5.7 checking an algorithm analysis 212

5.8 limitations of big-oh analysis 213

summary 214

key concepts 214

common errors 215

on the internet 216

exercises 216

references 227

Chapter 6 the collections api 229

6.1 introduction 230

6.2 the iterator pattern 231

6.2.1 basic iterator design 232

6.2.2 inheritance-based iterators and factories 234

6.3 collections api:containers and iterators 236

6.3.1 the Collecti on interface 237

6.3.2 Iterator interface 240

6.4 generic algorithms 242

6.4.1 Comparator function objects 243

6.4.2 the Collections class 243

6.4.3 binary search 246

6.4.4 sorting 246

6.5 the List interface 248

6.5.1 the ListIterator interface 249

6.5.2 LinkedList class 251

6.5.3 running time for Lists 253

6.5.4 removing from and adding to the middle of a List 256

6.6 stacks and queues 258

6.6.1 stacks 258

6.6.2 stacks and computer languages 259

6.6.3 queues 260

6.6.4 stacks and queues in the collections api 261

6.7 sets 261

6.7.1 the TreeSet class 263

6.7.2 the HashSet class 264

6.8 maps 268

6.9 priority queues 274

6.10 views in the collections api 277

6.10.1 the subList method for Lists 277

6.10.2 the headSet,subSet,and tailSet methods for SortedSets 277

summary 278

key concepts 279

common errors 280

on the internet 281

exercises 281

references 292

Chapter 7 recursion 293

7.1 what is recursion? 294

7.2 background:proofs by mathematical induction 295

7.3 basic recursion 297

7.3.1 printing numbers in any base 299

7.3.2 why it works 301

7.3.3 how it works 302

7.3.4 too much recursion can be dangerous 304

7.3.5 preview of trees 305

7.3.6 additional examples 306

7.4 numerical applications 311

7.4.1 modular arithmetic 311

7.4.2 modular exponentiation 312

7.4.3 greatest common divisor and multiplicative inverses 314

7.4.4 the rsa cryptosystem 317

7.5 divide-and-conquer algorithms 319

7.5.1 the maximum contiguous subsequence sum problem 320

7.5.2 analysis of a basic divide-and-conquer recurrence 323

7.5.3 a general upper bound for divide-and-conquer running times 327

7.6 dynamic programming 329

7.7 backtracking 333

summary 336

key concepts 338

common errors 339

on the internet 339

exercises 340

references 348

Chapter 8 sorting algorithms 351

8.1 why is sorting important? 352

8.2 preliminaries 353

8.3 analysis of the insertion sort and other simple sorts 353

8.4 shellsort 357

8.4.1 performance of shellsort 358

8.5 mergesort 361

8.5.1 linear-time merging of sorted arrays 361

8.5.2 the mergesort algorithm 363

8.6 quicksort 364

8.6.1 the quicksort algorithm 367

8.6.2 analysis of quicksort 369

8.6.3 picking the pivot 372

8.6.4 a partitioning strategy 374

8.6.5 keys equal to the pivot 376

8.6.6 median-of-three partitioning 376

8.6.7 small arrays 377

8.6.8 java quicksort routine 378

8.7 quickselect 380

8.8 a lower bound for sorting 381

summary 383

key concepts 384

common errors 385

on the internet 385

exercises 385

references 391

Chapter 9 randomization 393

9.1 why do we need random numbers? 393

9.2 random number generators 394

9.3 nonuniform randam numbers 402

9.4 generating a random permutation 404

9.5 randomized algorithms 406

9.6 randomized primality testing 409

summary 412

key concepts 412

common errors 413

on the internet 414

exercises 414

references 417

part three Applications 421

Chapter 10 fun and games 421

10.1 word search puzzles 421

10.1.1 theory 422

10.1.2 java implementation 423

10.2 the game of tic-tac-toe 427

10.2.1 alpha-beta pruning 428

10.2.2 transposition tables 431

10.2.3 computer chess 435

summary 438

key concepts 438

common errors 438

on the internet 438

exercises 439

references 441

Chapter 11 stacks and compilers 443

11.1 balanced-symbol checker 443

11.1.1 basic algorithm 444

11.1.2 implementation 445

11.2 a simple calculator 454

11.2.1 postfix machines 456

11.2.2 infix to postfix conversion 457

11.2.3 implementation 459

11.2.4 expression trees 468

summary 469

key concepts 470

common errors 470

on the internet 471

exercises 471

references 472

Chapter 12 utilities 473

12.1 file compression 474

12.1.1 prefix codes 475

12.1.2 huffman's algorithm 477

12.1.3 implementation 479

12.2 a cross-reference generator 495

12.2.1 basic ideas 495

12.2.2 iava implementation 495

summary 499

key concepts 500

common errors 500

on the internet 500

exercises 500

references 506

Chapter 13 simulation 507

13.1 the josephus problem 507

13.1.1 the simple solution 509

13.1.2 a more efficient algorithm 509

13.2 event-driven simulation 513

13.2.1 basic ideas 513

13.2.2 example:a call bank simulation 514

summary 522

key concepts 522

common errors 523

on the internet 523

exercises 523

Chapter 14 graphs and paths 527

14.1 definitions 528

14.1.1 representation 530

14.2 unweighted shortest-path problem 539

14.2.1 theory 539

14.2.2 java implementation 545

14.3 positive-weighted,shortest-path problem 545

14.3.1 theory:dijkstra's algorithm 546

14.3.2 java implementation 550

14.4 negative-weighted,shortest-path problem 552

14.4.1 theory 552

14.4.2 java implementation 553

14.5 path problems in acyclic graphs 555

14.5.1 topological sorting 555

14.5.2 theory of the acyclic shortest-path algorithm 557

14.5.3 java implementation 557

14.5.4 an application:critical-path analysis 560

summary 562

key concepts 563

common errors 564

on the internet 565

exercises 565

references 569

part four ImplementationsChapter 15 inner classes and implementation of ArrayList 573

15.1 iterators and nested classes 574

15.2 iterators and inner classes 576

15.3 the AbstractCollection class 580

15.4 StringBuilder 584

15.5 implementation of ArrayList with an iterator 585

summary 590

key concepts 591

common errors 591

on the internet 591

exercises 591

Chapter 16 stacks and queues 595

16.1 dynamic array implementations 595

16.1.1 stacks 596

16.1.2 queues 600

16.2 linked list implementations 605

16.2.1 stacks 606

16.2.2 queues 609

16.3 comparison of the two methods 613

16.4 the java.util.Stack class 613

16.5 double-ended queues 615

summary 615

key concepts 615

common errors 615

on the internet 616

exercises 616

Chapter 17 linked lists 619

17.1 basic ideas 619

17.1.1 header nodes 621

17.1.2 iterator classes 622

17.2 java implementation 624

17.3 doubly linked lists and circularly linked lists 630

17.4 sorted linked lists 633

17.5 implementing the collections api LinkedList class 635

summary 646

key concepts 646

common errors 647

on the internet 647

exercises 647

Chapter 18 trees 651

18.1 general trees 651

18.1.1 definitions 652

18.1.2 implementation 653

18.1.3 an application:file systems 654

18.2 binary trees 658

18.3 recursion and trees 665

18.4 tree traversal:iterator classes 667

18.4.1 postorder traversal 671

18.4.2 inorder traversal 675

18.4.3 preorder traversal 675

18.4.4 level-order traversals 678

summary 679

key concepts 680

common errors 681

on the internet 682

exercises 682

Chapter 19 binary search trees 687

19.1 basic ideas 687

19.1.1 the operations 688

19.1.2 java implementation 690

19.2 order statistics 697

19.2.1 java implementation 698

19.3 analysis of binary search tree operations 702

19.4 avl trees 706

19.4.1 properties 707

19.4.2 single rotation 709

19.4.3 double rotation 712

19.4.4 summary of avl insertion 714

19.5 red-black trees 715

19.5.1 bottom-up insertion 716

19.5.2 top-down red-black trees 718

19.5.3 java implementation 719

19.5.4 top-down deletion 726

19.6 aa-trees 728

19.6.1 insertion 730

19.6.2 deletion 732

19.6.3 java implementation 733

19.7 implementing the collections api TreeSet and TreeMap classes 738

19.8 b-trees 756

summary 762

key concepts 763

common errors 764

on the internet 764

exercises 765

references 769

Chapter 20 hash tables 773

20.1 basic ideas 774

20.2 hash function 775

20.2.1 headCode in java.lang.String 777

20.3 linear probing 779

20.3.1 naive analysis of linear probing 780

20.3.2 what really happens:primary clustering 781

20.3.3 analysis of the find operation 782

20.4 quadratic probing 784

20.4.1 java implementation 788

20.4.2 analysis of quadratic probing 797

20.5 separate chaining hashing 797

20.6 hash tables versus binary search trees 798

20.7 hashing applications 800

summary 800

key concepts 801

common errors 802

on the internet 802

exercises 802

references 805

Chapter 21 a priority queue:the binary heap 807

21.1 basic ideas 808

21.1.1 structure property 808

21.1.2 heap-order property 810

21.1.3 allowed operations 811

21.2 implementation of the basic operations 814

21.2.1 insertion 814

21.2.2 the del eteMin operation 816

21.3 the buildHeap operation:linear-time heap construction 818

21.4 advanced operations:decreaseKey and merge 823

21.5 internal sorting:heapsort 823

21.6 external sorting 826

21.6.1 why we need new algorithms 826

21.6.2 model for external sorting 827

21.6.3 the simple algorithm 827

21.6.4 multiway merge 829

21.6.5 polyphase merge 830

21.6.6 replacement selection 832

summary 833

key concepts 834

common errors 834

on the internet 835

exercises 835

references 839

part five Advanced Data StructuresChapter 22 splay trees 843

22.1 self-adjustment and amortized analysis 844

22.1.1 amortized time bounds 845

22.1.2 a simple self-adjusting strategy(that does not work) 845

22.2 the basic bottom-up splay tree 847

22.3 basic splay tree operations 850

22.4 analysis of bottom-up splaying 851

22.4.1 proof of the splaying bound 854

22.5 top-down splay trees 857

22.6 implementation of top-down splay trees 860

22.7 comparison of the splay tree with other search trees 865

summary 866

key concepts 866

common errors 867

on the internet 867

exercises 867

references 868

Chapter 23 merging priority queues 871

23.1 the skew heap 871

23.1.1 merging is fundamental 872

23.1.2 simplistic merging of heap-ordered trees 872

23.1.3 the skew heap:a simple modification 873

23.1.4 analysis of the skew heap 874

23.2 the pairing heap 876

23.2.1 pairing heap operations 877

23.2.2 implementation of the pairing heap 878

23.2.3 application:dijkstra's shortest weighted path algorithm 884

summary 888

key concepts 888

common errors 888

on the internet 889

exercises 889

references 890

Chapter 24 the disjoint set class 893

24.1 equivalence relations 894

24.2 dynamic equivalence and applications 894

24.2.1 application:generating mazes 895

24.2.2 application:minimum spanning trees 898

24.2.3 application:the nearest common ancestor problem 901

24.3 the quick-find algorithm 904

24.4 the quick-union algorithm 905

24.4.1 smart union algorithms 907

24.4.2 path compression 909

24.5 java implementation 910

24.6 worst case for union-by-rank and path compression 913

24.6.1 analysis of the union/find algorithm 914

summary 921

key concepts 921

common errors 922

on the internet 922

exercises 923

references 925

appendix A operators 927

appendix B graphical user interfaces 929

B.1 the abstract window toolkit and swing 930

B.2 basic objects in swing 931

B.2.1 Component 932

B.2.2 Container 933

B.2.3 top-level containers 933

B.2.4 JPanel 934

B.2.5 important i/o components 936

B.3 basic principles 940

B.3.1 layout managers 941

B.3.2 graphics 945

B.3.3 events 947

B.3.4 event handling:adapters and anonymous inner classes 949

B.3.5 summary:putting the pieces together 951

B.3.6 is this everything i need to know about swing? 952

summary 953

key concepts 953

common errors 955

on the internet 956

exercises 956

references 957

appendix C bitwise operators 959

index 963