دانلود کتاب 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