Data Abstraction and Problem Solving with Java

Dr. Janet Prichard is an assistant professor at Bryant College where she teaches web design and development, object-oriented computing, operating systems, and data structures courses. She has a B.A. in mathematics from Providence College, and earned her M.S. and Ph.D. in computer science from the University of Rhode Island. Her academic interests include real-time databases, database query languages, object-oriented analysis and design methodologies, database standards, client-server models, and Internet security. Dr. Prichard is the lead author of the Third Edition of Data Abstraction and Problem Solving with Java.Frank M. Carrano is Professor Emeritus of Computer Science at the University of Rhode Island. He received his Ph.D. degree in Computer Science from Syracuse University in 1969. His interests include data structures, computer science education, social issues in computing, and numerical computation. Professor Carrano is particularly interested in the design and delivery of undergraduate courses in computer science. He has authored several well-known computer science textbooks for undergraduates.Frank’s Making it Real blog http://frank-m-carrano.com/blog/ extends his textbooks and lectures to a lively discussion with instructors and students about teaching and learning computer science.Follow Frank on Twitter: http://twitter.com/Frank_M_CarranoFind him on Facebook:

• Preface xvChapter Dependency Chart xviiiPART ONE Problem-Solving Techniques 11 Review of Java Fundamentals 31.1 Language Basics 4Comments 4Identifiers and Keywords 4Variables 4Primitive Data Types 5References 6Literal Constants 6Named Constants 7Assignments and Expressions 8Arrays 111.2 Selection Statements 14The if Statement 15The switch Statement 161.3 Iteration Statements 17The while Statement 17The for Statement 18The do Statement 211.4 Program Structure 21Packages 22Classes 23Data Fields 24Methods 26How to Access Members of an Object 30Class Inheritance 301.5 Useful Java Classes 32The Object Class 32The Array Class 34String Classes 351.6 Java Exceptions 40Catching Exceptions 40Throwing Exceptions 471.7 Text Input and Output 49Input 49Output 51The Console Class 541.8 File Input and Output 56Text Files 58Object Serialization 66Summary 69 Cautions 72 Self-Test Exercises 72Exercises 73 Programming Problems 78 2 Principles of Programming and Software Engineering 812.1 Problem Solving and Software Engineering 82What Is Problem Solving? 82The Life Cycle of Software 83What Is a Good Solution? 932.2 Achieving an Object-Oriented Design 95Abstraction and Information Hiding 96Object-Oriented Design 98Functional Decomposition 100General Design Guidelines 101Modeling Object-Oriented Designs Using UML 102Advantages of an Object-Oriented Approach 1062.3 A Summary of Key Issues in Programming 107Modularity 107Modifiability 109Ease of Use 111Fail-Safe Programming 112Style 118Debugging 122Summary 125 Cautions 126 Self-Test Exercises 126Exercises 127 Programming Problems 132 3 Recursion: The Mirrors 1373.1 Recursive Solutions 138A Recursive Valued Method: The Factorial of n 141A Recursive void Method: Writing a String Backward 1483.2 Counting Things 159Multiplying Rabbits (The Fibonacci Sequence) 159Organizing a Parade 161Mr. Spock’s Dilemma (Choosing k out of n Things) 1643.3 Searching an Array 166Finding the Largest Item in an Array 167Binary Search 168Finding the k th Smallest Item in an Array 1723.4 Organizing Data 176The Towers of Hanoi 1763.5 Recursion and Efficiency 180Summary 187 Cautions 187 Self-Test Exercises 188Exercises 189 Programming Problems 195 4 Data Abstraction: The Walls 1974.1 Abstract Data Types 1984.2 Specifying ADTs 203The ADT List 204The ADT Sorted List 209Designing an ADT 211Axioms (Optional) 2154.3 Implementing ADTs 218Java Classes Revisited 219Java Interfaces 221Java Packages 224An Array-Based Implementation of the ADT List 226Summary 233 Cautions 233 Self-Test Exercises 234Exercises 235 Programming Problems 238 5 Linked Lists 2415.1 Preliminaries 242Object References 242Resizeable Arrays 248Reference-Based Linked Lists 2495.2 Programming with Linked Lists 253Displaying the Contents of a Linked List 253Deleting a Specified Node from a Linked List 255Inserting a Node into a Specified Position of a Linked List 258A Reference-Based Implementation of the ADT List 264Comparing Array-Based and Reference-Based Implementations 268Passing a Linked List to a Method 271Processing Linked Lists Recursively 2715.3 Variations of the Linked List 277Tail References 277Circular Linked Lists 278Dummy Head Nodes 280Doubly Linked Lists 2805.4 Application: Maintaining an Inventory 2845.5 The Java Collections Framework 290Generics 291Iterators 292The Java Collection’s Framework List Interface 295Summary 298 Cautions 300 Self-Test Exercises 301Exercises 303 Programming Problems 307 PART TWOProblem Solving with Abstract Data Types 3136 Recursion as a Problem-Solving Technique 3156.1 Backtracking 316The Eight Queens Problem 3166.2 Defining Languages 321The Basics of Grammars 322Two Simple Languages 323Algebraic Expressions 3266.3 The Relationship Between Recursion and Mathematical Induction 336The Correctness of the Recursive Factorial Method 336The Cost of Towers of Hanoi 337Summary 339 Cautions 339 Self-Test Exercises 340Exercises 340 Programming Problems 344 7 Stacks 3517.1 The Abstract Data Type Stack 352Developing an ADT During the Design of a Solution 3527.2 Simple Applications of the ADT Stack 358Checking for Balanced Braces 358Recognizing Strings in a Language 3627.3 Implementations of the ADT Stack 363An Array-Based Implementation of the ADT Stack 365A Reference-Based Implementation of the ADT Stack 367An Implementation That Uses the ADT List 369Comparing Implementations 371The Java Collections Framework Class Stack 3717.4 Application: Algebraic Expressions 373Evaluating Postfix Expressions 373Converting Infix Expressions to Equivalent Postfix Expressions 3757.5 Application: A Search Problem 378A Nonrecursive Solution That Uses a Stack 380A Recursive Solution 3887.6 The Relationship Between Stacks and Recursion 391Summary 393 Cautions 393 Self-Test Exercises 394Exercises 395 Programming Problems 400 8 Queues 4098.1 The Abstract Data Type Queue 4108.2 Simple Applications of the ADT Queue 412Reading a String of Characters 412Recognizing Palindromes 4138.3 Implementations of the ADT Queue 414A Reference-Based Implementation 416An Array-Based Implementation 419An Implementation That Uses the ADT List 425The JCF Interfaces Queue and Deque 426Comparing Implementations 4328.4 A Summary of Position-Oriented ADTs 4338.5 Application: Simulation 434Summary 444 Cautions 445 Self-Test Exercises 445Exercises 446 Programming Problems 450 9 Advanced Java Topics 4559.1 Inheritance Revisited 456Java Access Modifiers 462Is-a and Has-a Relationships 4649.2 Dynamic Binding and Abstract Classes 466Abstract Classes 469Java Interfaces Revisited 4749.3 Java Generics 475Generic Classes 475Generic Wildcards 477Generic Classes and Inheritance 478Generic Implementation of the Class List 481Generic Methods 4839.4 The ADTs List and Sorted List Revisited 484Implementations of the ADT Sorted List That Use the ADT List 4859.5 Iterators 489Summary 493 Cautions 494 Self-Test Exercises 494Exercises 495 Programming Problems 500 10 Algorithm Efficiency and Sorting 50510.1 Measuring the Efficiency of Algorithms 506The Execution Time of Algorithms 507Algorithm Growth Rates 509Order-of-Magnitude Analysis and Big O Notation 509Keeping Your Perspective 515The Efficiency of Searching Algorithms 51710.2 Sorting Algorithms and Their Efficiency 518Selection Sort 519Bubble Sort 523Insertion Sort 525Mergesort 527Quicksort 533Radix Sort 545A Comparison of Sorting Algorithms 547The Java Collections Framework Sort Algorithm 548Summary 552 Cautions 553 Self-Test Exercises 553Exercises 554 Programming Problems 558 11 Trees 56111.1 Terminology 56211.2 The ADT Binary Tree 570Basic Operations of the ADT Binary Tree 570General Operations of the ADT Binary Tree 571Traversals of a Binary Tree 574Possible Representations of a Binary Tree 577A Reference-Based Implementation of the ADT Binary Tree 581Tree Traversals Using an Iterator 58611.3 The ADT Binary Search Tree 594Algorithms for the Operations of the ADT Binary Search Tree 600A Reference-Based Implementationof the ADT Binary Search Tree 615The Efficiency of Binary Search Tree Operations 619Treesort 624Saving a Binary Search Tree in a File 625The JCF Binary Search Algorithm 62811.4 General Trees 629Summary 631 Cautions 632 Self-Test Exercises 632Exercises 634 Programming Problems 640 12 Tables and Priority Queues 64312.1 The ADT Table 644Selecting an Implementation 651A Sorted Array-Based Implementation of the ADT Table 658A Binary Search Tree Implementation of the ADT Table 66112.2 The ADT Priority Queue: A Variation of the ADT Table 663Heaps 667A Heap Implementation of the ADT Priority Queue 676Heapsort 67812.3 Tables and Priority Queues in the JCF 681The JCF Map Interface 681The JCF Set Interface 685The JCF PriorityQueue Class 689Summary 691 Cautions 692 Self-Test Exercises 692Exercises 693 Programming Problems 696 13 Advanced Implementations of Tables 69913.1 Balanced Search Trees 7002-3 Trees 7012-3-4 Trees 721Red-Black Trees 728AVL Trees 73113.2 Hashing 737Hash Functions 741Resolving Collisions 743The Efficiency of Hashing 752What Constitutes a Good Hash Function? 755Table Traversal: An Inefficient Operation under Hashing 757The JCF Hashtable and TreeMap Classes 758The Hashtable Class 758The TreeMap Class 76113.3 Data with Multiple Organizations 764Summary 769 Cautions 770 Self-Test Exercises 771Exercises 771 Programming Problems 774 14 Graphs 77714.1 Terminology 77814.2 Graphs as ADTs 781Implementing Graphs 782Implementing a Graph Class Using the JCF 78514.3 Graph Traversals 788Depth-First Search 790Breadth-First Search 791Implementing a BFS Iterator Class Using the JCF 79314.4 Applications of Graphs 796Topological Sorting 796Spanning Trees 799Minimum Spanning Trees 804Shortest Paths 807Circuits 811Some Difficult Problems 814Summary 815 Cautions 816 Self-Test Exercises 816Exercises 817 Programming Problems 820 15 External Methods 82315.1 A Look at External Storage 82415.2 Sorting Data in an External File 82715.3 External Tables 835Indexing an External File 837External Hashing 841B-Trees 845Traversals 855Multiple Indexing 857Summary 858 Cautions 859 Self-Test Exercises 859Exercises 859 Programming Problems 862 A. A Comparison of Java to C++ 863B. Unicode Character Codes (ASCII Subset) 867C. Java Resources 868Java Web Sites 868Using Java SE 6 868Integrated Development Environments (IDEs) 869D. Mathematical Induction 870Example 1 870Example 2 871Example 3 872Example 4 873Example 5 873Self-Test Exercises 874 Exercises 874Glossary 877Self-Test Answers 897Index 921