【数据结构】电子书 - Data Structures and Algorithms in Python [Goodrich, Tamassia & Goldwasser 2013-03-18]

书籍目录

Cover

Title Page

Copyright Page

Preface

Contents

1 Python Primer

1.1 Python Overview

1.1.1 The Python Interpreter

1.1.2 Preview of a Python Program

1.2 Objects in Python

1.2.1 Identifiers, Objects, and the Assignment Statement

1.2.2 Creating and Using Objects

1.2.3 Python’s Built-In Classes

1.3 Expressions, Operators, and Precedence

1.3.1 Compound Expressions and Operator Precedence

1.4 Control Flow

1.4.1 Conditionals

1.4.2 Loops

1.5 Functions

1.5.1 Information Passing

1.5.2 Python’s Built-In Functions

1.6 Simple Input and Output

1.6.1 Console Input and Output

1.6.2 Files

1.7 Exception Handling

1.7.1 Raising an Exception

1.7.2 Catching an Exception

1.8 Iterators and Generators

1.9 Additional Python Conveniences

1.9.1 Conditional Expressions

1.9.2 Comprehension Syntax

1.9.3 Packing and Unpacking of Sequences

1.10 Scopes and Namespaces

1.11 Modules and the Import Statement

1.11.1 Existing Modules

1.12 Exercises

2 Object-Oriented Programming

2.1 Goals, Principles, and Patterns

2.1.1 Object-Oriented Design Goals

2.1.2 Object-Oriented Design Principles

2.1.3 Design Patterns

2.2 Software Development

2.2.1 Design

2.2.2 Pseudo-Code

2.2.3 Coding Style and Documentation

2.2.4 Testing and Debugging

2.3 Class Definitions

2.3.1 Example: CreditCard Class

2.3.2 Operator Overloading and Python’s Special Methods

2.3.3 Example: Multidimensional Vector Class

2.3.4 Iterators

2.3.5 Example: Range Class

2.4 Inheritance

2.4.1 Extending the CreditCard Class

2.4.2 Hierarchy of Numeric Progressions

2.4.3 Abstract Base Classes

2.5 Namespaces and Object-Orientation

2.5.1 Instance and Class Namespaces

2.5.2 Name Resolution and Dynamic Dispatch

2.6 Shallow and Deep Copying

2.7 Exercises

3 Algorithm Analysis

3.1 Experimental Studies

3.1.1 Moving Beyond Experimental Analysis

3.2 The Seven Functions Used in This Book

3.2.1 Comparing Growth Rates

3.3 Asymptotic Analysis

3.3.1 The “Big-Oh” Notation

3.3.2 Comparative Analysis

3.3.3 Examples of Algorithm Analysis

3.4 Simple Justification Techniques

3.4.1 By Example

3.4.2 The “Contra” Attack

3.4.3 Induction and Loop Invariants

3.5 Exercises

4 Recursion

4.1 Illustrative Examples

4.1.1 The Factorial Function

4.1.2 Drawing an English Ruler

4.1.3 Binary Search

4.1.4 File Systems

4.2 Analyzing Recursive Algorithms

4.3 Recursion Run Amok

4.3.1 Maximum Recursive Depth in Python

4.4 Further Examples of Recursion

4.4.1 Linear Recursion

4.4.2 Binary Recursion

4.4.3 Multiple Recursion

4.5 Designing Recursive Algorithms

4.6 Eliminating Tail Recursion

4.7 Exercises

5 Array-Based Sequences

5.1 Python’s Sequence Types

5.2 Low-Level Arrays

5.2.1 Referential Arrays

5.2.2 Compact Arrays in Python

5.3 Dynamic Arrays and Amortization

5.3.1 Implementing a Dynamic Array

5.3.2 Amortized Analysis of Dynamic Arrays

5.3.3 Python’s List Class

5.4 Efficiency of Python’s Sequence Types

5.4.1 Python’s List and Tuple Classes

5.4.2 Python’s String Class

5.5 Using Array-Based Sequences

5.5.1 Storing High Scores for a Game

5.5.2 Sorting a Sequence

5.5.3 Simple Cryptography

5.6 Multidimensional Data Sets

5.7 Exercises

6 Stacks, Queues, and Deques

6.1 Stacks

6.1.1 The Stack Abstract Data Type

6.1.2 Simple Array-Based Stack Implementation

6.1.3 Reversing Data Using a Stack

6.1.4 Matching Parentheses and HTML Tags

6.2 Queues

6.2.1 The Queue Abstract Data Type

6.2.2 Array-Based Queue Implementation

6.3 Double-Ended Queues

6.3.1 The Deque Abstract Data Type

6.3.2 Implementing a Deque with a Circular Array

6.3.3 Deques in the Python Collections Module

6.4 Exercises

7 Linked Lists

7.1 Singly Linked Lists

7.1.1 Implementing a Stack with a Singly Linked List

7.1.2 Implementing a Queue with a Singly Linked List

7.2 Circularly Linked Lists

7.2.1 Round-Robin Schedulers

7.2.2 Implementing a Queue with a Circularly Linked List

7.3 Doubly Linked Lists

7.3.1 Basic Implementation of a Doubly Linked List

7.3.2 Implementing a Deque with a Doubly Linked List

7.4 The Positional List ADT

7.4.1 The Positional List Abstract Data Type

7.4.2 Doubly Linked List Implementation

7.5 Sorting a Positional List

7.6 Case Study: Maintaining Access Frequencies

7.6.1 Using a Sorted List

7.6.2 Using a List with the Move-to-Front Heuristic

7.7 Link-Based vs. Array-Based Sequences

7.8 Exercises

8 Trees

8.1 General Trees

8.1.1 Tree Definitions and Properties

8.1.2 The Tree Abstract Data Type

8.1.3 Computing Depth and Height

8.2 Binary Trees

8.2.1 The Binary Tree Abstract Data Type

8.2.2 Properties of Binary Trees

8.3 Implementing Trees

8.3.1 Linked Structure for Binary Trees

8.3.2 Array-Based Representation of a Binary Tree

8.3.3 Linked Structure for General Trees

8.4 Tree Traversal Algorithms

8.4.1 Preorder and Postorder Traversals of General Trees

8.4.2 Breadth-First Tree Traversal

8.4.3 Inorder Traversal of a Binary Tree

8.4.4 Implementing Tree Traversals in Python

8.4.5 Applications of Tree Traversals

8.4.6 Euler Tours and the Template Method Pattern

8.5 Case Study: An Expression Tree

8.6 Exercises

9 Priority Queues

9.1 The Priority Queue Abstract Data Type

9.1.1 Priorities

9.1.2 The Priority Queue ADT

9.2 Implementing a Priority Queue

9.2.1 The Composition Design Pattern

9.2.2 Implementation with an Unsorted List

9.2.3 Implementation with a Sorted List

9.3 Heaps

9.3.1 The Heap Data Structure

9.3.2 Implementing a Priority Queue with a Heap

9.3.3 Array-Based Representation of a Complete Binary Tree

9.3.4 Python Heap Implementation

9.3.5 Analysis of a Heap-Based Priority Queue

9.3.6 Bottom-Up Heap Construction

9.3.7 Python’s heapq Module

9.4 Sorting with a Priority Queue

9.4.1 Selection-Sort and Insertion-Sort

9.4.2 Heap-Sort

9.5 Adaptable Priority Queues

9.5.1 Locators

9.5.2 Implementing an Adaptable Priority Queue

9.6 Exercises

10 Maps, Hash Tables, and Skip Lists

10.1 Maps and Dictionaries

10.1.1 The Map ADT

10.1.2 Application: Counting Word Frequencies

10.1.3 Python’s MutableMapping Abstract Base Class

10.1.4 Our MapBase Class

10.1.5 Simple Unsorted Map Implementation

10.2 Hash Tables

10.2.1 Hash Functions

10.2.2 Collision-Handling Schemes

10.2.3 Load Factors, Rehashing, and Efficiency

10.2.4 Python Hash Table Implementation

10.3 Sorted Maps

10.3.1 Sorted Search Tables

10.3.2 Two Applications of Sorted Maps

10.4 Skip Lists

10.4.1 Search and Update Operations in a Skip List

10.4.2 Probabilistic Analysis of Skip Lists

10.5 Sets, Multisets, and Multimaps

10.5.1 The Set ADT

10.5.2 Python’s MutableSet Abstract Base Class

10.5.3 Implementing Sets, Multisets, and Multimaps

10.6 Exercises

11 Search Trees

11.1 Binary Search Trees

11.1.1 Navigating a Binary Search Tree

11.1.2 Searches

11.1.3 Insertions and Deletions

11.1.4 Python Implementation

11.1.5 Performance of a Binary Search Tree

11.2 Balanced Search Trees

11.2.1 Python Framework for Balancing Search Trees

11.3 AVL Trees

11.3.1 Update Operations

11.3.2 Python Implementation

11.4 Splay Trees

11.4.1 Splaying

11.4.2 When to Splay

11.4.3 Python Implementation

11.4.4 Amortized Analysis of Splaying

11.5 (2,4) Trees

11.5.1 Multiway Search Trees

11.5.2 (2,4)-Tree Operations

11.6 Red-Black Trees

11.6.1 Red-Black Tree Operations

11.6.2 Python Implementation

11.7 Exercises

12 Sorting and Selection

12.1 Why Study Sorting Algorithms?

12.2 Merge-Sort

12.2.1 Divide-and-Conquer

12.2.2 Array-Based Implementation of Merge-Sort

12.2.3 The Running Time of Merge-Sort

12.2.4 Merge-Sort and Recurrence Equations

12.2.5 Alternative Implementations of Merge-Sort

12.3 Quick-Sort

12.3.1 Randomized Quick-Sort

12.3.2 Additional Optimizations for Quick-Sort

12.4 Studying Sorting through an Algorithmic Lens

12.4.1 Lower Bound for Sorting

12.4.2 Linear-Time Sorting: Bucket-Sort and Radix-Sort

12.5 Comparing Sorting Algorithms

12.6 Python’s Built-In Sorting Functions

12.6.1 Sorting According to a Key Function

12.7 Selection

12.7.1 Prune-and-Search

12.7.2 Randomized Quick-Select

12.7.3 Analyzing Randomized Quick-Select

12.8 Exercises

13 Text Processing

13.1 Abundance of Digitized Text

13.1.1 Notations for Strings and the Python str Class

13.2 Pattern-Matching Algorithms

13.2.1 Brute Force

13.2.2 The Boyer-Moore Algorithm

13.2.3 The Knuth-Morris-Pratt Algorithm

13.3 Dynamic Programming

13.3.1 Matrix Chain-Product

13.3.2 DNA and Text Sequence Alignment

13.4 Text Compression and the Greedy Method

13.4.1 The Huffman Coding Algorithm

13.4.2 The Greedy Method

13.5 Tries

13.5.1 Standard Tries

13.5.2 Compressed Tries

13.5.3 Suffix Tries

13.5.4 Search Engine Indexing

13.6 Exercises

14 Graph Algorithms

14.1 Graphs

14.1.1 The Graph ADT

14.2 Data Structures for Graphs

14.2.1 Edge List Structure

14.2.2 Adjacency List Structure

14.2.3 Adjacency Map Structure

14.2.4 Adjacency Matrix Structure

14.2.5 Python Implementation

14.3 Graph Traversals

14.3.1 Depth-First Search

14.3.2 DFS Implementation and Extensions

14.3.3 Breadth-First Search

14.4 Transitive Closure

14.5 Directed Acyclic Graphs

14.5.1 Topological Ordering

14.6 Shortest Paths

14.6.1 Weighted Graphs

14.6.2 Dijkstra’s Algorithm

14.7 Minimum Spanning Trees

14.7.1 Prim-Jarník Algorithm

14.7.2 Kruskal’s Algorithm

14.7.3 Disjoint Partitions and Union-Find Structures

14.8 Exercises

15 Memory Management and B-Trees

15.1 Memory Management

15.1.1 Memory Allocation

15.1.2 Garbage Collection

15.1.3 Additional Memory Used by the Python Interpreter

15.2 Memory Hierarchies and Caching

15.2.1 Memory Systems

15.2.2 Caching Strategies

15.3 External Searching and B-Trees

15.3.1 (a,b) Trees

15.3.2 B-Trees

15.4 External-Memory Sorting

15.4.1 Multiway Merging

15.5 Exercises

A Character Strings in Python

B Useful Mathematical Facts

Bibliography

Index

下载地址