数据结构与问题求解：Java语言描述（原书第4版） [美]马克·艾伦·维斯

定　　价：169 元

• 作者：[美]马克·艾伦·维斯(Mark Allen Weiss)
• 出版时间：2024/5/1
• ISBN：9787111746874
• 出 版 社：机械工业出版社

• 中图法分类：TP312.8JA 
• 纸张：胶版纸
• 开本：16开

内容简介

本书从介绍什么是数据结构开始，继而对高级数据结构与算法进行分析。本书以独特的方式，清晰地将每种数据结构的接口与其实现分离开来，即将如何使用数据结构与如何对数据结构编程相分离，本书从抽象思维和问题求解的角度出发，为数据结构和算法提供实用的介绍，并采用现今流行的Java编程语言来实现，是数据结构与算法分析的理想教材。

编辑推荐

本书采用了一种独特的方法，将每个数据结构的接口(如何使用数据结构)与其实现(如何对数据结构进行编程)清晰地分离开来。从抽象思维和解决问题的角度提供了对数据结构和Java的实用介绍。全书主要分为五个部分，第一部分描述了贯穿全文的Java语言和面向对象编程的基础知识。第二部分讨论了算法和构成要素，包括大O、递归、随机化等内容。第三部分展示了几个经典的研究案例。第四部分介绍了每种数据结构的实现。第五部分讨论了适用于高级课程的数据结构。

序 言

前　　言
Data Structures and Problem Solving Using Java, Fourth Edition
本书是为计算机科学专业两学期系列课程而设计的，从典型的数据结构开始，然后介绍高级数据结构和算法分析。它适用于2001年计算机课程项目（CC2001，ACM和IEEE的联合项目）的最终报告所概述的“B.1导论课程”中两门或三门课程系列中的课程。
数据结构课程的内容已经发展了很多年。虽然涉及主题时有普遍的共识，但在细节上仍存在相当大的分歧。被一致接受的主题之一是软件开发原则，最突出的是封装和信息隐藏的概念。算法方面，所有数据结构课程都倾向于包括运行时间分析、递归、基本排序算法和基本数据结构的介绍。许多大学提供高级课程，涵盖更高层次的数据结构、算法及运行时间分析主题。本书的内容旨在涵盖两个层次的课程，所以不需要购买第二本教材。
虽然数据结构中最激烈的争论围绕着编程语言的选择，但也需要做出其他基本选择：
先介绍面向对象设计还是基于对象的设计。
数学严谨程度。
数据结构的实现和其用途之间的适当平衡。
与所选语言相关的编程细节（例如，GUI应该尽早使用）。
我编写这本书时的目的是，希望从抽象思维及问题求解的视角提供数据结构和算法的实用性介绍。我试图覆盖关于数据结构、数据结构的分析及其Java实现的所有重要细节，但同时避开在理论上有趣但没有广泛应用的数据结构。在一门课程中，不可能覆盖所有不同的数据结构，包括它们的使用及分析。所以，我设计了本书，让教师在选择主题时具有灵活性。教师需要在实践和理论方面进行适当的平衡，然后选择最适合课程的主题。正如我将在后面所讨论的，我组织内容时会尽量减少各章之间的依赖性。
第4版更新
提供了关于使用类（第2章）、编写类（第3章）及接口（第4章）的额外讨论。
第6章包含了附加资料，讨论了线性表的运行时间、映射的使用及Java Collections API中视图的使用。
描述了Scanner类，贯穿全书的代码使用了Scanner类。
第9章描述并实现了48位线性同余生成器，这是Java和C++库中的一部分。
第20章有一些关于独立链散列表及String hashCode方法的新资料。
对文字做了大量修订，改进了上一版的文字表达。
在第一、二和四部分提供了更多新练习。
独特的方法
我的基本前提是，所有语言中的软件开发工具都带有大型库，而且许多数据结构都是这些库的一部分。我设想最终将数据结构课程的重点从实现转移到使用。在本书中，我采用了独特的方法，将数据结构划分为规范说明和后续实现，并利用了已有的数据结构库Java Collections API。
第二部分的第6章讨论了适合大部分应用的Collections API的子集。第二部分还涉及基本分析技术、递归和排序。第三部分包含使用Collections API数据结构的众多应用程序。使用过的数据结构的Collections API的实现将在第四部分展示。因为Collections API是Java的一部分，所以学生可以在早期使用已有的软件组件设计大型项目。
尽管本书中主要使用了Collections API，但本书既不是关于Collections API的书，也不是关于实现Collections API的入门教材。本书仍是一本强调数据结构及基本的问题求解技术的书。当然，用来设计数据结构的一般技术也适用于Collections API的实现，所以第四部分的几章中包括了Collections API的实现。不过，教师可以选择第四部分中没有讨论Collections API协议的更简单的实现。用于介绍Collections API的第6章对理解第三部分中的代码很重要。我试图仅使用Collections API的基本部分。
很多教师更愿意选择传统的方法，即定义、实现然后使用每个数据结构。因为第三部分和第四部分的内容之间没有依赖性，所以使用本书也可以用来讲授传统课程。
先导课
使用本书的学生应该具备面向对象或面向过程程序设计语言的知识。假设学生已经了解了基本特性，包括基本数据类型、运算符、控制结构、函数（方法），以及输入输出（但不一定是数组和类）。
学习过C++或Java的学生可能发现前四章的某些地方阅读起来很轻松。不过，如果之前学过的课程中没有涉及Java细节的部分，阅读起来依然会相当困难。
学习过另一种语言的学生，应该从第1章开始，循序渐进。如果学生想使用一些Java参考书，那么第1章中给出了一些推荐。
离散数学的知识对本书的学习是有帮助的，但离散数学不是绝对必要的先导课。本书给出了几个数学证明，且在更复杂的证明之前都进行了简单的数学回顾。第7章和第19～24章需要一定程度的数学知识。教师可以选择简单跳过证明的数学内容，只给出结果。本书中的所有证明都清楚地标注出来。
Java
本书使用Java编程语言给出相关代码。Java语言常常与C++进行比较。Java更有优势，程序员常常认为Java比C++更安全、更便携、更易于使用。
在编写本书时，使用Java需要做一些决定。所做的决定如下：
需要的编译器版本最低是Java 5。请确保你正使用的编译器与Java 5兼容。
不强调GUI。虽然GUI是Java中一个很好的特性，但它们似乎是实现细节，而不是核心数据结构的主题。我们在书中没有使用Swing，但因为许多教师可能愿意使用，所以在附录B中对Swing进行了简短介绍。
不强调Applet。Applet使用GUI。另外，本书的重点是数据结构，而不是语言特性。愿意讨论Applet的教师需要使用Java参考资料来进行补充。
没有使用内部类。内部类主要用在Collections API的实现中，如果愿意的话，教师可以避免使用。
在介绍引用变量时讨论了指针的概念。Java没有指针类型，但有引用类型。不过，传统上指针是数据结构中需要介绍的重要主题。在讨论引用变量时我用其他语言说明了指针的概念。
没有讨论线程。计算机科学社区的有些成员在争论，在入门级编程系列课程中，多线程计算是否应该成为核心主题。虽然在未来这是有可能的，但很少有入门级编程课程讨论这个困难的主题。
Java 5的有些特性没有用到。包括：
静态引入。没有使用是因为在我看来，它实际上让代码变得难读。
枚举类型。没有使用是因为很少有地方能声明客户可用的公有枚举类型。在少数几个可能的地方，它似乎对代码的可读性没有帮助。
本书的组织
本书在第一部分介绍Java和面向对象编程（特别是抽象）。在设计类和继承之前，讨论了基本类型、引用类型和一些预定义的类及异常。
在第二部分，讨论了大O及算法范式，包括递归和随机。用完整的一章介绍排序，有一章描述了基本的数据结构。我使用Collections API来表示数据结构的接口和运行时间。在本书的这些章节中，教师可以采取几种方法来介绍其余的内容，包括以下两种：
当描述每种数据结构时，讨论第四部分中相应的实现（Collections API版本或更简单的版本）。教师可以按照练习中的建议，要求学生以不同的方式扩展类。
展示如何使用每个Collections API类，并在课程后期介绍其实现。第三部分的案例研究可用来支持这种方法。由于每个现代Java编译器都有完整的实现，因此教师可以在编程项目中使用Collections API。稍后给出使用这种方法的细节。
第五部分描述高级数据结构，如伸展树、配对堆和不相交集合数据结构，如果时间允许，可以介绍这些内容，或者在后续课程中介绍。
各章结构组织
第一部分由四章组成，描述了贯穿本书所用的Java的基本内容。第1章描述基本类型，说明如何用Java编写基本的程序。第2章讨论引用类型，说明指针的一般概念—虽然Java没有指针—以便学生能了解这个重要的数据结构主题；还说明了几种基本的引用类型（字符串、数组、文件和Scanner），讨论了异常的使用。第3章继续这个讨论，描述如何实现一个类。第4章说明了在设计层次关系中继承的使用（包括异常类和I/O）及泛型组件。包括包装类、适配器和装饰器模式在内的设计模式的资料都在第一部分讨论。
第二部分重点介绍基本算法和构成要素。第5章全面讨论时间复杂度和大O符号，还讨论并分析了二分搜索。第6章很重要，因为它涉及Collections API，并直观讨论了每个数据结构应该支持的操作的运行时间。（这些数据结构的实现，包括Collections API风格及简化版本，都在第四部分提供。）这一章还介绍了迭代器模式及嵌套类、局部类和匿名类。内部类推迟到第四部分，届时作为一种实现技术来讨论。第7章先介绍归纳法证明，从而描述递归，还讨论了分治、动态规划和回溯。其中一节描述了几个用于实现RSA加密系统的递归数值算法。对于许多学生来说，第7章后半部分的内容更适合后续课程。第8章描述并编写代码，分析了几个基本排序算法，包括插入排序、希尔排序、归并排序和快速排序，以及排序附带的内容，还证明了排序的经典下界，并讨论了选择的相关问题。最后，第9章是个简单的章节，讨论了随机数，包括它们的生成以及在随机算法中的使用。
第三部分提供了几个案例研究，每一章围绕一个一般性的主题进行组织。第10章通过研究游戏说明了一些重要的技术。第11章通过研究检查平衡符号的算法和经典的运算符优先级解析算法，讨论了栈在计算机语言中的使用，同时提供了这两个算法的完整代码实现。第12章讨论了文件压缩和交叉引用生成的基本实用程序，提供了二者的完整实现。第13章先观察了一个可以被视为模拟的问题，然后研究了更经典的事件驱动模拟，从而对模拟进行了广泛研究。最后，第14章说明了如何使用数据结构高效实现图的几种最短路径算法。
第四部分呈现了数据结构的实现。第15章讨论了作为一种实现技术的内部类，并说明了它们在实现ArrayList中的作用。在第四部分的其余章节中，提供了使用简单协议（insert、 find、remove及它们的变形）的实现。有些情况下，（除了由于需要大量的操作而变得复杂之外）还提出了倾向于使用更复杂Java语法的Collections API实现。这部分还运用了数学知识，特别是在第19～21章，可以由教师决定是否跳过。第16章提供了栈和队列的实现。这些数据结构首先使用扩展数组实现，然后使用链表实现。Collections API版本在第16章最后讨论。第17章描述了一般链表。单链表用一个简单的协议来说明，本章最后给出了使用双向链表的更复杂的Collections API版本。第18章描述了树

作者介绍

马克·艾伦·维斯（Mark Allen Weiss） 佛罗里达国际大学工程与计算学院杰出教授、副院长。他于1983年获得库伯高级科学艺术联合学院电子工程学士学位，并于1987年获得普林斯顿大学计算机科学博士学位。他是IEEE、AAAS会士和ACM杰出教育家。曾获SIGCSE计算机科学教育杰出贡献奖、IEEE泰勒·布斯教育奖、IEEE威廉·塞尔教育奖、ACM卡尔斯特罗姆杰出教育家奖。

目 录

目　　录
Data Structures and Problem Solving Using Java, Fourth Edition
译者序
前言
第一部分　Java之旅
第1章　Java的基本特性　　2
1.1　总体运行环境　　2
1.2　第一个程序　　3
1.2.1　注释　　3
1.2.2　main　　3
1.2.3　终端输出　　4
1.3　Java的基本类型　　4
1.3.1　基本类型　　4
1.3.2　常量　　4
1.3.3　基本类型的声明和初始化　　5
1.3.4　终端输入和输出　　5
1.4　基本运算符　　5
1.4.1　赋值运算符　　5
1.4.2　二元算术运算符　　6
1.4.3　一元运算符　　6
1.4.4　类型转换　　7
1.5　条件语句　　7
1.5.1　关系运算符和相等运算符　　7
1.5.2　逻辑运算符　　8
1.5.3　if语句　　8
1.5.4　while语句　　9
1.5.5　for语句　　9
1.5.6　do语句　　10
1.5.7　break和continue语句　　11
1.5.8　switch语句　　11
1.5.9　条件运算符　　12
1.6　方法　　12
1.6.1　方法名的重载　　13
1.6.2　存储类　　13
1.7　总结　　13
1.8　核心概念　　14
1.9　常见错误　　15
1.10　网络资源　　15
1.11　练习　　15
1.12　参考文献　　16
第2章　引用类型　　18
2.1　什么是引用　　18
2.2　对象和引用的基础知识　　19
2.2.1　点运算符　　19
2.2.2　对象的声明　　20
2.2.3　垃圾收集　　20
2.2.4　=的含义　　21
2.2.5　参数传递　　22
2.2.6　==的含义　　22
2.2.7　没有对象的运算符重载　　23
2.3　字符串　　23
2.3.1　字符串操作的基础　　23
2.3.2　字符串连接　　23
2.3.3　字符串比较　　24
2.3.4　其他String方法　　24
2.3.5　将其他类型转换为字符串　　24
2.4　数组　　25
2.4.1　声明、赋值和方法　　25
2.4.2　动态数组扩展　　27
2.4.3　ArrayList　　29
2.4.4　多维数组　　30
2.4.5　命令行参数　　31
2.4.6　增强的for循环　　31
2.5　异常处理　　32
2.5.1　处理异常　　32
2.5.2　finally子句　　33
2.5.3　常见的异常　　33
2.5.4　throw和throws子句　　34
2.6　输入和输出　　35
2.6.1　基本的流操作　　35
2.6.2　Scanner类型　　36
2.6.3　顺序文件　　38
2.7　总结　　40
2.8　核心概念　　40
2.9　常见错误　　41
2.10　网络资源　　42
2.11　练习　　42
2.12　参考文献　　45
第3章　对象和类　　46
3.1　什么是面向对象程序设计　　46
3.2　简单示例　　47
3.3　javadoc　　48
3.4　基本方法　　50
3.4.1　构造方法　　50
3.4.2　设置方法和访问方法　　51
3.4.3　输出和toString　　52
3.4.4　equals　　52
3.4.5　main　　52
3.5　示例：使用java.math.
BigInteger　　52
3.6　其他结构成分　　54
3.6.1　this引用　　54
3.6.2　用于构造方法的this简写　　55
3.6.3　instanceof运算符　　55
3.6.4　实例成员和静态成员　　55
3.6.5　静态域和方法　　55
3.6.6　静态初始化程序　　57
3.7　示例：实现BigRational类　　58
3.8　包　　61
3.8.1　import指令　　61
3.8.2　package语句　　62
3.8.3　CLASSPATH环境变量　　63
3.8.4　包可见性规则　　64
3.9　设计模式：复合　　64
3.10　总结　　65
3.11　核心概念　　66
3.12　常见错误　　67
3.13　网络资源　　67
3.14　练习　　67
3.15　参考文献　　71
第4章　继承　　72
4.1　什么是继承　　72
4.1.1　创建新的类　　72
4.1.2　类型兼容性　　76
4.1.3　动态调度和多态　　76
4.1.4　继承层次结构　　77
4.1.5　可见性规则　　77
4.1.6　构造方法和super　　78
4.1.7　final方法和类　　79
4.1.8　覆盖一个方法　　80
4.1.9　再次讨论类型兼容性　　81
4.1.10　数组类型的兼容性　　82
4.1.11　协变返回类型　　82
4.2　设计层次结构　　83
4.2.1　抽象方法和类　　85
4.2.2　为未来而设计　　86
4.3　多继承　　87
4.4　接口　　88
4.4.1　规范接口　　89
4.4.2　实现一个接口　　89
4.4.3　多接口　　90
4.4.4　接口是抽象类　　90
4.5　Java中的基本继承　　90
4.5.1　Object类　　90
4.5.2　异常的层次结构　　90
4.5.3　I/O：装饰器模式　　92
4.6　使用继承实现泛型组件　　94
4.6.1　Object用于泛型　　94
4.6.2　基本类型的包装类　　96
4.6.3　装箱/拆箱　　97
4.6.4　适配器：改变接口　　97
4.6.5　为泛型使用接口类型　　98