Data Abstraction and Problem Solving with Java

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 Exercises 301
Exercises 303 Programming Problems 307


PART TWOProblem Solving with Abstract Data Types 313
6 Recursion as a Problem-Solving Technique 315
6.1 Backtracking 316
The Eight Queens Problem 316
6.2 Defining Languages 321
The Basics of Grammars 322
Two Simple Languages 323
Algebraic Expressions 326
6.3 The Relationship Between Recursion and Mathematical Induction 336
The Correctness of the Recursive Factorial Method 336
The Cost of Towers of Hanoi 337
Summary 339 Cautions 339 Self-Test Exercises 340
Exercises 340 Programming Problems 344


7 Stacks 351
7.1 The Abstract Data Type Stack 352
Developing an ADT During the Design of a Solution 352
7.2 Simple Applications of the ADT Stack 358
Checking for Balanced Braces 358
Recognizing Strings in a Language 362
7.3 Implementations of the ADT Stack 363
An Array-Based Implementation of the ADT Stack 365
A Reference-Based Implementation of the ADT Stack 367
An Implementation That Uses the ADT List 369
Comparing Implementations 371
The Java Collections Framework Class Stack 371
7.4 Application: Algebraic Expressions 373
Evaluating Postfix Expressions 373
Converting Infix Expressions to Equivalent Postfix Expressions 375
7.5 Application: A Search Problem 378
A Nonrecursive Solution That Uses a Stack 380
A Recursive Solution 388
7.6 The Relationship Between Stacks and Recursion 391
Summary 393 Cautions 393 Self-Test Exercises 394
Exercises 395 Programming Problems 400


8 Queues 409
8.1 The Abstract Data Type Queue 410
8.2 Simple Applications of the ADT Queue 412
Reading a String of Characters 412
Recognizing Palindromes 413
8.3 Implementations of the ADT Queue 414
A Reference-Based Implementation 416
An Array-Based Implementation 419
An Implementation That Uses the ADT List 425
The JCF Interfaces Queue and Deque 426
Comparing Implementations 432
8.4 A Summary of Position-Oriented ADTs 433
8.5 Application: Simulation 434
Summary 444 Cautions 445 Self-Test Exercises 445
Exercises 446 Programming Problems 450


9 Advanced Java Topics 455
9.1 Inheritance Revisited 456
Java Access Modifiers 462
Is-a and Has-a Relationships 464
9.2 Dynamic Binding and Abstract Classes 466
Abstract Classes 469
Java Interfaces Revisited 474
9.3 Java Generics 475
Generic Classes 475
Generic Wildcards 477
Generic Classes and Inheritance 478
Generic Implementation of the Class List 481
Generic Methods 483
9.4 The ADTs List and Sorted List Revisited 484
Implementations of the ADT Sorted List That Use the ADT List 485
9.5 Iterators 489
Summary 493 Cautions 494 Self-Test Exercises 494
Exercises 495 Programming Problems 500

10 Algorithm Efficiency and Sorting 505
10.1 Measuring the Efficiency of Algorithms 506
The Execution Time of Algorithms 507
Algorithm Growth Rates 509
Order-of-Magnitude Analysis and Big O Notation 509
Keeping Your Perspective 515
The Efficiency of Searching Algorithms 517
10.2 Sorting Algorithms and Their Efficiency 518
Selection Sort 519
Bubble Sort 523
Insertion Sort 525
Mergesort 527
Quicksort 533
Radix Sort 545
A Comparison of Sorting Algorithms 547
The Java Collections Framework Sort Algorithm 548
Summary 552 Cautions 553 Self-Test Exercises 553
Exercises 554 Programming Problems 558


11 Trees 561
11.1 Terminology 562
11.2 The ADT Binary Tree 570
Basic Operations of the ADT Binary Tree 570
General Operations of the ADT Binary Tree 571
Traversals of a Binary Tree 574
Possible Representations of a Binary Tree 577
A Reference-Based Implementation of the ADT Binary Tree 581
Tree Traversals Using an Iterator 586
11.3 The ADT Binary Search Tree 594
Algorithms for the Operations of the ADT Binary Search Tree 600
A Reference-Based Implementation
of the ADT Binary Search Tree 615
The Efficiency of Binary Search Tree Operations 619
Treesort 624
Saving a Binary Search Tree in a File 625
The JCF Binary Search Algorithm 628
11.4 General Trees 629
Summary 631 Cautions 632 Self-Test Exercises 632
Exercises 634 Programming Problems 640


12 Tables and Priority Queues 643
12.1 The ADT Table 644
Selecting an Implementation 651
A Sorted Array-Based Implementation of the ADT Table 658
A Binary Search Tree Implementation of the ADT Table 661
12.2 The ADT Priority Queue: A Variation of the ADT Table 663
Heaps 667
A Heap Implementation of the ADT Priority Queue 676
Heapsort 678
12.3 Tables and Priority Queues in the JCF 681
The JCF Map Interface 681
The JCF Set Interface 685
The JCF PriorityQueue Class 689
Summary 691 Cautions 692 Self-Test Exercises 692
Exercises 693 Programming Problems 696


13 Advanced Implementations of Tables 699
13.1 Balanced Search Trees 700
2-3 Trees 701
2-3-4 Trees 721
Red-Black Trees 728
AVL Trees 731
13.2 Hashing 737
Hash Functions 741
Resolving Collisions 743
The Efficiency of Hashing 752
What Constitutes a Good Hash Function? 755
Table Traversal: An Inefficient Operation under Hashing 757
The JCF Hashtable and TreeMap Classes 758
The Hashtable Class 758
The TreeMap Class 761
13.3 Data with Multiple Organizations 764
Summary 769 Cautions 770 Self-Test Exercises 771
Exercises 771 Programming Problems 774


14 Graphs 777
14.1 Terminology 778
14.2 Graphs as ADTs 781
Implementing Graphs 782
Implementing a Graph Class Using the JCF 785
14.3 Graph Traversals 788
Depth-First Search 790
Breadth-First Search 791
Implementing a BFS Iterator Class Using the JCF 793
14.4 Applications of Graphs 796
Topological Sorting 796
Spanning Trees 799
Minimum Spanning Trees 804
Shortest Paths 807
Circuits 811
Some Difficult Problems 814
Summary 815 Cautions 816 Self-Test Exercises 816
Exercises 817 Programming Problems 820


15 External Methods 823
15.1 A Look at External Storage 824
15.2 Sorting Data in an External File 827
15.3 External Tables 835
Indexing an External File 837
External Hashing 841
B-Trees 845
Traversals 855
Multiple Indexing 857
Summary 858 Cautions 859 Self-Test Exercises 859
Exercises 859 Programming Problems 862


A. A Comparison of Java to C++ 863
B. Unicode Character Codes (ASCII Subset) 867
C. Java Resources 868
Java Web Sites 868
Using Java SE 6 868
Integrated Development Environments (IDEs) 869
D. Mathematical Induction 870
Example 1 870
Example 2 871
Example 3 872
Example 4 873
Example 5 873
Self-Test Exercises 874 Exercises 874
Glossary 877
Self-Test Answers 897
Index 921