数据结构Java语言描述（第2版·影印版） (2008 年度畅销榜NO.6376 )

本书为数据结构的教材，讲述如何用开放的、纯面向对象的Java作为描述语言来设计和实现传统的数据结构。全书结构严谨，讲解清晰，提供了大量示例，使读者不仅能学习数据结构的具体实现，而且抽象出一般的设计原则，掌握并灵活运用这些原则，将使读者受益非浅。
本书可作为计算机及相关专业的数据结构课程的教材。对于不熟悉Java语言的读者，建议先进行附录B的Java语言学习。

Preface to First Edition
Preface to the Second Edition

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 Vectors

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 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.1.4 Back-of-the-Envelope Estimations
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 Conclusions
4.5 Laboratory: How Fast Is Java?

5 Sorting
5.1 Approaching the Problem
5.2 Selection Sort
5.3 Insertion Sort
5.4 Mergesort
5.5 Quicksoft
5.6 Radix Sort
5.7 Sorting Objects
5.8 Ordering Objects Using Comparators
5.9 Vector-Based Sorting
5.10 Conclusions
5.11 Laboratory: Sorting with Comparators

6 A Design Method
6.1 The Interface-Based Approach
6.1.1 Design of the Interface
6.1.2 Development of an Abstract Implementation
6.1.3 Implementation
6.2 Example: Development of Generators
6.3 Example: Playing Cards
6.4 Conclusions

7 Iterators
7.1 Java's Enumeration Interface
7.2 The Iterator Interface
7.3 Example: Vector Iterators
7.4 Example: Rethinking Generators
7.5 Example: Filtering Iterators
7.6 Conclusions
7.7 Laboratory: The Two-Towers Problem

8 Lists
8.1 Example: A Unique Program
8.2 Example: Free Lists
8.3 Partial Implementation: Abstract Lists
8.4 Implementation: Singly Linked Lists
8.5 Implementation: Doubly Linked Lists
8.6 Implementation: Circularly Linked Lists
8.7 Implementation: Vectors
8.8 List Iterators
8.9 Conclusions
8.10 Laboratory: Lists with Dummy Nodes

9 Linear Structures
9.1 Stacks
9.1.1 Example: Simulating Recursion
9.1.2 Vector-Based Stacks
9.1.3 List-Based Stacks
9.1.4 Comparisons
9.2 Queues
9.2.1 Example: Solving a Coin Puzzle
9.2.2 List-Based Queues
9.2.3 Vector-Based Queues
9.2.4 Array-Based Queues
9.3 Example: Solving Mazes
9.4 Conclusions
9.5 Laboratory: A Stack-Based Language
9.6 Laboratory: The Web Crawler

10 Ordered Structures
10.1 Comparable Objects Revisited
10.1.1 Example: Comparable Ratios
10.1.2 Example: Comparable Associations
10.2 Keeping Structures Ordered
10.2.1 The OrderedStructure Interface
10.2.2 The Ordered Vector and Binary Search
10.2.3 Example: Sorting Revisited
10.2.4 A Comparator-based Approach
10.2.5 The Ordered List
10.2.6 Example: The Modified Parking Lot
10.3 Conclusions
10.4 Laboratory: Computing the "Best Of"

11 Binary Trees
11.1 Terminology
11.2 Example: Pedigree Charts
11.3 Example: Expression Trees
11.4 Implementation
11.4.1 The BinaryTree Implementation
11.5 Example: An Expert System
11.6 Traversals of Binary Trees
11.6.1 Preorder Traversal
11.6.2 In-order Traversal
11.6.3 Postorder Traversal
11.6.4 Level-order Traversal
11.6.5 Recursion in Iterators
11.7 Property-Based Methods
11.8 Example: Huffman Compression
11.9 Example Implementation: Ahnentafel
11.10Conclusions
11.11Laboratory: Playing Gardner's Hex-a-Pawn

12 Priority Queues
12.1 The Interface
12.2 Example: Improving the Huffman Code
12.3 A Vector-Based Implementation
12.4 A Heap Implementation
12.4.1 Vector-Based Heaps
12.4.2 Example: Heapsort
12.4.3 Skew Heaps
12.5 Example: Circuit Simulation
12.6 Conclusions
12.7 Laboratory: Simulating Business

13 Search Trees
13.1 Binary Search Trees
13.2 Example: Tree Sort
13.3 Example: Associative Structures
13.4 Implementation
13.5 Splay Trees
13.6 Splay Tree Implementation
13.7 An Alternative:Red-Black Trees
13.8 Conclusions
13.9 Laboratory: Improving the BinarySearchTree

14 Maps
14.1 Example Revisited: The Symbol Table
14.2 The Interface
14.3 Simple Implementation: MapList
14.4 Constant Time Maps: Hash Tables
14.4.1 Open Addressing
14.4.2 External Chaining
14.4.3 Generation of Hash Codes
14.4.4 Hash Codes for Collection Classes
14.4.5 Performance Analysis
14.5 Ordered Maps and Tables
14.6 Example: Document Indexing
14.7 Conclusions
14.8 Laboratory: The Soundex Name Lookup System

15 Graphs
15.1 Terminology
15.2 The Graph Interface
15.3 Implementations
15.3.1 Abstract Classes Reemphasized
15.3.2 Adjacency Matrices
15.3.3 Adjacency Lists
15.4 Examples: Common Graph Algorithms
15.4.1 Reachability
15.4.2 Topological Sorting
15.4.3 Transitive Closure
15.4.4 All Pairs Minimum Distance
15.4.5 Greedy Algorithms
15.5 Conclusions
15.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 ReadStream Class
B.3.2 The PrintStream Class
B.3.3 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

E Environments
E.1 Downloading Software
E.2 Creating Libraries
E.3 Creating Project Stationery

F Further Reading

G Glossary
Index

Preface to the First Edition "IT'S A WONDERFUL TIME TO BE ALIVE." At least that's what I've found myself saying over the past couple of decades. When I first started working with computers, they were resources used by a privileged (or in my case, persistent) few. They were physically large, and logically small. They were cast from iron. The challenge was to make these behemoths solve complex problems quickly. Today, computers are everywhere. They are in the office and at home. They speak to us on telephones; they zap our food in the microwave. They make starting cars in New England a possibility. Everyone's using them. What has aided their introduction into society is their diminished size and cost, and increased capability. The challenge is to make these behemoths solve complex problems quickly. Thus, while the computer and its applications have changed over time, the challenge remains the same: How can we get the best performance out of the current technology? The design and analysis of data structures lay the fundamental groundwork for a scientific understanding of what computers can do efficiently. The motivations for data structure design work accomplished three decades ago in assembly language at the keypunch are just as familiar to us today as we practice our craft in modern languages on computers on our laps. The focus of this material is the identification and development of relatively abstract principles for structuring data in ways that make programs efficient in terms of their consumption of resources, as well as efficient in terms of "programmability." In the past, my students have encountered this material in Pascal, Modula-2, and, most recently, C++. None of these languages has been ideal, but each has been met with increasing expectation. This text uses The Java Programming Language1--"Java"--to structure data. Java is a new and exciting language that has received considerable public attention. At the time of this writing, for example, Java is one of the few tools that can effectively use the Internet as a computing resource. That particular aspect of Java is not touched on greatly in this text. Still, Internet-driven applications in Java will need supporting data structures. This book attempts to provide a flesh and focused approach to the design and implementation of classic structures in a manner that meshes well with existing Java packages. It is hoped that learning this material in Java will improve the way working programmers craft programs, and the way future designers craft languages. Pedagogical Implications. This text was developed specifically for use with CS2 in a standard Computer Science curriculum. It is succinct in its approach, and requires, perhaps, a little more effort to read. I hope, though, that this text becomes not a brief encounter with object-oriented data structure design, but a touchstone for one's programming future. The material presented in this text follows the syllabus I have used for several years at Williams. As students come to this course with experience using Java, the outline of the text may be followed directly. Where students are new to Java, a couple of weeks early in the semester will be necessary with a good companion text to introduce the student to new concepts, and an introductory Java language text or reference manual is recommended. For students that need a quick introduction to Java we provide a tutorial in Appendix B. While the text was designed as a whole, some may wish to eliminate less important topics and expand upon others. Students may wish to drop (or consider!) the section on induction (Section 4.2.2). The more nontraditional topics--including, for example, iteration and the notions of symmetry and friction--have been included because I believe they arm programmers with important mechanisms for implementing and analyzing problems. In many departments the subtleties of more advanced structures--maps (Chapter 14) and graphs (Chapter 15)--may be considered in an algorithms course. Chapter 5, a discussion of sorting, provides very important motivating examples and also begins an early investigation of algorithms. The chapter may be dropped when better examples are at hand, but students may find the refinements on implementing sorting interesting. Associated with this text is a Java package of data structures that is freely available over the Internet for noncommercial purposes. I encourage students, educators, and budding software engineers to download it, tear it down, build it up, and generally enjoy it. In particular, students of this material are encouraged to follow along with the code online as they read. Also included is extensive documentation gleaned from the code by java doc. All documentation--within the book and on the Web--includes pre- and post conditions. The motivation for this style of commenting is provided in Chapter 2. While it's hard to be militant about commenting, this style of documentation provides an obvious, structured approach to minimally documenting one's methods that students can appreciate and users will welcome. These resources, as well as many others, are available from McGraw-Hill at http://www.mhhe, com/java structures. Three icons appear throughout the text, as they do in the margin. The top "compass" icon highlights the statement of a principle--a statement that encourages abstract discussion. The middle icon marks the first appearance of a particular class from the structure package. Students will find these files at McGraw-Hill, or locally, if they've been downloaded. The bottom icon similarly marks the appearance of example code. Finally, I'd like to note an unfortunate movement away from studying the implementation of data structures, in favor of studying applications. In the extreme this is a disappointing and, perhaps, dangerous precedent. The design of a data structure is like the solution to a riddle: the process of developing the answer is as important as the answer itself. The text may, however, be used as a reference for using the structure package in other applications by selectively avoiding the discussions of implementation. Preface to the Second Edition Since the first edition of Java Structures support for writing programs in Java 2 has grown considerably. At that time the Java Development Toolkit consisted of 504 classes in 23 packages3 In Java 1.2 (also called Java 2) Sun rolled out 1520 classes in 59 packages. This book is ready for Java 1.4, where the number of classes and packages continues to grow. Most computer scientists are convinced of the utility of Java for programming in a well structured and platform independent manner. While there are still significant arguments about important aspects of the language (for example, support for generic types), the academic community is embracing Java, for example, as the subject of the Computer Science Advanced Placement Examination. It might seem somewhat perplexing to think that many aspects of the original Java environment have been retracted (or deprecated) or reconsidered. The developers at Sun have one purpose in mind: to make Java the indispensable language of the current generation. As a result, documenting their progress on the development of data structures gives us valuable insight into the process of designing useful data structures for general purpose programming. Those students and faculty considering a move to this second edition of Java Structures will see first-hand some of the decisions that have been made in the intervening years. During that time, for example, the Collection-based classes were introduced, and are generally considered an improvement. Another force--one similar to calcification--has left a trail of backwards compatible features that are sometimes difficult to understand. For example, the Iterator class was introduced, but the Enumeration class was not deprecated. One subject of the first edition--the notion of Comparable classes--has been introduced into a number of important classes including String and Integer. This is a step forward and a reconsideration of what we have learned about that material has lead to important improvements in the text. Since the main purpose of the text is to demonstrate the design and behavior of traditional data structures, we have not generally tracked the progress of Java where it blurs the view. For example, Java 2 introduces a List interface (we applaud) but the Vector class has been extended to include methods that are, essentially, motivated by linked lists (we wonder). As this text points out frequently, the purpose of an interface is often to provide reduced functionality. If the data structure does not naturally provide the functionality required by the application, it is probably not an effective tool for solving the problem: search elsewhere for an effective structure. As of this writing, more than 100,000 individuals have searched for and downloaded the structure package. To facilitate using the comprehensive~ set of classes with the Java 2 environment, we have provided a number of features that support the use of the structure package in more concrete applications. Please see Appendix C. Also new to this edition are more than 200 new problems, several dozen exercises, and over a dozen labs we regularly use at Williams. Acknowledgments. Several students, instructors, and classes have helped to shape this edition of Java Structures. Parth Doshi and Alex Glenday--diligent Williams students--pointed out a large number of typos and stretches of logic. Kim Bruce, Andrea Danyluk, Jay Sachs, and Jim Teresco have taught this course at Williams over the past few years, and have provided useful feedback. I tip my hat to Bill Lenhart, a good friend and advisor, who has helped improve this text in subtle ways. To Sean Sandys I am indebted for showing me new ways to teach new minds. The various reviewers have made, collectively, hundreds of pages of comments that have been incorporated (as much as possible) into this edition:Eleanor Hare and David Jacobs (Clemson University), Ram Athavale (North Carolina State University), Yannick Daoudi (McGill University), Walter Daugherty (Texas A&M University), Subodh Kumar (Johns Hopkins University), Toshimi Minoura (Oregon State University), Carolyn Schauble (Colorado State University), Val Tannen (University of Pennsylvania), Frank Tompa (University of Waterloo), Richard Wiener (University of Colorado at Colorado Springs), Cynthia Brown Zickos (University of Mississippi), and my good friend Robbie Moll (University of Massachusetts). Deborah Trytten (University of Oklahoma) has reviewed both editions! Still, until expert authoring systems are engineered, authors will remain human. Any mistakes left behind or introduced are purely those of the author. The editors and staff at McGraw-Hill-Kelly Lowery, Melinda Dougharty, John Wannemacher, and Joyce Berendes-have attempted the impossible: to keep me within a deadline. David Hash, Phil Meek, and Jodi Banowetz are responsible for the look and feel of things. I am especially indebted to Lucy Mullins, Judy Gantenbein, and Patti Evers whose red pens have often shown me a better way. Betsy Jones, publisher and advocate, has seen it all and yet kept the faith: thanks. Be aware, though: long after these pages are found to be useless folly, my best work will be recognized in my children, Kate, Megan, and Ryan. None of these projects, of course, would be possible without the support of my best friend, my north star, and my partner, Mary. Enjoy!