內容介紹
內容簡介這是一本讓讀者在現代程式設計環境中學習如何生成和
分析常用數據結構的教材。書中介紹了如何用Java語言設計
與實現傳統的數據結構。不書有下列特點：
用Java這一開放的、純面向對象的語言作為描述語言。
採用面向對象方法來設計傳統的數據結構；引入類、界面、
繼承、封裝等思想。
全書結構嚴謹，前後連線自然，內容簡潔而又清晰。
使用適應於事物本身規律的方法來描述事物，亦即用對象、
類這一封裝了數據和操作的結構來描述數據組織。
不僅講述了如何用Java實現數據結構，而且抽象出一般的設計
原則；掌握並靈活運用這些原則，可以使讀者受益非淺。
書中有50多個已實現並經過測試的類。這些類構成一個結構
包，可以作為程式設計師編程的基礎。
書中有大量實例，告訴讀者如何去使用定義好的數據結構。
每一章後有大量精心設計的提問，可以幫助讀者複習和進一
步提高。
本書適合於本科高年級學生使用。本書附錄A雖有Java語
言的簡介，但對不熟悉Java語言的讀者，建議最好在學習本
書前花上幾周時間了解Java語言。
作品目錄
ContentsPreface
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 Sketching an Example: A Word List
1.5 A Special Purpose Class: A Bank Account
1.6 A General Purpose Class: An Association
1.7 Interfaces
1.8 Who Is the User?
1.9 Conclusions
2 Comments, Conditions, and Assertions
2.1 Pre- and Postconditions
2.2 Assertions
2.3 Craftsmanship
2.4 Conclusions
3 Vectors
3.1 Application: The Word List Revisited
3.2 Application: Word Frequency
3.3 The Interface
3.4 The Implementation
3.5 Extensibility: A Feature
3.6 Application: The Matrix Class
3.7 Conclusions
4 Design Fundamentals
4.1 Asymptotic Analysis Tools
4.1.1 Time and Space Complexity
4.1.2 Examples
4.1.3 The Trading of Time and Space
4.2 Self-Reference
4.2.1 Recursion
4.2.2 Mathematical Induction
4.3 Properties of Design
4.3.1 Symmetry
4.3.2 Friction
4.4 Conclusionp
5 Sorting
5.1 Approaching the Problem
5.2 Selection Sort
5.3 Insertion Sort
5.4 Mergesort
5.5 Quicksort
5.6 Sorting Objects
5.7 Vector-Based Sorting
5.8 Conclusions
6 Lists
6.1 Example: A Unique Program
6.2 Example: Free-Lists
6.3 Implementation: Singly-Linked Lists
6.4 Implementation: Doubly-Linked Lists
6.5 Implementation: Circularly-Linked Lists
6.6 Conclusions
7 Linear Structures
7.1 Stacks
7.1.1 Example: Simulating Recursion
7.1.2 Vector-Based Stacks
7.1.3 List-Based Stacks
7.1.4 Comparisons
7.2 Queues
7.2.1 Example: Solving a Coin Puzzle
7.2.2 List-Based Queues
7.2.3 Vector-Based Queues
7.2.4 Array-Based Queues
7.3 Example: Solving Mazes
7.4 Conclusions
8 Iterators
8.1 Java's Enumeration Interface
8.2 The Iterator Interface
8.3 Example: Vector Iterators
8.4 Example: List Iterators
8.5 Example: Filtering Iterators
8.6 Conclusions
9 Ordered Structures
9.1 Comparable Objects
9.1.1 Example: Comparable Integers
9.1.2 Example: Comparable Associations
9.2 Keeping Structures Ordered
9.2.1 The OrderedStructure Intertace
9.2.2 The Ordered Vector
9.2.3 Example: Sorting
9.2.4 The Ordered List
9.2.5 Example: The Modified Parking Lot
9.3 Conclusions
10 Trees
10.1 Terminology
10.2 The Interface
10.3 Motivating Example: Expression Trees
10.4 Implementation
10.4.1 The BinaryTreeNode Implementation
10.4.2 Implementation of the BinaryTree Wrapper
10.5 Traversals
10.5.1 Preorder Traversal
10.5.2 Inorder Traversal
10.5.3 Postorder Traversal
10.5.4 Levelorder Traversal
10.5.5 Recursion in Iterators
10.6 Property-Based Methods
10.7 Example: Huffman Compression
10.8 Conclusions
11 Priority Queues
11.1 The Interface
11.2 Example: Improving the Huffman Code
11.3 Priority Vectors
11.4 A Heap Implementation
11.4.1 Vector-Based Heaps
11.4.2 Example: Heapsort
11.4.3 Skew Heaps
11.5 Example: Circuit Simulation
11.6 Conclusions
12 Search Trees
12.1 Binary Search Trees
12.2 Example: Tree Sort
12.3 Implementation
12.4 Splay Trees
12.5 Splay Tree Implementation
12.6 Conclusions
13 Dictionaries
13.1 The Interface
13.2 Unit Cost Dictionaries: Hash Tables
13.2.1 Open Addressing
13.2.2 External Chaining
13.2.3 Generation of Hash Codes
13.2.4 Analysis
13.3 Ordered Dictionaries and Tables
13.4 Example: Document Indexing
13.5 Conclusions
14 Graphs
14.1 Terminology
14.2 The Graph Interface
14.3 Implementations
14.3.1 Abstract Classes
14.3.2 Adjacency Matrices
14.3.3 Adjacency Lists
14.4 Examples: Common Graph Algorithms
14.4.1 Reachability
14.4.2 Topological Sorting
14.4.3 Transitive Closure
14.4.4 All Pairs Minimum Distance
14.4.5 Greedy Algorithms
14.5 Conclusions
A A Sip of Java
A.l A First Program
A.2 Declarations
A.2.1 Primitive Types
A.2.2 Reference Types
A.3 Important Classes
A.3.l The ReadStream Class
A.3.2 PrintStreams
A.3.3 Strings
A.4 Control Constructs
A.4.l Conditional Statements
A.4.2 Loops
A.5 Methods
A.6 Inheritance and Subtyping
A.6.l Inheritance
A.6.2 Subtyping
A.6.3 Interfaces and Abstract Classes
B Use of the Keyword Protected
C Principles
D Structure Package Hierarchy
E Selected Answers
Index
