GO TO
Data Structures and Algorithms in Java, 4th Edition
by
Goodrich, Michael T., University of California, Irvine ; Tamassia, Roberto, Brown University
Publisher: John Wiley & Sons
Publishing Date: 2005/08/24
eText ISBN-10
0-470-19001-9
eText ISBN-13
978-0-470-19001-2
Print ISBN-10
0-471-73884-0
Print ISBN-13
978-0-471-73884-8
« Back to My CourseSmart
Data Structures and Algorithms in Java, 4th Edition
by
Goodrich, Michael T., University of California, Irvine ; Tamassia, Roberto, Brown University
eTextbook $63.50
(180 day subscription)
Compare Online & Downloadable
Copyright, iv
Preface to the Fourth Edi...
1. Java Programming Basic...
2. Object-Oriented Design...
3. Arrays, Linked Lists, ...
4. Analysis Tools, 153
5. Stacks and Queues, 187
6. Lists and Iterators, 2...
7. Trees, 265
8. Priority Queues, 319
9. Maps and Dictionaries,...
10. Search Trees, 417
11. Sorting, Sets, and Se...
12. Text Processing, 539
13. Graphs, 579
14. Memory, 649
A Useful Mathematical Fac...
Bibliography, 681
Index, 687
Table of Contents
Copyright, iv
Preface to the Fourth Edition, vii
1. Java Programming Basics, 1
1.1. Getting Started: Classes, Types, and Objects, 2
1.1.1. Base Types, 5
1.1.2. Objects, 7
1.1.3. Enum Types, 14
1.2. Methods, 15
1.3. Expressions, 20
1.3.1. Literals, 20
1.3.2. Operators, 21
1.3.3. Casting and Autoboxing/Unboxing in Expressions, 25
1.4. Control Flow, 27
1.4.1. The If and Switch Statements, 27
1.4.2. Loops, 29
1.4.3. Explicit Control-Flow Statements, 32
1.5. Arrays, 34
1.5.1. Declaring Arrays, 36
1.5.2. Arrays are Objects, 37
1.6. Simple Input and Output, 39
1.7. An Example Program, 42
1.8. Nested Classes and Packages, 45
1.9. Writing a Java Program, 47
1.9.1. Design, 47
1.9.2. Pseudo-Code, 48
1.9.3. Coding, 49
1.9.4. Testing and Debugging, 53
1.10. Exercises, 55
2. Object-Oriented Design, 57
2.1. Goals, Principles, and Patterns, 58
2.1.1. Object-Oriented Design Goals, 58
2.1.2. Object-Oriented Design Principles, 59
2.1.3. Design Patterns, 62
2.2. Inheritance and Polymorphism, 63
2.2.1. Inheritance, 63
2.2.2. Polymorphism, 65
2.2.3. Using Inheritance in Java, 66
2.3. Exceptions, 76
2.3.1. Throwing Exceptions, 76
2.3.2. Catching Exceptions, 78
2.4. Interfaces and Abstract Classes, 80
2.4.1. Implementing Interfaces, 80
2.4.2. Multiple Inheritance in Interfaces, 83
2.4.3. Abstract Classes and Strong Typing, 84
2.5. Casting and Generics, 85
2.5.1. Casting, 85
2.5.2. Generics, 89
2.6. Exercises, 91
3. Arrays, Linked Lists, and Recursion, 95
3.1. Using Arrays, 96
3.1.1. Storing Game Entries in an Array, 96
3.1.2. Sorting an Array, 103
3.1.3. java.util Methods for Arrays and Random Numbers, 106
3.1.4. Simple Cryptography with Strings and Character Arrays, 108
3.1.5. Two-Dimensional Arrays and Positional Games, 111
3.2. Singly Linked Lists, 115
3.2.1. Insertion in a Singly Linked List, 117
3.2.2. Removing an Element in a Singly Linked List, 119
3.3. Doubly Linked Lists, 120
3.3.1. Insertion in the Middle of a Doubly Linked List, 123
3.3.2. Removal in the Middle of a Doubly Linked List, 124
3.3.3. An Implementation of a Doubly Linked List, 125
3.4. Circularly Linked Lists and Linked-List Sorting, 128
3.4.1. Circularly Linked Lists and Duck, Duck, Goose, 128
3.4.2. Sorting a Linked List, 133
3.5. Recursion, 134
3.5.1. Linear Recursion, 140
3.5.2. Binary Recursion, 144
3.5.3. Multiple Recursion, 147
3.6. Exercises, 149
4. Analysis Tools, 153
4.1. The Seven Functions Used in This Book, 154
4.1.1. The Constant Function, 154
4.1.2. The Logarithm Function, 154
4.1.3. The Linear Function, 156
4.1.4. The N-Log-N Function, 156
4.1.5. The Quadratic Function, 156
4.1.6. The Cubic Function and Other Polynomials, 158
4.1.7. The Exponential Function, 159
4.1.8. Comparing Growth Rates, 161
4.2. Analysis of Algorithms, 162
4.2.1. Experimental Studies, 163
4.2.2. Primitive Operations, 164
4.2.3. Asymptotic Notation, 166
4.2.4. Asymptotic Analysis, 170
4.2.5. Using the Big-Oh Notation, 172
4.2.6. A Recursive Algorithm for Computing Powers, 176
4.3. Simple Justification Techniques, 177
4.3.1. By Example, 177
4.3.2. The “Contra” Attack, 177
4.3.3. Induction and Loop Invariants, 178
4.4. Exercises, 181
5. Stacks and Queues, 187
5.1. Stacks, 188
5.1.1. The Stack Abstract Data Type, 189
5.1.2. A Simple Array-Based Stack Implementation, 192
5.1.3. Implementing a Stack with a Generic Linked List, 197
5.1.4. Reversing an Array Using a Stack, 199
5.1.5. Matching Parentheses and HTML Tags, 200
5.2. Queues, 204
5.2.1. The Queue Abstract Data Type, 204
5.2.2. A Simple Array-Based Queue Implementation, 206
5.2.3. Implementing a Queue with a Generic Linked List, 210
5.2.4. Round Robin Schedulers, 211
5.3. Double-Ended Queues, 213
5.3.1. The Deque Abstract Data Type, 213
5.3.2. Implementing a Deque, 214
5.4. Exercises, 217
6. Lists and Iterators, 221
6.1. Array Lists, 222
6.1.1. The Array List Abstract Data Type, 222
6.1.2. The Adapter Pattern, 223
6.1.3. A Simple Array-Based Implementation, 224
6.1.4. A Simple Interface and the java.util.ArrayList Class, 226
6.1.5. Implementing an Array List Using Extendable Arrays, 227
6.2. Node Lists, 231
6.2.1. Node-Based Operations, 231
6.2.2. Positions, 232
6.2.3. The Node List Abstract Data Type, 232
6.2.4. Doubly Linked List Implementation, 236
6.3. Iterators, 242
6.3.1. The Iterator and Iterable Abstract Data Types, 242
6.3.2. The Java For-Each Loop, 244
6.3.3. Implementing Iterators, 245
6.3.4. List Iterators in Java, 247
6.4. List ADTs and the Collections Framework, 249
6.4.1. The Java Collections Framework, 249
6.4.2. The java.util.LinkedList Class, 250
6.4.3. Sequences, 251
6.5. Case Study: The Move-to-Front Heuristic, 253
6.5.1. Using a Sorted List and a Nested Class, 253
6.5.2. Using a List with the Move-to-Front Heuristic, 256
6.5.3. Possible Uses of a Favorites List, 257
6.6. Exercises, 260
7. Trees, 265
7.1. General Trees, 266
7.1.1. Tree Definitions and Properties, 267
7.1.2. The Tree Abstract Data Type, 270
7.1.3. Implementing a Tree, 271
7.2. Tree Traversal Algorithms, 273
7.2.1. Depth and Height, 273
7.2.2. Preorder Traversal, 276
7.2.3. Postorder Traversal, 279
7.3. Binary Trees, 282
7.3.1. The Binary Tree ADT, 284
7.3.2. A Binary Tree Interface in Java, 284
7.3.3. Properties of Binary Trees, 285
7.3.4. A Linked Structure for Binary Trees, 287
7.3.5. An Array-List Representation of a Binary Tree, 296
7.3.6. Traversals of Binary Trees, 298
7.3.7. The Template Method Pattern, 305
7.4. Exercises, 309
8. Priority Queues, 319
8.1. The Priority Queue Abstract Data Type, 320
8.1.1. Keys, Priorities, and Total Order Relations, 320
8.1.2. Entries and Comparators, 322
8.1.3. The Priority Queue ADT, 325
8.1.4. Sorting with a Priority Queue, 327
8.2. Implementing a Priority Queue with a List, 328
8.2.1. Implementation with an Unsorted List, 328
8.2.2. Implementation with a Sorted List, 328
8.2.3. Selection-Sort and Insertion-Sort, 332
8.3. Heaps, 334
8.3.1. The Heap Data Structure, 334
8.3.2. Complete Binary Trees and Their Representation, 337
8.3.3. Implementing a Priority Queue with a Heap, 342
8.3.4. A Java Heap Implementation, 347
8.3.5. Heap-Sort, 350
8.3.6. Bottom-Up Heap Construction *, 352
8.4. Adaptable Priority Queues, 356
8.4.1. Methods of the Adaptable Priority Queue ADT, 356
8.4.2. Location-Aware Entries, 357
8.4.3. Implementing an Adaptable Priority Queue, 358
8.5. Exercises, 361
9. Maps and Dictionaries, 367
9.1. The Map Abstract Data Type, 368
9.1.1. A Simple List-Based Map Implementation, 371
9.2. Hash Tables, 372
9.2.1. Bucket Arrays, 372
9.2.2. Hash Functions, 373
9.2.3. Hash Codes, 374
9.2.4. Compression Functions, 377
9.2.5. Collision-Handling Schemes, 379
9.2.6. A Java Hash Table Implementation, 383
9.2.7. Load Factors and Rehashing, 387
9.2.8. Application: Counting Word Frequencies, 388
9.3. The Dictionary Abstract Data Type, 389
9.3.1. List-Based Dictionaries and Audit Trails, 390
9.3.2. Hash Table Dictionary Implementation, 393
9.3.3. Ordered Search Tables and Binary Search, 394
9.4. Skip Lists, 398
9.4.1. Search and Update Operations in a Skip List, 400
9.4.2. A Probabilistic Analysis of Skip Lists *, 404
9.5. Extensions and Applications of Dictionaries, 407
9.5.1. Supporting Location-Aware Dictionary Entries, 407
9.5.2. The Ordered Dictionary ADT, 408
9.5.3. Flight Databases and Maxima Sets, 410
9.6. Exercises, 413
10. Search Trees, 417
10.1. Binary Search Trees, 418
10.1.1. Searching, 419
10.1.2. Update Operations, 421
10.1.3. Java Implementation, 425
10.2. AVL Trees, 429
10.2.1. Update Operations, 431
10.2.2. Java Implementation, 437
10.3. Splay Trees, 440
10.3.1. Splaying, 440
10.3.2. When to Splay, 444
10.3.3. Amortized Analysis of Splaying *, 446
10.4. (2,4) Trees, 451
10.4.1. Multi-Way Search Trees, 451
10.4.2. Update Operations for (2,4) Trees, 457
10.5. Red-Black Trees, 463
10.5.1. Update Operations, 465
10.5.2. Java Implementation, 478
10.6. Exercises, 481
11. Sorting, Sets, and Selection, 487
11.1. Merge-Sort, 488
11.1.1. Divide-and-Conquer, 488
11.1.2. Merging Arrays and Lists, 493
11.1.3. The Running Time of Merge-Sort, 496
11.1.4. Java Implementations of Merge-Sort, 497
11.1.5. Merge-Sort and Recurrence Equations *, 500
11.2. Quick-Sort, 501
11.2.1. Randomized Quick-Sort, 508
11.2.2. In-Place Quick-Sort, 510
11.3. A Lower Bound on Sorting, 513
11.4. Bucket-Sort and Radix-Sort, 515
11.4.1. Bucket-Sort, 515
11.4.2. Radix-Sort, 516
11.5. Comparison of Sorting Algorithms, 518
11.6. The Set ADT and Union/Find Structures, 520
11.6.1. A Simple Set Implementation, 521
11.6.2. Partitions with Union-Find Operations, 524
11.6.3. A Tree-Based Partition Implementation *, 526
11.7. Selection, 529
11.7.1. Prune-and-Search, 529
11.7.2. Randomized Quick-Select, 530
11.7.3. Analyzing Randomized Quick-Select, 531
11.8. Exercises, 532
12. Text Processing, 539
12.1. String Operations, 540
12.1.1. The Java String Class, 541
12.1.2. The Java StringBuffer Class, 542
12.2. Pattern Matching Algorithms, 543
12.2.1. Brute Force, 543
12.2.2. The Boyer-Moore Algorithm, 545
12.2.3. The Knuth-Morris-Pratt Algorithm, 549
12.3. Tries, 554
12.3.1. Standard Tries, 554
12.3.2. Compressed Tries, 558
12.3.3. Suffix Tries, 560
12.3.4. Search Engines, 564
12.4. Text Compression, 565
12.4.1. The Huffman Coding Algorithm, 566
12.4.2. The Greedy Method, 567
12.5. Text Similarity Testing, 568
12.5.1. The Longest Common Subsequence Problem, 568
12.5.2. Dynamic Programming, 569
12.5.3. Applying Dynamic Programming to the LCS Problem, 569
12.6. Exercises, 573
13. Graphs, 579
13.1. The Graph Abstract Data Type, 580
13.1.1. The Graph ADT, 585
13.2. Data Structures for Graphs, 586
13.2.1. The Edge List Structure, 586
13.2.2. The Adjacency List Structure, 589
13.2.3. The Adjacency Matrix Structure, 591
13.3. Graph Traversals, 593
13.3.1. Depth-First Search, 593
13.3.2. Implementing Depth-First Search, 597
13.3.3. Breadth-First Search, 605
13.4. Directed Graphs, 608
13.4.1. Traversing a Digraph, 610
13.4.2. Transitive Closure, 612
13.4.3. Directed Acyclic Graphs, 615
13.5. Weighted Graphs, 619
13.6. Shortest Paths, 620
13.6.1. Dijkstra’s Algorithm, 621
13.7. Minimum Spanning Trees, 630
13.7.1. Kruskal’s Algorithm, 632
13.7.2. The Prim-Jarník Algorithm, 636
13.8. Exercises, 639
14. Memory, 649
14.1. Memory Management, 650
14.1.1. Stacks in the Java Virtual Machine, 650
14.1.2. Allocating Space in the Memory Heap, 654
14.1.3. Garbage Collection, 656
14.2. External Memory and Caching, 658
14.2.1. The Memory Hierarchy, 658
14.2.2. Caching Strategies, 659
14.3. External Searching and B-Trees, 664
14.3.1. (
a,b
) Trees, 665
14.3.2. B-Trees, 667
14.4. External-Memory Sorting, 668
14.4.1. Multi-way Merging, 669
14.5. Exercises, 670
A Useful Mathematical Facts, 673
Bibliography, 681
Index, 687
Please use the Print button in the CourseSmart Reader header.
