main

1 Think C++Allen B. DowneyVersion C++Copyright (C) 1999 Allen B. DowneyGreen Tea Press9 Washburn AveNeedham MA 02492 Permission is granted to copy, distribute, transmit and adapt this work undera Creative Commons Attribution-NonCommercial-ShareAlike InternationalLicense: you are interested in distributing a commercial version of this work, pleasecontact the LATEX source and code for this book is available The way of the What is a programming language? .. What is a program? .. What is debugging? .. Compile-time errors .. Run-time errors .. Logic errors and semantics .. Experimental debugging .. Formal and natural languages .. The first program .. Glossary .. 82 Variables and More output .. Values .. Variables .. Assignment .. Outputting variables .. Keywords .. Operators .. Order of operations .. Operators for characters .. Composition.

2 Glossary .. 183 Floating-point .. Converting fromdoubletoint.. Math functions .. Composition .. Adding new functions .. Definitions and uses .. Programs with multiple functions .. Parameters and arguments .. Parameters and variables are local .. Functions with multiple parameters .. Functions with results .. Glossary .. 314 Conditionals and The modulus operator .. Conditional execution .. Alternative execution .. Chained conditionals .. Nested conditionals .. Thereturnstatement .. Recursion .. Infinite recursion .. Stack diagrams for recursive functions .. Glossary .. 405 Fruitful Return values .. Program development .. Composition .. Overloading .. Boolean values .. Boolean variables .. Logical operators .. Bool functions .. Returning frommain.. More recursion .. Leap of faith .. One more example.

3 Glossary .. 536 Multiple assignment .. Iteration .. Thewhilestatement .. Tables .. Two-dimensional tables .. Encapsulation and generalization .. Functions .. More encapsulation .. Local variables .. More generalization .. Glossary .. 65 CONTENTSiii7 Strings and Containers for strings .. Extracting characters from a string .. Length .. Traversal .. A run-time error .. Thefindfunction .. Our own version offind.. Looping and counting .. Increment and decrement operators .. String concatenation .. are mutable .. are comparable .. Character classification .. Otherstringfunctions .. Glossary .. 758 Compound values .. Accessing instance variables .. Operations on structures .. Structures as parameters .. Call by value .. Call by reference .. Rectangles .. Structures as return types .. Passing other types by reference.

4 Getting user input .. Glossary .. 879 More Time .. Functions for objects .. Pure functions .. Modifiers .. Fill-in functions .. Which is best? .. Incremental development versus planning .. Generalization .. Algorithms .. Glossary .. 97ivCONTENTS10 Accessing elements .. Copying vectors .. Vector size .. Vector functions .. Random numbers .. Statistics .. Vector of random numbers .. Counting .. the other values .. histogram .. single-pass solution .. seeds .. 10911 Member Objects and functions .. Implicit variable access .. Another example .. Yet another example .. A more complicated example .. Constructors .. Initialize or construct? .. One last example .. files .. 12112 Vectors of Composition .. TheprintCardfunction .. Theequalsfunction .. TheisGreaterfunction .. Vectors of cards .. TheprintDeckfunction .. Searching.

5 Bisection search .. and subdecks .. 135 CONTENTSv13 Objects of Enumerated types .. Decks .. Another constructor .. functions .. Shuffling .. Sorting .. Subdecks .. Shuffling and dealing .. 14714 Classes and Private data and classes .. What is a class? .. Complex numbers .. Accessor functions .. Output .. A function onComplexnumbers .. Another function onComplexnumbers .. Invariants .. Preconditions .. functions .. 16015 File Input/Output Streams .. File input .. File output .. Parsing input .. Parsing numbers .. TheSetdata structure .. A distance matrix .. A proper distance matrix .. 173A Quick reference for AP .. 177viCONTENTSC hapter 1 The way of the programThe goal of this book is to teach you to think like a computer scientist. I likethe way computer scientists think because they combine someof the best fea-tures of Mathematics, Engineering, and Natural Science.

6 Like mathematicians,computer scientists use formal languages to denote ideas (specifically computa-tions). Like engineers, they design things, assembling components into systemsand evaluating tradeoffs among alternatives. Like scientists, they observe thebehavior of complex systems, form hypotheses, and test single most important skill for a computer scientist that I mean the ability to formulate problems, think creatively about solu-tions, and express a solution clearly and accurately. As it turns out, the processof learning to program is an excellent opportunity to practice problem-solvingskills. That s why this chapter is called The way of the program. Of course, the other goal of this book is to prepare you for theComputerScience AP Exam. We may not take the most direct approach to that goal,though. For example, there are not many exercises in this book that are similarto the AP questions. On the other hand, if you understand the concepts in thisbook, along with the details of programming in C++, you will have all the toolsyou need to do well on the What is a programming language?

7 The programming language you will be learning is C++, because that is thelanguage the AP exam is based on, as of 1998. Before that, the exam usedPascal. Both C++ and Pascal arehigh-level languages; other high-levellanguages you might have heard of are Java, C and you might infer from the name high-level language, there are alsolow-level languages, sometimes referred to as machine language or assemblylanguage. Loosely-speaking, computers can only execute programs written inlow-level languages. Thus, programs written in a high-level language have tobe translated before they can run. This translation takes some time, which is a12 CHAPTER 1. THE WAY OF THE PROGRAM small disadvantage of high-level the advantages are enormous. First, it ismucheasier to program ina high-level language; by easier I mean that the program takes less time towrite, it s shorter and easier to read, and it s more likely to be correct. Secondly,high-level languages areportable, meaning that they can run on different kindsof computers with few or no modifications.

8 Low-level programs can only run onone kind of computer, and have to be rewritten to run on to these advantages, almost all programs are written in high-level lan-guages. Low-level languages are only used for a few special are two ways to translate a program; interpreter is a program that reads a high-level program and does what itsays. In effect, it translates the program line-by-line, alternately reading linesand carrying out interpreterreads thesource and the resultappears onthe compiler is a program that reads a high-level program and translates it allat once, before executing any of the commands. Often you compile the programas a separate step, and then execute the compiled code this case, thehigh-level program is called thesource code, and the translated program iscalled theobject codeor an example, suppose you write a program in C++. You might use atext editor to write the program (a text editor is a simple word processor).

9 When the program is finished, you might save it in a file ,where program is an arbitrary name you make up, and the aconvention that indicates that the file contains C++ source , depending on what your programming environment is like, you mightleave the text editor and run the compiler. The compiler would read your sourcecode, translate it, and create a new file contain the objectcode, contain the WHAT IS A PROGRAM?3objectcodeexecutorThe compilerreads thesource and generatesobject execute theprogram (one wayor another).. and the resultappears onthe next step is to run the program, which requires some kind of role of the executor is to load the program (copy it from disk into memory)and make the computer start executing the this process may seem complicated, the good news isthat inmost programming environments (sometimes called development environments),these steps are automated for you. Usually you will only haveto write a pro-gram and type a single command to compile and run it.

10 On the other hand, itis useful to know what the steps are that are happening in the background, sothat if something goes wrong you can figure out what it What is a program?A program is a sequence of instructions that specifies how to perform a com-putation. The computation might be something mathematical, like solving asystem of equations or finding the roots of a polynomial, but it can also bea symbolic computation, like searching and replacing text in a document or(strangely enough) compiling a instructions (or commands, or statements) look different in differentprogramming languages, but there are a few basic functions that appear in justabout every language:input:Get data from the keyboard, or a file, or some other :Display data on the screen or send data to a file or other :Perform basic mathematical operations like addition and :Check for certain conditions and execute the appropriate sequence :Perform some action repeatedly, usually with some it or not, that s pretty much all there is to it.