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.Length; i++)
{
if (words[i].Length > minLength)
dictionary.Put(words[i], i);
}
sr.Close();
// 读入单词
var srFile = new StreamReader(File.OpenRead(filename));
var inputs = srFile.ReadToEnd().Split(new[] { ' ', '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries);
srFile.Close();
var stDictionary = new BinarySearchSt<int, string>();
var stFrequency = new BinarySearchSt<string, int>();
foreach (var s in inputs)
{
if (stFrequency.Contains(s))
stFrequency.Put(s, stFrequency.Get(s) + 1);
else if (dictionary.Contains(s))
{
stFrequency.Put(s, 1);
stDictionary.Put(dictionary.Get(s), s);
}
}
// 输出字典序
Console.WriteLine("Alphabet");
foreach (var i in stDictionary.Keys())
{
var s = stDictionary.Get(i);
Console.WriteLine(s + "\t" + stFrequency.Get(s));
}
// 频率序
Console.WriteLine("Frequency");
var n = stFrequency.Size();
for (var i = 0; i < n; i++)
{
var max = "";
stFrequency.Put(max, 0);
foreach (var s in stFrequency.Keys())
if (stFrequency.Get(s) > stFrequency.Get(max))
max = s;
Console.WriteLine(max + "\t" + stFrequency.Get(max));
stFrequency.Delete(max);
}
}