Data Abstraction and Problem Solving with Java: Walls and Mirrors

<p>Preface xv<br>Chapter Dependency Chart xviii<br><strong>PART ONE Problem-Solving Techniques 1</strong><br><strong>1 Review of Java Fundamentals 3</strong><br>1.1 Language Basics 4<br>Comments 4<br>Identifiers and Keywords 4<br>Variables 4<br>Primitive Data Types 5<br>References 6<br>Literal Constants 6<br>Named Constants 7<br>Assignments and Expressions 8<br>Arrays 11<br>1.2 Selection Statements 14<br>The if Statement 15<br>The switch Statement 16<br>1.3 Iteration Statements 17<br>The while Statement 17<br>The for Statement 18<br>The do Statement 21<br>1.4 Program Structure 21<br>Packages 22<br>Classes 23<br>Data Fields 24<br>Methods 26<br>How to Access Members of an Object 30<br>Class Inheritance 30<br>1.5 Useful Java Classes 32<br>The Object Class 32<br>The Array Class 34<br>String Classes 35<br>1.6 Java Exceptions 40<br>Catching Exceptions 40<br>Throwing Exceptions 47<br>1.7 Text Input and Output 49<br>Input 49<br>Output 51<br>The Console Class 54<br>1.8 File Input and Output 56<br>Text Files 58<br>Object Serialization 66<br>Summary 69 Cautions 72 Self-Test Exercises 72<br>Exercises 73 Programming Problems 78<br></p> <p><strong>2 Principles of Programming and Software Engineering 81</strong><br>2.1 Problem Solving and Software Engineering 82<br>What Is Problem Solving? 82<br>The Life Cycle of Software 83<br>What Is a Good Solution? 93<br>2.2 Achieving an Object-Oriented Design 95<br>Abstraction and Information Hiding 96<br>Object-Oriented Design 98<br>Functional Decomposition 100<br>General Design Guidelines 101<br>Modeling Object-Oriented Designs Using UML 102<br>Advantages of an Object-Oriented Approach 106<br>2.3 A Summary of Key Issues in Programming 107<br>Modularity 107<br>Modifiability 109<br>Ease of Use 111<br>Fail-Safe Programming 112<br>Style 118<br>Debugging 122<br>Summary 125 Cautions 126 Self-Test Exercises 126<br>Exercises 127 Programming Problems 132<br></p> <p><strong>3 Recursion: The Mirrors 137</strong><br>3.1 Recursive Solutions 138<br>A Recursive Valued Method: The Factorial of n 141<br>A Recursive void Method: Writing a String Backward 148<br>3.2 Counting Things 159<br>Multiplying Rabbits (The Fibonacci Sequence) 159<br>Organizing a Parade 161<br>Mr. Spock’s Dilemma (Choosing k out of n Things) 164<br>3.3 Searching an Array 166<br>Finding the Largest Item in an Array 167<br>Binary Search 168<br>Finding the k th Smallest Item in an Array 172<br>3.4 Organizing Data 176<br>The Towers of Hanoi 176<br>3.5 Recursion and Efficiency 180<br>Summary 187 Cautions 187 Self-Test Exercises 188<br>Exercises 189 Programming Problems 195<br></p> <p><strong>4 Data Abstraction: The Walls 197</strong><br>4.1 Abstract Data Types 198<br>4.2 Specifying ADTs 203<br>The ADT List 204<br>The ADT Sorted List 209<br>Designing an ADT 211<br>Axioms (Optional) 215<br>4.3 Implementing ADTs 218<br>Java Classes Revisited 219<br>Java Interfaces 221<br>Java Packages 224<br>An Array-Based Implementation of the ADT List 226<br>Summary 233 Cautions 233 Self-Test Exercises 234<br>Exercises 235 Programming Problems 238<br></p> <p><strong>5 Linked Lists 241</strong><br>5.1 Preliminaries 242<br>Object References 242<br>Resizeable Arrays 248<br>Reference-Based Linked Lists 249<br>5.2 Programming with Linked Lists 253<br>Displaying the Contents of a Linked List 253<br>Deleting a Specified Node from a Linked List 255<br>Inserting a Node into a Specified Position of a Linked List 258<br>A Reference-Based Implementation of the ADT List 264<br>Comparing Array-Based and Reference-Based Implementations 268<br>Passing a Linked List to a Method 271<br>Processing Linked Lists Recursively 271<br>5.3 Variations of the Linked List 277<br>Tail References 277<br>Circular Linked Lists 278<br>Dummy Head Nodes 280<br>Doubly Linked Lists 280<br>5.4 Application: Maintaining an Inventory 284<br>5.5 The Java Collections Framework 290<br>Generics 291<br>Iterators 292<br>The Java Collection’s Framework List Interface 295<br>Summary 298 Cautions 300 Self-Test Exe</p>