Java Structures: Data Structures in Java for the Principled Programmer (2nd edition)

✍ Scribed by Duane Bailey

• Publisher: McGraw-Hill Science/Engineering/Math
• Year: 2002
• Tongue: English
• Leaves: 546
• Edition: 2nd
• Category: Library

✦ Synopsis

The second edition of Duane Bailey's Java Structures considers the design, implementation, and use of data structures using Java 2. The structure package, a collection of nearly 100 different classes implementing a wide variety of data structures, has been the basis of Java Structures for more than five years. Thousands of faculty, students, researchers, industrial and recreational programmers have investigated this lean and well tested approach to data structure design. In this edition, the text develops a heavily tested package that is independent of but consistent with the Collection package offered by Sun. In many cases, the variety of implementations provides the programmer choices of data structure that are not available with the Collection system. For those curricula that make use of the Collection package, the structure package can be easily integrated into existing applications. All classes are fully documented and make consistent use of pre- and post-conditioning, and include support for assertion testing. The second edition also brings a wealth of new resources, including a large number of new and original exercises and drill problems. Throughout the text, exercises appear in the running text to direct a deeper consideration of subtle issues by students. Perhaps the most innovative feature (first found in Bailey's Java Elements) is the inclusion of more than a dozen original lab exercises that focus on interesting and often classic problems of computer science. All code for the book's examples, documentation, and the STRUCTURE package is posted on the book's website at www.mhhe.com/javastructures.

✦ Table of Contents

Java Structures......Page 4
Copyright (c) 2005-2007 Duane A. Bailey......Page 5
Table of Contents......Page 6
Preface to First Edition......Page 14
Preface to the Second Edition......Page 16
Preface to the Root 7'' Edition......Page 18<br>0.1 Read Me......Page 20<br>0.2 He Can't Say That, Can He?......Page 21<br>1 The Object-Oriented Method......Page 24<br>1.1 Data Abstraction and Encapsulation......Page 25<br>1.2 The Object Model......Page 26<br>1.3 Object-Oriented Terminology......Page 27<br>1.4 A Special-Purpose Class: A Bank Account......Page 30<br>1.5 A General-Purpose Class: An Association......Page 33<br>1.6 Sketching an Example: A Word List......Page 37<br>1.7 Sketching an Example: A Rectangle Class......Page 39<br>1.8 Interfaces......Page 41<br>1.9 Who Is the User?......Page 43<br>1.10 Conclusions......Page 44<br>1.11 Laboratory: The Day of the Week Calculator......Page 48<br>2 Comments, Conditions, and Assertions......Page 52<br>2.2 Assertions......Page 53<br>2.3 Craftsmanship......Page 55<br>2.4 Conclusions......Page 56<br>2.5 Laboratory: Using Javadoc Commenting......Page 58<br>3 Vectors......Page 62<br>3.1 The Interface......Page 64<br>3.2 Example: The Word List Revisited......Page 66<br>3.3 Example: Word Frequency......Page 67<br>3.4 The Implementation......Page 69<br>3.5 Extensibility: A Feature......Page 72<br>3.6 Example: L-Systems......Page 75<br>3.7 Example: Vector-Based Sets......Page 76<br>3.8 Example: The Matrix Class......Page 79<br>3.9 Conclusions......Page 83<br>3.10 Laboratory: The Silver Dollar Game......Page 86<br>4 Generics......Page 88<br>4.1 Motivation (in case we need some)......Page 89<br>4.1.1 Possible Solution: Specialization......Page 90<br>4.2.1 Generic Associations......Page 91<br>4.2.2 Parameterizing the Vector Class......Page 93<br>4.2.3 Restricting Parameters......Page 98<br>4.3 Conclusions......Page 99<br>5.1 Asymptotic Analysis Tools......Page 100<br>5.1.1 Time and Space Complexity......Page 101<br>5.1.2 Examples......Page 104<br>5.1.3 The Trading of Time and Space......Page 110<br>5.1.4 Back-of-the-Envelope Estimations......Page 111<br>5.2.1 Recursion......Page 113<br>5.2.2 Mathematical Induction......Page 120<br>5.3.1 Symmetry......Page 127<br>5.4 Conclusions......Page 129<br>5.5 Laboratory: How Fast Is Java?......Page 134<br>6.1 Approaching the Problem......Page 138<br>6.2 Selection Sort......Page 141<br>6.3 Insertion Sort......Page 144<br>6.4 Mergesort......Page 146<br>6.5 Quicksort......Page 150<br>6.6 Radix Sort......Page 153<br>6.7 Sorting Objects......Page 157<br>6.8 Ordering Objects Using Comparators......Page 159<br>6.9 Vector-Based Sorting......Page 162<br>6.10 Conclusions......Page 163<br>6.11 Laboratory: Sorting with Comparators......Page 166<br>7.1 The Interface-Based Approach......Page 168<br>7.1.1 Design of the Interface......Page 169<br>7.1.2 Development of an Abstract Implementation......Page 170<br>7.2 Example: Development of Generators......Page 171<br>7.3 Example: Playing Cards......Page 174<br>7.4 Conclusions......Page 179<br>8.1 Java's Enumeration Interface......Page 180<br>8.2 The Iterator Interface......Page 182<br>8.3 Example: Vector Iterators......Page 184<br>8.4 Example: Rethinking Generators......Page 186<br>8.5 Example: Filtering Iterators......Page 189<br>8.6 Conclusions......Page 191<br>8.7 Laboratory: The Two-Towers Problem......Page 194<br>9 Lists......Page 198<br>9.1 Example: A Unique Program......Page 201<br>9.2 Example: Free Lists......Page 202<br>9.3 Partial Implementation: Abstract Lists......Page 205<br>9.4 Implementation: Singly Linked Lists......Page 207<br>9.5 Implementation: Doubly Linked Lists......Page 220<br>9.6 Implementation: Circularly Linked Lists......Page 225<br>9.8 List Iterators......Page 228<br>9.9 Conclusions......Page 230<br>9.10 Laboratory: Lists with Dummy Nodes......Page 234<br>10 Linear Structures......Page 238<br>10.1 Stacks......Page 240<br>10.1.1 Example: Simulating Recursion......Page 241<br>10.1.2 Vector-Based Stacks......Page 244<br>10.1.3 List-Based Stacks......Page 246<br>10.1.4 Comparisons......Page 247<br>10.2 Queues......Page 248<br>10.2.1 Example: Solving a Coin Puzzle......Page 250<br>10.2.2 List-Based Queues......Page 253<br>10.2.3 Vector-Based Queues......Page 254<br>10.2.4 Array-Based Queues......Page 257<br>10.3 Example: Solving Mazes......Page 261<br>10.4 Conclusions......Page 263<br>10.5 Laboratory: A Stack-Based Language......Page 266<br>10.6 Laboratory: The Web Crawler......Page 270<br>11.1 Comparable Objects Revisited......Page 272<br>11.1.1 Example: Comparable Ratios......Page 273<br>11.1.2 Example: Comparable Associations......Page 275<br>11.2.1 The OrderedStructure Interface......Page 277<br>11.2.2 The Ordered Vector and Binary Search......Page 278<br>11.2.3 Example: Sorting Revisited......Page 283<br>11.2.4 A Comparator-based Approach......Page 284<br>11.2.5 The Ordered List......Page 286<br>11.2.6 Example: The Modified Parking Lot......Page 289<br>11.3 Conclusions......Page 291<br>11.4 Laboratory: Computing theBest Of''......Page 294
12.1 Terminology......Page 296
12.2 Example: Pedigree Charts......Page 299
12.3 Example: Expression Trees......Page 300
12.4 Implementation......Page 301
12.4.1 The BinaryTree Implementation......Page 303
12.5 Example: An Expert System......Page 306
12.6 Traversals of Binary Trees......Page 309
12.6.1 Preorder Traversal......Page 310
12.6.2 In-order Traversal......Page 312
12.6.3 Postorder Traversal......Page 314
12.6.4 Level-order Traversal......Page 315
12.6.5 Recursion in Iterators......Page 316
12.7 Property-Based Methods......Page 318
12.8 Example: Huffman Compression......Page 322
12.9 Example Implementation: Ahnentafel......Page 326
12.10 Conclusions......Page 328
12.11 Laboratory: Playing Gardner's Hex-a-Pawn......Page 332
13.1 The Interface......Page 334
13.2 Example: Improving the Huffman Code......Page 336
13.3 A Vector-Based Implementation......Page 337
13.4 A Heap Implementation......Page 338
13.4.1 Vector-Based Heaps......Page 339
13.4.2 Example: Heapsort......Page 345
13.4.3 Skew Heaps......Page 348
13.5 Example: Circuit Simulation......Page 352
13.6 Conclusions......Page 356
13.7 Laboratory: Simulating Business......Page 360
14.1 Binary Search Trees......Page 362
14.3 Example: Associative Structures......Page 364
14.4 Implementation......Page 367
14.5 Splay Trees......Page 373
14.6 Splay Tree Implementation......Page 376
14.7 An Alternative: Red-Black Trees......Page 380
14.8 Conclusions......Page 382
14.9 Laboratory: Improving the BinarySearchTree......Page 386
15.1 Example Revisited: The Symbol Table......Page 388
15.2 The Interface......Page 389
15.3 Simple Implementation: MapList......Page 391
15.4 Constant Time Maps: Hash Tables......Page 393
15.4.1 Open Addressing......Page 394
15.4.2 External Chaining......Page 402
15.4.3 Generation of Hash Codes......Page 404
15.4.4 Hash Codes for Collection Classes......Page 410
15.5 Ordered Maps and Tables......Page 411
15.6 Example: Document Indexing......Page 414
15.7 Conclusions......Page 417
15.8 Laboratory: The Soundex Name Lookup System......Page 420
16.1 Terminology......Page 422
16.2 The Graph Interface......Page 423
16.3.1 Abstract Classes Reemphasized......Page 427
16.3.2 Adjacency Matrices......Page 429
16.3.3 Adjacency Lists......Page 435
16.4.1 Reachability......Page 441
16.4.2 Topological Sorting......Page 443
16.4.3 Transitive Closure......Page 446
16.4.4 All Pairs Minimum Distance......Page 447
16.4.5 Greedy Algorithms......Page 448
16.5 Conclusions......Page 453
16.6 Laboratory: Converting Between Units......Page 458
A.1 Solutions to Self Check Problems......Page 460
A.2 Solutions to Odd-Numbered Problems......Page 470
B.1 A First Program......Page 508
B.2.1 Primitive Types......Page 510
B.2.2 Reference Types......Page 512
B.3.1 The structure.ReadStream Class......Page 513
B.3.2 The java.util.Scanner Class......Page 514
B.3.3 The PrintStream Class......Page 515
B.3.4 Strings......Page 516
B.4.1 Conditional Statements......Page 517
B.4.2 Loops......Page 518
B.6.1 Inheritance......Page 521
B.6.2 Subtyping......Page 522
B.6.3 Interfaces and Abstract Classes......Page 523
B.7 Use of the Assert Command......Page 525
B.8 Use of the Keyword Protected......Page 526
C.2 Parallel Features......Page 530
C.3 Conversion......Page 531
D.1 Structure Package Hierarchy......Page 532
D.2 Principles......Page 534
Index......Page 536
Colophon......Page 545