Data Structures Outside-In with Java
Pearson (Verlag)
978-0-13-198619-0 (ISBN)
- Keine Verlagsinformationen verfügbar
- Artikel merken
Preface xv
1 Object-Oriented Programming in Java 1
1.1 Objects and Encapsulation . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.2 Lifetime, State and Messages . . . . . . . . . . . . . . . . . . . . 2
1.1.3 Clients of an Object . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.4 Separation of Interface from Implementation . . . . . . . . . . . . 3
1.2 Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 State and Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.2 Method Overloading . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.3 Object Creation, Constructors, Garbage Collection . . . . . . . . . 7
1.2.4 Method Invocation . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.5 Static Fields and Methods . . . . . . . . . . . . . . . . . . . . . . 12
1.2.6 Object References . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3 Inheritance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3.1 Superclass and Subclass . . . . . . . . . . . . . . . . . . . . . . . 17
1.3.2 Inherited and Specialized Fields . . . . . . . . . . . . . . . . . . . 19
1.3.3 Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
ii CONTENTS
1.3.4 Object Creation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.3.5 Inherited and Specialized Methods . . . . . . . . . . . . . . . . . . 22
1.3.6 Method Overriding . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.4 The Object Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.4.1 The equals Method . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4.2 The toString Method . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.4.3 The clone Method . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.5 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.5.1 Interpreting an exception message . . . . . . . . . . . . . . . . . . 29
1.5.2 Homegrown error handling . . . . . . . . . . . . . . . . . . . . . . 31
1.5.3 Throwing an exception . . . . . . . . . . . . . . . . . . . . . . . . 37
1.5.4 Catching an exception . . . . . . . . . . . . . . . . . . . . . . . . 39
1.5.5 Exception class . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
1.6 Input and Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
1.6.1 Terminal-driven IO . . . . . . . . . . . . . . . . . . . . . . . . . . 47
1.6.2 File-based IO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
1.6.3 String tokenizing . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
1.6.4 Writing an exception class . . . . . . . . . . . . . . . . . . . . . . 55
1.7 Class Packages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
1.7.1 Java packages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
1.7.2 Organizing packages . . . . . . . . . . . . . . . . . . . . . . . . . 58
1.7.3 Name conflict resolution . . . . . . . . . . . . . . . . . . . . . . . 62
1.8 Access control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
1.8.1 Private Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
1.8.2 Package Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
1.8.3 Protected Access . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
CONTENTS iii
1.8.4 Public Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
1.8.5 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
1.9 Polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
1.9.1 Polymorphic Reference . . . . . . . . . . . . . . . . . . . . . . . . 67
1.9.2 Casting Up the Class Hierarchy . . . . . . . . . . . . . . . . . . . 68
1.9.3 Casting Down the Class Hierarchy . . . . . . . . . . . . . . . . . . 69
1.9.4 The instanceof Operator . . . . . . . . . . . . . . . . . . . . . . . 70
1.10 Abstract Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
1.10.1 Abstract Class Shape . . . . . . . . . . . . . . . . . . . . . . . . . 72
1.10.2 Abstract Class Properties . . . . . . . . . . . . . . . . . . . . . . . 73
1.11 A Game Park Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
1.12 Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
1.12.1 The Java interface Construct . . . . . . . . . . . . . . . . . . . . . 78
1.12.2 Implementing an interface . . . . . . . . . . . . . . . . . . . . . . 78
1.12.3 Interface as a Type . . . . . . . . . . . . . . . . . . . . . . . . . . 79
1.12.4 The Need for Interfaces . . . . . . . . . . . . . . . . . . . . . . . 79
1.12.5 Extending Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . 81
1.13 Generics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
1.13.1 Using java.util.ArrayList for Collections . . . . . . . . . . . . . . . 83
1.13.2 The java.util.ArrayList Public Interface . . . . . . . . . . . . . . . 85
1.13.3 Implementing a Generic Class . . . . . . . . . . . . . . . . . . . . 86
1.13.4 Implementing a Generic Interface . . . . . . . . . . . . . . . . . . 87
1.13.5 Static Template Methods . . . . . . . . . . . . . . . . . . . . . . . 91
1.14 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
1.15 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
1.16 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
iv CONTENTS
2 The Big Picture 103
2.1 What Are Data Structures? . . . . . . . . . . . . . . . . . . . . . . . . . . 104
2.2 What Data Structures Do We Study? . . . . . . . . . . . . . . . . . . . . . 104
2.3 What are Abstract Data Types? . . . . . . . . . . . . . . . . . . . . . . . . 108
2.4 Why OOP and Java for Data Structures? . . . . . . . . . . . . . . . . . . . 110
2.5 How Do I Choose the Right Data Structures? . . . . . . . . . . . . . . . . 112
3 Efficiency of Algorithms 115
3.1 Polynomial Arithmetic: A Running Example . . . . . . . . . . . . . . . . 116
3.2 Basic Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
3.3 Input Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
3.4 Asymptotic Growth of Functions . . . . . . . . . . . . . . . . . . . . . . . 121
3.5 Order and Big Oh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
3.5.1 Typical Running Time Orders . . . . . . . . . . . . . . . . . . . . 125
3.5.2 Multi-variable Order . . . . . . . . . . . . . . . . . . . . . . . . . 129
3.5.3 Relative Order . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
3.5.4 Order Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
3.6 Worst-case and Average . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
3.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
4 Unordered List 141
4.1 Unordered List Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
4.2 Sequential Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
4.2.1 Average Case Analysis . . . . . . . . . . . . . . . . . . . . . . . . 144
4.2.2 Rearranging Data Based on Search Patterns . . . . . . . . . . . . . 146
4.3 A List Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
CONTENTS v
4.4 An ExpenseList Class Using List . . . . . . . . . . . . . . . . . . . . . . . 150
4.4.1 Expense Class Interface . . . . . . . . . . . . . . . . . . . . . . . 150
4.4.2 Expense Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
4.4.3 ExpenseList Class Interface . . . . . . . . . . . . . . . . . . . . . 153
4.4.4 ExpenseList Class Implementation . . . . . . . . . . . . . . . . . . 155
4.4.5 Equality of Objects and Searching . . . . . . . . . . . . . . . . . . 157
4.5 Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
4.5.1 Node . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
4.5.2 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
4.5.3 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
4.5.4 Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
4.5.5 Circular Linked List . . . . . . . . . . . . . . . . . . . . . . . . . 167
4.6 A LinkedList class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
4.7 List Class Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 177
4.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
4.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
4.10 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
5 Ordered List 187
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
5.2 Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
5.2.1 Divide In Half . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
5.2.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
5.3 Ordering: Interface java.lang.Comparable . . . . . . . . . . . . . . 193
5.4 An OrderedList Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
5.5 Merging Ordered Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
5.5.1 Two-finger Merge Algorithm . . . . . . . . . . . . . . . . . . . . . 201
vi CONTENTS
5.6 List Consolidation Using OrderedList . . . . . . . . . . . . . . . . . . . . 205
5.6.1 Merger: A Utility Class . . . . . . . . . . . . . . . . . . . . . . . 205
5.6.2 A Consolidation Class . . . . . . . . . . . . . . . . . . . . . . . . 208
5.7 OrderedList Class Implementation . . . . . . . . . . . . . . . . . . . . . . 209
5.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
5.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
5.10 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
6 Queue 223
6.1 Queue Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
6.2 UNIX Print Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
6.3 A Queue Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
6.4 A PrintQueue Class Using Queue . . . . . . . . . . . . . . . . . . . . . . . 228
6.5 Queue Class Implementation . . . . . . . . . . . . . . . . . . . . . . . . . 234
6.5.1 Design 1: Using Array-based Storage . . . . . . . . . . . . . . . . 234
6.5.2 Design 2: Using Linked List . . . . . . . . . . . . . . . . . . . . . 237
6.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
6.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
6.8 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
7 Stack 245
7.1 Stack Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
7.2 Stack Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
7.2.1 Parentheses Matching . . . . . . . . . . . . . . . . . . . . . . . . 247
7.2.2 Postfix Expression Evaluation . . . . . . . . . . . . . . . . . . . . 248
7.2.3 Infix to Postfix Conversion . . . . . . . . . . . . . . . . . . . . . . 251
7.3 A Stack Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
CONTENTS vii
7.4 A Postfix Expression Evaluation Package . . . . . . . . . . . . . . . . . . 252
7.4.1 Class PostfixEvaluator . . . . . . . . . . . . . . . . . . . . . . . . 254
7.4.2 Class StatusKeeper . . . . . . . . . . . . . . . . . . . . . . . . . . 256
7.4.3 Class StackKeeper . . . . . . . . . . . . . . . . . . . . . . . . . . 257
7.4.4 Class PostfixEvaluator Implementation . . . . . . . . . . . . . . . 260
7.5 Stack Class Implementation . . . . . . . . . . . . . . . . . . . . . . . . . 262
7.5.1 Design 1: Array List for Storage . . . . . . . . . . . . . . . . . . . 262
7.5.2 Design 2: Linked List for Storage . . . . . . . . . . . . . . . . . . 263
7.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
7.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
7.8 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
8 Recursion 271
8.1 Recursive Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
8.1.1 List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
8.1.2 Ordered List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
8.1.3 Factorial Function . . . . . . . . . . . . . . . . . . . . . . . . . . 275
8.1.4 Fibonacci Sequence . . . . . . . . . . . . . . . . . . . . . . . . . 275
8.2 Recursive Programs and Backing Out . . . . . . . . . . . . . . . . . . . . 276
8.2.1 Computing the Factorial . . . . . . . . . . . . . . . . . . . . . . . 277
8.2.2 Computing the Fibonacci Sequence . . . . . . . . . . . . . . . . . 279
8.2.3 Recursion with Linked Lists . . . . . . . . . . . . . . . . . . . . . 280
8.3 Recursion On An Array: Binary Search . . . . . . . . . . . . . . . . . . . 282
8.4 Towers of Hanoi: An Application . . . . . . . . . . . . . . . . . . . . . . 283
8.4.1 A Recursive Definition . . . . . . . . . . . . . . . . . . . . . . . . 284
8.4.2 A Recursive Program . . . . . . . . . . . . . . . . . . . . . . . . . 286
8.5 Recursion and Stacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
viii CONTENTS
8.6 Drawbacks of Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . 288
8.7 Tail Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
8.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
8.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
8.10 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
9 Binary Tree and General Tree 299
9.1 Binary Tree Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
9.1.1 Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
9.1.2 Position as Meaning . . . . . . . . . . . . . . . . . . . . . . . . . 301
9.1.3 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
9.1.4 Recursive Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 304
9.2 Binary Tree Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
9.3 A BinaryTree Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
9.4 Storing and Recreating a Binary Tree . . . . . . . . . . . . . . . . . . . . . 312
9.4.1 Signature of a Binary Tree . . . . . . . . . . . . . . . . . . . . . . 313
9.4.2 Building a Binary Tree From Its Signature . . . . . . . . . . . . . . 314
9.5 Huffman Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
9.5.1 Statistical and Dictionary Coding . . . . . . . . . . . . . . . . . . 318
9.5.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
9.5.3 Average Code Length and Prefix Property . . . . . . . . . . . . . . 320
9.5.4 A Huffman Class Using BinaryTree . . . . . . . . . . . . . . . . . 321
9.6 BinaryTree Class Implementation . . . . . . . . . . . . . . . . . . . . . . 329
9.7 Stack-based Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
9.7.1 Inorder Traversal of Binary Tree . . . . . . . . . . . . . . . . . . . 333
9.7.2 A Visitor Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
9.8 General Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
CONTENTS ix
9.8.1 Example: Hierarchy in a University . . . . . . . . . . . . . . . . . 335
9.8.2 Example: UNIX Filesystem . . . . . . . . . . . . . . . . . . . . . 336
9.8.3 Space Issues in Implementation . . . . . . . . . . . . . . . . . . . 337
9.8.4 Correspondence with Binary Tree . . . . . . . . . . . . . . . . . . 338
9.8.5 Signature of General Tree . . . . . . . . . . . . . . . . . . . . . . 340
9.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341
9.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
9.11 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
10 Binary Search Tree and AVL Tree 351
10.1 Comparison Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
10.1.1 Search Time Using Comparison Tree . . . . . . . . . . . . . . . . 353
10.1.2 Height of Comparison Tree . . . . . . . . . . . . . . . . . . . . . . 355
10.2 Binary Search Tree Properties . . . . . . . . . . . . . . . . . . . . . . . . 356
10.3 Binary Search Tree Operations . . . . . . . . . . . . . . . . . . . . . . . . 358
10.3.1 Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
10.3.2 Insert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359
10.3.3 Delete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359
10.4 A BinarySearchTree Class . . . . . . . . . . . . . . . . . . . . . . . . . . 362
10.5 Using Class BinarySearchTree . . . . . . . . . . . . . . . . . . . . . . . . 364
10.5.1 Example: Treesort . . . . . . . . . . . . . . . . . . . . . . . . . . 365
10.5.2 Example: Counting Keys . . . . . . . . . . . . . . . . . . . . . . . 366
10.6 BinarySearchTree Class Implementation . . . . . . . . . . . . . . . . . . . 367
10.6.1 Search Implementation . . . . . . . . . . . . . . . . . . . . . . . . 368
10.6.2 Insert Implementation . . . . . . . . . . . . . . . . . . . . . . . . 369
10.6.3 Delete Implementation . . . . . . . . . . . . . . . . . . . . . . . . 370
10.6.4 Convenience Methods and Traversals . . . . . . . . . . . . . . . . 373
x CONTENTS
10.7 AVL Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374
10.7.1 AVL Tree Structure . . . . . . . . . . . . . . . . . . . . . . . . . . 374
10.7.2 Search, Insert, Delete Overview . . . . . . . . . . . . . . . . . . . 376
10.7.3 Rotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
10.7.4 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377
10.7.5 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380
10.7.6 Running Times of AVL Tree Operations . . . . . . . . . . . . . . . 385
10.7.7 AVL Insert and Delete: Generalization . . . . . . . . . . . . . . . . 385
10.8 Binary Search: Average Number of Comparisons . . . . . . . . . . . . . . 389
10.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392
10.10Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393
10.11Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397
11 Heap 401
11.1 Heap as Priority Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
11.2 Heap Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
11.2.1 Max and Min Heaps . . . . . . . . . . . . . . . . . . . . . . . . . 403
11.3 Heap Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404
11.3.1 Insert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404
11.3.2 Delete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405
11.4 A Heap Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
11.5 Priority Scheduling with Heap . . . . . . . . . . . . . . . . . . . . . . . . 408
11.5.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
11.5.2 A Scheduling Package using Heap . . . . . . . . . . . . . . . . . . 410
11.6 Sorting with the Heap Class . . . . . . . . . . . . . . . . . . . . . . . . . 417
11.6.1 Example: Sorting Integers . . . . . . . . . . . . . . . . . . . . . . 418
11.7 Heap Class Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 419
CONTENTS xi
11.7.1 Array Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
11.7.2 Implementation using ArrayList . . . . . . . . . . . . . . . . . . . 422
11.8 Updatable Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425
11.8.1 Designing an Updatable Heap . . . . . . . . . . . . . . . . . . . . 425
11.8.2 Handles to heap entries . . . . . . . . . . . . . . . . . . . . . . . . 425
11.8.3 Shared handle array . . . . . . . . . . . . . . . . . . . . . . . . . . 426
11.8.4 Encapsulating handles within heap . . . . . . . . . . . . . . . . . . 427
11.8.5 Recycling free handle space . . . . . . . . . . . . . . . . . . . . . 427
11.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
11.10Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
11.11Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
12 Hash Table 433
12.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434
12.2 Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435
12.3 Collision Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436
12.3.1 Linear Probing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437
12.3.2 Quadratic Probing . . . . . . . . . . . . . . . . . . . . . . . . . . 439
12.3.3 Chaining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440
12.3.4 Comparison of Runnning Times . . . . . . . . . . . . . . . . . . . 441
12.4 The java.util.HashMap Class . . . . . . . . . . . . . . . . . . . . . . . . . 442
12.4.1 Table and Load Factor . . . . . . . . . . . . . . . . . . . . . . . . 443
12.4.2 Storage of Entries . . . . . . . . . . . . . . . . . . . . . . . . . . . 444
12.4.3 Adding an Entry . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
12.4.4 Rehashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448
12.4.5 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449
12.5 Quadratic Probing: Repetition of Probe Locations . . . . . . . . . . . . . . 450
xii CONTENTS
12.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450
12.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451
12.8 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453
13 Sorting 455
13.1 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
13.2 Sorting by Divide and Conquer . . . . . . . . . . . . . . . . . . . . . . . . 459
13.2.1 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
13.2.2 Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466
13.3 Heapsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468
13.3.1 Building a Heap in Linear Time . . . . . . . . . . . . . . . . . . . 469
13.3.2 Sorting a Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470
13.4 Radix Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
13.5 Implementation: A Quicksort Class . . . . . . . . . . . . . . . . . . . . . 474
13.6 Heap Build: Linear Running Time . . . . . . . . . . . . . . . . . . . . . . 477
13.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
13.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479
13.9 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483
14 Graphs I: Algorithms 485
14.1 Modeling Relationships using Graphs . . . . . . . . . . . . . . . . . . . . 486
14.1.1 Undirected Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 486
14.1.2 Directed Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 488
14.1.3 Weighted Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 490
14.2 Graph Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491
14.3 Graph Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493
14.3.1 Depth-first Search for Undirected Graphs . . . . . . . . . . . . . . 494
CONTENTS xiii
14.3.2 Breadth-first Search for Undirected Graphs . . . . . . . . . . . . . 495
14.3.3 Traversal Driver . . . . . . . . . . . . . . . . . . . . . . . . . . . 497
14.3.4 Traversals for Directed Graphs . . . . . . . . . . . . . . . . . . . . 498
14.4 Topological Sort on a Directed Graph . . . . . . . . . . . . . . . . . . . . 499
14.4.1 Partial and Total Order . . . . . . . . . . . . . . . . . . . . . . . . 500
14.4.2 Topological Numbering . . . . . . . . . . . . . . . . . . . . . . . 501
14.4.3 Topological Sorting Using Depth-first Search . . . . . . . . . . . . 502
14.4.4 Topological Sorting Using Breadth-first Search . . . . . . . . . . . 503
14.5 Connected Components of an Undirected Graph . . . . . . . . . . . . . . . 504
14.6 Shortest Paths in a Weighted Directed Graph . . . . . . . . . . . . . . . . . 505
14.6.1 Dijkstra’s Single-Source Algorithm . . . . . . . . . . . . . . . . . 506
14.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513
14.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514
15 Graphs II: Implementation 519
15.1 A Directed Graph Class: DirGraph . . . . . . . . . . . . . . . . . . . . . . 520
15.1.1 Vertex numbering . . . . . . . . . . . . . . . . . . . . . . . . . . . 520
15.1.2 Neighbor class . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522
15.1.3 Exercising the DirGraph Class . . . . . . . . . . . . . . . . . . . . 524
15.2 An Undirected Graph Class: UndirGraph . . . . . . . . . . . . . . . . . . 525
15.3 A Depth-first Search Class: DFS . . . . . . . . . . . . . . . . . . . . . . . 527
15.3.1 Design and Interface . . . . . . . . . . . . . . . . . . . . . . . . . 528
15.3.2 Visitor Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528
15.3.3 DFS Implementation . . . . . . . . . . . . . . . . . . . . . . . . . 531
15.4 A Topological Sort Class: DFSTopsort . . . . . . . . . . . . . . . . . . . . 532
15.4.1 TopVisitor: Extending the Visitor Class . . . . . . . . . . . . . . . 532
15.4.2 DFSTopsort Implementation . . . . . . . . . . . . . . . . . . . . . 534
xiv CONTENTS
15.5 A Connected Components Class: DFSConncomp . . . . . . . . . . . . . . 534
15.5.1 ConnVisitor: Extending the Visitor Class . . . . . . . . . . . . . . 535
15.5.2 DFSConncomp Implementation . . . . . . . . . . . . . . . . . . . 536
15.6 A Shortest Paths Class: ShortestPaths . . . . . . . . . . . . . . . . . . . . 536
15.6.1 WeightedNeighbor: Extending the Neighbor Class . . . . . . . . . 538
15.6.2 ShortestPaths Implementation . . . . . . . . . . . . . . . . . . . . 538
15.7 Graph Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543
15.7.1 DirGraph Implementation . . . . . . . . . . . . . . . . . . . . . . 543
15.7.2 UndirGraph Class Implementation . . . . . . . . . . . . . . . . . . 548
15.7.3 Implementation of Weighted Graphs . . . . . . . . . . . . . . . . . 549
15.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 549
15.9 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 550
| Erscheint lt. Verlag | 7.12.2006 |
|---|---|
| Sprache | englisch |
| Maße | 177 x 234 mm |
| Gewicht | 710 g |
| Themenwelt | Informatik ► Programmiersprachen / -werkzeuge ► Java |
| Mathematik / Informatik ► Informatik ► Web / Internet | |
| ISBN-10 | 0-13-198619-8 / 0131986198 |
| ISBN-13 | 978-0-13-198619-0 / 9780131986190 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
