| |
| |
| |
| Getting Organized | |
| |
| |
| |
| Software Engineering | |
| |
| |
| Software Life Cycles | |
| |
| |
| Agile Methods | |
| |
| |
| Goals of Quality Software | |
| |
| |
| |
| Object Orientation | |
| |
| |
| Benefits | |
| |
| |
| 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 | |
| |
| |
| |
| Sum of Consecutive Integers | |
| |
| |
| |
| Finding a Number in a Phone Book | |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| |
| Abstract Data Types | |
| |
| |
| |
| Abstraction | |
| |
| |
| Information Hiding | |
| |
| |
| Data Abstraction | |
| |
| |
| Data Levels | |
| |
| |
| Preconditions and Postconditions | |
| |
| |
| 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 LLStringNode 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 | |
| |
| |
| |
| 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 | |
| |
| |
| |
| Application: Well-Formed Expressions | |
| |
| |
| The Balanced Class | |
| |
| |
| The Application | |
| |
| |
| |
| Array-Based Implementations | |
| |
| |
| The ArrayStack Class | |
| |
| |
| Definitions of Stack Operations | |
| |
| |
| Test Plan | |
| |
| |
| |
| 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 | |
| |
| |
| |
| A 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 | |
| |
| |
| |
| The Queue ADT | |
| |
| |
| |
| Queues | |
| |
| |
| Operations on the Queues | |
| |
| |
| Using Queues | |
| |
| |
| |
| Formal Specification | |
| |
| |
| |
| Application: Palindromes | |
| |
| |
| The Palindrome Class | |
| |
| |
| The Application | |
| |
| |
| |
| Array-Based Implementations | |
| |
| |
| The ArrayBndQueue Class | |
| |
| |
| The ArrayUnbndQueue Class | |
| |
| |
| |
| 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 | |
| |
| |
| |
| Case Study: Average Waiting Time | |
| |
| |
| Problem Discussion | |
| |
| |
| Program Design | |
| |
| |
| Program Details | |
| |
| |
| Testing Considerations | |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| |
| The List ADT | |
| |
| |
| |
| Comparing Objects Revisited | |
| |
| |
| The equals Method | |
| |
| |
| The Comparable Interface | |
| |
| |
| |
| Lists | |
| |
| |
| Varieties of Lists | |
| |
| |
| Assumptions for Our Lists | |
| |
| |
| |
| Formal Specification | |
| |
| |
| The ListInterface | |
| |
| |
| The Specialized Interfaces | |
| |
| |
| Example Use | |
| |
| |
| |
| Array-Based Implementations | |
| |
| |
| The List Class | |
| |
| |
| 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 RefList Class | |
| |
| |
| The RefUnsortedList Class | |
| |
| |
| The RefSortedList Class | |
| |
| |
| |
| Storing Objects and Structures in Files | |
| |
| |
| Saving Object Data in Text Files | |
| |
| |
| Serialization of Objects | |
| |
| |
| Serializing Structures | |
| |
| |
| Application: Song Lists | |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| |
| More Lists | |
| |
| |
| |
| Circular Linked Lists | |
| |
| |
| An Unsorted Circular List | |
| |
| |
| The CrefList Class | |
| |
| |
| 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 | |
| |
| |
| |
| 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 WordFreq Class | |
| |
| |
| The Word Frequency Generator Program | |
| |
| |
| Testing | |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| |
| Priority Queues, Heaps, and Graphs | |
| |
| |
| |
| Priority Queues | |
| |
| |
| Logical Level | |
| |
| |
| Application Level | |
| |
| |
| Implementation Level | |
| |
| |
| |
| Heaps | |
| |
| |
| Heap Implementation | |
| |
| |
| The enqueue Method | |
| |
| |
| The dequeue Method | |
| |
| |
| Heaps versus Other Representations of Priority Queues | |
| |
| |
| |
| Introduction to Graphs | |
| |
| |
| |
| Formal Specification of a Graph ADT | |
| |
| |
| |
| Graph Applications | |
| |
| |
| Depth-First Searching | |
| |
| |
| Breadth-First Searching | |
| |
| |
| The Single-Source Shortest-Paths Problem | |
| |
| |
| |
| Implementations of Graphs | |
| |
| |
| Array-Based Implementation | |
| |
| |
| Linked Implementation | |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| |
| Sorting and Searching Algorithms | |
| |
| |
| |
| Sorting | |
| |
| |
| A Test Harness | |
| |
| |
| |
| Simple Sorts | |
| |
| |
| Straight Selection Sort | |
| |
| |
| Bubble Sort | |
| |
| |
| Insertion Sort | |
| |
| |
| |
| O(N log[subscript 2]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 | |
| |
| |
| |
| Java Reserved Words | |
| |
| |
| |
| Operator Precedence | |
| |
| |
| |
| Primitive Data Types | |
| |
| |
| |
| ASCII Subset of Unicode | |
| |
| |
| |
| Application of Programmer Interfaces for the Java Classes and Interfaces Used in This Book | |
| |
| |
| |
| A Generic Stack | |
| |
| |
| |
| The Bounded Stack Interface | |
| |
| |
| |
| The Bounded Stack Class | |
| |
| |
| |
| The SampleApp Class | |
| |
| |
| Index | |