2019-2-12
3.1.1 # 解答 # 官方解答：https://algs4.cs.princeton.edu/31elementary/GPA.java.html
ST.java：https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/ST.java.html
建立一个符号表，然后把键值放进去，读取计算即可。
和上一章节用过的方法类似，先定义了一个接口 IST<Key, Value> ，包含书中提到的基本 API。
然后定义类 ST ，用标准库里面的 Dictionary 实现了 IST 。
代码 # public class St<TKey, TValue> : ISt<TKey, TValue>, IEnumerable<TKey> { private readonly Dictionary<TKey, TValue> _st; /// <summary> /// 新建一个符号表。 /// </summary> public St() => _st = new Dictionary<TKey, TValue>(); /// <summary> /// 检查符号表中是否存在与键 <paramref name="key"/> 对应的值。 /// </summary> /// <param name="key">要检查是否存在的键。</param> /// <returns>如果存在则返回 <c>true</c>，否则返回 <c>false</c>。</returns> public virtual bool Contains(TKey key) => _st.
...
2019-2-12
3.1.2 # 解答 # 官方解答：https://algs4.cs.princeton.edu/31elementary/ArrayST.java.html
建立两个数组，分别存放键和值，一一对应。
添加时直接将新键值对放到数组最后即可。
删除时将待删除的键值对和位于最后的键值对交换，然后将其置空即可。
代码 # public class ArraySt<TKey, TValue> : ISt<TKey, TValue> { /// <summary> /// 键数组。 /// </summary> /// <value>键数组。</value> private TKey[] _keys; /// <summary> /// 值数组。 /// </summary> /// <value>值数组。</value> private TValue[] _values; /// <summary> /// 键值对数目。 /// </summary> /// <value>键值对数目。</value> private int _n; /// <summary> /// 建立基于数组实现的符号表。 /// </summary> public ArraySt() : this(8) { } /// <summary> /// 建立基于数组实现的符号表。 /// </summary> /// <param name="initCapacity">初始大小。</param> public ArraySt(int initCapacity) { _keys = new TKey[initCapacity]; _values = new TValue[initCapacity]; } /// <summary> /// 检查键 <typeparamref name="TKey"/> 是否存在。 /// </summary> /// <param name="key">需要检查是否存在的键。</param> /// <returns>如果存在则返回 <c>true</c>，否则返回 <c>false</c>。</returns> public bool Contains(TKey key) => Get(key).
...
2019-2-12
3.1.3 # 解答 # 基于无序链表的官方实现：https://algs4.cs.princeton.edu/31elementary/SequentialSearchST.java.html
有序符号表的 API 见书中表 3.1.4（中文版 P230，英文版 P366）。
在官方实现的基础上修改 Put 方法，先找到合适位置再插入新的键值对，保证链表有序。
为方便插入操作，可以使用双向链表作为基础进行实现。
表中同时维护开头和末尾引用，加快获得最值的速度。
代码 # public class OrderedSequentialSearchSt<TKey, TValue> : ISt<TKey, TValue>, IOrderedSt<TKey, TValue> where TKey : IComparable<TKey> { /// <summary> /// 符号表结点。 /// </summary> private class Node { public TKey Key { get; set; } // 键。 public TValue Value { get; set; } // 值。 public Node Next { get; set; } // 后继。 public Node Prev { get; set; } // 前驱。 } private Node _first; // 起始结点。 private Node _tail; // 末尾结点。 private int _n; // 键值对数量。 /// <summary> /// 大于等于 key 的最小值。 /// </summary> /// <returns>大于等于 key 的最小值，不存在则返回 <c>default(Key)</c>。</returns> public TKey Ceiling(TKey key) { var pointer = _first; while (pointer !
...
2019-2-13
3.1.4 # 解答 # 利用 Time 类型记录时间，用 Event 来记录事件内容。
Time 类型包含时分秒三个 int 变量，同时实现 IComparable 接口。
Event 类型只包含事件的名称，相当于对 string 做了一个封装。
随后以 Time 为键类型，Event 为值类型，利用上一题编写的有序符号表进行操作。
代码 # Time 类
public class Time : IComparable<Time> { public int Hour { get; init; } public int Minute { get; init; } public int Second { get; init; } public Time() : this(0, 0, 0) { } public Time(int hour, int minute, int second) { Hour = hour; Minute = minute; Second = second; } public int CompareTo(Time other) { var result = Hour.
...
2019-2-15
3.1.5 # 解答 # 官方解答：https://algs4.cs.princeton.edu/31elementary/SequentialSearchST.java.html
size() 方法只需要直接返回当前的 n 值即可。
delete() 方法需要遍历链表，找到对应结点并删除。
keys() 方法只需要根据当前的 n 新建一个数组，把链表中的键值存入即可。
代码 # /// <summary> /// 从表中删去键 <paramref name="key"/> 及其对应的值。 /// </summary> /// <param name="key">要删除的键。</param> public void Delete(TKey key) { if (key == null) throw new ArgumentNullException(nameof(key), "key can't be null"); Node before = null, target = _first; while (target != null && !target.Key.Equals(key)) { before = target; target = target.Next; } if (target != null) Delete(before, target); } /// <summary> /// 从链表中删除指定的结点。 /// </summary> /// <param name="before"><paramref name="target"/> 的前驱。</param> /// <param name="target">准备删除的结点。</param> /// <exception cref="ArgumentNullException">当 <paramref name="target"/> 为 <c>null</c> 时抛出此异常。</exception> private void Delete(Node before, Node target) { if (target == null) throw new ArgumentNullException(nameof(target), "target can't be null"); if (before == null) _first = target.
...
2019-2-17
3.1.6 # 解答 # FrequencyCounter 的官方实现：https://algs4.cs.princeton.edu/31elementary/FrequencyCounter.java.html
每个单词都会被放进符号表一次，
因此 Put 的调用次数就等于单词总数 W +1（注意寻找最大值的时候有一次 Put 调用）
对于重复的单词，输入时会先调用 Get 获得当前计数之后再 Put 回去。
寻找最大值时，对于符号表中的每个键值都会调用两次 Get。
重复的单词数量 = (W - D)。
因此 Get 方法的调用次数 = (W - D) + 2D
2019-2-17
3.1.7 # 解答 # 在 FrequencyCounter 中添加一个 CountDistinct 方法，计算不重复的键数。
public static int CountDistinct<TKey>(TKey[] keys, ISt<TKey, int> st) { var distinct = 0; for (var i = 0; i < keys.Length; i++) { if (!st.Contains(keys[i])) st.Put(keys[i], distinct++); } return distinct; } 结果如下：
另请参阅 # SymbolTable 库
2019-2-17
3.1.8 # 解答 # FrequencyCounter 的官方实现：https://algs4.cs.princeton.edu/31elementary/FrequencyCounter.java.html
《双城记》：https://introcs.cs.princeton.edu/java/data/tale.txt
官网给出的数据末尾有完整的版权说明，因此使用频率最高的单词变成了版权方的名字 Gutenberg-tm。
去掉末尾的版权声明之后，获得的单词是：Monseigneur
另请参阅 # SymbolTable 库
2019-2-19
3.1.9 # 解答 # FrequencyCounter 的官方实现：https://algs4.cs.princeton.edu/31elementary/FrequencyCounter.java.html
《双城记》：https://introcs.cs.princeton.edu/java/data/tale.txt
对 FrequencyCounter 做修改，在调用 Put 方法之前，将单词记录在字符串变量 lastPut 中。
在读入单词结束之后输出 lastPut 和 words 变量。
将末尾的版权信息删除后，得到的结果如下：
代码 # public static string MostFrequentlyWord(string filename, int minLength, ISt<string, int> st) { var words = 0; var sr = new StreamReader(File.OpenRead(filename)); var inputs = sr .ReadToEnd() .Split(new[] { ' ', '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries); var lastPut = ""; foreach (var s in inputs) { if (s.Length < minLength) continue; words++; if (st.
...
2019-2-19
3.1.10 # 解答 # 如图所示：
插入新的键值对需要遍历整个链表，比较次数等于链表在插入前的键值对数目。
修改已有的键值对则需要遍历链表直到找到该键值对，比较次数等于该键值对以及它之前所有键值对的数目。
共比较 0 + 1 + 2 + 3 + 4 + 5 + 6 + 4 + 6 + 7 + 8 + 9 = 55 次。