数据结构Java描述--数据结构的设计原则与Java实现

出版时间：1999-12  出版社：清华大学出版社  作者：Duane A.Bailey  页数：369  
Tag标签：无  

内容概要

这是一本让读存在现代程序设计环境中学习如何生成和分析常用数据结构的教材。书中介绍了如何用Java语言设计与实现传统的数据结构。本书目下列情点：
·用Java这一开放的、纯面向对象的语著作为描述语言。
·采用面向对象方法来设计传统的数据结构；引入类、并面、继承、封装等思想。
·全书结枸严谨，前后连接自然，内容简洁而又清晰。
·使用适应于事物本易规律的方法来描述事物，亦即用对象、类这一封装了数据和操作的结构来描还数据组织。
·不仅讲述了如何用Java实现数据结构且抽象出一般的设计原则掌握并灵活运用这些原则可以使读香受益非浅。
·书中有50多个已实现并经过测试的类。这些类构成一个结构包，可以作为程序员编程的基础。
·书中有大量实例，吉诉读著如何去使用定义好的数据结构。
·每一章后有大量精心设计的提问，目以帮助读者复习和进一步提高。
    本书适合于本科高年级学生使用。本书附录A虽有Java语言的简介，但对不熟悉Java语言的读者，建议最好在学习本书轭花上几周时间了解Java语言。

书籍目录

Preface 0 Introduction0.1 Read Me0.2 He Cant Say That, Can He?1 The Object-Oriented Method1.1 Data Abstraction and Encapsulationl.2 The Object Model1.3 Object-Oriented Terminology1.4 Sketching an Example: A Word Listl.5 A Special Purpose Class: A Bank Account1.6 AGeneral Purpose Class: An Association1.7 Interfacesl.8 Who Is the User?l.9 Conclusions2 Comments, Conditions, and Assertions2.1 Pre- and Postconditions2.2 Assertions2.3 Craftsmanship2.4 Conclusions3 Vectors3.1 Application: The Word List Revisited3.2 Application: Word Frequency3.3 The Interface3.4 The Implementation3.5 Extensibility: A Feature3.6 Application: The Matrix Class3.7 Conclusions4 Design Thndamentals4.1 Asymptotic Analysis Tools4.1.1 Time and Space Complexity4.1.2 Examples4.1.3 The Trading of Time and Space4.2 Self Reference4.2.1 Recursion4.2.2 Mathematical Induction4.3 Properties of Design4.3.1 Symmetry4.3.2 Friction4.4 Conclusions5 Sorting5.1 Approaching the Problem5.2 Selection Sort5.3 Insertion Sort5.4 Mergesort5.5 QuickPort5.6 Sorting Objects5.7 Vector-Based Sorting5.8 Conclusions6 Lists6.1 Example: A Unique Program6.2 Example: Free-Lists6.3 Implementation: Singly-Linked Lists6.4 Implementation: Doubly-Linked Lists6.5 Implementation: Circularly-Linked Lists6.6 Conclusions7 Linear Structures7.1 Stacks7.1.1 Example: Simulating Recursion7.1.2 Vector-Based Stacks7.1.3 List-Based Stacks7.1.4 Comparisons7.2 Queues7.2.1 Example: Solving a Coin Puzzle7.2.2 List-Based Queues7.2.3 Vector-Based Queues7.2.4 Array-Based Queues7.3 Example: Solving Mazes7.4 Conclusions8 Iterates 18.1 Javas Enumeration Interface8.2 The Iterate Interface8.3 Example: Vector Iterates8.4 Example: List Iterates8.5 Example: Filtering Iterates8.6 Conclusions9 Ordered Structures9.1 Comparable Objects9.1.1 Example: Comparable Integers9.1.2 Example: Comparable Associations9.2 Keeping Structures Ordered9.2.1 The OrderedStructure Interface9.2.2 The Ordered Vector9.2.3 Example: Sorting9.2.4 The Ordered List9.2.5 Example: The Modified Parking Lot9.3 Conclusions10 Thesel0.1 Terminology10.2 TheInterfacel0.3 Motivating Example: Expression Trees10.4 Implementationl0.4.1 The BinaryTreeNode Implementationl0.4.2 implementation of the BinaryTree Wrapper10.5 Traversalsl0.5.1 Preorder Traversall0.5.2 Ignored Traversall0.5.3 Postured Traversall0.5.4 Levelorder Traversal10.5.5 Recursion in Iteratesl0.6 Property-Based Methods10.7 Example: Huffman Compression10.8 Conclusions11 Priority Queuesl1.1 The Interface11.2 Example: Improving the Huffman Codel1.3 Priority Vectorsll.4 A Heap Implementation1l.4.1 Vector-Based Heapsll.4.2 Example: Heapsort11.4.3 Skew Heapsl1.5 Example: Circuit Simulationl1.6 Conclusions12 Search kneesl2.1 Binary Search Trees12.2 Example: Tree Sortl2.3 Implementation12.4 Splay Treesl2.5 Splay Tree Implementationl2.6 Conclusions13 Dictionaries13.1 TheInterfacel3.2 Unit Cost Dictionaries: Hash Tablesl3.2.1 Open Addressingl3.2.2 External Chaining13.2.3 Generation of Hash Codes13.2.4 Analysis13.3 Ordered Dictionaries and Tables13.4 Example: Document Indexing13.5 Conclusions14 Graphsl4.1 Terminologyl4.2 The Graph Interface14.3 Implementationsl4.3.1 Abstract Classes14.3.2 Adjacency Matricesl4.3.3 Adjacency Lists14.4 Examples: Common Graph Algorithmsl4.4.1 Ratability14.4.2 Topological Sorting14.4.3 Transitive Closure14.4.4 All Pairs Minimum Distance14.4.5 Greedy Algorithmsl4.5 ConclusionsA A Sip of JavaA.1 A First ProgramA.2 DeclarationsA.2.1 Primitive TypesA.2.2 Reference TypesA.3 Important ClassesA.3.1 The roadster!n ClassA.3.2 PrintStreamsA.3.3 StringsA.4 Control ConstructsA.4.1 Conditional StatementsA.4.2 LoopsA.5 MethodsA.6 Inheritance and SubtypingA.6.1 InheritanceA.6.2 SubtypingA.6.3 Interfaces and Abstract ClassesB Use of the Keyword ProtectedC PrinciplesD Structure Package HierarchyE Selected Answers