数据结构与算法分析：Java语言描述（原书第3版）
使用本教材的高校
国际著名计算机教育专家Weiss数据结构与算法Java描述经典教材新版，把算法分析与高效率的Java程序的开发有机地结合起来，深入分析每种算法。
基本信息
- 原书名：Data Structures and Algorithm Analysis in Java，Third Edition
- 作者： （美）马克·艾伦·维斯（Mark Allen Weiss）
- 译者： 冯舜玺 陈越
- 丛书名： 计算机科学丛书
- 出版社：机械工业出版社
- ISBN：9787111528395
- 上架时间：2016-2-29
- 出版日期：2016 年3月
- 开本：16开
- 页码：403
- 版次：1-1
- 所属分类：计算机 > 计算机科学理论与基础知识 > 数据结构
教材
机械工业出版社分类专区 > 机工电工电子分社 > 相关图书
【插图】
编辑推荐
本书是国外数据结构与算法分析方面的经典教材，使用卓越的Java编程语言作为实现工具，讨论数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。
随着计算机速度的不断增加和功能的日益强大，人们对有效编程和算法分析的要求也不断增长。本书将算法分析与最有效率的Java程序的开发有机结合起来，深入分析每种算法，并细致讲解精心构造程序的方法，内容全面，缜密严格。
内容简介
作译者
马克·艾伦·维斯(Mark Allen Weiss)佛罗里达国际大学计算与信息科学学院教授、副院长，本科教育主任和研究生教育主任。他于1987年获得普林斯顿大学计算机科学博士学位，师从Bob Sedgewick。他曾经担任全美AP(Advanced Placement)考试计算机学科委员会的主席(2000-2004)。他的主要研究兴趣是数据结构、算法和教育学。
目录
出版者的话
前言
第1章 引论1
1.1 本书讨论的内容1
1.2 数学知识复习2
1.2.1 指数2
1.2.2 对数2
1.2.3 级数2
1.2.4 模运算4
1.2.5 证明的方法4
1.3 递归简论5
1.4 实现泛型构件pre-Java 57
1.4.1 使用Object表示泛型8
1.4.2 基本类型的包装9
1.4.3 使用接口类型表示泛型9
1.4.4 数组类型的兼容性10
1.5 利用Java 5泛型特性实现泛型构件11
1.5.1 简单的泛型类和接口11
1.5.2 自动装箱/拆箱11
1.5.3 菱形运算符12
前言
第1章 引论1
1.1 本书讨论的内容1
1.2 数学知识复习2
1.2.1 指数2
1.2.2 对数2
1.2.3 级数2
1.2.4 模运算4
1.2.5 证明的方法4
1.3 递归简论5
1.4 实现泛型构件pre-Java 57
1.4.1 使用Object表示泛型8
1.4.2 基本类型的包装9
1.4.3 使用接口类型表示泛型9
1.4.4 数组类型的兼容性10
1.5 利用Java 5泛型特性实现泛型构件11
1.5.1 简单的泛型类和接口11
1.5.2 自动装箱/拆箱11
1.5.3 菱形运算符12
前言
本书目标
本书新的Java版论述数据结构——组织大量数据的方法，以及算法分析——算法运行时间的估计。随着计算机的速度越来越快，对于能够处理大量输入数据的程序的需求变得日益迫切。可是，由于在输入量很大的时候程序的低效率变得非常明显，因此这又要求对效率问题给予更仔细的关注。通过在实际编程之前对算法的分析，我们可以确定某个特定的解法是否可行。例如，查阅本书中一些特定的问题，可以看到我们如何通过巧妙的实现，将其处理大量数据的时间限制从几个世纪减至不到1秒。因此，我们在提出所有算法和数据结构时都会阐释其运行时间。在某些情况下，对于影响实现的运行时间的一些微小细节都需要认真探究。
一旦确定了解法，接着就要编写程序。随着计算机功能的日益强大，它们必须解决的问题也变得更加庞大和复杂，这就要求我们开发更加复杂的程序。本书的目的是同时教授学生良好的程序设计技巧和算法分析能力，使得他们能够以最高的效率开发出这种程序。
本书适用于高级数据结构（CS7）课程或是第一年研究生的算法分析课程。学生应该掌握一些中级编程知识，包括基于对象的程序设计和递归等内容，并具备一些离散数学的背景。
第3版中最显著的变化
第3版订正了大量的错误，也修改了很多地方，以使内容更加清晰。此外还有以下修订：
●第4章包括了AVL树的删除算法——这也是读者经常需要的内容。
●第5章进行了大量修改和扩充，现在包含两种新算法：布谷鸟散列（cuckoo hashing）和跳房子散列（hopscotch hashing）。此外还增加了一节讨论通用散列法。
●第7章现在包含了基数排序的内容，并且增加了一节讨论下界的证明。
●第8章用到Seidel和Sharir提出的新的并查集分析，并且证明了O(Mα(M,N))界，而不是前一版中比较弱的O(Mlog*N)界。
●第12章增加了后缀树和后缀数组的内容，包括Karkkainen和Sanders提出的构造后缀数组的线性时间算法（附带实现）。关于确定性跳跃表和AA树的章节被删除。
●通篇代码已做更新，使用了Java 7的菱形运算符。
处理方法
虽然本书的内容大部分都与语言无关，但是，程序设计还是需要使用某种特定的语言。正如书名所示，我们为本书选择了Java。
人们常常将Java和C++比较。Java具有许多优点，程序员常常把Java看成是一种比C++更安全、更具有可移植性并且更容易使用的语言。因此，这使得它成为讨论和实现基础数据结构的一种优秀的核心语言。Java的其他重要的方面，诸如线程和GUI（图形用户界面），虽然很重要，但是本书并不需要，因此也就不再讨论。
完整的Java和C++版数据结构均在互联网上提供。我们采用相似的编码约定以使得这两种语言之间的对等性更加明显。
内容概述
第1章包含离散数学和递归的一些复习材料。我相信熟练掌握递归的唯一办法是反复不断地研读一些好的用法。因此，除第5章外，递归遍及本书每一章的例子之中。第1章还介绍了一些相关内容，作为对Java中“继承”的复习，包括对Java泛型的讨论。
第2章讨论算法分析，阐述渐近分析及其主要缺点，提供了许多例子，包括对对数级运行时间的深入分析。我们通过直观地把递归程序转变成迭代程序，对一些简单递归程序进行了分析。更复杂的分治程序也在此介绍，不过有些分析（求解递推关系）要推迟到第7章再进行详细讨论。
第3章介绍表、栈和队列。包括对Collections API ArrayList类和LinkedList类的讨论，提供了Collections API ArrayList类和LinkedList类的一个重要子集的若干实现。
本书新的Java版论述数据结构——组织大量数据的方法，以及算法分析——算法运行时间的估计。随着计算机的速度越来越快，对于能够处理大量输入数据的程序的需求变得日益迫切。可是，由于在输入量很大的时候程序的低效率变得非常明显，因此这又要求对效率问题给予更仔细的关注。通过在实际编程之前对算法的分析，我们可以确定某个特定的解法是否可行。例如，查阅本书中一些特定的问题，可以看到我们如何通过巧妙的实现，将其处理大量数据的时间限制从几个世纪减至不到1秒。因此，我们在提出所有算法和数据结构时都会阐释其运行时间。在某些情况下，对于影响实现的运行时间的一些微小细节都需要认真探究。
一旦确定了解法，接着就要编写程序。随着计算机功能的日益强大，它们必须解决的问题也变得更加庞大和复杂，这就要求我们开发更加复杂的程序。本书的目的是同时教授学生良好的程序设计技巧和算法分析能力，使得他们能够以最高的效率开发出这种程序。
本书适用于高级数据结构（CS7）课程或是第一年研究生的算法分析课程。学生应该掌握一些中级编程知识，包括基于对象的程序设计和递归等内容，并具备一些离散数学的背景。
第3版中最显著的变化
第3版订正了大量的错误，也修改了很多地方，以使内容更加清晰。此外还有以下修订：
●第4章包括了AVL树的删除算法——这也是读者经常需要的内容。
●第5章进行了大量修改和扩充，现在包含两种新算法：布谷鸟散列（cuckoo hashing）和跳房子散列（hopscotch hashing）。此外还增加了一节讨论通用散列法。
●第7章现在包含了基数排序的内容，并且增加了一节讨论下界的证明。
●第8章用到Seidel和Sharir提出的新的并查集分析，并且证明了O(Mα(M,N))界，而不是前一版中比较弱的O(Mlog*N)界。
●第12章增加了后缀树和后缀数组的内容，包括Karkkainen和Sanders提出的构造后缀数组的线性时间算法（附带实现）。关于确定性跳跃表和AA树的章节被删除。
●通篇代码已做更新，使用了Java 7的菱形运算符。
处理方法
虽然本书的内容大部分都与语言无关，但是，程序设计还是需要使用某种特定的语言。正如书名所示，我们为本书选择了Java。
人们常常将Java和C++比较。Java具有许多优点，程序员常常把Java看成是一种比C++更安全、更具有可移植性并且更容易使用的语言。因此，这使得它成为讨论和实现基础数据结构的一种优秀的核心语言。Java的其他重要的方面，诸如线程和GUI（图形用户界面），虽然很重要，但是本书并不需要，因此也就不再讨论。
完整的Java和C++版数据结构均在互联网上提供。我们采用相似的编码约定以使得这两种语言之间的对等性更加明显。
内容概述
第1章包含离散数学和递归的一些复习材料。我相信熟练掌握递归的唯一办法是反复不断地研读一些好的用法。因此，除第5章外，递归遍及本书每一章的例子之中。第1章还介绍了一些相关内容，作为对Java中“继承”的复习，包括对Java泛型的讨论。
第2章讨论算法分析，阐述渐近分析及其主要缺点，提供了许多例子，包括对对数级运行时间的深入分析。我们通过直观地把递归程序转变成迭代程序，对一些简单递归程序进行了分析。更复杂的分治程序也在此介绍，不过有些分析（求解递推关系）要推迟到第7章再进行详细讨论。
第3章介绍表、栈和队列。包括对Collections API ArrayList类和LinkedList类的讨论，提供了Collections API ArrayList类和LinkedList类的一个重要子集的若干实现。
