《DATA STRUCTURES AND PROBLEM SOLVING USING JAVA》求取 ⇩

Part Ⅰ：Tour of Java3

CHAPTER1 Primitive Java3

1.1 The General Environment4

1.2The First Program5

1.2.1 Comments5

1.2.2 main6

1.2.3 Terminal Output6

1.3Primitive 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.4Basic Operators8

1.4.1 Assignment Operators9

1.4.2 Binary Arithmetic Operators10

1.4.3 Unary Operators10

1.4.4 Type Conversions10

1.5Conditional Statements11

1.5.1 Relational and Equality Operators11

1.5.2 Logical Operators12

1.5.3 The i f 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.6Methods18

1.6.1 Overloading of Method Names19

1.6.2 Storage Classes20

Summary20

Objects of the Game20

Common Errors22

On the Internet23

Exercises23

References25

CHAPTER 2References27

2.1 What Is a Reference？27

2.2Basics of Objects and References29

2.2.1 The Dot Operator （.）30

2.2.2 Declaration of Objects30

2.2.3 Garbage Collection31

2.2.4 The Meaning of =31

2.2.5 Parameter Passing32

2.2.6 The Meaning of ==33

2.2.7 Operator Overloading for Objects33

2.3Strings33

2.3.1 Basics of String Manipulation34

2.3.2 String Concatenation34

2.3.3 Comparing Strings35

2.3.4 Other String Methods35

2.3.5 Converting between Strings and Primitive Types35

2.4Arrays36

2.4.1 Declaration，Assignment，and Methods36

2.4.2 Dynamic Array Expansion39

2.4.3 Multidimensional Arrays41

2.4.4 Command-line Arguments41

2.5Exception Handling42

2.5.1 Processing Exceptions42

2.5.2 The finally Clause43

2.5.3 Common Exceptions43

2.5.4 The throw and throws Clauses44

2.6Input and Output45

2.6.1 Basic Stream Operations46

2.6.2 The StringTokenizer Object46

2.6.3 Sequential Files47

Summary49

Objects of the Game49

Common Errors51

On the Internet51

Exercises51

References52

CHAPTER 3Objects and Classes53

3.1 What Is Object-oriented Programming？53

3.2 A Simple Example55

3.3 Javadoc57

3.4Basic Methods58

3.4.1 Constructors58

3.4.2 Mutators and Accessors60

3.4.3 Output and toString60

3.4.4 equals62

3.4.5 static Methods62

3.4.6 main62

3.5Packages62

3.5.1 The import Directive63

3.5.2 The package Statement64

3.5.3 The CLASSPATH Environment Variable65

3.5.4 Package-friendly Visibility Rules66

3.5.5 Separate Compilation66

3.6Additional Constructs66

3.6.1 The this Reference66

3.6.2 The this Shorthand for Constructors67

3.6.3 The instanceof Operator68

3.6.4 Static Fields68

3.6.5 Static Initializers69

Summary70

Objects of the Game70

Common Errors71

On the Internet72

Exercises72

References74

CHAPTER 4Inheritance75

4.1 What Is Inheritance？75

4.2Basic Java Syntax78

4.2.1 Visibility Rules79

4.2.2 The Constructor and super79

4.2.3 final Methods and Classes80

4.2.4 Overriding a Method81

4.2.5 Abstract Methods and Classes82

4.3Example：Expanding the Shape Class84

4.3.1 Digression：An Introduction to Sorting86

4.4 Multiple Inheritance90

4.5The Interface90

4.5.1 Specifying an Interface91

4.5.2 Implementing an Interface91

4.5.3 Multiple Interfaces94

4.6 Implementing Generic Components94

Summary97

Objects of the Game98

Common Errors99

On the Internet100

Exercises100

References102

Part Ⅱ：Algorithms and Building Blocks107

CHAPTER 5Algorithm Analysis107

5.1 What Is Algorithm Analysis？107

5.2 Examples of Algorithm Running Times111

5.3The Maximum Contiguous Subsequence Sum Problem113

5.3.1 The Obvious O（N3） Algorithm114

5.3.2 An Improved O（N2） Algorithm117

5.3.3 A Linear Algorithm118

5.4 General Big-Oh Rules121

5.5 The Logarithm124

5.6Static Searching Problem127

5.6.1 Sequential Search127

5.6.2 Binary Search128

5.6.3 Interpolation Search129

5.7 Checking an Algorithm Analysis131

5.8 Limitations of Big-Oh Analysis133

Summary133

Objects of the Game134

Common Errors134

On the Internet135

Exercises135

References139

CHAPTER 6Data Structures143

6.1 Why Do We Need Data Structures？143

6.2Stacks145

6.2.1 Stacks and Computer Languages147

6.3 Queues148

6.4 Linked Lists150

6.5 General Trees155

6.6 Binary Search Trees157

6.7 Hash Tables161

6.8 Priority Queues163

Summary166

Objects of the Game167

Common Errors168

On the Internet168

Exercises169

References172

CHAPTER 7Recursion173

7.1 What Is Recursion？173

7.2 Background：Proofs by Mathematical Induction174

7.3Basic Recursion177

7.3.1 Printing Numbers in Any Base179

7.3.2 Why It Works180

7.3.3 How It Works182

7.3.4 Too Much Recursion Can Be Dangerous183

7.3.5 Additional Examples185

7.4Numerical Applications189

7.4.1 Modular Arithmetic190

7.4.2 Modular Exponentiation190

7.4.3 Greatest Common Divisor and Multiplicative Inverses192

7.4.4 The RSA Cryptosystem194

7.5Divide-and-Conquer Algorithms197

7.5.1 The Maximum Contiguous Subsequence Sum Problem197

7.5.2 Analysis of a Basic Divide-and-Conquer Recurrence199

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

7.6 Dynamic Programming207

7.7 Backtracking Algorithms211

Summary214

Objects of the Game215

Common Errors217

On the Internet217

Exercises218

References221

CHAPTER 8Sorting Algorithms223

8.1 Why Is Sorting Important？223

8.2 Preliminaries225

8.3 Analysis of the Insertion Sort and Other Simple Sorts225

8.4Shellsort227

8.4.1 Performance of Shellsort229

8.5Mergesort231

8.5.1 Linear-time Merging of Sorted Arrays231

8.5.2 The Mergesort Algorithm234

8.6Quicksort235

8.6.1 The Quicksort Algorithm235

8.6.2 Analysis of Quicksort236

8.6.3 Picking the Pivot240

8.6.4 A Partitioning Strategy241

8.6.5 Keys Equal to the Pivot244

8.6.6 Median-of-three Partitioning244

8.6.7 Small Arrays245

8.6.8 Java Quicksort Routine246

8.7 Quickselect248

8.8 A Lower Bound for Sorting250

Summary251

Objects of the Game251

Common Errors252

On the Internet252

Exercises253

References256

CHAPTER 9Randomization259

9.1 Why Do We Need Random Numbers？259

9.2 Random-number Generators260

9.3 Nonuniform Random Numbers265

9.4 Generating a Random Permutation268

9.5 Randomized Algorithms269

9.6 Randomized Primality Testing271

Summary275

Objects of the Game275

Common Errors276

On the Internet277

Exercises277

References279

Part Ⅲ：Applications283

CHAPTER10 Fun and Games283

10.1 Word Search Puzzles283

10.1.1Theory283

10.1.2 Java Implementation288

10.2 The Game of Tic-Tac-Toe292

10.2.1Alpha-beta Pruning292

10.2.2 Transposition Tables293

10.2.3 Computer Chess298

Summary299

Objects of the Game299

Common Errors300

On the Internet300

Exercises300

References302

CHAPTER 11Stacks and Compilers303

11.1 Balanced-symbol Checker303

11.1.1Basic Algorithm303

11.1.2 Implementation306

11.2 A Simple Calculator313

11.2.1Postfix Machines314

11.2.2 Infix to Postfix Conversion316

11.2.3 Implementation318

11.2.4 Expression Trees326

Summary327

Objects of the Game327

Common Errors328

On the Internet328

Exercises329

References330

CHAPTER 12Utilities331

12.1 File Compression331

12.1.1Prefix Codes332

12.1.2 Huffman’s Algorithm334

12.1.3 The Encoding Phase337

12.1.4 Decoding Phase337

12.1.5 Practical Considerations338

12.2 A Cross-reference Generator338

12.2.1Basic Ideas339

12.2.2 Java Implementation339

Summary343

Objects of the Game345

Common Errors345

On the Internet345

Exercises345

References348

CHAPTER13 Simulation349

13.1 The Josephus Problem349

13.1.1The Simple Solution350

13.1.2 A More Efficient Algorithm352

13.2 Event-driven Simulation354

13.2.1Basic Ideas354

13.2.2 Example：A Modem Bank Simulation356

Summary363

Objects of the Game363

Common Errors364

On the Internet364

Exercises364

CHAPTER14 Graphs and Paths367

14.1 Definitions367

14.1.1Representation369

14.2 Unweighted Shortest-path Problem379

14.2.1Theory382

14.2.2 Java Implementation386

14.3 Positive-weighted，Shortest-path Problem387

14.3.1Theory：Dijkstra’s Algorithm387

14.3.2 Java Implementation390

14.4 Negative-weighted，Shortest-path Problem393

14.4.1Theory393

14.4.2 Java Implementation395

14.5 Path Problems in Acyclic Graphs395

14.5.1Topological Sorting396

14.5.2 Theory of the Acyclic Shortest-path Algorithm398

14.5.3 Java Implementation399

14.5.4 An Application：Critical-path Analysis399

Summary403

Objects of the Game403

Common Errors405

On the Internet405

Exercises405

References408

Part Ⅳ：Implementations411

CHAPTER15 Stacks and Queues411

15.1 Dynamic Array Implementations411

15.1.1Stacks411

15.1.2 Queues416

15.2 Linked-list Implementations421

15.2.1Stacks422

15.2.2 Queues426

15.3 Comparison of the Two Methods428

15.4 Double-ended Queues428

Summary429

Objects of the Game430

Common Errors430

On the Internet430

Exercises430

CHAPTER16 Linked Lists433

16.1 Basic Ideas433

16.1.1Header Nodes435

16.1.2 Iterator Classes436

16.2 Java Implementation437

16.3 Doubly Linked Lists and Circular Linked Lists445

16.4 Sorted Linked Lists447

Summary450

Objects of the Game450

Common Errors450

On the Internet451

Exercises451

CHAPTER 17Trees455

17.1 General Trees455

17.1.1Definitions455

17.1.2 Implementation457

17.1.3 An Application：File Systems459

17.2 Binary Trees463

17.3 Recursion and Trees468

17.4 Tree Traversal：Iterator Classes471

17.4.1Postorder Traversal474

17.4.2 Inorder Traversal477

17.4.3 Preorder Traversal477

17.4.4 Level-order Traversals481

Summary483

Objects of the Game483

Common Errors484

On the Internet484

Exercises485

CHAPTER 18Binary Search Trees489

18.1 Basic Ideas489

18.1.1The Operations490

18.1.2 Java Implementation494

18.2 Order Statistics500

18.2.1Java Implementation500

18.3 Analysis of Binary Search Tree Operations504

18.4 AVL Trees508

18.4.1Properties509

18.4.2 Single Rotation511

18.4.3 Double Rotation512

18.4.4 Summary of AVL Insertion515

18.5 Red-Black Trees517

18.5.1Bottom-up Insertion518

18.5.2 Top-down Red-Black Trees520

18.5.3 Java Implementation522

18.5.4 Top-down Deletion526

18.6 AA-Trees530

18.6.1Insertion532

18.6.2 Deletion536

18.6.3 Java Implementation537

18.7 B-Trees540

Summary545

Objects of the Game546

Common Errors547

On the Internet547

Exercises548

References550

CHAPTER19 Hash Tables553

19.1 Basic Ideas553

19.2 Hash Function554

19.3 Linear Probing557

19.3.1Naive Analysis of Linear Probing558

19.3.2 What Really Happens：Primary Clustering560

19.3.3 Analysis of the f ind Operation560

19.4 Quadratic Probing562

19.4.1Java Implementation568

19.4.2 Analysis of Quadratic Probing572

19.5 Separate Chaining Hashing573

Summary573

Objects of the Game575

Common Errors575

On the Internet576

Exercises576

References578

CHAPTER 20A Priority Queue：The Binary Heap581

20.1 Basic Ideas581

20.1.1Structure Property582

20.1.2 Heap-order Property584

20.1.3 Allowed Operations584

20.2 Implementation of the Basic Operations588

20.2.1insert588

20.2.2 deleteMin591

20.3 fixHeap：Linear Time Heap Construction593

20.4 Advanced Operations：decreasekey and merge598

20.5 Internal Sorting：Heapsort598

20.6 External Sorting601

20.6.1Why We Need New Algorithms601

20.6.2 Model for External Sorting602

20.6.3 The Simple Algorithm602

20.6.4 Multiway Merge604

20.6.5 Polyphase Merge604

20.6.6 Replacement Selection607

Summary608

Objects of the Game608

Common Errors609

On the Internet610

Exercises610

References612

Part Ⅴ：Advanced Data Structures617

CHAPTER 21Splay Trees617

21.1 Self-adjustment and Amortized Analysis617

21.1.1Amortized Time Bounds618

21.1.2 A Simple Self-adjusting Strategy （That Does Not Work）619

21.2 The Basic Bottom-up Splay Tree621

21.3 Basic Splay Tree Operations623

21.4 Analysis of Bottom-up Splaying624

21.4.1Proof of the Splaying Bound627

21.5 Top-down Splay Trees630

21.6 Implementation of Top-down Splay Trees633

21.7 Comparison of the Splay Tree with Other Search Trees636

Summary640

Objects of the Game640

Common Errors640

On the Internet641

Exercises641

References642

CHAPTER 22Merging Priority Queues643

22.1 The Skew Heap643

22.1.1Merging Is Fundamental643

22.1.2 Simplistic Merging of Heap-ordered Trees644

22.1.3 The Skew Heap：A Simple Modification645

22.1.4 Analysis of the Skew Heap646

22.2 The Pairing Heap648

22.2.1Pairing Heap Operations and Theory649

22.2.2 Implementation of the Pairing Heap651

22.2.3 Application：Dijkstra’s Shortest Weighted Path Algorithm660

Summary660

Objects of the Game661

Common Errors661

On the Internet661

Exercises661

References662

CHAPTER 23The Disjoint Set Class665

23.1 Equivalence Relations665

23.2 Dynamic Equivalence and Two Applications666

23.2.1Application #1：Minimum Spanning Trees667

23.2.2 Application #2：The Nearest Common Ancestor Problem669

23.3 The Quick-find Algorithm672

23.4 The Quick-union Algorithm674

23.4.1Smart Union Algorithms676

23.4.2 Path Compression677

23.5 Java Implementation679

23.6 Worst Case for Union-by-rank and Path Compression681

23.6.1Analysis of the Union/Find Algorithm682

Summary689

Objects of the Game689

Common Error690

On the Internet690

Exercises690

References692

APPENDICES697

APPENDIXAJava Platforms697

A.1Setting the Environment697

A.1.1 Unix Instructions698

A.1.2 Windows 95/NT Instructions699

A.2 Sun’s JDK700

A.3 Visual Development Environments700

A.3.1Symantec Cafe701

A.3.2 Microsoft Visual J++707

APPENDIX B Operators713

APPENDIX CSome Library Routines715

C.1Classes in Package java.lang715

C.1.1 Character715

C.1.2 Integer716

C.1.3 Object717

C.1.4 String718

C.1.5 StringBuffer719

C.1.6 System721

C.1.7 Thread723

C.1.8 Throwable723

C.2 Classes in Package java.io724

C.2.1BufferedReader724

C.2.2 File725

C.2.3 FileReader726

C.2.4 InputStreamReader726

C.2.5 PushbackReader727

C.3Classes in Package java.util727

C.3.1 Random728

C.3.2 StringTokenizer728

C.3.3 Vector730

On the Internet730

APPENDIXDGraphical User Interfaces731

D.1 The Abstract Window Toolkit731

D.2 Basic Objects in the AWT732

D.2.1Component733

D.2.2 Container734

D.2.3 Top-level Windows734

D.2.4 Panel736

D.2.5 Important I/O Components736

D.3 Basic AWT Principles741

D.3.1Layout Managers741

D.3.2 Graphics745

D.3.3 Events747

D.3.4 Summary：Putting the Pieces Together750

D.4 Animations and Threads750

D.5 Applets753

D.5.1Hypertext Markup Language753

D.5.2 Parameters756

D.5.3 Applet Limitations756

D.5.4 Making an Application an Applet758

D.5.5 Applets with Animation760

Summary762

Objects of the Game762

Common Errors764

On the Internet765

Exercises766

Reference768

Index769