外科学

内容：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
13.5.2 Primary Clustering
13.5.3 Double Hashing
13.5.4 Analysis of Open-Address Hashing
Summary
Exercises
Programming Project 13.1: Comparing Chained Hashing and Open-Address Hashing

Chapter14 Graphs, Trees, and Networks
Chapter Objectives
14.1 Undirected Graphs
14.2 Directed Graphs
14.3 Trees
14.4 Networks
14.5 Graph Algorithms
14.5.1 Iterators
14.5.2 Connectedness
14.5.3 Generating a Minimum Spanning Tree
14.5.4 Finding the Shortest Path through a Network
14.6 Developing a Network Class
14.6.1 Method Descriptions in the Network Class
14.6.2 Fields in the Network Class
14.6.3 Implementation of the Network Class
Lab 24: The Traveling Salesperson Problem
14.6.4 An Alternative Design and Implementation of the Network Class
14.7 Backtracking through a Network
Summary
Exercises
Programming Project 14.1: Completing the Implementation of the Network Class under the Adjacency-Matrix Design
Programming Project 14.2: A Network Search

Appendix 1 Mathematical Background
A1.1 Introduction
A1.2 Functions and Sequences
A1.3 Sums and Products
A1.4 Logarithms
A1.5 Methematical Induction
A1.5.1 Induction and Recursion
Exercises

Appendix 2 The GUI and GUIListener Classes
A2.1 Introduction
A2.2 Threads
A2.3 Implementing the Process Interface
A2.4 The GUI Class
A2.4.1 The GUI Constructor
A2.4.2 The Other Methods in the GUI Class
A2.5 The GUIListener Class
A2.6 Putting It All Together

Appendix 3 The Java Collections Framework
A3.1 Introduction
A3.2 The Collection Interface
A3.3 The List Interface
A3.4 The ListIterator Interface
A3.5 The Set Interface
A3.6 The Map Interface
A3.6.1 The Entry Interface within the Map Interface
A3.7 The ArrayList Class
A3.8 The LinkedList Class
A3.8.1 The ListItr Class within the LinkedList Class
A3.9 The TreeSet Class
A3.10 The TreeMap Class
A.3.10.1 The Iterator Class within the TreeMap Class
A3.11 The HashSet Class
A3.12 The HashMap Class
A3.12.1 The HashIterator Class within the HashMap Class

Bibliography
Index