Java Foundations

Inspired by the success of their best-selling introductory programming text, Java Software Solutions, authors Lewis, DePasquale, and Chase now release Java Foundations, Third Edition. This text is a comprehensive resource for instructors who want a two-or three-semester introduction to programming textbook that includes detail on data structures topics. Java Foundations introduces a Software Methodology early on and revisits it throughout to ensure students develop sound program development skills from the beginning. Control structures are covered before writing classes, providing a solid foundation of fundamental concepts and sophisticated topics.

Table of Contents:
Preface vii Chapter 1 Introduction 1 1.1 The Java Programming Language 2 A Java Program 3 Comments 5 Identifiers and Reserved Words 7 White Space 9 1.2 Program Development 11 Programming Language Levels 11 Editors, Compilers, and Interpreters 13 Development Environments 15 Syntax and Semantics 16 Errors 17 1.3 Problem Solving 18 1.4 Software Development Activities 20 1.5 Object-Oriented Programming 21 Object-Oriented Software Principles 22   Chapter 2 Data and Expressions 33 2.1 Character Strings 34 The print and println Methods 34 String Concatenation 36 Escape Sequences 40 2.2 Variables and Assignment 41 Variables 41 The Assignment Statement 44 Constants 46 2.3 Primitive Data Types 47 Integers and Floating Points 47 Characters 48 Booleans 50 2.4 Expressions 51 Arithmetic Operators 51 Operator Precedence 52 Increment and Decrement Operators 56 Assignment Operators 57 2.5 Data Conversion 58 Conversion Techniques 60 2.6 Reading Input Data 61 The Scanner Class 61   Chapter 3 Using Classes and Objects 75 3.1 Creating Objects 76 Aliases 78 3.2 The String Class 80 3.3 Packages 83 The import Declaration 84 3.4 The Random Class 86 3.5 The Math Class 89 3.6 Formatting Output 92 The NumberFormat Class 92 The DecimalFormat Class 94 The printf Method 96 3.7 Enumerated Types 97 3.8 Wrapper Classes 100 Autoboxing 102   Chapter 4 Conditionals and Loops 111 4.1 Boolean Expressions 112 Equality and Relational Operators 113 Logical Operators 114 4.2 The if Statement 116 The if-else Statement 119 Using Block Statements 121 The Conditional Operator 124 Nested if Statements 125 4.3 Comparing Data 127 Comparing Floats 127 Comparing Characters 127 Comparing Objects 128 4.4 The switch Statement 130 4.5 The while Statement 134 Infinite Loops 140 Nested Loops 141 Other Loop Controls 144 4.6 Iterators 145 Reading Text Files 146 4.7 The do Statement 148 4.8 The for Statement 151 Iterators and for Loops 156 Comparing Loops 157   Chapter 5 Writing Classes 169 5.1 Classes and Objects Revisited 170 Identifying Classes and Objects 171 Assigning Responsibilities 173 5.2 Anatomy of a Class 173 Instance Data 178 UML Class Diagrams 179 5.3 Encapsulation 181 Visibility Modifiers 182 Accessors and Mutators 183 5.4 Anatomy of a Method 188 The return Statement 194 Parameters 196 Local Data 197 Constructors Revisited 198 5.5 Static Class Members 199 Static Variables 199 Static Methods 200 5.6 Class Relationships 203 Dependency 203 Dependencies among Objects of the Same Class 204 Aggregation 206 The this Reference 211 5.7 Method Design 212 Method Decomposition 213 Method Parameters Revisited 218 5.8 Method Overloading 223 5.9 Testing 224 Reviews 225 Defect Testing 226 Unit Testing 227 Integration Testing 228 System Testing 228 Test-Driven Development 228 5.10 Debugging 229 Simple Debugging with print Statements 230 Debugging Concepts 230   Chapter 6 Graphical User Interfaces 245 6.1 GUI Elements 246 Frames and Panels 247 Buttons and Action Events 251 Determining Event Sources 253 6.2 More Components 256 Text Fields 257 Check Boxes 260 Radio Buttons 263 Sliders 267 Combo Boxes 272 Timers 277 6.3 Layout Managers 282 Flow Layout 285 Border Layout 288 Grid Layout 291 Box Layout 293 Containment Hierarchies 296 6.4 Mouse and Key Events 297 Mouse Events 297 Key Events 305 Extending Adapter Classes 310 6.5 Dialog Boxes 311 File Choosers 314 Color Choosers 316 6.6 Some Important Details 317 Borders 317 Tool Tips and Mnemonics 321 6.7 GUI Design 328 Chapter 7 Arrays 339 7.1 Array Elements 340 Overview of Arrays 341 7.2 Declaring and Using Arrays 341 Bounds Checking 344 Alternative Array Syntax 349 Initializer Lists 350 Arrays as Parameters 351 7.3 Arrays of Objects 351 7.4 Command-Line Arguments 361 7.5 Variable-Length Parameter Lists 363 7.6 Two-Dimensional Arrays 367 Multidimensional Arrays 370   Chapter 8 Inheritance 379 8.1 C reating Subclasses 380 The protected Modifier 385 The super Reference 386 Multiple Inheritance 390 8.2 Overriding Methods 391 Shadowing Variables 394 8.3 C lass Hierarchies 394 The Object Class 395 Abstract Classes 397 8.4 Visibility 399 8.5 Designing for Inheritance 401 Restricting Inheritance 402   Chapter 9 Polymorphism 411 9.1 Dynamic Binding 412 9.2 Polymorphism via Inheritance 413 9.3 Interfaces 425 Interface Hierarchies 430 The Comparable Interface 431 The Iterator Interface 431 9.4 Polymorphism via Interfaces 432 Event Processing 434   Chapter 10 Exceptions 441 10.1 Exception Handling 442 10.2 Uncaught Exceptions 443 10.3 The try-catch Statement 444 The finally Clause 447 10.4 Exception Propagation 448 10.5 The Exception Class Hierarchy 451 Checked and Unchecked Exceptions 455 10.6 I/O Exceptions 455   Chapter 11 Analysis of Algorithms 465 11.1 Algorithm Efficiency 466 11.2 Growth Functions and Big-Oh Notation 467 11.3 Comparing Growth Functions 469 11.4 Determining Time Complexity 471 Analyzing Loop Execution 471 Nested Loops 472 Method Calls 473   Chapter 12 Introduction to Collections–Stacks 479 12.1 Collections 480 Abstract Data Types 481 The Java Collections API 483 12.2 A Stack Collection 483 12.3 C rucial OO Concepts 485 Inheritance and Polymorphism 486 Generics 487 12.4 Using Stacks: Evaluating Postfix Expressions 488 Javadoc 496 12.5 Exceptions 497 12.6 A Stack ADT 498 12.7 Implementing a Stack: With Arrays 501 Managing Capacity 502 12.8 The ArrayStack Class 503 The Constructors 504 The push Operation 506 The pop Operation 508 The peek Operation 509 Other Operations 509 The EmptyCollectionException Class 510 Other Implementations 511   Chapter 13 Linked Structures–Stacks 519 13.1 References as Links 520 13.2 Managing Linked Lists 522 Accessing Elements 522 Inserting Nodes 523 Deleting Nodes 524 13.3 Elements without Links 525 Doubly Linked Lists 525 13.4 Stacks in the Java API 526 13.5 Using Stacks: Traversing a Maze 527 13.6 Implementing a Stack: With Links 536 The LinkedStack Class 536 The push Operation 540 The pop Operation 542 Other Operations 543   Chapter 14 Queues 549 14.1 A Conceptual Queue 550 14.2 Queues in the Java API 551 14.3 Using Queues: Code Keys 552 14.4 Using Queues: Ticket Counter Simulation 556 14.5 A Queue ADT 561 14.6 A Linked Implementation of a Queue 562 The enqueue Operation 564 The dequeue Operation 566 Other Operations 567 14.7 Implementing Queues: With Arrays 568 The enqueue Operation 572 The dequeue Operation 574 Other Operations 575 14.8 Double-Ended Queues (Deque) 575   Chapter 15 Lists 581 15.1 A List Collection 582 15.2 Lists in the Java Collections API 584 15.3 Using Unordered Lists: Program of Study 585 15.4 Using Indexed Lists: Josephus 595 15.5 A List ADT 597 Adding Elements to a List 598 15.6 Implementing Lists with Arrays 603 The remove Operation 605 The contains Operation 607 The add Operation for an Ordered List 608 Operations Particular to Unordered Lists 609 The addAfter Operation for an Unordered List 609 15.7 Implementing Lists with Links 610 The remove Operation 611   Chapter 16 Iterators 619 16.1 What’s an Iterator? 620 Other Iterator Issues 622 16.2 Using Iterators: Program of Study Revisited 622 Printing Certain Courses 626 Removing Courses 627 16.3 Implementing Iterators: With Arrays 629 16.4 Implementing Iterators: With Links 631   Chapter 17 Recursion 637 17.1 Recursive Thinking 638 Infinite Recursion 638 Recursion in Math 639 17.2 Recursive Programming 640 Recursion versus Iteration 643 Direct versus Indirect Recursion 643 17.3 Using Recursion 644 Traversing a Maze 644 The Towers of Hanoi 652 17.4 Analyzing Recursive Algorithms 657   Chapter 18 Searching and Sorting 665 18.1 Searching 666 Static Methods 667 Generic Methods 667 Linear Search 668 Binary Search 670 Comparing Search Algorithms 672 18.2 Sorting 673 Selection Sort 676 Insertion Sort 678 Bubble Sort 680 Quick Sort 682 Merge Sort 686 18.3 Radix Sort 689   Chapter 19 Trees 699 19.1 Trees 700 Tree Classifications 701 19.2 Strategies for Implementing Trees 703 Computational Strategy for Array Implementation of Trees 703 Simulated Link Strategy for Array Implementation of Trees 703 Analysis of Trees 19.3 Tree Traversals 706 Preorder Traversal 706 Inorder Traversal 707 Postorder Traversal 707 Level-Order Traversal 708 19.4 A Binary Tree ADT 709 19.5 Using Binary Trees: Expression Trees 713 19.6 A Backpain Analyzer 725 19.7 Implementing Binary Trees with Links 729 The find Method 734 The iteratorInOrder Method 736   Chapter 20 Binary Search Trees 743 20.1 A Binary Search Tree 744 20.2 Implementing Binary Search Trees: With Links 746 The addElement Operation 747 The removeElement Operation 750 The removeAllOccurrences Operation 753 The removeMin Operation 754 Implementing Binary Search Trees: With Arrays 756 20.3 Using Binary Search Trees: Implementing Ordered Lists 756 Analysis of the BinarySearchTreeList Implementation 759 20.4 Balanced Binary Search Trees 760 Right Rotation 761 Left Rotation 762 Rightleft Rotation 763 Leftright Rotation 763 20.5 Implementing Binary Search Trees: AVL Trees 764 Right Rotation in an AVL Tree 765 Left Rotation in an AVL Tree 765 Rightleft Rotation in an AVL Tree 765 Leftright Rotation in an AVL Tree 767 20.6 Implementing Binary Search Trees: Red/Black Trees 767 Insertion into a Red/Black Tree 768 Element Removal from a Red/Black Tree 771   Chapter 21 Heaps and Priority Queues 781 21.1 A Heap 782 The addElement Operation 784 The removeMin Operation 785 The findMin Operation 786 21.2 Using Heaps: Priority Queues 786 The addElement Operation 790 The removeMin Operation 794 The findMin Operation 797 21.4 Implementing Heaps: With Arrays 797 The addElement Operation 799 The removeMin Operation 800 The findMin Operation 802 21.5 Using Heaps: Heap Sort 802   Chapter 22 Sets and Maps 809 22.1 Set and Map Collections 810 22.2 Sets and Maps in the Java API 810 22.3 Using Sets: Domain Blocker 813 22.4 Using Maps: Product Sales 816 22.5 Using Maps: User Management 820 22.6 Implementing Sets and Maps Using Trees 825 22.7 Implementing Sets and Maps Using Hashing 825   Chapter 23 Multi-way Search Trees 833 23.1 Combining Tree Concepts 834 23.2 2-3 Trees 834 Inserting Elements into a 2-3 Tree 835 Removing Elements from a 2-3 Tree 837 23.3 2-4 Trees 840 23.4 B-Trees 842 B*-Trees 843 B+-Trees 843 Analysis of B-Trees 844 23.5 Implementation Strategies for B-Trees 844   Chapter 24 Graphs 1 24.1 Undirected Graphs 2 24.2 Directed Graphs 3 24.3 Networks 5 24.4 Common Graph Algorithms 6 Traversals 6 Testing for Connectivity 10 Minimum Spanning Trees 12 Determining the Shortest Path 15 24.5 Strategies for Implementing Graphs 15 Adjacency Lists 16 Adjacency Matrices 16 24.6 Implementing Undirected Graphs with an Adjacency Matrix 17 The addEdge Method 22 The addVertex Method 22 The expandCapacity Method 23 Other Methods 24   Chapter 25 Databases 781 25.1 Introduction to Databases 782 25.2 Establishing a Connection to a Database 784 Obtaining a Database Driver 784 25.3 Creating and Altering Database Tables 787 Create Table 787 Alter Table 788 Drop Column 789 25.4 Querying the Database 789 Show Columns 790 25.5 Inserting, Viewing, and Updating Data 792 Insert 793 SELECT . . . FROM 793 Update 798 25.6 Deleting Data and Database Tables 799 Deleting Data 799 Deleting Database Tables 800   Appendix A    Glossary 905 Appendix B Number Systems 939 Place Value 940 Bases Higher Than 10 941 Conversions 942 Shortcut Conversions 945 Appendix C    The Unicode Character Set 951 Appendix D Java Operators 955 Java Bitwise Operators 957 Appendix E Java Modifiers 961 Java Visibility Modifiers 962 A Visibility Example 962 Other Java Modifiers 963 Appendix F    Java Graphics 965 Coordinate Systems 966 Representing Color 966 Drawing Shapes 967 Polygons and Polylines 976 The Polygon Class 980 Appendix G Java Applets 985 Embedding Applets in HTML 988 More Applet Methods 988 GUIs in Applets 993 Appendix H Regular Expressions 1003 Appendix I Hashing 1005 I.1 A Hashing 1006 I.2 Hashing Functions 1007 The Division Method 1008 The Folding Method 1008 The Mid-Square Method 1009 The Radix Transformation Method 1009 The Digit Analysis Method 1009 The Length-Dependent Method 1010 Hashing Functions in the Java Language 1010 I.3 Resolving Collisions 1010 Chaining 1011 Open Addressing 1012 I.4 Deleting Elements from a Hash Table 1015 Deleting from a Chained Implementation 1015 Deleting from an Open Addressing Implementation 1016 I.5 Hash Tables in the Java Collections API 1017 The Hashtable Class 1017 The HashSet Class 1019 The HashMap Class 1019 The IdentityHashMap Class 1020 I.6 The WeakHashMap Class 1021 LinkedHashSet and LinkedHashMap 1022 Appendix J Java Syntax 1029 Index 1043