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

　　本书着重阐述数据结构的基础知识及其Java语言实现。学生通过对书中编程项目和实验的实践和训练，可加深对基本概念和方法的理解和掌握，并可直接了解实际当中的应用。本书的主要特点包括：全面涵盖了数据结构与Java类集框架的内容，尤其介绍了重要数据结构的实现，如表、树和Hash表等；运用简单的图形用户接口作为输入/输出，以使学生能更好地理解在实际当中普遍应用的事件驱动程序设计方法；本书含有大量的例题和练习、应用案例和实例，以加强学生的实际训练。本书前言进入21世纪，尤其随着我国加入WTO，信息产业的国际竞争将更加激烈。我国信息产业虽然在20世纪末取得了迅猛发展，但与发达国家相比，甚至与印度、爱尔兰等国家相比，还有很大差距。国家信息化的发展速度和信息产业的国际竞争能力，最终都将取决于信息科学技术人才的质量和数量。引进国外信息科学和技术优秀教材，在有条件的学校推动开展英语授课或双语教学，是教育部为加快培养大批高质量的信息技术人才采取的一项重要举措。为此，教育部要求由高等教育出版社首先开展信息科学和技术教材的引进试点工作。同时提出了两点要求，一是要高水平、二是要低价格。在高等教育出版社和信息科学技术引进教材专家组的努力下，经过比较短的时间，第一批引进的20多种教材已经陆续出版。这套教材出版后受到了广泛的好评、其中有不少是世界信息科学技术领域著名专家、教授的经典之作和反映信息科学技术最新进展的优秀作品，代表了目前世界信息科学技术教育的一流水平，而且价格也是最优惠的，与国内同类自编教材相当。这项教材引进工作是在教育部高等教育司和高教社的共同组织下，由国内信息科学技术领域的专家、教授广泛参与，在对大量国外教材进行多次遴选的基础上，参考了国内和国外著名大学相关专业的课程设置进行系统引进的。其中，JohnWiley公司出版的贝尔实验室信息科学研究中心副总裁Silberschatz教授的经典著作《操作系统概念》，是我们经过反复谈判，做了很多努力才得以引进的。WilliamStallihgs先生曾编写了在美国深受欢迎的信息科学技术系列教材，其中有多种教材获得过美国教材和学术著作者协会颁发的计算机科学与工程教材奖，这批引进教材中就有他的两本著作。留美中国学者JiaweiHan先生的《数据挖掘》是该领域中具有里程碑意义的著作。由达特茅斯学院的ThomasCormen和麻省理工学院、哥伦比亚大学的几位学者共同编著的经典著作《算法导论》，在经历了11年的锤炼之后于2001年出版了第二版。目前任教于美国Massachusetts大学的JamesKurose教授，曾在美国三所高校先后10次获得杰出教师或杰出教学奖，由他主编的《计算机网络》出版后，以其体系新颖、内容先进而倍受欢迎。在努力降低引进教材售价方面，高等教育出版社做了大量和细致的工作。这套引进的教材体现了权威性、系统性、先进性和经济性等特点。

　　作者WilliamJ.Collins现在美国Lafayette学院计算机系从事数据结构课程的教学。

内容：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