查字典图书网
查字典图书网
内容简介：
本书全面讲述算法和数据结构的必备知识，具有以下几大特色。
算法领域的经典参考书
Sedgewick畅销著作的最新版，反映了经过几十年演化而成的算法核心知识体系
内容全面
全面论述排序、搜索、图处理和字符串处理的算法和数据结构，涵盖每位程序员应知应会的50种算法
全新修订的代码
全新的Java实现代码，采用模块化的编程风格，所有代码均可供读者使用
与实际应用相结合
在重要的科学、工程和商业应用环境下探讨算法，给出了算法的实际代码，而非同类著作常用的伪代码
富于智力趣味性
简明扼要的内容，用丰富的视觉元素展示的示例，精心设计的代码，详尽的历史和科学背景知识，各种难度的练习，这一切都将使读者手不释卷
科学的方法
用合适的数学模型精确地讨论算法性能，这些模型是在真实环境中得到验证的
与网络相结合
配套网站algs4.cs.princeton.edu提供了本书内容的摘要及相关的代码、测试数据、编程练习、教学课件等资源
作者简介：
Robert Sedgewick 斯坦福大学博士，导师为Donald E. Knuth，从1985年开始一直担任普林斯顿大学计算机科学系教授，曾任该系主任，也是Adobe Systems公司董事会成员，曾在Xerox PARC、国防分析研究所（Institute for Defense Analyses）和法国国家信息与自动化研究所（INRIA）从事研究工作。他的研究方向包括解析组合学、数据结构和算法的分析与设计、程序可视化等。
Kevin Wayne 康奈尔大学博士，普林斯顿大学计算机科学系高级讲师，研究方向包括算法的设计、分析和实现，特别是图和离散优化。
目录：
目录
第1章 基础1
1.1 基础编程模型4
1.1.1 Java程序的基本结构4
1.1.2 原始数据类型与表达式6
1.1.3 语句8
1.1.4 简便记法9
1.1.5 数组10
1.1.6 静态方法12
1.1.7 API16
1.1.8 字符串20
1.1.9 输入输出21
1.1.10 二分查找28
1.1.11 展望30
1.2 数据抽象38
1.2.1 使用抽象数据类型38
1.2.2 抽象数据类型举例45
1.2.3 抽象数据类型的实现52
1.2.4 更多抽象数据类型的实现55
1.2.5 数据类型的设计60
1.3 背包、队列和栈74
1.3.1 API74
1.3.2 集合类数据类型的实现81
1.3.3 链表89
1.3.4 综述98
1.4 算法分析108
1.4.1 科学方法108
1.4.2 观察108
1.4.3 数学模型112
1.4.4 增长数量级的分类117
1.4.5 设计更快的算法118
1.4.6 倍率实验121
1.4.7 注意事项123
1.4.8 处理对于输入的依赖124
1.4.9 内存126
1.4.10 展望129
1.5 案例研究：union-find算法136
1.5.1 动态连通性136
1.5.2 实现140
1.5.3 展望148
第2章 排序152
2.1 初级排序算法153
2.1.1 游戏规则153
2.1.2 选择排序155
2.1.3 插入排序157
2.1.4 排序算法的可视化159
2.1.5 比较两种排序算法159
2.1.6 希尔排序162
2.2 归并排序170
2.2.1 原地归并的抽象方法170
2.2.2 自顶向下的归并排序171
2.2.3 自底向上的归并排序175
2.2.4 排序算法的复杂度177
2.3 快速排序182
2.3.1 基本算法182
2.3.2 性能特点185
2.3.3 算法改进187
2.4 优先队列195
2.4.1 API195
2.4.2 初级实现197
2.4.3 堆的定义198
2.4.4 堆的算法199
2.4.5 堆排序205
2.5 应用214
2.5.1 将各种数据排序214
2.5.2 我应该使用哪种排序算法218
2.5.3 问题的归约219
2.5.4 排序应用一览221
第3章 查找227
3.1 符号表228
3.1.1 API228
3.1.2 有序符号表230
3.1.3 用例举例233
3.1.4 无序链表中的顺序查找235
3.1.5 有序数组中的二分查找238
3.1.6 对二分查找的分析242
3.1.7 预览244
3.2 二叉查找树250
3.2.1 基本实现250
3.2.2 分析255
3.2.3 有序性相关的方法与删除操作257
3.3 平衡查找树269
3.3.1 2-3查找树269
3.3.2 红黑二叉查找树275
3.3.3 实现280
3.3.4 删除操作282
3.3.5 红黑树的性质284
3.4 散列表293
3.4.1 散列函数293
3.4.2 基于拉链法的散列表297
3.4.3 基于线性探测法的散列表300
3.4.4 调整数组大小304
3.4.5 内存使用306
3.5 应用312
3.5.1 我应该使用符号表的哪种实现312
3.5.2 集合的API313
3.5.3 字典类用例315
3.5.4 索引类用例318
3.5.5 稀疏向量322
第4章 图329
4.1 无向图331
4.1.1 术语表331
4.1.2 表示无向图的数据类型333
4.1.3 深度优先搜索338
4.1.4 寻找路径342
4.1.5 广度优先搜索344
4.1.6 连通分量349
4.1.7 符号图352
4.1.8 总结358
4.2 有向图364
4.2.1 术语364
4.2.2 有向图的数据类型365
4.2.3 有向图中的可达性367
4.2.4 环和有向无环图369
4.2.5 有向图中的强连通性378
4.2.6 总结385
4.3 最小生成树390
4.3.1 原理391
4.3.2 加权无向图的数据类型393
4.3.3 最小生成树的API和测试用例396
4.3.4 Prim算法398
4.3.5 Prim算法的即时实现401
4.3.6 Kruskal算法404
4.3.7 展望407
4.4 最短路径412
4.4.1 最短路径的性质413
4.4.2 加权有向图的数据结构414
4.4.3 最短路径算法的理论基础420
4.4.4 Dijkstra算法421
4.4.5 无环加权有向图中的最短路径算法425
4.4.6 一般加权有向图中的最短路径问题433
4.4.7 展望445
第5章 字符串451
5.1 字符串排序455
5.1.1 键索引计数法455
5.1.2 低位优先的字符串排序458
5.1.3 高位优先的字符串排序461
5.1.4 三向字符串快速排序467
5.1.5 字符串排序算法的选择470
5.2 单词查找树474
5.2.1 单词查找树475
5.2.2 单词查找树的性质483
5.2.3 三向单词查找树485
5.2.4 三向单词查找树的性质487
5.2.5 应该使用字符串符号表的哪种实现489
5.3 子字符串查找493
5.3.1 历史简介493
5.3.2 暴力子字符串查找算法494
5.3.3 Knuth-Morris-Pratt子字符串查找算法496
5.3.4 Boyer-Moore字符串查找算法502
5.3.5 Rabin-Karp指纹字符串查找算法505
5.3.6 总结509
5.4 正则表达式514
5.4.1 使用正则表达式描述模式514
5.4.2 缩略写法516
5.4.3 正则表达式的实际应用517
5.4.4 非确定有限状态自动机518
5.4.5 模拟NFA的运行520
5.4.6 构造与正则表达式对应的
5.5 数据压缩529
5.5.1 游戏规则529
5.5.2 读写二进制数据530
5.5.3 局限533
5.5.4 热身运动：基因组534
5.5.5 游程编码537
5.5.6 霍夫曼压缩540
第6章 背景558
索引611
文章试读：...
(查看全部试读)