0 Introduction

0．1 Read Me

0．2 He Can t Say That, Can He?

1 The Object-Oriented Method

1．1 Data Abstractin and Encapsulation

1．2 The Object Model

1．3 Object-Oriented Terminology

1．4 Sketching an Example: A Word List

1．5 A Special Purpose Class:A Bank Account

1．6 A General Purpose Class:An Association

1．7 Interfaces

1．8 Who Is the User?

1．9 Conclusions

2 Comments, Conditions, and Assertions

2．1 Pre-and Postconditions

2．2 Assertions

2．3 Craftsmanship

2．4 Conclusions

3 Vectors

3．1 Application:The Word List Revisited

3．2 Application:Word Frequency

3．3 The Interface

3．4 The Implementation

3．5 Extensibility: A Feature

3．6 Application: The Matrix Class

3．7 Conclusions

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．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

5 Sorting

5．1 Approaching the Problem

5．2 Selection Sort

5．3 Insertion Sort

5．4 Mergesort

5．5 Quicksort

5．6 Sorting Objects

5．7 Vector-Based Sorting

5．8 Conclusions

6 Lists

6．1 Example: A Unique Program

6．2 Example:Free-Lists

6．3 Implementation:Singly-Linked Lists

6．4 Implementation:Doubly-Linked Lists

6．5 Implementation:Circularly-Linked Lists

6．6 Conclusions

7 Linear Structures

7．1 Stacks

7．1．1 Example: Simulating Recursion

7．1．2 Vector-Based Stacks

7．1．3 List-Based Stacks

7．1．4 Comparisons

7．2 Queues

7．2．1 Example:Solving a Coin ruzzle

7．2．2 List-Based Queues

7．2．3 Vector-Based Queues

7．2．4 Array-Based Queues

7．3 Example: Solving Mazes

7．4 Conclusions

8 Iterators

8．1 Java s Enumeration Interface

8．2 The Iterator Interface

8．3 Example: Vector Iterators

8．4 Example: List Iterators

8．5 Example: Filtering Iterators

8．6 Conclusions

9 Ordered Structures

9．1 Comparable Objects

9．1．1 Example: Comparable Integers

9．1．2 Example: Comparable Associations

9．2 Keeping Structures Ordered

9．2．1 The OrderedStructure Interface

9．2．2 The Ordered Vector

9．2．4 The Ordered List

9．2．3 Example: Sorting

9．2．5 Example: The Modified Parking Lot

9．3 Conclusions

10 Trees

10．1 Terminology

10．2 The Interface

10．3 Motivating Example: Expression Trees

10．4 Implementation

10．4．1 The BinaryTreeNode Implementation

10．4．2 Implementation of the BinaryTree Wrapper

10．5 Traversals

10．5．1 Preorder Traversal

10．5．2 Inorder Traversal

10．5．3 Postorder Traversal

10．5．4 Levelorder Traversal

10．5．5 Recursion in Iterators

10．6 Property-Based Methods

10．7 Example: Huffman Compression

10．8 Conclusions

11．1 The Interface

11 Priority Queues

11．2 Example:Improving the Huffman Code

11．3 Priority Vectors

11．4 A Heap Implementation

11．4．1 Vector-Based Heaps

11．4．2 Example: Heapsort

11．4．3 Skew Heaps

11．5 Example: Circuit Simulation

11．6 Conclusions

12．1 Binary Search Trees

12 Search Trees

12．2 Example: Tree Sort

12．3 Implementation

12．4 Splay Trees

12．5 Splay Tree Implementation

12．6 Conclusions

13 Dictionaries

13．1 The Interface

13．2 Unit Cost Dictionaries: Hash Tables

13．2．1 Open Addressing

13．2．2 External Chaining

13．2．3 Generation of Hash Codes

13．2．4 Analysis

13．3 Ordered Dictionaries and Tables

13．4 Example: Document Indexing

13．5 Conclusions

14 Graphs

14．1 Terminology

14．2 The Graph Interface

14．3．1 Abstract Classes

14．3 Implementations

14．3．2 Adjacency Matrices

14．3．3 Adjacency Lists

14．4 Examples: Common Graph Algorithms

14．4．1 Reachability

14．4．2 Topological Sorting

14．4．3 Transitive Closure

14．4．4 All Pairs Minimum Distance

14．4．5 Greedy Algorithms

14．5 Conclusions

A．1 A First Program

A A Sip of Java

A．2 Declarations

A．2．1 Primitive Types

A．2．2 Reference Types

A．3 Important Classes

A．3．1 The ReadStream Class

A．3．2 PrintStreams

A．3．3 Strings

A．4 Control Constructs

A．4．1 Conditional Statements

A．4．2 Loops

A．5 Methods

A．6 Inheritance and Subtyping

A．6．1 Inheritance

A．6．2 Subtyping

A．6．3 Interfaces and Abstract Classes

B Use of the Keyword Protected

C Principles

D Structure Package Hierarchy

E Selected Answers

Index