Data structures and algorithms using Python

Все больше и больше программистов обращаются к языку Python, и эта книга даст им понимание того, что им нужно. Автор представляет основную структуру массива и исследует основы реализации и использовании многомерных массивов. Изложены основные механизмы, многие структуры и конструкции из встроенных даннёых языка Python. Чтобы понять, как вводятся новые структуры данных Число АТД и приложений, рассматриваются как потоки на протяжении всей книги,. Также представлены реальные приложения. Это дает программистам полный охват основных структур данных и алгоритмов в языке Python.More and more programmers are turning to Python and this book will give them the understanding they need. Necaise introduces the basic array structure and explores the fundamentals of implementing and using multi-dimensional arrays. The underlying mechanisms of many of Python’s built-in data structures and constructs are covered. A number of ADTs and applications are discussed as threads throughout the book to allow for multiple implementations as new data structures are introduced. Real-world applications of the various chapter topics are also presented. This gives programmers complete coverage of abstraction and the basic data structures and algorithms in the Python language.This book is designed for a data structures and algorithms course that uses Python. A key objective is to provide a «back to basics» approach to learning data structures and algorithms without overwhelming the reader with all of the object-oriented programming terminology and concepts. To provide flexibility in topic coverage for a wide variety of courses, the author focuses on data structures and algorithms, while designing the examples to allow the introduction of object-oriented programming if so desired. The book also introduces the concept of algorithm analysis and explores the efficiency of algorithms and data structures throughout the text.Provides complete coverage of abstraction and the basic data structures and algorithms using a «back to basics» approach.Python (version 3) used to design and implement classes for abstract data types and programs and algorithms.Flexible organziation allows coverage of class inheritance as needed or desired.Introduces students to the basic array structure and the fundamentals of implementing and using multi-dimensional arrays.The underlying mechanism of many of Pythons built-in data structures and constructs are explored in order to expose the «magic» and to evaluate their efficiency.Sample applications of various chapter topics are presented throughout the text to help engage students.A number of ADTs and applications are presented as threads throughout the text (i.e. the Set, Bag, Matrix, Sparse Matrix, and Map ADTs.) This allows for multiple implementations as new data structures are introduced, which provides the opportunity to reinforce the abstraction concept and for studying algorithm efficiency. Cover Title Page Copyright Contents Preface Chapter 1: Abstract Data Types 1.1 Introduction 1.1.1 Abstractions 1.1.2 Abstract Data Types 1.1.3 Data Structures 1.1.4 General Definitions 1.2 The Date Abstract Data Type 1.2.1 Defining the ADT 1.2.2 Using the ADT 1.2.3 Preconditions and Postconditions 1.2.4 Implementing the ADT 1.3 Bags 1.3.1 The Bag Abstract Data Type 1.3.2 Selecting a Data Structure 1.3.3 List-Based Implementation 1.4 Iterators 1.4.1 Designing an Iterator 1.4.2 Using Iterators 1.5 Application: Student Records 1.5.1 Designing a Solution 1.5.2 Implementation Exercises Programming Projects Chapter 2: Arrays 2.1 The Array Structure 2.1.1 Why Study Arrays? 2.1.2 The Array Abstract Data Type 2.1.3 Implementing the Array 2.2 The Python List 2.2.1 Creating a Python List 2.2.2 Appending Items 2.2.3 Extending A List 2.2.4 Inserting Items 2.2.5 List Slice 2.3 Two-Dimensional Arrays 2.3.1 The Array2D Abstract Data Type 2.3.2 Implementing the 2-D Array 2.4 The Matrix Abstract Data Type 2.4.1 Matrix Operations 2.4.2 Implementing the Matrix 2.5 Application: The Game of Life 2.5.1 Rules of the Game 2.5.2 Designing a Solution 2.5.3 Implementation Exercises Programming Projects Chapter 3: Sets and Maps 3.1 Sets 3.1.1 The Set Abstract Data Type 3.1.2 Selecting a Data Structure 3.1.3 List-Based Implementation 3.2 Maps 3.2.1 The Map Abstract Data Type 3.2.2 List-Based Implementation 3.3 Multi-Dimensional Arrays 3.3.1 The MultiArray Abstract Data Type 3.3.2 Data Organization 3.3.3 Variable-Length Arguments 3.3.4 Implementing the MultiArray 3.4 Application: Sales Reports Exercises Programming Projects Chapter 4: Algorithm Analysis 4.1 Complexity Analysis 4.1.1 Big-O Notation 4.1.2 Evaluating Python Code 4.2 Evaluating the Python List 4.3 Amortized Cost 4.4 Evaluating the Set ADT 4.5 Application: The Sparse Matrix 4.5.1 List-Based Implementation 4.5.2 Efficiency Analysis Exercises Programming Projects Chapter 5: Searching and Sorting 5.1 Searching 5.1.1 The Linear Search 5.1.2 The Binary Search 5.2 Sorting 5.2.1 Bubble Sort 5.2.2 Selection Sort 5.2.3 Insertion Sort 5.3 Working with Sorted Lists 5.3.1 Maintaining a Sorted List 5.3.2 Merging Sorted Lists 5.4 The Set ADT Revisited 5.4.1 A Sorted List Implementation 5.4.2 Comparing the Implementations Exercises Programming Projects Chapter 6: Linked Structures 6.1 Introduction 6.2 The Singly Linked List 6.2.1 Traversing the Nodes 6.2.2 Searching for a Node 6.2.3 Prepending Nodes 6.2.4 Removing Nodes 6.3 The Bag ADT Revisited 6.3.1 A Linked List Implementation 6.3.2 Comparing Implementations 6.3.3 Linked List Iterators 6.4 More Ways to Build a Linked List 6.4.1 Using a Tail Reference 6.4.2 The Sorted Linked List 6.5 The Sparse Matrix Revisited 6.5.1 An Array of Linked Lists Implementation 6.5.2 Comparing the Implementations 6.6 Application: Polynomials 6.6.1 Polynomial Operations 6.6.2 The Polynomial ADT 6.6.3 Implementation Exercises Programming Projects Chapter 7: Stacks 7.1 The Stack ADT 7.2 Implementing the Stack 7.2.1 Using a Python List 7.2.2 Using a Linked List 7.3 Stack Applications 7.3.1 Balanced Delimiters 7.3.2 Evaluating Postfix Expressions 7.4 Application: Solving a Maze 7.4.1 Backtracking 7.4.2 Designing a Solution 7.4.3 The Maze ADT 7.4.4 Implementation Exercises Programming Projects Chapter 8: Queues 8.1 The Queue ADT 8.2 Implementing the Queue 8.2.1 Using a Python List 8.2.2 Using a Circular Array 8.2.3 Using a Linked List 8.3 Priority Queues 8.3.1 The Priority Queue ADT 8.3.2 Implementation: Unbounded Priority Queue 8.3.3 Implementation: Bounded Priority Queue 8.4 Application: Computer Simulations 8.4.1 Airline Ticket Counter 8.4.2 Implementation Exercises Programming Projects Chapter 9: Advanced Linked Lists 9.1 The Doubly Linked List 9.1.1 Organization 9.1.2 List Operations 9.2 The Circular Linked List 9.2.1 Organization 9.2.2 List Operations 9.3 Multi-Linked Lists 9.3.1 Multiple Chains 9.3.2 The Sparse Matrix 9.4 Complex Iterators 9.5 Application: Text Editor 9.5.1 Typical Editor Operations 9.5.2 The Edit Buffer ADT 9.5.3 Implementation Exercises Programming Projects Chapter 10: Recursion 10.1 Recursive Functions 10.2 Properties of Recursion 10.2.1 Factorials 10.2.2 Recursive Call Trees 10.2.3 The Fibonacci Sequence 10.3 How Recursion Works 10.3.1 The Run Time Stack 10.3.2 Using a Software Stack 10.3.3 Tail Recursion 10.4 Recursive Applications 10.4.1 Recursive Binary Search 10.4.2 Towers of Hanoi 10.4.3 Exponential Operation 10.4.4 Playing Tic-Tac-Toe 10.5 Application: The Eight-Queens Problem 10.5.1 Solving for Four-Queens 10.5.2 Designing a Solution Exercises Programming Projects Chapter 11: Hash Tables 11.1 Introduction 11.2 Hashing 11.2.1 Linear Probing 11.2.2 Clustering 11.2.3 Rehashing 11.2.4 Efficiency Analysis 11.3 Separate Chaining 11.4 Hash Functions 11.5 The HashMap Abstract Data Type 11.6 Application: Histograms 11.6.1 The Histogram Abstract Data Type 11.6.2 The Color Histogram Exercises Programming Projects Chapter 12: Advanced Sorting 12.1 Merge Sort 12.1.1 Algorithm Description 12.1.2 Basic Implementation 12.1.3 Improved Implementation 12.1.4 Efficiency Analysis 12.2 Quick Sort 12.2.1 Algorithm Description 12.2.2 Implementation 12.2.3 Efficiency Analysis 12.3 How Fast Can We Sort? 12.4 Radix Sort 12.4.1 Algorithm Description 12.4.2 Basic Implementation 12.4.3 Efficiency Analysis 12.5 Sorting Linked Lists 12.5.1 Insertion Sort 12.5.2 Merge Sort Exercises Programming Projects Chapter 13: Binary Trees 13.1 The Tree Structure 13.2 The Binary Tree 13.2.1 Properties 13.2.2 Implementation 13.2.3 Tree Traversals 13.3 Expression Trees 13.3.1 Expression Tree Abstract Data Type 13.3.2 String Representation 13.3.3 Tree Evaluation 13.3.4 Tree Construction 13.4 Heaps 13.4.1 Definition 13.4.2 Implementation 13.4.3 The Priority Queue Revisited 13.5 Heapsort 13.5.1 Simple Implementation 13.5.2 Sorting In Place 13.6 Application: Morse Code 13.6.1 Decision Trees 13.6.2 The ADT Definition Exercises Programming Projects Chapter 14: Search Trees 14.1 The Binary Search Tree 14.1.1 Searching 14.1.2 Min and Max Values 14.1.3 Insertions 14.1.4 Deletions 14.1.5 Efficiency of Binary Search Trees 14.2 Search Tree Iterators 14.3 AVL Trees 14.3.1 Insertions 14.3.2 Deletions 14.3.3 Implementation 14.4 The 2-3 Tree 14.4.1 Searching 14.4.2 Insertions 14.4.3 Efficiency of the 2-3 Tree Exercises Programming Projects Appendix A: Python Review A.1 The Python Interpreter A.2 The Basics of Python A.2.1 Primitive Types A.2.2 Statements A.2.3 Variables A.2.4 Arithmetic Operators A.2.5 Logical Expressions A.2.6 Using Functions and Methods A.2.7 Standard Library A.3 User Interaction A.3.1 Standard Input A.3.2 Standard Output A.4 Control Structures A.4.1 Selection Constructs A.4.2 Repetition Constructs A.5 Collections A.5.1 Strings A.5.2 Lists A.5.3 Tuples A.5.4 Dictionaries A.6 Text Files A.6.1 File Access A.6.2 Writing to Files A.6.3 Reading from Files A.7 User-Defined Functions A.7.1 The Function Definition A.7.2 Variable Scope A.7.3 Main Routine Appendix B: User-Defined Modules B.1 Structured Programs B.2 Namespaces Appendix C: Exceptions C.1 Catching Exceptions C.2 Raising Exceptions C.3 Standard Exceptions C.4 Assertions Appendix D: Classes D.1 The Class Definition D.1.1 Constructors D.1.2 Operations D.1.3 Using Modules D.1.4 Hiding Attributes D.2 Overloading Operators D.3 Inheritance D.3.1 Deriving Child Classes D.3.2 Creating Class Instances D.3.3 Invoking Methods D.4 Polymorphism Bibliography Index