| |
| |
| Preface | |
| |
| |
| Chapter Dependency Chart | |
| |
| |
| |
| Problem-Solving Techniques | |
| |
| |
| |
| Review of Java Fundamentals | |
| |
| |
| |
| Language Basics | |
| |
| |
| Comments | |
| |
| |
| Identifiers and Keywords | |
| |
| |
| Variables | |
| |
| |
| Primitive Data Types | |
| |
| |
| References | |
| |
| |
| Literal Constants | |
| |
| |
| Named Constants | |
| |
| |
| Assignments and Expressions | |
| |
| |
| Arrays | |
| |
| |
| |
| Selection Statements | |
| |
| |
| The if Statement | |
| |
| |
| The switch Statement | |
| |
| |
| |
| Iteration Statements | |
| |
| |
| The while Statement | |
| |
| |
| The for Statement | |
| |
| |
| The do Statement | |
| |
| |
| |
| Program Structure | |
| |
| |
| Packages | |
| |
| |
| Classes | |
| |
| |
| Data Fields | |
| |
| |
| Methods | |
| |
| |
| How to Access Members of an Object | |
| |
| |
| Class Inheritance | |
| |
| |
| |
| Useful Java Classes | |
| |
| |
| The Object Class | |
| |
| |
| The Array Class | |
| |
| |
| String Classes | |
| |
| |
| |
| Java Exceptions | |
| |
| |
| Catching Exceptions | |
| |
| |
| Throwing Exceptions | |
| |
| |
| |
| Text Input and Output | |
| |
| |
| Input | |
| |
| |
| Output | |
| |
| |
| The Console Class | |
| |
| |
| |
| File Input and Output | |
| |
| |
| Text Files | |
| |
| |
| Object Serialization | |
| |
| |
| Summary | |
| |
| |
| Cautions | |
| |
| |
| Self-Test Exercises | |
| |
| |
| Exercises | |
| |
| |
| Programming Problems | |
| |
| |
| |
| Principles of Programming and Software Engineering | |
| |
| |
| |
| Problem Solving and Software Engineering | |
| |
| |
| What Is Problem Solving? | |
| |
| |
| The Life Cycle of Software | |
| |
| |
| What Is a Good Solution? | |
| |
| |
| |
| Achieving an Object-Oriented Design | |
| |
| |
| Abstraction and Information Hiding | |
| |
| |
| Object-Oriented Design | |
| |
| |
| Functional Decomposition | |
| |
| |
| General Design Guidelines | |
| |
| |
| Modeling Object-Oriented Designs Using UML | |
| |
| |
| Advantages of an Object-Oriented Approach | |
| |
| |
| |
| A Summary of Key Issues in Programming | |
| |
| |
| Modularity | |
| |
| |
| Modifiability | |
| |
| |
| Ease of Use | |
| |
| |
| Fail-Safe Programming | |
| |
| |
| Style | |
| |
| |
| Debugging | |
| |
| |
| Summary | |
| |
| |
| Cautions | |
| |
| |
| Self-Test Exercises | |
| |
| |
| Exercises | |
| |
| |
| Programming Problems | |
| |
| |
| |
| Recursion: The Mirrors | |
| |
| |
| |
| Recursive Solutions | |
| |
| |
| A Recursive Valued Method: The Factorial of n | |
| |
| |
| A Recursive void Method: Writing a String Backward | |
| |
| |
| |
| Counting Things | |
| |
| |
| Multiplying Rabbits (The Fibonacci Sequence) | |
| |
| |
| Organizing a Parade | |
| |
| |
| Mr. Spock's Dilemma (Choosing k out of n Things) | |
| |
| |
| |
| Searching an Array | |
| |
| |
| Finding the Largest Item in an Array | |
| |
| |
| Binary Search | |
| |
| |
| Finding the k th Smallest Item in an Array | |
| |
| |
| |
| Organizing Data | |
| |
| |
| The Towers of Hanoi | |
| |
| |
| |
| Recursion and Efficiency | |
| |
| |
| Summary | |
| |
| |
| Cautions | |
| |
| |
| Self-Test Exercises | |
| |
| |
| Exercises | |
| |
| |
| Programming Problems | |
| |
| |
| |
| Data Abstraction: The Walls | |
| |
| |
| |
| Abstract Data Types | |
| |
| |
| |
| Specifying ADTs | |
| |
| |
| The ADT List | |
| |
| |
| The ADT Sorted List | |
| |
| |
| Designing an ADT | |
| |
| |
| Axioms (Optional) | |
| |
| |
| |
| Implementing ADTs | |
| |
| |
| Java Classes Revisited | |
| |
| |
| Java Interfaces | |
| |
| |
| Java Packages | |
| |
| |
| An Array-Based Implementation of the ADT List | |
| |
| |
| Summary | |
| |
| |
| Cautions | |
| |
| |
| Self-Test Exercises | |
| |
| |
| Exercises | |
| |
| |
| Programming Problems | |
| |
| |
| |
| Linked Lists | |
| |
| |
| |
| Preliminaries | |
| |
| |
| Object References | |
| |
| |
| Resizeable Arrays | |
| |
| |
| Reference-Based Linked Lists | |
| |
| |
| |
| Programming with Linked Lists | |
| |
| |
| Displaying the Contents of a Linked List | |
| |
| |
| Deleting a Specified Node from a Linked List | |
| |
| |
| Inserting a Node into a Specified Position of a Linked List | |
| |
| |
| A Reference-Based Implementation of the ADT List | |
| |
| |
| Comparing Array-Based and Reference-Based Implementations | |
| |
| |
| Passing a Linked List to a Method | |
| |
| |
| Processing Linked Lists Recursively | |
| |
| |
| |
| Variations of the Linked List | |
| |
| |
| Tail References | |
| |
| |
| Circular Linked Lists | |
| |
| |
| Dummy Head Nodes | |
| |
| |
| Doubly Linked Lists | |
| |
| |
| |
| Application: Maintaining an Inventory | |
| |
| |
| |
| The Java Collections Framework | |
| |
| |
| Generics | |
| |
| |
| Iterators | |
| |
| |
| The Java Collection's Framework List Interface | |
| |
| |
| Summary | |
| |
| |
| Cautions | |
| |
| |
| Self-Test Exercises | |
| |
| |
| Exercises | |
| |
| |
| Programming Problems | |
| |
| |
| |
| Problem Solving with Abstract Data Types | |
| |
| |
| |
| Recursion as a Problem-Solving Technique | |
| |
| |
| |
| Backtracking | |
| |
| |
| The Eight Queens Problem | |
| |
| |
| |
| Defining Languages | |
| |
| |
| The Basics of Grammars | |
| |
| |
| Two Simple Languages | |
| |
| |
| Algebraic Expressions | |
| |
| |
| |
| The Relationship Between Recursion and Mathematical Induction | |
| |
| |
| The Correctness of the Recursive Factorial Method | |
| |
| |
| The Cost of Towers of Hanoi | |
| |
| |
| Summary | |
| |
| |
| Cautions | |
| |
| |
| Self-Test Exercises | |
| |
| |
| Exercises | |
| |
| |
| Programming Problems | |
| |
| |
| |
| Stacks | |
| |
| |
| |
| The Abstract Data Type Stack | |
| |
| |
| Developing an ADT During the Design of a Solution | |
| |
| |
| |
| Simple Applications of the ADT Stack | |
| |
| |
| Checking for Balanced Braces | |
| |
| |
| Recognizing Strings in a Language | |
| |
| |
| |
| Implementations of the ADT Stack | |
| |
| |
| An Array-Based Implementation of the ADT Stack | |
| |
| |
| A Reference-Based Implementation of the ADT Stack | |
| |
| |
| An Implementation That Uses the ADT List | |
| |
| |
| Comparing Implementations | |
| |
| |
| The Java Collections Framework Class Stack | |
| |
| |
| |
| Application: Algebraic Expressions | |
| |
| |
| Evaluating Postfix Expressions | |
| |
| |
| Converting Infix Expressions to Equivalent Postfix Expressions | |
| |
| |
| |
| Application: A Search Problem | |
| |
| |
| A Nonrecursive Solution That Uses a Stack | |
| |
| |
| A Recursive Solution | |
| |
| |
| |
| The Relationship Between Stacks and Recursion | |
| |
| |
| Summary | |
| |
| |
| Cautions | |
| |
| |
| Self-Test Exercises | |
| |
| |
| Exercises | |
| |
| |
| Programming Problems | |
| |
| |
| |
| Queues | |
| |
| |
| |
| The Abstract Data Type Queue | |
| |
| |
| |
| Simple Applications of the ADT Queue | |
| |
| |
| Reading a String of Characters | |
| |
| |
| Recognizing Palindromes | |
| |
| |
| |
| Implementations of the ADT Queue | |
| |
| |
| A Reference-Based Implementation | |
| |
| |
| An Array-Based Implementation | |
| |
| |
| An Implementation That Uses the ADT List | |
| |
| |
| The JCF Interfaces Queue and Deque | |
| |
| |
| Comparing Implementations | |
| |
| |
| |
| A Summary of Position-Oriented ADTs | |
| |
| |
| |
| Application: Simulation | |
| |
| |
| Summary | |
| |
| |
| Cautions | |
| |
| |
| Self-Test Exercises | |
| |
| |
| Exercises | |
| |
| |
| Programming Problems | |
| |
| |
| |
| Advanced Java Topics | |
| |
| |
| |
| Inheritance Revisited | |
| |
| |
| Java Access Modifiers | |
| |
| |
| Is-a and Has-a Relationships | |
| |
| |
| |
| Dynamic Binding and Abstract Classes | |
| |
| |
| Abstract Classes | |
| |
| |
| Java Interfaces Revisited | |
| |
| |
| |
| Java Generics | |
| |
| |
| Generic Classes | |
| |
| |
| Generic Wildcards | |
| |
| |
| Generic Classes and Inheritance | |
| |
| |
| Generic Implementation of the Class List | |
| |
| |
| Generic Methods | |
| |
| |
| |
| The ADTs List and Sorted List Revisited | |
| |
| |
| Implementations of the ADT Sorted List That Use the ADT List | |
| |
| |
| |
| Iterators | |
| |
| |
| Summary | |
| |
| |
| Cautions | |
| |
| |
| Self-Test Exercises | |
| |
| |
| Exercises | |
| |
| |
| Programming Problems | |
| |
| |
| |
| Algorithm Efficiency and Sorting | |
| |
| |
| |
| Measuring the Efficiency of Algorithms | |
| |
| |
| The Execution Time of Algorithms | |
| |
| |
| Algorithm Growth Rates | |
| |
| |
| Order-of-Magnitude Analysis and Big O Notation | |
| |
| |
| Keeping Your Perspective | |
| |
| |
| The Efficiency of Searching Algorithms | |
| |
| |
| |
| Sorting Algorithms and Their Efficiency | |
| |
| |
| Selection Sort | |
| |
| |
| Bubble Sort | |
| |
| |
| Insertion Sort | |
| |
| |
| Mergesort | |
| |
| |
| Quicksort | |
| |
| |
| Radix Sort | |
| |
| |
| A Comparison of Sorting Algorithms | |
| |
| |
| The Java Collections Framework Sort Algorithm | |
| |
| |
| Summary | |
| |
| |
| Cautions | |
| |
| |
| Self-Test Exercises | |
| |
| |
| Exercises | |
| |
| |
| Programming Problems | |
| |
| |
| |
| Trees | |
| |
| |
| |
| Terminology | |
| |
| |
| |
| The ADT Binary Tree | |
| |
| |
| Basic Operations of the ADT Binary Tree | |
| |
| |
| General Operations of the ADT Binary Tree | |
| |
| |
| Traversals of a Binary Tree | |
| |
| |
| Possible Representations of a Binary Tree | |
| |
| |
| A Reference-Based Implementation of the ADT Binary Tree | |
| |
| |
| Tree Traversals Using an Iterator | |
| |
| |
| |
| The ADT Binary Search Tree | |
| |
| |
| Algorithms for the Operations of the ADT Binary Search Tree | |
| |
| |
| A Reference-Based Implementation of the ADT Binary Search Tree | |
| |
| |
| The Efficiency of Binary Search Tree Operations | |
| |
| |
| Treesort | |
| |
| |
| Saving a Binary Search Tree in a File | |
| |
| |
| The JCF Binary Search Algorithm | |
| |
| |
| |
| General Trees | |
| |
| |
| Summary | |
| |
| |
| Cautions | |
| |
| |
| Self-Test Exercises | |
| |
| |
| Exercises | |
| |
| |
| Programming Problems | |
| |
| |
| |
| Tables and Priority Queues | |
| |
| |
| |
| The ADT Table | |
| |
| |
| Selecting an Implementation | |
| |
| |
| A Sorted Array-Based Implementation of the ADT Table | |
| |
| |
| A Binary Search Tree Implementation of the ADT Table | |
| |
| |
| |
| The ADT Priority Queue: A Variation of the ADT Table | |
| |
| |
| Heaps | |
| |
| |
| A Heap Implementation of the ADT Priority Queue | |
| |
| |
| Heapsort | |
| |
| |
| |
| Tables and Priority Queues in the JCF | |
| |
| |
| The JCF Map Interface | |
| |
| |
| The JCF Set Interface | |
| |
| |
| The JCF PriorityQueue Class | |
| |
| |
| Summary | |
| |
| |
| Cautions | |
| |
| |
| Self-Test Exercises | |
| |
| |
| Exercises | |
| |
| |
| Programming Problems | |
| |
| |
| |
| Advanced Implementations of Tables | |
| |
| |
| |
| Balanced Search Trees | |
| |
| |
| 2-3 Trees | |
| |
| |
| 2-3-4 Trees | |
| |
| |
| Red-Black Trees | |
| |
| |
| AVL Trees | |
| |
| |
| |
| Hashing | |
| |
| |
| Hash Functions | |
| |
| |
| Resolving Collisions | |
| |
| |
| The Efficiency of Hashing | |
| |
| |
| What Constitutes a Good Hash Function? | |
| |
| |
| Table Traversal: An Inefficient Operation under Hashing | |
| |
| |
| The JCF Hashtable and TreeMap Classes | |
| |
| |
| The Hashtable Class | |
| |
| |
| The TreeMap Class | |
| |
| |
| |
| Data with Multiple Organizations | |
| |
| |
| Summary | |
| |
| |
| Cautions | |
| |
| |
| Self-Test Exercises | |
| |
| |
| Exercises | |
| |
| |
| Programming Problems | |
| |
| |
| |
| Graphs | |
| |
| |
| |
| Terminology | |
| |
| |
| |
| Graphs as ADTs | |
| |
| |
| Implementing Graphs | |
| |
| |
| Implementing a Graph Class Using the JCF | |
| |
| |
| |
| Graph Traversals | |
| |
| |
| Depth-First Search | |
| |
| |
| Breadth-First Search | |
| |
| |
| Implementing a BFS Iterator Class Using the JCF | |
| |
| |
| |
| Applications of Graphs | |
| |
| |
| Topological Sorting | |
| |
| |
| Spanning Trees | |
| |
| |
| Minimum Spanning Trees | |
| |
| |
| Shortest Paths | |
| |
| |
| Circuits | |
| |
| |
| Some Difficult Problems | |
| |
| |
| Summary | |
| |
| |
| Cautions | |
| |
| |
| Self-Test Exercises | |
| |
| |
| Exercises | |
| |
| |
| Programming Problems | |
| |
| |
| |
| External Methods | |
| |
| |
| |
| A Look at External Storage | |
| |
| |
| |
| Sorting Data in an External File | |
| |
| |
| |
| External Tables | |
| |
| |
| Indexing an External File | |
| |
| |
| External Hashing | |
| |
| |
| B-Trees | |
| |
| |
| Traversals | |
| |
| |
| Multiple Indexing | |
| |
| |
| Summary | |
| |
| |
| Cautions | |
| |
| |
| Self-Test Exercises | |
| |
| |
| Exercises | |
| |
| |
| Programming Problems | |
| |
| |
| |
| A Comparison of Java to C++ | |
| |
| |
| |
| Unicode Character Codes (ASCII Subset) | |
| |
| |
| |
| Java Resources | |
| |
| |
| Java Web Sites | |
| |
| |
| Using Java SE 6 | |
| |
| |
| Integrated Development Environments (IDEs) | |
| |
| |
| |
| Mathematical Induction | |
| |
| |
| Example 1 | |
| |
| |
| Example 2 | |
| |
| |
| Example 3 | |
| |
| |
| Example 4 | |
| |
| |
| Example 5 | |
| |
| |
| Self-Test Exercises | |
| |
| |
| Exercises | |
| |
| |
| Glossary | |
| |
| |
| Self-Test Answers | |
| |
| |
| Index | |