Think Java How to Think Like a Computer Scientist (Allen B. Downey, Chris Mayfield) (Z-Library)

📄 File Format: PDF

💾 File Size: 6.0 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

Allen B. Downey & Chris Mayfield Think Java HOW TO THINK LIKE A COMPUTER SCIENTIST www.it-ebooks.info

📄 Page 2

www.it-ebooks.info

📄 Page 3

Allen B. Downey and Chris Mayfield Think Java How to Think Like a Computer Scientist Boston Farnham Sebastopol TokyoBeijing www.it-ebooks.info

📄 Page 4

978-1-491-92956-8 [LSI] Think Java by Allen B. Downey and Chris Mayfield Copyright © 2016 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://safaribooksonline.com). For more information, contact our corporate/ institutional sales department: 800-998-9938 or corporate@oreilly.com. Editor: Brian Foster Production Editor: Kristen Brown Copyeditor: Charles Roumeliotis Proofreader: Christina Edwards Indexers: Allen B. Downey and Chris Mayfield Interior Designer: David Futato Cover Designer: Karen Montgomery Illustrator: Rebecca Demarest May 2016: First Edition Revision History for the First Edition 2016-05-06: First Release See http://oreilly.com/catalog/errata.csp?isbn=9781491929568 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. 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 3.0 Unported License. The author maintains an online version at http://greenteapress.com/wp/think-java/. www.it-ebooks.info

📄 Page 5

Table of Contents Preface. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix 1. The Way of the Program. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 What Is Programming? 1 What Is Computer Science? 2 Programming Languages 3 The Hello World Program 4 Displaying Strings 5 Escape Sequences 6 Formatting Code 7 Debugging Code 8 Vocabulary 8 Exercises 10 2. Variables and Operators. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Declaring Variables 13 Assignment 14 State Diagrams 15 Printing Variables 16 Arithmetic Operators 16 Floating-Point Numbers 17 Rounding Errors 19 Operators for Strings 19 Composition 21 Types of Errors 21 Vocabulary 24 Exercises 25 iii www.it-ebooks.info

📄 Page 6

3. Input and Output. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 The System Class 29 The Scanner Class 30 Program Structure 31 Inches to Centimeters 32 Literals and Constants 33 Formatting Output 33 Centimeters to Inches 35 Modulus Operator 35 Putting It All Together 36 The Scanner Bug 37 Vocabulary 38 Exercises 39 4. Void Methods. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Math Methods 43 Composition Revisited 44 Adding New Methods 45 Flow of Execution 47 Parameters and Arguments 48 Multiple Parameters 49 Stack Diagrams 50 Reading Documentation 51 Writing Documentation 53 Vocabulary 54 Exercises 55 5. Conditionals and Logic. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Relational Operators 57 Logical Operators 58 Conditional Statements 59 Chaining and Nesting 60 Flag Variables 61 The return Statement 61 Validating Input 62 Recursive Methods 62 Recursive Stack Diagrams 64 Binary Numbers 65 Vocabulary 66 Exercises 67 iv | Table of Contents www.it-ebooks.info

📄 Page 7

6. Value Methods. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Return Values 71 Writing Methods 73 Method Composition 75 Overloading 76 Boolean Methods 77 Javadoc Tags 78 More Recursion 79 Leap of Faith 81 One More Example 82 Vocabulary 82 Exercises 83 7. Loops. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 The while Statement 89 Generating Tables 90 Encapsulation and Generalization 92 More Generalization 94 The for Statement 96 The do-while Loop 97 break and continue 98 Vocabulary 99 Exercises 99 8. Arrays. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 Creating Arrays 103 Accessing Elements 104 Displaying Arrays 105 Copying Arrays 106 Array Length 107 Array Traversal 107 Random Numbers 108 Traverse and Count 109 Building a Histogram 110 The Enhanced for Loop 111 Vocabulary 112 Exercises 113 9. Strings and Things. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 Characters 117 Strings Are Immutable 118 String Traversal 119 Table of Contents | v www.it-ebooks.info

📄 Page 8

Substrings 120 The indexOf Method 121 String Comparison 121 String Formatting 122 Wrapper Classes 123 Command-Line Arguments 123 Vocabulary 125 Exercises 125 10. Objects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 Point Objects 131 Attributes 132 Objects as Parameters 133 Objects as Return Types 133 Mutable Objects 134 Aliasing 136 The null Keyword 137 Garbage Collection 137 Class Diagrams 138 Java Library Source 139 Vocabulary 140 Exercises 140 11. Classes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 The Time Class 145 Constructors 146 More Constructors 148 Getters and Setters 149 Displaying Objects 151 The toString Method 151 The equals Method 152 Adding Times 154 Pure Methods and Modifiers 155 Vocabulary 156 Exercises 157 12. Arrays of Objects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 Card Objects 161 Card toString 163 Class Variables 164 The compareTo Method 165 Cards Are Immutable 166 vi | Table of Contents www.it-ebooks.info

📄 Page 9

Arrays of Cards 167 Sequential Search 169 Binary Search 169 Tracing the Code 170 Recursive Version 171 Vocabulary 172 Exercises 172 13. Objects of Arrays. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 The Deck Class 175 Shuffling Decks 176 Selection Sort 177 Merge Sort 178 Subdecks 178 Merging Decks 179 Adding Recursion 180 Vocabulary 181 Exercises 181 14. Objects of Objects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 Decks and Hands 186 CardCollection 186 Inheritance 189 Dealing Cards 190 The Player Class 191 The Eights Class 194 Class Relationships 197 Vocabulary 198 Exercises 198 A. Development Tools. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 B. Java 2D Graphics. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 C. Debugging. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 Index. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 Table of Contents | vii www.it-ebooks.info

📄 Page 10

www.it-ebooks.info

📄 Page 11

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 recursion and object-oriented program‐ ming, are divided into smaller examples and introduced over the course of several chapters. This book is intentionally concise. Each chapter is 12–14 pages and covers the mate‐ rial for one week of a college course. It is not meant to be a comprehensive presenta‐ tion 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. 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 glossa‐ ries at the end of each chapter. ix www.it-ebooks.info

📄 Page 12

• Program development. There are many strategies for writing programs, including bottom-up, top-down, and others. We demonstrate multiple program develop‐ ment techniques, allowing readers to choose methods that work best for them. • Multiple learning curves. To write a program, you have to understand the algo‐ rithm, know the programming language, and be able to debug errors. We discuss these and other aspects throughout the book, and include an appendix that sum‐ marizes our advice. Object-Oriented Programming Some Java books introduce classes and objects immediately; others begin with proce‐ dural programming and transition to object-oriented more gradually. Many of Java’s object-oriented features are motivated by problems with previous lan‐ guages, and their implementations are influenced by this history. Some of these fea‐ tures are hard to explain when people aren’t familiar with the problems they solve. We get to object-oriented programming as quickly as possible, limited by the require‐ ment that 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. But 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. This book is well suited to prepare students for the AP Computer Science A exam, which includes object-oriented design and implementation. (AP is a registered trade‐ mark of the College Board.) We introduce nearly every topic in the “AP Java subset” with a few exceptions. A mapping of Think Java section numbers to the current AP course description is available on our website: http://thinkjava.org. Appendixes The chapters of this book are meant to be read in order, because each one builds on the previous one. We also include three appendixes with material that can be read at any time: Appendix A, Development Tools The steps for compiling, running, and debugging Java code depend on the details of the development environment and operating system. We avoided putting these details in the main text, because they can be distracting. Instead, we provide this appendix with a brief introduction to DrJava—an interactive development envi‐ x | Preface www.it-ebooks.info

📄 Page 13

ronment (IDE) that is helpful for beginners—and other development tools, including Checkstyle for code quality and JUnit for testing. Appendix B, Java 2D 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 readers will not completely understand until after Chapter 11, but they can be used much earlier. Appendix C, Debugging We provide debugging suggestions throughout the book, but we also collect our debugging advice in an appendix. We recommend that readers review this appen‐ dix several times as they work through the book. Using the Code Examples Most of the code examples in this book are available from a Git repository at https:// github.com/AllenDowney/ThinkJavaCode. 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 conve‐ nient web interface. It provides several ways to work with the code: • You can create a copy of the repository on GitHub by pressing 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 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. • 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: http:// tinyurl.com/ThinkJavaCodeZip. After you clone the repository or unzip the ZIP file, you should have a directory called ThinkJavaCode with a subdirectory for each chapter in the book. All examples in this book were developed and tested using Java SE Development Kit 8. If you are using a more recent version, the examples in this book should still work. If you are using an older version, some of them may not. Preface | xi www.it-ebooks.info

📄 Page 14

Conventions Used in This Book The following typographical conventions are used in this book: Italic Indicates emphasis, keystrokes, menu options, URLs, and email addresses. Bold Indicates terms defined in the Vocabulary section at the end of each chapter. Constant width Used for program listings, as well as within paragraphs to refer to filenames, file extensions, and program elements such as variable and function names, data types, statements, and keywords. Constant width bold Shows commands or other text that should be typed literally by the user. Safari® Books Online Safari Books Online (www.safaribooksonline.com) is an on- demand digital library that delivers expert content in both book and video form from the world’s leading authors in tech‐ nology and business. Technology professionals, software developers, web designers, and business and crea‐ tive professionals use Safari Books Online as their primary resource for research, problem solving, learning, and certification training. Safari Books Online offers a range of plans and pricing for enterprise, government, education, and individuals. Members have access to thousands of books, training videos, and prepublication manuscripts in one fully searchable database from publishers like O’Reilly Media, Prentice Hall Professional, Addison-Wesley Professional, Microsoft Press, Sams, Que, Peachpit Press, Focal Press, Cisco Press, John Wiley & Sons, Syngress, Morgan Kauf‐ mann, IBM Redbooks, Packt, Adobe Press, FT Press, Apress, Manning, New Riders, McGraw-Hill, Jones & Bartlett, Course Technology, and hundreds more. For more information about Safari Books Online, please visit us online. xii | Preface www.it-ebooks.info

📄 Page 15

How to Contact Us Please address comments and questions concerning this book to the publisher: O’Reilly Media, Inc. 1005 Gravenstein Highway North 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 http://bit.ly/think-java-1e. To comment or ask technical questions about this book, send email to bookques‐ tions@oreilly.com. For more information about our books, courses, conferences, and news, see our web‐ site 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, and we appreciate their valuable feedback! • Ellen Hildreth used this book to teach Data Structures at Wellesley College and submitted a whole stack of corrections, along with some great suggestions. • Tania Passfield pointed out that some glossaries had leftover terms that no longer appeared in the text. • 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. Preface | xiii www.it-ebooks.info

📄 Page 16

• Marius Margowski found an inconsistency in a code example. • Leslie Klein discovered another error in the series expansion of exp − x2 , iden‐ tified typos in the card array figures, and gave helpful suggestions to clarify sev‐ eral exercises. • Micah Lindstrom reported half a dozen typos and sent corrections. • James Riely ported the textbook source from LaTeX to Sphinx: http:// fpl.cs.depaul.edu/jriely/thinkapjava/. • Peter Knaggs ported the book to C#: http://www.rigwit.co.uk/think/sharp/. • Heidi Gentry-Kolen recorded several video lectures that follow the book: https:// www.youtube.com/user/digipipeline. We are especially grateful to our technical reviewers: Blythe Samuels, David Wisneski, and Stephen Rose. They found errors, made many great suggestions, and helped make the book much better. Additional contributors who found one or more typos: Stijn Debrouwere, Guy Drie‐ sen, Andai Velican, Chris Kuszmaul, Daniel Kurikesu, Josh Donath, Rens Findham‐ mer, Elisa Abedrapo, Yousef BaAfif, Bruce Hill, Matt Underwood, Isaac Sultan, Dan Rice, Robert Beard, and Daniel Pierce. If you have additional comments or ideas about the text, please send them to: feedback@greenteapress.com. xiv | Preface www.it-ebooks.info

📄 Page 17

CHAPTER 1 The Way of the Program 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 com‐ ponents into systems and evaluating trade-offs among alternatives. And like scien‐ tists, they observe the behavior of complex systems, form hypotheses, and test predictions. The single most 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 is an excellent opportunity to develop problem solving skills. That’s why this chapter is called, “The way of the program”. On one level you will be learning to program, 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 Programming? A program is a sequence of instructions that specifies how to perform a computation. The computation might be something mathematical, like solving a system of equa‐ tions or finding the roots of a polynomial. It can also be a symbolic computation, like searching and replacing text in a document or (strangely enough) compiling a pro‐ gram. The details look different in different languages, but a few basic instructions appear in just about every language. 1 www.it-ebooks.info

📄 Page 18

input: 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. decisions: Check for certain conditions and execute the appropriate code. repetition: Perform some 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 down a large, complex task into smaller and smaller subtasks. The process continues until the sub‐ tasks are simple enough to be performed with the basic instructions provided by the computer. What Is Computer Science? One of the most interesting aspects of writing programs is deciding how to solve a particular problem, especially when there are multiple solutions. For example, there are numerous ways to sort a list of numbers, and each way has its advantages. In order to determine which way is best for a given situation, we need techniques for describing and analyzing solutions formally. Computer science is the science of algorithms, including their discovery and analy‐ sis. An algorithm is a sequence of steps that specifies how to solve a problem. Some algorithms are faster than others, and some use less space in computer memory. As you learn to develop algorithms for problems you haven’t solved before, you also learn to think like a computer scientist. Designing algorithms and writing code is difficult and error-prone. For historical rea‐ sons, programming errors are called bugs, and the process of tracking them down and correcting them is called debugging. As you learn to debug your programs, you will develop new problem solving skills. You will need to think creatively when unex‐ pected errors happen. Although it can be frustrating, debugging is an intellectually rich, challenging, and interesting part of computer programming. In some ways, debugging is like detective work. You are confronted with clues, and you have to infer the processes and events 2 | Chapter 1: The Way of the Program www.it-ebooks.info

📄 Page 19

that led to the results you see. Thinking about how to correct programs and improve their performance sometimes even leads to the discovery of new algorithms. Programming Languages The programming language you will learn is Java, which is a high-level language. Other high-level languages you may have heard of include Python, C and C++, 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 advantages: • It is much easier to program in a high-level language. Programs take less time to write, they are shorter and easier to read, and they 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 only run on one kind of computer, and have to be rewritten to run on another. Two kinds of programs translate high-level languages into low-level languages: inter‐ preters 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-1 shows the struc‐ ture of an interpreter. Figure 1-1. How interpreted languages are executed. In contrast, a compiler reads the entire program and translates it completely before the program starts running. In this context, the high-level program is called the source code, and the translated program is called the object code or the executable. Once a program is compiled, you can execute it repeatedly without further transla‐ tion. As a result, compiled programs often run faster than interpreted programs. Java is both compiled and interpreted. Instead of translating programs directly into machine language, the Java compiler generates byte code. Similar to machine lan‐ guage, byte code is easy and fast to interpret. But it is also portable, so it is possible to compile a Java program on one machine, transfer the byte code to another machine, Programming Languages | 3 www.it-ebooks.info

📄 Page 20

and run the byte code on the other machine. The interpreter that runs byte code is called a “Java Virtual Machine” (JVM). Figure 1-2. The process of compiling and running a Java program. Figure 1-2 shows the steps of this process. Although it might seem complicated, these steps are automated for you in most program development environments. Usually you only have to press a button or type a single command to compile and run your program. On the other hand, it is important to know what steps are happening in the background, so if something goes wrong you can figure out what it is. The Hello World Program Traditionally, the first program you write when learning a new programming lan‐ guage is called the hello world program. All it does is display the words “Hello, World!” on 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: 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 operation. In the hello world program, this line is a print statement that displays a message on the screen: 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 (;). 4 | Chapter 1: The Way of the Program www.it-ebooks.info