Data Structures & Algorithms in Python
Häftad, Engelska, 2022
579 kr
Beställningsvara. Skickas inom 7-10 vardagar
Fri frakt för medlemmar vid köp för minst 249 kr.LEARN HOW TO USE DATA STRUCTURES IN WRITING HIGH PERFORMANCE PYTHON PROGRAMS AND ALGORITHMS
This practical introduction to data structures and algorithms can help every programmer who wants to write more efficient software. Building on Robert Lafore's legendary Java-based guide, this book helps you understand exactly how data structures and algorithms operate. You'll learn how to efficiently apply them with the enormously popular Python language and scale your code to handle today's big data challenges.
Throughout, the authors focus on real-world examples, communicate key ideas with intuitive, interactive visualizations, and limit complexity and math to what you need to improve performance. Step-by-step, they introduce arrays, sorting, stacks, queues, linked lists, recursion, binary trees, 2-3-4 trees, hash tables, spatial data structures, graphs, and more. Their code examples and illustrations are so clear, you can understand them even if you're a near-beginner, or your experience is with other procedural or object-oriented languages.
- Build core computer science skills that take you beyond merely “writing code”
- Learn how data structures make programs (and programmers) more efficient
- See how data organization and algorithms affect how much you can do with today's, and tomorrow's, computing resources
- Develop data structure implementation skills you can use in any language
- Choose the best data structure(s) and algorithms for each programming problem—and recognize which ones to avoid
Data Structures & Algorithms in Python is packed with examples, review questions, individual and team exercises, thought experiments, and longer programming projects. It's ideal for both self-study and classroom settings, and either as a primary text or as a complement to a more formal presentation.
Produktinformation
- Utgivningsdatum2022-10-18
- Mått183 x 235 x 37 mm
- Vikt1 338 g
- FormatHäftad
- SpråkEngelska
- SerieDeveloper's Library
- Antal sidor928
- Upplaga1
- FörlagPearson Education
- ISBN9780134855684
Tillhör följande kategorier
Dr. John Canning is an engineer, computer scientist, and researcher. He earned an S.B. degree in electrical engineering from the Massachusetts Institute of Technology and a Ph.D. in Computer Science from the University of Maryland at College Park. His varied professions include being a professor of computer science, a researcher and software engineer in industry, and a company vice president. He now is president of Shakumant Software.Alan Broder is clinical professor and chair of the Department of Computer Science at Stern College for Women of Yeshiva University in New York City. He teaches introductory and advanced courses in Python programming, data structures, and data science. Before joining Stern College, he was a software engineer, designing and building large-scale data analysis systems. He founded and led White Oak Technologies, Inc. as its CEO, and later served as the chairman and fellow of its successor company, Novetta, in Fairfax, Virginia.Robert Lafore has degrees in Electrical Engineering and Mathematics, has worked as a systems analyst for the Lawrence Berkeley Laboratory, founded his own software company, and is a best-selling writer in the field of computer programming. Some of his titles are Object-Oriented Programming in C++ and Data Structures and Algorithms in Java.
- 1 Overview . . . 1 What Are Data Structures and Algorithms?. . . . . . . . . . . . . . . . . . . . . . . 1Overview of Data Structures.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4Overview of Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6Some Definitions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6Programming in Python.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8Object-Oriented Programming.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282 Arrays . . . 29The Array Visualization Tool.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30Using Python Lists to Implement the Array Class.. . . . . . . . . . . . . . . . . 37The OrderedArray Visualization Tool.. . . . . . . . . . . . . . . . . . . . . . . . . . 47Binary Search.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48Python Code for an OrderedArray Class.. . . . . . . . . . . . . . . . . . . . . . . . 52Logarithms.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58Storing Objects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60Big O Notation.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65Why Not Use Arrays for Everything?.. . . . . . . . . . . . . . . . . . . . . . . . . . 69Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 733 Simple Sorting . . . 75How Would You Do It?.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76Bubble Sort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77Selection Sort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83Insertion Sort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87Comparing the Simple Sorts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1014 Stacks and Queues . . . 103Different Structures for Different Use Cases.. . . . . . . . . . . . . . . . . . . . . 103Stacks.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104Queues. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116Priority Queues.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126Parsing Arithmetic Expressions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1555 Linked Lists . . . 157Links.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158The LinkedList Visualization Tool.. . . . . . . . . . . . . . . . . . . . . . . . . . . . 164A Simple Linked List.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167Double-Ended Lists.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177Linked List Efficiency.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183Abstract Data Types and Objects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184Ordered Lists.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192Doubly Linked Lists.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198Insertion and Deletion at the Ends.. . . . . . . . . . . . . . . . . . . . . . . 201Insertion and Deletion in the Middle.. . . . . . . . . . . . . . . . . . . . . 204Doubly Linked List as Basis for Deques.. . . . . . . . . . . . . . . . . . . . 208Circular Lists.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209Iterators.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2276 Recursion . . . 229Triangular Numbers.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230Factorials. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237Anagrams.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239A Recursive Binary Search.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242The Tower of Hanoi.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245Sorting with mergesort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255Eliminating Recursion.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267Some Interesting Recursive Applications.. . . . . . . . . . . . . . . . . . . . . . . 275Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2837 Advanced Sorting . . . 285 Shellsort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285Partitioning.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294Quicksort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302Radix Sort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320Timsort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3328 Binary Trees . . . 335 Why Use Binary Trees?.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335Tree Terminology.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337An Analogy.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340How Do Binary Search Trees Work?.. . . . . . . . . . . . . . . . . . . . . . . . . . 341Finding a Node.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346Inserting a Node.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350Traversing the Tree.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353Finding Minimum and Maximum Key Values. . . . . . . . . . . . . . . . . . . 365Deleting a Node.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366The Efficiency of Binary Search Trees.. . . . . . . . . . . . . . . . . . . . . . . . . 375Trees Represented as Arrays.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377Printing Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379Duplicate Keys.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381The BinarySearchTreeTester.py Program. . . . . . . . . . . . . . . . . . . . . . . . 382The Huffman Code.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3979 2-3-4 Trees and External Storage . . . 401Introduction to 2-3-4 Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401The Tree234 Visualization Tool. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408Python Code for a 2-3-4 Tree.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412Efficiency of 2-3-4 Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4302-3 Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432External Storage.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46010 AVL and Red-Black Trees 463 Our Approach to the Discussion.. . . 463Balanced and Unbalanced Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464AVL Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470The Efficiency of AVL Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486Red-Black Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487Using the Red-Black Tree Visualization Tool.. . . . . . . . . . . . . . . . . . . . 489Experimenting with the Visualization Tool.. . . . . . . . . . . . . . . . . . . . . 492Rotations in Red-Black Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497Inserting a New Node.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498Deletion.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 508The Efficiency of Red-Black Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . 5092-3-4 Trees and Red-Black Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 510Red-Black Tree Implementation.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 520Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52111 Hash Tables 525 Introduction to Hashing.. . . . . . . . . . . . . . . . . 526Open Addressing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 536Separate Chaining.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565Hash Functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575Hashing Efficiency.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 581Hashing and External Storage.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 588Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 590Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 592Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59512 Spatial Data Structures 597 Spatial Data.. . . . . .. . . . . . . . . . . . 597 Computing Distances Between Points.. . . . . . . . . . . . . . . . . . . . . . . . . 599Circles and Bounding Boxes.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 601Searching Spatial Data.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 611Lists of Points.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612Grids.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 617Quadtrees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633Theoretical Performance and Optimizations.. . . . . . . . . . . . . . . . . . . . 656Practical Considerations.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 656Further Extensions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 658Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 659Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 661Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 662Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66313 Heaps 665 Introduction to Heaps.. . . . . . . . . . . . . . . . . . . .. . . . . 666 The Heap Visualization Tool.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 674Python Code for Heaps.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 677A Tree-Based Heap. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 684Heapsort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 686Order Statistics.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 694Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 700Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 701Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 703Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70314 Graphs 705 Introduction to Graphs.. . . . . . . . . . . . . . . . . . . . . . . 705 Traversal and Search.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 718Minimum Spanning Trees.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 734Topological Sorting.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 740Connectivity in Directed Graphs.. . . . . . . . . . . . . . . . . . . . . . . . . . . . 753Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 759Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 760Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 762Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76315 Weighted Graphs . . . 767 Minimum Spanning Tree with Weighted Graphs.. . . . . . . . . . . . . . . . . 767The All-Pairs Shortest-Path Problem.. . . . . . . . . . . . . . . . . . . . . . . . . . 797Efficiency.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 800Intractable Problems.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 801Summary.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 805Questions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 806Experiments.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 808Programming Projects.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80916 What to Use and Why 813 Analyzing the Problem.. . . . . . . . . . . 814Foundational Data Structures.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 818Special-Ordering Data Structures.. . . . . . . . . . . . . . . . . . . . . . . . . . . . 824Sorting.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 826Specialty Data Structures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 828External Storage.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 829Onward. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 831A Running the Visualizations . . . 833 B Further Reading . . . 841 C Answers to Questions . . . 8459780134855684, TOC, 8/3/2022
Hoppa över listan