Java数据结构与算法分析（影印版） (2008 年度畅销榜NO.6489 )

本书介绍了常见的数据结构，如链表、堆栈、队列、树、哈希表等，并对查找、排序等进行了算法分析，还给出了相应的Java实现。\r\n\r\n 本书逻辑结构严谨，主次分明，可用做计算机教材或程序员参考用书。\r\n
\r\n

Contents \r\n\r\n Chapter 1 Introduction \r\n\r\n 1.1. What's the Book About? \r\n\r\n 1.2. Mathematics Review \r\n\r\n 1.2.1. Exponents \r\n\r\n 1.2.2. Logarithms \r\n\r\n 1.2.3. Series \r\n\r\n 1.2.4. Modular Arithmetic \r\n\r\n 1.2.5. The P Word \r\n\r\n 1.3. A Brief Introduction to Recursion \r\n\r\n 1.4. Genetic Objects in Java \r\n\r\n 1.4.1. The IntCell Class \r\n\r\n 1.4.2. The MemoryCell Class \r\n\r\n 1.4.3. Implementing Genetic findMax \r\n\r\n 1.5. Exceptions \r\n\r\n 1.6. Input and Output \r\n\r\n 1.6.1. Basic Stream Operations \r\n\r\n 1.6.2. The StringTokenizer Object \r\n\r\n 1.6.3. Sequential Files \r\n\r\n 1.7. Code Organization \r\n\r\n 1.7.1. Packages \r\n\r\n 1.7.2. The MyInteger Class \r\n\r\n 1.7.3. Efficiency Considerations \r\n\r\n Summary \r\n\r\n Exercises \r\n\r\n References \r\n\r\n Chapter 2 Algorithm Analysis \r\n\r\n 2.1. Mathematical Background \r\n\r\n 2.2. Model \r\n\r\n 2.3. What to Analyze \r\n\r\n 2.4. Running Time Calculations \r\n\r\n 2.4.1. A Simple Example \r\n\r\n 2.4.2. General Rules \r\n\r\n 2.4.3. Solutions for the Maximum Subsequence \r\n\r\n Sum Problem \r\n\r\n 2.4.4. Logarithms in the Running Time \r\n\r\n 2.4.5. Checking Your Analysis \r\n\r\n 2.4.6. A Grain of Salt \r\n\r\n Summary \r\n\r\n Exercises \r\n\r\n References \r\n\r\n Chapter 3 Lists, Stacks, and Queues \r\n\r\n 3.1. Abstract Data Types (ADTS) \r\n\r\n 3.2. The List ADT \r\n\r\n 3.2.1. Simple Array Implementation of Lists \r\n\r\n 3.2.2. Linked Lists \r\n\r\n 3.2.3. Programming Details \r\n\r\n 3.2.4. Doubly Linked Lists \r\n\r\n 3.2.5. Circular Linked Lists \r\n\r\n 3.2.6. Examples \r\n\r\n 3.2.7. Cursor Implementation of Linked Lists \r\n\r\n 3.3. The Stack ADT \r\n\r\n 3.3.1. Stack Model \r\n\r\n 3.3.2. Implementation of Stacks \r\n\r\n 3.3.3. Applications \r\n\r\n 3.4. The Queue ADT \r\n\r\n 3.4.1. Queue Model \r\n\r\n 3.4.2. Array Implementation of Queues \r\n\r\n 3.4.3. Applications of Queues \r\n\r\n Summary \r\n\r\n Exercises \r\n\r\n Chapter 4 Trees \r\n\r\n 4.1. Preliminaries \r\n\r\n 4.1.1. Implementation of Trees \r\n\r\n 4.1.2. Tree Traversals with an Application \r\n\r\n 4.2. Binary Trees \r\n\r\n 4.2.1. Implementation \r\n\r\n 4.2.2. An Example: Expression Trees \r\n\r\n 4.3. The Search Tree ADT--Binary Search Trees \r\n\r\n 4.3.1. find \r\n\r\n 4.3.2. findMin and findMax \r\n\r\n 4.3.3. insert \r\n\r\n 4.3.4. remove \r\n\r\n 4.3.5. Average-Case Analysis \r\n\r\n 4.4. AVL Trees \r\n\r\n 4.4.1. Single Rotation \r\n\r\n 4.4.2. Double Rotation \r\n\r\n 4.5. Splay Trees \r\n\r\n 4.5.1. A Simple Idea (That Does Not Work) \r\n\r\n 4.5.2. Splaying \r\n\r\n 4.6. Tree Traversals (Revisited) \r\n\r\n 4.7. B-Trees \r\n\r\n Summary \r\n\r\n Exercises \r\n\r\n References \r\n\r\n Chapter 5 Hashing \r\n\r\n 5.1. General Idea \r\n\r\n 5.2. Hash Function \r\n\r\n 5.3. Separate Chaining \r\n\r\n 5.4. Open Addressing \r\n\r\n 5.4.1. Linear Probing \r\n\r\n 5.4.2. Quadratic Probing \r\n\r\n 5.4.3. Double Hashing \r\n\r\n 5.5. Rehashing \r\n\r\n 5.6. Extendible Hashing \r\n\r\n Summary \r\n\r\n Exercises \r\n\r\n References \r\n\r\n Chapter 6 Priority Queues (Heaps) \r\n\r\n 6.1. Model \r\n\r\n 6.2. Simple Implementations \r\n\r\n 6.3. Binary Heap \r\n\r\n 6.3.1. Structure Property \r\n\r\n 6.3.2. Heap Order Property \r\n\r\n 6.3.3. Basic Heap Operations \r\n\r\n 6.3.4. Other Heap Operations \r\n\r\n 6.4. Applications of Priority Queues \r\n\r\n 6.4.1. The Selection Problem \r\n\r\n 6.4.2. Event Simulation \r\n\r\n 6.5. d-Heaps \r\n\r\n 6.6. Leftist Heaps \r\n\r\n 6.6.1. Leftist Heap Property \r\n\r\n 6.6.2. Leftist Heap Operations \r\n\r\n 6.7. Skew Heaps \r\n\r\n 6.8. Binomial Queues \r\n\r\n 6.8.1. Binomial Queue Structure \r\n\r\n 6.8.2. Binomial Queue Operations \r\n\r\n 6.8.3. Implementation of Binomial Queues \r\n\r\n Summary \r\n\r\n Exercises \r\n\r\n References \r\n\r\n Chapter 7 Sorting \r\n\r\n 7.2. Insertion Sort \r\n\r\n 7.2.1. The Algorithm \r\n\r\n 7.2.2. Analysis of Insertion Sort \r\n\r\n 7.3. A Lower Bound for Simple Sorting Algorithms \r\n\r\n 7.4. Shellsort \r\n\r\n 7.4.1. Worst-Case Analysis of Shellsort \r\n\r\n 7.5. Heapsort \r\n\r\n 7.5.1. Analysis of Heapsort \r\n\r\n 7.6. Mergesort \r\n\r\n 7.6.1. Analysis of Mergesort \r\n\r\n 7.7. Quicksort \r\n\r\n 7.7.1. Picking the Pivot \r\n\r\n 7.7.2. Partitioning Strategy \r\n\r\n 7.7.3. Small Arrays \r\n\r\n 7.7.4. Actual Quicksort Routines \r\n\r\n 7.7.5. Analysis of Quicksort \r\n\r\n 7.7.6. A Linear-Expected-Time Algorithm for Selection \r\n\r\n 7.8. A General Lower Bound for Sorting \r\n\r\n 7.8.1. Decision Trees \r\n\r\n 7.9. Bucket Sort \r\n\r\n 7.10. External Sorting \r\n\r\n 7.10.1. Why We Need New Algorithms \r\n\r\n 7.10.2. Model for External Sorting \r\n\r\n 7.10.3. The Simple Algorithm \r\n\r\n 7.10.4. Multiway Merge \r\n\r\n 7.10.5. Polyphase Merge \r\n\r\n 7.10.6. Replacement Selection \r\n\r\n Summary \r\n\r\n Exercises \r\n\r\n References \r\n\r\n Chapter 8 The Disjoint Set ADT \r\n\r\n 8.1. Equivalence Relations \r\n\r\n 8.2. The Dynamic Equivalence Problem \r\n\r\n 8.3. Basic Data Structure \r\n\r\n 8.4. Smart Union Algorithms \r\n\r\n 8.5. Path Compression \r\n\r\n 8.6. Worst Case for Union-by-Rank and Path Compression \r\n\r\n 8.6.1. Analysis of the Union/Find Algorithm \r\n\r\n 8.7. An Application \r\n\r\n Summary \r\n\r\n Exercises \r\n\r\n References \r\n\r\n Chapter 9 Graph Algorithms \r\n\r\n 9.1. Definitions \r\n\r\n 9.1.1. Representation of Graphs \r\n\r\n 9.2. Topological Sort \r\n\r\n 9.3. Shortest-Path Algorithms \r\n\r\n 9.3.1. Unweighted Shortest Paths \r\n\r\n 9.3.2. Dijkstra's Algorithm \r\n\r\n 9.3.3. Graphs with Negative Edge Costs \r\n\r\n 9.3.4. Acyclic Graphs \r\n\r\n 9.3.5. All-Pairs Shortest Path \r\n\r\n 9.4. Network Flow Problems \r\n\r\n 9.4.1. A Simple Maximum-Flow Algorithm \r\n\r\n 9.5. Minimum Spanning Tree \r\n\r\n 9.5.1. Prim's Algorithm \r\n\r\n 9.5.2. Kruskal's Algorithm \r\n\r\n 9.6. Applications of Depth-First Search \r\n\r\n 9.6.1. Undirected Graphs \r\n\r\n 9.6.5. Biconnectivity \r\n\r\n 9.6.3. Euler Circuits \r\n\r\n 9.6.5. Finding Strong Components \r\n\r\n 9.7. Introduction to NP-Completeness \r\n\r\n 9.7.1. Easy vs. Hard \r\n\r\n 9.7.2. The Class NP \r\n\r\n 9.7.3. NP-Complete Problems \r\n\r\n Summary \r\n\r\n Exercises \r\n\r\n References \r\n\r\n Chapter 10 Algorithm Design Techniques \r\n\r\n 10.1. Greedy Algorithms \r\n\r\n 10.1.1. A Simple Scheduling Problem \r\n\r\n 10.1.2. Huffman Codes \r\n\r\n 10.1.3. Approximate Bin Packing \r\n\r\n 10.2. Divide and Conquer \r\n\r\n 10.2.1. Running Time of Divide \r\n\r\n and Conquer Algorithms \r\n\r\n 10.2.2. Closest-Points Problem \r\n\r\n 10.2.3. The Selection Problem \r\n\r\n 10.2.4. Theoretical Improvements \r\n\r\n for Arithmetic Problems \r\n\r\n 10.3. Dynamic Programming \r\n\r\n 10.3.1. Using a Table Instead of Recursion \r\n\r\n 10.3.2. Ordering Matrix Multiplications \r\n\r\n 10.3.3. Optimal Binary Search Tree \r\n\r\n 10.3.4. All-Pairs Shortest Path \r\n\r\n 10.4. Randomized Algorithms \r\n\r\n 10.4.1. Random Number Generators \r\n\r\n 10.4.2. Skip Lists \r\n\r\n 10.4.3. Primality Testing \r\n\r\n 10.5. Backtracking Algorithms \r\n\r\n 10.5.1. The Turnpike Reconstruction Problem \r\n\r\n 10.5.2. Games \r\n\r\n Summary \r\n\r\n Exercises \r\n\r\n References \r\n\r\n Chapter 11 Amortized Analysis \r\n\r\n 11.1. An Unrelated Puzzle \r\n\r\n 11.2. Binomial Queues \r\n\r\n 11.3. Skew Heaps \r\n\r\n 11.4. Fibonacci Heaps \r\n\r\n 11.4.1. Cutting Nodes in Leftist Heaps \r\n\r\n 11.4.2. Lazy Merging for Binomial Queues \r\n\r\n 11.4.3. The Fibonacci Heap Operations \r\n\r\n 11.4.4. Proof of the Time Bound \r\n\r\n 11.5 Splay Trees \r\n\r\n Summary \r\n\r\n Exercises \r\n\r\n References \r\n\r\n Chapter 12 Advanced Data Structures \r\n\r\n and Implementation \r\n\r\n 12.1. Top-Down Splay Trees \r\n\r\n 12.2. Red-Black Trees \r\n\r\n 12.2.1. Bottom-Up Insertion \r\n\r\n 12.2.2. Top-Down Red-Black Trees \r\n\r\n 12.2.3. Top-Down Deletion \r\n\r\n 12.3. Deterministic Skip Lists \r\n\r\n 12.4. AA-Trees \r\n\r\n 12.5. Treaps \r\n\r\n 12.6. k-d Trees \r\n\r\n 12.7. Pairing Heaps \r\n\r\n Summary \r\n\r\n Exercises \r\n\r\n References \r\n\r\n Appendix A Some Library Routines \r\n\r\n A. 1. Classes in Package java.lang \r\n\r\n A.1.1. Character \r\n\r\n A.1.2. Integer \r\n\r\n A.1.3. Object \r\n\r\n A.1.4. String \r\n\r\n A.1.5. StringBuffer \r\n\r\n A.1.6. System \r\n\r\n A.1.7. Throwable \r\n\r\n A.2. Classes in Package java.io \r\n\r\n A.2.1. BufferedReader \r\n\r\n A.2.2. BufferedWriter \r\n\r\n A.2.3. File \r\n\r\n A.2.4. FileReader \r\n\r\n A.2.5. FileWriter \r\n\r\n A.2.6. InputStreamReader \r\n\r\n A.2.7. PrintWriter \r\n\r\n A.2.8. PushbackReader \r\n\r\n A.3. Classes in Package java.util \r\n\r\n A.3.1. Random \r\n\r\n A.3.2. StringTokenizer \r\n\r\n Appendix B The Collections Library \r\n\r\n B.1. Introduction \r\n\r\n B.2. Basic Classes \r\n\r\n B.2.1. Collection \r\n\r\n B.2.2. Iterator \r\n\r\n B.2.3. Comparable \r\n\r\n B.2.4. Comparator \r\n\r\n B.3. Lists \r\n\r\n B.3.1. ArrayList vs. LinkedList \r\n\r\n B.3.2. Stacks and Queues \r\n\r\n B.3.3. ListIterator \r\n\r\n B.4. Sets \r\n\r\n B.5. Maps \r\n\r\n B.5.1. put, get, remove, and contains \r\n\r\n B.5.2. Getting a Collection from the Map \r\n\r\n B.5.3. Map. Entry Pairs \r\n\r\n B.6. Example: Generating a Concordance \r\n\r\n B.6.1. Collections API Version \r\n\r\n B.6.2. Version Using Package DataStructures \r\n\r\n B.7. Example: Shortest-Path Calculation \r\n\r\n B.7.1. Collections API Implementation \r\n\r\n B.7.7. Version Using Package DataStructures \r\n\r\n B.8. Priority Queues \r\n\r\n Summary \r\n\r\n Index \r\n
\r\n

程序设计在于处理复杂性：问题的复杂性和所用的程序设计工具的复杂性. Java的魅力在于其本身的低复杂性, 同时又能很好地处理高度复杂的问题. Java程序的开发周期只有类似的C++程序的一半甚至更少, 而且Java可以方便地处理复杂软件问题：多线程. 分布式. 跨平台. 安全性等. Java从诞生到现在, 已经广泛应用于几乎所有类型软件系统的构建. 尤其在基于Web的系统开发中, Java技术具有独特的优势. 熟悉Java历史的人都知道, Java的前身——编程语言Oak就是致力于电子产品互连的语言, Internet的发展导致了Oak的重生和Java的广为流行. 现在, J2EE技术已经成为企业级Web应用系统的标准平台.

好的程序设计人员不仅仅要掌握优秀的编程工具, 更需要掌握优秀的编程思想. 随着面向对象编程技术数十年的发展, 人们开始提炼和总结面向对象编程中行之有效的. 具有一定普遍意义的方法, 即面向对象的设计模式. 以Gamma. Helm. Johnson和Vlissides合著的经典书籍《设计模式》为开端, 面向对象设计模式的研究和应用成为面向对象程序设计的重要内容. 所有结构良好的面向对象软件系统都包含了大量的设计模式, 能否熟练应用设计模式已经成为衡量程序员水平的至关重要的标准.

本丛书收录了与Java程序设计和Java设计模式相关的经典书籍, 反映了应用Java开发软件系统的最佳经验总结和最新动态.

《Java设计模式》采用方便而简洁的编写风格, 以可视化的Java程序为例, 详细介绍了Gamma. Helm. Johnson和Vlissides合著的经典书籍《设计模式》中列出的所有23种模式. 通过本书, Java程序员可以迅速了解和掌握设计模式的内容, 并在实践中应用设计模式来创建复杂而健壮的Java程序.

《Java模式应用》介绍了基于模式的开发技巧, 演示了使用Java开发各种商务系统中的模式应用. 书中首先概述设计模式, 然后就四种主要模式——创建模式. 行为模式. 结构模式和系统模式展开了详细的论述. 该书还针对系统构建过程中常用的J2EE. JSP. EJB和API等技术作了介绍, 适合具有一定编程基础的Java程序员阅读参考.

《J2EE核心模式》是Sun Java Center的资深设计师的J2EE亲身实践经验的总结. 该书主要描述J2EE关键技术（Java Server Pages, Java Servlet, Enterprise Java Beans, Java Message Services等）的模式. 最佳实践. 设计策略和经过验证的解决方案. 该书介绍了J2EE包括的15个模式的分类和大量的策略, 不仅具有理论深度, 而且非常实用. 该书内容适合J2EE的爱好者. 程序员. 设计师. 开发者和技术管理者. 一句话, 该书适合于设计. 构建和开发J2EE平台应用的所有人.

XML是新一代文档的标准, Web页. 数据. 源码等等, 均可以用XML文档表示. 越来越多的程序员正在使用Java来处理XML文档. 《用Java处理XML》详细论述了如何使用Java来读写XML文档. 该书是目前最新和最全的Java处理XML技术的介绍, 包含内容超过1000页的关于SAX, DOM, JDOM, JAXP, TrAX, XPath, XSLT, SOAP等的讲解. 该书适合于使用Java读写XML文档的Java程序员. 其内容从基本概念到高级应用无所不包, 特别适合作为手册随时参考.

　　在《实时Java》中, 作为RTSJ专家组的成员之一, Dibble从Java平台特有的实时问题概述开始, 依次讲解了RTSJ各项主要特性的使用方法. 从广泛的实时原理到详细的编程隐患, 该书覆盖了构建有效实时程序所需的一切知识. 其主要内容包括：与非实时代码的互操作性. 实时开发中的取舍以及JVM软件的实时问题, 垃圾收集. 无堆栈访问. 物理内存和“不朽”内存以及无堆栈内存的常数时间分配, 优先级调度. 期限调度以及速率单调分析, 闭包. 异步传输控制. 异步事件以及计时器. 这是一本非常实用的指南, 适用于有经验的Java平台开发人员.

《Java数据结构与算法分析》介绍了常见的数据结构, 如链表. 堆栈. 队列. 树和哈希表等, 并对查找和排序进行了算法分析, 给出了相应的Java实现. 该书逻辑结构严谨, 主次分明, 可用作程序员参考书.

总之, 这套书详细介绍了Java应用的许多重要方面： 从具有普遍性的Java数据结构和算法. Java设计模式. Java模式应用. J2EE核心模式, 到日益显著的Java特殊应用领域（Java处理XML文档和Java实时系统开发）. 其内容具有一定的理论深度, 更有重要的实际参考价值.

有鉴于此, 特向Java系统开发和应用领域中不同程度的读者推荐这套书, 相信每位有心的读者都能得到物超所值的收获.

清华大学经济管理学院管理科学与工程系 朱涛 博士

讲授课程：Java程序设计, 面向对象的分析设计方法