Java Structures: Data Structures for the Principled Programmer
Free
Description
Contents
Reviews
Language
English
ISBN
Unknown
Java Structures
Copyright (c) 2005-2007 Duane A. Bailey
Table of Contents
Preface to First Edition
Preface to the Second Edition
Preface to the ``Root 7'' Edition
0 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
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 Generics
4.1 Motivation (in case we need some)
4.1.1 Possible Solution: Specialization
4.2 Implementing Generic Container Classes
4.2.1 Generic Associations
4.2.2 Parameterizing the Vector Class
4.2.3 Restricting Parameters
4.3 Conclusions
5 Design Fundamentals
5.1 Asymptotic Analysis Tools
5.1.1 Time and Space Complexity
5.1.2 Examples
5.1.3 The Trading of Time and Space
5.1.4 Back-of-the-Envelope Estimations
5.2 Self-Reference
5.2.1 Recursion
5.2.2 Mathematical Induction
5.3 Properties of Design
5.3.1 Symmetry
5.3.2 Friction
5.4 Conclusions
5.5 Laboratory: How Fast Is Java?
6 Sorting
6.1 Approaching the Problem
6.2 Selection Sort
6.3 Insertion Sort
6.4 Mergesort
6.5 Quicksort
6.6 Radix Sort
6.7 Sorting Objects
6.8 Ordering Objects Using Comparators
6.9 Vector-Based Sorting
6.10 Conclusions
6.11 Laboratory: Sorting with Comparators
7 A Design Method
7.1 The Interface-Based Approach
7.1.1 Design of the Interface
7.1.2 Development of an Abstract Implementation
7.1.3 Implementation
7.2 Example: Development of Generators
7.3 Example: Playing Cards
7.4 Conclusions
8 Iterators
8.1 Java's Enumeration Interface
8.2 The Iterator Interface
8.3 Example: Vector Iterators
8.4 Example: Rethinking Generators
8.5 Example: Filtering Iterators
8.6 Conclusions
8.7 Laboratory: The Two-Towers Problem
9 Lists
9.1 Example: A Unique Program
9.2 Example: Free Lists
9.3 Partial Implementation: Abstract Lists
9.4 Implementation: Singly Linked Lists
9.5 Implementation: Doubly Linked Lists
9.6 Implementation: Circularly Linked Lists
9.7 Implementation: Vectors
9.8 List Iterators
9.9 Conclusions
9.10 Laboratory: Lists with Dummy Nodes
10 Linear Structures
10.1 Stacks
10.1.1 Example: Simulating Recursion
10.1.2 Vector-Based Stacks
10.1.3 List-Based Stacks
10.1.4 Comparisons
10.2 Queues
10.2.1 Example: Solving a Coin Puzzle
10.2.2 List-Based Queues
10.2.3 Vector-Based Queues
10.2.4 Array-Based Queues
10.3 Example: Solving Mazes
10.4 Conclusions
10.5 Laboratory: A Stack-Based Language
10.6 Laboratory: The Web Crawler
11 Ordered Structures
11.1 Comparable Objects Revisited
11.1.1 Example: Comparable Ratios
11.1.2 Example: Comparable Associations
11.2 Keeping Structures Ordered
11.2.1 The OrderedStructure Interface
11.2.2 The Ordered Vector and Binary Search
11.2.3 Example: Sorting Revisited
11.2.4 A Comparator-based Approach
11.2.5 The Ordered List
11.2.6 Example: The Modified Parking Lot
11.3 Conclusions
11.4 Laboratory: Computing the ``Best Of''
12 Binary Trees
12.1 Terminology
12.2 Example: Pedigree Charts
12.3 Example: Expression Trees
12.4 Implementation
12.4.1 The BinaryTree Implementation
12.5 Example: An Expert System
12.6 Traversals of Binary Trees
12.6.1 Preorder Traversal
12.6.2 In-order Traversal
12.6.3 Postorder Traversal
12.6.4 Level-order Traversal
12.6.5 Recursion in Iterators
12.7 Property-Based Methods
12.8 Example: Huffman Compression
12.9 Example Implementation: Ahnentafel
12.10 Conclusions
12.11 Laboratory: Playing Gardner's Hex-a-Pawn
13 Priority Queues
13.1 The Interface
13.2 Example: Improving the Huffman Code
13.3 A Vector-Based Implementation
13.4 A Heap Implementation
13.4.1 Vector-Based Heaps
13.4.2 Example: Heapsort
13.4.3 Skew Heaps
13.5 Example: Circuit Simulation
13.6 Conclusions
13.7 Laboratory: Simulating Business
14 Search Trees
14.1 Binary Search Trees
14.2 Example: Tree Sort
14.3 Example: Associative Structures
14.4 Implementation
14.5 Splay Trees
14.6 Splay Tree Implementation
14.7 An Alternative: Red-Black Trees
14.8 Conclusions
14.9 Laboratory: Improving the BinarySearchTree
15 Maps
15.1 Example Revisited: The Symbol Table
15.2 The Interface
15.3 Simple Implementation: MapList
15.4 Constant Time Maps: Hash Tables
15.4.1 Open Addressing
15.4.2 External Chaining
15.4.3 Generation of Hash Codes
15.4.4 Hash Codes for Collection Classes
15.4.5 Performance Analysis
15.5 Ordered Maps and Tables
15.6 Example: Document Indexing
15.7 Conclusions
15.8 Laboratory: The Soundex Name Lookup System
16 Graphs
16.1 Terminology
16.2 The Graph Interface
16.3 Implementations
16.3.1 Abstract Classes Reemphasized
16.3.2 Adjacency Matrices
16.3.3 Adjacency Lists
16.4 Examples: Common Graph Algorithms
16.4.1 Reachability
16.4.2 Topological Sorting
16.4.3 Transitive Closure
16.4.4 All Pairs Minimum Distance
16.4.5 Greedy Algorithms
16.5 Conclusions
16.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 structure.ReadStream Class
B.3.2 The java.util.Scanner Class
B.3.3 The PrintStream Class
B.3.4 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
Index
Colophon
The book hasn't received reviews yet.
