JavaStructures数据结构Java描述：英文PDF电子书下载

0 Introduction 1

0．1 Read Me 1

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

1 The Object-Oriented Method 5

1．1 Data Abstractin and Encapsulation 5

1．2 The Object Model 7

1．3 Object-Oriented Terminology 8

1．4 Sketching an Example: A Word List 10

1．5 A Special Purpose Class:A Bank Account 12

1．6 A General Purpose Class:An Association 15

1．7 Interfaces 18

1．8 Who Is the User? 19

1．9 Conclusions 20

2 Comments, Conditions, and Assertions 25

2．1 Pre-and Postconditions 26

2．2 Assertions 26

2．3 Craftsmanship 28

2．4 Conclusions 28

3 Vectors 31

3．1 Application:The Word List Revisited 33

3．2 Application:Word Frequency 34

3．3 The Interface 36

3．4 The Implementation 38

3．5 Extensibility: A Feature 41

3．6 Application: The Matrix Class 43

3．7 Conclusions 47

4 Design Fundamentals 49

4．1 Asymptotic Analysis Tools 49

4．1．1 Time and Space Complexity 50

4．1．2 Examples 53

4．1．3 The Trading of Time and Space 57

4．2 Self-Reference 58

4．2．1 Recursion 58

4．2．2 Mathematical Induction 65

4．3 Properties of Design 70

4．3．1 Symmetry 70

4．3．2 Friction 72

4．4 Conclusions 72

5 Sorting 77

5．1 Approaching the Problem 77

5．2 Selection Sort 80

5．3 Insertion Sort 82

5．4 Mergesort 85

5．5 Quicksort 89

5．6 Sorting Objects 92

5．7 Vector-Based Sorting 95

5．8 Conclusions 96

6 Lists 99

6．1 Example: A Unique Program 101

6．2 Example:Free-Lists 102

6．3 Implementation:Singly-Linked Lists 105

6．4 Implementation:Doubly-Linked Lists 116

6．5 Implementation:Circularly-Linked Lists 121

6．6 Conclusions 124

7 Linear Structures 127

7．1 Stacks 127

7．1．1 Example: Simulating Recursion 128

7．1．2 Vector-Based Stacks 132

7．1．3 List-Based Stacks 134

7．1．4 Comparisons 136

7．2 Queues 136

7．2．1 Example:Solving a Coin ruzzle 137

7．2．2 List-Based Queues 140

7．2．3 Vector-Based Queues 142

7．2．4 Array-Based Queues 145

7．3 Example: Solving Mazes 149

7．4 Conclusions 152

8 Iterators 155

8．1 Java s Enumeration Interface 155

8．2 The Iterator Interface 157

8．3 Example: Vector Iterators 158

8．4 Example: List Iterators 160

8．5 Example: Filtering Iterators 162

8．6 Conclusions 165

9 Ordered Structures 167

9．1 Comparable Objects 167

9．1．1 Example: Comparable Integers 168

9．1．2 Example: Comparable Associations 170

9．2 Keeping Structures Ordered 172

9．2．1 The OrderedStructure Interface 173

9．2．2 The Ordered Vector 173

9．2．4 The Ordered List 179

9．2．3 Example: Sorting 179

9．2．5 Example: The Modified Parking Lot 183

9．3 Conclusions 184

10 Trees 187

10．1 Terminology 187

10．2 The Interface 190

10．3 Motivating Example: Expression Trees 192

10．4 Implementation 194

10．4．1 The BinaryTreeNode Implementation 194

10．4．2 Implementation of the BinaryTree Wrapper 197

10．5 Traversals 201

10．5．1 Preorder Traversal 202

10．5．2 Inorder Traversal 204

10．5．3 Postorder Traversal 206

10．5．4 Levelorder Traversal 207

10．5．5 Recursion in Iterators 209

10．6 Property-Based Methods 210

10．7 Example: Huffman Compression 214

10．8 Conclusions 219

11．1 The Interface 223

11 Priority Queues 223

11．2 Example:Improving the Huffman Code 224

11．3 Priority Vectors 225

11．4 A Heap Implementation 227

11．4．1 Vector-Based Heaps 228

11．4．2 Example: Heapsort 236

11．4．3 Skew Heaps 237

11．5 Example: Circuit Simulation 241

11．6 Conclusions 244

12．1 Binary Search Trees 249

12 Search Trees 249

12．2 Example: Tree Sort 251

12．3 Implementation 251

12．4 Splay Trees 257

12．5 Splay Tree Implementation 260

12．6 Conclusions 264

13 Dictionaries 267

13．1 The Interface 267

13．2 Unit Cost Dictionaries: Hash Tables 268

13．2．1 Open Addressing 269

13．2．2 External Chaining 277

13．2．3 Generation of Hash Codes 279

13．2．4 Analysis 285

13．3 Ordered Dictionaries and Tables 285

13．4 Example: Document Indexing 287

13．5 Conclusions 291

14 Graphs 293

14．1 Terminology 293

14．2 The Graph Interface 294

14．3．1 Abstract Classes 298

14．3 Implementations 298

14．3．2 Adjacency Matrices 300

14．3．3 Adjacency Lists 306

14．4 Examples: Common Graph Algorithms 312

14．4．1 Reachability 312

14．4．2 Topological Sorting 315

14．4．3 Transitive Closure 317

14．4．4 All Pairs Minimum Distance 318

14．4．5 Greedy Algorithms 319

14．5 Conclusions 324

A．1 A First Program 329

A A Sip of Java 329

A．2 Declarations 331

A．2．1 Primitive Types 331

A．2．2 Reference Types 333

A．3 Important Classes 334

A．3．1 The ReadStream Class 334

A．3．2 PrintStreams 335

A．3．3 Strings 335

A．4 Control Constructs 336

A．4．1 Conditional Statements 336

A．4．2 Loops 337

A．5 Methods 339

A．6 Inheritance and Subtyping 340

A．6．1 Inheritance 340

A．6．2 Subtyping 341

A．6．3 Interfaces and Abstract Classes 342

B Use of the Keyword Protected 345

C Principles 349

D Structure Package Hierarchy 351

E Selected Answers 355

Index 363