Fundamentals of Python Data Structures

Cover......Page 1
Contents......Page 7
Introduction......Page 18
  Programs and Modules......Page 24
  An Example Python Program: Guessing a Number......Page 25
  Editing, Compiling, and Running Python Programs......Page 26
  Spelling and Naming Conventions......Page 27
  String Literals......Page 28
  Operators and Expressions......Page 29
  Optional and Keyword Function Arguments......Page 30
  Variables and Assignment Statements......Page 31
  Getting Help on Program Components......Page 32
  Conditional Statements......Page 33
  Using if __name__ == "__main__"......Page 34
  Loop Statements......Page 35
  Operators......Page 36
  Formatting Strings for Output......Page 37
  Objects and Method Calls......Page 39
  Lists......Page 40
  Loops Over Sequences......Page 41
  Pattern Matching with Collections......Page 42
  Function Definitions......Page 43
  Recursive Functions......Page 44
  Higher-Order Functions......Page 47
  Creating Anonymous Functions with lambda......Page 48
 Catching Exceptions......Page 49
  Text File Output......Page 50
  Writing Numbers to a Text File......Page 51
  Reading Text from a Text File......Page 52
  Reading Numbers from a File......Page 53
  Reading and Writing Objects with pickle......Page 54
 Creating New Classes......Page 55
 Projects......Page 59
 Collection Types......Page 62
  Hierarchical Collections......Page 63
  Sorted Collections......Page 64
  A Taxonomy of Collection Types......Page 65
 Operations on Collections......Page 66
 Implementations of Collections......Page 68
 Review Questions......Page 70
 Projects......Page 71
 Measuring the Efficiency of Algorithms......Page 72
  Measuring the Run Time of an Algorithm......Page 73
  Counting Instructions......Page 75
  Exercises 3.1......Page 78
  Orders of Complexity......Page 79
  The Role of the Constant of Proportionality......Page 81
  Exercises 3.2......Page 82
  Sequential Search of a List......Page 83
  Best-Case, Worst-Case, and Average-Case Performance......Page 84
  Binary Search of a Sorted List......Page 85
  Comparing Data Items......Page 86
 Basic Sort Algorithms......Page 88
  Selection Sort......Page 89
  Bubble Sort......Page 90
  Insertion Sort......Page 91
  Best-Case, Worst-Case, and Average-Case Performance Revisited......Page 93
 Faster Sorting......Page 94
  Overview of Quicksort......Page 95
  Merge Sort......Page 99
  Exercises 3.5......Page 102
 An Exponential Algorithm: Recursive Fibonacci......Page 103
  Converting Fibonacci to a Linear Algorithm......Page 104
  Analysis......Page 105
  Design......Page 107
  Implementation (Coding)......Page 108
 Summary......Page 110
 Review Questions......Page 111
 Projects......Page 113
 The Array Data Structure......Page 116
  Random Access and Contiguous Memory......Page 119
  Physical Size and Logical Size......Page 120
 Operations on Arrays......Page 121
  Decreasing the Size of an Array......Page 122
  Inserting an Item into an Array That Grows......Page 123
  Removing an Item from an Array......Page 124
  Complexity Trade-Off: Time, Space, and Arrays......Page 125
  Exercises 4.2......Page 126
  Processing a Grid......Page 127
  Defining a Grid Class......Page 128
  Exercises 4.3......Page 129
  Singly Linked Structures and Doubly Linked Structures......Page 130
  Noncontiguous Memory and Nodes......Page 132
  Using the Singly Linked Node Class......Page 134
  Traversal......Page 136
  Searching......Page 137
  Replacement......Page 138
  Inserting at the Beginning......Page 139
  Inserting at the End......Page 140
  Removing at the End......Page 141
  Inserting at Any Position......Page 143
  Removing at Any Position......Page 144
  Complexity Trade-Off: Time, Space, and Singly Linked Structures......Page 146
  A Circular Linked Structure with a Dummy Header Node......Page 147
  Doubly Linked Structures......Page 148
 Summary......Page 151
 Projects......Page 152
Chapter 5 Interfaces, Implementations, and Polymorphism......Page 156
  Designing the Bag Interface......Page 157
  Specifying Arguments and Return Values......Page 158
  Constructors and Implementing Classes......Page 160
  Preconditions, Postconditions, Exceptions, and Documentation......Page 161
  Coding an Interface in Python......Page 162
 Developing an Array-Based Implementation......Page 163
  Choose and Initialize the Data Structures......Page 164
  Complete the Easy Methods First......Page 165
  Complete the Iterator......Page 166
  Complete the Methods That Use the Iterator......Page 167
  Complete the remove Method......Page 168
 Developing a Link-Based Implementation......Page 169
  Initialize the Data Structures......Page 170
  Complete the Method remove......Page 171
 Testing the Two Bag Implementations......Page 173
 Diagramming the Bag Resource with UML......Page 175
 Review Questions......Page 176
 Projects......Page 177
Chapter 6 Inheritance and Abstract Classes......Page 178
  Subclassing an Existing Class......Page 179
  Revising the__init__ Method......Page 180
  Modifying the Existing add Method......Page 181
  Exercises 6.1......Page 183
  Designing an AbstractBag Class......Page 184
  Modifying the Subclasses of AbstractBag......Page 186
  Generalizing the__add__ Method in AbstractBag......Page 187
  Integrating AbstractCollection into the Collection Hierarchy......Page 188
  Using Two Iterators in the__eq__ Method......Page 190
 Summary......Page 191
 Projects......Page 192
 Overview of Stacks......Page 194
 Using a Stack......Page 195
  The Stack Interface......Page 196
  Example Application: Matching Parentheses......Page 198
  Exercises 7.1......Page 200
  Evaluating Arithmetic Expressions......Page 201
  Evaluating Postfix Expressions......Page 202
  Exercises 7.2......Page 203
  Converting Infix to Postfix......Page 204
 Backtracking......Page 206
  Memory Management......Page 209
  Test Driver......Page 211
  Array Implementation......Page 213
  Linked Implementation......Page 215
  The Role of the Abstract Stack Class......Page 218
  Time and Space Analysis of the Two Implementations......Page 219
  Analysis......Page 220
  Design......Page 224
  Implementation......Page 227
 Review Questions......Page 230
 Projects......Page 231
 Overview of Queues......Page 234
 The Queue Interface and Its Use......Page 236
  Exercises 8.1......Page 238
  Simulations......Page 239
  Round-Robin CPU Scheduling......Page 241
 Implementations of Queues......Page 242
  A Linked Implementation of Queues......Page 243
  An Array Implementation......Page 244
 Case Study: Simulating a Supermarket Checkout Line......Page 247
  Analysis......Page 248
  Classes and Responsibilities......Page 249
 Priority Queues......Page 256
 Case Study: An Emergency Room Scheduler......Page 261
  Analysis......Page 262
  Classes......Page 263
  Design and Implementation......Page 264
 Summary......Page 266
 Review Questions......Page 267
 Projects......Page 268
 Overview of Lists......Page 270
  Index-Based Operations......Page 272
  Content-Based Operations......Page 273
  Position-Based Operations......Page 274
  Interfaces for Lists......Page 279
  Heap-Storage Management......Page 281
  Organization of Files on a Disk......Page 282
 List Implementations......Page 284
  The Role of the AbstractList Class......Page 285
  An Array-Based Implementation......Page 286
  A Linked Implementation......Page 288
  Time and Space Analysis for the Two Implementations......Page 291
  Role and Responsibilities of a List Iterator......Page 293
  Setting Up and Instantiating a List Iterator Class......Page 294
  The Navigational Methods in the List Iterator......Page 295
  The Mutator Methods in the List Iterator......Page 296
  Request......Page 298
  Analysis......Page 299
  Design......Page 300
  Implementation (Coding)......Page 303
 Review Questions......Page 304
 Projects......Page 305
 An Overview of Trees......Page 308
  Tree Terminology......Page 309
  General Trees and Binary Trees......Page 310
 Why Use a Tree?......Page 311
 The Shape of Binary Trees......Page 313
  Heaps......Page 316
  Binary Search Trees......Page 317
  Expression Trees......Page 318
  Preorder Traversal......Page 320
  Postorder Traversal......Page 321
 Developing a Binary Search Tree......Page 322
  The Binary Search Tree Interface......Page 323
  Data Structure for the Linked Implementation......Page 325
  Complexity Analysis of Binary Search Trees......Page 330
  Introduction to Grammars......Page 331
  Lexical Analysis and the Scanner......Page 334
  Parsing Strategies......Page 335
  Analysis......Page 336
  Design and Implementation of the Node Classes......Page 337
  Design and Implementation of the Parser Class......Page 339
 An Array Implementation of Binary Trees......Page 340
 Implementing Heaps......Page 342
 Summary......Page 346
 Review Questions......Page 347
 Projects......Page 348
 Using Sets......Page 350
 The Python set Class......Page 351
  A Sample Session with Sets......Page 352
  Relationship Between Sets and Dictionaries......Page 353
 Array-Based and Linked Implementations of Sets......Page 354
  The AbstractSet Class......Page 355
  The ArraySet Class......Page 356
 Using Dictionaries......Page 357
  The Item Class......Page 358
  The AbstractDict Class......Page 359
  The ArrayDict Class......Page 361
 Hashing Strategies......Page 363
  The Relationship of Collisions to Density......Page 364
  Hashing with Nonnumeric Keys......Page 366
  Linear Probing......Page 368
  Chaining......Page 370
  Complexity Analysis......Page 371
  Exercises 11.3......Page 372
  Analysis......Page 373
  Design......Page 375
  Implementation......Page 376
 Hashing Implementation of Sets......Page 378
 Hashing Implementation of Dictionaries......Page 381
  Exercises 11.4......Page 383
 Sorted Sets and Dictionaries......Page 384
 Review Questions......Page 385
 Projects......Page 387
 Graph Terminology......Page 388
  Exercises 12.1......Page 392
  Adjacency Matrix......Page 393
  Adjacency List......Page 395
  Analysis of the Two Representations......Page 396
  Exercises 12.2......Page 397
  A Generic Traversal Algorithm......Page 398
  Breadth-First and Depth-First Traversals......Page 399
  Graph Components......Page 401
  Spanning Trees and Forests......Page 402
  Algorithms for Minimum Spanning Trees......Page 403
 Topological Sort......Page 405
  The Initialization Step......Page 407
  The Computation Step......Page 409
  Exercises 12.4......Page 410
  Floyd’s Algorithm......Page 411
 Developing a Graph Collection......Page 412
  Example Use of the Graph Collection......Page 413
  The Class LinkedDirectedGraph......Page 414
  The Class LinkedVertex......Page 418
  The Class LinkedEdge......Page 420
  Analysis......Page 422
  The Classes GraphDemoView and GraphDemoModel......Page 423
  Implementation (Coding)......Page 424
 Summary......Page 428
 Review Questions......Page 429
 Projects......Page 431
Appendix A: Collection Framework for Python Programmers......Page 434
 A......Page 436
 B......Page 437
 C......Page 438
 E......Page 440
 G......Page 441
 I–J......Page 442
 L......Page 443
 M......Page 444
 P......Page 445
 S......Page 446
 T......Page 448
 W–Z......Page 449