Introduction to Java Programming and Data Structures (2019) by Y. Daniel Liang - PDF

 INTRODUCTION TO JAVA ™ PROGRAMMING AND DATA STRUCTURES COMPREHENSIVE...

 INTRODUCTION TO JAVA ™ PROGRAMMING AND DATA STRUCTURES COMPREHENSIVE VERSION Twelfth Edition Y. Daniel Liang Georgia Southern University A01_LIAN9966_12_SE_FM.indd 1 28/09/19 3:26 PM  To Samantha, Michael, and Michelle Microsoft and/or its respective suppliers make no representations about the suitability of the information ­contained in the documents and related graphics published as part of the services for any purpose. All such documents and related graphics are provided “as is” without warranty of any kind. Microsoft and/or its respective suppliers hereby disclaim all warranties and conditions with regard to this information, including all warranties and conditions of merchantability, whether express, implied or statutory, fitness for a particular purpose, title and non-infringement. In no event shall Microsoft and/or its respective suppliers be liable for any special, indirect or consequential ­damages or any damages whatsoever resulting from loss of use, data or profits, whether in an action of contract, negligence or other tortious action, arising out of or in connection with the use or performance of ­information ­available from the services. The documents and related graphics contained herein could include technical i­naccuracies or typographical errors. Changes are periodically added to the information herein. Microsoft and/or its respective suppliers may make improvements and/or changes in the product(s) and/or the program(s) described herein at any time. Partial screen shots may be viewed in full within the software version specified. Microsoft® and Windows® are registered trademarks of the Microsoft Corporation in the U.S.A. and other countries. This book is not sponsored or endorsed by or affiliated with the Microsoft Corporation. Copyright © 2020, 2018, 2015 by Pearson Education, Inc. or its affiliates, 221 River Street, Hoboken, NJ 07030. All Rights Reserved. Manufactured in the United States of America. This publication is protected by copyright, and permission should be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise. For information regarding permissions, request forms, and the appropriate contacts within the Pearson Education Global Rights and Permissions department, please visit www.pearsoned.com/permissions/. Acknowledgments of third-party content appear on the appropriate page within the text PEARSON, ALWAYS LEARNING, and MYLAB are exclusive trademarks owned by Pearson Education, Inc. or its affiliates in the U.S. and/or other countries. Unless otherwise indicated herein, any third-party trademarks, logos, or icons that may appear in this work are the property of their respective owners, and any references to third-party trademarks, logos, icons, or other trade dress are for demonstrative or descriptive purposes only. Such references are not intended to imply any sponsorship, endorsement, authorization, or promotion of Pearson’s products by the owners of such marks, or any relationship between the owner and Pearson Education, Inc., or its affiliates, authors, licensees, or distributors. Library of Congress Cataloging-in-Publication Data Names: Liang, Y. Daniel, author. Title: Java programming and data structures / Y. Daniel Liang, Georgia Southern University. Other titles: Introduction to Java programming and data structures Description: Twelfth edition. Comprehensive version | Hoboken, NJ : Pearson, 2019. | Revised edition of: Introduction to Java programming and data structures / Y. Daniel Liang, Georgia Southern University. Eleventh edition. Comprehensive version. 2018. | Includes bibliographical references and index. Identifiers: LCCN 2019038073 | ISBN 9780136520238 (paperback) Subjects: LCSH: Java (Computer program language) Classification: LCC QA76.73.J38 L52 2019 | DDC 005.13/3–dc23 LC record available at https://lccn.loc.gov/2019038073 ScoutAutomatedPrintCode LLE ISBN ISBN-10: 0-13-651996-2 ISBN-13: 978-0-13-651996-6 SE ISBN-10: 0-13-652023-5 ISBN-13: 978-0-13-652023-8 A01_LIAN9966_12_SE_FM.indd 2 28/09/19 3:26 PM  PREFACE Dear Reader, Many of you have provided feedback on earlier editions of this book, and your comments and suggestions have greatly improved the book. This edition has been substantially enhanced in presentation, organization, examples, exercises, and supplements. The book is fundamentals first by introducing basic programming concepts and techniques fundamentals-first before designing custom classes. The fundamental concepts and techniques of selection statements, loops, methods, and arrays are the foundation for programming. Building this strong foundation prepares students to learn object-oriented programming and advanced Java programming. This book teaches programming in a problem-driven way that focuses on problem solv- problem-driven ing rather than syntax. We make introductory programming interesting by using thought-­ provoking problems in a broad context. The central thread of early chapters is on problem solving. Appropriate syntax and library are introduced to enable readers to write programs for solving the problems. To support the teaching of programming in a problem-driven way, the book provides a wide variety of problems at various levels of difficulty to motivate students. To appeal to students in all majors, the problems cover many application areas, including math, science, business, financial, gaming, animation, and multimedia. The book seamlessly integrates programming, data structures, and algorithms into one text. data structures It employs a practical approach to teach data structures. We first introduce how to use various data structures to develop efficient algorithms, and then show how to implement these data structures. Through implementation, students gain a deep understanding on the efficiency of data structures and on how and when to use certain data structures. Finally, we design and implement custom data structures for trees and graphs. The book is widely used in the introductory programming, data structures, and algorithms courses in the universities around the world. This comprehensive version covers fundamen- comprehensive version tals of programming, object-oriented programming, GUI programming, data structures, algo- rithms, concurrency, networking, database, and Web programming. It is designed to prepare students to become proficient Java programmers. A brief version (Introduction to Java Pro- brief version gramming, Brief Version, Twelfth Edition) is available for a first course on programming, commonly known as CS1. The brief version contains the first 18 chapters of the comprehen- sive version. An AP version of the book is also available for high school students taking an AP Computer Science course. AP Computer Science The best way to teach programming is by example, and the only way to learn p­ rogramming examples and exercises is by doing. Basic concepts are explained by example and a large number of exercises with various levels of difficulty are provided for students to practice. For our programming courses, we assign programming exercises after each lecture. Our goal is to produce a text that teaches problem solving and programming in a broad context using a wide variety of interesting examples. If you have any comments on and ­suggestions for improving the book, please email me. Sincerely, Y. Daniel Liang [email protected] www.pearsonhighered.com/liang iii A01_LIAN9966_12_SE_FM.indd 3 28/09/19 3:26 PM  iv Preface ACM/IEEE Curricular 2013 and ABET Course Assessment The new ACM/IEEE Computer Science Curricular 2013 defines the Body of Knowledge organized into 18 Knowledge Areas. To help instructors design the courses based on this book, we provide sample syllabi to identify the Knowledge Areas and Knowledge Units. The ­sample syllabi are for a three semester course sequence and serve as an example for institutional ­customization. The sample syllabi are accessible from the Instructor Resource Website. Many of our users are from the ABET-accredited programs. A key component of the ABET accreditation is to identify the weakness through continuous course assessment against the course outcomes. We provide sample course outcomes for the courses and sam- ple exams for measuring course outcomes on the ­Instructor Resource Website. What’s New in This Edition? This edition is completely revised in every detail to enhance clarity, presentation, content, examples, and exercises. The major improvements are as follows: Updated to Java 9, 10, and 11. Examples are improved and simplified by using the new features in Java 9, 10, 11. The GUI chapters are updated to JavaFX 11. The examples are revised. The user interfaces in the examples and exercises are now resizable and displayed in the center of the window. More examples and exercises in the data structures chapters use Lambda expressions to simplify coding. Both Comparable and Comparator are used to compare elements in Heap, Priority- Queue, BST, and AVLTree. This is consistent with the Java API and is more useful and flexible. String matching algorithms are introduced in Chapter 22. VideoNotes are updated. Provided additional exercises not printed in the book. These exercises are available for instructors only. Please visit www.pearsonhighered.com/liang for a complete list of new features as well as correlations to the previous edition. Pedagogical Features The book uses the following elements to help students get the most from the material: The Objectives at the beginning of each chapter list what students should learn from the chapter. This will help them determine whether they have met the objectives after ­completing the chapter. The Introduction opens the discussion with a thought-provoking question to motivate the reader to delve into the chapter. Key Points highlight the important concepts covered in each section. Check Points provide review questions to help students track their progress as they read through the chapter and evaluate their learning. A01_LIAN9966_12_SE_FM.indd 4 28/09/19 3:26 PM  Preface v Problems and Case Studies, carefully chosen and presented in an easy-to-follow style, teach problem solving and programming concepts. The book uses many small, simple, and stimulating examples to demonstrate important ideas. The Chapter Summary reviews the important subjects that students should understand and remember. It helps them reinforce the key concepts they have learned in the chapter. Quizzes are accessible online, grouped by sections, for students to do self-test on ­programming concepts and techniques. Programming Exercises are grouped by sections to provide students with opportunities to apply the new skills they have learned on their own. The level of difficulty is rated as easy (no asterisk), moderate (*), hard (**), or challenging (***). The trick of learning programming is practice, practice, and practice. To that end, the book provides a great many exercises. Additionally, more than 200 programming exercises with solutions are provided to the instructors on the Instructor Resource Website. These exercises are not printed in the text. Notes, Tips, Cautions, and Design Guides are inserted throughout the text to offer ­valuable advice and insight on important aspects of program development. Note Provides additional information on the subject and reinforces important concepts. Tip Teaches good programming style and practice. Caution Helps students steer away from the pitfalls of programming errors. Design Guide Provides guidelines for designing programs. Flexible Chapter Orderings The book is designed to provide flexible chapter orderings to enable GUI, exception ­handling, recursion, generics, and the Java Collections Framework to be covered earlier or later. The ­diagram on the next page shows the chapter dependencies. Organization of the Book The chapters can be grouped into five parts that, taken together, form a comprehensive intro- duction to Java programming, data structures and algorithms, and database and Web pro- gramming. Because knowledge is cumulative, the early chapters provide the conceptual basis for understanding programming and guide students through simple examples and exercises; subsequent chapters progressively present Java programming in detail, culminating with the development of comprehensive Java applications. The appendixes contain a mixed bag of topics, including an introduction to number systems, bitwise operations, regular expressions, and enumerated types. A01_LIAN9966_12_SE_FM.indd 5 28/09/19 3:26 PM  vi Preface A01_LIAN9966_12_SE_FM.indd 6 Part I: Fundamentals of Part II: Object-Oriented Part III: GUI Programming Part IV: Data Structures and Part V: Advanced Java Programming Programming Algorithms Ch 16 Programming Chapter 1 Introduction to Chapter 9 Objects and Classes Chapter 14 JavaFX Basics Ch 7 Chapter 18 Recursion Chapter 32 Multithreading and Computers, Programs, and Parallel Programming Java Chapter 10 Thinking in Objects Chapter 15 Event-Driven Ch 13 Chapter 19 Generics Programming and Chapter 33 Networking Chapter 2 Elementary Animations Chapter 11 Inheritance and Chapter 20 Lists, Stacks, Queues, Programming Polymorphism and Priority Queues Chapter 34 Java Database Chapter 16 JavaFX Controls Programming Chapter 3 Selections and Multimedia Chapter 12 Exception Chapter 21 Sets and Maps Handling and Text I/O Chapter 35 Advanced Java Chapter 4 Mathematical Chapter 31 Advanced JavaFX Database Programming Chapter 22 Developping Functions, Characters, Chapter 13 Abstract Classes and FXML Efficient Algorithms and Strings and Interfaces Chapter 36 Internationalization Chapter 23 Sorting Chapter 5 Loops Chapter 17 Binary I/O Chapter 37 Servlets Chapter 24 Implementing Lists, Chapter 6 Methods Stacks, Queues, and Priority Chapter 38 JavaServer Pages Queues Chapter 7 Single-Dimensional Chapter 39 JavaServer Faces Arrays Chapter 25 Binary Search Trees Chapter 40 RMI Note: Chapters 1–18 are in the Chapter 8 Multidimensional Chapter 26 AVL Trees brief version of this book. Arrays Chapter 41 Web Services Note: Chapters 1–30 are in the Chapter 27 Hashing comprehensive version. Note: Chapters 31–44 are bonus Chapter 28 Graphs and chapters available from the Applications Companion Website. Chapter 29 Weighted Graphs and Applications Chapter 30 Aggregate Operations and Collection Streams Chapter 42 2-4 Trees and B- Trees Chapter 43 Red-Black Trees Ch 9 Chapter 44 Testing Using JUnit 28/09/19 3:27 PM  Preface vii Part I: Fundamentals of Programming (Chapters 1–8) The first part of the book is a stepping stone, preparing you to embark on the journey of learning Java. You will begin to learn about Java (Chapter 1) and fundamental programming ­techniques with primitive data types, variables, constants, assignments, expressions, and operators (­Chapter 2), selection statements (Chapter 3), mathematical functions, characters, and strings (Chapter 4), loops (Chapter 5), methods (Chapter 6), and arrays (Chapters 7–8). After ­Chapter 7, you can jump to Chapter 18 to learn how to write recursive methods for solving inherently recursive problems. Part II: Object-Oriented Programming (Chapters 9–13, and 17) This part introduces object-oriented programming. Java is an object-oriented program- ming language that uses abstraction, encapsulation, inheritance, and polymorphism to pro- vide great flexibility, modularity, and reusability in developing software. You will learn programming with objects and classes (Chapters 9–10), class inheritance (Chapter 11), polymorphism (­Chapter 11), exception handling (Chapter 12), abstract classes (Chapter 13), and interfaces (Chapter 13). Text I/O is introduced in Chapter 12 and binary I/O is discussed in Chapter 17. Part III: GUI Programming (Chapters 14–16 and Bonus Chapter 31) JavaFX is a new framework for developing Java GUI programs. It is not only useful for developing GUI programs, but also an excellent pedagogical tool for learning object-oriented programming. This part introduces Java GUI programming using JavaFX in Chapters 14–16. Major topics include GUI basics (Chapter 14), container panes (Chapter 14), drawing shapes (Chapter 14), event-driven programming (Chapter 15), animations (Chapter 15), and GUI ­controls (Chapter 16), and playing audio and video (Chapter 16). You will learn the a­ rchitecture of JavaFX GUI programming and use the controls, shapes, panes, image, and video to develop useful applications. Chapter 31 covers advanced features in JavaFX. Part IV: Data Structures and Algorithms (Chapters 18–30 and Bonus Chapters 42–43) This part covers the main subjects in a typical data structures and algorithms course. Chapter 18 introduces recursion to write methods for solving inherently recursive problems. Chapter 19 presents how generics can improve software reliability. Chapters 20 and 21 introduce the Java Collection Framework, which defines a set of useful API for data structures. Chapter 22 discusses measur- ing algorithm efficiency in order to choose an appropriate algorithm for applications. Chapter 23 describes classic sorting algorithms. You will learn how to implement several classic data struc- tures lists, queues, and priority queues in Chapter 24. Chapters 25 and 26 introduce binary search trees and AVL trees. Chapter 27 presents hashing and implementing maps and sets using hashing. Chapters 28 and 29 introduce graph applications. Chapter 30 introduces aggregate operations for collection streams. The 2-4 trees, B-trees, and red-black trees are covered in Bonus Chapters 42–43. Part V: Advanced Java Programming (Chapters 32-41, 44) This part of the book is devoted to advanced Java programming. Chapter 32 treats the use of multithreading to make programs more responsive and interactive and introduces parallel pro- gramming. Chapter 33 discusses how to write programs that talk with each other from different hosts over the Internet. Chapter 34 introduces the use of Java to develop database projects. Chapter 35 delves into advanced Java database programming. Chapter 36 covers the use of internationalization support to develop projects for international audiences. Chapters 37 and 38 introduce how to use Java servlets and JavaServer Pages to generate dynamic content from Web servers. Chapter 39 introduces modern Web application development using JavaServer Faces. Chapter 40 introduces remote method invocation and Chapter 41 discusses Web ser- vices. Chapter 44 introduces testing Java programs using JUnit. A01_LIAN9966_12_SE_FM.indd 7 28/09/19 3:27 PM  viii Preface Appendixes This part of the book covers a mixed bag of topics. Appendix A lists Java keywords. ­Appendix B gives tables of ASCII characters and their associated codes in decimal and in hex. Appen- dix C shows the operator precedence. Appendix D summarizes Java modifiers and their usage. Appendix E discusses special floating-point values. Appendix F introduces number systems and conversions among binary, decimal, and hex numbers. Finally, Appendix G introduces bitwise operations. Appendix H introduces regular expressions. Appendix I covers enumerated types. Java Development Tools You can use a text editor, such as the Windows Notepad or WordPad, to create Java programs and to compile and run the programs from the command window. You can also use a Java development tool, such as NetBeans or Eclipse. These tools support an integrated develop- ment environment (IDE) for developing Java programs quickly. Editing, compiling, building, executing, and debugging programs are integrated in one graphical user interface. Using these tools effectively can greatly increase your programming productivity. NetBeans and Eclipse IDE tutorials are easy to use if you follow the tutorials. Tutorials on NetBeans and Eclipse can be found in the supplements on the Companion Website www.pearsonhighered.com/liang. Student Resource Website The Student Resource Website (www.pearsonhighered.com/liang) contains the following resources: Answers to CheckPoint questions Solutions to majority of even-numbered programming exercises Source code for the examples in the book Interactive quiz (organized by sections for each chapter) Supplements Debugging tips Video notes Algorithm animations Errata Supplements The text covers the essential subjects. The supplements extend the text to introduce additional topics that might be of interest to readers. The supplements are available from the Companion Website. Instructor Resource Website The Instructor Resource Website, accessible from www.pearsonhighered.com/liang, contains the following resources: Microsoft PowerPoint slides with interactive buttons to view full-color, syntax-highlighted source code and to run programs without leaving the slides. Solutions to majority of odd-numbered programming exercises. A01_LIAN9966_12_SE_FM.indd 8 28/09/19 3:27 PM  Preface ix More than 200 additional programming exercises and 300 quizzes organized by ­chapters. These exercises and quizzes are available only to the instructors. Solutions to these ­exercises and quizzes are provided. Web-based quiz generator. (Instructors can choose chapters to generate quizzes from a large database of more than two thousand questions.) Sample exams. Most exams have four parts: Multiple-choice questions or short-answer questions Correct programming errors Trace programs Write programs Sample exams with ABET course assessment. Projects. In general, each project gives a description and asks students to analyze, design, and implement the project. Some readers have requested the materials from the Instructor Resource Website. Please understand that these are for instructors only. Such requests will not be answered. Online Practice and Assessment with MyProgrammingLab MyProgrammingLab helps students fully grasp the logic, semantics, and syntax of programming. Through practice exercises and immediate, personalized feedback, MyPro- grammingLab improves the programming competence of beginning students who often struggle with the basic concepts and paradigms of popular high-level programming languages. A self-study and homework tool, a MyProgrammingLab course consists of hundreds of small practice problems organized around the structure of this textbook. For students, the system auto- matically detects errors in the logic and syntax of their code submissions and offers targeted hints that enable students to figure out what went wrong—and why. For instructors, a compre- hensive gradebook tracks correct and incorrect answers and stores the code inputted by students for review. MyProgrammingLab is offered to users of this book in partnership with Turing’s Craft, the makers of the CodeLab interactive programming exercise system. For a full demonstration, to see feedback from instructors and students, or to get started using MyProgrammingLab in your course, visit www.myprogramminglab.com. Video Notes We are excited about the new Video Notes feature that is found in this new edition. These VideoNote videos provide additional help by presenting examples of key topics and showing how to solve problems completely from design through coding. Video Notes are available from www.pearsonhighered.com/liang. Algorithm Animations We have provided numerous animations for algorithms. These are valuable pedagogical tools Animation to demonstrate how algorithms work. Algorithm animations can be accessed from the Com- panion Website. A01_LIAN9966_12_SE_FM.indd 9 28/09/19 3:27 PM  x Preface Acknowledgments I would like to thank Georgia Southern University for enabling me to teach what I write and for supporting me in writing what I teach. Teaching is the source of inspiration for continuing to improve the book. I am grateful to the instructors and students who have offered comments, suggestions, corrections, and praise. My special thanks go to Stefan Andrei of Lamar Univer- sity and William Bahn of University of Colorado Colorado Springs for their help to improve the data structures part of this book. This book has been greatly enhanced thanks to outstanding reviews for this and previous editions. The reviewers are: Elizabeth Adams (James Madison University), Syed Ahmed (North G ­ eorgia College and State University), Omar Aldawud (Illinois Institute of Technology), Stefan Andrei (Lamar University), Yang Ang (University of Wollongong, Australia), Kevin Bierre (Rochester Institute of Technology), Aaron Braskin (Mira Costa High School), David Champion (DeVry Insti- tute), James Chegwidden (Tarrant County College), Anup Dargar (University of North Dakota), Daryl Detrick (Warren Hills Regional High School), Charles Dierbach (Towson University), Frank Ducrest (University of Louisiana at Lafayette), Erica Eddy (University of Wisconsin at Parkside), Summer Ehresman (Center Grove High School), Deena Engel (New York University), Henry A. Etlinger (Rochester Institute of Technology), James Ten Eyck (Marist College), Myers Foreman (Lamar University), Olac Fuentes (University of Texas at El Paso), Edward F. Gehringer (North Carolina State University), Harold Grossman (Clemson University), Barbara Guillot (Louisiana State University), Stuart Hansen (University of Wisconsin, Parkside), Dan Harvey (Southern Ore- gon University), Ron Hofman (Red River College, Canada), Stephen Hughes (Roanoke College), Vladan Jovanovic (Georgia Southern University), Deborah Kabura Kariuki (Stony Point High School), Edwin Kay (Lehigh University), Larry King (University of Texas at Dallas), Nana Kofi (Langara College, Canada), George Koutsogiannakis (Illinois Institute of Technology), Roger Kraft (Purdue University at Calumet), Norman Krumpe (Miami University), Hong Lin (DeVry Institute), Dan Lipsa (Armstrong State University), James Madison (Rensselaer Polytechnic Institute), Frank Malinowski (Darton College), Tim Margush (University of Akron), Debbie Masada (Sun Microsys- tems), Blayne Mayfield (Oklahoma State University), John McGrath (J.P. McGrath Consulting), Hugh McGuire (Grand Valley State), Shyamal Mitra (University of Texas at Austin), Michel Mitri (James Madison University), Kenrick Mock (University of Alaska Anchorage), Frank Murgolo (California State University, Long Beach), Jun Ni (University of Iowa), Benjamin N ­ ystuen (Univer- sity of Colorado at Colorado Springs), Maureen Opkins (CA State University, Long Beach), Gavin Osborne (University of Saskatchewan), Kevin Parker (Idaho State University), Dale Parson (Kutz- town University), Mark Pendergast (Florida Gulf Coast University), Richard Povinelli (Marquette University), Roger Priebe (University of Texas at Austin), Mary Ann Pumphrey (De Anza Junior College), Pat Roth (Southern Polytechnic State University), Amr Sabry (Indiana University), Ben Setzer (Kennesaw State University), Carolyn Schauble (Colorado State University), David Scuse (University of Manitoba), Ashraf Shirani (San Jose State University), Daniel Spiegel (Kutztown University), Joslyn A. Smith (Florida Atlantic University), Lixin Tao (Pace University), Ronald F. Taylor (Wright State University), Russ Tront (Simon Fraser University), Deborah T ­ rytten (Univer- sity of Oklahoma), Michael Verdicchio (Citadel), Kent Vidrine (George Washington University), and Bahram Zartoshty (California State University at Northridge). It is a great pleasure, honor, and privilege to work with Pearson. I would like to thank Tracy Johnson and her colleagues Marcia Horton, Demetrius Hall, Yvonne Vannatta, Kristy Alaura, Carole Snyder, Scott Disanno, Bob Engelhardt, Shylaja Gattupalli, and their colleagues for organizing, producing, and promoting this project. As always, I am indebted to my wife, Samantha, for her love, support, and encouragement. A01_LIAN9966_12_SE_FM.indd 10 28/09/19 3:27 PM  BRIEF CONTENTS 1 Introduction to Computers, 30 Aggregate Operations for Programs, and Java™ 1 Collection Streams 1129 2 Elementary Programming 33 3 Selections 77 CHAPTER 31–44 are available from the 4 Mathematical Functions, Companion Website at www.pearsonhighered Characters, and Strings 121.com/liang 5 Loops 159 31 Advanced JavaFX and FXML 6 Methods 205 32 Multithreading and Parallel 7 Single-Dimensional Arrays 249 ­Programming 8 Multidimensional Arrays 289 33 Networking 9 Objects and Classes 323 34 Java Database Programming 10 Object-Oriented Thinking 367 35 Advanced Java Database Programming 11 Inheritance and Polymorphism 411 36 Internationalization 12 Exception Handling 37 Servlets and Text I/O 453 38 JavaServer Pages 13 Abstract Classes and Interfaces 499 39 JavaServer Faces 14 JavaFX Basics 541 40 RMI 15 Event-Driven Programming and 41 Web Services Animations 593 42 2-4 Trees and B-Trees 16 JavaFX UI Controls and 43 Red-Black Trees Multimedia 643 44 Testing Using JUnit 17 Binary I/O 691 18 Recursion 719 Appendixes 1161 19 Generics 751 A Java Keywords and Reserved Words 1163 20 Lists, Stacks, Queues, and Priority B The ASCII Character Set 1164 Queues 775 C Operator Precedence Chart 1166 21 Sets and Maps 815 D Java Modifiers 1168 22 Developing Efficient Algorithms 839 E Special Floating-Point Values 1170 23 Sorting 887 F Number Systems 1171 24 Implementing Lists, Stacks, Queues, and Priority Queues 923 G Bitwise Operations 1175 25 Binary Search Trees 959 H Regular Expressions 1176 26 AVL Trees 995 I Enumerated Types 1182 27 Hashing 1015 J The Big-O, Big-Omega,    and Big-Theta Notations 1187 28 Graphs and Applications 1045 29 Weighted Graphs and Quick Reference 1189 Applications 1091 Index 1191 xi A01_LIAN9966_12_SE_FM.indd 11 28/09/19 3:27 PM  CONTENTS Chapter 1 I ntroduction to Computers, ­Programs, and Java™ 1 1.1 Introduction 2 1.2 What Is a Computer? 2 1.3 Programming Languages 7 1.4 Operating Systems 9 1.5 Java, the World Wide Web, and Beyond 10 1.6 The Java Language Specification, API, JDK, JRE, and IDE 11 1.7 A Simple Java Program 12 1.8 Creating, Compiling, and Executing a Java Program 15 1.9 Programming Style and Documentation 18 1.10 Programming Errors 19 1.11 Developing Java Programs Using NetBeans 23 1.12 Developing Java Programs Using Eclipse 26 Chapter 2 Elementary Programming 33 2.1 Introduction 34 2.2 Writing a Simple Program 34 2.3 Reading Input from the Console 37 2.4 Identifiers 40 2.5 Variables 40 2.6 Assignment Statements and Assignment Expressions 42 2.7 Named Constants 43 2.8 Naming Conventions 44 2.9 Numeric Data Types and Operations 45 2.10 Numeric Literals 48 2.11 JShell 50 2.12 Evaluating Expressions and Operator Precedence 52 2.13 Case Study: Displaying the Current Time 54 2.14 Augmented Assignment Operators 56 2.15 Increment and Decrement Operators 57 2.16 Numeric Type Conversions 58 2.17 Software Development Process 61 2.18 Case Study: Counting Monetary Units 64 2.19 Common Errors and Pitfalls 67 Chapter 3 Selections 77 3.1 Introduction 78 3.2 boolean Data Type, Values, and Expressions 78 3.3 if Statements 80 3.4 Two-Way if-else Statements 82 3.5 Nested if and Multi-Way if-else Statements 83 3.6 Common Errors and Pitfalls 85 3.7 Generating Random Numbers 89 3.8 Case Study: Computing Body Mass Index 91 3.9 Case Study: Computing Taxes 92 3.10 Logical Operators 95 3.11 Case Study: Determining Leap Year 99 3.12 Case Study: Lottery 100 xii A01_LIAN9966_12_SE_FM.indd 12 28/09/19 3:27 PM  Contents xiii 3.13 switch Statements 102 3.14 Conditional Operators 105 3.15 Operator Precedence and Associativity 106 3.16 Debugging 108 Chapter 4 M  athematical Functions, Characters, and Strings 121 4.1 Introduction 122 4.2 Common Mathematical Functions 122 4.3 Character Data Type and Operations 126 4.4 The String Type 131 4.5 Case Studies 140 4.6 Formatting Console Output 146 Chapter 5 Loops 159 5.1 Introduction 160 5.2 The while Loop 160 5.3 Case Study: Guessing Numbers 163 5.4 Loop Design Strategies 166 5.5 Controlling a Loop with User Confirmation or a Sentinel Value 168 5.6 The do-while Loop 171 5.7 The for Loop 173 5.8 Which Loop to Use? 176 5.9 Nested Loops 178 5.10 Minimizing Numeric Errors 180 5.11 Case Studies 182 5.12 Keywords break and continue 186 5.13 Case Study: Checking Palindromes 189 5.14 Case Study: Displaying Prime Numbers 191 Chapter 6 Methods 205 6.1 Introduction 206 6.2 Defining a Method 206 6.3 Calling a Method 208 6.4 void vs. Value-Returning Methods 211 6.5 Passing Arguments by Values 213 6.6 Modularizing Code 217 6.7 Case Study: Converting Hexadecimals to Decimals 219 6.8 Overloading Methods 221 6.9 The Scope of Variables 224 6.10 Case Study: Generating Random Characters 225 6.11 Method Abstraction and Stepwise Refinement 227 Chapter 7 Single-Dimensional Arrays 249 7.1 Introduction 250 7.2 Array Basics 250 7.3 Case Study: Analyzing Numbers 257 7.4 Case Study: Deck of Cards 258 7.5 Copying Arrays 260 7.6 Passing Arrays to Methods 261 7.7 Returning an Array from a Method 264 7.8 Case Study: Counting the Occurrences of Each Letter 265 7.9 Variable-Length Argument Lists 268 7.10  Searching Arrays 269 A01_LIAN9966_12_SE_FM.indd 13 28/09/19 3:27 PM  xiv Contents 7.11 Sorting Arrays 273 7.12 The Arrays Class 274 7.13 Command-Line Arguments 276 Chapter 8 Multidimensional Arrays 289 8.1 Introduction 290 8.2 Two-Dimensional Array Basics 290 8.3 Processing Two-Dimensional Arrays 293 8.4 Passing Two-Dimensional Arrays to Methods 295 8.5 Case Study: Grading a Multiple-Choice Test 296 8.6 Case Study: Finding the Closest Pair 298 8.7 Case Study: Sudoku 300 8.8 Multidimensional Arrays 303 Chapter 9 Objects and Classes 323 9.1 Introduction 324 9.2 Defining Classes for Objects 324 9.3 Example: Defining Classes and Creating Objects 326 9.4 Constructing Objects Using Constructors 331 9.5 Accessing Objects via Reference Variables 332 9.6 Using Classes from the Java Library 336 9.7 Static Variables, Constants, and Methods 339 9.8 Visibility Modifiers 344 9.9 Data Field Encapsulation 346 9.10 Passing Objects to Methods 349 9.11 Array of Objects 353 9.12 Immutable Objects and Classes 355 9.13 The Scope of Variables 357 9.14 The this Reference 358 Chapter 10 Object-Oriented Thinking 367 10.1 Introduction 368 10.2 Class Abstraction and Encapsulation 368 10.3 Thinking in Objects 372 10.4 Class Relationships 375 10.5 Case Study: Designing the Course Class 378 10.6 Case Study: Designing a Class for Stacks 380 10.7 Processing Primitive Data Type Values as Objects 382 10.8 Automatic Conversion between Primitive Types and Wrapper Class Types 386 10.9 The BigInteger and BigDecimal Classes 387 10.10 The String Class 388 10.11 The StringBuilder and StringBuffer Classes 395 Chapter 11 Inheritance and Polymorphism 411 11.1 Introduction 412 11.2 Superclasses and Subclasses 412 11.3 Using the super Keyword 418 11.4 Overriding Methods 421 11.5 Overriding vs. Overloading 422 11.6 The Object Class and Its toString() Method 424 11.7 Polymorphism 425 11.8 Dynamic Binding 425 11.9 Casting Objects and the instanceof Operator 429 A01_LIAN9966_12_SE_FM.indd 14 28/09/19 3:27 PM  Contents xv 11.10 The Object’s equals Method 433 11.11 The ArrayList Class 434 11.12 Useful Methods for Lists 440 11.13 Case Study: A Custom Stack Class 441 11.14 The protected Data and Methods 442 11.15 Preventing Extending and Overriding 445 Chapter 12 Exception Handling and Text I/O 453 12.1 Introduction 454 12.2 Exception-Handling Overview 454 12.3 Exception Types 459 12.4 Declaring, Throwing, and Catching Exceptions 462 12.5 The finally Clause 470 12.6 When to Use Exceptions 472 12.7 Rethrowing Exceptions 472 12.8 Chained Exceptions 473 12.9 Defining Custom Exception Classes 474 12.10 The File Class 477 12.11 File Input and Output 480 12.12 Reading Data from the Web 487 12.13 Case Study: Web Crawler 488 Chapter 13 Abstract Classes and Interfaces 499 13.1 Introduction 500 13.2 Abstract Classes 500 13.3 Case Study: The Abstract Number Class 505 13.4 Case Study: Calendar and GregorianCalendar 507 13.5 Interfaces 510 13.6 The Comparable Interface 514 13.7 The Cloneable Interface 518 13.8 Interfaces vs. Abstract Classes 523 13.9 Case Study: The Rational Class 526 13.10 Class-Design Guidelines 531 Chapter 14 JavaFX Basics 541 14.1 Introduction 542 14.2 JavaFX vs Swing and AWT 542 14.3 The Basic Structure of a JavaFX Program 542 14.4 Panes, Groups, UI Controls, and Shapes 545 14.5 Property Binding 548 14.6 Common Properties and Methods for Nodes 551 14.7 The Color Class 553 14.8 The Font Class 554 14.9 The Image and ImageView Classes 556 14.10 Layout Panes and Groups 558 14.11 Shapes 567 14.12 Case Study: The ClockPane Class 580 Chapter 15 Event-Driven Programming and Animations 593 15.1 Introduction 594 15.2 Events and Event Sources 596 15.3 Registering Handlers and Handling Events 597 15.4 Inner Classes 601 A01_LIAN9966_12_SE_FM.indd 15 28/09/19 3:27 PM  xvi Contents 15.5 Anonymous Inner Class Handlers 602 15.6 Simplifying Event Handling Using Lambda Expressions 605 15.7 Case Study: Loan Calculator 609 15.8 Mouse Events 611 15.9 Key Events 613 15.10 Listeners for Observable Objects 616 15.11 Animation 618 15.12 Case Study: Bouncing Ball 626 15.13 Case Study: US Map 630 Chapter 16 JavaFX UI Controls and Multimedia 643 16.1 Introduction 644 16.2 Labeled and Label 644 16.3 Button 646 16.4 CheckBox 648 16.5 RadioButton 651 16.6 TextField 654 16.7 TextArea 655 16.8 ComboBox 659 16.9 ListView 662 16.10 ScrollBar 665 16.11 Slider 668 16.12 Case Study: Developing a Tic-Tac-Toe Game 671 16.13 Video and Audio 676 16.14 Case Study: National Flags and Anthems 679 Chapter 17 Binary I/O 691 17.1 Introduction 692 17.2 How Is Text I/O Handled in Java? 692 17.3 Text I/O vs. Binary I/O 693 17.4 Binary I/O Classes 694 17.5 Case Study: Copying Files 704 17.6 Object I/O 706 17.7 Random-Access Files 711 Chapter 18 Recursion 719 18.1 Introduction 720 18.2 Case Study: Computing Factorials 720 18.3 Case Study: Computing Fibonacci Numbers 723 18.4 Problem Solving Using Recursion 726 18.5 Recursive Helper Methods 728 18.6 Case Study: Finding the Directory Size 731 18.7 Case Study: Tower of Hanoi 733 18.8 Case Study: Fractals 736 18.9 Recursion vs. Iteration 740 18.10 Tail Recursion 740 Chapter 19 Generics 751 19.1 Introduction 752 19.2 Motivations and Benefits 752 19.3 Defining Generic Classes and Interfaces 754 19.4 Generic Methods 756 19.5 Case Study: Sorting an Array of Objects 758 A01_LIAN9966_12_SE_FM.indd 16 28/09/19 3:27 PM  Contents xvii 19.6 Raw Types and Backward Compatibility 760 19.7 Wildcard Generic Types 761 19.8 Erasure and Restrictions on Generics 764 19.9 Case Study: Generic Matrix Class 766 Chapter 20 L  ists, Stacks, Queues, and Priority Queues 775 20.1 Introduction 776 20.2 Collections 776 20.3 Iterators 780 20.4 Using the forEach Method 782 20.5 Lists 783 20.6 The Comparator Interface 787 20.7 Static Methods for Lists and Collections 792 20.8 Case Study: Bouncing Balls 795 20.9 Vector and Stack Classes 798 20.10 Queues and Priority Queues 800 20.11 Case Study: Evaluating Expressions 803 Chapter 21 Sets and Maps 815 21.1 Introduction 816 21.2 Sets 816 21.3 Comparing the Performance of Sets and Lists 824 21.4 Case Study: Counting Keywords 827 21.5 Maps 828 21.6 Case Study: Occurrences of Words 833 21.7 Singleton and Unmodifiable Collections and Maps 835 Chapter 22 Developing Efficient Algorithms 839 22.1 Introduction 840 22.2 Measuring Algorithm Efficiency Using Big O Notation 840 22.3 Examples: Determining Big O 842 22.4 Analyzing Algorithm Time Complexity 846 22.5 Finding Fibonacci Numbers Using Dynamic Programming 849 22.6 Finding Greatest Common Divisors Using Euclid’s Algorithm 851 22.7 Efficient Algorithms for Finding Prime Numbers 855 22.8 Finding the Closest Pair of Points Using Divide-and-Conquer 861 22.9 Solving the Eight Queens Problem Using Backtracking 864 22.10 Computational Geometry: Finding a Convex Hull 867 22.11 String Matching 869 Chapter 23 Sorting 887 23.1 Introduction 888 23.2 Insertion Sort 888 23.3 Bubble Sort 890 23.4 Merge Sort 892 23.5 Quick Sort 896 23.6 Heap Sort 900 23.7 Bucket and Radix Sorts 907 23.8 External Sort 909 A01_LIAN9966_12_SE_FM.indd 17 28/09/19 3:27 PM  xviii Contents Chapter 24 I mplementing Lists, Stacks, Queues, and Priority Queues 923 24.1 Introduction 924 24.2 Common Operations for Lists 924 24.3 Array Lists 928 24.4 Linked Lists 935 24.5 Stacks and Queues 949 24.6 Priority Queues 953 Chapter 25 Binary Search Trees 959 25.1 Introduction 960 25.2 Binary Search Trees Basics 960 25.3 Representing Binary Search Trees 961 25.4 Searching for an Element 962 25.5 Inserting an Element into a BST 962 25.6 Tree Traversal 963 25.7 The BST Class 965 25.8 Deleting Elements from a BST 974 25.9 Tree Visualization and MVC 980 25.10 Iterators 983 25.11 Case Study: Data Compression 985 Chapter 26 AVL Trees 995 26.1 Introduction 996 26.2 Rebalancing Trees 996 26.3 Designing Classes for AVL Trees 999 26.4 Overriding the insert Method 1000 26.5 Implementing Rotations 1001 26.6 Implementing the delete Method 1002 26.7 The AVLTree Class 1002 26.8 Testing the AVLTree Class 1008 26.9 AVL Tree Time Complexity Analysis 1011 Chapter 27 Hashing 1015 27.1 Introduction 1016 27.2 What Is Hashing? 1016 27.3 Hash Functions and Hash Codes 1017 27.4 Handling Collisions Using Open Addressing 1019 27.5 Handling Collisions Using Separate Chaining 1023 27.6 Load Factor and Rehashing 1025 27.7 Implementing a Map Using Hashing 1025 27.8 Implementing Set Using Hashing 1034 Chapter 28 Graphs and Applications 1045 28.1 Introduction 1046 28.2 Basic Graph Terminologies 1047 28.3 Representing Graphs 1048 28.4 Modeling Graphs 1054 28.5 Graph Visualization 1064 28.6 Graph Traversals 1067 A01_LIAN9966_12_SE_FM.indd 18 28/09/19 3:27 PM  Contents xix 28.7 Depth-First Search (DFS) 1068 28.8 Case Study: The Connected Circles Problem 1072 28.9 Breadth-First Search (BFS) 1074 28.10 Case Study: The Nine Tails Problem 1077 Chapter 29 W  eighted Graphs and Applications 1091 29.1 Introduction 1092 29.2 Representing Weighted Graphs 1093 29.3 The WeightedGraph Class 1095 29.4 Minimum Spanning Trees 1103 29.5 Finding Shortest Paths 1109 29.6 Case Study: The Weighted Nine Tails Problem 1118 Chapter 30  Aggregate Operations for Collection Streams 1129 30.1 Introduction 1130 30.2 Stream Pipelines 1130 30.3 IntStream, LongStream, and DoubleStream 1136 30.4 Parallel Streams 1139 30.5 Stream Reduction Using the reduce Method 1141 30.6 Stream Reduction Using the collect Method 1144 30.7 Grouping Elements Using the groupingby Collector 1147 30.8 Case Studies 1150 Chapter 31–44 are available from the Companion Website at www.pearsonhighered.com/liang Chapter 31 Advanced JavaFX and FXML Chapter 32 Multithreading and Parallel Programming Chapter 33 Networking Chapter 34 Java Database Programming Chapter 35 Advanced Database Programming Chapter 36 Internationalization Chapter 37 Servlets Chapter 38 JavaServer Pages Chapter 39 JavaServer Faces Chapter 40 RMI Chapter 41 Web Services A01_LIAN9966_12_SE_FM.indd 19 28/09/19 3:27 PM  xx Contents Chapter 42 2-4 Trees and B-Trees Chapter 43 Red-Black Trees Chapter 44 Testing Using JUnit Appendixes 1161 Appendix A Java Keywords and Reserved Words 1163 Appendix B The ASCII Character Set 1164 Appendix C Operator Precedence Chart 1166 Appendix D Java Modifiers 1168 Appendix E Special Floating-Point Values 1170 Appendix F Number Systems 1171 Appendix G Bitwise Operations 1175 Appendix H Regular Expressions 1176 Appendix I Enumerated Types 1182 Appendix J The Big-O, Big-Omega, and Big-Theta Notations 1187 Quick Reference 1189 Index 1191 A01_LIAN9966_12_SE_FM.indd 20 28/09/19 3:27 PM  VideoNotes Locations of VideoNotes VideoNote http://www.pearsonhighered.com/liang Chapter 1 Introduction to Computers, Programs, Coupon collector’s problem 284 and Java™ 1 Consecutive four 286 Your first Java program 12 Compile and Run a Java Program 17 Chapter 8 Multidimensional Arrays 289 NetBeans brief tutorial 23 Find the row with the largest sum 294 Eclipse brief tutorial 26 Grade multiple-choice test 296 Sudoku 300 Chapter 2 Elementary Programming 33 Multiply two matrices 309 Obtain Input 37 Even number of 1s 316 Use operators / and % 54 Software development Chapter 9 Objects and Classes 323 process 61 Define classes and create objects 324 Compute loan payments 62 Static vs. instance 339 Compute BMI 73 Data field encapsulation 346 Immutable objects and this keyword 355 Chapter 3 Selections 77 The this keyword 358 Program addition quiz 79 The Fan class 364 Program subtraction quiz 89 Use multi-way if-else Chapter 10 Object-Oriented Thinking 367 statements 92 the Loan class 369 Sort three integers 112 The BMI class 372 Check point location 114 The StackOfIntegers class 380 Process large numbers 387 Chapter 4 Mathematical Functions, Characters, The String class 388 and Strings 121 The MyPoint class 403 Introduce Math functions 122 Introduce strings and objects 131 Chapter 11 Inheritance and Polymorphism 411 Convert hex to decimal 143 Geometric class hierarchy 412 Compute great circle distance 152 Polymorphism and dynamic Convert hex to binary 154 binding demo 426 Chapter 5 Loops 159 New Account class 448 Use while loop 160 Guess a number 163 Chapter 12 Exception Handling and Text I/O 453 Multiple subtraction quiz 166 Exception-handling advantages 454 Use do-while loop 171 Create custom exception classes 474 Minimize numeric errors 180 Write and read data 480 Display loan schedule 197 HexFormatException 493 Sum a series 198 Chapter 13 Abstract Classes and Interfaces 499 Chapter 6 Methods 205 Abstract GeometricObject class 500 Define/invoke max method 208 Calendar and GregorianCalendar Use void method 211 classes 507 Modularize code 217 The concept of interface 510 Stepwise refinement 227 Reverse an integer 236 Chapter 14 JavaFX Basics 541 Estimate p 240 Getting started with JavaFX 542 Understand property binding 548 Chapter 7 Single-Dimensional Arrays 249 Use Image and ImageView 556 Random shuffling 254 Use layout panes 558 Deck of cards 258 Use shapes 567 Selection sort 273 Display a tic-tac-toe board 586 Command-line arguments 277 Display a bar chart 588 xxi A01_LIAN9966_12_SE_FM.indd 21 28/09/19 3:27 PM  xxii VideoNotes Chapter 15 Event-Driven Programming Use Media, MediaPlayer, and Animations 593 and MediaView 676 Handler and its registration 600 Use radio buttons and text fields 683 Anonymous handler 603 Set fonts 685 Move message using the mouse 612 Chapter 17 Binary I/O 691 Animate a rising flag 618 Copy file 704 Flashing text 624 Object I/O 706 Simple calculator 634 Split a large file 716 Check mouse-point location 636 Display a running fan 639 Chapter 18 Recursion 719 Binary search 730 Chapter 16 JavaFX UI Controls and Multimedia 643 Directory size 731 Use ListView 662 Search a string in a directory 747 Use Slider 668 Recursive tree 750 Tic-Tac-Toe 671 Animations Chapter 7 Single-Dimensional Arrays 249 Chapter 24 Implementing Lists, Stacks, linear search animation on Queues, and Priority Queues 923 Companion Website 270 list animation on Companion binary search animation on Website 924 Companion Website 270 stack and queue animation on selection sort animation on Companion Website 950 Companion Website 273 Chapter 25 Binary Search Trees 959 Chapter 8 Multidimensional Arrays 289 BST animation on Companion closest-pair animation on Website 960 the Companion Website 298 Chapter 26 AVL Trees 995 Chapter 22 Developing Efficient Algorithms 839 AVL tree animation on binary search animation on Companion Website 996 the Companion Website 846 selection sort animation on Chapter 27 Hashing 1015 the Companion Website 846 linear probing animation on closest-pair animation on Compa