 |
Ksiazki - Informatyczne .pl » informatyka » informatyka Data Structures Outside-In with Java
Opis Data Structures Outside-In with Java: For courses in Java - Data Structures/CS2. This innovative new text encourages students to utilize the "Outside-In" approach to learning the use, design and implementation of data structures. The author introduces every data structure by first narrating its properties and use in applications (the "outside" view) - enabling instructors to introduce a data structure in a realistic context where it is used. He then teaches how to build data structures (the "inside" view); students learn how to evaluate usability, flexibility, extensibility, and performance in designing and implementing classic data structures. * The properties of a data structure are formalized by defining its Java public interface: - The interface of a data structure specifies its usability and flexibility, which play a big role in choosing between candidate data structures that may be suitable for use in an application. * A "price tag" associated with every data structure at the "outside" level: - Performance is the other primary factor (along with usability/flexibility) that determines whether or not a data structure will be chosen for use in an application; the price tag details performance. * Mathematical analysis integrated at a level that is appropriate and relevant to construct the price tags: - Students understand how to analyze and construct price tags for structures they build, and the cost of using them in applications. * Complete Java code listed and discussed for many applications and all data structures discussed that are not part of the Java APIs. - Students learn how Java can be used to use and implement data structures in a rigorous and complete way * Numerous examples worked throughout the text * Consistent pedagogy in every chapter, including: - A set of learning objectives at the start of each chapter - Unique boxed key points - End-of-chapter summary points - End-of-chapter analytical and design exercises - End-of-chapter programming * Public interfaces for Java classes - Presented as a stand-alone, one-page figure in a special format. * Unique price tag of public operations for every structure - Presented in tabular format for quick reference. * Complete Java code for applications and structures - Presented in a special format with line numbers. * Algorithms throughout the book written in pseudo-code and stylized with appropriate notation to distinguish from Java code. Spis treści Data Structures Outside-In with Java: 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 |
|
Księgarnia informatyczna © ksiazki-informatyczne.pl
- prentice hall , książka informatyczna - Data Structures Outside-In with Java
|