具体描述
内容简介
这是一本让读者在现代程序设计环境中学习如何生成和
分析常用数据结构的教材。书中介绍了如何用Java语言设计
与实现传统的数据结构。不书有下列特点：
用Java这一开放的、纯面向对象的语言作为描述语言。
采用面向对象方法来设计传统的数据结构；引入类、界面、
继承、封装等思想。
全书结构严谨，前后连接自然，内容简洁而又清晰。
使用适应于事物本身规律的方法来描述事物，亦即用对象、
类这一封装了数据和操作的结构来描述数据组织。
不仅讲述了如何用Java实现数据结构，而且抽象出一般的设计
原则；掌握并灵活运用这些原则，可以使读者受益非浅。
书中有50多个已实现并经过测试的类。这些类构成一个结构
包，可以作为程序员编程的基础。
书中有大量实例，告诉读者如何去使用定义好的数据结构。
每一章后有大量精心设计的提问，可以帮助读者复习和进一
步提高。
本书适合于本科高年级学生使用。本书附录A虽有Java语
言的简介，但对不熟悉Java语言的读者，建议最好在学习本
书前花上几周时间了解Java语言。
作者简介
目录信息
Preface
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
· · · · · · (收起)
读后感
用户评价
这本书的排版和纸张质量也值得一提。在长时间阅读技术书籍时，眼睛的舒适度至关重要。这本书采用了高质量的哑光纸张，有效减少了反光，长时间盯着屏幕后的我，拿起这本书时感到非常放松。文字间距和行距的设置也恰到好处，无论是阅读复杂的递归定义，还是对照大段的代码块，都不会产生阅读上的疲劳感。特别是那些涉及到算法流程的示意图，线条清晰，色彩运用得当（尽管主要还是黑白灰的组合，但层次分明），极大地帮助了对动态过程的理解。我发现自己很少需要来回翻页来确认某个变量的定义或上一步的推导，这很大程度上归功于作者和编辑团队在细节处理上的用心。一本好的技术书，不仅仅是内容的载体，它本身也是一种精心设计的用户体验，这一点，这本书做到了极致。它让学习过程本身，变成了一种享受。
这本书的行文风格非常独特，它既有学术著作的严谨性，又流露出一种久经沙场的工程师的务实精神。作者似乎很清楚，一个初学者和一个经验丰富的开发者在面对同一个问题时，关注点是不同的。因此，在讲解完基础的实现后，总会有一个“深入探讨”或者“工程考量”的章节。例如，在讲解哈希表时，除了标准的拉链法和开放寻址法，作者还花了不少篇幅讨论了Java 8中HashMap的优化策略，包括链表转化为红黑树的阈值设置。这种与时俱进的讨论，让这本书即便在技术快速迭代的今天，依然保持着很高的参考价值。它不仅仅是教授“如何做”，更是在探讨“为什么现有最好的方案是这样设计的”，这对于希望成为架构师级别的开发人员来说，是极其宝贵的思维训练。它培养的不是代码工人，而是算法的建筑师。
这本书的封面设计得相当有品位，那种深邃的蓝色调搭配简洁的字体，一眼就能看出这是一本严肃的技术著作。我拿到书后，立刻被它扎实的理论功底所吸引。作者显然在数据结构领域浸淫多年，对算法的理解绝非停留在表面。比如，在讲解树这种复杂结构时，他没有采用那种流水账式的描述，而是深入剖析了其背后的数学原理和逻辑推导过程。特别是关于红黑树的平衡机制，他用了好几页篇幅，结合图示和伪代码，将枯燥的旋转和着色规则讲得如同侦探小说般引人入胜，让你在理解的同时，还能体会到设计的精妙。这种对细节的苛求，使得即便是初次接触这些高级数据结构的读者，也能建立起一个坚实的概念基础。书中的代码示例也经过了精心的打磨，Java语言的特性被展现得淋漓尽致，每一个类和方法的命名都力求清晰、准确，体现了专业程序员的素养。我个人非常欣赏作者那种“授人以渔”的教学理念，比起直接抛出标准答案，他更侧重于引导读者思考“为什么是这样设计”。这种深度的探讨，远超出了普通教材的范畴，更像是一本与资深工程师的私密对话录。
对我来说，这本书最核心的价值在于它对“设计原则”的强调，这部分内容往往是其他同类书籍所忽略的。作者没有把Java看作是一堆固定的语法规则，而是将其视为实现数据结构抽象的最佳工具。例如，在设计栈和队列的接口时，他非常强调契约（Contract）的重要性，如何利用泛型确保类型安全，以及如何使用内部类或匿名内部类来封装特定实现细节，保持API的简洁性。读完这部分的章节，我开始重新审视自己过去项目中那些“凑合着用”的集合类实现，深刻理解到良好的抽象和封装对于长期维护的深远影响。这本书不仅仅是关于数据结构，它更像是一本关于如何用Java语言的哲学思想去构建高效、优雅的底层支撑系统的实践指南。它教会我的远不止是如何写一个快速排序算法，而是如何像一名优秀的软件工程师那样去思考问题的结构和实现方式。
当我翻阅到关于图论算法的部分时，那种豁然开朗的感觉尤为强烈。以往我接触的很多资料，在处理最小生成树或者最短路径问题时，往往只是罗列出Prim或Dijkstra算法的步骤，然后就结束了。然而，这本书的处理方式完全不同。它没有回避那些计算复杂度上的细微差别和适用场景的边界条件。作者详细对比了邻接矩阵和邻接表在不同图密度下的性能表现，并用严谨的数学语言阐述了为何在某些情况下，一种表示法会显著优于另一种。更令人称赞的是，作者非常注重“设计原则”的体现。他不仅展示了如何实现这些算法，更阐释了在Java环境下，如何通过接口和抽象类来构建一个灵活、可扩展的图模型框架。这种面向对象的设计思维贯穿始终，让你在学习具体算法的同时，也在潜移默化中提升了自己构建健壮软件系统的能力。这种层次感，是市面上很多只注重功能的工具书所无法比拟的，它真正做到了理论与实践的完美融合。
