《程序设计思想与方法》课程教学资源（课程教材）How to Think Like a Computer Scientist（Learning with Python）

Contents xxiii 8.15 Matrices...······· 94 8.16 Strings and lists..... 95 8.17 Glossary。········ 96 9 Tuples 97 9.1 Mutability and tuples 97 9.2 Tuple assignment..... 98 9.3 Tuples as return values . 99 9.4 Random numbers.·.··· 99 9.5 List of random numbers 100 9.6 Counting:..······ 4 。 。 101 9.7 Many buckets ... 102 9.8 A single-pass solution.. 104 9.9 Glossary···· 4 105 10 Dictionaries 107 10.1 Dictionary operations... 108 10.2 Dictionary methods.. 。 109 10.3 Aliasing and copying 4 110 10.4 Sparse matrices 110 10.5 Hints.····· 111 10.6 Long integers·· 113 10.7 Counting letters... 113 10.8 Glossary.·:··· 114 11 Files and exceptions 117 11.1 Text files.... 119 11.2 Vriting variables·.. 120 11.3 Directories..... 123

Contents xxiii 8.15 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 8.16 Strings and lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 8.17 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 9 Tuples 97 9.1 Mutability and tuples . . . . . . . . . . . . . . . . . . . . . . . . 97 9.2 Tuple assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 9.3 Tuples as return values . . . . . . . . . . . . . . . . . . . . . . . . 99 9.4 Random numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 9.5 List of random numbers . . . . . . . . . . . . . . . . . . . . . . . 100 9.6 Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 9.7 Many buckets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 9.8 A single-pass solution . . . . . . . . . . . . . . . . . . . . . . . . . 104 9.9 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 10 Dictionaries 107 10.1 Dictionary operations . . . . . . . . . . . . . . . . . . . . . . . . . 108 10.2 Dictionary methods . . . . . . . . . . . . . . . . . . . . . . . . . . 109 10.3 Aliasing and copying . . . . . . . . . . . . . . . . . . . . . . . . . 110 10.4 Sparse matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 10.5 Hints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 10.6 Long integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 10.7 Counting letters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 10.8 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 11 Files and exceptions 117 11.1 Text files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 11.2 Writing variables . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 11.3 Directories . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

xxiv Contents 11.4 Pickling··········· 123 11.5 Exceptions,···· 124 11.6 Glossary······ 126 12 Classes and objects 129 12.1 User-defined compound types . 129 12.2 Attributes......... 。。 130 12.3 Instances as arguments... 131 12.4 Sameness....·.··· 131 12.5 Rectangles....·.·· 4 133 12.6 Instances as return values 134 12.7 Objects are mutable 134 12.8 Copying 135 12.9 Glossary···· 137 13 Classes and functions 139 13.1 Time.······· 4 139 13.2 Pure functions... 44 140 13.3 Modifiers 44 141 13.4 Which is better? 142 13.5 Prototype development versus planning 143 13.6 Generalization.... 144 13.7 Algorithms 。。 144 13.8 Glossary .... 145 14 Classes and methods 147 14.1 Object-oriented features.. 147 14.2 printTime.···· 148 14.3 Another example 。。。 149

xxiv Contents 11.4 Pickling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 11.5 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 11.6 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 12 Classes and objects 129 12.1 User-defined compound types . . . . . . . . . . . . . . . . . . . . 129 12.2 Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 12.3 Instances as arguments . . . . . . . . . . . . . . . . . . . . . . . . 131 12.4 Sameness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 12.5 Rectangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 12.6 Instances as return values . . . . . . . . . . . . . . . . . . . . . . 134 12.7 Objects are mutable . . . . . . . . . . . . . . . . . . . . . . . . . 134 12.8 Copying . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 12.9 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 13 Classes and functions 139 13.1 Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 13.2 Pure functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 13.3 Modifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 13.4 Which is better? . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 13.5 Prototype development versus planning . . . . . . . . . . . . . . 143 13.6 Generalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 13.7 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 13.8 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 14 Classes and methods 147 14.1 Object-oriented features . . . . . . . . . . . . . . . . . . . . . . . 147 14.2 printTime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 14.3 Another example . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

Contents XXV 14.4 A more complicated example 150 14.5 Optional arguments.···· 151 14.6 The initialization method 152 14.7 Points revisited..... 153 14.8 Operator overloading.... 154 14.9 Polymorphism...·. 155 14.10G1 lossary.·.···· 157 15 Sets of objects 159 15.1 Composition...... 159 15.2 Card objects.......... 159 15.3 Class attributes and the_str__method 161 15.4 Comparing cards 162 15.5 Decks 163 15.6 Printing the deck 163 15.7 Shuffling the deck.···· 165 15.8 Removing and dealing cards 166 15.9 Glossary.········ 167 16 Inheritance 169 16.1 Inheritance... 169 16.2 A hand of cards ... 170 16.3 Dealing cards .... 171 16.4 Printing a Hand... 171 16.5 The CardGame class.. 172 16.6 01dMaidHand class 173 16.7 0ldMaidGame class .. 175 16.8 Glossary······ 179

Contents xxv 14.4 A more complicated example . . . . . . . . . . . . . . . . . . . . 150 14.5 Optional arguments . . . . . . . . . . . . . . . . . . . . . . . . . . 151 14.6 The initialization method . . . . . . . . . . . . . . . . . . . . . . 152 14.7 Points revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 14.8 Operator overloading . . . . . . . . . . . . . . . . . . . . . . . . . 154 14.9 Polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 14.10 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 15 Sets of objects 159 15.1 Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 15.2 Card objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 15.3 Class attributes and the str method . . . . . . . . . . . . . . 161 15.4 Comparing cards . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 15.5 Decks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 15.6 Printing the deck . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 15.7 Shuffling the deck . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 15.8 Removing and dealing cards . . . . . . . . . . . . . . . . . . . . . 166 15.9 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 16 Inheritance 169 16.1 Inheritance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 16.2 A hand of cards . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 16.3 Dealing cards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 16.4 Printing a Hand . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 16.5 The CardGame class . . . . . . . . . . . . . . . . . . . . . . . . . . 172 16.6 OldMaidHand class . . . . . . . . . . . . . . . . . . . . . . . . . . 173 16.7 OldMaidGame class . . . . . . . . . . . . . . . . . . . . . . . . . . 175 16.8 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179

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