Java软件结构与数据结构
2009-9
清华大学出版社
（美）刘易斯，（美）切斯 著
526
This book is designed to serve as a text for a course on data structures and algo-rithms. This course is typically referred to as the CS2 course because it is oftentaken as the second course in a computing curriculum. We have designed thisbook to embrace the tenets of Computing Curricula 2001 （CC2001）. Pedagogically, this book follows the style and approach of the leading CS1book Java Software Solutions: Foundations of Program Design, by John Lewisand William Loftus. Our book uses many of the highly regarded features of thatbook, such as the Key Concept boxes and complete code examples. Together,these two books support a solid and consistent approach to either a two-courseor three-course introductory sequence for computing students. That said, thisbook does not assume that students have used Java Sofware Solutions in a previ-ous course. Material that might be presented in either course （such as recursion or sorting）is presented in this book as well. We also include strong reference material pro-viding an overview of object-oriented concepts and how they are realized in Java. We understand the crucial role that the data structures and algorithms courseplays in a curriculum and we think this book serves the needs of that course well.The Third EditionWe have made some key modifications in this third edition to enhance its peda-gogy. The most important-change is a fundamental reorganization of material thatis designed to create a cleaner flow of topics. Instead of having an early, largechapter to review obiect-oriented concepts, weve included that material as anappendix for reference. Then we review concepts as needed and appropriate in thecontext of the implementation strategies discussed throughout the book and citethe appropriate reference material. This not only links the topics in a timely fash-ion but also demonstrates the usefulness of particular language constructs. Weve expanded the discussion of Analysis of Algorithms, and given it its ownchapter. The discussion, however, stays at an appropriately moderate level. Ourstrategy is to motivate the concepts involved in the analysis of algorithms, layinga solid foundation, rather than get embroiled in too much formality.
本书是著名作者John Lewis与William Loftus作为其一流的CS1教材“Java Software Solutions：Foundations of Program Design”的姊妹篇。尽管本书的英文名为“Java Software Structures: Designing and Using Data Structures”，但正如作者在前言中所说的那样，本书其实是一本可作为“数据结构与算法”课程的教材。根据使用了前两版的教师和学生的反馈，作者在第3版中进行了重大修改，以适应教学的需要。 本书关注的是数据结构和算法背后的核心设计问题。在展现每种集合时，本书都是先探讨该集合的一般概念，接着再讨论该集合在问题求解中的用法，最后讨论了各种候选实现方案。因此，本书是“数据结构与算法”Java语言描述课程的理想教材。
ContentsPreface Chapter 1 Introduction 1.1 Soffware Quality Correctness Reliability Robustness Usability Maintainability Reusability Portability Efficiency Quality Issues 1.2 Data Structures A Physical Example Containers as Objects Chapter 2 Analysis of Algorithms 2.1 Algorithm Efficiency 2.2 Growth Functions and Big-OH Notation 2.3 Comparing Growth Functions 2.4 Determining Time Complexity Analyzing Loop Execution Nested Loops Method Calls Chapter 3 Collections 3.1 Introduction to Collections Abstract Data Types The Java Collections 3.2 A Stack Collection 3.3 CruciaI OO Concepts Inheritance Class Hierarchies The Object Class Polymorphism References and Class Hierarchies Generics 3.4 A Stack ADT Interfaces 3.5 Using Stacks：Evaluating Postfix Expressions 3.6 Exceptions Exception Messages The try Statement Exception Propagation 3.7 Implementing a Stack：With Arrays Managing Capacity 3.8 The ArrayStack Class The Constructors The push operation The pop operation The peek operation 0ther OperationsChapter 4 Linked Structures 4.1 References as Links 4.2 Managing Linked Lists Accessing Elements Inserting Nodes Deleting Nodes Sentinel Nodes 4.3 Elements Without Links Doubly Linked Lists 4.4 Implementing a Stack：With Links The LinkedStack Class ……Chapter 5 Queues Chapter 6 Lists Chapter 7 RecursionChapter 8 Sorting and Searching Chapter 9 TheesChapter 10 Binary Search Thees Chapter 11 Priority Queues and HeapsChapter 12 Multi-way Search TreesChapter 13 GraphsChapter 14 Hashing Chapter 15 Sets adn MapsAppendix A UMLAppendix B Object-Oriented Design
Abstraction is another important software engineering concept. In large soft-ware systems, it is virtually impossible for any one person to grasp all of the de-tails of the system at once. Instead, the system is divided into abstract subsystemssuch that the purpose of and the interactions among those subsystems can bespecified. Subsystems may then be assigned to different developers or groups ofdevelopers that will develop the subsystem to meet its specification. An object is the perfect mechanism for creating a collection because, if it is de-signed correctly, the internal workings of an object are encapsulated from the restof the system. In almost all cases, the instance variables defined in a class shouldbe declared with private visibility. Therefore, only the methods of that class canaccess and modify them. The only interaction a user has with an object should bethrough its public methods, which represent the services that the object provides. As we progress through our exploration of collections, we will always stressthe idea of separating the interface from the implementation. Therefore, for everycollection that we examine, we should consider the following: How does the collection operate, conceptually？ How do we formally define the interface to the collection？ What kinds of problems does the collection help us solve？ In which various ways might we implement the collection？ What are the benefits and costs of each implementation？ Before we continue, lets carefully define some other terms related to the explo-ration of collections. A data type is a group of values and the operations definedon those values. The primitive data types defined in Java are the primary exam-pies. For example, the integer data type defines a set of numeric values and theoperations （addition, subtraction, etc.） that can be used on them. An abstract data type （ADT） is a data type whose values and operations arenot inherently defined within a programming language. It is abstract only in thatthe details of its implementation must be defined and should be hidden from theuser. A collection, therefore, is an abstract data type.
