Data Abstraction and Problem Solving with Java: Walls and Mirrors

Preface xv
Chapter Dependency Chart xviii
PART ONE Problem-Solving Techniques 1
1 Review of Java Fundamentals 3
1.1 Language Basics 4
Comments 4
Identifiers and Keywords 4
Variables 4
Primitive Data Types 5
References 6
Literal Constants 6
Named Constants 7
Assignments and Expressions 8
Arrays 11
1.2 Selection Statements 14
The if Statement 15
The switch Statement 16
1.3 Iteration Statements 17
The while Statement 17
The for Statement 18
The do Statement 21
1.4 Program Structure 21
Packages 22
Classes 23
Data Fields 24
Methods 26
How to Access Members of an Object 30
Class Inheritance 30
1.5 Useful Java Classes 32
The Object Class 32
The Array Class 34
String Classes 35
1.6 Java Exceptions 40
Catching Exceptions 40
Throwing Exceptions 47
1.7 Text Input and Output 49
Input 49
Output 51
The Console Class 54
1.8 File Input and Output 56
Text Files 58
Object Serialization 66
Summary 69 Cautions 72 Self-Test Exercises 72
Exercises 73 Programming Problems 78


2 Principles of Programming and Software Engineering 81
2.1 Problem Solving and Software Engineering 82
What Is Problem Solving? 82
The Life Cycle of Software 83
What Is a Good Solution? 93
2.2 Achieving an Object-Oriented Design 95
Abstraction and Information Hiding 96
Object-Oriented Design 98
Functional Decomposition 100
General Design Guidelines 101
Modeling Object-Oriented Designs Using UML 102
Advantages of an Object-Oriented Approach 106
2.3 A Summary of Key Issues in Programming 107
Modularity 107
Modifiability 109
Ease of Use 111
Fail-Safe Programming 112
Style 118
Debugging 122
Summary 125 Cautions 126 Self-Test Exercises 126
Exercises 127 Programming Problems 132


3 Recursion: The Mirrors 137
3.1 Recursive Solutions 138
A Recursive Valued Method: The Factorial of n 141
A Recursive void Method: Writing a String Backward 148
3.2 Counting Things 159
Multiplying Rabbits (The Fibonacci Sequence) 159
Organizing a Parade 161
Mr. Spock’s Dilemma (Choosing k out of n Things) 164
3.3 Searching an Array 166
Finding the Largest Item in an Array 167
Binary Search 168
Finding the k th Smallest Item in an Array 172
3.4 Organizing Data 176
The Towers of Hanoi 176
3.5 Recursion and Efficiency 180
Summary 187 Cautions 187 Self-Test Exercises 188
Exercises 189 Programming Problems 195


4 Data Abstraction: The Walls 197
4.1 Abstract Data Types 198
4.2 Specifying ADTs 203
The ADT List 204
The ADT Sorted List 209
Designing an ADT 211
Axioms (Optional) 215
4.3 Implementing ADTs 218
Java Classes Revisited 219
Java Interfaces 221
Java Packages 224
An Array-Based Implementation of the ADT List 226
Summary 233 Cautions 233 Self-Test Exercises 234
Exercises 235 Programming Problems 238


5 Linked Lists 241
5.1 Preliminaries 242
Object References 242
Resizeable Arrays 248
Reference-Based Linked Lists 249
5.2 Programming with Linked Lists 253
Displaying the Contents of a Linked List 253
Deleting a Specified Node from a Linked List 255
Inserting a Node into a Specified Position of a Linked List 258
A Reference-Based Implementation of the ADT List 264
Comparing Array-Based and Reference-Based Implementations 268
Passing a Linked List to a Method 271
Processing Linked Lists Recursively 271
5.3 Variations of the Linked List 277
Tail References 277
Circular Linked Lists 278
Dummy Head Nodes 280
Doubly Linked Lists 280
5.4 Application: Maintaining an Inventory 284
5.5 The Java Collections Framework 290
Generics 291
Iterators 292
The Java Collection’s Framework List Interface 295
Summary 298 Cautions 300 Self-Test Exe