数据结构与问题求解 Java语言版 英文版PDF|Epub|txt|kindle电子书版本网盘下载

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

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

part one Tour of Java3

Chapter 1 Primitive java3

1.1 the general environment4

1.2 the first program5

1.2.1 comments5

1.2.2 main6

1.2.3 terminal output6

1.3 primitive types6

1.3.1 the primitive types6

1.3.2 constants7

1.3.3 declaration and initialization of primitive types7

1.3.4 terminal input and output8

1.4 basic operators8

1.4.1 assignment operators9

1.4.2 binary arithmetic operators10

1.4.3 unary operators10

1.4.4 type conversions10

1.5 conditional statements11

1.5.1 relational and equality operators11

1.5.2 logical operators12

1.5.3 the if statement13

1.5.4 the while statement14

1.5.5 the for statement14

1.5.6 the do statement15

1.5.7 break and continue16

1.5.8 the switch statement17

1.5.9 the conditional operator17

1.6 methods18

1.6.1 overloading of method names19

1.6.2 storage classes20

summary20

key concepts20

common errors22

on the internet23

exercises23

references25

Chapter 2 reference types27

2.1 what is a reference?27

2.2 basics of objects and references30

2.2.1 the dot operator(.)30

2.2.2 declaration of objects30

2.2.3 garbage collection31

2.2.4 the meaning of=32

2.2.5 parameter passing33

2.2.6 the meaning of==33

2.2.7 no operator overloading for objects34

2.3 strings35

2.3.1 basics of string manipulation35

2.3.2 string concatenation35

2.3.3 comparing strings36

2.3.4 other String methods36

2.3.5 converting other types to strings37

2.4 arrays37

2.4.1 declaration,assignment,and methods38

2.4.2 dynamic array expansion40

2.4.3 ArrayList42

2.4.4 multidimensional arrays45

2.4.5 command-line arguments45

2.4.6 enhanced for loop46

2.5 exception handling47

2.5.1 processing exceptions48

2.5.2 the finally clause48

2.5.3 common exceptions49

2.5.4 the throw and throws clauses51

2.6 input and output51

2.6.1 basic stream operations52

2.6.2 the Scanner type53

2.6.3 sequential files56

summary59

key concepts60

common errors61

on the internet62

exercises62

references68

Chapter 3 objects and classes69

3.1 what is object-oriented programming?69

3.2 a simple example71

3.3 javadoc73

3.4 basic methods76

3.4.1 constructors76

3.4.2 mutators and accessors76

3.4.3 output and toString78

3.4.4 equals78

3.4.5 main78

3.5 example:using java.math.BigInteger78

3.6 additional constructs79

3.6.1 the this reference81

3.6.2 the this shorthand for constructors82

3.6.3 the instanceof operator82

3.6.4 instance members versus static members83

3.6.5 static fields and methods83

3.6.6 static initializers86

3.7 example:implementing a BigRational class86

3.8 packages90

3.8.1 the import directive91

3.8.2 the package statement93

3.8.3 the CLASSPATH environment variable94

3.8.4 package visibility rules95

3.9 a design pattern:composite(pair)95

summary96

key concepts97

common errors100

on the internet100

exercises101

references107

Chapter 4 inheritance109

4.1 what is inheritance?110

4.1.1 creating new classes110

4.1.2 type compatibility115

4.1.3 dynamic dispatch and polymorphism116

4.1.4 inheritance hierarchies117

4.1.5 visibility rules117

4.1.6 the constructor and super118

4.1.7 final methods and classes119

4.1.8 overriding a method121

4.1.9 type compatibility revisited121

4.1.10 compatibility of array types124

4.1.11 covariant return types124

4.2 designing hierarchies125

4.2.1 abstract methods and classes126

4.2.2 designing for the future130

4.3 multiple inheritance131

4.4 the interface134

4.4.1 specifying an interface134

4.4.2 implementing an interface135

4.4.3 multiple interfaces135

4.4.4 interfaces are abstract classes136

4.5 fundamental inheritance in java136

4.5.1 the Object class136

4.5.2 the hierarchy of exceptions137

4.5.3 i/o:the decorator pattern138

4.6 implementing generic components using inheritance142

4.6.1 using Object for genericity142

4.6.2 wrappers for primitive types143

4.6.3 autoboxing/unboxing145

4.6.4 adapters:changing an interface146

4.6.5 using interface types for genericity147

4.7 implementing generic components using java 5 generics150

4.7.1 simple generic classes and interfaces150

4.7.2 wildcards with bounds151

4.7.3 generic static methods152

4.7.4 type bounds153

4.7.5 type erasure154

4.7.6 restrictions on generics154

4.8 the functor(function objects)157

4.8.1 nested classes161

4.8.2 local classes161

4.8.3 anonymous classes163

4.8.4 nested classes and generics164

4.9 dynamic dispatch details164

summary168

key concepts168

common errors171

on the internet171

exercises173

references183

part two Algorithms and Building BlocksChapter 5 algorithm analysis187

5.1 what is algorithm analysis?188

5.2 examples of algorithm running times192

5.3 the maximum contiguous subsequence sum problem193

5.3.1 the obvious O(N3)algorithm194

5.3.2 an improved O(N2)algorithm197

5.3.3 a linear algorithm197

5.4 general big-oh rules201

5.5 the logarithm205

5.6 static searching problem207

5.6.1 sequential search207

5.6.2 binary search208

5.6.3 interpolation search211

5.7 checking an algorithm analysis212

5.8 limitations of big-oh analysis213

summary214

key concepts214

common errors215

on the internet216

exercises216

references227

Chapter 6 the collections api229

6.1 introduction230

6.2 the iterator pattern231

6.2.1 basic iterator design232

6.2.2 inheritance-based iterators and factories234

6.3 collections api:containers and iterators236

6.3.1 the Collecti on interface237

6.3.2 Iterator interface240

6.4 generic algorithms242

6.4.1 Comparator function objects243

6.4.2 the Collections class243

6.4.3 binary search246

6.4.4 sorting246

6.5 the List interface248

6.5.1 the ListIterator interface249

6.5.2 LinkedList class251

6.5.3 running time for Lists253

6.5.4 removing from and adding to the middle of a List256

6.6 stacks and queues258

6.6.1 stacks258

6.6.2 stacks and computer languages259

6.6.3 queues260

6.6.4 stacks and queues in the collections api261

6.7 sets261

6.7.1 the TreeSet class263

6.7.2 the HashSet class264

6.8 maps268

6.9 priority queues274

6.10 views in the collections api277

6.10.1 the subList method for Lists277

6.10.2 the headSet,subSet,and tailSet methods for SortedSets277

summary278

key concepts279

common errors280

on the internet281

exercises281

references292

Chapter 7 recursion293

7.1 what is recursion?294

7.2 background:proofs by mathematical induction295

7.3 basic recursion297

7.3.1 printing numbers in any base299

7.3.2 why it works301

7.3.3 how it works302

7.3.4 too much recursion can be dangerous304

7.3.5 preview of trees305

7.3.6 additional examples306

7.4 numerical applications311

7.4.1 modular arithmetic311

7.4.2 modular exponentiation312

7.4.3 greatest common divisor and multiplicative inverses314

7.4.4 the rsa cryptosystem317

7.5 divide-and-conquer algorithms319

7.5.1 the maximum contiguous subsequence sum problem320

7.5.2 analysis of a basic divide-and-conquer recurrence323

7.5.3 a general upper bound for divide-and-conquer running times327

7.6 dynamic programming329

7.7 backtracking333

summary336

key concepts338

common errors339

on the internet339

exercises340

references348

Chapter 8 sorting algorithms351

8.1 why is sorting important?352

8.2 preliminaries353

8.3 analysis of the insertion sort and other simple sorts353

8.4 shellsort357

8.4.1 performance of shellsort358

8.5 mergesort361

8.5.1 linear-time merging of sorted arrays361

8.5.2 the mergesort algorithm363

8.6 quicksort364

8.6.1 the quicksort algorithm367

8.6.2 analysis of quicksort369

8.6.3 picking the pivot372

8.6.4 a partitioning strategy374

8.6.5 keys equal to the pivot376

8.6.6 median-of-three partitioning376

8.6.7 small arrays377

8.6.8 java quicksort routine378

8.7 quickselect380

8.8 a lower bound for sorting381

summary383

key concepts384

common errors385

on the internet385

exercises385

references391

Chapter 9 randomization393

9.1 why do we need random numbers?393

9.2 random number generators394

9.3 nonuniform randam numbers402

9.4 generating a random permutation404

9.5 randomized algorithms406

9.6 randomized primality testing409

summary412

key concepts412

common errors413

on the internet414

exercises414

references417

part three Applications421

Chapter 10 fun and games421

10.1 word search puzzles421

10.1.1 theory422

10.1.2 java implementation423

10.2 the game of tic-tac-toe427

10.2.1 alpha-beta pruning428

10.2.2 transposition tables431

10.2.3 computer chess435

summary438

key concepts438

common errors438

on the internet438

exercises439

references441

Chapter 11 stacks and compilers443

11.1 balanced-symbol checker443

11.1.1 basic algorithm444

11.1.2 implementation445

11.2 a simple calculator454

11.2.1 postfix machines456

11.2.2 infix to postfix conversion457

11.2.3 implementation459

11.2.4 expression trees468

summary469

key concepts470

common errors470

on the internet471

exercises471

references472

Chapter 12 utilities473

12.1 file compression474

12.1.1 prefix codes475

12.1.2 huffman's algorithm477

12.1.3 implementation479

12.2 a cross-reference generator495

12.2.1 basic ideas495

12.2.2 iava implementation495

summary499

key concepts500

common errors500

on the internet500

exercises500

references506

Chapter 13 simulation507

13.1 the josephus problem507

13.1.1 the simple solution509

13.1.2 a more efficient algorithm509

13.2 event-driven simulation513

13.2.1 basic ideas513

13.2.2 example:a call bank simulation514

summary522

key concepts522

common errors523

on the internet523

exercises523

Chapter 14 graphs and paths527

14.1 definitions528

14.1.1 representation530

14.2 unweighted shortest-path problem539

14.2.1 theory539

14.2.2 java implementation545

14.3 positive-weighted,shortest-path problem545

14.3.1 theory:dijkstra's algorithm546

14.3.2 java implementation550

14.4 negative-weighted,shortest-path problem552

14.4.1 theory552

14.4.2 java implementation553

14.5 path problems in acyclic graphs555

14.5.1 topological sorting555

14.5.2 theory of the acyclic shortest-path algorithm557

14.5.3 java implementation557

14.5.4 an application:critical-path analysis560

summary562

key concepts563

common errors564

on the internet565

exercises565

references569

part four ImplementationsChapter 15 inner classes and implementation of ArrayList573

15.1 iterators and nested classes574

15.2 iterators and inner classes576

15.3 the AbstractCollection class580

15.4 StringBuilder584

15.5 implementation of ArrayList with an iterator585

summary590

key concepts591

common errors591

on the internet591

exercises591

Chapter 16 stacks and queues595

16.1 dynamic array implementations595

16.1.1 stacks596

16.1.2 queues600

16.2 linked list implementations605

16.2.1 stacks606

16.2.2 queues609

16.3 comparison of the two methods613

16.4 the java.util.Stack class613

16.5 double-ended queues615

summary615

key concepts615

common errors615

on the internet616

exercises616

Chapter 17 linked lists619

17.1 basic ideas619

17.1.1 header nodes621

17.1.2 iterator classes622

17.2 java implementation624

17.3 doubly linked lists and circularly linked lists630

17.4 sorted linked lists633

17.5 implementing the collections api LinkedList class635

summary646

key concepts646

common errors647

on the internet647

exercises647

Chapter 18 trees651

18.1 general trees651

18.1.1 definitions652

18.1.2 implementation653

18.1.3 an application:file systems654

18.2 binary trees658

18.3 recursion and trees665

18.4 tree traversal:iterator classes667

18.4.1 postorder traversal671

18.4.2 inorder traversal675

18.4.3 preorder traversal675

18.4.4 level-order traversals678

summary679

key concepts680

common errors681

on the internet682

exercises682

Chapter 19 binary search trees687

19.1 basic ideas687

19.1.1 the operations688

19.1.2 java implementation690

19.2 order statistics697

19.2.1 java implementation698

19.3 analysis of binary search tree operations702

19.4 avl trees706

19.4.1 properties707

19.4.2 single rotation709

19.4.3 double rotation712

19.4.4 summary of avl insertion714

19.5 red-black trees715

19.5.1 bottom-up insertion716

19.5.2 top-down red-black trees718

19.5.3 java implementation719

19.5.4 top-down deletion726

19.6 aa-trees728

19.6.1 insertion730

19.6.2 deletion732

19.6.3 java implementation733

19.7 implementing the collections api TreeSet and TreeMap classes738

19.8 b-trees756

summary762

key concepts763

common errors764

on the internet764

exercises765

references769

Chapter 20 hash tables773

20.1 basic ideas774

20.2 hash function775

20.2.1 headCode in java.lang.String777

20.3 linear probing779

20.3.1 naive analysis of linear probing780

20.3.2 what really happens:primary clustering781

20.3.3 analysis of the find operation782

20.4 quadratic probing784

20.4.1 java implementation788

20.4.2 analysis of quadratic probing797

20.5 separate chaining hashing797

20.6 hash tables versus binary search trees798

20.7 hashing applications800

summary800

key concepts801

common errors802

on the internet802

exercises802

references805

Chapter 21 a priority queue:the binary heap807

21.1 basic ideas808

21.1.1 structure property808

21.1.2 heap-order property810

21.1.3 allowed operations811

21.2 implementation of the basic operations814

21.2.1 insertion814

21.2.2 the del eteMin operation816

21.3 the buildHeap operation:linear-time heap construction818

21.4 advanced operations:decreaseKey and merge823

21.5 internal sorting:heapsort823

21.6 external sorting826

21.6.1 why we need new algorithms826

21.6.2 model for external sorting827

21.6.3 the simple algorithm827

21.6.4 multiway merge829

21.6.5 polyphase merge830

21.6.6 replacement selection832

summary833

key concepts834

common errors834

on the internet835

exercises835

references839

part five Advanced Data StructuresChapter 22 splay trees843

22.1 self-adjustment and amortized analysis844

22.1.1 amortized time bounds845

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

22.2 the basic bottom-up splay tree847

22.3 basic splay tree operations850

22.4 analysis of bottom-up splaying851

22.4.1 proof of the splaying bound854

22.5 top-down splay trees857

22.6 implementation of top-down splay trees860

22.7 comparison of the splay tree with other search trees865

summary866

key concepts866

common errors867

on the internet867

exercises867

references868

Chapter 23 merging priority queues871

23.1 the skew heap871

23.1.1 merging is fundamental872

23.1.2 simplistic merging of heap-ordered trees872

23.1.3 the skew heap:a simple modification873

23.1.4 analysis of the skew heap874

23.2 the pairing heap876

23.2.1 pairing heap operations877

23.2.2 implementation of the pairing heap878

23.2.3 application:dijkstra's shortest weighted path algorithm884

summary888

key concepts888

common errors888

on the internet889

exercises889

references890

Chapter 24 the disjoint set class893

24.1 equivalence relations894

24.2 dynamic equivalence and applications894

24.2.1 application:generating mazes895

24.2.2 application:minimum spanning trees898

24.2.3 application:the nearest common ancestor problem901

24.3 the quick-find algorithm904

24.4 the quick-union algorithm905

24.4.1 smart union algorithms907

24.4.2 path compression909

24.5 java implementation910

24.6 worst case for union-by-rank and path compression913

24.6.1 analysis of the union/find algorithm914

summary921

key concepts921

common errors922

on the internet922

exercises923

references925

appendix A operators927

appendix B graphical user interfaces929

B.1 the abstract window toolkit and swing930

B.2 basic objects in swing931

B.2.1 Component932

B.2.2 Container933

B.2.3 top-level containers933

B.2.4 JPanel934

B.2.5 important i/o components936

B.3 basic principles940

B.3.1 layout managers941

B.3.2 graphics945

B.3.3 events947

B.3.4 event handling:adapters and anonymous inner classes949

B.3.5 summary:putting the pieces together951

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

summary953

key concepts953

common errors955

on the internet956

exercises956

references957

appendix C bitwise operators959

index963