Data Structures

Abstraction and Design Using Java

Häftad, Engelska, 2021

1 716 kr

Beställningsvara. Skickas inom 5-8 vardagar. Fri frakt över 249 kr.

Beskrivning

Data Structures: Abstraction and Design Using Java offers a coherent and well-balanced presentation of data structure implementation and data structure applications with a strong emphasis on problem solving and software design. Step-by-step, the authors introduce each new data structure as an abstract data type (ADT), explain its underlying theory and computational complexity, provide its specification in the form of a Java interface, and demonstrate its implementation as one or more Java classes. Case studies using the data structures covered in the chapter show complete and detailed solutions to real-world problems, while a variety of software design tools are discussed to help students “Think, then code.” The book supplements its rigorous coverage of basic data structures and algorithms with chapters on sets and maps, balanced binary search trees, graphs, event-oriented programming, testing and debugging, and other key topics. Now available as an enhanced e-book, the fourth edition of Data Structures: Abstraction and Design Using Java enables students to measure their progress after completing each section through interactive questions, quick-check questions, and review questions.

Produktinformation

Utgivningsdatum:2021-03-02
Mått:250 x 20 x 200 mm
Vikt:1 225 g
Format:Häftad
Språk:Engelska
Antal sidor:688
Upplaga:4
Förlag:John Wiley & Sons Inc
ISBN:9781119703617

Utforska kategorier

Programmeringsböcker inom Data och IT

Innehållsförteckning

Preface iiiChapter 1 Object-Oriented Programming and Class Hierarchies 11.1 Abstract Data Types (ADTs), Interfaces, and the Java API 2Interfaces 2The implements Clause 5Declaring a Variable of an Interface Type 6Exercises for Section 1.1 61.2 Introduction to OOP 7A Superclass and Subclass Example 8Use of this. 9Initializing Data Fields in a Subclass 10The No-Parameter Constructor 11Protected Visibility for Superclass Data Fields 11Is-a versus Has-a Relationships 12Exercises for Section 1.2 121.3 Method Overriding, Method Overloading, and Polymorphism 13Method Overriding 13Method Overloading 15Polymorphism 17Methods with Class Parameters 17Exercises for Section 1.3 181.4 Abstract Classes 19Referencing Actual Objects 21Initializing Data Fields in an Abstract Class 21Abstract Class Number and the Java Wrapper Classes 21Summary of Features of Actual Classes, Abstract Classes, and Interfaces 22Implementing Multiple Interfaces 23Extending an Interface 23Exercises for Section 1.4 241.5 Class Object and Casting 24The Method toString 24Operations Determined by Type of Reference Variable 25Casting in a Class Hierarchy 26Using instanceof to Guard a Casting Operation 27The Class Class 29Exercises for Section 1.5 291.6 A Java Inheritance Example—The Exception Class Hierarchy 30Division by Zero 30Array Index Out of Bounds 30Null Pointer 31The Exception Class Hierarchy 31The Class Throwable 31Checked and Unchecked Exceptions 32Handling Exceptions to Recover from Errors 34Using try−catch to Recover from an Error 35Throwing an Exception When Recovery Is Not Obvious 35Exercises for Section 1.6 361.7 Packages and Visibility 37Packages 37The No−Package−Declared Environment 37Package Visibility 38Visibility Supports Encapsulation 38Exercises for Section 1.7 391.8 A Shape Class Hierarchy 40Case Study: Processing Geometric Figures 40Exercises for Section 1.8 46Chapter Review 46Java Constructs Introduced in This Chapter 47Java API Classes Introduced in This Chapter 47User-Defined Interfaces and Classes in This Chapter 47Quick-Check Exercises 47Review Questions 48Programming Projects 49Answers to Quick-Check Exercises 51Chapter 2 Lists and the Collections Framework 532.1 Algorithm Efficiency and Big-O 54Big-O Notation 56Formal Definition of Big-O 57Summary of Notation 60Comparing Performance 60The Power of O(log n) Algorithms 62Algorithms with Exponential and Factorial Growth Rates 62Exercises for Section 2.1 632.2 The List Interface and ArrayList Class 63The ArrayList Class 65Generic Collections 67Exercises for Section 2.2 692.3 Applications of ArrayList 70A Phone Directory Application 71Exercises for Section 2.3 722.4 Implementation of an ArrayList Class 72The Constructor for Class KWArrayList 73The add(E anEntry) Method 74The add(int index, E anEntry) Method 75The set and get Methods 76The remove Method 76The reallocate Method 77Performance of the KWArrayList Algorithms 77Exercises for Section 2.4 772.5 Single-Linked Lists 78A List Node 80Connecting Nodes 81A Single-Linked List Class 81Inserting a Node in a List 82Removing a Node 83Completing the KWSingleLinkedList Class 84The get and set Methods 85The add Methods 85Exercises for Section 2.5 862.6 Double-Linked Lists and Circular Lists 87The Node Class 88Inserting into a Double-Linked List 88Removing from a Double-Linked List 89A Double-Linked List Class 90Circular Lists 90Exercises for Section 2.6 912.7 The LinkedList Class and the Iterator, ListIterator, and Iterable Interfaces 91The LinkedList Class 91The Iterator 92The Iterator Interface 93The Enhanced for Loop 95The ListIterator Interface 95Comparison of Iterator and ListIterator 97Conversion between a ListIterator and an Index 97The Iterable Interface 97Exercises for Section 2.7 982.8 Application of the LinkedList Class 98Case Study: Maintaining an Ordered List 99Exercises for Section 2.8 1052.9 Implementation of a Double-Linked List Class 105Implementing the KWLinkedList Methods 106A Class That Implements the ListIterator Interface 107The Constructor 108The hasNext and next Methods 108The hasPrevious and previous Methods 109The add Method 110Inner Classes: Static and Nonstatic 112Exercises for Section 2.9 1132.10 The Collections Framework Design 114The Collection Interface 114Common Features of Collections 114The AbstractCollection, AbstractList, and AbstractSequentialList Classes 116The List and RandomAccess Interfaces (Advanced) 116Exercises for Section 2.10 117Chapter Review 117Java API Interfaces and Classes Introduced in This Chapter 118User-Defined Interfaces and Classes in this Chapter 119Quick-Check Exercises 119Review Questions 119Programming Projects 120Answers to Quick-Check Exercises 122Chapter 3 Testing and Debugging 1233.1 Types of Testing 124Preparations for Testing 126Testing Tips for Program Systems 126Exercises for Section 3.1 1273.2 Specifying the Tests 127Testing Boundary Conditions 127Exercises for Section 3.2 1283.3 Stubs and Drivers 129Stubs 129Preconditions and Postconditions 129Drivers 130Exercises for Section 3.3 1303.4 The JUnit5 Platform 130Exercises for Section 3.4 1353.5 Test-Driven Development 136Exercises for Section 3.5 1403.6 Testing Interactive Programs in JUnit 140ByteArrayInputStream 141ByteArrayOutputStream 141Exercises for Section 3.6 1423.7 Debugging a Program 143Using a Debugger 144The IntelliJ and Eclipse Debuggers 144Exercises for Section 3.7 147Chapter Review 148Java API Classes Introduced in This Chapter 149User-Defined Interfaces and Classes in This Chapter 149Quick-Check Exercises 149Review Questions 149Programming Projects 149Answers to Quick-Check Exercises 151Chapter 4 Stacks, Queues, and Deques 1524.1 Stack Abstract Data Type 153Specification of the Stack Abstract Data Type 153Exercises for Section 4.1 1554.2 Stack Applications 156Case Study: Finding Palindromes 156Exercises for Section 4.2 1604.3 Implementing a Stack 160Implementing a Stack with an ArrayList Component 160Implementing a Stack as a Linked Data Structure 162Comparison of Stack Implementations 163Exercises for Section 4.3 1644.4 Additional Stack Applications 164Case Study: Evaluating Postfix Expressions 165Case Study: Converting from Infix to Postfix 170Case Study: Converting Expressions with Parentheses 178Tying the Case Studies Together 181Exercises for Section 4.4 1814.5 Queue Abstract Data Type 182A Print Queue 182The Unsuitability of a “Print Stack” 183A Queue of Customers 183Using a Queue for Traversing a Multi-Branch Data Structure 183Specification for a Queue Interface 184Class LinkedList Implements the Queue Interface 184Exercises for Section 4.5 1854.6 Queue Applications 186Case Study: Maintaining a Queue 186Exercises for Section 4.6 1914.7 Implementing the Queue Interface 192Using a Double-Linked List to Implement the Queue Interface 192Using a Single-Linked List to Implement the Queue Interface 192Using a Circular Array to Implement the Queue Interface 194Overview of the Design 194Implementing ArrayQueue 196Increasing Queue Capacity 198Implementing Class ArrayQueue.Iter 199Comparing the Three Implementations 200Exercises for Section 4.7 2014.8 The Deque Interface 201Classes that Implement Deque 202Using a Deque as a Queue 203Using a Deque as a Stack 203Exercises for Section 4.8 204Chapter Review 205Java API Classes Introduced in This Chapter 205User-Defined Interfaces and Classes in This Chapter 205Quick-Check Exercises 206Review Questions 207Programming Projects 208Answers to Quick-Check Exercises 211Chapter 5 Recursion 2135.1 Recursive Thinking 214Steps to Design a Recursive Algorithm 216Proving that a Recursive Method Is Correct 218Tracing a Recursive Method 218The Run-Time Stack and Activation Frames 219Exercises for Section 5.1 2205.2 Recursive Definitions of Mathematical Formulas 221Tail Recursion versus Iteration 225Efficiency of Recursion 225Exercises for Section 5.2 2285.3 Recursive Array Search 229Design of a Recursive Linear Search Algorithm 229Implementation of Linear Search 230Design of a Binary Search Algorithm 231Efficiency of Binary Search 232The Comparable Interface 233Implementation of Binary Search 233Testing Binary Search 235Method Arrays.binarySearch 236Exercises for Section 5.3 2365.4 Recursive Data Structures 236Recursive Definition of a Linked List 237Class LinkedListRec 237Method size 237Method toString 238Method replace 238Method add 239Removing a List Node 239Exercises for Section 5.4 2405.5 Problem Solving with Recursion 241Case Study: Towers of Hanoi 241Case Study: Counting Cells in a Blob 246Exercises for Section 5.5 2505.6 Backtracking 250Case Study: Finding a Path through a Maze 251Exercises for Section 5.6 255Chapter Review 255User-Defined Classes in This Chapter 256Quick-Check Exercises 256Review Questions 256Programming Projects 257Answers to Quick-Check Exercises 258Chapter 6 Trees 2596.1 Tree Terminology and Applications 260Tree Terminology 260Binary Trees 261Some Types of Binary Trees 262General Trees 265Exercises for Section 6.1 2666.2 Tree Traversals 267Visualizing Tree Traversals 268Traversals of Binary Search Trees and Expression Trees 268Exercises for Section 6.2 2696.3 Implementing a BinaryTree Class 270The Node Class 270The BinaryTree Class 271The Constructors 272The getLeftSubtree and getRightSubtree Methods 273The isLeaf Method 274The toString Method 274The Recursive toString Method 274Exercises for Section 6.3 2766.4 Lambda Expressions and Functional Interfaces 277Functional Interfaces 278A General Preorder Traversal Method 281Using preOrderTraverse 282Exercises for Section 6.4 2826.5 Binary Search Trees 283Overview of a Binary Search Tree 283Performance 284Interface SearchTree 284The BinarySearchTree Class 285Implementing the find Methods 286Insertion into a Binary Search Tree 287Implementing the add Methods 287Removal from a Binary Search Tree 289Implementing the delete Methods 291Method findLargestChild 293Testing a Binary Search Tree 294Case Study: Writing an Index for a Term Paper 294Exercises for Section 6.5 2976.6 Heaps and Priority Queues 298Inserting an Item into a Heap 298Removing an Item from a Heap 299Implementing a Heap 299Performance of the Heap 302Priority Queues 302The PriorityQueue Class 303The offer Method 305The poll Method 306The Other Methods 307Exercises for Section 6.6 3076.7 Huffman Trees 308Case Study: Building a Custom Huffman Tree 309Exercises for Section 6.7 315Chapter Review 316Java API Interfaces and Classes Introduced in This Chapter 317User-Defined Interfaces and Classes in This Chapter 317Quick-Check Exercises 317Review Questions 318Programming Projects 318Answers to Quick-Check Exercises 321Chapter 7 Sets and Maps 3227.1 Sets and the Set Interface 323The Set Abstraction 323The Set Interface and Methods 325Using Method of to Initialize a Collection 327Comparison of Lists and Sets 327Exercises for Section 7.1 3287.2 Maps and the Map Interface 329The Map Hierarchy 330The Map Interface 330Creating a Map 331Exercises for Section 7.2 3337.3 Hash Tables 333Hash Codes and Index Calculation 334Methods for Generating Hash Codes 335Open Addressing 335Table Wraparound and Search Termination 336Traversing a Hash Table 338Deleting an Item Using Open Addressing 338Reducing Collisions by Expanding the Table Size 338Algorithm for rehashing 339Reducing Collisions Using Quadratic Probing 339Problems with Quadratic Probing 340Chaining 340Performance of Hash Tables 341Performance of Open Addressing versus Chaining 341Performance of Hash Tables versus Sorted Arrays and Binary Search Trees 342Storage Requirements for Hash Tables, Sorted Arrays, and Trees 342Storage requirements for Open Addressing and Chaining 343Exercises for Section 7.3 3437.4 Implementing the Hash Table 345Interface KWHashMap 345Class Entry 345Class HashtableOpen 346Class HashtableChain 351Testing the Hash Table Implementations 354Exercises for Section 7.4 3557.5 Implementation Considerations for Maps and Sets 355Methods hashCode and equals 355Implementing HashSetOpen 356Writing HashSetOpen as an Adapter Class 356Implementing the Java Map and Set Interfaces 357Interface Map.Entry and Class AbstractMap.SimpleEntry 357Creating a Set View of a Map 358Method entrySet and Classes EntrySet and SetIterator 358Classes TreeMap and TreeSet 359Exercises for Section 7.5 3607.6 Additional Applications of Maps 360Case Study: Implementing a Cell Phone Contact list 360Case Study: Completing the Huffman Coding Problem 362Encoding the Huffman Tree 366Exercises for Section 7.6 3677.7 Navigable Sets and Maps 367Application of a NavigableMap 369Exercises for Section 7.7 3717.8 Skip-Lists 371Skip-List Structure 372Searching a Skip-List 372Performance of a Skip-List Search 373Inserting into a Skip-List 373Increasing the Height of a Skip-List 374Implementing a Skip-List 374SkipList Methods for Search and Retrieval 375Method put for Inserting into a Skip-List 376Constants and Methods for Computing Random Level 378Performance of a Skip-List 378Testing Class Skip-List 379Exercises for Section 7.8 379Chapter Review 380Java API Interfaces and Classes Introduced in This Chapter 381User-Defined Interfaces and Classes in This Chapter 381Quick-Check Exercises 381Review Questions 382Programming Projects 383Answers to Quick-Check Exercises 384Chapter 8 Sorting 3858.1 Using Java Sorting Methods 386Collections.sort Methods 389Method List.sort 389Exercises for Section 8.1 3908.2 Selection Sort 390Analysis of Selection Sort 391Implementation of Selection Sort 392Exercises for Section 8.2 3938.3 Insertion Sort 393Analysis of Insertion Sort 395Implementation of Insertion Sort 395Exercises for Section 8.3 3968.4 Comparison of Quadratic Sorts 397Comparisons versus Exchanges 398Exercises for Section 8.4 3988.5 Shell Sort: A Better Insertion Sort 398Analysis of Shell Sort 400Implementation of Shell Sort 400Exercises for Section 8.5 4018.6 Merge Sort 402Analysis of Merge 403Implementation of Merge 403Design of Merge Sort 404Trace of Merge Sort Algorithm 404Analysis of Merge Sort 405Implementation of Merge Sort 406Exercises for Section 8.6 4068.7 Timsort 407Merging Adjacent Runs 410Performance of Timsort 410Implementation of Timsort 411Exercises for Section 8.7 4148.8 Heapsort 414First Version of a Heapsort Algorithm 414Analysis of Revised Heapsort Algorithm 416Implementation of Heapsort 417Exercises for Section 8.8 4188.9 Quicksort 418Algorithm for Quicksort 419Analysis of Quicksort 420Implementation of Quicksort 420Algorithm for Partitioning 421Implementation of partition 422A Revised partition Algorithm 424Implementation of Revised partition Method 425Exercises for Section 8.9 4268.10 Testing the Sort Algorithms 427Exercises for Section 8.10 4288.11 The Dutch National Flag Problem (Optional Topic) 428Case Study: The Problem of the Dutch National Flag 429Exercises for Section 8.11 431Chapter Review 432Java Classes Introduced in This Chapter 432User-Defined Classes in This Chapter 432Quick-Check Exercises 433Review Questions 433Programming Projects 433Answers to Quick-Check Exercises 434Chapter 9 Self-Balancing Search Trees 4359.1 Tree Balance and Rotation 436Why Balance Is Important 436Rotation 436Algorithm for Rotation 437Implementing Rotation 438Exercises for Section 9.1 4409.2 AVL Trees 440Balancing a Left–Left Tree 440Balancing a Left–Right Tree 441Four Kinds of Critically Unbalanced Trees 442Implementing an AVL Tree 444The AVLNode Class 445Inserting into an AVL Tree 446add Starter Method 447Recursive add Method 447Initial Algorithm for rebalanceLeft 448The Effect of Rotations on Balance 448Revised Algorithm for rebalanceLeft 449Method rebalanceLeft 449The decrementBalance Method 450Removal from an AVL Tree 451Performance of the AVL Tree 452Exercises for Section 9.2 4529.3 Red–Black Trees 453Insertion into a Red–Black Tree 453Implementation of Red–Black Tree Class 458Algorithm for Red–Black Tree Insertion 458The add Starter Method 460The Recursive add Method 461Removal from a Red–Black Tree 462Performance of a Red–Black Tree 462The TreeMap and TreeSet Classes 463Exercises for Section 9.3 4639.4 2–3 Trees 464Searching a 2–3 Tree 465Inserting an Item into a 2–3 Tree 465Inserting into a 2-Node Leaf 465Inserting into a 3-Node Leaf with a 2-Node Parent 466Inserting into a 3-Node Leaf with a 3-Node Parent 466Analysis of 2–3 Trees and Comparison with Balanced Binary Trees 468Removal from a 2–3 Tree 469Exercises for Section 9.4 4709.5 B-Trees and 2–3–4 Trees 470B-Trees 471Implementing the B-Tree 472Code for the insert Method 474The insertIntoNode Method 475The splitNode Method 476Removal from a B-Tree 478B+ Trees 4792–3–4 Trees 480Relating 2–3–4 Trees to Red–Black Trees 481Exercises for Section 9.5 482Chapter Review 483Java Classes Introduced in This Chapter 484User-Defined Interfaces and Classes in This Chapter 484Quick-Check Exercises 485Review Questions 486Programming Projects 486Answers to Quick-Check Exercises 489Chapter 10 Graphs 49210.1 Graph Terminology 493Visual Representation of Graphs 493Directed and Undirected Graphs 494Paths and Cycles 494Relationship between Graphs and Trees 496Graph Applications 496Exercises for Section 10.1 49710.2 The Graph ADT and Edge Class 497Representing Vertices and Edges 498Exercises for Section 10.2 49910.3 Implementing the Graph ADT 499Adjacency List 499Adjacency Matrix 501Overview of the Hierarchy 501Declaring the Graph Interface 502The ListGraph Class 503Comparing Implementations 506Exercises for Section 10.3 50710.4 Traversals of Graphs 508Breadth-First Search 508Depth-First Search 513Exercises for Section 10.4 51910.5 Applications of Graph Traversals 519Case Study: Shortest Path through a Maze 519Case Study: Topological Sort of a Graph 523Exercises for Section 10.5 52610.6 Algorithms Using Weighted Graphs 526Finding the Shortest Path from a Vertex to All Other Vertices 526Analysis of Dijkstra’s Algorithm 528Minimum Spanning Trees 530Exercises for Section 10.6 53310.7 A Heuristic Algorithm A* to Find the Best Path 534A* (A-Star) an Improvement of Dijkstra’s Algorithm 535Exercises for Section 10.7 541Chapter Review 541User-Defined Classes and Interfaces in This Chapter 542Quick-Check Exercises 542Review Questions 543Programming Projects 543Answers to Quick-Check Exercises 545Appendix A Introduction to Java A-1A.1 The Java Environment and Classes A-2The Java Virtual Machine A-3The Java Compiler A-3Classes and Objects A-3The Java API A-3The import Statement A-4Method main A-4Execution of a Java Program A-5Use of jshell A-5Exercises for Section A.1 A-6A.2 Primitive Data Types and Reference Variables A-6Primitive Data Types A-6Primitive-Type Variables A-8Primitive-Type Constants A-8Operators A-8Postfix and Prefix Increment A-10Type Compatibility and Conversion A-10Referencing Objects A-11Creating Objects A-11Exercises for Section A.2 A-12A.3 Java Control Statements A-13Sequence and Compound Statements A-13Selection and Repetition Control A-13Nested if Statements A-15The switch Statement A-16Exercises for Section A.3 A-17A.4 Methods and Class Math A-17The Instance Methods println and print A-18Call-by-Value Arguments A-18The Class Math A-18Escape Sequences A-19Exercises for Section A.4 A-20A.5 The String, StringBuilder, StringBuffer, and StringJoiner Classes A-21The String Class A-21Strings Are Immutable A-23The Garbage Collector A-24Comparing Objects A-24The String.format Method A-25The Formatter Class A-26The String.split Method A-27Introduction to Regular Expressions A-27Matching One of a Group of Characters A-27Qualifiers A-27Defined Character Groups A-28Unicode Character Class Support A-29The StringBuilder and StringBuffer Classes A-29StringJoiner Class A-31Exercises for Section A.5 A-32A.6 Wrapper Classes for Primitive Types A-33Exercises for Section A.6 A-34A.7 Defining Your Own Classes A-35Private Data Fields, Public Methods A-38Constructors A-39The No-Parameter Constructor A-39Modifier and Accessor Methods A-40Use of this. in a Method A-40The Method toString A-40The Method equals A-41Declaring Local Variables in Class Person A-42An Application that Uses Class Person A-42Objects as Arguments A-43Classes as Components of Other Classes A-44Java Documentation Style for Classes and Methods A-44Exercises for Section A.7 A-47A.8 Arrays A-47Data Field length A-49Method Arrays.copyOf A-50Method System.arrayCopy A-50Array Data Fields A-51Array Results and Arguments A-52Arrays of Arrays A-52Exercises for Section A.8 A-55A.9 Enumeration Types A-56Using Enumeration Types A-57Assigning Values to Enumeration Types A-58Exercises for Section A.9 A-58A.10 I/O Using Streams, Class Scanner, and Class JOptionPane A-58The Scanner A-59Using a Scanner to Read from a File A-61Exceptions A-61Tokenized Input A-61Extracting Tokens Using Scanner.findInLine A-62Using a BufferedReader to Read from an Input Stream A-62Output Streams A-62Passing Arguments to Method main A-63Closing Streams A-63Try with Resources A-63A Complete File-Processing Application A-64Input/Output Using Class JOptionPane A-65Converting Numeric Strings to Numbers A-66GUI Menus Using Method showOptionDialog A-66Exercises for Section A.10 A-67A.11 Catching Exceptions A-67Catching and Handling Exceptions A-68Exercises for Section A.11 A-74A.12 Throwing Exceptions A-74The throws Clause A-74The throw Statement A-75Exercises for Section A.12 A-78Appendix Review A-79Java Constructs Introduced in This Appendix A-81Java API Classes Introduced in This Appendix A-81User‐Defined Interfaces and Classes in This Appendix A-82Quick‐Check Exercises A-82Review Questions A-82Programming Projects A-83Answer to Quick‐Check Exercises A-84Appendix B Overview of UML A-85B.1 The Class Diagram A-85Representing Classes and Interfaces A-86Generalization A-87Inner or Nested Classes A-88Aggregation and Composition A-88B.2 Object Diagrams A-89Glossary G-1Index I-1