《数据结构(Java版)》 - 清华大学出版社第五事业部
书名:《数据结构(Java版)》
定价：￥118.00
版权信息和内容简介
作&nbsp&nbsp&nbsp&nbsp者：(美)William&nbspH.&nbspFord&nbsp&nbsp&nbsp&nbsp&nbspWilliam&nbspR.&nbspTopp&nbsp著译&nbsp&nbsp&nbsp&nbsp者：梁志敏&nbsp&nbsp译组稿编辑：曹&nbsp&nbsp康 文稿编辑：徐燕萍封面设计：康&nbsp&nbsp博 版式设计：康&nbsp&nbsp博印&nbsp刷&nbsp者：发&nbsp行&nbsp者：新华书店总店北京发行所开&nbsp&nbsp&nbsp&nbsp本：185×260&nbsp&nbsp&nbsp&nbsp印&nbsp张：62.25&nbsp&nbsp&nbsp&nbsp字&nbsp数：1594千字版&nbsp&nbsp&nbsp&nbsp次：2006年11月第1版&nbsp&nbsp2006年11月第1次印刷书&nbsp&nbsp&nbsp&nbsp号：ISBN&nbsp7-302-13544-4/TP&#印&nbsp&nbsp&nbsp&nbsp数：1~3000定&nbsp&nbsp&nbsp&nbsp价：118.00元
本书从面向对象的角度讲述了数据结构的基本理论。总的来说，数据结构就是处理批量数据的存储处理机。数据结构又称为集合(collection)，它可进行添加和删除数据项的操作，并且能够提供对集合中元素的访问。面向对象的编程方法将数据结构视为可对数据进行特定操作的对象。类声明定义了数据底层的存储结构和能高效执行操作的实现方法。
数据结构在计算机科学的各个领域中都扮演着非常重要的角色。在几乎所有重要的计算机应用程序的设计和实现中，它都是一个关键的要素。所以大多数学生在回顾数据结构的课程时，都认为这是他们将计算机科学作为一种学科来认识和了解的第一步。在数据结构的学习中会介绍大量的重要概念。
本书的编排
现代的观点将数据结构分为面向对象的编程原理和算法分析的概念。我们的学习主要是围绕定义集合类型的类别的接口来进行。这种接口把数据结构视为一种抽象数据类型(ADT)，它描述了集合如何存储元素并定义了关键的数据处理操作。集合类是一种聚合数据结构，它用特定的方法来实现存储和访问元素的接口。
本书对数据结构的学习按简单的接口和类的层次结构来进行。位于最高层的接口描述了与对集合中对象进行访问和更新操作有关的抽象结构。最底层含有的集合类使用不同的底层存储结构来保存元素和实现接口。接口和集合类的层次结构为数据结构创建了一个总的构造，我们将其称为集合架构(collections framework)。在本书中，我们模仿Java Collections Framework创建了一个简单的集合架构，该架构定义了使用有限的一组方法的接口，这些方法描述了集合类的基本功能。
Java Collections Framework是一个商业级软件系统，它提供了多种方法来帮助应用程序的编程人员。Java Framework中的集合类代码很大程度上依赖于抽象类和相当复杂的继承层次结构。书中的集合使用用于接口的相同名称和方法签名来模仿Java Collections Framework，此外还创建了具有相同名称和底层存储结构的集合类。不过，我们使用直观的实现来设计集合类。通过这种方式，学生能够阅读书中的代码并理解各种方法及其算法。学习本书所有内容后，读者会发现在职业生涯中很容易掌握更完整的Java Collection Framework。
图0-1示例了本书中集合架构的接口和集合类。类用阴影表示。List接口是按位置存储元素的数据结构模型，而Set接口是按值存储元素的数据结构模型，它不允许集合中存在重复值。Map接口是按键/值对存储元素的关联集合模型。映射中存储的键是不可重复的，并且提供了某种机制将键和值关联起来。在映射集合中，程序员通过键而不是索引来访问相应的值。Stack、Queue、PQueue是用于适配器集合的接口，上述接口将另外一个集合用作底层存储结构，不过只为这些结构提供受限的操作。图是由顶点和连接边组成的数据结构。网络就是图的一种模型。本书会讲述图及其经典的搜索和最优化算法。Graph接口中列出了这些操作以及作为具体数据结构的有向图。
本书中介绍的接口与类
数据结构与算法
数据结构除了存储数据外，还具有处理数据的操作。这些操作的设计和实现涉及由完成任务所需的有限指令序列所组成的算法。学习数据结构必须对算法也有所了解，以便确保正确地处理数据。我们还必须考虑到大数据集带来的问题。数据结构的选择对访问和更新操作的效率影响非常大。假设要维护100 000张信用卡账户，类似数组的结构平均需要50 000次迭代才能定位某个元素，而用映射完成同样的任务只需要大约16次迭代。这两种结构都具有查找某个数据值的算法，但是两者的性能结果却大不相同。在讨论算法时，我们会使用简单、直观但却非常有效的方法来评估算法的执行时的时间性能，这种评估方式与所用的机器或编程语言无关。
数据结构需要优良的算法，反之亦然。在后面章节介绍图、数据压缩、密码术以及高级递归算法的时候，读者会看到这方面的示例。我们将重点讨论密切依赖于针对问题采用特定方式构造数据的算法和算法设计技术。通过这种方法，我们就能够使用在本书中讲述的数据结构特性。著名的计算机科学家Niklaus Wirth在其经典论文Algorithms + Data Structures = Programs一书中表明：对于计算机编程来说，算法和数据结构具有同样的重要性。在现代的面向对象编程中，数据结构对于算法设计和分析来说仍然至关重要。
Java与数据结构
本书中讨论的大多数素材都能够应用于任何编程语言。我们重点强调了与数据结构的设计和使用相关的概念。不过，读者还必须理解如何实现数据结构和编写应用程序。这要求读者采用特定的编程语言来编写代码，在本书中我们选择了Java语言。Java语言具有优良的、支持数据结构现代观点的面向对象设计构造。我们使用这种编程语言以一个层次架构来描绘数据结构。Java接口定义了数据结构(集合)的类别，而Java类则定义了单独的集合类型。
Java是可移植的，它允许程序不需重新编译就能够在任何平台上运行。这种特性具有许多实用的优点。学生可以先在Windows、Macintosh或UNIX系统中开发程序，然后再将代码移植到另一个系统中。大学里应该可以为实验室提供中央计算设备，这样学生就可以在自己的主系统上开始或完成所从事的项目。
Java是创建交互式图形用户界面(Graphical User Interface，GUI)程序的理想语言。大多数现代应用程序的形式是GUI程序。第3章使用Java Swing组件独立地介绍了GUI编程。本书的目标是促进读者对数据结构的理解，并且绝大部分示例、程序和练习都基于控制台，也就是使用键盘输入和屏幕输出。不过，GUI应用程序零散地遍布于全书以及练习当中。
Java语言具有许多有助于数据结构使用和实现的编程构造。这些构造包括：
● 自动装箱和自动拆箱，自动装箱提供从某个原始类型到其相关包装类型的自动转换，自动拆箱则提供从某个包装类型到其相关原始类型的自动转换。这允许我们将原始数字和字符数据作为对象存储在集合中。
● 集合使用迭代器扫描数据。Java引入了使编译器能够维护迭代器的“增强的for”语句。这种语句使用变化形式的loop循环简化了初始化迭代器的需求以及使用迭代器方法访问集合元素。
● Java提供了一个枚举工具，这个枚举工具允许程序定义其成员为命名常量的特殊类。编程人员能够使用enum类来增强程序的可读性。我们将在选定的应用程序和实现中示例说明这种特性。
● Scanner对象为来自文件或键盘的文本数据输入提供一个简单的文本扫描器。这个扫描器将输入流中的文本分割为若干标记，并且使用多种方法将标记转换为一个串或一个原始类型值。
对于数据结构来说，Java语言中最重要的特性是泛型。泛型扩展了将类型参数与集合类实例、接口或方法相关联的语言。Java的编译器能够检查代码是否与指定类型一致；如果一致，那么代码是类型安全的。执行类型安全的代码不会导致某些运行时错误，这些运行时错误包括由于不正确的类型检查和类型处理所带来的代码质量和可靠性问题。
第5章详细阐述了Java泛型。我们首先阐明在Java语言中包含泛型的动机，随后讲述创建泛型类和方法时必须使用的机制。这些讨论的重点是读者必须了解的基础。本书的后面部分还将为更复杂的泛型开发相应的语法，并且始终重点讲述读者“需要知道”的基础知识。Java泛型的其他一些特征则超出了本书的讨论范围。
本书的功能部件
本书包含能够提高学生知识水平的功能部件以及促进深入理解数据结构的介绍主题。
● UML：对象技术的发展促进了用于程序设计的各种表示法的出现。其中一个最重要的表示法是通用建模语言(Unified Modeling Language，UML)。UML使用图形规范来帮助完成对象和程序设计。通过使用UML图作为列出接口或集合类中方法的一种有效途径，使读者对UML有一定的了解。
● 练习集：每一章都含有书面练习和编程练习。设计这些练习的目的是巩固对基本知识的理解，使学生能够设计与实现方法以及完成程序，促进对各种素材的创造性认识。每一章还含有编程项目，这些编程项目要求更高级的设计和编程以及开发更多算法。
设计模式：问题的面向对象解决方案经常使用软件重用的公共设计模式进行构造。我们选择介绍了一些设计模式，这些设计模式增强了读者对数据结构及其应用的理解，并且能够帮助构造类、方法以及对象的实现。
● 注释：在研究各种主题的过程中，我们在文中插入了一些主要概念的注释。这些注释突出了重要的知识点，并且为学生提供了一种复习素材的简单有效方法。
本书假定学生至少已学过一门编程课程。针对没有Java编程经验的学生，我们在附录A中提供了“Java入门”指南。“Java入门”采用文本样式编写，并且含有示例和完整的程序。这个指南为读者阅读和理解本书提供了必要的背景知识。学生应当掌握中学的大学预备课程中的数学知识。递归的示例以及算法运行时效率的讨论使用了高等代数课程中所讲述的数学知识。
教师需要注意的问题
本书可以用作两学期计算机科学授课内容的一部分，也可以作为一门为学习数据结构专门设计的课程。某些学校(如笔者的学校)开设了一门课程来阐述数据结构和介绍数据结构在算法中的应用。我们已经发现：本书中知识点的深度与多样性所达到的教学效果非常不错，并且能够在今后的算法设计与分析课程中为学生提供某些编程工具。本书的设计方式允许教师能够非常灵活、自由地组织和讲解各种知识点。
我们广泛使用示例、图表以及注释来包涵所有知识点。本书的前7个章节介绍了学习数据结构时要用到的各种概念和工具。
● 第1~ 3章介绍了Java的对象技术特征，包括对象的使用、类的设计与实现、组合、继承、接口以及异常处理。这一部分通过许多示例和程序说明了使用Time24对象的数据结构。
● 第4章讨论了如何使用独立于任何机器或编程语言的算法运行时间性能来描述算法的特征。我们直观地提出了效率度量Big-O，并且将其应用在全书范围内，以便有助于选择适用于特定程序应用的算法或数据结构。
● 第5章较详细地讲述了Java泛型类与方法。泛型的使用贯穿全书，并且这一章节的知识点为学生提供了至关重要的背景知识。
● 第6章和第7章介绍了递归及其在高效的归并排序与快速排序算法中的应用。对于学习二叉树来说，理解递归至关重要。
● 第8~19章覆盖了初次接触数据结构的读者应当了解的主题。我们使用一种体系方式逐渐展开每种数据结构。这种方式认为学生需要从下列4个方面来理解每种数据结构：存储数据的方式，指定具体集合类的接口，在应用程序中使用这个类的能力，以及对类实现的理解。
动态数组、单链表和双链表以及二叉树是分别为ArrayList、LinkedList、TreeSet和TreeMap集合类提供底层存储结构的低级数据结构。我们首先介绍了这些数据结构，然后开发了定位、插入和删除元素的算法。
集合类型(接口)指定了用于集合类的大多数设计特性。一个类可以包含利用底层存储结构特征的额外方法。例如，ArrayList类定义了方法ensureCapacity()，该方法更新底层动态数组的大小。
我们为每种数据结构都提供了若干应用程序。某些应用程序简单地示例说明了如何使用集合类方法；另外一些应用程序则利用了独特的特征并示例说明了算法与数据结构之间的交互。
在讲述数据结构的课程中，学生必须理解每种集合类型的抽象设计和实现设计。他们应该掌握需要使用哪种数据结构以及如何使用这种数据结构。我们在介绍每种集合类的同一章节中开发了各种集合类的实现。读者可以根据自己的需求随时研究这些实现。对集合类实现的讨论独立于学生需要了解的其他方面的内容。
● 第20~29章覆盖了数据结构高级课程与算法应用的主题。笔者建议：介绍集与映射的第19章既可以作为数据结构预备课程的内容，也可以作为数据结构高级课程的内容。在预备课程中，本章可以向学生介绍应用程序中所使用的重要集合类型以及作为键-值对的元素。在高级课程中，教师能够更详细地开发作为关联数组的映射并讨论区分元素键字段和值字段的迭代器访问方法。
数据结构预备课程介绍了简单的、具有节点和引用字段的二叉搜索树。数据结构高级课程将二叉搜索树的概念扩展到包含平衡树以及定义堆的基于数组的二叉树，此外，还将散列表开发为一种可供选择的搜索结构。第21、22和27章阐述了上述内容，并且使用它们创建用于有序与无序集、映射和优先队列的高效实现。
计算机科学专业的学生通常都需要参加算法设计与分析课程的学习。这门课程的重点是不同的算法设计策略，并且对算法效率进行更深入的数学分析。伪码被用于描述实现技术。针对实现算法的数据结构，通过示例说明这些数据结构的复杂与总是巧妙的用法，数据结构高级课程融会了算法设计与分析。因此，本书包含了数据与文件压缩(第23章)、图算法(第25章)、数论与密码术(第28章)以及杂类算法(第29章)等相关章节。这些章节都是独立的单元，教师可以选取某些主题进行教学。
教师指南可供教师使用，它不仅提供了所有书面练习的答案以及大多数编程练习和编程项目的解决方案，而且提供了每章的测验模拟题。除此之外，我们还为练习中开发的程序和类给出了源文件。您可以通过Prentice Hall驻北京办事处的销售代理商购买教师指南。
从如下所示的网址上可以得到本书的所有补充内容：
.cn/downpage
软件补充内容
软件补充内容位于ftjavads目录中，这个目录由programs、packages和docs目录组成。programs目录包含用于本书每个章节的若干独立子目录，这些子目录中存在用于本章中程序的源文件和数据文件。在某些情况下，读者还会发现指定章节所引用的图形程序和其他程序清单。packages目录包含全书范围内所使用的软件，它的结构定义了ds子目录，该子目录又分支为对应于包graphics、time和util的目录。util软件包包含了本书所介绍的接口、集合类和静态方法库。
软件API文档
文件docs包含对packages目录中软件的完整API说明，这为学生和教师提供了易于使用的、资料丰富的在线文档。packages目录中的Java源文件清单包含文档注释。javadoc工具使用这些注释来创建相应的HTML页面集。通过Web浏览器打开文件index.html，读者就可以使用API文档。
Web补充内容
笔者尽可能使本书自成一体。不过在某些情况下，我们引入了基本的功能与算法，并且基于Web补充内容进行更详细的讨论。这些补充内容通过简单地扩展本书的版面来提供额外的素材。
现代应用程序通常使用依赖于GUI窗体的交互式I/O，而GUI窗体具有组件和事件处理程序。第3章介绍了GUI应用程序设计，并且讨论了基本的组件集以及动作侦听器机制。
图形显示可以帮助读者理解各种算法，如Hanoi塔、八皇后问题等。本书还使用图形显示来示例说明二叉树以及用于二叉搜索树、AVL树、红-黑树和堆数组的插入与删除方法。软件补充内容包含基本的画图软件。Web补充内容“Graphics Package”给出了对画图系统的详细讨论，此外还提供了继承的一个优秀示例。
本书只简单描述了用于中缀表达式求解与红-黑树插入和删除方法的算法。对这些算法感兴趣的读者可以通过Web补充内容“Infix Expression Evaluation”和“RBTree Implementation”得到更详细的讨论以及Java实现的代码清单。
EZJava IDE
EZJava是一个灵活的集成开发环境(Integrated Development Environment，IDE)，它允许在Windows、Linux、Solaris或Macintosh OS X系统下开发和运行Java程序。读者可以选择与当前系统匹配的版本。EZJava IDE允许非常简单地编译和运行一个主类以及位于相同目录中的任何支持类。对于更高级的软件开发来说，我们可以创建一个由相同软件包结构中多个源文件组成的项目。
EZJava拥有十分复杂的编程环境才具有的特性。虽然EZJava可以用来开发大型的软件系统，不过它是为了在学术课程作业中方便Java的使用而专门设计的。我们可以创建若干单独的程序，并且可以在项目环境之外运行这些程序。应用程序使用一个用于多个运行的命令按钮在自己的运行时窗口中执行命令。EZJava编译了Synchronous Java，Synchronous Java是一个具有并行编程工具的Java扩充，并行编程工具在操作系统课程中非常有用。
附录E讨论了如何获取和安装EZJava以及如何使用其主要功能创建和运行一个程序。这个软件所集成的帮助系统提供了更多的指南。
William Ford
William Topp
类与对象 1
本书内容 1
动态数组 1
关联数组 3
适配器结构 4
数据结构与面向对象编程 5
数据结构与算法 5
面向对象编程 5
理解类的概念 7
Time24类 8
设计Time24类 8
构造函数 9
toString方法 10
Accessor和mutator方法 11
静态方法 12
对象的声明和使用 12
对象方法的使用 13
引用与别名 14
一个使用Time24对象的
应用程序 15
类的表示 16
类的实现 18
Time24类声明 19
私有的工具方法 20
accessor与mutator方法 21
构造函数 22
格式化的对象描述 23
增加时间 23
时间间隔 23
类的构造 24
String类 26
书面练习 33
编程练习 34
编程项目 36
类之间的关系 39
wrapper类 40
Integer对象的比较 40
静态wrapper类成员 41
字符处理 42
自动装箱与自动拆箱 43
对象组合 44
TimeCard类 45
TimeCard类的实现 46
TimeCard类的UML图 47
Java中的继承 47
一个雇员层次结构 48
继承层次结构中成员的
Employee类的声明 50
SalaryEmployee子类 51
继承层次结构中的关键
字super 52
HourlyEmployee子类 53
运行时错误的处理 60
throw语句 60
处理异常的try/catch
finally子句 62
异常传播 63
Java异常的层次结构 63
标准的异常 65
输入与输出 65
控制台I/O 66
文件I/O 67
使用Reader流的文本输入 67
输入串的分析 69
使用Writer流的文本输出 71
输出流的控制 72
Scanner类 73
声明Scanner对象 73
输入流的读取 73
文件输入 75
Scanner类API 75
应用程序：Scanner类
书面练习 80
编程练习 83
编程项目 87
类的设计 89
Java接口 89
作为模板的接口 91
使用接口类型 92
接口与继承 94
使用javadoc创建API 96
设计模式 99
GUI应用程序设计 100
图形组件 101
GUI应用程序设计模式 102
事件侦听器与事件处理
骰子投掷动作事件 106
书面练习 108
编程练习 108
编程项目 112
算法介绍 115
选择排序 115
简单的搜索算法 119
顺序搜索 119
二叉搜索 121
算法的分析 126
系统/内存性能标准 126
算法性能：运行时间分析 126
Big-O符号 129
通用数量级 131
搜索算法的比较 133
书面练习 136
编程练习 138
编程项目 141
泛型类与方法 143
Object超类 144
对象数组方法 145
通用的顺序搜索 146
Java泛型介绍 147
基于Object的Store类 148
泛型集合 149
泛型Store类 150
泛型接口 151
泛型方法 155
基本的泛型方法 155
为泛型类型使用绑定 156
泛型与继承 157
被绑定的泛型类型 158
泛型与通配符 160
泛型搜索/排序算法 161
书面练习 165
编程练习 166
编程项目 168
递归的概念 171
描述一个递归算法 173
递归方法的实现 173
递归的工作方式 175
多种基数表示法 176
递归的应用 179
构建一个刻度尺 179
Hanoi塔 181
递归的评价 185
Fibonacci方法 186
使用递归的标准 189
书面练习 190
编程练习 192
编程项目 194
排序算法 195
插入排序 195
分治排序算法 198
归并排序 198
通用的排序方法 201
msort()方法 202
归并排序的效率 205
快速排序 206
使用基准值分割列表 206
快速排序递归下降 209
pivotIndex()方法 211
quicksort()方法 213
快速排序的运行时间 215
排序算法的比较 216
第k大元素的查找 219
书面练习 222
编程练习 223
编程项目 225
集合类型 227
集合介绍 227
集合的概述 229
List集合 230
Set集合 232
Map集合 233
适配器集合 234
Graph集合 235
Java Collections Framework 236
Bag集合 237
创建和使用一个Bag集合 238
应用：Eratosthenes筛选法 240
Bag类的实现 243
私有的remove()方法 244
插入和访问方法 245
集合的toString()方法 246
书面练习 247
编程练习 248
编程项目 249
基于数组的列表集合 251
列表集合 251
ArrayList类 255
调整ArrayList的大小 257
ArrayList API 259
ArrayList应用程序 259
ArrayList的连接 259
closest-pair问题 262
实现ArrayList类 266
ArrayList类的设计 266
准备更大的容量 267
添加和删除元素 268
实现索引访问 272
Cloneable对象 273
克隆Time24对象 274
克隆引用变量 275
克隆ArrayList对象 277
克隆数组 279
ArrayList集合的评价 279
书面练习 280
编程练习 282
编程项目 285
单链表 289
创建链表 289
扫描链表 291
定位列表位置 291
更新列表头 292
通用的插入和删除操作 292
删除目标节点 294
双链表 298
LinkedList集合 299
LinkedList类 300
基于索引的LinkedList
访问列表尾 302
使用LinkedList集合的
应用程序 304
应用程序：选拔列表 304
应用程序：回文列表 307
书面练习 310
编程练习 313
编程项目 318
实现LinkedList类 321
双链表 321
DNode对象 322
使用DNode对象 323
循环双链表 325
声明双链表 326
更新双链表 327
应用程序：词汇杂乱 330
实现LinkedList类 333
LinkedList类的私有
LinkedList类的构造
列表中基于索引的访问 335
搜索列表 336
修改列表 337
书面练习 339
编程练习 340
编程项目 342
迭代器 345
迭代器的概念 345
集合迭代器 346
迭代器扫描方法 347
通用的迭代器方法 350
使用增强的for语句
进行迭代 351
列表迭代器 352
ListIterator方法set() 353
列表的后向扫描 354
ListIterator方法add() 356
迭代器设计模式 357
迭代器的应用 358
有序列表 358
删除有序列表中的
重复值 360
OrderedList集合 361
OrderedList类方法 362
应用程序：确定字频 363
适配器设计模式 367
顺序集合的选择 367
书面练习 369
编程练习 371
编程项目 373
迭代器的实现 375
迭代器实现设计 375
迭代器变量 376
迭代器接口方法 377
LinkedList迭代器 378
列表迭代器的实现 381
列表迭代器构造函数 381
列表迭代器的公共方法 382
快速失效迭代器 385
书面练习 387
编程练习 388
编程项目 390
堆栈集合 392
堆栈的应用 396
多种基数 397
符号对的平衡 400
递归与运行时堆栈 403
后缀表达式 405
后缀表达式的求解 406
PostfixEval类 408
evaluate()方法 410
中缀表达式的求解 412
中缀表达式属性 412
中缀-后缀转换 413
书面练习 417
编程练习 419
编程项目 422
队列与优先队列 425
Queue接口 426
创建一个队列集合类 427
应用：队列的调度 428
基数排序 430
有界队列 436
BQueue类的设计实现 438
BQueue类的声明 440
优先队列 441
优先队列接口 442
应用程序：支持服务库 444
事件驱动的仿真 447
对银行的仿真 447
仿真设计模式 449
BankSimulation类 451
书面练习 457
编程练习 460
编程项目 463
二叉树 465
树结构 465
树的相关术语 466
二叉树 468
二叉树节点 473
二叉树扫描算法 477
递归树遍历 477
中序扫描算法 478
扫描方法的设计 480
迭代的层序扫描 482
Visitor设计模式 484
Visitor设计模式的使用 486
树扫描算法的使用 489
树高度的计算 489
复制二叉树 491
清除树 494
显示二叉树 495
排序的下界(选读) 497
书面练习 500
编程练习 503
编程项目 505
二叉树的应用 507
表达式树 507
迭代的树遍历 512
中序迭代遍历 513
InorderIterator类的实现 515
Euler回路遍历 518
绘制二叉树 521
影像树的构建 521
影像树的显示 523
书面练习 526
编程练习 526
编程项目 529
二叉搜索树 531
二叉搜索树 531
构建二叉搜索树 532
在二叉搜索树中定位
删除二叉搜索树节点 535
STree：一种二叉搜索树类 536
STree类的实现 540
STree类的私有成员与
构造函数 541
插入和定位节点 542
删除节点 544
其他操作 550
二叉搜索树操作的
复杂度 551
STree迭代器 551
书面练习 556
编程练习 558
编程项目 559
集与映射 561
TreeSet集合 563
简单的拼写检查器 565
集运算符 568
集运算符的实现 569
应用程序：计算机账号的
使用有序集的操作 574
Map接口 577
有序映射TreeMap 579
应用程序：一个学生时间
记录映射 581
应用程序：计算机软件
映射集合视图 586
键集集合视图 586
条目集集合视图 588
应用程序：构建词汇
书面练习 596
编程练习 598
编程项目 602
有序集与映射的实现 603
TreeSet类的实现 603
TreeMap类的实现 604
TreeMap类的设计 607
使用键对条目进行访问 608
更新条目 609
删除条目 611
TreeSet和TreeMap类中
插入和删除操作的
复杂度 611
集合视图的实现 611
查看视图 612
实现视图 614
keySet集合视图 615
书面练习 617
编程练习 618
编程项目 621
实现映射的散列法 625
散列法 625
散列函数的设计 627
Java方法hashCode() 627
自定义的散列函数 629
散列表的设计 631
线性探查法 631
具有不同列表的拉链法 633
再散列 635
作为集合的散列表 636
Hash类的实现 637
Hash类的add()和
rehash()方法 639
Hash类的remove()方法 641
Hash类迭代器的实现 642
无序映射集合 645
访问HashMap类中的
更新HashMap类中的
无序集集合 649
散列表的性能 650
书面练习 653
编程练习 655
编程项目 657
基于数组的二叉树 661
Comparator接口 663
通用比较对象 664
通用的数组排序 665
堆的插入操作 668
堆的删除操作 670
堆的显示 674
使用堆进行排序 676
堆的产生 676
堆排序 679
静态堆方法概述 680
优先队列的实现 681
书面练习 684
编程练习 687
编程项目 689
位数组与文件压缩 691
位数组 691
BitArray类 694
BitArray类的实现 696
二进制文件 699
Huffman压缩 703
Huffman树的构建 707
Huffman压缩的实现 708
Huffman解压的实现 714
序列化 716
对象的序列化 717
使类可序列化 718
反序列化对象 718
应用程序：对象的
序列化 718
定制序列化 721
书面练习 724
编程练习 728
编程项目 729
图与路径 731
图的相关术语 731
有向图 733
带权图 734
图的创建和使用 735
Graph接口 735
DiGraph类 737
图遍历算法 741
广度优先搜索算法 741
深度优先访问算法 746
深度优先搜索算法 751
无环图 753
书面练习 755
编程练习 758
编程项目 761
图算法 763
拓扑排序 763
拓扑排序的目的 764
topologicalSort()方法
的实现 765
强连通组件 766
25.2.1 强连通组件算法的工作
strongComponents()方法
的实现 769
图最优化算法 771
最短路径算法 772
shortestPath()方法的实现 774
Dijkstra最小路径算法 777
Dijkstra算法的设计 778
Dijkstra算法的工作
minimumPath()方法的
无环图中的最小路径 784
最小生成树 787
Prim算法 788
minSpanTree()方法的
书面练习 794
编程练习 796
编程项目 798
图的实现 799
图的表示 799
DiGraph类的组件 800
顶点信息的表示 801
顶点映射与VertexInfo
数组列表 803
DiGraph类设计 806
DiGraph类方法 807
ArrayList的访问 808
邻接顶点的标识 808
入度和出度的求解 809
添加边 809
删除顶点 810
图算法支持方法 813
图集合视图 814
书面练习 816
编程练习 817
编程项目 819
平衡的搜索树 821
AVLTree类的实现 824
AVLTree类的add()
私有的addNode()方法 831
add()方法 832
2-3-4树 835
2-3-4树的搜索 836
2-3-4树中的插入操作 836
红-黑树 839
2-3-4树节点的表示 840
2-3-4树的红-黑树表示 841
在红-黑树中插入节点 844
4-节点的分割 844
红-黑树底部的插入
红-黑树的构建 849
红-黑树的搜索运行
在红-黑树中删除节点 851
RBTree类 852
书面练习 855
编程练习 858
编程项目 859
数论与加密 861
基本的数论概念 861
Euclid GCD算法 862
模运算 863
Euler Φ函数 865
安全的消息传输 866
创建用于RSA加密的
使用用于RSA加密的
如何保护RSA通信 868
大整数的使用 868
RSA的客户-服务器模式 872
RSA算法(选读) 873
Euclid GCD算法的实现 873
RSA定理 876
书面练习 878
编程练习 879
编程项目 880
杂类算法 881
组合学 881
组合的构建 882
查找所有子集 883
列出置换 885
旅行推销员问题 888
置换与TSP 889
动态编程 889
由顶向下动态编程 890
使用动态编程的组合 893
由底向上动态编程 894
背包问题 896
Knapsack类 899
回溯：八皇后问题 903
问题分析 905
程序设计 907
显示棋盘 911
书面练习 914
编程练习 915
编程项目 920
Java入门 923
Java程序的结构 923
关键字与标识符 925
变量的声明和使用 925
控制台输出 925
Java编程环境 926
原始数据类型 927
数值类型 927
Java的char类型 929
命名常量的声明 930
运算符 930
算术运算符 930
赋值运算符 931
A.4.3 复合赋值运算符 931
增量运算符 932
运算符的优先顺序 932
类型之间的转换 933
选择语句 935
if语句 937
嵌套的if语句 938
多路if/else语句 939
条件表达式运算符 939
switch语句 940
boolean类型 941
循环语句 942
while语句 942
do/while语句 943
for语句 944
break语句 945
数组的初始化 947
使用增强的for语句
扫描数组 947
二维数组 948
Java的方法 949
预定义的方法 949
自定义的方法 951
作为方法参数的数组 953
Java关键字 957
ASCII字符编码 959
Java操作符的优先顺序 961
EZJava集成开发环境 963
安装EZJava 963
启动EZJava 964
创建新文档 965
菜单选项 966
程序的编译和运行 966
项目的使用 968
Copyrights(C) 2005 By 清华大学出版社第五事业部()&All
Rights Reserved
技术支持: 025- FAX: 025- E-Mail:
地址：清华大学南门内200米绿楼 电话:010- 邮编：100084