数据抽象和问题求解—— Java语言描述(第2版) (2008 年度畅销榜NO.42386 )

本书全面系统地讲述了如何利用Java语言解决实际问题，重点剖析了数据结构和数据抽象的核心概念，并通过大量示例向读者展示了面向对象程序设计理念的精髓。本书在第1版的基础上完善了所有的Java代码，使用UML处理了所有伪代码，通过准确的概念讲解、贴切的示例和范围广泛的问题讨论，使老师和学生的教与学都变得轻松自如。本书能够使读者系统地掌握问题求解技术和相关的编程技能，为日后的软件开发工作打下坚实的基础。
本书表述严谨、推理缜密，适合作为计算机及相关专业本科学生的教材，也是一本技术含量很高的专业参考书。

第I部分 问题求解技术
第1章 Java编程基础 3
1.1 程序结构 3
1.1.1 包 3
1.1.2 类 5
1.1.3 数据字段 5
1.1.4 方法 6
1.1.5 对象成员的访问方法 8
1.2 Java基础知识 8
1.2.1 注释 8
1.2.2 标识符和关键字 9
1.2.3 变量 9
1.2.4 基本数据类型 9
1.2.5 引用 10
1.2.6 字面常量 10
1.2.7 命名常量 11
1.2.8 赋值和表达式 11
1.2.9 数组 14
1.3 分支结构 17
1.3.1 if语句 17
1.3.2 switch语句 18
1.4 循环结构 19
1.4.1 while语句 19
1.4.2 for语句 19
1.4.3 do语句 22
1.5 有用的Java类 22
1.5.1 Object类 23
1.5.2 字符串类 23
1.6 Java异常 26
1.6.1 捕获异常 27
1.6.2 抛出异常 32
1.7 文本输入和输出 33
1.7.1 输入 33
1.7.2 输出 35
1.8 文件输入和输出 37
1.8.1 文本文件 38
1.8.2 对象串行化 45
1.9 小结 47
1.10 提示 50
第2章 编程原理与软件工程 51
2.1 问题求解与软件工程 51
2.1.1 问题求解的含义 51
2.1.2 软件的生命周期 52
2.1.3 优秀的解决方案 59
2.2 面向对象设计 60
2.2.1 抽象与信息隐藏 60
2.2.2 面向对象的设计 62
2.2.3 功能分解 64
2.2.4 一般设计原则 65
2.2.5 使用UML为面向对象的
设计建模 65
2.2.6 面向对象方式的优点 68
2.3 关键编程问题 68
2.3.1 模块化 69
2.3.2 可修改性 70
2.3.3 易用性 71
2.3.4 防故障编程 72
2.3.5 风格 77
2.3.6 调试 80
2.4 小结 82
2.5 提示 83
2.6 自我测试题 83
2.7 练习题 83
2.8 编程问题 86

第3章 递归：镜子 89
3.1 递归解决方案 89
3.1.1 递归值方法：n的阶乘 92
3.1.2 递归void方法：逆置
字符串 97
3.2 计数 105
3.2.1 兔子繁殖(Fibonacci序列) 105
3.2.2 组织游行队伍 108
3.2.3 Spock的困惑 109
3.3 数组查找 111
3.3.1 查找数组的最大项 111
3.3.2 二叉查找 112
3.3.3 查找数组中的
第k个最小项 116
3.4 组织数据 118
3.5 递归与效率 123
3.6 小结 126
3.7 提示 126
3.8 自我测试题 127
3.9 练习题 127
3.10 编程问题 133
第4章 数据抽象：墙 135
4.1 抽象数据类型 135
4.2 指定ADT 139
4.2.1 ADT列表 139
4.2.2 ADT有序表 144
4.2.3 设计ADT 145
4.2.4 公理(可选) 148
4.3 实现ADT 150
4.3.1 Java类 152
4.3.2 Java接口 158
4.3.3 Java包 161
4.3.4 基于数组的ADT
列表的实现 162
4.4 小结 168
4.5 提示 168


4.6 自我测试题 169
4.7 练习题 169
4.8 编程问题 171
第5章 链表 173
5.1 预备知识 173
5.1.1 对象引用 174
5.1.2 变长数组 177
5.1.3 基于引用的链表 178
5.2 链表编程 182
5.2.1 显示链表的内容 182
5.2.2 从链表中删除
指定的节点 183
5.2.3 在链表的指定位置
插入节点 185
5.2.4 ADT列表的基于
引用的实现 190
5.2.5 比较基于数组的实现
和基于引用的实现 194
5.2.6 将链表传给方法 195
5.2.7 递归地处理链表 196
5.3 链表的各种变体 200
5.3.1 尾引用 200
5.3.2 循环链表 201
5.3.3 虚拟头节点 203
5.3.4 双向链表 203
5.4 清单应用程序 206
5.5 Java集合框架 210
5.5.1 泛型 211
5.5.2 迭代器 212
5.5.3 JCF的List接口 214
5.6 小结 217
5.7 提示 218
5.8 自我测试题 219
5.9 练习题 221
5.10 编程问题 223


第Ⅱ部分 使用抽象数据
类型解决问题
第6章 递归问题求解技术 229
6.1 回溯 229
6.2 定义语言 234
6.2.1 语法知识基础 234
6.2.2 两种简单语言 236
6.2.3 代数表达式 238
6.3 递归和数学归纳法的关系 245
6.3.1 factorial递归算法的
正确性 246
6.3.2 Hanoi塔的成本 246
6.4 小结 248
6.5 提示 248
6.6 自我测试题 249
6.7 练习题 249
6.8 编程问题 252
第7章 栈 257
7.1 ADT栈 257
7.2 ADT栈的简单应用 262
7.2.1 检查括号匹配 262
7.2.2 识别语言中的字符串 265
7.3 ADT栈的实现 266
7.3.1 ADT栈的基于
数组的实现 268
7.3.2 ADT栈的基于
引用的实现 270
7.3.3 使用ADT列表的实现 271
7.3.4 各种实现的比较 273
7.3.5 JCF的Stack类 273
7.4 应用：代数表达式 275
7.4.1 计算后缀表达式 275
7.4.2 将中缀表达式转换为
后缀表达式 276
7.5 应用：查找问题 279


7.5.1 使用栈的非递归
解决方案 280
7.5.2 递归解决方案 286
7.6 栈和递归的关系 289
7.7 小结 290
7.8 提示 290
7.9 自我测试题 291
7.10 练习题 292
7.11 编程问题 295
第8章 队列 301
8.1 ADT队列 301
8.2 ADT队列的简单应用 303
8.2.1 读取字符串 303
8.2.2 识别回文 304
8.3 实现ADT队列 305
8.3.1 基于引用的实现 306
8.3.2 基于数组的实现 309
8.3.3 使用ADT列表的实现 314
8.3.4 JCF接口Queue 315
8.3.5 比较实现 317
8.4 基于位置的ADT总览 317
8.5 模拟应用 318
8.6 小结 326
8.7 提示 327
8.8 自我测试题 327
8.9 练习题 328
8.10 编程问题 330
第9章 高级Java主题 333
9.1 继承 333
9.1.1 Java访问修饰符 338
9.1.2 is-a和has-a关系 339
9.2 动态绑定和抽象类 341
9.2.1 抽象类 344
9.2.2 Java接口 347
9.3 ADT列表和有序表 348
9.4 Java泛型 352
9.4.1 泛型类 352
9.4.2 泛型通配符 354
9.4.3 泛型类和继承 354
9.4.4 类List的泛型实现 357
9.4.5 泛型方法 359
9.5 迭代器 359
9.6 小结 361
9.7 提示 361
9.8 自我测试题 361
9.9 练习题 362
9.10 编程问题 364
第10章 算法的效率和排序 367
10.1 确定算法的效率 367
10.1.1 算法的执行时间 368
10.1.2 算法增率 369
10.1.3 数量阶分析和大O
表示法 370
10.1.4 正确分析问题 373
10.1.5 查找算法的效率 374
10.2 排序算法及其效率 375
10.2.1 选择排序 376
10.2.2 冒泡排序 379
10.2.3 插入排序 380
10.2.4 归并排序 382
10.2.5 快速排序 387
10.2.6 基数排序 397
10.2.7 各种排序算法的比较 399
10.2.8 JCF的排序算法 399
10.3 小结 403
10.4 提示 403
10.5 自我测试题 404
10.6 练习题 405
10.7 编程问题 407
第11章 树 409
11.1 术语 410
11.2 ADT二叉树 415
11.2.1 ADT二叉树的
基本操作 416
11.2.2 ADT二叉树的
一般操作 416
11.2.3 二叉树的遍历 419
11.2.4 二叉树的表示 421
11.2.5 ADT二叉树的基于
引用的实现 424
11.2.6 使用迭代器遍历树 429
11.3 ADT二叉查找树 436
11.3.1 ADT二叉查找树
操作的算法 440
11.3.2 ADT二叉查找树的
基于引用的实现 453
11.3.3 二叉查找树操作的效率 457
11.3.4 树排序 460
11.3.5 将二叉查找树
保存到文件中 461
11.3.6 JCF的二叉树查找算法 463
11.4 一般树 464
11.5 小结 466
11.6 提示 466
11.7 自我测试题 467
11.8 练习题 468
11.9 编程问题 473
第12章 表和优先队列 477
12.1 ADT表 477
12.1.1 选择实现 483
12.1.2 ADT表的基于数组
的有序实现 488
12.1.3 ADT表的基于二叉
查找树的实现 490
12.2 ADT优先队列：
ADT表的变体 493
12.2.1 堆 495
12.2.2 ADT优先队列的
堆实现 503
12.2.3 堆排序 504
12.3 JCF中的表和优先队列 508
12.3.1 JCF的Map接口 508
12.3.2 JCF的Set接口 510
12.3.3 JCF的PriorityQueue类 513
12.4 小结 515
12.5 提示 516
12.6 自我测试题 516
12.7 练习题 517
12.8 编程问题 519
第13章 表的高级实现方案 521
13.1 平衡查找树 521
13.1.1 2-3树 522
13.1.2 2-3-4树 538
13.1.3 红-黑树 544
13.1.4 AVL树 548
13.2 散列 551
13.2.1 散列函数 554
13.2.2 解决冲突 556
13.2.3 散列效率 563
13.2.4 如何确立散列函数 565
13.2.5 表遍历：散列的
低效操作 567
13.2.6 JCF的Hashtable
和TreeMap类 567
13.2.7 Hashtable类 568
13.2.8 TreeMap类 570
13.3 按多种形式组织数据 572
13.4 小结 576
13.5 提示 577
13.6 自我测试题 577
13.7 练习题 578
13.8 编程问题 580
第14章 图 583
14.1 术语 583
14.2 将图作为ADT 585
14.2.1 实现图 586
14.2.2 用JCF实现Graph类 588
14.3 图的遍历 591
14.3.1 深度优先查找 592
14.3.2 广度优先查找 594
14.3.3 用JCF实现BFS
迭代器类 595

14.4 图的应用 598
14.4.1 拓扑排序 598
14.4.2 生成树 601
14.4.3 最小生成树 603
14.4.4 最短路径 606
14.4.5 回路 609
14.4.6 一些复杂问题 611
14.5 小结 612
14.6 提示 613
14.7 自我测试题 613
14.8 练习题 614
14.9 编程问题 617
第15章 外部方法 619
15.1 了解外部存储 619
15.2 排序外部文件的数据 621
15.3 外部表 628
15.3.1 确定外部文件的索引 630
15.3.2 外部散列 633
15.3.3 B-树 636
15.3.4 遍历 643
15.3.5 多索引 644
15.4 小结 645
15.5 提示 646
15.6 自我测试题 646
15.7 练习题 647
15.8 编程练习 649
附录A Java与C++的区别 651
附录B Unicode字符代码 655
附录C Java资源 657
附录D 数学归纳法 659
附录E Java操作符 665
附录F 术语表 669
附录G 自我测试题答案 685

本书是《数据抽象和问题求解—— Java语言描述》的第2版，相信本书会使您的教学或者学习大受裨益。Java目前已经成为计算机科学课程的主要语言之一，也非常适合以面向对象的方式讲解数据抽象原理。 本书基于Paul Helman和Robert Veroff合著的Intermediate Problem Solving and Data Structures:Walls and Mirrors(Benjamin/Cummings公司，1986年)，继承了原著的组织方式和理念，包括技术要点与正文内容、示例、图和练习题。Paul Helman和Robert Veroff教授把数据抽象和问题求解比喻为墙和镜子，并提出多种有利于教学的理念。 本书重点介绍数据抽象和其他主流的问题求解工具，非常适合作为计算机科学中级课程的教材。考虑到计算机科学的动态性和多样性，本书涵盖各种主题，以求适用于不同课程的教学要求。例如，可将本书用作数据结构入门级教材，也可用作高级程序设计和问题求解方面的教材。本书旨在使学生切实了解和掌握数据抽象、面向对象编程和其他高级问题求解技术。 第2版中的新增内容 基于Java 5：第2版进行了全面修订，以兼容Java的最新版本Java 5。书中的所有代码都修改为Java 5兼容版本。泛型是Java 5的重要部分，第9章将对它进行深入的讲解，并在后续章节中应用。 更多面向对象的Java知识：本书还增加了大量面向对象的Java语言知识，帮助学生从Java入门课程转向本课程。第1章概述了Java的重要概念，其中包括Java 5的新特性，例如Scanner类和自动装箱(autoboxing)。第9章重点介绍了Java的高级主题。 UML介绍：添加了UML(Unified Modeling Language，统一建模语言)的简要介绍，而且书中的所有伪代码都更新为使用UML。 使用Java集合框架：对Java集合框架(Java Collections Framework，JCF)的讨论贯穿全书，还新增了一些介绍JCF类的章节，提供了一些使用JCF类的示例。 其他扩充内容：其他的修订旨在提高整本书的可用性和可读性，包括一些新的练习和设计。 致学生 已经有成千上万的学生了解了“墙”和“镜子”的概念。“墙”和“镜子”代表两种贯穿全书的基本问题求解技术。“数据抽象”技术将模块的实现细节与程序的其余部分隔离开，就像一堵将您和邻居隔开的墙。“递归”是重复技术，通过解决同类型的小问题来解决问题，就像镜像一样，每次反射都会逐渐变小。 本书在编写时充分考虑了学生的需求。作者一直在从事教学工作，很明白清晰表述的重要性。本书在风格上力求明晰精练，通俗易懂。为了帮助学生学习本书，并通过练习进行复习，各章添加了小结、自我测试题及练习题，附录部分提供了自我测试题的答案和一个术语表。本书的第1章提供了Java参考资料。后面“本书概览”一节还列出了本书的主要特性。 第1章在章节概述中对学生掌握Java知识的情况作了几个基本的假定。有的学生可能是首次接触Java，或者需要对以前所学的Java知识进行全面回顾；而一些学生可能已经掌握了第1章中介绍的大部分编程知识。不管您属于哪一类，都需要知道if和switch分支结构，for、while和do迭代语句，类、方法、参数，数组，字符串和文件等。除了第1章中介绍的内容外，第9章还讨论了Java的一些高级主题，例如泛型和迭代器。本书还假定学生不具备使用递归方法的经验，所以在第3章和第6章中将讲述这方面的内容。 本书的所有Java源代码学生都可以使用。后面的“辅助资料”一节中将说明如何获取这些文件。 致教师 本书使用Java 5来描述数据抽象原理和数据结构。我们根据Java语言的优缺点，采用针对性的教学方法，力求做到实用、明确和透彻。 先决条件 本书要求学生了解Java的基础知识，或者了解另外一种高级语言，并有教师帮助他过渡到使用Java语言。对于没有Java语言背景的学生，可以通过第1章快速掌握其基本知识，为后面的学习打好基础。另外，本书还讨论了Java类，包括类的各种基本概念，诸如继承、多态性、接口和包。但本书只介绍这些与实现抽象数据类型(ADT)有关的内容，重点仍是ADT，而非Java。本书在基于对象的编程环境中介绍数据抽象，要求学生掌握面向对象设计和软件工程知识。这样，后面就会将注意力集中在数据抽象上。当然，我们还介绍了UML这种设计工具。 组织方式 本书分为两部分。一般而言，第1~11章是一学期的核心课程。第1~2章可作为学生的复习资料。可根据该课程在全部课程中的安排来选用第11~15章的内容。 安排灵活 本书内容详尽，教师可按课程计划，根据需要选择各章所讲的主题。下图列出了关联图，展示教师在教授某一章之前应帮助学生掌握的预备章节。 第I部分：问题求解技术 第I部分的前两章介绍了Java的基础知识、编程原理和软件工程，为进一步学习打下基础。第3章分析递归，帮助学生巩固基础知识；递归思维能力是计算机科学家必须掌握的实用技术之一，对理解问题的本质极具价值。这一章与后面的第6章全面、深入地讲解了递归技术，对它的应用也将贯穿全书。其中列举了大量递归实例，包括简单的递归定义，用于语言识别、查找和排序的递归算法等。 第4章详细讨论了数据抽象和抽象数据类型(ADT)。在讨论了ADT的规范和用法后，阐述了Java类、接口和包，并用它们来实现ADT。第5章在讨论Java引用变量和链表时介绍了其他的实现工具。 可根据学生的背景，选择并按适当顺序讲授这些主题。 第II部分：利用ADT解决问题 第II部分继续将数据抽象作为问题求解技术。首先指定栈、队列、二叉树、二叉查找树、表、堆和优先队列等基本ADT，然后将它们实现为类。在示例中使用ADT，并比较它们的实现。 第9章介绍继承、类之间的关系、泛型和迭代器，扩充学生的Java类知识。第10章介绍数量阶分析和大 O表示法，分析了递归归并排序、快速排序等几种查找和排序算法的效率。 第II部分还包括几个高级主题，如平衡查找树(2-3树、2-3-4树、红-黑树和AVL树)和散列，并用它们实现表。分析这些实现方案，确定它们最适合支持的操作。 最后分析从外部直接访问文件的数据存储器。修改归并排序来排序这些数据，用外部散列和B-树索引执行查找过程。这些查找算法是内部散列方案和2-3树的泛化。 在第I部分，可根据学生的背景选择讲授其中的主题。其中有3章介绍了数据抽象和递归。这两个主题都很重要，至于应首先介绍哪个，不同的人有不同的看法。本书是先介绍递归，后介绍数据抽象，但老师完全可以根据情况重新安排顺序。 第II部分亦是如此，老师可进行各种安排。例如，可在第7章(栈) 之前或之后讲解第9章(高级Java知识)的部分或者全部内容。在第6章后，可任意安排第10章(算法效率和排序)。可将树放在队列之前，或将图放在表之前；在讲授表后，可按任意顺序安排散列、平衡二叉查找树或优先队列。可提前讲授第15章的外部方法，例如，可在第10章的归并排序后讲授外部排序。 数据抽象 在本书介绍的问题求解方法中，普遍涉及到抽象数据类型(ADT)的设计和使用。一些例子说明如何将设计ADT作为解决方案总体设计的一部分。所有的ADT都是先用英语和伪码编写规范，然后将ADT用于简单的应用程序，最后考虑实现代码。ADT与实现它的数据结构的区别一直是中心议题。本书前面介绍了封装和Java类，以演示Java类如何对ADT的客户程序隐藏实现的数据结构。列表、栈、队列、树、表、堆和优先队列等抽象数据类型是讨论的重点。 问题求解 本书通过介绍计算机科学家的思考过程及所选用的技术，帮助学生学习如何整合问题求解和编程能力。学习计算机科学家如何开发、分析和实现解决方案与学习算法机制同等重要。 在示例问题中，包含了开发方案的分析技巧。抽象是对算法和数据结构的准确定义，而递归用于设计书中问题的解决方案。 本书先介绍Java引用和链表的处理，在构建数据结构时要用到它们。还简要介绍算法的数量阶分析。这种方式可先定性、后定量地分析基于数组和基于引用的数据结构的优缺点。强调各种可能的解决方案和实现之间的平衡是问题求解的中心内容。 在实现和验证解决方案时，编程风格、包含初始条件和结束条件的文档记录、调试工具和循环不变式是问题求解方法学的重要部分。这些内容将贯穿全书。 应用 在本书的重要主题中，列举了一些经典应用领域。例如，二叉查找、快速排序和归并算法提供了递归的重要应用，并引入了数量阶分析。平衡查找树、散列和文件索引等主题继续讨论了查找问题。在介绍外部文件时，又讨论了查找和排序。 本书首先在“递归”主题中介绍了识别和计算代数表达式的算法，后来又作为栈的应用讨论了这些问题。其他应用，如将八皇后(Eight Queens)问题作为回溯(backtracking)的例子，事件驱动模拟作为队列的一个应用，图查找和遍历作为栈和队列的其他重要应用。 本书概览 本书层次分明，组织精练，符合教材的特点。教师可按具体专业的要求做适当的调整。本书包含下面这些特色，不仅有助于学生第一次学习其中的内容，还有利于学生进行复习： ● 关键概念突出显示 ● 每章有“小结” ● 每章有“提示”，指明常见错误 ● 每章有“自我测试题”，书末附有“自我检测题答案” ● 每章有“练习题”和“编程问题”。难度较大的题目标有星号。答案在《教师资源手册》中 ● 用英语和伪码编写所有主要ADT的规范 ● 所有主要ADT的Java类定义

无封面