Searching

3.1.1

2019-2-12
Searching

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. ...

3.1.2

2019-2-12
Searching

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). ...

3.1.3

2019-2-12
Searching

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 ! ...

3.1.4

2019-2-13
Searching

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. ...

3.1.5

2019-2-15
Searching

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. ...

3.1.6

2019-2-17
Searching

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

3.1.7

2019-2-17
Searching

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 库

3.1.8

2019-2-17
Searching

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 库

3.1.9

2019-2-19
Searching

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. ...

3.1.10

2019-2-19
Searching

3.1.10 # 解答 # 如图所示: 插入新的键值对需要遍历整个链表,比较次数等于链表在插入前的键值对数目。 修改已有的键值对则需要遍历链表直到找到该键值对,比较次数等于该键值对以及它之前所有键值对的数目。 共比较 0 + 1 + 2 + 3 + 4 + 5 + 6 + 4 + 6 + 7 + 8 + 9 = 55 次。