Think Java - How to think like a computer scientist (Allen B. Downey, Chris Mayfield) (Z-Library)

📄 File Format: PDF

💾 File Size: 18.3 MB

📖 Read Online ⬇️ Download

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

📄 Page 1

(This page has no text content)

📄 Page 2

Think Java SECOND EDITION How to Think Like a Computer Scientist Allen B. Downey and Chris Mayfield

📄 Page 3

Think Java by Allen B. Downey and Chris Mayfield Copyright © 2020 Allen B. Downey and Chris Mayfield. All rights reserved. Printed in the United States of America. Published by O’Reilly Media, Inc., 1005 Gravenstein Highway North, Sebastopol, CA 95472. O’Reilly books may be purchased for educational, business, or sales promotional use. Online editions are also available for most titles (http://oreilly.com). For more information, contact our corporate/institutional sales department: 800-998-9938 or corporate@oreilly.com. Acquisitions Editor: Suzanne McQuade Development Editor: Corbin Collins Production Editor: Christopher Faucher Copyeditor: Sharon Wilkey Proofreader: Christina Edwards Indexers: Allen Downey and Chris Mayfield Interior Designer: David Futato Cover Designer: Karen Montgomery Illustrator: Rebecca Demarest May 2016: First Edition December 2019: Second Edition

📄 Page 4

Revision History for the Second Edition 2019-11-27: First Release See http://oreilly.com/catalog/errata.csp?isbn=9781492072508 for release details. The O’Reilly logo is a registered trademark of O’Reilly Media, Inc. Think Java, the cover image, and related trade dress are trademarks of O’Reilly Media, Inc. The views expressed in this work are those of the authors, and do not represent the publisher’s views. While the publisher and the authors have used good faith efforts to ensure that the information and instructions contained in this work are accurate, the publisher and the authors disclaim all responsibility for errors or omissions, including without limitation responsibility for damages resulting from the use of or reliance on this work. Use of the information and instructions contained in this work is at your own risk. If any code samples or other technology this work contains or describes is subject to open source licenses or the intellectual property rights of others, it is your responsibility to ensure that your use thereof complies with such licenses and/or rights. Think Java is available under the Creative Commons Attribution- NonCommercial-ShareAlike 4.0 International License. The authors maintain an online version at https://greenteapress.com/wp/think-java-2e. 978-1-492-07250-8 [LSI]

📄 Page 5

Preface Think Java is an introduction to computer science and programming intended for readers with little or no experience. We start with the most basic concepts and are careful to define all terms when they are first used. The book presents each new idea in a logical progression. Larger topics, like control flow statements and object-oriented programming, are divided into smaller examples and introduced over the course of several chapters. This book is intentionally concise. Each chapter is 10–12 pages and covers the material for one week of a college course. It is not meant to be a comprehensive presentation of Java, but rather, an initial exposure to programming constructs and techniques. We begin with small problems and basic algorithms and work up to object-oriented design. In the vocabulary of computer science pedagogy, this book uses the objects late approach. The Philosophy Behind the Book Here are the guiding principles that make the book the way it is: One concept at a time We break down topics that give beginners trouble into a series of small steps, so that they can exercise each new concept in isolation before continuing. Balance of Java and concepts The book is not primarily about Java; it uses code examples to demonstrate computer science. Most chapters start with language features and end with concepts. Conciseness

📄 Page 6

An important goal of the book is to be small enough so that students can read and understand the entire text in a one-semester college or AP course. Emphasis on vocabulary We try to introduce the minimum number of terms and define them carefully when they are first used. We also organize them in glossaries at the end of each chapter. Program development There are many strategies for writing programs, including bottom-up, top-down, and others. We demonstrate multiple program development techniques, allowing readers to choose methods that work best for them. Multiple learning curves To write a program, you have to understand the algorithm, know the programming language, and be able to debug errors. We discuss these and other aspects throughout the book, and summarize our advice in Appendix D. Object-Oriented Programming Some Java books introduce classes and objects immediately; others begin with procedural programming and transition to object-oriented more gradually. Many of Java’s object-oriented features are motivated by problems with previous languages, and their implementations are influenced by this history. Some of these features are hard to explain when people aren’t familiar with the problems they solve. We get to object-oriented programming as quickly as possible (beginning with Chapter 9). But we introduce concepts one at a time, as clearly as possible, in a way that allows readers to practice each idea in isolation before moving on. So it takes some time to get there.

📄 Page 7

You can’t write Java programs (even Hello World) without encountering object-oriented features. In some cases we explain a feature briefly when it first appears, and then explain it more deeply later on. If you read the entire book, you will see nearly every topic required for Java SE Programmer I certification. Supplemental lessons are available in the official Java tutorials on http://thinkjava.org/tutorial. This book is also well suited to prepare high school students for the AP Computer Science A exam, which includes object-oriented design and implementation. (AP is a registered trademark of The College Board.) A mapping of Think Java section numbers to the AP course is available on https://thinkjava.org. Changes to the Second Edition This new edition was written over several years, with feedback from dozens of instructors and hundreds of students. A complete history of all changes is available on GitHub. Here are some of the highlights: Chapters 2–4 We reordered the material in Chapter 1 to present a more interesting balance of theory and practice. Chapters 2 and 3 are much cleaner now too. Methods are now presented in a single chapter, along with additional in-depth examples. Chapters 5–8 We rearranged these chapters a lot, added many examples and new figures, and removed unnecessary details. Strings are covered earlier (before arrays) so that readers can apply them to loop problems. The material on recursion is now a chapter, and we added new sections to explain binary numbers and CodingBat. Chapters 9–12

📄 Page 8

Our main goal for these chapters was to provide better explanations and more diagrams. Chapters 9 and 10 focus more on immutable versus mutable objects, and we added new sections on BigInteger and StringBuilder. The other content is largely the same, but it should be easier to understand now. Chapters 13–17 We balanced the amount of content in Chapters 13–14 by moving ArrayLists earlier, and we implement the War card game as another example. Chapters 15–17 are brand-new in this edition; they cover more advanced topics including 2D arrays, graphics, exceptions, abstract classes, interfaces, and events. Appendixes We added Appendix B to explain documentation comments and Javadoc in more detail. The other three appendixes that were present in the first edition have been revised for clarity and layout. About the Appendixes The chapters of this book are meant to be read in order, because each one builds on the previous one. We also include several appendixes with material that can be read at any time: Appendix A, “Tools” This appendix explains how to download and install Java so you can compile programs on your computer. It also provides a brief introduction to DrJava—an integrated development environment (IDE) that is designed primarily for students—and other development tools, including Checkstyle for code quality and JUnit for testing. Appendix B, “Javadoc” It’s important to document your classes and methods so that other programmers (including yourself in the future) will know how to use

📄 Page 9

them. This appendix explains how to read documentation, how to write documentation, and how to use the Javadoc tool. Appendix C, “Graphics” Java provides libraries for working with graphics and animation, and these topics can be engaging for students. The libraries require object- oriented features that students will not completely understand until after Chapter 10, but they can be used much earlier. Appendix D, “Debugging” We provide debugging suggestions throughout the book, but this appendix provides many more suggestions on how to debug your programs. We recommend that you review this appendix frequently as you work through the book. Using the Code Examples Most of the code examples in this book are available from https://github.com/ChrisMayfield/ThinkJavaCode2. Git is a “version control system” that allows you to keep track of the files that make up a project. A collection of files under Git’s control is called a repository. GitHub is a hosting service that provides storage for Git repositories and a convenient web interface. It provides several ways to work with the code: You can create a copy of the repository on GitHub by clicking the Fork button. If you don’t already have a GitHub account, you’ll need to create one. After forking, you’ll have your own repository on GitHub that you can use to keep track of code you write. Then you can clone the repository, which downloads a copy of the files to your computer. Alternatively, you could clone the original repository without forking. If you choose this option, you don’t need a GitHub account, but you won’t be able to save your changes on GitHub.

📄 Page 10

If you don’t want to use Git at all, you can download the code in a ZIP archive using the Download ZIP button on the GitHub page, or this link: https://thinkjava.org/code2zip. After you clone the repository or unzip the ZIP file, you should have a directory named ThinkJavaCode2 with a subdirectory for each chapter in the book. The examples in this book were developed and tested using OpenJDK 11. If you are using a more recent version, everything should still work. If you are using an older version, some of the examples might not. If example code is offered with this book, you may use it in your programs and documentation. You do not need to contact us for permission unless you’re reproducing a significant portion of the code. For example, writing a program that uses several chunks of code from this book does not require permission. Selling or distributing examples from O’Reilly books does require permission. Answering a question by citing this book and quoting example code does not require permission. Incorporating a significant amount of example code from this book into your product’s documentation does require permission. We appreciate, but generally do not require, attribution. An attribution usually includes the title, author, publisher, and ISBN. For example: “Think Java by Allen B. Downey and Chris Mayfield. (O’Reilly). Copyright 2020 Allen B. Downey and Chris Mayfield, 978-1-492-07250-8.” If you feel your use of code examples falls outside fair use or the permission given above, feel free to contact us at permissions@oreilly.com. Conventions Used in This Book The following typographical conventions are used in this book: Italic Indicates new terms, URLs, email addresses, filenames, and file extensions.

📄 Page 11

Bold Indicates vocabulary words defined at the end of each chapter. Constant width Used for program listings, as well as within paragraphs to refer to program elements such as variable or function names, databases, data types, environment variables, statements, and keywords. Constant width bold Shows commands or other text that should be typed literally by the user. O’Reilly Online Learning For more than 40 years, O’Reilly Media has provided technology and business training, knowledge, and insight to help companies succeed. Our unique network of experts and innovators share their knowledge and expertise through books, articles, conferences, and our online learning platform. O’Reilly’s online learning platform gives you on-demand access to live training courses, in-depth learning paths, interactive coding environments, and a vast collection of text and video from O’Reilly and 200+ other publishers. For more information, please visit http://oreilly.com. How to Contact Us Please address comments and questions concerning this book to the publisher: O’Reilly Media, Inc. 1005 Gravenstein Highway North

📄 Page 12

Sebastopol, CA 95472 800-998-9938 (in the United States or Canada) 707-829-0515 (international or local) 707-829-0104 (fax) We have a web page for this book, where we list errata, examples, and any additional information. You can access this page at https://oreil.ly/think- java-2e. Email bookquestions@oreilly.com to comment or ask technical questions about this book. For more information about our books, courses, conferences, and news, see our website at http://www.oreilly.com. Find us on Facebook: http://facebook.com/oreilly Follow us on Twitter: http://twitter.com/oreillymedia Watch us on YouTube: http://www.youtube.com/oreillymedia Acknowledgments Many people have sent corrections and suggestions over the years, and we appreciate their valuable feedback! This list begins with version 4.0 of the open source edition, so it omits those who contributed to earlier versions: Ellen Hildreth used this book to teach data structures at Wellesley College and submitted a whole stack of corrections and suggestions. Tania Passfield pointed out that some glossaries had leftover terms that no longer appeared in the text.

📄 Page 13

Elizabeth Wiethoff noticed that the series expansion of exp(-x2) was wrong. She has also worked on a Ruby version of the book. Matt Crawford sent in a whole patch file full of corrections. Chi-Yu Li pointed out a typo and an error in one of the code examples. Doan Thanh Nam corrected an example. Muhammad Saied translated the book into Arabic and found several errors in the process. Marius Margowski found an inconsistency in a code example. Leslie Klein discovered another error in the series expansion of exp(-x2), identified typos in the card array figures, and helped clarify several exercises. Micah Lindstrom reported half a dozen typos and sent corrections. James Riely ported the textbook source from LaTeX to http://fpl.cs.depaul.edu/jriely/thinkapjava. Peter Knaggs ported the book to https://www.rigwit.co.uk/think/sharp. Heidi Gentry-Kolen recorded several https://www.youtube.com/user/digipipeline that follow the book. Waldo Ribeiro submitted a pull request that corrected a dozen typos. Michael Stewart made suggestions for improving the first half of the book. Steven Richardson adapted the book for an online course and contributed many ideas for improving the text. Fazl Rahman provided detailed feedback, chapter by chapter, and offered many suggestions for improving the text.

📄 Page 14

We are especially grateful to the technical reviewers of the O’Reilly Media first edition: Blythe Samuels, David Wisneski, and Stephen Rose. They found errors, made many great suggestions, and helped make the book much better. Likewise, we thank Marc Loy for his thorough review of the O’Reilly Media second edition. He contributed many corrections, insights, and clarifications. Many students have given exceptional feedback, including Ian Staton, Tanner Wernecke, Jacob Green, Rasha Abuhantash, Nick Duncan, Kylie Davidson, Shirley Jiang, Elena Trafton, Jennifer Gregorio, and Azeem Mufti. Other contributors who found one or more typos: Stijn Debrouwere, Guy Driesen, Andai Velican, Chris Kuszmaul, Daniel Kurikesu, Josh Donath, Rens Findhammer, Elisa Abedrapo, Yousef BaAfif, Bruce Hill, Matt Underwood, Isaac Sultan, Dan Rice, Robert Beard, Daniel Pierce, Michael Giftthaler, Chris Fox, Min Zeng, Markus Geuss, Mauricio Gonzalez, Enrico Sartirana, Kasem Satitwiwat, and Jason Miller. If you have additional comments or ideas about the text, please send them to feedback@greenteapress.com. —Allen Downey and Chris Mayfield

📄 Page 15

Chapter 1. Computer Programming The goal of this book is to teach you to think like a computer scientist. This way of thinking combines some of the best features of mathematics, engineering, and natural science. Like mathematicians, computer scientists use formal languages to denote ideas—specifically, computations. Like engineers, they design things, assembling components into systems and evaluating trade-offs among alternatives. And like scientists, they observe the behavior of complex systems, form hypotheses, and test predictions. An important skill for a computer scientist is problem solving. It involves the ability to formulate problems, think creatively about solutions, and express solutions clearly and accurately. As it turns out, the process of learning to program computers is an excellent opportunity to develop problem-solving skills. On one level, you will be learning to write Java programs, a useful skill by itself. But on another level, you will use programming as a means to an end. As we go along, that end will become clearer. What Is a Computer? When people hear the word computer, they often think of a desktop or laptop. Not surprisingly, searching for “computer” on Google Images displays rows and rows of these types of machines. However, in a more general sense, a computer can be any type of device that stores and processes data. Dictionary.com defines a computer as “a programmable electronic device designed to accept data, perform prescribed mathematical and logical operations at high speed, and display the results of these operations.

📄 Page 16

Mainframes, desktop and laptop computers, tablets, and smartphones are some of the different types of computers.” Each type of computer has its own unique design, but internally they all share the same type of hardware. The two most important hardware components are processors (or CPUs) that perform simple calculations and memory (or RAM) that temporarily stores information. Figure 1-1 shows what these components look like. Figure 1-1. Example processor and memory hardware Users generally see and interact with touchscreens, keyboards, and monitors, but it’s the processors and memory that perform the actual computation. Nowadays it’s fairly standard, even for a smartphone, to have at least eight processors and four gigabytes (four billion cells) of memory. What Is Programming? A program is a sequence of instructions that specifies how to perform a computation on computer hardware. The computation might be something mathematical, like solving a system of equations or finding the roots of a polynomial. It could also be a symbolic computation, like searching and replacing text in a document or (strangely enough) compiling a program. The details look different in different languages, but a few basic instructions appear in just about every language: Input

📄 Page 17

Get data from the keyboard, a file, a sensor, or some other device. Output Display data on the screen, or send data to a file or other device. Math Perform basic mathematical operations like addition and division. Secision Check for certain conditions and execute the appropriate code. Repetition Perform an action repeatedly, usually with some variation. Believe it or not, that’s pretty much all there is to it. Every program you’ve ever used, no matter how complicated, is made up of small instructions that look much like these. So you can think of programming as the process of breaking a large, complex task into smaller and smaller subtasks. The process continues until the subtasks are simple enough to be performed with the electronic circuits provided by the hardware. The Hello World Program Traditionally, the first program you write when learning a new programming language is called the Hello World program. All it does is output the words Hello, World! to the screen. In Java, it looks like this: public class Hello { public static void main(String[] args) { // generate some simple output System.out.println("Hello, World!"); } } When this program runs, it displays the following:

📄 Page 18

Hello, World! Notice that the output does not include the quotation marks. Java programs are made up of class and method definitions, and methods are made up of statements. A statement is a line of code that performs a basic action. In the Hello World program, this line is a print statement that displays a message to the user: System.out.println("Hello, World!"); System.out.println displays results on the screen; the name println stands for print line. Confusingly, print can mean both display on the screen and send to the printer. In this book, we’ll try to say display when we mean output to the screen. Like most statements, the print statement ends with a semicolon (;). Java is case-sensitive, which means that uppercase and lowercase are not the same. In the Hello World program, System has to begin with an uppercase letter; system and SYSTEM won’t work. A method is a named sequence of statements. This program defines one method named main: public static void main(String[] args) The name and format of main is special: when the program runs, it starts at the first statement in main and ends when it finishes the last statement. Later, you will see programs that define more than one method. This program defines a class named Hello. For now, a class is a collection of methods; we’ll have more to say about this later. You can give a class any name you like, but it is conventional to start with a capital letter. The name of the class has to match the name of the file it is in, so this class has to be in a file named Hello.java.

📄 Page 19

Java uses curly braces ({ and }) to group things together. In Hello.java, the outermost braces contain the class definition, and the inner braces contain the method definition. The line that begins with two slashes (//) is a comment, which is a bit of English text that explains the code. When Java sees //, it ignores everything from there until the end of the line. Comments have no effect on the execution of the program, but they make it easier for other programmers (and your future self) to understand what you meant to do. Compiling Java Programs The programming language you will learn in this book is Java, which is a high-level language. Other high-level languages you may have heard of include Python, C and C++, PHP, Ruby, and JavaScript. Before they can run, programs in high-level languages have to be translated into a low-level language, also called machine language. This translation takes some time, which is a small disadvantage of high-level languages. But high-level languages have two major advantages: It is much easier to program in a high-level language. Programs take less time to write, are shorter and easier to read, and are more likely to be correct. High-level languages are portable, meaning they can run on different kinds of computers with few or no modifications. Low- level programs can run on only one kind of computer. Two kinds of programs translate high-level languages into low-level languages: interpreters and compilers. An interpreter reads a high-level program and executes it, meaning that it does what the program says. It processes the program a little at a time, alternately reading lines and performing computations. Figure 1-2 shows the structure of an interpreter.

📄 Page 20

Figure 1-2. How interpreted languages are executed In contrast, a compiler reads the entire program and translates it completely before the program starts running. The high-level program is called the source code. The translated program is called the object code, or the executable. Once a program is compiled, you can execute it repeatedly without further translation. As a result, compiled programs often run faster than interpreted programs. Note that object code, as a low-level language, is not portable. You cannot run an executable compiled for a Windows laptop on an Android phone, for example. To run a program on different types of machines, it must be compiled multiple times. It can be difficult to write source code that compiles and runs correctly on different types of machines. To address this issue, Java is both compiled and interpreted. Instead of translating source code directly into an executable, the Java compiler generates code for a virtual machine. This “imaginary” machine has the functionality common to desktops, laptops, tablets, phones, etc. Its language, called Java byte code, looks like object code and is easy and fast to interpret. As a result, it’s possible to compile a Java program on one machine, transfer the byte code to another machine, and run the byte code on that other machine. Figure 1-3 shows the steps of the development process. The Java compiler is a program named javac. It translates .java files into .class files that store the resulting byte code. The Java interpreter is another program, named java, which is short for Java Virtual Machine (JVM).