thinkCScpp.pdf

How to think like a computer scientist

Allen B. Downey

C++ Version, First Edition

How to think like a computer scientist

C++ Version, First Edition

This book is an Open Source Textbook (OST). Permission is granted to

reproduce, store or transmit the text of this book by any means, electrical,

mechanical, or biological, in accordance with the terms of the GNU General

Public License as published by the Free Software Foundation (version 2).

This book is distributed in the hope that it will be useful, but WITHOUT

ANY WARRANTY; without even the implied warranty of MERCHANTABIL-

ITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General

Public License for more details.

The original form of this book is LaTeX source code. Compiling this LaTeX

source has the eect of generating a device-independent representation of a

textbook, which can be converted to other formats and printed. All intermediate

representations (including DVI and Postscript), and all printed copies of the

textbook are also covered by the GNU General Public License.

The LaTeX source for this book, and more information about the Open

Source Textbook project, is available from

http://www.cs.colby.edu/~downey/ost

or by writing to Allen B. Downey, 5850 Mayower Hill, Waterville, ME 04901.

The GNU General Public License is available from www.gnu.org or by writ-

ing to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,

MA 02111-1307, USA.

This book was typeset by the author using LaTeX and dvips, which are both

free, open-source programs.

Contents

1 The way of the program 1

1.1 What is a programming language? . . . . . . . . . . . . . . . . . 1

1.2 What is a program? . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 What is debugging? . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3.1 Compile-time errors . . . . . . . . . . . . . . . . . . . . . 4

1.3.2 Run-time errors . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3.3 Logic errors and semantics . . . . . . . . . . . . . . . . . 4

1.3.4 Experimental debugging . . . . . . . . . . . . . . . . . . . 5

1.4 Formal and natural languages . . . . . . . . . . . . . . . . . . . . 5

1.5 The rst program . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.6 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Variables and types 11

2.1 More output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.2 Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.3 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.4 Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.5 Outputting variables . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.6 Keywords . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.7 Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.8 Order of operations . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.9 Operators for characters . . . . . . . . . . . . . . . . . . . . . . . 17

2.10 Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.11 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3 Function 21

3.1 Floating-point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.2 Converting from double to int . . . . . . . . . . . . . . . . . . . 22

3.3 Math functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.4 Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.5 Adding new functions . . . . . . . . . . . . . . . . . . . . . . . . 24

3.6 Denitions and uses . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.7 Programs with multiple functions . . . . . . . . . . . . . . . . . . 27

3.8 Parameters and arguments . . . . . . . . . . . . . . . . . . . . . 27

CONTENTS

3.9 Parameters and variables are local . . . . . . . . . . . . . . . . . 28

3.10 Functions with multiple parameters . . . . . . . . . . . . . . . . . 29

3.11 Functions with results . . . . . . . . . . . . . . . . . . . . . . . . 30

3.12 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4 Conditionals and recursion 31

4.1 The modulus operator . . . . . . . . . . . . . . . . . . . . . . . . 31

4.2 Conditional execution . . . . . . . . . . . . . . . . . . . . . . . . 31

4.3 Alternative execution . . . . . . . . . . . . . . . . . . . . . . . . . 32

4.4 Chained conditionals . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.5 Nested conditionals . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.6 The return statement . . . . . . . . . . . . . . . . . . . . . . . . 34

4.7 Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.8 Innite recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4.9 Stack diagrams for recursive functions . . . . . . . . . . . . . . . 36

4.10 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

5 Fruitful functions 39

5.1 Return values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5.2 Program development . . . . . . . . . . . . . . . . . . . . . . . . 41

5.3 Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

5.4 Overloading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

5.5 Boolean values . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5.6 Boolean variables . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5.7 Logical operators . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5.8 Bool functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5.9 Returning from main . . . . . . . . . . . . . . . . . . . . . . . . . 47

5.10 More recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

5.11 Leap of faith . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5.12 One more example . . . . . . . . . . . . . . . . . . . . . . . . . . 51

5.13 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

6 Iteration 53

6.1 Multiple assignment . . . . . . . . . . . . . . . . . . . . . . . . . 53

6.2 Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

6.3 The while statement . . . . . . . . . . . . . . . . . . . . . . . . . 54

6.4 Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

6.5 Two-dimensional tables . . . . . . . . . . . . . . . . . . . . . . . 58

6.6 Encapsulation and generalization . . . . . . . . . . . . . . . . . . 58

6.7 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

6.8 More encapsulation . . . . . . . . . . . . . . . . . . . . . . . . . . 60

6.9 Local variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

6.10 More generalization . . . . . . . . . . . . . . . . . . . . . . . . . 61

6.11 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

CONTENTS

iii

7 Strings and things 65

7.1 Containers for strings . . . . . . . . . . . . . . . . . . . . . . . . 65

7.2 apstring variables . . . . . . . . . . . . . . . . . . . . . . . . . . 66

7.3 Extracting characters from a string . . . . . . . . . . . . . . . . . 66

7.4 Length . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

7.5 Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

7.6 A run-time error . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

7.7 The find function . . . . . . . . . . . . . . . . . . . . . . . . . . 68

7.8 Our own version of find . . . . . . . . . . . . . . . . . . . . . . . 69

7.9 Looping and counting . . . . . . . . . . . . . . . . . . . . . . . . 69

7.10 Increment and decrement operators . . . . . . . . . . . . . . . . . 70

7.11 String concatenation . . . . . . . . . . . . . . . . . . . . . . . . . 71

7.12 apstring s are mutable . . . . . . . . . . . . . . . . . . . . . . . . 72

7.13 apstring s are comparable . . . . . . . . . . . . . . . . . . . . . . 72

7.14 Character classication . . . . . . . . . . . . . . . . . . . . . . . . 73

7.15 Other apstring functions . . . . . . . . . . . . . . . . . . . . . . 73

7.16 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

8 Structures 75

8.1 Compound values . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

8.2 Point objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

8.3 Accessing instance variables . . . . . . . . . . . . . . . . . . . . . 76

8.4 Operations on structures . . . . . . . . . . . . . . . . . . . . . . . 77

8.5 Structures as parameters . . . . . . . . . . . . . . . . . . . . . . . 78

8.6 Call by value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

8.7 Call by reference . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

8.8 Rectangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

8.9 Structures as return types . . . . . . . . . . . . . . . . . . . . . . 82

8.10 Passing other types by reference . . . . . . . . . . . . . . . . . . 82

8.11 Getting user input . . . . . . . . . . . . . . . . . . . . . . . . . . 83

8.12 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

9 More structures 87

9.1 Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

9.2 printTime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

9.3 Functions for objects . . . . . . . . . . . . . . . . . . . . . . . . . 88

9.4 Pure functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

9.5 const parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

9.6 Modiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

9.7 Fill-in functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

9.8 Which is best? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

9.9 Incremental development versus planning . . . . . . . . . . . . . 92

9.10 Generalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

9.11 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

9.12 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: