算法 第四版 Algorithms (4th Edition)(Chinese Edition) ((美)Robert Sedgewick，(美)Kevin Wayne著 谢路云译) (Z-Library)

Page 1

(This page has no text content)

Page 2

(This page has no text content)

Page 3

图灵社区的电子书没有采用专有客 户端，您可以在任意设备上，用自 己喜欢的浏览器和PDF阅读器进行 阅读。 但您购买的电子书仅供您个人使用， 未经授权，不得进行传播。 我们愿意相信读者具有这样的良知 和觉悟，与我们共同保护知识产权。 如果购买者有侵权行为，我们可能 对该用户实施包括但不限于关闭该 帐号等维权措施，并可能追究法律 责任。

Page 4

表 1.2.14 一种能够累加数据的抽象数据类型（可视版本） API public class VisualAccumulator VisualAccumulator(int trials, double max) void addDataValue(double val) 添加一个新的数据值 double mean() 所有数据的平均值 String toString() 对象的字符串表示 public class TestVisualAccumulator { public static void main(String[] args) { int T = Integer.parseInt(args[0]); VisualAccumulator a = new VisualAccumulator(T, 1.0); for (int t = 0; t < T; t++) a.addDataValue(StdRandom.random()); StdOut.println(a); } } public class VisualAccumulator { private double total; private int N; public VisualAccumulator(int trials, double max) { StdDraw.setXscale(0, trials); StdDraw.setYscale(0, max); StdDraw.setPenRadius(.005); } public void addDataValue(double val) { N++; total += val; StdDraw.setPenColor(StdDraw.DARK_GRAY); StdDraw.point(N, val); StdDraw.setPenColor(StdDraw.RED); StdDraw.point(N, total/N); } public double mean() public String toString() // 和 Accumulator 相同 } 典型的用例 数据类型的实现

Page 5

一个装有 弹子球的 背包 处理任意弹子球 m（任意顺序） add( ) for (Marble m : bag) add( ) 图 1.3.1 背包的操作 灰点的高度 即数据点的值 左起第N个红点的高度为最 靠左的N个灰点的平均高度 　 % java TestVisualAccumulator 2000 Mean (2000 values): 0.509789 图 1.2.8 可视化累加器图像 0 0 128 256 成 本 （ 数 组 引 用 ） add()操作的数量 每个灰点表 示一次操作 红点表示的是累计平均 5 128 64 图 1.4.7　向一个 RandomBag对象中添加元素时的 均摊成本

Page 6

0 1 2 3 4 5 6 7 8 9 4 3 3 8 6 5 9 4 2 1 8 9 5 0 7 2 6 1 1 0 6 7 2个连通分量 不用打印 出已知相 连的整数对 图 1.5.1 动态连通性问题 黑色的元素 参与了比较 灰色的元素 没有被移动 插入排序 选择排序 图 2.1.1 初级排序算法的可视轨迹图 quick-union算法 加权quick-union算法 0 0 900 1300 458 访 问 数 组 的 次 数 连接总数 0 100 0 20 每个灰点都表 示用例处理过 的一条连接 每个红点都表 示一个累计平均 union()操作至 少访问数组625次 connected()操作 只会访问数组2次 find()操作变 得越来越昂贵 没有任何昂贵的操作 20 8 quick-find算法 图 1.5.10 所有操作的总成本

Page 7

切分元素 输入 结果 第一次切 分的结果 左子数组 部分有序 两个子数组 都已部分有序 图 2.3.3 使用了三取样切分和插入排序转换的快速排序 和切分元素相等的元素 图 2.3.5 三向切分的快速排序的可视轨迹

Page 8

输入 排序 结果 堆有序 红色的条目 是下沉的元素 灰色的元 素不会移动 黑色的元素 正在进行交换 图 2.4.8 堆排序的可视轨迹 中位数 lo i hi 图 2.5.2 用切分找出中位数 红色为新 加入的结点 黑色是在查找 中被遍历的结点 首结点 S 0 S 0E 1 S 0E 1A 2 S 0E 1A 2R 3 S 0E 1A 2R 3C 4 S 0E 1A 2R 3C 4H 5 S 0E 6A 2R 3C 4H 5 S 0E 6A 2R 3C 4H 5 S 0E 6A 8R 3C 4H 5 X 7 X 7 M 9 P 10 L 11 L 11 圈中是被 修改过的值 灰色结点没 有被访问过 S 0E 6A 8R 3C 4H 5X 7 M 9 S 0E 6A 8R 3C 4H 5X 7 P 10 M 9 S 0E 6A 8R 3C 4H 5X 7 P 10 M 9 S 0E 12A 8R 3C 4H 5X 7 键 值 S 0 E 1 A 2 R 3 C 4 H 5 E 6 X 7 A 8 M 9 P 10 L 11 E 12 图 3.1.2　使用基于链表的符号表的索引用例的轨迹

Page 9

1.39 lgN −1.85 20 0 10 000节点数量N 平 均 路 径 长 度 16 100 图 3.2.14　一棵随机构造的二叉查找树中由根到达任意结点的平均路径长度 图 3.3.13　将红链接画平时，一棵红黑树就是一棵 2-3 树 ... ... ... ... ... ... a b3-结点 a b 介于a 和b之间 介于a 和b之间 小于a 小于a 大于b 大于b 图 3.3.12　由一条红色左链接相连的两个 2- 结点表示一个 3- 结点

Page 10

X SH P J R E A M C L XSH P J RE A M C L 红黑树 将红链接画平 2-3树 E J H L M R P S XA C private static final boolean RED = true; private static final boolean BLACK = false; private class Node { Key key; // 键 Value val; // 相关联的值 Node left, right; // 左右子树 int N; // 这棵子树中的结点总数 boolean color; // 由其父结点指向它的链接的颜色 Node(Key key, Value val, int N, boolean color) { this.key = key; this.val = val; this.N = N; this.color = color; } } private boolean isRed(Node x) { if (x == null) return false; return x.color == RED; } J G E A D C hh.left.color 的值是RED h.right.color 的值是BLACK 图 3.3.14　红黑树和 2-3 树的一一对应关系 图 3.3.15　红黑树的结点表示 Node rotateLeft(Node h) { Node x = h.right; h.right = x.left; x.left = h; x.color = h.color; h.color = RED; x.N = h.N; h.N = 1 + size(h.left) + size(h.right); return x; } h x x h E S E S 介于E 和S之间 可能是左链接也可能是 右链接，颜色可红可黑 小于E 大于S 介于E 和S之间小于E 大于S Node rotateRight(Node h) { Node x = h.left; h.left = x.right; x.right = h; x.color = h.color; h.color = RED; x.N = h.N; h.N = 1 + size(h.left) + size(h.right); return x; } x h h x E S 介于E 和S之间小于E 大于S E S 介于E 和S之间 小于E 大于S 图 3.3.16　左旋转 h的右链接 图 3.3.17　右旋转 h的左链接

Page 11

指向含有a的 新结点的红链 接将这个2-结点 变为一个3-结点 查找结束 于该空链接 查找结束 于该空链接 用红链接和 新结点相连 左旋转得到一 个正常的3-结点 a b a a b b a b 根结点 根结点 根结点 根结点 向左插入 向右插入 E A E R S R S A C E R S C A 在此处插 入新结点 出现红色右链接， 进行左旋转 插入C 图 3.3.18　向单个 2- 结点中插入一个新键 图 3.3.19　向树底部的 2- 结点插入一个新键 a c b 旋转后变为红色左链接 旋转后变为 红色右链接 旋转后变为 红色右链接 查找结束 于该空链接 查找结束 于该空链接 查找结束 于该空链接 用红链接和 新结点相连 用红链接和 新结点相连 用红链接和 新结点相连 将链接颜 色变为黑 将链接颜 色变为黑 将链接颜 色变为黑 a c b b c a b c a b c a b c a b c a c a c b 新键最小 新键介于两者之间 a b a b c a b c 新键最大 图 3.3.20　向一棵双键树（即一个 3- 结点）中插入一个新键的三种情况

Page 12

void flipColors(Node h) { h.color = RED; h.left.color = BLACK; h.right.color = BLACK; } h A E 介于A 和E之间小于A S 可能是左链接， 也可能是右链接 用红链接将中间 结点和父结点相连 黑色链接分 别指向两个 2-结点 大于S A E S 介于E 和S之间 介于A 和E之间小于A 大于S 介于E 和S之间 图 3.3.21　通过转换链接的颜色来分解 4- 结点 H E R S A C S S R E H 在此插 入新结点 E R S A C 出现红色右链 接，需要左旋转 出现两条连续的左 链接，需要右旋转 E H R A C 拥有两个红色子链接， 需要进行颜色转换 S E H R A C A C 插入H E R SA C E H R SA C SH E R A C 图 3.3.22　向树底部的 3- 结点插入一个新键 颜色转换 右旋转 左旋转 h h h 图 3.3.23　红黑树中红链接向上传递

Page 13

S E A S E A PA H C M E L A H C M E L E A R C H X M P L C S A E H L M P R S X E R S L M P R S X A H C E R S C A E H A C E S A C A E A C S X M R E A H C S X R E A C H P R S X M E A C H P R SH X M E A C L S R E A C H L H C A E S R M L P A H C E R M L P H C A E 标准索引测试用例 用同一组键按照升序插入来构造一棵红黑树 插入 插入 图 3.3.24　红黑树的构造轨迹 图 3.3.27　使用随机键构造的典型红黑树，没有画出空链接

Page 14

图 3.3.28　使用升序键列构造的一棵红黑树，没有画出空链接 lgN − 0.5 20 0 10 000 操作 成 本 13 100 图 3.3.30　随机构造的红黑树中到达一个随机结点的平均路径长度 0 96 频 率 键值 110 10679/97 图 3.4.2　《双城记》中每个单词的散列值的出现频率（10 679 个键，即单词，M=97） 125 0 0 10 20 30 α =10.711... αke-α k ! 链表的长度（10 679个键， M = 997） 频 率 图 3.4.4　 使用 SeparateChainingHashST，运行 java FrequencyCounter 8 < tale.txt时所有链表 的长度

Page 15

0 1 2 3 4 5 6 7 8 9 S 0 S E 0 1 A S E 2 0 1 A S E R 2 0 1 3 A C S E R 2 4 0 1 3 A C S H E R 2 4 0 5 1 3 A C S H E R 2 4 0 5 6 3 A C S H E R X 2 4 0 5 6 3 7 A C S H E R X 8 4 0 5 6 3 7 M A C S H E R X 9 8 4 0 5 6 3 7 P M A C S H E R X 9 8 4 0 5 6 3 7 P M A C S H L E R X 9 8 4 0 5 6 3 7 P M A C S H L E R X 9 8 4 0 5 3 7 10 11 12 13 14 15 11 12 1110 10 10 灰色的键 未被访问 探测序列 折回到0 红色的是 新插入的键 黑色的 是探针键 S 6 0 E 10 1 A 4 2 R 14 3 C 5 4 H 4 5 E 10 6 X 15 7 A 4 8 M 1 9 P 14 10 L 6 11 E 10 12 keys[] vals[] 键散列值 值 图 3.4.6　标准索引用例使用的基于线性探测的符号表的轨迹 13 13 0 5 4 3 0 1 9 12 6 4 5 4 0 2 11 12 9 10 0 6 7 8 9 11 5 3 % java Graph tinyG.txt 13 vertices, 13 edges 0: 6 2 1 5 1: 0 2: 0 3: 5 4 4: 5 6 3 5: 3 4 0 6: 0 4 7: 8 8: 7 9: 11 10 12 10: 9 11: 9 12 12: 11 9 tinyG.txt V E 输入的第一个 相邻顶点在链表 中排在最后 每条边在第 二次出现时 都被标记为红色 图 4.1.10 由边得到的邻接表 图 4.1.12 Tremaux 搜索 0 3 4 7 10 11 图 4.1.7 二分图

Page 16

marked[] 0 T 1 2 3 4 5 0 T 1 2 T 3 4 5 0 T 1 T 2 T 3 4 5 0 T 1 T 2 T 3 T 4 5 0 T 1 T 2 T 3 T 4 5 T 0 T 1 T 2 T 3 T 4 T 5 T dfs(0) dfs(2) 检查 0 dfs(1) 检查 0 检查 2 1 完成 dfs(3) dfs(5) 检查 3 检查 0 5 完成 dfs(4) 检查 3 检查 2 4 完成 检查 2 3 完成 检查 4 2 完成 检查 1 检查 5 0 完成 0 2 1 5 1 0 2 2 0 1 3 4 3 5 4 2 4 3 2 5 3 0 0 2 1 5 1 0 2 2 0 1 3 4 3 5 4 2 4 3 2 5 3 0 0 2 1 5 1 0 2 2 0 1 3 4 3 5 4 2 4 3 2 5 3 0 0 2 1 5 1 0 2 2 0 1 3 4 3 5 4 2 4 3 2 5 3 0 0 2 1 5 1 0 2 2 0 1 3 4 3 5 4 2 4 3 2 5 3 0 adj[] 0 2 1 5 1 0 2 2 0 1 3 4 3 5 4 2 4 3 2 5 3 0 图 4.1.14　 使用深度优先搜索的轨迹，寻找所有和顶点 0 连通的顶点 edgeTo[] 0 1 2 3 4 5 0 1 2 0 3 4 5 0 1 2 2 0 3 4 5 0 1 2 2 0 3 2 4 5 0 1 2 2 0 3 2 4 5 3 0 1 2 2 0 3 2 4 3 5 3 dfs(0) dfs(2) 检查 0 dfs(1) 检查 0 检查 2 1 完成 dfs(3) dfs(5) 检查 3 检查 0 5 完成 dfs(4) 检查 3 检查 2 4 完成 检查 2 3 完成 检查 4 2 完成 检查 1 检查 5 0 完成 0 1 2 2 0 3 2 4 3 5 3 图 4.1.15　 使用深度优先搜索的轨迹，寻找所有 起点为 0 的路径

Page 17

marked[] 0 T 1 2 3 4 5 0 T 1 T 2 T 3 4 5 T 0 T 1 T 2 T 3 T 4 T 5 T 0 1 5 3 4 2 1 5 5 3 4 3 4 4 edgeTo[] 0 1 2 3 4 5 0 1 0 2 0 3 4 5 0 0 1 0 2 0 3 2 4 2 5 0 0 2 1 5 1 0 2 2 0 1 3 4 3 5 4 2 4 3 2 5 3 0 0 2 1 5 1 0 2 2 0 1 3 4 3 5 4 2 4 3 2 5 3 0 0 T 1 T 2 T 3 T 4 T 5 T 0 1 0 2 0 3 2 4 2 5 0 0 2 1 5 1 0 2 2 0 1 3 4 3 5 4 2 4 3 2 5 3 0 adj[] 0 2 1 5 1 0 2 2 0 1 3 4 3 5 4 2 4 3 2 5 3 0 0 T 1 T 2 T 3 T 4 T 5 T 0 1 0 2 0 3 2 4 2 5 0 0 2 1 5 1 0 2 2 0 1 3 4 3 5 4 2 4 3 2 5 3 0 0 T 1 T 2 T 3 T 4 T 5 T 0 1 0 2 0 3 2 4 2 5 0 0 2 1 5 1 0 2 2 0 1 3 4 3 5 4 2 4 3 2 5 3 0 queue 图 4.1.18　 使用广度优先搜索的轨迹，寻找所有起点为 0的路径 0 1 2 3 4 5 6 7 8 9 10 11 12 0 T T T T T T 1 T 2 T T T T T T 3 T T T T T T 4 T T T T T T 5 T T T T T T 6 T T T T T T T T T T T 7 T T T T T T T T T T T T T 8 T T T T T T T T T T T T T 9 T T T T T T T T T T 10 T T T T T T T T T T 11 T T T T T T T T T T 12 T T T T T T T T T T 自环（灰色） 顶点12是从 顶点6可达的 原始有向图 中的边（红色） 图 4.2.18 传递闭包 最小生成树中的边 切分生成的权 重最小的边 图 4.3.6 贪心最小生成树算法 权重最小的横切边肯 定属于最小生成树 将灰色和白色顶点区别 开来的横切边为红色 e f 图 4.3.4 切分定理

Page 18

将要添加到最 小生成树中的 权重最小的横 切边 树中的边 （黑色加粗） 横切边 （红色） 失效的边 （灰色） 图 4.3.9 最小生成树的 Prim 算法 3-6 0.52 6-0 0.58 6-4 0.93 * 0-7 0.16 * 0-2 0.26 * 0-4 0.38 * 6-0 0.58 * 1-7 0.19 0-2 0.26 * 5-7 0.28 * 2-7 0.34 * 4-7 0.37 0-4 0.38 6-0 0.58 0-2 0.26 5-7 0.28 * 1-3 0.29 * 1-5 0.32 2-7 0.34 * 1-2 0.36 4-7 0.37 0-4 0.38 6-0 0.58 * 2-3 0.17 5-7 0.28 1-3 0.29 1-5 0.32 2-7 0.34 1-2 0.36 4-7 0.37 0-4 0.38 * 6-2 0.40 6-0 0.58 5-7 0.28 1-3 0.29 1-5 0.32 2-7 0.34 1-2 0.36 4-7 0.37 0-4 0.38 6-2 0.40 * 3-6 0.52 6-0 0.58 1-3 0.29 1-5 0.32 2-7 0.34 * 4-5 0.35 1-2 0.36 4-7 0.37 0-4 0.38 6-2 0.40 3-6 0.52 6-0 0.58 1-2 0.36 4-7 0.37 0-4 0.38 6-2 0.40 3-6 0.52 6-0 0.58 * 6-4 0.93 失效的边 （灰色） 所有横切边 （按照权重排序） * 表示新 加入的边 图 4.3.10 Prim 算法的轨迹

Page 19

红色：优先队 列（pq）中的边 红色加粗：优先 队列（pq）中的最 小边，即将被加 入最小生成树 黑色：最小 生成树中的边 灰色：非最小 生成树中的边 0 1 2 0-2 0.26 3 4 0-4 0.38 5 6 6-0 0.58 7 0-7 0.16 0 1 1-7 0.19 2 0-2 0.26 3 4 4-7 0.37 5 5-7 0.28 6 6-0 0.58 7 0-7 0.16 0 1 1-7 0.19 2 0-2 0.26 3 1-3 0.29 4 4-7 0.37 5 5-7 0.28 6 6-0 0.58 7 0-7 0.16 0 1 1-7 0.19 2 0-2 0.26 3 2-3 0.17 4 4-7 0.37 5 5-7 0.28 6 6-2 0.40 7 0-7 0.16 0 1 1-7 0.19 2 0-2 0.26 3 2-3 0.17 4 4-7 0.37 5 5-7 0.28 6 6-2 0.40 7 0-7 0.16 0 1 1-7 0.19 2 0-2 0.26 3 2-3 0.17 4 4-5 0.35 5 5-7 0.28 6 6-2 0.40 7 0-7 0.16 0 1 1-7 0.19 2 0-2 0.26 3 2-3 0.17 4 4-5 0.35 5 5-7 0.28 6 6-2 0.40 7 0-7 0.16 0 1 1-7 0.19 2 0-2 0.26 3 2-3 0.17 4 4-5 0.35 5 5-7 0.28 6 6-2 0.40 7 0-7 0.16 edgeTo[] distTo[] 4.3.12  Prim 算法的轨迹图

Page 20

0-7 0.16 2-3 0.17 1-7 0.19 0-2 0.26 5-7 0.28 1-3 0.29 1-5 0.32 2-7 0.34 4-5 0.35 1-2 0.36 4-7 0.37 0-4 0.38 6-2 0.40 3-6 0.52 6-0 0.58 6-4 0.93 无用的 边（灰色） 灰色的顶点是由和所 有红色边的顶点相邻 的顶点所构成的一个切分 下一条将要被加入最 小生成树中的边为红色 最小生成树 的边（黑色） 按权重排 序的所有边 图 4.3.14 Kruskal 算法的轨迹 0 6->0 1 null 2 6->2 3 1->3 4 6->4 5 7->5 6 3->6 7 2->7 0 6->0 1 5->1 2 null 3 7->3 4 5->4 5 7->5 6 3->6 7 2->7 0 null 1 5->1 2 0->2 3 7->3 4 0->4 5 4->5 6 3->6 7 2->7 0 6->0 1 5->1 2 6->2 3 null 4 6->4 5 7->5 6 3->6 7 2->7 0 6->0 1 5->1 2 6->2 3 7->3 4 null 5 4->5 6 3->6 7 4->70 6->1 1 5->1 2 6->2 3 1->3 4 5->4 5 null 6 3->6 7 5->7 0 6->0 1 5->1 2 6->2 3 7->3 4 6->4 5 7->5 6 null 7 2->70 6->0 1 5->1 2 6->2 3 7->3 4 5->4 5 7->5 6 3->6 7 null 父链接数组 起点 0 1 2 3 4 5 6 7 图 4.4.2 最短路径树