You are previewing Data Structures and Algorithms Using Python.
O'Reilly logo
Data Structures and Algorithms Using Python

Book Description

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.

Table of Contents

  1. Copyright
  2. Preface
    1. Overview
    2. Prerequisites
    3. Contents and Organization
    4. Acknowledgments
  3. 1. Abstract Data Types
    1. 1.1. Introduction
      1. 1.1.1. Abstractions
      2. 1.1.2. Abstract Data Types
      3. 1.1.3. Data Structures
      4. 1.1.4. General Definitions
    2. 1.2. The Date Abstract Data Type
      1. 1.2.1. Defining the ADT
      2. 1.2.2. Using the ADT
      3. 1.2.3. Preconditions and Postconditions
      4. 1.2.4. Implementing the ADT
        1. 1.2.4.1. Date Representations
        2. 1.2.4.2. Constructing the Date
        3. 1.2.4.3. The Gregorian Date
        4. 1.2.4.4. Comparing Date Objects
    3. 1.3. Bags
      1. 1.3.1. The Bag Abstract Data Type
        1. 1.3.1.1. Examples
        2. 1.3.1.2. Why a Bag ADT?
      2. 1.3.2. Selecting a Data Structure
      3. 1.3.3. List-Based Implementation
    4. 1.4. Iterators
      1. 1.4.1. Designing an Iterator
      2. 1.4.2. Using Iterators
    5. 1.5. Application: Student Records
      1. 1.5.1. Designing a Solution
        1. 1.5.1.1. Creating the Report
        2. 1.5.1.2. Storage Class
      2. 1.5.2. Implementation
    6. 1.6. Exercises
    7. 1.7. Programming Projects
  4. 2. Arrays
    1. 2.1. The Array Structure
      1. 2.1.1. Why Study Arrays?
      2. 2.1.2. The Array Abstract Data Type
      3. 2.1.3. Implementing the Array
        1. 2.1.3.1. The ctypes Module
        2. 2.1.3.2. Creating a Hardware Array
        3. 2.1.3.3. The Class Definition
    2. 2.2. The Python List
      1. 2.2.1. Creating a Python List
      2. 2.2.2. Appending Items
      3. 2.2.3. Extending A List
      4. 2.2.4. Inserting Items
        1. 2.2.4.1. Removing Items
      5. 2.2.5. List Slice
    3. 2.3. Two-Dimensional Arrays
      1. 2.3.1. The Array2D Abstract Data Type
      2. 2.3.2. Implementing the 2-D Array
        1. 2.3.2.1. Basic Operations
        2. 2.3.2.2. Element Access
    4. 2.4. The Matrix Abstract Data Type
      1. 2.4.1. Matrix Operations
        1. 2.4.1.1. Addition and Subtraction.
        2. 2.4.1.2. Scaling
        3. 2.4.1.3. Multiplication
        4. 2.4.1.4. Transpose
      2. 2.4.2. Implementing the Matrix
    5. 2.5. Application: The Game of Life
      1. 2.5.1. Rules of the Game
      2. 2.5.2. Designing a Solution
      3. 2.5.3. Implementation
    6. 2.6. Exercises
    7. 2.7. Programming Projects
  5. 3. Sets and Maps
    1. 3.1. Sets
      1. 3.1.1. The Set Abstract Data Type
        1. 3.1.1.1. Example Use
      2. 3.1.2. Selecting a Data Structure
      3. 3.1.3. List-Based Implementation
        1. 3.1.3.1. Adding Elements
        2. 3.1.3.2. Comparing Two Sets
        3. 3.1.3.3. The Set Union
    2. 3.2. Maps
      1. 3.2.1. The Map Abstract Data Type
      2. 3.2.2. List-Based Implementation
    3. 3.3. Multi-Dimensional Arrays
      1. 3.3.1. The MultiArray Abstract Data Type
      2. 3.3.2. Data Organization
        1. 3.3.2.1. Array Storage
        2. 3.3.2.2. Index Computation
      3. 3.3.3. Variable-Length Arguments
      4. 3.3.4. Implementing the MultiArray
        1. 3.3.4.1. Constructor
        2. 3.3.4.2. Dimensionality and Lengths
        3. 3.3.4.3. Element Access
        4. 3.3.4.4. Computing the Offset
    4. 3.4. Application: Sales Reports
      1. 3.4.1.
        1. 3.4.1.1. Data Organization
        2. 3.4.1.2. Total Sales by Store
        3. 3.4.1.3. Total Sales by Month
        4. 3.4.1.4. Total Sales by Item
        5. 3.4.1.5. Monthly Sales by Store
    5. 3.5. Exercises
    6. 3.6. Programming Projects
  6. 4. Algorithm Analysis
    1. 4.1. Complexity Analysis
      1. 4.1.1. Big-O Notation
        1. 4.1.1.1. Defining Big-O
        2. 4.1.1.2. Constant of Proportionality
        3. 4.1.1.3. Constructing T(n)
        4. 4.1.1.4. Choosing the Function
        5. 4.1.1.5. Classes of Algorithms
      2. 4.1.2. Evaluating Python Code
        1. 4.1.2.1. Linear Time Examples
        2. 4.1.2.2. Quadratic Time Examples
        3. 4.1.2.3. Logarithmic Time Examples
        4. 4.1.2.4. Different Cases
    2. 4.2. Evaluating the Python List
      1. 4.2.1.
        1. 4.2.1.1. List Traversal
        2. 4.2.1.2. List Allocation
        3. 4.2.1.3. Appending to a List
        4. 4.2.1.4. Extending a List
        5. 4.2.1.5. Inserting and Removing Items
    3. 4.3. Amortized Cost
    4. 4.4. Evaluating the Set ADT
      1. 4.4.1.
        1. 4.4.1.1. Simple Operations
        2. 4.4.1.2. Operations of Two Sets
        3. 4.4.1.3. Set Union Operation
    5. 4.5. Application: The Sparse Matrix
      1. 4.5.1. List-Based Implementation
        1. 4.5.1.1. Constructor
        2. 4.5.1.2. Helper Method
        3. 4.5.1.3. Modifying an Element
        4. 4.5.1.4. Matrix Scaling
        5. 4.5.1.5. Matrix Addition
      2. 4.5.2. Efficiency Analysis
    6. 4.6. Exercises
    7. 4.7. Programming Projects
  7. 5. Searching and Sorting
    1. 5.1. Searching
      1. 5.1.1. The Linear Search
        1. 5.1.1.1. Finding a Specific Item
        2. 5.1.1.2. Searching a Sorted Sequence
        3. 5.1.1.3. Finding the Smallest Value
      2. 5.1.2. The Binary Search
        1. 5.1.2.1. Algorithm Description
        2. 5.1.2.2. Implementation
        3. 5.1.2.3. Run Time Analysis
    2. 5.2. Sorting
      1. 5.2.1. Bubble Sort
      2. 5.2.2. Selection Sort
      3. 5.2.3. Insertion Sort
    3. 5.3. Working with Sorted Lists
      1. 5.3.1. Maintaining a Sorted List
      2. 5.3.2. Merging Sorted Lists
        1. 5.3.2.1. Problem Solution
        2. 5.3.2.2. Run Time Analysis
    4. 5.4. The Set ADT Revisited
      1. 5.4.1. A Sorted List Implementation
        1. 5.4.1.1. Basic Operations
        2. 5.4.1.2. A New Set Equals
        3. 5.4.1.3. A New Set Union
      2. 5.4.2. Comparing the Implementations
    5. 5.5. Exercises
    6. 5.6. Programming Projects
  8. 6. Linked Structures
    1. 6.1. Introduction
    2. 6.2. The Singly Linked List
      1. 6.2.1. Traversing the Nodes
      2. 6.2.2. Searching for a Node
      3. 6.2.3. Prepending Nodes
      4. 6.2.4. Removing Nodes
    3. 6.3. The Bag ADT Revisited
      1. 6.3.1. A Linked List Implementation
      2. 6.3.2. Comparing Implementations
      3. 6.3.3. Linked List Iterators
    4. 6.4. More Ways to Build a Linked List
      1. 6.4.1. Using a Tail Reference
        1. 6.4.1.1. Appending Nodes
        2. 6.4.1.2. Removing Nodes
      2. 6.4.2. The Sorted Linked List
        1. 6.4.2.1. Linear Search
        2. 6.4.2.2. Inserting Nodes
        3. 6.4.2.3. Traversing and Deleting
    5. 6.5. The Sparse Matrix Revisited
      1. 6.5.1. An Array of Linked Lists Implementation
        1. 6.5.1.1. Changing Element Values
        2. 6.5.1.2. Matrix Scaling
        3. 6.5.1.3. Matrix Addition
      2. 6.5.2. Comparing the Implementations
    6. 6.6. Application: Polynomials
      1. 6.6.1. Polynomial Operations
        1. 6.6.1.1. Addition
        2. 6.6.1.2. Multiplication
        3. 6.6.1.3. Evaluation
      2. 6.6.2. The Polynomial ADT
      3. 6.6.3. Implementation
        1. 6.6.3.1. Linked List Structure
        2. 6.6.3.2. Basic Operations
        3. 6.6.3.3. Appending Terms
        4. 6.6.3.4. Polynomial Addition
        5. 6.6.3.5. Multiplication
    7. 6.7. Exercises
    8. 6.8. Programming Projects
  9. 7. Stacks
    1. 7.1. The Stack ADT
    2. 7.2. Implementing the Stack
      1. 7.2.1. Using a Python List
      2. 7.2.2. Using a Linked List
    3. 7.3. Stack Applications
      1. 7.3.1. Balanced Delimiters
      2. 7.3.2. Evaluating Postfix Expressions
        1. 7.3.2.1. Converting from Infix to Postfix
        2. 7.3.2.2. Postfix Evaluation Algorithm
    4. 7.4. Application: Solving a Maze
      1. 7.4.1. Backtracking
      2. 7.4.2. Designing a Solution
        1. 7.4.2.1. Problem Details
        2. 7.4.2.2. Describing the Algorithm
      3. 7.4.3. The Maze ADT
        1. 7.4.3.1. Example Use
        2. 7.4.3.2. Maze Text File Format
      4. 7.4.4. Implementation
        1. 7.4.4.1. Class Definition
        2. 7.4.4.2. Maze Components
        3. 7.4.4.3. Helper Methods
        4. 7.4.4.4. Finding the Path
    5. 7.5. Exercises
    6. 7.6. Programming Projects
  10. 8. Queues
    1. 8.1. The Queue ADT
    2. 8.2. Implementing the Queue
      1. 8.2.1. Using a Python List
      2. 8.2.2. Using a Circular Array
        1. 8.2.2.1. Data Organization
        2. 8.2.2.2. Queue Implementation
        3. 8.2.2.3. Run Time Analysis
      3. 8.2.3. Using a Linked List
    3. 8.3. Priority Queues
      1. 8.3.1. The Priority Queue ADT
      2. 8.3.2. Implementation: Unbounded Priority Queue
        1. 8.3.2.1. Python List Implementation
        2. 8.3.2.2. Linked List Implementation
      3. 8.3.3. Implementation: Bounded Priority Queue
    4. 8.4. Application: Computer Simulations
      1. 8.4.1. Airline Ticket Counter
        1. 8.4.1.1. Queuing System Model
        2. 8.4.1.2. Random Events
      2. 8.4.2. Implementation
        1. 8.4.2.1. System Parameters
        2. 8.4.2.2. Passenger Class
        3. 8.4.2.3. Ticket Agent Class
        4. 8.4.2.4. Simulation Class
    5. 8.5. Exercises
    6. 8.6. Programming Projects
  11. 9. Advanced Linked Lists
    1. 9.1. The Doubly Linked List
      1. 9.1.1. Organization
      2. 9.1.2. List Operations
        1. 9.1.2.1. Traversals
        2. 9.1.2.2. Searching
        3. 9.1.2.3. Adding Nodes
        4. 9.1.2.4. Removing Nodes
    2. 9.2. The Circular Linked List
      1. 9.2.1. Organization
      2. 9.2.2. List Operations
        1. 9.2.2.1. Traversals
        2. 9.2.2.2. Searching
        3. 9.2.2.3. Adding Nodes
        4. 9.2.2.4. Removing Nodes
    3. 9.3. Multi-Linked Lists
      1. 9.3.1. Multiple Chains
      2. 9.3.2. The Sparse Matrix
    4. 9.4. Complex Iterators
    5. 9.5. Application: Text Editor
      1. 9.5.1. Typical Editor Operations
        1. 9.5.1.1. Layout
        2. 9.5.1.2. Text Cursor
        3. 9.5.1.3. Inserting Text
        4. 9.5.1.4. Deleting Text
      2. 9.5.2. The Edit Buffer ADT
      3. 9.5.3. Implementation
        1. 9.5.3.1. Constructor
        2. 9.5.3.2. Cursor Movement
        3. 9.5.3.3. Modifying the Buffer
        4. 9.5.3.4. Splitting a Line
    6. 9.6. Exercises
    7. 9.7. Programming Projects
  12. 10. Recursion
    1. 10.1. Recursive Functions
    2. 10.2. Properties of Recursion
      1. 10.2.1. Factorials
      2. 10.2.2. Recursive Call Trees
      3. 10.2.3. The Fibonacci Sequence
    3. 10.3. How Recursion Works
      1. 10.3.1. The Run Time Stack
      2. 10.3.2. Using a Software Stack
      3. 10.3.3. Tail Recursion
    4. 10.4. Recursive Applications
      1. 10.4.1. Recursive Binary Search
      2. 10.4.2. Towers of Hanoi
      3. 10.4.3. Exponential Operation
      4. 10.4.4. Playing Tic-Tac-Toe
    5. 10.5. Application: The Eight-Queens Problem
      1. 10.5.1. Solving for Four-Queens
      2. 10.5.2. Designing a Solution
        1. 10.5.2.1. The Board Definition
        2. 10.5.2.2. Using the ADT
        3. 10.5.2.3. Implementing the ADT
    6. 10.6. Exercises
    7. 10.7. Programming Projects
  13. 11. Hash Tables
    1. 11.1. Introduction
    2. 11.2. Hashing
      1. 11.2.1. Linear Probing
        1. 11.2.1.1. Searching
        2. 11.2.1.2. Deletions
      2. 11.2.2. Clustering
        1. 11.2.2.1. Modified Linear Probe
        2. 11.2.2.2. Quadratic Probing
        3. 11.2.2.3. Double Hashing
      3. 11.2.3. Rehashing
      4. 11.2.4. Efficiency Analysis
    3. 11.3. Separate Chaining
    4. 11.4. Hash Functions
      1. 11.4.1.
        1. 11.4.1.1. Division
        2. 11.4.1.2. Truncation
        3. 11.4.1.3. Folding
        4. 11.4.1.4. Hashing Strings
    5. 11.5. The HashMap Abstract Data Type
      1. 11.5.1.
        1. 11.5.1.1. The Hash Table
        2. 11.5.1.2. Hash Functions
        3. 11.5.1.3. Searching
        4. 11.5.1.4. Insertions
        5. 11.5.1.5. Rehashing
    6. 11.6. Application: Histograms
      1. 11.6.1. The Histogram Abstract Data Type
        1. 11.6.1.1. Building a Histogram
        2. 11.6.1.2. Implementation
      2. 11.6.2. The Color Histogram
    7. 11.7. Exercises
    8. 11.8. Programming Projects
  14. 12. Advanced Sorting
    1. 12.1. Merge Sort
      1. 12.1.1. Algorithm Description
      2. 12.1.2. Basic Implementation
      3. 12.1.3. Improved Implementation
      4. 12.1.4. Efficiency Analysis
    2. 12.2. Quick Sort
      1. 12.2.1. Algorithm Description
      2. 12.2.2. Implementation
      3. 12.2.3. Efficiency Analysis
    3. 12.3. How Fast Can We Sort?
    4. 12.4. Radix Sort
      1. 12.4.1. Algorithm Description
      2. 12.4.2. Basic Implementation
      3. 12.4.3. Efficiency Analysis
    5. 12.5. Sorting Linked Lists
      1. 12.5.1. Insertion Sort
      2. 12.5.2. Merge Sort
        1. 12.5.2.1. Splitting the List
        2. 12.5.2.2. Merging the Lists
    6. 12.6. Exercises
    7. 12.7. Programming Projects
  15. 13. Binary Trees
    1. 13.1. The Tree Structure
      1. 13.1.1.
        1. 13.1.1.1. Root
        2. 13.1.1.2. Path
        3. 13.1.1.3. Parent
        4. 13.1.1.4. Children
        5. 13.1.1.5. Nodes
        6. 13.1.1.6. Relatives
    2. 13.2. The Binary Tree
      1. 13.2.1. Properties
        1. 13.2.1.1. Tree Size
        2. 13.2.1.2. Tree Structure
      2. 13.2.2. Implementation
      3. 13.2.3. Tree Traversals
        1. 13.2.3.1. Preorder Traversal
        2. 13.2.3.2. Inorder Traversal
        3. 13.2.3.3. Postorder Traversal
        4. 13.2.3.4. Breadth-First Traversal
    3. 13.3. Expression Trees
      1. 13.3.1. Expression Tree Abstract Data Type
      2. 13.3.2. String Representation
      3. 13.3.3. Tree Evaluation
      4. 13.3.4. Tree Construction
    4. 13.4. Heaps
      1. 13.4.1. Definition
        1. 13.4.1.1. Insertions
        2. 13.4.1.2. Extractions
      2. 13.4.2. Implementation
        1. 13.4.2.1. Node Access
        2. 13.4.2.2. Class Definition
        3. 13.4.2.3. Analysis
      3. 13.4.3. The Priority Queue Revisited
    5. 13.5. Heapsort
      1. 13.5.1. Simple Implementation
      2. 13.5.2. Sorting In Place
    6. 13.6. Application: Morse Code
      1. 13.6.1. Decision Trees
      2. 13.6.2. The ADT Definition
    7. 13.7. Exercises
    8. 13.8. Programming Projects
  16. 14. Search Trees
    1. 14.1. The Binary Search Tree
      1. 14.1.1. Searching
      2. 14.1.2. Min and Max Values
      3. 14.1.3. Insertions
      4. 14.1.4. Deletions
        1. 14.1.4.1. Removing a Leaf Node
        2. 14.1.4.2. Removing an Interior Node with One Child
        3. 14.1.4.3. Removing an Interior Node with Two Children
      5. 14.1.5. Efficiency of Binary Search Trees
    2. 14.2. Search Tree Iterators
    3. 14.3. AVL Trees
      1. 14.3.1. Insertions
        1. 14.3.1.1. Rotations
        2. 14.3.1.2. New Balance Factors
      2. 14.3.2. Deletions
      3. 14.3.3. Implementation
    4. 14.4. The 2-3 Tree
      1. 14.4.1. Searching
      2. 14.4.2. Insertions
        1. 14.4.2.1. Splitting a Leaf Node
        2. 14.4.2.2. Splitting a Parent Node
        3. 14.4.2.3. Splitting the Root Node
        4. 14.4.2.4. Implementation
      3. 14.4.3. Efficiency of the 2–3 Tree
    5. 14.5. Exercises
    6. 14.6. Programming Projects
  17. A. Python Review
    1. A.1. The Python Interpreter
    2. A.2. The Basics of Python
      1. A.2.1. Primitive Types
      2. A.2.2. Statements
      3. A.2.3. Variables
        1. A.2.3.1. Assignments
        2. A.2.3.2. Aliases
        3. A.2.3.3. Null References
        4. A.2.3.4. Constants
      4. A.2.4. Arithmetic Operators
      5. A.2.5. Logical Expressions
        1. A.2.5.1. Relational Operators
        2. A.2.5.2. Boolean Operators
        3. A.2.5.3. Object References
      6. A.2.6. Using Functions and Methods
      7. A.2.7. Standard Library
    3. A.3. User Interaction
      1. A.3.1. Standard Input
      2. A.3.2. Standard Output
        1. A.3.2.1. Escape Sequences
        2. A.3.2.2. Formatted Output
    4. A.4. Control Structures
      1. A.4.1. Selection Constructs
        1. A.4.1.1. The If-Else Statement
        2. A.4.1.2. Nested If Statements
        3. A.4.1.3. Multiway Branching
      2. A.4.2. Repetition Constructs
        1. A.4.2.1. The While Loop
        2. A.4.2.2. The For Loop
    5. A.5. Collections
      1. A.5.1. Strings
      2. A.5.2. Lists
        1. A.5.2.1. Element Access
        2. A.5.2.2. List Modification
        3. A.5.2.3. Searching the List
      3. A.5.3. Tuples
      4. A.5.4. Dictionaries
        1. A.5.4.1. Element Access
        2. A.5.4.2. Dictionary Modification
    6. A.6. Text Files
      1. A.6.1. File Access
      2. A.6.2. Writing to Files
      3. A.6.3. Reading from Files
    7. A.7. User-Defined Functions
      1. A.7.1. The Function Definition
        1. A.7.1.1. Function Arguments
        2. A.7.1.2. Returning Values
        3. A.7.1.3. Default and Keyword Arguments
      2. A.7.2. Variable Scope
      3. A.7.3. Main Routine
  18. B. User-Defined Modules
    1. B.1. Structured Programs
    2. B.2. Namespaces
  19. C. Exceptions
    1. C.1. Catching Exceptions
    2. C.2. Raising Exceptions
    3. C.3. Standard Exceptions
    4. C.4. Assertions
  20. D. Classes
    1. D.1. The Class Definition
      1. D.1.1. Constructors
        1. D.1.1.1. Data Attributes
        2. D.1.1.2. Object Instantiation
        3. D.1.1.3. The self Reference
      2. D.1.2. Operations
      3. D.1.3. Using Modules
      4. D.1.4. Hiding Attributes
    2. D.2. Overloading Operators
    3. D.3. Inheritance
      1. D.3.1. Deriving Child Classes
      2. D.3.2. Creating Class Instances
      3. D.3.3. Invoking Methods
    4. D.4. Polymorphism
  21. Bibliography