xxvi Contents 17 Linked lists 181 17.1 Embedded references ... 181 17.2 The Node class....... 181 17.3 Lists as collections 183 17.4 Lists and recursion..... 184 17.5 Infinite lists········· 185 17.6 The fundamental ambiguity theorem . 186 17.7 Modifying lists 186 17.8 Wrappers and helpers 187 17.9 The LinkedList class 4 188 17.10 Invariants... 189 17.11 Glossary.... 4 190 18 Stacks 191 18.1 Abstract data types···· 191 18.2 The Stack ADT.··.·.· 192 18.3 Implementing stacks with Python lists 192 18.4 Pushing and popping。。················· 193 18.5 Using a stack to evaluate postfix 194 18.6 Parsing.···· 4 194 18.7 Evaluating postfix 195 18.8 Clients and providers.. 196 18.9 Glossary···· 4 197 19 Queues 199 19.1 The Queue ADT.... 199 19.2 Linked Queue...····· 200 19.3 Performance characteristics 201
xxvi Contents 17 Linked lists 181 17.1 Embedded references . . . . . . . . . . . . . . . . . . . . . . . . . 181 17.2 The Node class . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 17.3 Lists as collections . . . . . . . . . . . . . . . . . . . . . . . . . . 183 17.4 Lists and recursion . . . . . . . . . . . . . . . . . . . . . . . . . . 184 17.5 Infinite lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 17.6 The fundamental ambiguity theorem . . . . . . . . . . . . . . . . 186 17.7 Modifying lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 17.8 Wrappers and helpers . . . . . . . . . . . . . . . . . . . . . . . . 187 17.9 The LinkedList class . . . . . . . . . . . . . . . . . . . . . . . . 188 17.10 Invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 17.11 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 18 Stacks 191 18.1 Abstract data types . . . . . . . . . . . . . . . . . . . . . . . . . 191 18.2 The Stack ADT . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 18.3 Implementing stacks with Python lists . . . . . . . . . . . . . . . 192 18.4 Pushing and popping . . . . . . . . . . . . . . . . . . . . . . . . . 193 18.5 Using a stack to evaluate postfix . . . . . . . . . . . . . . . . . . 194 18.6 Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 18.7 Evaluating postfix . . . . . . . . . . . . . . . . . . . . . . . . . . 195 18.8 Clients and providers . . . . . . . . . . . . . . . . . . . . . . . . . 196 18.9 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 19 Queues 199 19.1 The Queue ADT . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 19.2 Linked Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 19.3 Performance characteristics . . . . . . . . . . . . . . . . . . . . . 201
Contents xxvii 19.4 Improved Linked Queue..... 201 19.5 Priority queue···· 203 19.6 The Golfer class 205 19.7 Glossary··· 206 20 Trees 207 20.1 Building trees···· 208 20.2 Traversing trees·.· 209 20.3 Expression trees.... 209 20.4 Tree traversal·.····· 210 20.5 Building an expression tree 212 20.6 Handling errors······ 216 20.7 The animal tree... 216 20.8 Glossary·· 219 A Debugging 221 A.1 Syntax errors 221 A.2 Runtime errors··· 223 A.3 Semantic errors.... 227 B Creating a new data type 231 B.1 Fraction multiplication 232 B.2 Fraction addition .. 234 B.3 Euclid's algorithm·.· 234 B.4 Comparing fractions 235 B.5 Taking it further.... 236 B.6 Glossary。··········· 236 C Recommendations for further reading 239 C.1 Python-related web sites and books,················ 240 C.2 Recommended general computer science books..........241
Contents xxvii 19.4 Improved Linked Queue . . . . . . . . . . . . . . . . . . . . . . . 201 19.5 Priority queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 19.6 The Golfer class . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 19.7 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 20 Trees 207 20.1 Building trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 20.2 Traversing trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 20.3 Expression trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 20.4 Tree traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 20.5 Building an expression tree . . . . . . . . . . . . . . . . . . . . . 212 20.6 Handling errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 20.7 The animal tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 20.8 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 A Debugging 221 A.1 Syntax errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 A.2 Runtime errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 A.3 Semantic errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 B Creating a new data type 231 B.1 Fraction multiplication . . . . . . . . . . . . . . . . . . . . . . . . 232 B.2 Fraction addition . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 B.3 Euclid’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 234 B.4 Comparing fractions . . . . . . . . . . . . . . . . . . . . . . . . . 235 B.5 Taking it further . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 B.6 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 C Recommendations for further reading 239 C.1 Python-related web sites and books . . . . . . . . . . . . . . . . . 240 C.2 Recommended general computer science books . . . . . . . . . . 241
xxviii Contents
xxviii Contents
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 components into systems and evaluating tradeoffs among alternatives. Like scientists,they observe the behavior of complex systems,form hypotheses, and test predictions. The single most important skill for a computer scientist is problem solving. Problem solving means the ability to formulate problems,think creatively about solutions,and express a solution clearly and accurately.As it turns out,the process of learning to program is an excellent opportunity to practice 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.On another level,you will use programming as a means to an end.As we go along,that end will become clearer. 1.1 The Python programming language The programming language you will be learning is Python.Python is an example of a high-level language;other high-level languages you might have heard of are C,C++,Perl,and Java. As you might infer from the name "high-level language,"there are also low- level languages,sometimes referred to as "machine languages"or "assembly
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 components into systems and evaluating tradeoffs among alternatives. Like scientists, they observe the behavior of complex systems, form hypotheses, and test predictions. The single most important skill for a computer scientist is problem solving. Problem solving means the ability to formulate problems, think creatively about solutions, and express a solution clearly and accurately. As it turns out, the process of learning to program is an excellent opportunity to practice problemsolving 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. On another level, you will use programming as a means to an end. As we go along, that end will become clearer. 1.1 The Python programming language The programming language you will be learning is Python. Python is an example of a high-level language; other high-level languages you might have heard of are C, C++, Perl, and Java. As you might infer from the name “high-level language,” there are also lowlevel languages, sometimes referred to as “machine languages” or “assembly
The way of the program languages."Loosely speaking,computers can only execute programs written in low-level languages.Thus,programs written in a high-level language have to be processed before they can run.This extra processing takes some time,which is a small disadvantage of high-level languages. But the advantages are enormous.First,it is much easier to program in a high- level language.Programs written in a high-level language take less time to write, they are shorter and easier to read,and they are more likely to be correct.Second, high-level languages are portable,meaning that they can run on different kinds of computers with few or no modifications.Low-level programs can run on only one kind of computer and have to be rewritten to run on another. Due to these advantages,almost all programs are written in high-level languages. Low-level languages are used only for a few specialized applications. Two kinds of programs process high-level languages into low-level languages:in- terpreters and compilers.An interpreter reads a high-level program and exe- cutes it,meaning that it does what the program says.It processes the program a little at a time,alternately reading lines and performing computations. SOURCE INTERPRETER OUTPUT CODE A compiler reads the program and translates it completely before the program starts running.In this case,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 translation. SOURCE COMPILER OBJECT EXECUTOR OUTPUT CODE CODE Python is considered an interpreted language because Python programs are exe- cuted by an interpreter.There are two ways to use the interpreter:command-line mode and script mode.In command-line mode,you type Python programs and the interpreter prints the result:
2 The way of the program languages.” Loosely speaking, computers can only execute programs written in low-level languages. Thus, programs written in a high-level language have to be processed before they can run. This extra processing takes some time, which is a small disadvantage of high-level languages. But the advantages are enormous. First, it is much easier to program in a highlevel language. Programs written in a high-level language take less time to write, they are shorter and easier to read, and they are more likely to be correct. Second, high-level languages are portable, meaning that they can run on different kinds of computers with few or no modifications. Low-level programs can run on only one kind of computer and have to be rewritten to run on another. Due to these advantages, almost all programs are written in high-level languages. Low-level languages are used only for a few specialized applications. Two kinds of programs process 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. SOURCE OUTPUT CODE INTERPRETER A compiler reads the program and translates it completely before the program starts running. In this case, 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 translation. OUTPUT CODE OBJECT EXECUTOR CODE SOURCE COMPILER Python is considered an interpreted language because Python programs are executed by an interpreter. There are two ways to use the interpreter: command-line mode and script mode. In command-line mode, you type Python programs and the interpreter prints the result: