数据结构与Java类集框架：英文本

内容：1. Java重要特性 2. 接口与类集 3. 软件工程简介 4. 递归 5. 数组列表 6. 链接表 7. 队列与栈 8. 二叉树与二叉排序树 9. 平衡二叉排序树 10. 树图与树集 11. 优先队列 12. 排序 13. 排序与哈希类 14. 图、树与网络 附录一 数学背景知识 附录二 图形用户接口及其相关类 附录三 Java类集框架中的接口与类

Chapter1 Important Features of Java

Chapter Objectives

1.1 Classes

1.1.1 Method Descriptions

1.1.2 Data Abstraction

1.1.3 An Employee Class

1.1.4 Local Variables and Fields

1.1.5 Constructors

1.1.6 Instance Variables and Static Variables

1.1.7 Visibility Modifiers

1.1.8 Graphical User Interfaces

1.1.9 The Company Class

Lab 1: The CompanyMain Project

1.1.10 Inheritance

1.1.11 The protected Visibility Modifier

1.1.12 Inheritance and Constructors

Lab 2: The SalariedEmployee Class

1.1.13 Polymorphism

1.1.14 Information Hiding

1.1.15 Exception Handling

1.1.16 Propagating Exceptions

Lab 3: An Example of Exception Handling

Summary

Exercises

Programming Project 1.1: Developing and Using a Sequence Class

Chapter2 Interfaces and Collection Classes

Chapter Objectives

2.1 Abstract Methods and Abstract Classes

Lab 4: A Class for Regular Polygons

2.2 Interfaces

2.3 Arrays

2.4 Collection Classes

2.5 Storage Structures for Collection Classes

Lab 5: The ArrayCollection Class's Implementation of the Collection Interface

2.5.1 Linked Structures

2.5.2 The LinkedCollection Class

2.5.3 Fields and Method Definitions in the LinkedCollection Class

2.5.4 Iterators

Lab 6: Expanding the LinkedCollection Class

2.5.5 Data Structures and the Java Collections Framework

Summary

Exercises

Programming Project 2.1: Expanding the LinkedCollection Class

Chapter3 Introduction to Software Engineering

Chapter Objectives

3.1 The Software Development Life Cycle

3.2 Problem Analysis

3.2.1 System Tests

3.3 Program Design

3.3.1 Method Descriptions and Fields

3.3.2 Dependency Diagrams

3.4 Program Implementation

3.4.1 Method Validation

Lab 7: Drivers

3.4.2 Is Correctness Feasible?

3.4.3 Estimating the Efficiency of Methods

3.4.4 Big-O Notation

3.4.5 Getting Big-O Estimates Quickly

3.4.6 Trade-Offs

3.4.7 Run-Time Analysis

3.4.8 Overview of the Random Class

Lab 8: Randomness and Timing

3.5 Program Maintenance

Summary

Exercises

Programming Project 3.1: Further Expansion of the LinkedCollection Class

Chapter4 Recursion

Chapter Objectives

4.1 Introduction

4.2 Factorials

4.2.1 Execution Frames

4.3 Decimal to Binary

Lab 9: Fibonacci Numbers

4.4 Towers of Hanoi

4.4.1 A Recurrence Relation

4.5 Backtracking

4.5.1 An A-maze-ing Application

4.6 Binary Search

Lab 10: Iterative Binary Search

Lab 11: Generating Permutations

4.7 Indirect Recursion

4.8 The Cost of Recursion

Summary

Exercises

Programming Project 4.1: Iterative Version of Towers of Hanoi

Programming Project 4.2: Eight Queens

Programming Project 4.3: A Knigh's Tour

Chapter5 Array Lists

Chapter Objectives

5.1 The List Interface

5.2 The ArrayList Class

5.2.1 Method Descriptions for the ArrayList Class

5.2.2 ArrayList Class Heading

5.2.3 Fields in the ArrayList Class

5.2.4 ArrayList Objects Are Serializable

5.2.5 ArrayList Objects Are Cloneable

5.3 The ArrayList Implementation

5.3.1 Definition of the add Method

5.3.2 Amortized Time

5.3.3 The clone Method and the Copy Constructor

5.3.4 Fail-Fast Iterators

Lab 12: More Details on the ArrayList Class

5.4 Application: High-Precision Arithmetic

5.4.1 Design of the VeryLongInt Class

5.4.2 Implementation of the VeryLongInt Class

Lab 13: Extending the VeryLongInt Class

5.5 The Vector Class

Summary

Exercises

Programming Project 5.1: Extending the VeryLongInt Class

Programming Project 5.2: The Deque Class

Chapter6 Linked Lists

Chapter Objectives

6.1 The LinkedList Class

6.1.1 The LinkedList Class versus the ArrayList Class

6.1.2 LinkedList Iterators

6.1.3 Fields and Implementation of the LinkedList Class

6.1.4 Fields and Implementation of ListItr Class

Lab 14: More Implementation Details of the ListItr Class

Lab 15: Timing the ArrayList and LinkedList Classes

6.1.5 Alternative Designs and Implementations of the LinkedList Class

6.1.6 Circular Linked Lists

6.2 Application: A Line Editor

6.2.1 Design of the Editor Class

6.2.2 Implementation of the Editor Class

6.2.3 Big-O Analysis of the Editor Class Methods

6.2.4 The EditorDriver Class

Summary

Exercises

Programming Project 6.1: Extending the Line Editor

Programming Project 6.2: Alternative Design and Implementation of the LinkedList Class

Chapter7 Queues and Stacks

Chapter Objectives

7.1 Queues

7.1.1 Design and Implementation of the Queue Class

7.1.2 Alternative Designs and Implementation of the Queue Class

7.2 Computer Simulation

7.3 Application: A Simulated Car Wash

7.3.1 Design of the CarWash Class

7.3.2 Implementation of the CarWash Class

7.3.3 Analysis of the CarWash Methods

7.3.4 Randomizing the Arrival Times

Lab 16: Randomizing the Arrival Times

7.4 Stacks

7.4.1 Design and Implementation of the Stack Class

7.4.2 The Stack Class in the Java Collections Framework

7.4.3 Alternative Designs and Implementations of the Stack Class

7.5 Application: How Compilers Implement Recursion

7.6 Application: Converting From Infix to Postfix

7.6.1 Postfix Notation

7.6.2 Transition Matrix

7.6.3 Tokens

Lab 17: Converting from Infix to Postfix

7.6.4 Prefix Notation

Summary

Exercises

Programming Project 7.1: Extending Speedo's Car Wash

Programming Project 7.2: Run-Time Evaluation of a Condition

Programming Project 7.3: An Iterative Version of Maze-Search

Chapter8 Binary Trees and Binary Search Trees

Chapter Objectives

8.1 Definition and Properties of Binary Trees

8.1.1 The Binary Tree Theorem

8.1.2 External Path Length

8.1.3 Traversals of a Binary Tree

8.2 Binary Search Trees

8.2.1 The BinSearchTree Class

8.2.2 Fields and Embedded Classes in the BinSearchTree Class

8.2.3 Implementation of the BinSearchTree Class

8.2.4 The remove Method

8.2.5 The TreeIterator Class

Lab 18: A Run-Time Estimate of the Average Height of a BinSearchTree Object

Summary

Exercises

Programming Project 8.1: An Alternative Design and Implementation of the Binary-Search-Tree Data Structure

Chapter9 Balanced Binary Search Trees

Chapter Objectives

9.1 A Problem with Binary Search Trees

9.2 Rotations

9.3 AVL Trees

9.3.1 The Height of an AVL Tree

9.3.2 The AVLTree Class

9.3.3 The fixAfterInsertion Method

9.3.4 Correctness of the add Method

9.4 Red-Black Trees

9.4.1 The Height of a Red-Black Tree

Summary

Exercises

Programming Project 9.1: Defining the remove Method in the AVLTree Class

Chapter10 Tree Maps and Tree Sets

Chapter Objectives

10.1 The TreeMap Class

10.1.1 Method Descriptions of the TreeMap Class

10.1.2 The Fields in the TreeMap Class

10.1.3 The Comparator and Comparable Classes

10.1.4 The Entry Class

10.1.5 Implementation of the TreeMap Class

10.1.6 The fixAfterInsertion Method

10.1.7 Three Cases of Insertion

Lab 19: A Red-Black Tree Insertion with All Three Cases

10.1.8 More TreeMap Methods

10.1.9 The fixAfterInsertion Method

Lab 20: A Red-Black Tree Removal with All Four Cases

10.1.10 The entrySet Method

10.2 Application: TreeMap Objects: A Simple Thesaurus

10.2.1 Design and Implementation of the Thesaurus Class

10.2.2 Disign and Implementation of the ThesaurusDriver Class

10.3 The TreeSet Class

10.3.1 Design and Implementation of the TreeSet Class

10.4 Application: A Simple Spell-Checker

10.4.1 Design and Implementation of the SpellChecker Class

10.4.2 Design and Implementation of the SpellCheckerDriver Class

Summary

Exercises

Programming Project 10.1: Enhancing the SpellChecker Project

Programming Project 10.2: Determining Word Frequencies

Programming Project 10.3: Building a Concordance

Chapter11 Priority Queues

Chapter Objectives

11.1 Introduction

11.2 Definition of the PriorityQueue Interface

11.3 Implementations of the PriorityQueue Interface

11.3.1 The Heap Class

11.3.2 Fields in the Heap Class

11.3.3 Implementation of the Heap Class

11.3.4 The percolateUp Method

11.3.5 The percolateDown Method

Lab 21: Incorporating Fairness in Heaps

11.4 Application: Huffman Codes

11.4.1 Huffman Tree

11.4.2 Greedy Algorithms

11.4.3 The Huffman Class

Summary

Exercises

Programming Project 11.1: Decoding a Huffman-Encoded Message

Chapter12 Sorting

Chapter Objectives

12.1 Introduction

12.2 Insertion Sort

12.3 How Fast Can We Sort?

12.4 Fast Sorts

12.4.1 Merge Sort

12.4.2 Tree Sort

12.4.3 Heap Sort

12.4.4 Quick Sort

Lab 22: Run-times for Sort Methods

Summary

Exercises

Programming Project 12.1: File Sorting

Chapter13 Searching and The Hash Classes

Chapter Objectives

13.1 A Framework to Analyze Searching

13.2 Review of Searching

13.2.1 Sequential Search

13.2.2 Binary Search

13.2.3 Red-Black-Tree Search

13.3 The HashMap Class

13.3.1 Method Descriptions in the HashMap Class

13.3.2 Fields in the HashMap Class

13.3.3 Hashing

13.3.4 The hashCode Method

13.3.5 The Uniform Hashing Assumption

13.3.6 Chaining

13.3.7 Implementation of the HashMap Class

13.3.8 Analysis of Chained Hashing

13.3.9 The HashIterator Class

13.4 The HashSet Class

Lab 23: Timing the Hash Classes

13.5 Open-Address Hashing

13.5.1 The remove Method