数据结构与问题求解：Java版 英文版

PART I: TOUR OF JAVA

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

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 l0

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

Objects of the Game 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 TheDotOperator(.) 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 Stri no Methods 36

2.3.5 Converting Other Types of 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 43

2.4.4 Multidimensional Arrays 45

2.4.5 Command-line Arguments 45

2.5 Exception Handling 47

2.5.1 Processing Exceptions 47

2.5.2 The finally Clause 47

2.5.3 Common Exceptions 49

2.5.4 The throw and throws Clauses 50

2.6 Input and Output 50

2.6.1 Basic Stream Operations 51

2.6.2 The 5tringl0kenizer Type 52

2.6.3 Sequential Files 53

Summary 55

Objects of the Game 57

Common Errors 58

On the Internet 59

Exercises 59

References 60

CHAPTER 3 Objects and Classes 61

3.1 What Is Object-Oriented Programming? 61

3.2 A Simple Example 63

3.3 Javadoc 65

3.4 Basic Methods 68

3.4.1 Constructors 68

3.4.2 Mutators and Accessors 68

3.4.3 OutputandtOString 70

3.4.4 equals 70

3.4.5 main 70

3.4.6 Static Fields and Methods 71

3.5 Additional Constructs 71

3.5.1 The this Reference 71

3.5.2 The this Shorthand for Constructors 72

3.5.3 The i nstance0f Operator 72

3.5.4 Instance Members vs. Static Members 73

3.5.5 Static Fields and Methods 73

3.5.6 Static Initializers 74

3.6 Packages 76

3.6.1 The import Directive 76

3.6.2 The package Statement 78

3.6.3 The CLASSPATH Environment Variable 78

3.6.4 Package Visibility Rules 79

3.7 A Design Pattern: Composite (Pair) 80

Summary 81

Objects of the Game 83

Common Errors 84

On the Internet 85

Exercises 85

References 88

CHAPTER 4 Inheritance 89

4.1 What Is Inheritance? 90

4.1.1 Creating New Classes 90

4.1.2 Type Compatibility 95

4.1.3 Dynamic Binding and Polymorphism 96

4.1.4 Inheritance Hierarchies 97

4.1.5 Visibility Rules 97

4.1.6 The Constructor and super 98

4.1.7 fi nal Methods and Classes 99

4.1.8 Overriding a Method 100

4.1.9 Type Compatibility Revisited 101

4.2 Designing Hierarchies 103

4.2.1 Abstract Methods and Classes 107

4.3 Multiple Inheritance 109

4.4 The Interface 110

4.4.1 Specifying an Interface 110

4.4.2 Implementing an Interface 111

4.4.3 Multiple Interfaces 112

4.4.4 Interfaces are Abstract Classes 112

4.5 Fundamental Inheritance in Java 113

4.5.1 The Object Class 113

4.5.2 The Hierarchy of Exceptions 113

4.5.3 I/O: The Decorator Pattern 113

4.6 Implementing Generic Components 118

4.6.1 Using Object for Genericity 119

4.6.2 Wrappers for Primitive Types 120

4.6.3 Adapters: Changing an Interface 120

4.6.4 Using Interface Types for Genericity 123

4.7 The Functor (Function Objects) 125

4.7.1 Nested Classes 128

4.7.2 Local Classes 129

4.7.3 Anonymous Classes 130

4.8 Dynamic Binding Details 131

Summary 135

Objects of the Game 136

Common Errors 138

On the Internet 138

Exercises 140

References 144

PART II: ALGORITHMS AND BUILDING BLOCKS

CHAPTER 5 Algorithm Analysis 147

5.1 What Is Algorithm Analysis? 148

5.2 Examples of Algorithm Running Times 151

5.3 The Maximum Contiguous Subsequence Sum Problem 153

5.3.1 The Obvious O(N 3) Algorithm 154

5.3.2 An Improved O(N 2) Algorithm 157

5.3.3 A Linear Algorithm 158

5.4 General Big-Oh Rules 160

5.5 The Logarithm 164

5.6 Static Searching Problem 167

5.6.1 Sequential Search 167

5.6.2 Binary Search 168

5.6.3 Interpolation Search 170

5.7 Checking an Algorithm Analysis 171

5.8 Limitations of Big-Oh Analysis 173

Summary 174

Objects of the Game 174

Common Errors 175

On the Internet 175

Exercises 176

References 181

CHAPTER 6 The Collections APl 183

6.1 Introduction 184

6.2 The Iterator Pattern 185

6.2.1 Basic Iterator Design 186

6.2.2 Inheritance-based Iterators and Factories 188

6.3 Collections API: Containers and Iterators 190

6.3.1 The Collection Interface 190

6.3.2 Iterator Interface 193

6.4 Generic Algorithms 195

6.4.1 C0mparator Function Objects 195

6.4.2 The Collections Class 195

6.4.3 Binary Search 198

6.4.4 Sorting 199

6.5 The List Interface 199

6.5.1 The Listlterat0r Interface 201

6.5.2 kinkedLiist Class 202

6.6 Stacks and Queues 205

6.6.1 Stacks 205

6.6.2 Stacks and Computer Languages 206

6.6.3 Queues 208

6.6.4 Stacks and Queues in the Collections API 208

6.7 Sets 209

6.7.1 ThelreeSet Class 210

6.7.2 The HashSet Class 211

6.8 Maps 216

6.9 Priority Queues 220

Summary 224

Objects of the Game 225

Common Errors 226

On the Internet 226

Exercises 227

References 230

CHAPTER 7 Recursion 231

7.1 What Is Recursion? 232

7.2 Background: Proofs by Mathematical Induction 233

7.3 Basic Recursion 235

7.3.1 Printing Numbers in Any Base 237

7.3.2 Why It Works 239

7.3.3 How It Works 241

7.3.4 Too Much Recursion Can Be Dangerous 242

7.3.5 Preview of Trees 243

7.3.6 Additional Examples 244

7.4 Numerical Applications 248

7.4.1 Modular Arithmetic 250

7.4.2 Modular Exponentiation 250

7.4.3 Greatest Common Divisor and Multiplicative Inverses 252

7.4.4 The RSA Cryptosystem 254

7.5 Divide-and-Conquer Algorithms 257

7.5.1 The Maximum Contiguous Subsequence Sum Problem 258

7.5.2 Analysis of a Basic Divide-and-Conquer Recurrence 260

7.5.3 A General Upper Bound for Divide-and-Conquer Running

Times 265

7.6 Dynamic Programming 267

7.7 Backtracking 272

Summary 276

Objects of the Game 276

Common Errors 277

On the Internet 278

Exercises 278

References 282

CHAPTER 8 Sorting Algorithms 283

8.1 Why Is Sorting Important? 284

8.2 Preliminaries 285

8.3 Analysis of the Insertion Sort and Other Simple Sorts 285

8.4 Shellsort 289

8.4.1 Performance of Shellsort 290

8.5 Mergesort 293

8.5.1 Linear-Time Merging of Sorted Arrays 293

8.5.2 The Mergesort Algorithm 295

8.6 Quicksort 295

8.6.1 The Quicksort Algorithm 296

8.6.2 Analysis of Quicksort 299

8.6.3 Picking the Pivot 303

8.6.4 A Partitioning Strategy 304

8.6.5 Keys Equal to the Pivot 307

8.6.6 Median-of-Three Partitioning 307

8.6.7 Small Arrays 308

8.6.8 Java Quicksort Routine 309

8.7 Quickselect 311

8.8 A Lower Bound for Sorting 312

Summary 314

Objects of the Game 315

Common Errors 315

On the Internet 316

Exercises 316

References 320

CHAPTER 9 Randomization 323

9.1 Why Do We Need Random Numbers? 323

9.2 Random Number Generators 324

9.3 Nonuniform Random Numbers 330

9.4 Generating a Random Permutation 333

9.5 Randomized Algorithms 334

9.6 Randomized Primality Testing 337

Summary 340

Objects of the Game 340

Common Errors 341

On the Internet 342

Exercises 342

References 344

PART III: APPLICATIONS

CHAPTER 10 Fun and Games 347

10.1 Word Search Puzzles 347

10.1.1 Theory 348

10.1.2 Java Implementation 350

10.2 The Game of Tic-Tac-Toe 350

10.2.1 Alpha-Beta Pruning 353

10.2.2 Transposition Tables 359

10.2.3 Computer Chess 362

Summary 364

Objects of the Game 364

Common Errors 364

On the Internet 365

Exercises 365

References 367

CHAPTER 11 Stacks and Compilers 369

11.1 Balanced-Symbol Checker 369

11.1.1 Basic Algorithm 370

11.1.2 Implementation 371

11.2 A Simple Calculator 380

11.2.1 Postfix Machines 382

11.2.2 Infix to Postfix Conversion 383

11.2.3 Implementation 386

11.2.4 Expression Trees 391

Summary 395

Objects of the Game 396

Common Errors 396

On the Internet 397

Exercises 397

References 398

CHAPTER 12 Utilities 399

12.1 File Compression 399

12.1.1 Prefix Codes 401

12.1.2 Huffman's Algorithm 403

12.1.3 Implementation 405

12.2 A Cross-Reference Generator 420

12.2.1 Basic Ideas 420

12.2.2 Java Implementation 420

Summary 424

Objects of the Game 425

Common Errors 425

On the Internet 425

Exercises 425

References 428

CHAPTER 13 Simulation 429

13.1 The Josephus Problem 429

13.1.1 The Simple Solution 431

13.1.2 A More Efficient Algorithm 431

13.2 Event-Driven Simulation 435

13.2.1 Basic Ideas 435

13.2.2 Example: A Modem Bank Simulation 436

Summary 444

Objects of the Game 444

Common Errors 444

On the Internet 444

Exercises 445

CHATPTER 14 Graphs and Paths 447

14.1 Definitions 448

14.1.1 Represent. ation 449

14.2 Unweighted Shortest-Path Problem 459

14.2.1 Theory 462

14.2.2 Java Implementation 466

14.3 Positive-Weighted, Shortest-Path Problem 467

14.3.1 Theory: Dijkstra's Algorithm 467

14.3.2 Java Implementation 469

14.4 Negative-Weighted, Shortest-Path Problem 471

14.4.1 Theory 473

14.4.2 Java Implementation 474

14.5 Path Problems in Acyclic Graphs 474

14.5.1 Topological Sorting 474

14.5.2 Theory of the Acyclic Shortest-Path Algorithm 476

14.5.3 Java Implementation 478

14.5.4 An Application: Critical-PathAnalysis 480

Summary 483

Objects of the Game 483

Common Errors 485

On the Internet 485

Exercises 485

References 489

PART IV: IMPLEMENTATIONS

CHATPTER 15 Inner Classes and Implementation of ArrayList 493

15.1 Iterators and Nested Classes 493

15.2 Iterators and Inner Classes 495

15.3 The abstractCOllection Class 500

15.4 Implementation of ArrayList with an Iterator 500

Summary 508

~ 13 ~

Objects of the Game 508

Common Error 508

On the Internet 509

Exercises 509

CHATPTER 16 Stacks andOueues 513

16.1 Dynamic Array Implementations 513

16.1.1 Stacks 514

16.1.2 Queues 518

16.2 Linked List Implementations 524

16.2.1 Stacks 524

16.2.2 Queues 525

16.3 Comparison of the Two Methods 530

16.4 The java.uti1 .Stack Class 531

16.5 Double-Ended Queues 533

Summary 534

Objects of the Game 534

Common Errors 534

On the Internet 534

Exercises 535

CHAPTER 17 Linked Lists 537

17.1 Basic Ideas 537

17.1.1 Header Nodes 539

17.1.2 IteratorClasses 541

17.2 Java Implementation 542

17.3 Doubly Linked Lists and Circularly Linked Lists 548

17.4 Sorted Linked Lists 551

17.5 Implementing the Collections API linkedlist Class 551

Summary 563

Objects of the Game 563

Common Errors 563

On the Internet 563

Exercises 564

CHAPTER 18 Trees 569

18.1 General Trees 569

18.1.1 Definitions 570

18.1.2 Implementation 571

18.1.3 An Application: File Systems 572

18.2 Binary Trees 576

18.3 Recursion and Trees 582

18.4 Tree Traversal: Iterator Classes 585

18.4.1 Postorder Traversal 589

18.4.2 InorderTraversal 592

18.4.3 Preorder Traversal 592

18.4.4 Level-OrderTraversals 596

Summary 597

Objects of the Game 598

Common Errors 599

On the Internet 599

Exercises 600

CHATPTER 19 Binary Search Trees 603

19.1 Basic Ideas 603

19.1.1 The Operations 604

19.1.2 Java Implementation 606

19.2 Order Statistics 613

19.2.1 Java Implementation 614

19.3 Analysis of Binary Search Tree Operations 618

19.4 AVL Trees 621

19.4.1 Properties 622

19.4.2 Single Rotation 624

19.4.3 Double Rotation 627

19.4.4 Summary of AVL Insertion 630

19.5 Red-Black Trees 630

19.5.1 Bottom-Up Insertion 631

19.5.2 Top-Down Red-Black Trees 634

19.5.3 Java Implementation 636

19.5.4 Top-DownDeletion 641

19.6 AA-Trees 644

19.6.1 Insertion 646

19.6.2 Deletion 648

19.6.3 Java Implementation 649

19.7 Implementing the Collections API lreeSet and IreeYap

Classes 654

19.8 B-Trees 663

Summary 675

Objects of the Game 676

Common Errors 677

On the Internet 677

Exercises 678

References 680

CHAPTER 20 Hash Tables 683

20.1 Basic Ideas 684

20.2 Hash Function 685

20.3 Linear Probing 687

20.3.1 Naive Analysis of Linear Probing 689

20.3.2 What Really Happens: Primary Clustering 690

20.3.3 Analysis of the find Operation 691

20.4 Quadratic Probing 693

20.4.1 Java Implementation 697

20.4.2 Analysis of Quadratic Probing 703

20.5 Separate Chaining Hashing 706

20.6 Hash Tables Versus Binary Search Trees 707

20.7 Hashing Applications 707

Summary 708

Objects of the Game 708

Common Errors 709

On the Internet 710

Exercises 710

References 712

CHATPTER 21 A Priority Queue: The Binary Heap 715

21.1 Basic Ideas 716

21.1.1 Structure Property 716

21.1.2 Heap-Order Property 718

21.1.3 Allowed Operations 718

21.2 Implementation of the Basic Operations 721

21.2.1 The insert Operation 722

21.2.2 The del eteMin Operation 723

21.3 The build.ap Operation: Linear-Time Heap Construction 726

21.4 Advanced Operations: decreaseKey and merge 731

21.5 Internal Sorting: Heapsort 731

21.6 External Sorting 734

21.6.1 Why We Need New Algorithms 734

21.6.2 Model for External Sorting 735

21.6.3 The Simple Algorithm 735

21.6.4 MultiwayMerge 737

21.6.5 Polyphase Merge 738

21.6.6 Replacement Selection 740

Summary 741

Objects of the Game 741

Common Errors 742

On the Internet 742

Exercises 743

References 747

PART V: ADVANCED DATA STRUCTURES

CHATPTER 22 Splay Trees 751

22.1 Self-Adjustment and Amortized Analysis 752

22.1.1 Amortized Time Bounds 753

22.1.2 A Simple Self-Adjusting Strategy (That Does Not

Work) 753

22.2 The Basic Bottom-Up Splay Tree 755

22.3 Basic Splay Tree Operations 758

22.4 Analysis of Bottom-Up Splaying 759

22.4.1 Proof of the Splaying Bound 762

22.5 Top-Down Splay Trees 765

22.6 Implementation of Top-Down Splay Trees 768

22.7 Comparison of the Splay Tree with Other Search Trees 771

Summary 773

Objects of the Game 773

Common Errors 776

On the Internet 776

Exercises 776

References 777

CHATPTER 23 Merging Priority Queues 779

23.1 The Skew Heap 779

23.1.1 Merging Is Fundamental 780

23.1.2 Simplistic Merging of Heap-Ordered Trees 780

23.1.3 The Skew Heap: A Simple Modification 781

23.1.4 Analysis of the Skew Heap 782

23.2 The Pairing Heap 784

23.2.1 Pairing Heap Operations 785

23.2.2 Implementation of the Pairing Heap 786

23.2.3 Application: Dijkstra's Shortest Weighted Path

Algorithm 791

Summary 796

Objects of the Game 796

Common Errors 796

On the Internet 797

Exercises 797

References 798

CHAPTER 24 The Oisjoint Set Class 801

24.1 Equivalence Relations 802

24.2 Dynamic Equivalence and Applications 802

24.2.1 Application: Generating Mazes 803

24.2.2 Application: Minimum Spanning Trees 806

24.2.3 Application: The Nearest Common Ancestor Problem 809

24.3 The Quick-Find Algorithm 813

24.4 The Quick-Union Algorithm 814

24.4.1 Smart Union Algorithms 815

24.4.2 Path Compression 817

24.5 Java Implementation 818

24.6 Worst Case for Union-by-Rank and Path Compression 821

24.6.1 Analysis of the Union/Find Algorithm 822

Summary 828

Objects of the Game 829

Common Errors 830

On the Internet 830

Exercises 830

References 833

APPENDICES

APPENDIX A Operators 835

APPENDIX B Graphical User Interfaces 837

B.1 The Abstract Window Toolkit and Swing 838

B.2 Basic Objects in Swing 839

B.2.1 Component 839

B.2.2 Container 841

B.2.3 Top-level Containers 841

B.2.4 jPanel 842

B.2.5 Important I/O Components 843

B.3 Basic Principles 848

B.3.1 Layout Managers 848

B.3.2 Graphics 852

B.3.3 Events 853

B.3.4 Event Handling: Adapters and Anonymous Inner

Classes 856

B.3.5 Summary: Putting the Pieces Together 859

B.3.6 Is This Everything I Need To Know About Swing? 860

Summary 860

Objects of the Game 861

Common Errors 863

On the Internet 863

Exercises 863

Reference 865

APPENDIX C BitwiseOperators 867

Index 871