谢弗编著的《数据结构与算法分析》采用程序员最爱用的面向对象C++语言来描述数据结构和算法，并把数据结构原理和算法分析技术有机地结合在一起，系统介绍了各种类型的数据结构和排序、检索的各种方法。作者非常注意对每一种数据结构的不同存储方法及有关算法进行分析比较。书中还引入了一些比较高级的数据结构与先进的算法分析技术，并介绍了可计算性理论的一般知识。书中分别给出了C++实现方法和伪码实现方法，便于读者根据情况选择。本书作者维护的网站上可下载相关代码、编程项目和辅助练习资料。

本书适合作为大专院校计算机软件专业与计算机应用专业学生的教材和参考书，也适合计算机工程技术人员参考。

Preface

Part Ⅰ Preliminaries

 Chapter 1 Data Structures and Algorithms

1.1 A Philosophy of Data Structures

1.1.1 The Need for Data Structures

1.1.2 Costs and Benefits

1.2 Abstract Data Types and Data Structures

1.3 Design Patterns

1.3.1 Flyweight

1.3.2 Visitor

1.3.3 Composite

1.3.4 Strategy

1.4 Problems, Algorithms, and Programs

1.5 Further Reading

1.6 Exercises

 Chapter 2 Mathematical Preliminaries

2.1 Sets and Relations

2.2 Miscellaneous Notation

2.3 Logarithms

2.4 Summations and Recurrences

2.5 Recursion

2.6 Mathematical Proof Techniques

2.6.1 Direct Proof

2.6.2 Proof by Contradiction

2.6.3 Proof by Mathematical Induction

2.7 Estimation

2.8 Further Reading

2.9 Exercises

 Chapter 3 Algorithm Analysis

3.1 Introduction

3.2 Best, Worst, and Average Cases

3.3 A Faster Computer, or a Faster Algorithm?

3.4 Asymptotic Analysis

3.4.1 Upper Bounds

3.4.2 Lower Bounds

3.4.3  Notation

3.4.4 Simplifying Rules

3.4.5 Classifying Functions

3.5 Calculating the Running Time for a Program

3.6 Analyzing Problems

3.7 Common Misunderstandings

3.8 Multiple Parameters

3.9 Space Bounds

3.10 Speeding Up Your Programs

3.11 Empirical Analysis

3.12 Further Reading

3.13 Exercises

3.14 Projects

Part Ⅱ Fundamental Data Structures

 Chapter 4 Lists, Stacks, and Queues

4.1 Lists

4.1.1 Array-Based List Implementation

4.1.2 Linked Lists

4.1.3 Comparison of List Implementations

4.1.4 Element Implementations

4.1.5 Doubly Linked Lists

4.2 Stacks

4.2.1 Array-Based Stacks

4.2.2 Linked Stacks

4.2.3 Comparison of Array-Based and Linked Stacks

4.2.4 Implementing Recursion

4.3 Queues

4.3.1 Array-Based Queues

4.3.2 Linked Queues

4.3.3 Comparison of Array-Based and Linked Queues

4.4 Dictionaries

4.5 Further Reading

4.6 Exercises

4.7 Projects

 Chapter 5 Binary Trees

5.1 Definitions and Properties

5.1.1 The Full Binary Tree Theorem

5.1.2 A Binary Tree Node ADT

5.2 Binary Tree Traversals

5.3 Binary Tree Node Implementations

5.3.1 Pointer-Based Node Implementations

5.3.2 Space Requirements

5.3.3 Array Implementation for Complete Binary Trees

5.4 Binary Search Trees

5.5 Heaps and Priority Queues

5.6 Huffman Coding Trees

5.6.1 Building Huffman Coding Trees

5.6.2 Assigning and Using Huffman Codes

5.6.3 Search in Huffman Trees

5.7 Further Reading

5.8 Exercises

5.9 Projects

 Chapter 6 Non-Binary Trees

6.1 General Tree Definitions and Terminology

6.1.1 An ADT for General Tree Nodes

6.1.2 General Tree Traversals

6.2 The Parent Pointer Implementation

6.3 General Tree Implementations

6.3.1 List of Children

6.3.2 The Left-Child/Right-Sibling Implementation

6.3.3 Dynamic Node Implementations

6.3.4 Dynamic “Left-Child/Right-Sibling” Implementation

6.4 K-ary Trees

6.5 Sequential Tree Implementations

6.6 Further Reading

6.7 Exercises

6.8 Projects

Part Ⅲ Sorting and Searching

 Chapter 7 Internal Sorting

7.1 Sorting Terminology and Notation

7.2 Three (n2) Sorting Algorithms

7.2.1 Insertion Sort

7.2.2 Bubble Sort

7.2.3 Selection Sort

7.2.4 The Cost of Exchange Sorting

7.3 Shellsort

7.4 Mergesort

7.5 Quicksort

7.6 Heapsort

7.7 Binsort and Radix Sort

7.8 An Empirical Comparison of Sorting Algorithms

7.9 Lower Bounds for Sorting

7.10 Further Reading

7.11 Exercises

7.12 Projects

 Chapter 8 File Processing and External Sorting

8.1 Primary versus Secondary Storage

8.2 Disk Drives

8.2.1 Disk Drive Architecture

8.2.2 Disk Access Costs

8.3 Buffers and Buffer Pools

8.4 The Programmer’s View of Files

8.5 External Sorting

8.5.1 Simple Approaches to External Sorting

8.5.2 Replacement Selection

8.5.3 Multiway Merging

8.6 Further Reading

8.7 Exercises

8.8 Projects

 Chapter 9 Searching

9.1 Searching Unsorted and Sorted Arrays

9.2 Self-Organizing Lists

9.3 Bit Vectors for Representing Sets

9.4 Hashing

9.4.1 Hash Functions

9.4.2 Open Hashing

9.4.3 Closed Hashing

9.4.4 Analysis of Closed Hashing

9.4.5 Deletion

9.5 Further Reading

9.6 Exercises

9.7 Projects

 Chapter 10 Indexing

10.1 Linear Indexing

10.2 ISAM

10.3 Tree-based Indexing

10.4 2-3 Trees

10.5 B-Trees

10.5.1 B+-Trees

10.5.2 B-Tree Analysis

10.6 Further Reading

10.7 Exercises

10.8 Projects

Part Ⅳ Advanced Data Structures

 Chapter 11 Graphs

11.1 Terminology and Representations

11.2 Graph Implementations

11.3 Graph Traversals

11.3.1 Depth-First Search

11.3.2 Breadth-First Search

11.3.3 Topological Sort

11.4 Shortest-Paths Problems

11.4.1 Single-Source Shortest Paths

11.5 Minimum-Cost Spanning Trees

11.5.1 Prim’s Algorithm

11.5.2 Kruskal’s Algorithm

11.6 Further Reading

11.7 Exercises

11.8 Projects

 Chapter 12 Lists and Arrays Revisited

12.1 Multilists

12.2 Matrix Representations

12.3 Memory Management

12.3.1 Dynamic Storage Allocation

12.3.2 Failure Policies and Garbage Collection

12.4 Further Reading

12.5 Exercises

12.6 Projects

 Chapter 13 Advanced Tree Structures

13.1 Tries

13.2 Balanced Trees

13.2.1 The AVL Tree

13.2.2 The Splay Tree

13.3 Spatial Data Structures

13.3.1 The K-D Tree

13.3.2 The PR quadtree

13.3.3 Other Point Data Structures

13.3.4 Other Spatial Data Structures

13.4 Further Reading

13.5 Exercises

13.6 Projects

Part Ⅴ Theory of Algorithms

14 Analysis Techniques

14.1 Summation Techniques

14.2 Recurrence Relations

14.2.1 Estimating Upper and Lower Bounds

14.2.2 Expanding Recurrences

14.2.3 Divide and Conquer Recurrences

14.2.4 Average-Case Analysis of Quicksort

14.3 Amortized Analysis

14.4 Further Reading

14.5 Exercises

14.6 Projects

 Chapter 15 Lower Bounds

15.1 Introduction to Lower Bounds Proofs

15.2 Lower Bounds on Searching Lists

15.2.1 Searching in Unsorted Lists

15.2.2 Searching in Sorted Lists

15.3 Finding the Maximum Value

15.4 Adversarial Lower Bounds Proofs

15.5 State Space Lower Bounds Proofs

15.6 Finding the ith Best Element

15.7 Optimal Sorting

15.8 Further Reading

15.9 Exercises

15.10 Projects

 Chapter 16 Patterns of Algorithms

16.1 Dynamic Programming

16.1.1 The Knapsack Problem

16.1.2 All-Pairs Shortest Paths

16.2 Randomized Algorithms

16.2.1 Randomized algorithms for finding large values

16.2.2 Skip Lists

16.3 Numerical Algorithms

16.3.1 Exponentiation

16.3.2 Largest Common Factor

16.3.3 Matrix Multiplication

16.3.4 Random Numbers

16.3.5 The Fast Fourier Transform

16.4 Further Reading

16.5 Exercises

16.6 Projects

 Chapter 17 Limits to Computation

17.1 Reductions

17.2 Hard Problems

17.2.1 The Theory of NP-Completeness

17.2.2 NP-Completeness Proofs

17.2.3 Coping with NP-Complete Problems

17.3 Impossible Problems

17.3.1 Uncountability

17.3.2 The Halting Problem Is Unsolvable

17.4 Further Reading

17.5 Exercises

17.6 Projects

Part Ⅵ APPENDIX

A Utility Functions

Bibliography

Index