Free

Java Structures: Data Structures for the Principled Programmer

By Duane A. Bailey

Free

Read Now

Description Table of Contents Reviews Comments

Book Description

Table of Contents

Java Structures
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

Java Structures: Data Structures for the Principled Programmer

Free Machine Learning Books

Free Chemistry Textbooks

Free Mathematics Textbooks

Free Children Books

Free Java Books