دانلود کتاب Data Structures Outside-In with Java

فهرست مطالب :

Cover......Page 1
Contents......Page 14
Preface......Page 6
List of Class Files......Page 12
1 Object-Oriented Programming in Java......Page 22
1.1.2 Lifetime, State, and Messages......Page 23
1.2 Classes......Page 24
1.2.2 Method Overloading......Page 26
1.2.3 Object Creation, Constructors, Garbage Collection......Page 27
1.2.5 Static Fields and Methods......Page 30
1.2.6 Object References......Page 33
1.3.1 Superclass and Subclass......Page 34
1.3.2 Inherited and Specialized Fields......Page 36
1.3.4 Object Creation......Page 37
1.3.5 Inherited and Specialized Methods......Page 38
1.4 The Object Class......Page 39
1.4.1 The equals Method......Page 40
1.4.3 The clone Method......Page 42
1.5 Exceptions......Page 43
1.5.1 Interpreting an Exception Message......Page 44
1.5.2 Homegrown Error Handling......Page 47
1.5.3 Throwing an Exception......Page 52
1.5.4 Catching an Exception......Page 54
1.5.5 Exception Class......Page 59
1.6.1 Terminal-Driven IO......Page 61
1.6.2 File-Based IO......Page 63
1.6.3 StringTokenizing......Page 67
1.7 Class Packages......Page 69
1.7.1 Java Packages......Page 70
1.7.2 Organizing Packages......Page 71
1.7.3 Name Conflict Resolution......Page 75
1.8.1 Private Access......Page 76
1.8.4 Public Access......Page 77
1.9 Polymorphism......Page 78
1.9.1 Polymorphic Reference......Page 79
1.9.2 Castingupthe Class Hierarchy......Page 80
1.9.3 Casting Down the Class Hierarchy......Page 81
1.9.4 The instance of Operator......Page 82
1.10.1 Abstract Class Shape......Page 83
1.10.2 Abstract Class Properties......Page 84
1.11 A Game Park Example......Page 85
1.12.2 Implementing an Interface......Page 88
1.12.4 The Need for Interfaces......Page 89
1.13 Generics......Page 91
1.13.1 Using java.util.ArrayList for Collections......Page 93
1.13.2 The java.util.ArrayList Public Interface......Page 94
1.13.3 Implementing a Generic Class......Page 95
1.13.4 Implementing a Generic Interface......Page 96
1.13.5 Static Template Methods......Page 99
1.14 Summary......Page 101
1.15 Exercises......Page 103
1.16 Programming Problems......Page 105
2 The Big Picture......Page 109
2.2 What Data Structures Do We Study?......Page 110
2.3 What Are Abstract Data Types?......Page 113
2.4 WhyOOP and Java for Data Structures?......Page 115
2.5 How Do I choose the Right Data Structures?......Page 117
3.1 Polynomial Arithmetic: A Running Example......Page 120
3.2 Basic Operations......Page 122
3.3 Input Size......Page 124
3.4 Asymptotic Growth of Functions......Page 125
3.5 Order and Big Oh......Page 127
3.5.1 Typical Running-Time Orders......Page 129
3.5.2 Multi-Variable Order......Page 131
3.5.3 Relative Order......Page 132
3.6 Worst-Case and Average......Page 133
3.7 Summary......Page 136
3.8 Exercises......Page 137
4 Unordered List......Page 140
4.1 Unordered List Properties......Page 141
4.2 Sequential Search......Page 142
4.2.1 Average Case Analysis......Page 143
4.2.2 Rearranging Data Based on Search Patterns......Page 145
4.3 A List Class......Page 146
4.4 An ExpenseList Class Using List......Page 148
4.4.2 Expense Class......Page 149
4.4.3 ExpenseList Class Interface......Page 151
4.4.4 ExpenseList Class Implementation......Page 152
4.4.5 Equality of Objects and Searching......Page 154
4.5 Linked List......Page 158
4.5.1 Node......Page 159
4.5.2 Insertion......Page 160
4.5.3 Deletion......Page 161
4.5.4 Access......Page 162
4.5.5 Circular Linked List......Page 163
4.6 A Linked List Class......Page 166
4.7 List Class Implementation......Page 171
4.8 Summary......Page 173
4.9 Exercises......Page 174
4.10 Programming Problems......Page 176
5 Ordered List......Page 180
5.1 Introduction......Page 181
5.2.1 Divide in Half......Page 182
5.2.2 Algorithm......Page 183
5.3 Ordering: Interface java.lang.Comparable......Page 185
5.4 An Ordered List Class......Page 187
5.5 Merging Ordered Lists......Page 191
5.5.1 Two-Finger Merge Algorithm......Page 192
5.6 List Consolidation Using Ordered List......Page 195
5.6.1 Merger: A Utility Class......Page 196
5.6.2 A Consolidation Class......Page 198
5.7 Ordered List Class Implementation......Page 200
5.8 Summary......Page 203
5.9 Exercises......Page 204
5.10 Programming Problems......Page 208
6.1 Queue Properties......Page 210
6.2 UNIX Print Queue......Page 212
6.3 A Queue Class......Page 213
6.4 A Print Queue Class Using Queue......Page 214
6.5.1 Design1:Using Array-Based Storage......Page 219
6.5.2 Design 2: Using Linked List......Page 222
6.7 Exercises......Page 224
6.8 Programming Problems......Page 226
7.1 Stack Properties......Page 228
7.2 Stack Applications......Page 229
7.2.2 Postfix Expression Evaluation......Page 230
7.2.3 Infix toPostfix Conversion......Page 233
7.4 A Postfix Expression Evaluation Package......Page 234
7.4.1 Class Postfix Evaluator......Page 235
7.4.2 Class StatusKeeper......Page 237
7.4.3 Class StackKeeper......Page 238
7.4.4 Class PostfixEvaluator Implementation......Page 240
7.5.2 Design2: Linked List for Storage......Page 243
7.7 Exercises......Page 245
7.8 Programming Problems......Page 247
8 Recursion......Page 250
8.1.1 List......Page 251
8.1.3 Factorial Function......Page 253
8.1.4 Fibonacci Sequence......Page 254
8.2.1 Computing the Factorial......Page 255
8.2.3 Recursion with Linked Lists......Page 258
8.3 Recursion on an Array:Binary Search......Page 261
8.4.1 A Recursive Definition......Page 262
8.5 Recursion and Stacks......Page 265
8.7 Tail Recursion......Page 267
8.9 Exercises......Page 270
8.10 Programming Problems......Page 272
9 Binary Tree and General Tree......Page 275
9.1.1 Components......Page 276
9.1.2 Position as Meaning......Page 277
9.1.3 Structure......Page 278
9.1.4 Recursive Definitions......Page 280
9.2 Binary Tree Traversals......Page 282
9.3 A Binary Tree Class......Page 285
9.4 Storing and Recreating a Binary Tree......Page 288
9.4.1 Signature of a Binary Tree......Page 289
9.4.2 Building a Binary Treefromits Signature......Page 290
9.5.1 Statistical and Dictionary Coding......Page 292
9.5.2 Algorithm......Page 293
9.5.3 Average Code Length and Prefix Property......Page 295
9.5.4 A Huffman Class Using BinaryTree......Page 296
9.6 BinaryTreeClass Implementation......Page 303
9.7.1 Inorder Traversal of Binary Tree......Page 306
9.8 General Tree......Page 308
9.8.2 Example:UNIX Filesystem......Page 309
9.8.4 Correspondence with Binary Tree......Page 311
9.8.5 Signature of General Tree......Page 312
9.9 Summary......Page 313
9.10 Exercises......Page 315
9.11 Programming Problems......Page 318
10 Binary Search Tree and AVL Tree......Page 322
10.1 Comparison Tree......Page 323
10.1.1 Search Time Using Comparison Tree......Page 324
10.1.2 Height of Comparison Tree......Page 326
10.2 Binary Search Tree Properties......Page 327
10.3.3 Delete......Page 329
10.4 A Binary Search Tree Class......Page 332
10.5.1 Example: Treesort......Page 334
10.5.2 Example: Counting Keys......Page 335
10.6 Binary Search Tree Class Implementation......Page 337
10.6.2 Insert Implementation......Page 338
10.6.3 Delete Implementation......Page 339
10.6.4 Convenience Methods and Traversals......Page 342
10.7.1 AVL Tree Structure......Page 343
10.7.3 Rotation......Page 345
10.7.4 Insertion......Page 346
10.7.5 Deletion......Page 349
10.7.7 AVL Insert and Delete: Generalization......Page 355
10.8 Binary Search: Average Number of Comparisons......Page 359
10.9 Summary......Page 361
10.10 Exercises......Page 362
10.11 Programming Problems......Page 365
11.1 Heapas Priority Queue......Page 368
11.2 Heap Properties......Page 369
11.2.1 Maxand Min Heaps......Page 370
11.3.1 Insert......Page 371
11.3.2 Delete......Page 372
11.5.1 Overview......Page 373
11.5.2 A Scheduling Package Using Heap......Page 376
11.6.1 Example: Sorting Integers......Page 383
11.7.1 Array Storage......Page 384
11.7.2 Implementation Using Array List......Page 386
11.8.1 Designing an Updatable Heap......Page 389
11.8.3 Shared Handle Array......Page 390
11.8.4 Encapsulating Handles within a Heap......Page 391
11.9 Summary......Page 392
11.10 Exercises......Page 393
11.11 Programming Problems......Page 394
12.1 Motivation......Page 397
12.2 Hashing......Page 399
12.3 Collision Resolution......Page 400
12.3.1 Linear Probing......Page 401
12.3.2 Quadratic Probing......Page 402
12.3.3 Chaining......Page 403
12.3.4 Comparison of Running Times......Page 404
12.4 The java.util.HashMap Class......Page 405
12.4.1 Table and Load Factor......Page 406
12.4.2 Storage of Entries......Page 407
12.4.3 Adding an Entry......Page 408
12.4.4 Rehashing......Page 410
12.5 Quadratic Probing: Repetition of Probe Locations......Page 412
12.6 Summary......Page 413
12.7 Exercises......Page 414
12.8 Programming Problems......Page 415
13.1 Insertion Sort......Page 417
13.2.1 Quicksort......Page 421
13.2.2 Mergesort......Page 427
13.3 Heapsort......Page 429
13.3.1 Building a Heapin Linear Time......Page 430
13.3.2 Sorting a Heap......Page 432
13.4 Radix Sort......Page 433
13.5 Implementation: A Quicksort Class......Page 435
13.6 Heap Build: Linear Running Time......Page 438
13.7 Summary......Page 439
13.8 Exercises......Page 440
13.9 Programming Problems......Page 442
14.1 Modeling Relationships Using Graphs......Page 444
14.1.1 Undirected Graphs......Page 445
14.1.2 Directed Graphs......Page 446
14.1.3 Weighted Graphs......Page 449
14.2 Graph Representation......Page 450
14.3.1 Depth-First Search for Undirected Graphs......Page 452
14.3.2 Breadth-First Search for Undirected Graphs......Page 454
14.3.3 Traversal Driver......Page 455
14.3.4 Traversals for Directed Graphs......Page 457
14.4.1 Partial and Total Order......Page 458
14.4.2 Topological Numbering......Page 459
14.4.3 Topological Sorting Using Depth-First Search......Page 460
14.4.4 Topological Sorting Using Breadth-First Search......Page 462
14.5 Connected Components of an Undirected Graph......Page 463
14.6.1 Dijkstra’s Single-Source Algorithm......Page 464
14.8 Exercises......Page 472
15 Graphs II: Implementation......Page 476
15.1 A Directed Graph Class: DirGraph......Page 477
15.1.1 Vertex Numbering......Page 478
15.1.2 Neighbor Class......Page 479
15.1.3 Exercising the DirGraph Class......Page 480
15.2 An Undirected Graph Class: UndirGraph......Page 482
15.3.1 Design and Interface......Page 484
15.3.2 Visitor Class......Page 485
15.3.3 DFS Implementation......Page 486
15.4.1 TopVisitor: Extending the Visitor Class......Page 488
15.4.2 DFSTopsort Implementation......Page 489
15.5.1 ConnVisitor: Extending the Visitor Class......Page 490
15.6 A Shortest-Paths Class: ShortestPaths......Page 491
15.6.1 Weighted Neighbor: Extending the Neighbor Class......Page 492
15.6.2 Shortest Paths Implementation......Page 493
15.7 Graph Implementation......Page 497
15.7.1 DirGraph Implementation......Page 498
15.7.2 UndirGraph Class Implementation......Page 501
15.7.3 Implementation of Weighted Graphs......Page 502
15.8 Summary......Page 503
15.9 Programming Problems......Page 504
B......Page 506
D......Page 507
H......Page 508
O......Page 509
R......Page 510
S......Page 511
Z......Page 512