| |
Description: Continuing the success of the popular second edition, the updated and revised Object-Oriented Data Structures Using Java TM, Third Edition is sure to be an essential resource for students learning data structures using the Java programming language. It presents traditional data structures and object-oriented topics with an emphasis on problem-solving, theory, and software engineering principles. Beginning early and continuing throughout the text, the authors introduce and expand upon the use of many Java features including packages, interfaces, abstract classes, inheritance, and exceptions. Numerous case studies provide readers with real-world examples and demonstrate possible solutions to interesting problems. The authors’ lucid writing style guides readers through the rigor of standard data structures and presents essential concepts from logical, applications, and implementation levels. Key concepts throughout the Third Edition have been clarified to increase student comprehension and retention, making Object-Oriented Data Structure using Java TM Third Edition a must –have resource for computer science students learning this popular programming language.
New and Key Features of the Revised Third Edition:
• Includes Java generics in Chapter 3 and expands upon their use throughout the text.
• Includes a new section on concurrency and synchronization
• Sections have been expanded or modified to increase clarity and student retention.
• Includes additional code examples and programming exercises, including several project – type exercises.
• Incorporates an accessible, student friendly writing style with real world case studies
• Each case study includes a problem description, an analysis of the problem input and required output, and a discussion of the appropriate data structures to use.
• Chapters conclude with a summary that highlights the most important topics of the chapter and ties together related topics
• Includes revised end of chapter question and exercises throughout
• Instructor’s Resource include an instructor’s manual, test bank, and Microsoft® PowerPoint® slides
Contents: Chapter 1: Getting Organized • Software Engineering • Software Life Cycles • Agile Methods • Goals of Quality Software • Object Orientation • The Unified Method • Classes, Objects, and Applications • Classes • Objects • Applications • Organizing Classes • Inheritance • Packages • Data Structures • Implementation-Dependent Structures • Implementation-Independent Structures • What Is a Data Structure? • Basic Structuring Mechanisms • References • Arrays • Comparing Algorithms: Big-O Analysis • Big-O Notation • Common Orders of Magnitude • Example 1: Sum of Consecutive Integers • Example 2: Finding a Number in a Phone Book • Summary • Exercises
Chapter 2: Abstract Data Types • Abstraction • Information Hiding • Data Abstraction • Data Levels • Preconditions and Post conditions • Java Interfaces • The StringLog ADT Specification • Constructors • Transformers • Observers • The StringLogInterface • Using the StringLogInterface • Array-Based StringLog ADT Implementation • Instance Variables • Constructors • Transformers • Observers • Software Testing • Identifying Test Cases • Test Plans • Testing ADT Implementations • Introduction to Linked Lists • Array Versus Linked Lists • The LL String Node Class • Operations on Linked Lists • Linked List StringLog ADT Implementation • Instance Variables • Constructors • Transformers • Observers • Software Design: Identification of Classes • Brainstorm • Filter • Scenario Analysis • Nouns and Verbs • Cohesive Designs • Summation of Our Approach • Design Choices • Case Study: A Trivia Game • The Source of the Trivia Game • Identifying Support Classes • Implementing the Support Classes • The Trivia Game Application • Case Study Summation • Summary • Exercises
Chapter 3: The Stack ADT • Stacks • Operations on Stacks • Using Stacks • Collection Elements • Generally Usable Collections • Exceptional Situations • Handling Exceptional Situations • Exceptions and ADTs: An Example • Error Situations and ADTs • Formal Specification • Exceptional Situations • The Interfaces • Example Use • Array-Based Implementations • The ArrayStack Class • Definitions of Stack Operations • Test Plan • Application: Well-Formed Expressions • The Balanced Class • The Application • Link-Based Implementation • The LLObject Node Class • The LinkedStack Class • The push Operation • The pop Operation • The Other Stack Operations • Comparing Stack Implementations • Case Study: Postfix Expression Evaluator • Discussion • Evaluating Postfix Expressions • Postfix Expression Evaluation Algorithm • Specification: Program Postfix Evaluation • Brainstorming and Filtering • The PostFixEvaluator Class • The PFixConsole Class • Testing the Postfix Evaluator • Summary • Exercises
Chapter 4: Recursion • Recursive Definitions, Algorithms, and Programs • Recursive Definitions • Recursive Algorithms • Recursive Programs • The Three Questions • Verifying Recursive Algorithms • Writing Recursive Methods • Debugging Recursive Methods • Towers of Hanoi • The Algorithm • The Method • The Program • Counting Blobs • Generating Blobs • The Counting Algorithm • The Marking Algorithm • The Grid Class • The Program • Recursive Linked-List Processing • Reverse Printing • Removing Recursion • How Recursion Works • Iteration • Stacking • Deciding Whether to Use a Recursive Solution • Recursion Overhead • Inefficient Algorithms • Clarity • Summary • Exercises
Chapter 5: The Queue ADT • Queues • Operations on the Queues • Using Queues • Formal Specification • Example Use • Array-Based Implementations • The ArrayBndQueue Class • The ArrayUnbndQueue Class • Application: Palindromes • The Palindrome Class • The Application • Application: The Card Game of War • The RankCardDeck Class • The WarGame Class • The WarGameApp Class • Link-Based Implementations • The Enqueue Operation • The Dequeue Operation • The Queue Implementation • A Circular Linked Queue Design • Comparing Queue Implementations • Concurrency, Interference, and Synchronization • The counter Class • Java Threads • Interference • Synchronization • A Synchronized Queue • Case Study: Average Waiting Time • Problem Discussion • Program Design • Program Details • Testing Considerations • Summary • Exercises
Chapter 6: The List ADT • Comparing Objects Revisited • The equals Method • The Comparable Interface • Lists • Varieties of Lists • Assumptions for Our Lists • Formal Specification • The List Interface • The Indexed List Interface • Example Use • Array-Based Implementations • The ArrayUnsortedList Class • The ArraySortedList Class • The ArrayIndexedList Class • Applications: Poker, Golf, and Music • Poker • Golf • Music • The Binary Search Algorithm • Improving Linear Search in a Sorted List • Binary Search Algorithm • Recursive Binary Search • Efficiency Analysis • Reference-Based Implementations • The RefUnsorted List Class • TheRefSorted List Class • Storing Objects and Structures in Files • Saving Object Data in Text Files • Serialization of Objects • Serializing Structures • Application: Song Lists • Summary • Exercises
Chapter 7: More Lists • Circular Linked Lists • An Unsorted Circular List • The CRefUnsorted List Class • Circular Versus Linear Linked Lists • Doubly Linked Lists • The Add and Remove Operations • Linked Lists with Headers and Trailers • A Linked List as an Array of Nodes • Why Use an Array? • How Is an Array Used? • A Specialized List ADT • The Specification • The Implementation • Case Study: Large Integers • The LargeInt Class • Addition and Subtraction • Test Plan • The LargeIntApp Program • Summary • Exercises
Chapter 8: Binary Search Trees • Trees • Binary Trees • Binary Search Trees • Binary Tree Traversals • The Logical Level • Tree Elements • The Binary Search Tree Specification • The Application Level • The Implementation Level: Basics • Iterative Versus Recursive Method Implementations • Recursive Approach to the size Method • Iterative Approach to the size Method • Recursion or Iteration? • The Implementation Level: Remaining Operations • The contains and get Operations • The add Operation • The remove Operation • Iteration • Testing Binary Search Tree Operations • Comparing Binary Search Tree and Linear Lists • Big-O Comparisons • Balancing a Binary Search Tree • A Nonlinked Representation of Binary Trees • Case Study: Word Frequency Generator • Problem • Discussion • Brainstorming • Filtering • The User Interface • Error Handling • Scenario Analysis • The Word Frequency Generator Program • Testing • Summary • Exercises
Chapter 9: Priority Queues, Heaps, and Graphs • Priority Queues • Logical Level • Application Level • Implementation Level • Heaps • Heap Implementation • The enqueue Method • The dequeue Method • A Sample Use • Heaps Versus Other Representations of Priority Queues • Introduction to Graphs • Formal Specification of a Graph ADT • Implementations of Graphs • Array-Based Implementation • Linked Implementation • Graph Applications • Depth-First Searching • Breadth-First Searching • The Single-Source Shortest-Paths Problem • Summary • Exercises
Chapter 10: Sorting and Searching Algorithms • Sorting • A Test Harness • Simple Sorts • Straight Selection Sort • Bubble Sort • Insertion Sort • O(N log2•N ) Sorts • Merge Sort • Quick Sort • Heap Sort • More Sorting Considerations • Testing • Efficiency • Objects and References • Using the Comparable Interface • Using the Comparator Interface • Stability • Searching • Linear Searching • High Probability Ordering • Sorted Lists • Hashing • Collisions • Choosing a Good Hash Function • Complexity • Summary • Exercises
Appendix A: Java Reserved Words • Appendix B: Operator Precedence • Appendix C: Primitive Data Types • Appendix D: ASCII Subset of Unicode • Appendix E; Application of Programmer Interfaces for the Java Classes and Interfaces Used in This Book • IndexISBN - 9789380853291
|
| |
Pages : 824
|