数据结构与问题求解（Java 版）（第二版） (2010 年度畅销榜NO.11906 )

本书使用流行的Java语言作为描述语言，详细介绍了数据结构和算法。全书共分为五大部分。第一部分的Java教程是全书的基础，具体讲述Java的运行环境、数据类型和运算符、基本语法等；同时介绍了面向对象的一些概念。第二部分对Java应用程序接口集（API）中的各种数据结构接口和其中涉及到的算法及算法分析进行了详细介绍，并用实例说明了如何使用这些数据结构。第三部分是这些数据结构在实际中的应用，每一章对不同应用的理论和具体实现做了详尽阐述。第四部分则针对第6章应用程序接口集中介绍过的各种数据结构接口，分别给予更加细致的实例解说。第五部分介绍了一些高级的数据结构。\r\n\r\n 通过对本书的学习，读者能够抽象地思考不同数据结构的功能，了解它们之间的相关性，掌握在计算机工程中使用这些数据结构的能力。\r\n\r\n 本书概念清楚，逻辑性强，内容新颖，可作为高等院校计算机软件专业与计算机应用专业学生的教材和参考用书，也可供计算机工程技术人员参考。\r\n
\r\n

第一部分 Java教程 \r\n\r\n 第1章 Java简介 2 \r\n\r\n 1.1 通用环境 2 \r\n\r\n 1.2 第一个程序 3 \r\n\r\n 1.3 基本数据类型 4 \r\n\r\n 1.4 基本运算符 5 \r\n\r\n 1.5 条件语句 7 \r\n\r\n 1.6 方法 11 \r\n\r\n 1.7 小结 13 \r\n\r\n 1.8 名词解释 13 \r\n\r\n 1.9 常见错误 14 \r\n\r\n 1.10 网上资源 14 \r\n\r\n 习题 15 \r\n\r\n 参考文献 16 \r\n\r\n 第2章 引用类型 17 \r\n\r\n 2.1 什么是引用 17 \r\n\r\n 2.2 对象和引用的基本概念 18 \r\n\r\n 2.3 字符串 21 \r\n\r\n 2.4 数组 23 \r\n\r\n 2.5 异常处理 30 \r\n\r\n 2.6 输入和输出 32 \r\n\r\n 2.7 小结 35 \r\n\r\n 2.8 名词解释 37 \r\n\r\n 2.9 常见错误 38 \r\n\r\n 2.10 网上资源 38 \r\n\r\n 习题 38 \r\n\r\n 参考文献 39 \r\n\r\n 第3章 对象与类 40 \r\n\r\n 3.1 何为面向对象编程 40 \r\n\r\n 3.2 一个简单的例子 41 \r\n\r\n 3.3 JavaDOC 42 \r\n\r\n 3.4 基本方法 43 \r\n\r\n 3.5 附加结构 46 \r\n\r\n 3.6 包 49 \r\n\r\n 3.7 设计模式：复合 52 \r\n\r\n 3.8 小结 52 \r\n\r\n 3.9 名词解释 53 \r\n\r\n 3.10 常见错误 54 \r\n\r\n 3.11 网上资源 55 \r\n\r\n 习题 55 \r\n\r\n 参考文献 57 \r\n\r\n 第4章 继承 58 \r\n\r\n 4.1 什么是继承 58 \r\n\r\n 4.2 层次结构设计 68 \r\n\r\n 4.3 多重继承 71 \r\n\r\n 4.4 接口 72 \r\n\r\n 4.5 Java中的基础继承体系 74 \r\n\r\n 4.6 通用实现组件 77 \r\n\r\n 4.7 函数（函数对象） 82 \r\n\r\n 4.8 动态绑定细节 87 \r\n\r\n 4.9 小结 89 \r\n\r\n 4.10 名词解释 90 \r\n\r\n 4.11 常见错误 91 \r\n\r\n 4.12 网上资源 91 \r\n\r\n 习题 92 \r\n\r\n 参考文献 95 \r\n\r\n 第二部分 算法与程序构建 \r\n\r\n 第5章 算法分析 98 \r\n\r\n 5.1 什么是算法分析 98 \r\n\r\n 5.2 算法运行时间举例 100 \r\n\r\n 5.3 最大连续子序列之和的问题 101 \r\n\r\n 5.4 通用Big-Oh规则 106 \r\n\r\n 5.5 对数 108 \r\n\r\n 5.6 静态搜索问题 109 \r\n\r\n 5.7 检验算法分析 112 \r\n\r\n 5.8 Big-Oh分析法的限制 113 \r\n\r\n 5.9 小结 113 \r\n\r\n 5.10 名词解释 113 \r\n\r\n 5.11 常见错误 114 \r\n\r\n 5.12 网上资源 114 \r\n\r\n 习题 114 \r\n\r\n 参考文献 118 \r\n\r\n 第6章 应用程序接口集 119 \r\n\r\n 6.1 简介 119 \r\n\r\n 6.2 迭代器模式 120 \r\n\r\n 6.3 应用程序接口集：容器和迭代器 123 \r\n\r\n 6.4 通用算法 127 \r\n\r\n 6.5 表接口 131 \r\n\r\n 6.6 栈和队列 134 \r\n\r\n 6.7 集合 137 \r\n\r\n 6.8 映射 142 \r\n\r\n 6.9 优先级队列 145 \r\n\r\n 6.10 小结 148 \r\n\r\n 6.11 名词解释 148 \r\n\r\n 6.12 常见错误 149 \r\n\r\n 6.13 网上资源 149 \r\n\r\n 习题 150 \r\n\r\n 参考文献 151 \r\n\r\n 第7章 递归 152 \r\n\r\n 7.1 什么是递归 152 \r\n\r\n 7.2 背景：通过数学归纳法证明 153 \r\n\r\n 7.3 基本递归 154 \r\n\r\n 7.4 数值应用 163 \r\n\r\n 7.5 分而治之算法 168 \r\n\r\n 7.6 动态规划 174 \r\n\r\n 7.7 回溯 177 \r\n\r\n 7.8 小结 180 \r\n\r\n 7.9 名词解释 181 \r\n\r\n 7.10 常见错误 181 \r\n\r\n 7.11 网上资源 181 \r\n\r\n 习题 182 \r\n\r\n 参考文献 184 \r\n\r\n 第8章 排序算法 185 \r\n\r\n 8.1 排序算法为什么重要 185 \r\n\r\n 8.2 基础知识 186 \r\n\r\n 8.3 插入排序算法和其他简单排序算法的分析 186 \r\n\r\n 8.4 希尔排序 188 \r\n\r\n 8.5 归并排序 190 \r\n\r\n 8.6 快速排序 192 \r\n\r\n 8.7 快速选择 202 \r\n\r\n 8.8 排序的下限 203 \r\n\r\n 8.9 小结 204 \r\n\r\n 8.10 名词解释 204 \r\n\r\n 8.11 常见错误 204 \r\n\r\n 8.12 网上资源 205 \r\n\r\n 习题 205 \r\n\r\n 参考文献 208 \r\n\r\n 第9章 随机化处理 209 \r\n\r\n 9.1 为什么需要随机数字 209 \r\n\r\n 9.2 随机数字发生器 209 \r\n\r\n 9.3 非均匀分布的随机数字 213 \r\n\r\n 9.4 产生随机排序 214 \r\n\r\n 9.5 随机化算法 215 \r\n\r\n 9.6 随机化初试 217 \r\n\r\n 9.7 小结 219 \r\n\r\n 9.8 名词解释 219 \r\n\r\n 9.9 常见错误 220 \r\n\r\n 9.10 网上资源 220 \r\n\r\n 习题 220 \r\n\r\n 参考文献 221 \r\n\r\n 第三部分 应用 \r\n\r\n 第10章 趣味游戏 224 \r\n\r\n 10.1 迷宫索字游戏 224 \r\n\r\n 10.2 Tic-Tac-Toe游戏 230 \r\n\r\n 10.3 小结 236 \r\n\r\n 10.4 名词解释 236 \r\n\r\n 10.5 常见错误 236 \r\n\r\n 10.6 网上资源 236 \r\n\r\n 习题 236 \r\n\r\n 参考文献 238 \r\n\r\n 第11章 栈和编译程序 239 \r\n\r\n 11.1 平衡符校验器 239 \r\n\r\n 11.2 一个简单的计算器 248 \r\n\r\n 11.3 小结 258 \r\n\r\n 11.4 名词解释 258 \r\n\r\n 11.5 常见错误 259 \r\n\r\n 11.6 网上资源 259 \r\n\r\n 习题 259 \r\n\r\n 参考文献 260 \r\n\r\n 第12章 公用程序 261 \r\n\r\n 12.1 文件压缩 261 \r\n\r\n 12.2 交叉引用发生器 276 \r\n\r\n 12.3 小结 279 \r\n\r\n 12.4 名词解释 279 \r\n\r\n 12.5 常见错误 280 \r\n\r\n 12.6 网上资源 280 \r\n\r\n 习题 280 \r\n\r\n 参考文献 282 \r\n\r\n 第13章 仿真 283 \r\n\r\n 13.1 Josephus问题 283 \r\n\r\n 13.2 事件驱动仿真 286 \r\n\r\n 13.3 小结 292 \r\n\r\n 13.4 名词解释 293 \r\n\r\n 13.5 常见错误 293 \r\n\r\n 13.6 网上资源 293 \r\n\r\n 习题 293 \r\n\r\n 第14章 图形和路径 295 \r\n\r\n 14.1 定义 295 \r\n\r\n 14.2 无权值最短路径问题 304 \r\n\r\n 14.3 正权值最短路径问题 307 \r\n\r\n 14.4 负权值最短路径问题 311 \r\n\r\n 14.5 无环图中的路径问题 313 \r\n\r\n 14.6 小结 318 \r\n\r\n 14.7 名词解释 318 \r\n\r\n 14.8 常见错误 319 \r\n\r\n 14.9 网上资源 319 \r\n\r\n 习题 319 \r\n\r\n 参考文献 321 \r\n\r\n 第四部分 实现 \r\n\r\n 第15章 内部类和数组表的实现 324 \r\n\r\n 15.1 迭代和嵌套类 324 \r\n\r\n 15.2 迭代类和内部类 326 \r\n\r\n 15.3 抽象集（AbstractCollection）类 328 \r\n\r\n 15.4 有迭代类的 ArrayList的实现 330 \r\n\r\n 15.5 小结 334 \r\n\r\n 15.6 名词解释 334 \r\n\r\n 15.7 常见错误 335 \r\n\r\n 15.8 网络资源 335 \r\n\r\n 习题 335 \r\n\r\n 第16章 堆栈和队列 337 \r\n\r\n 16.1 动态数组的实现 337 \r\n\r\n 16.2 链表的实现 345 \r\n\r\n 16.3 两种方法的对比 350 \r\n\r\n 16.4 java.util.Stack类 350 \r\n\r\n 16.5 双端队列 351 \r\n\r\n 16.6 小结 352 \r\n\r\n 16.7 名词解释 352 \r\n\r\n 16.8 常见错误 352 \r\n\r\n 16.9 网上资源 352 \r\n\r\n 习题 353 \r\n\r\n 第17章 链表 354 \r\n\r\n 17.1 基本概念 354 \r\n\r\n 17.2 Java 实现 357 \r\n\r\n 17.3 双向链表和循环链表 361 \r\n\r\n 17.4 排序链表 363 \r\n\r\n 17.5 API类库集中的LinkedList 类的实现 364 \r\n\r\n 17.6 小结 373 \r\n\r\n 17.7 名词解释 373 \r\n\r\n 17.8 常见错误 373 \r\n\r\n 17.9 网上资源 373 \r\n\r\n 习题 374 \r\n\r\n 第18章 树 376 \r\n\r\n 18.1 通用树 376 \r\n\r\n 18.2 二叉树 381 \r\n\r\n 18.3 递归和树 385 \r\n\r\n 18.4 树的遍历：iterator类 387 \r\n\r\n 18.5 小结 396 \r\n\r\n 18.6 名词解释 396 \r\n\r\n 18.7 常见错误 397 \r\n\r\n 18.8 网上资源 397 \r\n\r\n 习题 397 \r\n\r\n 第19章 二叉查找树 400 \r\n\r\n 19.1 基本思想 400 \r\n\r\n 19.2 静态顺序 407 \r\n\r\n 19.3 二叉查找树的操作分析 410 \r\n\r\n 19.4 AVL树 412 \r\n\r\n 19.5 红-黑树 418 \r\n\r\n 19.6 AA-树 427 \r\n\r\n 19.7 API类库中的集TreeSet和TreeMap类的实现 434 \r\n\r\n 19.8 B-树 446 \r\n\r\n 19.9 小结 449 \r\n\r\n 19.10 名词解释 450 \r\n\r\n 19.11 常见错误 451 \r\n\r\n 19.12 网上资源 451 \r\n\r\n 习题 451 \r\n\r\n 参考文献 453 \r\n\r\n 第20章 哈希表 455 \r\n\r\n 20.1 基本思想 455 \r\n\r\n 20.2 哈希函数 456 \r\n\r\n 20.3 线性探测 457 \r\n\r\n 20.4 二次探测 460 \r\n\r\n 20.5 单链哈希法 470 \r\n\r\n 20.6 哈希表与二叉查找树 470 \r\n\r\n 20.7 哈希法的应用 471 \r\n\r\n 20.8 小结 471 \r\n\r\n 20.9 名词解释 471 \r\n\r\n 20.10 常见错误 472 \r\n\r\n 20.11 网上资源 472 \r\n\r\n 习题 472 \r\n\r\n 参考文献 474 \r\n\r\n 第21章 优先队列：二分堆 475 \r\n\r\n 21.1 基本思想 475 \r\n\r\n 21.2 基本操作的实现 479 \r\n\r\n 21.3 buildHeap操作：线性时间堆结构 482 \r\n\r\n 21.4 高级操作：decreaseKey和merge 484 \r\n\r\n 21.5 内部排序：堆排序 485 \r\n\r\n 21.6 外部排序 487 \r\n\r\n 21.7 小结 491 \r\n\r\n 21.8 名词解释 491 \r\n\r\n 21.9 常见错误 492 \r\n\r\n 21.10 网上资源 492 \r\n\r\n 习题 492 \r\n\r\n 参考文献 494 \r\n\r\n 第五部分 高级数据结构 \r\n\r\n 第22章 splay树 498 \r\n\r\n 22.1 自动调整和分步偿付 498 \r\n\r\n 22.2 基本的自下而上的splay树 500 \r\n\r\n 22.3 基本的splay树操作 501 \r\n\r\n 22.4 自底而上的splay树的分析 502 \r\n\r\n 22.5 自顶而下的splay树的分析 505 \r\n\r\n 22.6 自顶而下splay树的实现 508 \r\n\r\n 22.7 splay树和其他查找树的比较 512 \r\n\r\n 22.8 小结 512 \r\n\r\n 22.9 名词解释 512 \r\n\r\n 22.10 常见错误 512 \r\n\r\n 22.11 网上资源 512 \r\n\r\n 习题 513 \r\n\r\n 参考文献 513 \r\n\r\n 第23章 归并优先级队列 515 \r\n\r\n 23.1 非对称堆 515 \r\n\r\n 23.2 对称堆 518 \r\n\r\n 23.3 小结 526 \r\n\r\n 23.4 名词解释 527 \r\n\r\n 23.5 常见错误 527 \r\n\r\n 23.6 网上资源 527 \r\n\r\n 习题 527 \r\n\r\n 参考文献 528 \r\n\r\n 第24章 不相交集合类 529 \r\n\r\n 24.1 等价关系 529 \r\n\r\n 24.2 动态等价及应用 529 \r\n\r\n 24.3 快速查找算法 536 \r\n\r\n 24.4 快速合并算法 536 \r\n\r\n 24.5 Java实现 539 \r\n\r\n 24.6 根据层合并和路径压缩的最差情况 541 \r\n\r\n 24.7 小结 545 \r\n\r\n 24.8 名词解释 546 \r\n\r\n 24.9 常见错误 546 \r\n\r\n 24.10 网上资源 546 \r\n\r\n 习题 546 \r\n\r\n 参考文献 548 \r\n\r\n 附录A 运算符 550 \r\n\r\n 附录B 图形用户界面 551 \r\n\r\n 附录 C 位运算符 569 \r\n
\r\n

本书的主要内容包括：Java程序语言的引用类型. 对象与类. 继承, Collection程序用户接口. 递归. 排序算法. 随机化处理等算法分析, 趣味游戏. 栈和编译程序. 共用程序. 仿真. 图形和路径等应用, 内部类和数组表. 栈和队列. 链表. 树. 二叉查找树. 哈希表. 二分堆等实现, Splay树. 归并优先级队列. 分解设置类等高级数据结构.

本书逻辑层次清楚, 结构为积木状, 内容深入而全面, 从上述介绍中可以看出全书构成了一个逻辑整体, 主要包括语言. 算法. 应用. 实现和高级数据结构等, 采用了Java程序语言描述, Java具有跨平台和重用等优异特性, Java语言是适用于分布式计算环境的面向对象的编程语言, 是比C++更安全. 移植性更强并且更易于使用的语言. 在目前的软件研制和开发中得到了广泛的应用. 本书是一部完整的教材, 既注重了理论分析, 又注重了实际应用. 不但重点描述了有实际应用意义的数据结构, 而且也介绍了几乎所有的流行的数据结构, 并使用了数据结构库Java应用程序接口集. 学生通过本教材的学习, 可以较系统地学习Java程序语言设计. 算法设计与分析. 数据结构实现及应用方面的内容, 进而为学习计算机科学与技术. 设计优秀程序建立坚实的基础.

在本书的前言中, 作者较详细地介绍了全书的内容, 对全书各章的内容和相互关系与独立性做了精辟的描述, 对使用本书提出了指导性计划.

本书作者 Mark Allen Weiss教授在美国普林斯顿大学获计算机科学博士学位, 现任佛罗里达国际大学计算机科学学院的教授, 他研究的领域包括数据结构. 算法及教育. 本书受到高度称赞, 并被世界各地的上百所大学所采用.

使用这本书的学生应具备面向对象或程序设计语言的知识. 需要有数据类型. 运算符. 控制结构. 函数（方法）和输入输出（但不一定是数组和类）基本特性的基础等.

为了学习优秀的外国计算机教材的内容, 我们将其翻译出来, 奉献给我国的计算机教育界, 供大家参考. 本书中译本的出现是我和我的研究生们集体劳动的结晶. 硕士研究生吴红梅. 张晓佳. 朱新月. 王玉亭. 王浩丽. 王国庆. 陈琳. 张颖. 郭新. 齐亚丽. 申玲. 张丽萍. 依学华. 王振武. 刘挣. 张琳参加了翻译. 博士研究生鲁强. 万本庭也参加了翻译和部分校对工作. 陈清夷对本书进行了审校.

限于译者的业务和英语水平, 翻译中难免出现不妥之处, 敬请批评指正.

本书是为计算机科学领域中的以下两部分设计的. 它从通常所知的数据结构（CS-2）开始, 接着介绍高级数据结构和算法分析.

CS-2部分的内容已经发展了一段时间, 虽然对主体部分已经有了大体一致的意见, 但在一些细节部分仍存在一些值得考虑的分歧. 一个统一认可的主题是软件发展的原则, 最引人注目的压缩概念和信息隐藏技术. 所有CS-2部分要包括一个对运行时间. 循环. 基本排序算法和基本数据结构的介绍. 许多大学开设了涉及到数据结构. 算法分析和运行时间分析的高级课程. 本书在内容设计上适用于这两个层次的课程, 这样就不需要第二本书了.

虽然在CS-2中最激烈的讨论是围绕一种编程语言的选择问题, 但仍有其他的基本问题要做出选择. 这包括：

● 是否要早些介绍面向对象设计或基于对象设计

● 数理精确的水平

● 数据结构工具与其用途之间的适当平衡

● 关系到语言选择的程序设计细节（例如, 应该早些用图形用户界面吗？）

撰写这些教学内容的目的是从抽象思维和解决问题的方法为出发点, 以提供对数据结构和算法的一个实用性介绍. 尽量涵盖到那些关系到数据结构. 分析及其Java工具的所有重要细节, 同时又避开了那些理论上令人感兴趣却没有广泛用途的数据结构. 但要覆盖到所有不同的数据结构（包括用法和分析）, 并在书中以简单的过程描述出来, 这一点是不可能的. 所以把这本书设计得能使教师在主题的侧重方面有一定的灵活性. 教师需要在理论和实践之间把握一个适度的平衡, 并选择那些最适合课程的内容. 正如稍后要讲到的, 文章的组织会使不同章节间的依赖性减小到最低限度.

惟一的方式

笔者的基本前提是, 在各种语言中软件开发工具以库的形式出现, 并且许多数据结构是库的一部分. 预计数据结构课程最终会经历从实现到实际使用的转化, 在这本书中, 笔者总是采取分别讲述这些数据结构的详细说明和相关的实用方法的步骤, 并用到一个已存在的数据结构库Java 应用程序接口（API）集.

第二部分以一个简单的章节（第6章）讨论了适用于大多数应用软件的API集的一个子集. 这一部分也覆盖了基本分析技术. 递归. 循环和排序. 第三部分包括一些实用API集数据结构的应用程序. 使用过的数据结构要到第四部分才给出它的API集的实现. 因为API集自从Java的1.2版就是它的一部分（老一些的编译器能使用本书的API集的代码——参阅“代码可用性”的相关内容）, 学生们可以使用已有的软件组件来设计大的项目.

尽管本书的中心是使用API集, 然而它既不是一本专门关于API集的书籍, 也不是一本专门介绍如何实现API集的入门教材, 它仍然是一本重点强调数据结构和基本问题求解技术的书籍. 当然, 在数据结构设计中使用的通常方法对于API集的实现也非常适用, 所以第四部分中的几个章节包括了API集的实现方法. 但教师也可以选择第四部分中那些没有涉及API集协议的简单方法. 介绍API集的第6章对于理解第三部分中的代码非常有用. 笔者试着只使用API集中的基本部分.

许多教师宁愿选择一种更传统的方式, 在此方式中每一数据结构被定义. 实现和使用. 因为第三部分和第四部分中的内容并没有相互依赖性, 所以从这本书出发可以很容易地讲授传统意义上的课程.

预备知识

使用本书的学生应具备一种面向对象或程序设计语言的知识. 需要有基本特性的知识, 包括旧式数据类型. 运算符. 控制结构, 函数（方法）和输入输出（但不一定是数组和类）, 等等.

已经学过怎样使用C++或Java课程的学生会发现, 起初四章某些地方阅读起来会很轻松, 但一些简介部分没有涉及到的Java细节, 阅读起来就有了一定的难度.

学习其他语言的学生应从第1章开始, 并且要进行得缓慢一些. 如果有的学生想选择一本Java参考书籍, 第1章里就推荐了一些好书.

离散数学的知识很有帮助, 但并不是必须提前具备的知识. 我们列举了几个数学证明, 但对更多的复杂证明只做了简要的回顾. 第7章. 第19章至第24章要求具备一定的数学修养. 教师也可选择跳过数学证明部分, 只给出结果.

第二版的变化摘要

1. 重写了第一部分中的一些内容. 在第2章中列举了一些基本的数组后, 提出了一个数组列表和add方法的讨论. 第3章的内容现在包括一个更详细的关于静态字段和方法的例子. 第4章改写了对于继承性的讨论以简化最初的介绍. 章节的末尾包括了一些更深层次的Java细节, 这些对于高级用户来说是很重要的.

2. 在设计模型中的内容已经被安排到书中的各个部分. 包括：第3章描述了部分构造, 封装. 衔接器. 修饰和运算符在第4章中描述, 迭代器在第6章中进行描述.

3. 第二部分中的数据结构章节用API集进行了改写. 通用接口（与第一版相同）和API集接口在修订后的第6章中做了说明.

4. 第三部分的代码是基于API集的, 好几处代码比以前更趋于面向对象. 霍夫曼编码的例子有了完整的代码.

5. 在第四部分中, 普通数据结构被改写得更加简洁和清晰. 另外, 如同固有的方法那样, 在第四部分各章节的末尾说明了一个更简易的API集实现. 实现的组件包括数组列表. 链表. 栈. 树集合. 树映射. 哈希集合. 哈希映射和各种接口. 函数对象与算法.

Java

本书使用的描述语言是Java. 与C++相比, Java是一门经常用于测试的较新的语言. Java有很多优点, 编程者经常把Java作为一门比C++来说更安全. 移植性更强, 并且更易于使用的语言.

当编写此教材时, Java的用法使我们必须做一些决定, 决定如下所示：

1. 所要求的编译器至少要有Java 1.2：当然所有代码在Java 1.3或1.4下都能运行, 然而使用API集要求Java 1.2编译器. 请确认正在使用的编译器是否与Java 1.2兼容.

2. 不强调图形用户界面（GUI）：虽然GUI是Java的一大特色, 但比起核心的CS-2主题来, 它们只不过是一种应用执行细节. 在正文中不使用Swing, 但由于许多教师也许希望这样做, 所以在附录中提供了一个对Swing的简明介绍.

3. 不强调Applet：Applet使用GUI, 另外此课程的着眼点在数据结构而不是语言特性. 那些想讨论Applet的教师需要给本教材配备一本Java参考书.

4. 使用内部类：主要在API集的实现中用到, 并且教师可以避开它（如果这样做的话）.

5. 当介绍各种引用变量时提到了指针的概念：Java并没有指针类型. 相反, 它有一个引用类型. 然而, 指针历来是需要介绍的一个重要的CS-2主题. 当讨论到引用变量时, 会用其他语言来描述指针.

6. 没有讨论线程：CS委员会的一些成员认为多线程计算应成为CS-1/2主题的核心. 虽然在将来这有可能发生, 但很少有CS-1/2课程涉及到这个复杂问题.

同其他编程语言一样, Java也有一些劣势. 它不直接支持通用编程, 而是需要一个工作环境, 这会在第4章中讨论. I/O能够支持最小范围的Java使用. 书中的所有例子都是最小程度地使用Java的I/O能力.

内容组织

笔者在第一部分介绍Java和面向对象编程（尤其是抽象的）. 在类和继承的设计以前, 将会讲到基本类型. 引用类型和预定义类以及异常. 这些章节的内容大体上是重写的, 这一版新增的是在设计模式上的内容.

在第二部分中讨论了Big-Oh和算法范例, 包括循环和随机. 我们用一个完整的章节讲解排序, 用一个单独的章节描述基本的数据结构. 在使用API集来描述接口和数据结构的运行时间上, 教师可采取多种途径来陈述保留的内容, 包括如下两点：

1. 在第四部分随着每种数据结构的介绍, 讨论相应的实现（无论是API版本还是更简易的版本）. 教师可以要求学生以不同的方式来扩展这些类（正如习题中建议的那样）.

2. 给出每种API集的类是如何使用的, 并且在课程中稍后一些的学习中涉及了实际执行. 第三部分的实例研究可以用来支持这一方法. 因为完整地实现在每一个较新版本的Java编译器中都可获得, 所以教师在编程练习中可以使用API集. 我们简单给出了使用这一方法的细节.

第五部分描述了高级数据结构, 例如Splay树. 堆对和不相关数据结构. 如果时间允许的话, 这些都可以讲解, 或者更可能的是在随后的课程中讲解.

章与章之间的组织

第一部分包括四章, 讲述了整个正文中使用的Java基础知识. 第1章描述基本类型, 并阐述如何使用Java编写基本的程序. 第2章讨论了引用类型, 并解释了指针的一般概念（尽管Java中没有指针）, 使学生们能顺利地学习这一重要的CS-2主题. 介绍了几个基本的引用类型（串. 数组. 文件和词法分析）并讨论了异常的使用. 第3章通过描述一个类如何实现来继续讨论. 第4章阐明了在设计层次（包括异常类和I/O）中继承的用法和类属成分. 在设计模式上的内容, 如封装. 衔接器. 装饰模式等, 也可以在第一部分中找到.

第二部分集介绍基本算法和构件. 在第5章提供了一个完整的时间复杂度和Big-Oh符号的讨论, 也讨论了二叉查找树. 第6章非常重要, 因为它覆盖了API集并直接说明了每种数据结构操作的运行时间（数据结构的实现, 无论是API集版本还是一个简化版本, 都在第四部分以后才提供）. 同嵌套类. 局部类和无名类一样, 这一章也介绍了遍历模式. 内部类推迟到第四部分, 在那里将它们作为实现技术来介绍. 第7章首先介绍用归纳法证明的概念, 描述了递归. 它也讨论了分而治之. 动态规划和回溯法. 其中, 有一节讲述了用以实现RSA密码体制的递归数值算法. 对许多学生来说, 第7章后半部分的内容对接下来的课程更适合一些. 第8章对几个基本的排序算法进行了描述. 编码和分析, 包括插入排序. 希尔排序. 归并排序和快速排序, 另外还有简洁排序. 它也证明了排序算法的典型下界, 并讨论了选择的相关问题. 最后的第9章很短, 讨论了随机数字, 包括它们的生成和在随机算法中的使用.

第三部分提供了几个研究实例, 并且每一章都围绕一个常规主题来组织. 第10章通过游戏测试阐明了几项重要技术. 第11章通过检验算法来核对平衡符和剖析算法的经典运行优先次序测试, 讨论了计算机语言中栈的应用. 我们为两个算法提供了完整的代码运行. 第12章讨论了文件压缩的实用程序和交叉应用的产生, 并提供了一个完整的实现. 第13章通过考察一个能被认为是仿真的问题和典型的事件驱动仿真来检验仿真. 最后第14章阐明数据结构是怎样有效实现几个图的最短路径算法.

第四部分给出了数据结构的实现. 第15章是新的一章, 它把内部类作为一种实现技术来讨论, 说明它们在数组表中的用法. 在第四部分的其他章节中, 提供了用于简单协议（插入. 查找. 删除等）的实现方法. 在一些情况中给出了API集的执行, 一般使用更复杂的Java语法（复杂是因为它们要求巨大的操作集合）. 在这一部分中, 尤其在第19章至第21章中, 用了一些数学内容, 教师可以选择跳过. 第16章提供了栈和队列的实现方法. 首先这些数据结构使用一个扩展数组实现, 接着使用链表实现. 在该章末尾讨论了API集版本. 在第17章给出了一般链表. 单独阐述了用一个简单协议的链表, 而在该章末尾给出了更复杂的. 使用双链表的API集版本. 第18章讲解了树, 并给出了基本遍历方案. 第19章是很详细的一章, 它给出了二叉查找树的几个实现方法. 一开始给出了基本的二叉查找树, 接着推出支持有序统计的二叉查找树. AVL树也讨论了, 但没有给出实现方法. 接着给出了红-黑树和AA-树的实现方法. 随后实现了API集的树集合和树映射. 最后检验了B-树. 在一个较简易的选择测试之后, 第20章讨论了哈希表, 并且把二次探测作为哈希集合和哈希映射的一部分来实现. 第21章叙述了二分堆并检验了堆排序和外部排序. 在Java 1.2的API集中没有优先队列, 所以我们执行了一个简易非标准版本.

第五部分包括适用于更高级课程或作为一般参考的内容. 其算法甚至大学一年级水平的读者也可以看懂. 然而要透彻了解的话, 就要具备超过了大学一年级学生能力的复杂数学算法知识. 第22章介绍了Splay树, 它是一种在实际应用中执行得相当好的二叉查找树, 在要求使用优先队列的应用程序中, 与二分堆相比, 很有竞争力. 第23章介绍了支持边缘操作的优先队列, 并提供了一种堆对的实现. 最后第24章检验了经典不相关的数据结构.

附录包括附加的Java参考资料. 附录A列出运算符和它们的优先级. 附录B列出有关Swing的资料, 附录C中介绍了在第12章中用到的位操作.

章节之间的依赖性

一般来说大多数章节之间是独立的. 然而, 以下有一些不可忽视的关联性：

● 第一部分（Java教程） ：前面的四章因它们的连续性, 应按顺序编写, 比其他部分要靠前.

● 第5章（算法分析）：比起第6章和第8章来, 这章应该先讲述. 递归（第7章）可以在这一章前先讲, 但教师可能为了避免低效率的递归而不得不解释一些细节.

● 第6章（应用程序接口集）：这一章可以在第三部分或第四部分之前讲授, 或与其相联系的内容一同讲授.

● 第7章（递归）：7.1节至7.3节中的内容应在讨论递归排序算法. 树. Tic-Tac-Toe实例研究和最短路径算法之前提到. 像RSA密码体制. 动态规划和回溯等内容则是可以任选的.

● 第8章（排序算法）：这一章应是接着第5章和第7章的. 然而没有第5章. 第7章, 也能讲授希尔排序, 希尔排序没有用到递归. 关于运行时间实在太复杂了, 所以在这本书里没有介绍.

● 第15章（内部类和数组表的实现）：这一部分内容应在API集的实现方法讨论之前介绍.

● 第16章（栈和队列）. 第17章（链表）：这两章可以以任意顺序讲授. 然而, 笔者认为应先讲述第16章, 因为它提供了一个较简单的链表的例子.

● 第18章（树）. 第19章（二叉查找树）：这两章可以以任意顺序讲授或同时进行.

独立的章节

以下各章没有或很少有依赖性：

● 第9章（随机化处理）：关于随机数字的内容可以按需要在任意进度讲授.

● 第三部分（应用）：第10章至第14章可同API集相联系或在其后涉及, 并可以按随意的顺序讲授, 并为早期的一些章节提供了参考, 包括10.2节（Tic-Tac-Toe游戏）参考了7.7节中的一个讨论, 12.2节（交叉引用发生器）引用了在11.1节（平衡符校验器）中的类似词典分析的代码.

● 第20章和第21章（哈希表/一个优先级队列）：这两章的内容自成一体, 可在任何时候讲授.

● 第五部分（高级数据结构）：在第22章至第24章中的内容是自成体系的, 通常在后续课程中讲授.

数学知识的要求

考虑到在强调理论的CS-2课程中的使用和要求更多分析的后续课程, 笔者一直尝试着提供一个数学标准. 然而这一内容是以独立的“定理”, 并且是以单独部分或从属部分出现的. 所以指导教师不强调理论时可以跳过.

在所有的场合, 定理的证明对定理的理解并不重要. 这是接口（定理阐述）与实现（证明）分离的又一个例子. 一些原本的教学资料, 例如7.4节（递归的数值应用）可以跳过而不影响其他章节的理解.

课程组织

在讲授课程中一个关键问题是决定如何使用第二部分至第四部分中的内容. 在第一部分中的内容应深入讲解, 学生应练习写出一到两个程序, 它能表明设计. 实现. 类的测试和一般类, 并且有可能在面向对象设计和使用继承性方面下些功夫. 第5章讨论Big-Oh符号, 学生可以做一个短程序的练习, 分析一下运行时间, 这个练习可用来测试理解力.

第6章的关键概念是不同的数据结构以不同的效率支持不同的途径模式. 任何情况的研究（除了Tic-Tac-Toe例子, 它都使用递归）都可用来表明数据结构的应用. 以这种方式学生可以了解数据结构和它的使用, 但并不包括它的有效实现. 这确实是一个独立体, 以这种方式看问题会极大地发展学生抽象思考的能力. 学生也可以提供某些API集的简易实现方式（在第6章的习题中给出了一些建议）, 并且可以看到在已存在API集的高效数据结构的实现方式和为它们写的低效数据结构实现方式之间的不同. 也可要求学生以扩展情况来研究, 但另一方面来说不应要求他们了解数据结构的每一个细节.

高效数据结构的实现可以留待以后讨论. 无论何时, 只要是在二叉查找树之前, 教师都可以在他认为合适的时候介绍递归. 排序的详细问题可以在递归之后的任一时间讨论. 在这一点上, 课程可使用同样的实例研究和数据结构的实现修正实验来继续. 例如学生可使用二叉查找树的不同形式来做试验.

选择更传统方式的教师可在第四部分讨论一个数据结构的实现之后, 简单地讨论一个实例研究. 另外, 在第三部分中章节设计尽可能地保持相互之间的独立性.

习题

习题可以有不同的风格, 这里提供四种不同的习题形式. 在最基本的“简答题”中, 一般是问一个简单问题或手写一个正文中算法的模拟. 在“理论题”部分提出一些问题, 这些问题要么是要求数学分析, 要么是要求给出理论上令人感兴趣的解决方法. “实践题”部分包括简单的程序问题, 有关于句法的问题或特别的代码技巧问题. 最后, “编程题”部分是扩展任务的一些想法.

教学特点

● “名词解释”部分列出了重要的技术术语.

● “常见错误”部分在每一章的末尾给出了普遍易犯的错误列表.

● 在大多数章节末尾给出了帮助进一步阅读理解的“参考文献”.

代码和可得到的演示文稿

正文中的代码已经函数化了, 并且在Sun的JDK 1.2, 1.3和1.4中测试过. 在http://www.aw .com/cssupport上能够找到. 每章末尾的“网上资源”部分列出了章节代码的文件名. 书中各种图示的幻灯片也可以在这个地址中获得.

教师的资源指南

可以获得解释几种有关这一内容的不同途径的“教师指南”. 分类包括按问题测试. 按任务分派和按音节, 并且也提供了所选习题的答案. 教师可以联系他们当地的Addison Wesley销售代表来索取相关的信息（参见书后的“教学支持说明”）. 这份指南只提供给教师使用.

致谢

在准备此书的过程当中有许多人帮助过我, 有一些已经在第一版及相关的主题中介绍过了. 其他人太多了以至于无法一一列出, 他们都曾发送E-mail指出错误, 或者指出笔者在这一版本中努力修正的不协调之处.

我想感谢在Addison-Wesley的所有朋友：编辑Susan Hartman Sullivan和项目编辑Katherine Harutunian, 他们帮助我做关于Java材料组织安排上的一些困难问题的决定, 并对这本书的付诸成型做了很大贡献. Gina Hagen设计了一个漂亮的封面. 一如既往, Michael Hirsch为市场拓展工作做了很大贡献. 尤其要感谢本书出版编辑Pat Mahtani和Caroline Roop, 感谢他们为整个工作的协调所做出的贡献.

还要感谢评论者给出的有价值的点评, 具体如下：

Divyakant Agrawal, University of California at Santa Barbara

Claude W. Anderson, Rose-Hulman Institute of Technology

David Avis, McGill University

Michael Clancy, University of California at Berkeley

Chris Eason, Valdosta State University

Tim Herman, Digital Anatomy, Inc.

Curdip Singh, Kansas State University

正文中的某些材料改编自教材“Efficient C Programming: A Practical Approach”（Prentice-Hall, 1995）, 得到了出版者的许可. 我已在合适的地方做了一些章末附注.

笔者的网页http：//www.cs.fiu.edu/~weiss会提供最新源代码. 一个错误列表和接受bug报告的链接.