Preface
0 Introduction
0.1 Read Me
0.2 He Cant Say That, Can He?
1 The Object-Oriented Method
1.1 Data Abstraction and Encapsulation
l.2 The Object Model
1.3 Object-Oriented Terminology
1.4 Sketching an Example: A Word List
l.5 A Special Purpose Class: A Bank Account
1.6 AGeneral Purpose Class: An Association
1.7 Interfaces
l.8 Who Is the User?
l.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 Thndamentals
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 QuickPort
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 Puzzle
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 Iterates 1
8.1 Javas Enumeration Interface
8.2 The Iterate Interface
8.3 Example: Vector Iterates
8.4 Example: List Iterates
8.5 Example: Filtering Iterates
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.3 Example: Sorting
9.2.4 The Ordered List
9.2.5 Example: The Modified Parking Lot
9.3 Conclusions
10 These
l0.1 Terminology
10.2 TheInterface
l0.3 Motivating Example: Expression Trees
10.4 Implementation
l0.4.1 The BinaryTreeNode Implementation
l0.4.2 implementation of the BinaryTree Wrapper
10.5 Traversals
l0.5.1 Preorder Traversal
l0.5.2 Ignored Traversal
l0.5.3 Postured Traversal
l0.5.4 Levelorder Traversal
10.5.5 Recursion in Iterates
l0.6 Property-Based Methods
10.7 Example: Huffman Compression
10.8 Conclusions
11 Priority Queues
l1.1 The Interface
11.2 Example: Improving the Huffman Code
l1.3 Priority Vectors
ll.4 A Heap Implementation
1l.4.1 Vector-Based Heaps
ll.4.2 Example: Heapsort
11.4.3 Skew Heaps
l1.5 Example: Circuit Simulation
l1.6 Conclusions
12 Search knees
l2.1 Binary Search Trees
12.2 Example: Tree Sort
l2.3 Implementation
12.4 Splay Trees
l2.5 Splay Tree Implementation
l2.6 Conclusions
13 Dictionaries
13.1 TheInterface
l3.2 Unit Cost Dictionaries: Hash Tables
l3.2.1 Open Addressing
l3.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
l4.1 Terminology
l4.2 The Graph Interface
14.3 Implementations
l4.3.1 Abstract Classes
14.3.2 Adjacency Matrices
l4.3.3 Adjacency Lists
14.4 Examples: Common Graph Algorithms
l4.4.1 Ratability
14.4.2 Topological Sorting
14.4.3 Transitive Closure
14.4.4 All Pairs Minimum Distance
14.4.5 Greedy Algorithms
l4.5 Conclusions
A A Sip of Java
A.1 A First Program
A.2 Declarations
A.2.1 Primitive Types
A.2.2 Reference Types
A.3 Important Classes
A.3.1 The roadster!n 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<>
鄂公网安备 42010302001612号 