算法.pdf

算法.pdf
 

书籍描述

编辑推荐
《算法(第4版)》适合用做大学教材或从业者的参考书。《算法(第4版)》全新修订的代码:全新的Java实现代码,采用模块化的编程风格,所有代码均可供读者使用。《算法(第4版)》与实际应用相结合:在重要的科学、工程和商业应用环境下探讨算法,给出了算法的实际代码,而非同类著作常用的伪代码。富于智力趣味性:简明扼要的内容,用丰富的视觉元素展示的示例,精心设计的代码,详尽的历史和科学背景知识,各种难度的练习,这一切将使读者手不释卷。

作者简介
作者:(美国)塞奇威克(Robert Sedgewick)(美国)韦恩(Kevin Wayne)译者:谢路云

塞奇威克(Robert Sedgewick),斯坦福大学博士,导师为Donald E.Knuth,从1985年开始一直担任普林斯顿大学计算机科学系教授,曾任该系主任,也是Adobe Systems公司董事会成员,曾在Xerox PARC、国防分析研究所(institute for Defense Analyses)和法国国家信息与自动化研究所(INRIA)从事研究工作。他的研究方向包括解析组合学、数据结构和算法的分析与设计、程序可视化等。
韦恩(Kevin Wayne),康奈尔大学博士,普林斯顿大学计算机科学系高级讲师,研究方向包括算法的设计、分析和实现,特别是图和离散优化。

目录
第1章 基础
1.1 基础编程模型
1.1.1 Java程序的基本结构
1.1.2 原始数据类型与表达式
1.1.3 语句
1.1.4 简便记法
1.1.5 数组
1.1.6 静态方法
1.1.7 API
1.1.8 字符串
1.1.9 输入输出
1.1.10 二分查找
1.1.11 展望
1.2 数据抽象
1.2.1 使用抽象数据类型
1.2.2 抽象数据类型举例
1.2.3 抽象数据类型的实现
1.2.4 更多抽象数据类型的实现
1.2.5 数据类型的设计
1.3 背包、队列和栈
1.3.1 API
1.3.2 集合类数据类型的实现
1.3.3 链表
1.3.4 综述
1.4 算法分析
1.4.1 科学方法
1.4.2 观察
1.4.3 数学模型
1.4.4 增长数量级的分类
1.4.5 设计更快的算法
1.4.6 倍率实验
1.4.7 注意事项
1.4.8 处理对于输入的依赖
1.4.9 内存
1.4.10 展望
1.5 案例研究:union—find算法
1.5.1 动态连通性
1.5.2 实现
1.5.3 展望
第2章 排序
2.1 初级排序算法
2.1.1 游戏规则
2.1.2 选择排序
2.1.3 插入排序
2.1.4 排序算法的可视化
2.1.5 比较两种排序算法
2.1.6 希尔排序
2.2 归并排序
2.2.1 原地归并的抽象方法
2.2.2 自顶向下的归并排序
2.2.3 自底向上的归并排序
2.2.4 排序算法的复杂度
2.3 快速排序
2.3.1 基本算法
2.3.2 性能特点
2.3.3 算法改进
2.4 优先队列
2.4.1 API
2.4.2 初级实现
2.4.3 堆的定义
2.4.4 堆的算法
2.4.5 堆排序
2.5 应用
2.5.1 将各种数据排序
2.5.2 我应该使用哪种排序算法
2.5.3 问题的归约
2.5.4 排序应用一览
第3章 查找
3.1 符号表
3.1.1 API
3.1.2 有序符号表
3.1.3 用例举例
3.1.4 无序链表中的顺序查找
3.1.5 有序数组中的二分查找
3.1.6 对二分查找的分析
3.1.7 预览
3.2 二叉查找树
3.2.1 基本实现
3.2.2 分析
3.2.3 有序性相关的方法与删除操作
3.3 平衡查找树
3.3.12—3查找树
3.3.2 红黑二叉查找树
3.3.3 实现
3.3.4 删除操作
3.3.5 红黑树的性质
3.4 散列表
3.4.1 散列函数
3.4.2 基于拉链法的散列表
3.4.3 基于线性探测法的散列表
3.4.4 调整数组大小
3.4.5 内存使用
3.5 应用
3.5.1 我应该使用符号表的哪种实现
3.5.2 集合的API
3.5.3 字典类用例
3.5.4 索引类用例
3.5.5 稀疏向量
第4章 图
4.1 无向图
4.1.1 术语表
4.1.2 表示无向图的数据类型
4.1.3 深度优先搜索
4.1.4 寻找路径
4.1.5 广度优先搜索
4.1.6 连通分量
4.1.7 符号图
4.1.8 总结
4.2 有向图
4.2.1 术语
4.2.2 有向图的数据类型
4.2.3 有向图中的可达性
4.2.4 环和有向无环图
4.2.5 有向图中的强连通性
4.2.6 总结
4.3 最小生成树
4.3.1 原理
4.3.2 加权无向图的数据类型
4.3.3 最小生成树的API和测试用例
4.3.4 Prim算法
4.3.5 Prim算法的即时实现
4.3.6 Kruskal算法
4.3.7 展望
4.4 最短路径
4.4.1 最短路径的性质
4.4.2 加权有向图的数据结构
4.4.3 最短路径算法的理论基础
4.4.4 Dijkstra算法
4.4.5 无环加权有向图中的最短路径算法
4.4.6 一般加权有向图中的最短路径问题
4.4.7 展望
第5章 字符串
5.1 字符串排序
5.1.1 键索引计数法
5.1.2 低位优先的字符串排序
5.1.3 高位优先的字符串排序
5.1.4 三向字符串快速排序
5.1.5 字符串排序算法的选择
5.2 单词查找树
5.2.1 单词查找树
5.2.2 单词查找树的性质
5.2.3 三向单词查找树
5.2.4 三向单词查找树的性质
5.2.5 应该使用字符串符号表的哪种实现
5.3 子字符串查找
5.3.1 历史简介
5.3.2 暴力子字符串查找算法
5.3.3 Knuth—Morris—Pratt子字符串查找算法
5.3.4 Boyer—Moore字符串查找算法
5.3.5 Rabin—Karp指纹字符串查找算法
5.3.6 总结
5.4 正则表达式
5.4.1 使用正则表达式描述模式
5.4.2 缩略写法
5.4.3 正则表达式的实际应用
5.4.4 非确定有限状态自动机
5.4.5 模拟NFA的运行
5.4.6 构造与正则表达式对应的NFA
5.5 数据压缩
5.5.1 游戏规则
5.5.2 读写二进制数据
5.5.3 局限
5.5.4 热身运动:基因组
5.5.5 游程编码
5.5.6 霍夫曼压缩
第6章 背景
索引

文摘
版权页:

算法

插图:

算法

警告:这段类型转换的用例代码和1.3.2.2节所示的有所不同。你可能会以为需要使用Object而非Stack。在使用泛型时,Java会在编译时检查类型的安全性,但会在运行时抛弃所有这些信息。因此在运行时语句右侧就变成了Stack()或者只剩下了Stack(),因此我们必须将它们转化为Stack ()。
问 在栈为空时调用pop()会发生什么?
答 这取决于实现。对于我们在算法1.2中给出的实现,你会得到一个NullPointerException异常。对于我们在本书的网站上给出的实现,我们会抛出一个运行时异常以帮助用户定位错误。一般来说,在应用广泛的代码中这类检查越多越好。
问 既然有了链表,为什么还要学习如何调整数组的大小?
答 我们还将会学习若干抽象数据类型的示例实现,它们需要使用数组来实现一些链表难以实现的操作。ResizingArrayStack是控制它们的内存使用的样板。
问 为什么将Node声明为嵌套类?为什么使用private?
答 将Node声明为私有的嵌套类之后,我们可以将Node的方法和实例变量的访问范围限制在包含它的类中。私有嵌套类的一个特点是只有包含它的类能够直接访问它的实例变量,因此无需将它的实例变量声明为public或是private。专业背景较强的读者注意:非静态的嵌套类也被称为内部类,因此从技术上来说我们的Node类也是内部类,尽管非泛型的类也可以是静态的。
问 当我输入javac Stack.java运行算法1.2和其他程序时,我发现了Stack.class和Stack$Node.class两个文件。第二个文件是做什么用的?
答 第二个文件是为内部类Node创建的。Java的命名规则会使用$分隔外部类和内部类。
问 Java标准库中有栈和队列吗?
答 有,也没有。Java有一个内置的库,叫做java.util.Stack,但你需要栈的时候请不要使用它。它新增了几个一般不属于栈的方法,例如获取第i个元素。它还允许从栈底添加元素(而非栈顶),所以它可以被当做队列使用!尽管拥有这些额外的操作看起来可能很有用,但它们其实是累赘。我们使用某种数据类型不仅仅是为了获得我们能够想象的各种操作,也是为了准确地指定我们所需要的操作。这么做的主要好处在于系统能够防止我们执行一些意外的操作。java.util.Stack的API是宽接口的一个典型例子,我们通常会极力避免出现这种情况。

内容简介
  《算法(第4版)》是Sedgewick之巨著,与高德纳TAOCP一脉相承,是算法领域经典的参考书,涵盖所有程序员必须掌握的50种算法,全面介绍了关于算法和数据结构的必备知识,并特别针对排序、搜索、图处理和字符串处理进行了论述。第4版具体给出了每位程序员应知应会的50个算法,提供了实际代码,而且这些Java代码实现采用了模块化的编程风格,读者可以方便地加以改造。配套网站提供了《算法(第4版)》内容的摘要及更多的代码实现、测试数据、练习、教学课件等资源。
  《算法(第4版)》适合用做大学教材或从业者的参考书。

搜索


已经是客户了吗?     登录
对本网站的建议
© 1999-2013, Amazon.com, Inc. or its affiliates

购买书籍

当当网购书 京东购书 卓越购书

PDF电子书下载地址

相关书籍

搜索更多