数据结构与算法分析:Java语言描述(原书第3版)
基本信息
- 原书名: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程序的开发有机结合起来,深入分析每种算法,并细致讲解精心构造程序的方法,内容全面,缜密严格。
内容简介
作译者
目录
前言
第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类的一个重要子集的若干实现。