3.1.21 # 解答 # BinarySearchST 包含一个键数组和一个值数组，以及一个 int 变量。 数组长度变化范围为 N~4N ，故总大小： 从 2 × (24 + 8N) +4 = 52 + 16N 字节 （100 %）， 到 2 × (24 + 32N) +4 = 52 + 64N 字节（25 %）之间变动。 SequentialSearchST 包含 N 个结点以及一个 int 变量 (16 + 8 + 8 + 8)N + 4 = 4 + 40N 字节
3.1.22 # 解答 # 对 Get() 做修改，得到 MoveToFrontArrayST。 public TValue Get(TKey key) { int i; for (i = 0; i < _n; i++) if (_keys[i].Equals(key)) break; if (i == _n) return default; var toFrontKey = _keys[i]; var toFrontValue = _values[i]; for (var j = i; j > 0; j--) _keys[j] = _keys[j - 1]; for (var j = i; j > 0; j--) _values[j] = _values[j - 1]; _keys[0] = toFrontKey; _values[0] = toFrontValue; return _values[0]; } 另请参阅 # SymbolTable 库
3.1.23 # 解答 # 这里的右移操作可以理解为 「小数点前移一位」 即数字依次向右退一位，个位上的数字被舍弃。 对于十进制，小数点前移一位会使 $n$ 变为 $\lfloor n / 10 \rfloor$。 同样对于二进制就会使 $n$ 变为 $\lfloor n / 2 \rfloor$。 当需要除以 $2$ 的 $k$ 次幂的时候，可以用右移 $k$ 位代替并减少时间开销。 同理可以用左移 $k$ 位来代替乘以 $2$ 的 $k$ 次幂。 注： 这样会降低程序可读性， 并且某些语言（C / C++）的编译器已经可以自动执行这项优化了。 请充分考虑你的代码受众之后再决定是否采用这种写法。 二分查找的最大查找次数 = $ \lg N + 1$ （见 3.1.20 的证明 {% post_link 3-1-20 %}） 一个数最多被左移的次数也正好等于 $\lfloor \lg N \rfloor + 1$ （任意正整数都能被表示为 $2 ^ k + m$ 的形式，即 $k +1$ 位二进制数） ...
3.1.24 # 解答 # FrequencyCounter 的官方实现：https://algs4.cs.princeton.edu/31elementary/FrequencyCounter.java.html 二分查找总是与中间值进行比较，现在改为与数组中第 x% 位置上的元素比较。 具体而言，$\frac{k_x-k_{lo}}{k_{hi}-k_{lo}}$ 代表数组在均匀情况下目标值 $k_x$ 的相对位置（一个比率，在数组第 x% 的位置上）。 那么相对应的下标就等于 $lo+\frac{k_x-k_{lo}}{k_{hi}-k_{lo}} \times (hi - lo)$。 用这个式子代替原来的 $mid=lo + (hi-lo)/2$ 即可。 不难看出这种方法对于分布相对均匀的数组比较有利，相对于二分查找而言迭代次数会少很多。 但如果数组分布不够均匀，也可能表现出不如二分查找的性能。 实验结果也证实了这一判断，就随机数组而言，插值查找相对于二分查找只有 1% 左右的性能提升。 代码 # SearchCompare 在书中没有出现，但可以简单的实现为调用 FrequencyCounter 并计时的方法： public static long Time<TKey>(IST<TKey, int> st, TKey[] keys) { Stopwatch sw = new Stopwatch(); sw.Start(); FrequencyCounter.MostFrequentlyKey(st, keys); sw.Stop(); return sw.ElapsedMilliseconds; } 由于这里需要使用数字而非字符串作为键值，需要对官方给出的 FrequencyCounter 做一些修改： public static TKey MostFrequentlyKey<TKey> (IST<TKey, int> st, TKey[] keys) { foreach (TKey s in keys) { if (st. ...
3.1.25 # 解答 # 英文原文指的是 most recently accessed key，因此指的是最近访问的键。 实现比较简单，先在类中定义一个新的成员 cache 作为缓存， 然后修改 Get 方法，在实际查找之前先检查缓存，如果缓存未命中则在查找之后更新它。 要注意的是缓存指向内容的有效性，在数组中指的是下标是否有效，在链表中指的是结点是否为空。 利用《双城记》测试的结果： 代码 # BinarySearchST # cache 是一个 int 类型的变量，代表下标。 在二分查找前先检查缓存，要注意cache超出数组大小的情况。 如果缓存未命中，则进行二分查找，并在返回结果前更新缓存。 public TValue Get(TKey key) { if (key == null) throw new ArgumentNullException(nameof(key), "argument to Get() is null"); if (IsEmpty()) return default; if (_cache < _n && _keys[_cache].Equals(key)) // 缓存检查 return _values[_cache]; var rank = Rank(key); if (rank < _n && _keys[rank].Equals(key)) { _cache = rank; // 更新缓存 return _values[rank]; } return default; } SequentialSearchST # cache 是一个结点类型的变量，代表一个键值对。 类似的，在顺序查找前先检查缓存，如果缓存未命中则更新缓存。 要注意的是如果缓存的结点被删除，需要将缓存置为 null。 ...
3.1.26 # 解答 # 字典文件：https://introcs.cs.princeton.edu/java/data/web2.txt 《双城记》：https://introcs.cs.princeton.edu/java/data/tale.txt 浏览器可能会直接打开 txt，此时右键链接-目标另存为即可下载。 FrequencyCounter 的官方实现：https://algs4.cs.princeton.edu/31elementary/FrequencyCounter.java.html 我们利用 BinarySearchST 会自动对键排序的性质来实现字典序排序。 首先将字典存到一个符号表中，按照 “单词-序号” 的形式保存。 然后读入文件，如果读入的单词存在于字典中， 则将其以 “序号-单词” 的形式存到 BinarySearchST 中去。 读入完毕后，遍历 BinarySearchST 即可获得字典序的单词列表。 对于按频率排序，我们基于已有的实现修改。 在每次取得最大值之后，输出并删除最大值，如此循环即可获得频率排序的单词序列。 也可以将单词-频率序列全部读出来存放到数组之中，然后用第二章的排序算法排序。 测试结果，取 minLength = 13，只截取了部分。 代码 # public static void LookUpDictionary(string filename, string dictionaryFile, int minLength) { // 初始化字典 var sr = new StreamReader(File.OpenRead(dictionaryFile)); var words = sr.ReadToEnd().Split(new[] { ' ', '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries); var dictionary = new BinarySearchSt<string, int>(); for (var i = 0; i < words. ...
3.1.27 # 解答 # 事实上就是说，先构造一个包含 N 个不重复键的符号表，然后进行 S 次查找。 给出 S 的增长数量级，使得构造符号表的成本和查找的成本相同。 这里假设一次数组交换和一次比较的成本是相同的。 先考虑构造符号表的成本，一次 Put() 需要调用一次 Rank() 和一次插入操作。 2.1 节插入排序的命题 B 给出了每次插入平均需要移动一半的数组元素的结论。 于是构造符号表所需的成本约为：$n\lg n + \frac{1}{2}\sum_{k=1}^{n} k=n\lg n + \frac{n(n-1)}{4} $ 。 这里查找的成本是这么计算的：$\lg0+\lg1+\cdots+\lg n < n\lg n$ 查找所需的成本比较简单，一次二分查找的比较次数约为 $\lg n$，总成本就是 $S\lg n$ 。 令两边相等，解方程即可得到 $S=n+\frac{n(n-1)}{4\lg n}$ 。 如果用大 O 记法，也可以记为 $O(n^2 / \lg n)$，如果要选择一个比较常用的上界则可以选择 $O(n^2)$。 实验结果，两边的成本是很接近的： 另请参阅 # SymbolTable 库
3.1.28 # 解答 # 将重新分配数组空间的代码提前，然后添加判断语句即可。 BinarySearchSTOrderedInsertion： /* 省略 */ if (_n == _keys.Length) Resize(_n * 2); // 如果插入的键比所有键都大则直接插入末尾。 if (_n == 0 || _keys[_n - 1].CompareTo(key) < 0) { _keys[_n] = key; _values[_n] = value; _n++; return; } var i = Rank(key); /* 省略 */ 另请参阅 # SymbolTable 库
3.1.29 # 解答 # 官方实现：https://algs4.cs.princeton.edu/31elementary/TestBinarySearchST.java.html 官方实现中有几处错误，需要做一些修改。 /* 省略 */ Console.WriteLine("Testing Select()"); Console.WriteLine("-----------------------------------"); for (var i = 0; i < st.Size(); i++) // 循环条件不能有 '=' Console.WriteLine(i + " " + st.Select(i)); Console.WriteLine(); /* 省略 */ while (!st.IsEmpty()) st.Delete(st.Select(st.Size() / 2)); Console.WriteLine("After deleting the remaining keys"); Console.WriteLine("-----------------------------------"); // 异常处理 try { foreach (var s in st.Keys()) Console.WriteLine(s + " " + st.Get(s)); } catch (Exception ex) { Console.WriteLine("Exception: " + ex.Message); } Console. ...
3.1.30 # 解答 # 官方实现：https://algs4.cs.princeton.edu/31elementary/BinarySearchST.java.html。 首先在 BinarySearchST 中添加如下方法。 /// <summary> /// 检查符号表结构是否有效。 /// </summary> /// <returns>检查通过则返回 <c>true</c>，否则返回 <c>false</c>。</returns> private bool Check() => IsSorted() && RankCheck(); /// <summary> /// 检查 <see cref="_keys"/> 数组是否有序。 /// </summary> /// <returns>如果 <see cref="_keys"/> 有序则返回 <c>true</c>，否则返回 <c>false</c>。</returns> private bool IsSorted() { for (var i = 1; i < Size(); i++) if (_keys[i].CompareTo(_keys[i - 1]) < 0) return false; return true; } /// <summary> /// 检查 Rank(Select(i)) = i 是否成立。 /// </summary> /// <returns>成立则返回 <c>true</c>，否则返回 <c>false</c>。</returns> private bool RankCheck() { for (var i = 0; i < Size(); i++) if (i ! ...