《JavaStructures数据结构Java描述：英文》

0 Introduction1

0．1 Read Me1

0．2 He Can t Say That, Can He?2

1 The Object-Oriented Method5

1．1 Data Abstractin and Encapsulation5

1．2 The Object Model7

1．3 Object-Oriented Terminology8

1．4 Sketching an Example: A Word List10

1．5 A Special Purpose Class:A Bank Account12

1．6 A General Purpose Class:An Association15

1．7 Interfaces18

1．8 Who Is the User?19

1．9 Conclusions20

2 Comments, Conditions, and Assertions25

2．1 Pre-and Postconditions26

2．2 Assertions26

2．3 Craftsmanship28

2．4 Conclusions28

3 Vectors31

3．1 Application:The Word List Revisited33

3．2 Application:Word Frequency34

3．3 The Interface36

3．4 The Implementation38

3．5 Extensibility: A Feature41

3．6 Application: The Matrix Class43

3．7 Conclusions47

4 Design Fundamentals49

4．1 Asymptotic Analysis Tools49

4．1．1 Time and Space Complexity50

4．1．2 Examples53

4．1．3 The Trading of Time and Space57

4．2 Self-Reference58

4．2．1 Recursion58

4．2．2 Mathematical Induction65

4．3 Properties of Design70

4．3．1 Symmetry70

4．3．2 Friction72

4．4 Conclusions72

5 Sorting77

5．1 Approaching the Problem77

5．2 Selection Sort80

5．3 Insertion Sort82

5．4 Mergesort85

5．5 Quicksort89

5．6 Sorting Objects92

5．7 Vector-Based Sorting95

5．8 Conclusions96

6 Lists99

6．1 Example: A Unique Program101

6．2 Example:Free-Lists102

6．3 Implementation:Singly-Linked Lists105

6．4 Implementation:Doubly-Linked Lists116

6．5 Implementation:Circularly-Linked Lists121

6．6 Conclusions124

7 Linear Structures127

7．1 Stacks127

7．1．1 Example: Simulating Recursion128

7．1．2 Vector-Based Stacks132

7．1．3 List-Based Stacks134

7．1．4 Comparisons136

7．2 Queues136

7．2．1 Example:Solving a Coin ruzzle137

7．2．2 List-Based Queues140

7．2．3 Vector-Based Queues142

7．2．4 Array-Based Queues145

7．3 Example: Solving Mazes149

7．4 Conclusions152

8 Iterators155

8．1 Java s Enumeration Interface155

8．2 The Iterator Interface157

8．3 Example: Vector Iterators158

8．4 Example: List Iterators160

8．5 Example: Filtering Iterators162

8．6 Conclusions165

9 Ordered Structures167

9．1 Comparable Objects167

9．1．1 Example: Comparable Integers168

9．1．2 Example: Comparable Associations170

9．2 Keeping Structures Ordered172

9．2．1 The OrderedStructure Interface173

9．2．2 The Ordered Vector173

9．2．4 The Ordered List179

9．2．3 Example: Sorting179

9．2．5 Example: The Modified Parking Lot183

9．3 Conclusions184

10 Trees187

10．1 Terminology187

10．2 The Interface190

10．3 Motivating Example: Expression Trees192

10．4 Implementation194

10．4．1 The BinaryTreeNode Implementation194

10．4．2 Implementation of the BinaryTree Wrapper197

10．5 Traversals201

10．5．1 Preorder Traversal202

10．5．2 Inorder Traversal204

10．5．3 Postorder Traversal206

10．5．4 Levelorder Traversal207

10．5．5 Recursion in Iterators209

10．6 Property-Based Methods210

10．7 Example: Huffman Compression214

10．8 Conclusions219

11．1 The Interface223

11 Priority Queues223

11．2 Example:Improving the Huffman Code224

11．3 Priority Vectors225

11．4 A Heap Implementation227

11．4．1 Vector-Based Heaps228

11．4．2 Example: Heapsort236

11．4．3 Skew Heaps237

11．5 Example: Circuit Simulation241

11．6 Conclusions244

12．1 Binary Search Trees249

12 Search Trees249

12．2 Example: Tree Sort251

12．3 Implementation251

12．4 Splay Trees257

12．5 Splay Tree Implementation260

12．6 Conclusions264

13 Dictionaries267

13．1 The Interface267

13．2 Unit Cost Dictionaries: Hash Tables268

13．2．1 Open Addressing269

13．2．2 External Chaining277

13．2．3 Generation of Hash Codes279

13．2．4 Analysis285

13．3 Ordered Dictionaries and Tables285

13．4 Example: Document Indexing287

13．5 Conclusions291

14 Graphs293

14．1 Terminology293

14．2 The Graph Interface294

14．3．1 Abstract Classes298

14．3 Implementations298

14．3．2 Adjacency Matrices300

14．3．3 Adjacency Lists306

14．4 Examples: Common Graph Algorithms312

14．4．1 Reachability312

14．4．2 Topological Sorting315

14．4．3 Transitive Closure317

14．4．4 All Pairs Minimum Distance318

14．4．5 Greedy Algorithms319

14．5 Conclusions324

A．1 A First Program329

A A Sip of Java329

A．2 Declarations331

A．2．1 Primitive Types331

A．2．2 Reference Types333

A．3 Important Classes334

A．3．1 The ReadStream Class334

A．3．2 PrintStreams335

A．3．3 Strings335

A．4 Control Constructs336

A．4．1 Conditional Statements336

A．4．2 Loops337

A．5 Methods339

A．6 Inheritance and Subtyping340

A．6．1 Inheritance340

A．6．2 Subtyping341

A．6．3 Interfaces and Abstract Classes342

B Use of the Keyword Protected345

C Principles349

D Structure Package Hierarchy351

E Selected Answers355

Index363