数据结构Java语言描述（第2版影印版）

Preface to First Edition

Preface to the Second Edition

Introduction

0.1 Read Me

0.2 He Can't Say That, Can He?

1 The Object-Oriented Method

1.1 Data Abstraction and Encapsulation

1.2 The Object Model

1.3 Object-Oriented Terminology

1.4 A Special-Purpose Class: A Bank Account

1.5 A General-Purpose Class: An Association

1.6 Sketching an Example: A Word List

1.7 Sketching an Example: A Rectangle Class

1.8 Interfaces

1.9 Who Is the User?

1.10 Conclusions

1.11 Laboratory: The Day of the Week Calculator

2 Comments, Conditions, and Assertions

2.1 Pre- and Postconditions

2.2 Assertions

2.3 Craftsmanship

2.4 Conclusions

2.5 Laboratory: Using Javadoc Commenting Vectors

3 Vectors

3.1 The Interface

3.2 Example: The Word List Revisited

3.3 Example: Word Frequency

3.4 The Implementation

3.5 Extensibility: A Feature

3.6 Example: L-Systems

3.7 Example: Vector-Based Sets

3.8 Example: The Matrix Class

3.9 Conclusions

3.10 Laboratory: The Silver Dollar Game

4 Design Fundamentals

4.1 Asymptotic Analysis Tools

4.1.1 Time and Space Complexity

4.1.2 Examples

4.1.3 The Trading of Time and Space

4.1.4 Back-of-the-Envelope Estimations

4.2 Self-Reference

4.2.1 Recursion

4.2.2 Mathematical Induction

4.3 Properties of Design

4.3.1 Symmetry

4.3.2 Friction

4.4 Conclusions

4.5 Laboratory: How Fast Is Java?

5 Sorting

5.1 Approaching the Problem

5.2 Selection Sort

5.3 Insertion Sort

5.4 Mergesort

5.5 Quicksoft

5.6 Radix Sort

5.7 Sorting Objects

5.8 Ordering Objects Using Comparators

5.9 Vector-Based Sorting

5.10 Conclusions

5.11 Laboratory: Sorting with Comparators

6 A Design Method

6.1 The Interface-Based Approach

6.1.1 Design of the Interface

6.1.2 Development of an Abstract Implementation

6.1.3 Implementation

6.2 Example: Development of Generators

6.3 Example: Playing Cards

6.4 Conclusions

7 Iterators

7.1 Java's Enumeration Interface

7.2 The Iterator Interface

7.3 Example: Vector Iterators

7.4 Example: Rethinking Generators

7.5 Example: Filtering Iterators

7.6 Conclusions

7.7 Laboratory: The Two-Towers Problem

8 Lists

8.1 Example: A Unique Program

8.2 Example: Free Lists

8.3 Partial Implementation: Abstract Lists

8.4 Implementation: Singly Linked Lists

8.5 Implementation: Doubly Linked Lists

8.6 Implementation: Circularly Linked Lists

8.7 Implementation: Vectors

8.8 List Iterators

8.9 Conclusions

8.10 Laboratory: Lists with Dummy Nodes

9 Linear Structures

9.1 Stacks

9.1.1 Example: Simulating Recursion

9.1.2 Vector-Based Stacks

9.1.3 List-Based Stacks

9.1.4 Comparisons

9.2 Queues

9.2.1 Example: Solving a Coin Puzzle

9.2.2 List-Based Queues

9.2.3 Vector-Based Queues

9.2.4 Array-Based Queues

9.3 Example: Solving Mazes

9.4 Conclusions

9.5 Laboratory: A Stack-Based Language

9.6 Laboratory: The Web Crawler

10 Ordered Structures

10.1 Comparable Objects Revisited

10.1.1 Example: Comparable Ratios

10.1.2 Example: Comparable Associations

10.2 Keeping Structures Ordered

10.2.1 The OrderedStructure Interface

10.2.2 The Ordered Vector and Binary Search

10.2.3 Example: Sorting Revisited

10.2.4 A Comparator-based Approach

10.2.5 The Ordered List

10.2.6 Example: The Modified Parking Lot

10.3 Conclusions

10.4 Laboratory: Computing the "Best Of"

11 Binary Trees

11.1 Terminology

11.2 Example: Pedigree Charts

11.3 Example: Expression Trees

11.4 Implementation

11.4.1 The BinaryTree Implementation

11.5 Example: An Expert System

11.6 Traversals of Binary Trees

11.6.1 Preorder Traversal

11.6.2 In-order Traversal

11.6.3 Postorder Traversal

11.6.4 Level-order Traversal

11.6.5 Recursion in Iterators

11.7 Property-Based Methods

11.8 Example: Huffman Compression

11.9 Example Implementation: Ahnentafel

11.10Conclusions

11.11Laboratory: Playing Gardner's Hex-a-Pawn

12 Priority Queues

12.1 The Interface

12.2 Example: Improving the Huffman Code

12.3 A Vector-Based Implementation

12.4 A Heap Implementation

12.4.1 Vector-Based Heaps

12.4.2 Example: Heapsort

12.4.3 Skew Heaps

12.5 Example: Circuit Simulation

12.6 Conclusions

12.7 Laboratory: Simulating Business

13 Search Trees

13.1 Binary Search Trees

13.2 Example: Tree Sort

13.3 Example: Associative Structures

13.4 Implementation

13.5 Splay Trees

13.6 Splay Tree Implementation

13.7 An Alternative:Red-Black Trees

13.8 Conclusions

13.9 Laboratory: Improving the BinarySearchTree

14 Maps

14.1 Example Revisited: The Symbol Table

14.2 The Interface

14.3 Simple Implementation: MapList

14.4 Constant Time Maps: Hash Tables

14.4.1 Open Addressing

14.4.2 External Chaining

14.4.3 Generation of Hash Codes

14.4.4 Hash Codes for Collection Classes

14.4.5 Performance Analysis

14.5 Ordered Maps and Tables

14.6 Example: Document Indexing

14.7 Conclusions

14.8 Laboratory: The Soundex Name Lookup System

15 Graphs

15.1 Terminology

15.2 The Graph Interface

15.3 Implementations

15.3.1 Abstract Classes Reemphasized

15.3.2 Adjacency Matrices

15.3.3 Adjacency Lists

15.4 Examples: Common Graph Algorithms

15.4.1 Reachability

15.4.2 Topological Sorting

15.4.3 Transitive Closure

15.4.4 All Pairs Minimum Distance

15.4.5 Greedy Algorithms

15.5 Conclusions

15.6 Laboratory: Converting Between Units

A Answers

A.1 Solutions to Self Check Problems

A.2 Solutions to Odd-Numbered Problems

B Beginning with Java

B.1 A First Program

B.2 Declarations

B.2.1 Primitive Types

B.2.2 Reference Types

B.3 Important Classes

B.3.1 The ReadStream Class

B.3.2 The PrintStream Class

B.3.3 Strings

B.4 Control Constructs

B.4.1 Conditional Statements

B.4.2 Loops

B.5 Methods

B.6 Inheritance and Subtyping

B.6.1 Inheritance

B.6.2 Subtyping

B.6.3 Interfaces and Abstract Classes

B.7 Use of the Assert Command

B.8 Use of the Keyword Protected

C Collections

C.1 Collection Class Features

C.2 Parallel Features

C.3 Conversion

D Documentation

D.1 Structure Package Hierarchy

D.2 Principles

E Environments

E.1 Downloading Software

E.2 Creating Libraries

E.3 Creating Project Stationery

F Further Reading

G Glossary

Index