算法（第四版）C# 习题题解——3.1

写在前面

整个项目都托管在了 github 上：https://github.com/ikesnowy/algorithms-4th-edition-in-csharp
查找更方便的版本见：
这一节内容可能会用到的库文件有 symboltable，同样在 github 上可以找到。
善用 ctrl + f 查找题目。

习题&题解

3.1.1

题目

编写一段程序，创建一张符号表并建立字母成绩和数值分数的对应关系，如下表所示。从标准输入读取一系列字母成绩，计算并打印 gpa（字母成绩对应的分数的平均值）。

a+	a	a-	b+	b	b-	c+	c	c-	d	f
4.33	4.00	3.67	3.33	3.00	2.67	2.33	2.00	1.67	1.00	0.00

解答

官方解答：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 。

代码

using system.collections;
using system.collections.generic;

namespace symboltable
{
    /// <summary> 利用库函数实现的标准符号表。 </summary>
    public class st<key, value> : ist<key, value>, ienumerable<key>
    {
        private dictionary<key, value> st;

        /// <summary> 新建一个符号表。 </summary>
        public st() => this.st = new dictionary<key, value>();

        /// <summary> 检查符号表中是否存在与键 <paramref name="key"/> 对应的值。 </summary>
        public virtual bool contains(key key) => this.st.containskey(key);

        /// <summary> 从符号表中删除键 <paramref name="key"/> 及对应的值。 </summary>
        public virtual void delete(key key) => this.st.remove(key);

        /// <summary> 获取键 <paramref name="key"/> 对应的值，不存在时返回 null。 </summary>
        public virtual value get(key key) => this.st[key];

        /// <summary> 获取枚举器。 </summary>
        public ienumerator<key> getenumerator() => this.st.keys.getenumerator();

        /// <summary> 检查符号表是否为空。 </summary>
        public virtual bool isempty() => this.st.count == 0;

        /// <summary> 获得符号表中所有键的集合。 </summary>
        public virtual ienumerable<key> keys() => this.st.keys;

        /// <summary> 向符号表中插入新的键值对。 </summary>
        public virtual void put(key key, value value) => this.st.add(key, value);

        /// <summary> 获取符号表中键值对的数量。 </summary>
        public virtual int size() => this.st.count;

        /// <summary> 获取枚举器。 </summary>
        ienumerator ienumerable.getenumerator() => getenumerator();
    }
}

另请参阅

symboltable 库

3.1.2

题目

开发一个符号表的实现 arrayst，使用（无序）数组来实现我们的基本 api。

解答

官方解答：https://algs4.cs.princeton.edu/31elementary/arrayst.java.html

建立两个数组，分别存放键和值，一一对应。
添加时直接将新键值对放到数组最后即可。
删除时将待删除的键值对和位于最后的键值对交换，然后将其置空即可。

代码

using system;
using system.collections.generic;

namespace symboltable
{
    /// <summary>
    /// 符号表（数组实现）。
    /// </summary>
    /// <typeparam name="key">键类型。</typeparam>
    /// <typeparam name="value">值类型。</typeparam>
    public class arrayst<key, value> : ist<key, value> 
    {
        private key[] keys;             // 键数组
        private value[] values;         // 值数组
        private int n = 0;              // 键值对数目

        /// <summary>
        /// 建立基于数组实现的符号表。
        /// </summary>
        public arrayst() : this(8) { }

        /// <summary>
        /// 建立基于数组实现的符号表。
        /// </summary>
        /// <param name="initcapacity">初始大小。</param>
        public arrayst(int initcapacity)
        {
            this.keys = new key[initcapacity];
            this.values = new value[initcapacity];
        }

        /// <summary>
        /// 检查键 <typeparamref name="key"/> 是否存在。
        /// </summary>
        /// <param name="key">需要检查是否存在的键。</param>
        /// <returns></returns>
        public bool contains(key key) => get(key).equals(default(key));

        /// <summary>
        /// 删除键 <paramref name="key"/> 及对应的值。
        /// </summary>
        /// <param name="key">需要删除的键。</param>
        public void delete(key key)
        {
            for (int i = 0; i < this.n; i++)
            {
                if (key.equals(this.keys[i]))
                {
                    this.keys[i] = this.keys[this.n - 1];
                    this.values[i] = this.values[this.n - 1];
                    this.keys[this.n - 1] = default(key);
                    this.values[this.n - 1] = default(value);
                    this.n--;
                    if (this.n > 0 && this.n == this.keys.length / 4)
                        resize(this.keys.length / 2);
                    return;
                }
            }
        }

        /// <summary>
        /// 获取键对应的值，若键不存在则返回 null。
        /// </summary>
        /// <param name="key">需要查找的键。</param>
        /// <returns></returns>
        public value get(key key)
        {
            for (int i = 0; i < this.n; i++)
                if (this.keys[i].equals(key))
                    return this.values[i];
            return default(value);
        }

        /// <summary>
        /// 检查符号表是否为空。
        /// </summary>
        /// <returns></returns>
        public bool isempty() => this.n == 0;

        /// <summary>
        /// 获得包含全部键的集合。
        /// </summary>
        /// <returns></returns>
        public ienumerable<key> keys()
        {
            key[] result = new key[this.n];
            array.copy(this.keys, result, this.n);
            return result;
        }

        /// <summary>
        /// 向符号表中插入新元素，若键存在将被替换。
        /// </summary>
        /// <param name="key">键。</param>
        /// <param name="value">值。</param>
        public void put(key key, value value)
        {
            delete(key);

            if (this.n >= this.values.length)
                resize(this.n * 2);

            this.keys[this.n] = key;
            this.values[this.n] = value;
            this.n++;
        }

        /// <summary>
        /// 返回符号表中键值对的数量。
        /// </summary>
        /// <returns>键值对数量。</returns>
        public int size() => this.n;

        /// <summary>
        /// 为符号表重新分配空间。
        /// </summary>
        /// <param name="capacity">新分配的空间大小。</param>
        private void resize(int capacity)
        {
            key[] tempkey = new key[capacity];
            value[] tempvalue = new value[capacity];

            for (int i = 0; i < this.n; i++)
                tempkey[i] = this.keys[i];
            for (int i = 0; i < this.n; i++)
                tempvalue[i] = this.values[i];

            this.keys = tempkey;
            this.values = tempvalue;
        }
    }
}

另请参阅

symboltable 库

3.1.3

题目

开发一个符号表的实现 orderedsequentialsearchst，
使用有序链表来实现我们的有序符号表 api。

解答

基于无序链表的官方实现：https://algs4.cs.princeton.edu/31elementary/sequentialsearchst.java.html

有序符号表的 api 见书中表 3.1.4（中文版 p230，英文版 p366）。
在官方实现的基础上修改 put 方法，先找到合适位置再插入新的键值对，保证链表有序。
为方便插入操作，可以使用双向链表作为基础进行实现。
表中同时维护开头和末尾引用，加快获得最值的速度。

代码

using system;
using system.collections.generic;

namespace symboltable
{
    /// <summary>
    /// 基于有序链表的有序符号表实现。
    /// </summary>
    /// <typeparam name="key">符号表键类型。</typeparam>
    /// <typeparam name="value">符号表值类型。</typeparam>
    public class orderedsequentialsearchst<key, value> : ist<key, value>, iorderedst<key, value> 
        where key : icomparable<key>
    {
        /// <summary>
        /// 符号表结点。
        /// </summary>
        private class node
        {
            public key key { get; set; }        // 键。
            public value value { get; set; }    // 值。
            public node next { get; set; }      // 后继。
            public node prev { get; set; }      // 前驱。
        }

        private node first = null;      // 起始结点。
        private node tail = null;       // 末尾结点。
        private int n = 0;              // 键值对数量。

        /// <summary>
        /// 构造基于有序链表的有序符号表。
        /// </summary>
        public orderedsequentialsearchst() { }

        /// <summary>
        /// 大于等于 key 的最小值。
        /// </summary>
        /// <returns></returns>
        public key ceiling(key key)
        {
            node pointer = this.tail;
            while (pointer != null && greater(key, pointer.key))
                pointer = pointer.prev;
            return pointer == null ? default(key) : pointer.key;
        }

        /// <summary>
        /// 键 <paramref name="key"/> 在表中是否存在对应的值。
        /// </summary>
        /// <param name="key">键。</param>
        /// <returns></returns>
        public bool contains(key key) => floor(key).equals(key);

        /// <summary>
        /// 从表中删去键 <paramref name="key"/> 对应的值。
        /// </summary>
        /// <param name="key">键。</param>
        public void delete(key key)
        {
            node pointer = this.first;
            while (pointer != null && !pointer.key.equals(key))
                pointer = pointer.next;
            if (pointer == null)
                return;
            delete(pointer);
        }

        /// <summary>
        /// 从链表中删除结点 <paramref name="node"/>。
        /// </summary>
        /// <param name="node">待删除的结点。</param>
        private void delete(node node)
        {
            node prev = node.prev;
            node next = node.next;
            if (prev == null)
                this.first = next;
            else
                prev.next = next;

            if (next == null)
                this.tail = prev;
            this.n--;
        }

        /// <summary>
        /// 删除最大的键。
        /// </summary>
        public void deletemax()
        {
            if (this.n == 0)
                throw new exception("st underflow");
            delete(this.tail);
        }

        /// <summary>
        /// 删除最小的键。
        /// </summary>
        public void deletemin()
        {
            if (this.n == 0)
                throw new exception("st underflow");
            delete(this.first);
        }

        /// <summary>
        /// 小于等于 key 的最大值。
        /// </summary>
        /// <returns></returns>
        public key floor(key key)
        {
            node pointer = this.first;
            while (pointer != null && less(key, pointer.key))
                pointer = pointer.next;
            return pointer == null ? default(key) : pointer.key;
        }

        /// <summary>
        /// 获取键 <paramref name="key"/> 对应的值，不存在则返回 null。
        /// </summary>
        /// <param name="key">键。</param>
        /// <returns></returns>
        public value get(key key)
        {
            node pointer = this.first;
            while (pointer != null && greater(key, pointer.key))
                pointer = pointer.next;

            if (pointer == null)
                return default(value);
            else if (pointer.key.equals(key))
                return pointer.value;
            else
                return default(value);
        }

        /// <summary>
        /// 符号表是否为空。
        /// </summary>
        /// <returns></returns>
        public bool isempty() => this.n == 0;

        /// <summary>
        /// 获得符号表中所有键的集合。
        /// </summary>
        /// <returns></returns>
        public ienumerable<key> keys() => this.n == 0 ? new list<key>() : keys(this.first.key, this.tail.key);

        /// <summary>
        /// 获得符号表中 [<paramref name="lo"/>, <paramref name="hi"/>] 之间的键。
        /// </summary>
        /// <param name="lo">范围起点。</param>
        /// <param name="hi">范围终点。</param>
        /// <returns></returns>
        public ienumerable<key> keys(key lo, key hi)
        {
            list<key> list = new list<key>();
            node pointer = this.first;
            while (pointer != null && less(pointer.key, lo))
                pointer = pointer.next;
            while (pointer != null && less(pointer.key, hi))
            {
                list.add(pointer.key);
                pointer = pointer.next;
            }
            if (pointer.key.equals(hi))
                list.add(pointer.key);
            return list;
        }

        /// <summary>
        /// 最大的键。
        /// </summary>
        /// <returns></returns>
        public key max() => this.tail == null ? default(key) : this.tail.key;

        /// <summary>
        /// 最小的键。
        /// </summary>
        /// <returns></returns>
        public key min() => this.first == null ? default(key) : this.first.key;

        /// <summary>
        /// 向符号表插入键值对，重复值将被替换。
        /// </summary>
        /// <param name="key">键。</param>
        /// <param name="value">值。</param>
        public void put(key key, value value)
        {
            delete(key);

            node temp = new node()
            {
                key = key,
                value = value,
                prev = null,
                next = null
            };

            node left = null, right = this.first;
            while (right != null && less(right.key, temp.key))
            {
                left = right;
                right = right.next;
            }

            insert(left, right, temp);

            if (left == null)
                this.first = temp;
            if (right == null)
                this.tail = temp;
            this.n++;
        }

        /// <summary>
        /// 小于 key 的键的数量。
        /// </summary>
        /// <returns></returns>
        public int rank(key key)
        {
            int counter = 0;
            node pointer = this.first;
            while (pointer != null && less(pointer.key, key))
            {
                pointer = pointer.next;
                counter++;
            }
            return counter;
        }

        /// <summary>
        /// 获得排名为 k 的键（从 0 开始）。
        /// </summary>
        /// <param name="k">排名</param>
        /// <returns></returns>
        public key select(int k)
        {
            if (k >= this.n)
                throw new exception("k must less than st size!");

            node pointer = this.first;
            for (int i = 0; i < k; i++)
                pointer = pointer.next;
            return pointer.key;
        }

        /// <summary>
        /// 获得符号表中键值对的数量。
        /// </summary>
        /// <returns></returns>
        public int size() => this.n;

        /// <summary>
        /// [<paramref name="lo"/>, <paramref name="hi"/>] 之间键的数量。
        /// </summary>
        /// <param name="lo">范围起点。</param>
        /// <param name="hi">范围终点。</param>
        /// <returns></returns>
        public int size(key lo, key hi)
        {
            int counter = 0;
            node pointer = this.first;
            while (pointer != null && less(pointer.key, lo))
                pointer = pointer.next;
            while (pointer != null && less(pointer.key, hi))
            {
                pointer = pointer.next;
                counter++;
            }
            return counter;
        }

        /// <summary>
        /// 键 <paramref name="a"/> 是否小于 <paramref name="b"/>。
        /// </summary>
        /// <param name="a">检查是否较小的键。</param>
        /// <param name="b">检查是否较大的键。</param>
        /// <returns></returns>
        private bool less(key a, key b) => a.compareto(b) < 0;

        /// <summary>
        /// 键 <paramref name="a"/> 是否大于 <paramref name="b"/>。
        /// </summary>
        /// <param name="a">检查是否较大的键。</param>
        /// <param name="b">检查是否较小的键。</param>
        /// <returns></returns>
        private bool greater(key a, key b) => a.compareto(b) > 0;

        /// <summary>
        /// 将结点 <paramref name="k"/> 插入到 <paramref name="left"/> 和 <paramref name="right"/> 之间。
        /// </summary>
        /// <param name="left">作为前驱的结点。</param>
        /// <param name="right">作为后继的结点。</param>
        /// <param name="insert">待插入的结点。</param>
        private void insert(node left, node right, node k)
        {
            k.prev = left;
            k.next = right;
            if (left != null)
                left.next = k;

            if (right != null)
                right.prev = k;
        }
    }
}

另请参阅

symboltable 库

3.1.4

题目

开发抽象数据类型 time 和 event 来处理表 3.1.5 中的例子中的数据。

解答

利用 time 类型记录时间，用 event 来记录事件内容。

time 类型包含时分秒三个 int 变量，同时实现 icomparable 接口。
event 类型只包含事件的名称，相当于对 string 做了一个封装。

随后以 time 为键类型，event 为值类型，利用上一题编写的有序符号表进行操作。

代码

time 类

using system;
using system.text;

namespace _3._1._4
{
    /// <summary>
    /// 时间类。
    /// </summary>
    public class time : icomparable<time>
    {
        public int hour { get; set; }
        public int minute { get; set; }
        public int second { get; set; }

        public time() : this(0, 0, 0) { }

        public time(int hour, int minute, int second)
        {
            this.hour = hour;
            this.minute = minute;
            this.second = second;
        }

        public int compareto(time other)
        {
            int result = this.hour.compareto(other.hour);
            if (result == 0)
                result = this.minute.compareto(other.minute);
            if (result == 0)
                result = this.second.compareto(other.second);
            return result;
        }

        public override bool equals(object obj)
        {
            if (this == obj)
                return true;
            return compareto((time)obj) == 0;
        }

        public override int gethashcode()
        {
            int result = 1;
            result += this.hour;
            result *= 31;
            result += this.minute;
            result *= 31;
            result += this.second;
            return result;
        }

        public override string tostring()
        {
            stringbuilder sb = new stringbuilder();
            sb.append(this.hour < 10 ? "0" + this.hour : this.hour.tostring());
            sb.append(":");
            sb.append(this.minute < 10 ? "0" + this.minute : this.minute.tostring());
            sb.append(":");
            sb.append(this.second < 10 ? "0" + this.second : this.second.tostring());
            return sb.tostring();
        }
    }
}

event 类

namespace _3._1._4
{
    public class event
    {
        public string eventmessage { get; set; }

        public event() : this(null) { }

        public event(string message)
        {
            this.eventmessage = message;
        }

        public override string tostring()
        {
            return this.eventmessage;
        }
    }
}

另请参阅

symboltable 库

3.1.5

题目

实现 sequentialsearchst 中的 size()、delete() 和 keys() 方法。

解答

官方解答：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(key key)
{
    if (key == null)
        throw new argumentnullexception("key can't be null");
    node before = null, target = this.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("target can't be null");

    if (before == null)
        this.first = target.next;
    else
        before.next = target.next;
    this.n--;
}

/// <summary>
/// 获得所有的键。
/// </summary>
/// <returns>包含所有键的集合。</returns>
public ienumerable<key> keys()
{
    key[] keys = new key[this.n];
    node pointer = this.first;
    for (int i = 0; i < this.n; i++)
    {
        keys[i] = pointer.key;
        pointer = pointer.next;
    }
    return keys;
}

/// <summary>
/// 获取符号表中的键值对数量。
/// </summary>
/// <returns>当前符号表中的键值对数量。</returns>
public int size() => this.n;

另请参阅

symboltable 库

3.1.6

题目

用输入中的单词总数 w 和不同单词总数 d 的函数给出 frequencycounter 调用的 put() 和 get() 方法的次数。

解答

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

题目

对于 n=10、10^2、10^3、10^4、10^5 和 10^6，
在 n 个小于 1000 的随机非负整数中 frequencycounter 平均能够找到多少个不同的键？

解答

在 frequencycounter 中添加一个 countdistinct 方法，计算不重复的键数。

public static int countdistinct<tkey>(tkey[] keys, ist<tkey, int> st)
{
    int distinct = 0;
    for (int i = 0; i < keys.length; i++)
    {
        if (!st.contains(keys[i]))
            st.put(keys[i], distinct++);
    }
    return distinct;
}

结果如下：

另请参阅

symboltable 库

3.1.8

题目

在《双城记》中，使用频率最高的长度大于等于 10 的单词是什么？

解答

frequencycounter 的官方实现：https://algs4.cs.princeton.edu/31elementary/frequencycounter.java.html
《双城记》：

官网给出的数据末尾有完整的版权说明，因此使用频率最高的单词变成了版权方的名字 gutenberg-tm。
去掉末尾的版权声明之后，获得的单词是：monseigneur

另请参阅

symboltable 库

3.1.9

题目

在 frequencycounter 中添加追踪 put() 方法的最后一次调用的代码。
打印出最后插入的那个单词以及在此之前总共从输入中处理了多少个单词。
用你的程序处理 tale.txt 中长度分别大于等于 1、8 和 10 的单词。

解答

frequencycounter 的官方实现：https://algs4.cs.princeton.edu/31elementary/frequencycounter.java.html
《双城记》：

对 frequencycounter 做修改，在调用 put 方法之前，将单词记录在字符串变量 lastput 中。
在读入单词结束之后输出 lastput 和 words 变量。

将末尾的版权信息删除后，得到的结果如下：

代码

public static string mostfrequentlyword(string filename, int minlength, ist<string, int> st)
{
    int distinct = 0, words = 0;
    streamreader sr = new streamreader(file.openread(filename));

    string[] inputs = 
        sr
        .readtoend()
        .split(new char[] { ' ', '\r', '\n' }, 
        stringsplitoptions.removeemptyentries);

    string lastput = "";
    foreach (string s in inputs)
    {
        if (s.length < minlength)
            continue;
        words++;
        if (st.contains(s))
        {
            lastput = s;
            st.put(s, st.get(s) + 1);
        }
        else
        {
            lastput = s;
            st.put(s, 1);
            distinct++;
        }
    }

    console.writeline("last put: " + lastput + "\t words count: " + words);

    string max = "";
    st.put(max, 0);
    foreach (string s in st.keys())
        if (st.get(s) > st.get(max))
            max = s;

    return max;
}

另请参阅

symboltable 库

3.1.10

题目

给出用 sequentialsearchst 将
键 e a s y q u e s t i o n 插入一个空符号表的过程的轨迹。
一共进行了多少次比较？

解答

如图所示：

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

3.1.11

题目

给出用 binarysearchst 将键 e a s y q u e s t i o n 插入一个空符号表的过程的轨迹。
一共进行了多少次比较？

解答

键的轨迹如下图所示：

键查找使用二分查找优化，插入新的键时不必与每个键都进行比较。
共进行了 0 + 1 + 2 + 2 + 2 + 3 + 3 + 3 + 3 + 3 + 3 + 4 = 29 次比较。

3.1.12

题目

修改 binarysearchst，用一个 item 对象的数组而非两个平行数组来保存键和值。
添加一个构造函数，接受一个 item 的数组为参数并将其归并排序。

解答

建立类 item：

public class item<tkey, tvalue> : icomparable<item<tkey, tvalue>>
    where tkey : icomparable<tkey>
{
    public tkey key { get; set; }
    public tvalue value { get; set; }

    public int compareto(item<tkey, tvalue> other)
    {
        return this.key.compareto(other.key);
    }
}

之后修改 binarysearchst，将其中的 tkey[] keys 和 tvalue[] values 数组用 item[] items 数组代替。
例如 keys[i] 变为 items[i].key，values[i] 变为 items[i].value。

添加一个构造函数，调用之前编写的归并排序实现。

/// <summary>
/// 根据已有的键值对构造一个符号表。
/// </summary>
/// <param name="items">已有的键值对。</param>
public itembinarysearchst(item<tkey, tvalue>[] items)
{
    this.items = new item<tkey, tvalue>[items.length];
    array.copy(items, this.items, items.length);
    this.n = items.length;
    mergesort merge = new mergesort();
    merge.sort(this.items);
}

另请参阅

merge 库
symboltable 库

3.1.13

题目

对于一个会随机混合进行 10^3 次 put() 和 10^6 次 get() 操作的应用程序，
你会使用本节中的哪种符号表的实现？说明理由。

解答

get() 调用次数比 put() 调用次数多了三个数量级，
binarysearchst 和 sequentialsearchst 的平均 put() 开销是一样的，
因此选择平均 get() 开销更小的 binarysearchst。

3.1.14

题目

对于一个会随机混合进行 10^6 次 put() 和 10^3 次 get() 操作的应用程序，
你会使用本节中的哪种符号表实现？说明理由。

解答

根据上题给出的结论，选择 binarysearchst。
由于 binarysearchst 和 sequentialsearchst 执行 put() 的开销相同
因此选择 get() 开销更低的 binarysearchst。

3.1.15

题目

假设在一个 binarysearchst 的用例程序中，查找操作的次数是插入操作的 1000 倍。
当分别进行 10^3、10^6 和 10^9 次查找时，请估计插入操作在总耗时中的比例。

解答

假设先全部 put()，再进行查找操作。
即分别进行 $ 1 $, $ 10 ^ 3 $, $ 10 ^ 6 $ 次插入
$ n = 1 $ 时，可以直接得出比例 $ 0.1 % $。
$ n = 10 ^ 3 $ 时，
插入耗时 $ = 1 + 2 + ... + 10 ^ 3 = 500500 $，
查询耗时 $ = 10 ^ 6 * \lg(10 ^ 3) = 9965784 $，
比例为 $ 4.782 % $。
$ n = 10 ^ 6 $ 时
插入耗时 $ = 1 + 2 + ... + 10 ^ 6 = 500000500000 $，
查询耗时 $ = 10 ^ 9 * \lg(10 ^ 6) = 19931568569 $，
比例为 $ 96.17 % ​$。

3.1.16

题目

为 binarysearchst 实现 delete() 方法。

解答

官方实现：https://algs4.cs.princeton.edu/31elementary/binarysearchst.java.html

先通过二分查找获得下标，然后后面的元素依次向前移动一位。

public void delete(tkey key)
{
    if (key == null)
        throw new argumentnullexception("argument to delete() is null");
    if (isempty())
        return;

    int i = rank(key);

    if (i == this.n && this.keys[i].compareto(key) != 0)
        return;

    for (int j = i; j < this.n - 1; j++)
    {
        this.keys[j] = this.keys[j + 1];
        this.values[j] = this.values[j + 1];
    }

    this.n--;
    this.keys[this.n] = default(tkey);
    this.values[this.n] = default(tvalue);

    if (this.n > 0 && this.n == this.keys.length / 4)
        resize(this.n / 2);
}

另请参阅

symboltable 库

3.1.17

题目

为 binarysearchst 实现 floor() 方法。

解答

官方实现：https://algs4.cs.princeton.edu/31elementary/binarysearchst.java.html

先通过二分查找大于等于 key 的键下标 i，
如果 keys[i] 和 key 相等则直接返回 keys[i]，
否则返回 keys[i-1]。

public tkey floor(tkey key)
{
    if (key == null)
        throw new argumentnullexception("argument to floor() is null");
    int i = rank(key);
    if (i < this.n && this.keys[i].compareto(key) == 0)
        return this.keys[i];
    if (i == 0)
        return default(tkey);
    else
        return this.keys[i - 1];
}

另请参阅

symboltable 库

3.1.18

题目

证明 binarysearchst 中 rank() 方法的实现的正确性。

解答

设 key 为目标键。
算法初始时 lo = 0, hi = n - 1，数组已排序。
当找到目标键时，返回的下标 mid 显然是正确的。
（0...a[mid - 1] 都小于 a[mid]，同时 a[mid] = key）

接下来证明：当目标键不存在时，lo 可以代表小于 key 的键的个数。
由算法内容，当循环退出时，一定有 lo 和 hi 交叉，即 lo > hi。
考虑最后一次循环，必然执行了 lo = mid + 1 或者 hi = mid - 1。
即最后一次循环之后 lo = mid + 1 > hi 或 hi = mid - 1 < lo。
又由于 mid = (lo + hi) / 2，代入有：
即(lo + hi) / 2 + 1 > hi 或(lo + hi) / 2 - 1 < lo
(lo - hi) / 2 + 1 > 0 或(hi - lo) / 2 - 1 < 0
(hi - lo) / 2 < 1
hi - lo < 2
由于 hi 和 lo 都是整数，故有 hi -lo <= 1

由算法的内容可以得出，最后一次循环时，
下标小于 lo 的元素都小于 key，下标大于 hi 的元素都大于 key
且下标小于 lo 的元素正好有 lo 个 （0...lo - 1)。

当 lo = hi 时，mid = lo
若 key > lo，则 lo = lo + 1，即 a[lo] 本身也小于 key。
若 key < lo，lo 不变，即 a[lo] 就是大于 key 的第一个元素。

当 lo = hi - 1 时，mid = lo
若 key > lo，则 lo = lo + 1 = hi，变为上一种情况。
若 key < lo，则 hi = lo - 1，a[lo] 是大于 key 的第一个元素。

综上，rank() 是正确的。

3.1.19

题目

修改 frequencycounter，打印出现频率最高的所有单词，而非之一。
提示：请用 queue。

解答

将频率和当前最大频率相同的单词都放到一个队列里即可。

string max = "";
queue<string> queue = new queue<string>();
st.put(max, 0);
foreach (string s in st.keys())
{
    if (st.get(s) > st.get(max))
    {
        max = s;
        queue.clear();
        queue.enqueue(s);
    }
    else if (st.get(s) == st.get(max))
    {
        queue.enqueue(s);
    }
}

另请参阅

symboltable 库

3.1.20

题目

补全命题 b 的证明（证明 n 的一般情况）。
提示：先证明 c(n) 的单调性，即对于所有的 n>0，c(n)<=c(n+1)。

解答

国内的书中关于命题 b 的证明有错误，新版的证明如下：

虽然新版还是有个小错误，$ n-2 $ 应该改为 $ k-2 $。
勘误见：。

先证单调性，利用数学归纳法：
已知对于 $ n=0 ​$，满足 $ c(0) \le c(1) ​$。
假设对于 $ n=n ​$，满足 $ c(n) \le c(n+1) ​$。
根据递归式，有：
\[ \begin{eqnarray*} & c(n) & \le c(\lfloor n/2 \rfloor) + 1 \\ \\ & c(n+1) & \le \begin{cases} c(\lfloor n/2 \rfloor) +1 & \text{$ n $ 是偶数} \\ c(\lfloor n/2 \rfloor + 1) + 1 & \text{$ n $ 是奇数} \end{cases}\\ \\ & c(n+2) & \le c(\lfloor n/2 \rfloor + 1) + 1 \end{eqnarray*} \]
又 $ c(n) \le c(n+1) ​$ ，推出 $ c(\lfloor n/2 \rfloor) + 1 \le c(\lfloor n/2 \rfloor + 1) + 1 ​$。
故 $ c(n+1) \le c(n+2) ​\(，由数学归纳法，\) c(n) \le c(n+1) ​$ 成立。

已知当 $ n = 2^k - 1 $ 时，有 $ c(n) \le k = \lg(n+1) \le \lg n + 1$。
接下来证明在 $ (2^k - 1, 2^{k + 1} -1) $ 范围内上式仍然成立。
不妨设 $ 0 < m < 2^k $ ，则有 $ 2^k - 1 < n + m < 2^{k + 1} -1 \(。 转变为证：\) c(n+m) \le \lg (n+m) + 1 $ 。
由于 $ c(n+m) $ 是一个整数，则 $ \lfloor \lg(n+m) +1\rfloor = k+1 $。
即求证： $ c(n+m) \le k+1 $。
由单调性可得 $ c(n+m) \le c(2^{k+1} - 1) \le k+1 ​$，得证。

3.1.21

题目

内存使用。
基于 1.4 节中的假设，
对于 n 对键值比较 binarysearchst 和 sequentialsearchst 的内存使用情况。
不需要记录键值本身占用的内存，只统计它们的引用。
对于binarysearchst，假设数组大小可以动态调整，
数组中被占用的空间比例为 25%~100%。

解答

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

题目

自组织查找。
自组织查找指的是一种能够将数组元素重新排序
使得被访问频率较高的元素更容易被找到的查找算法。
请修改你为习题 3.1.2 给出的答案，在每次查找命中时：
将被找到的键值对移动到数组的开头，将所有中间的键值对向右移动一格。
这个启发式的过程被称为前移编码。

解答

对 get() 做修改，得到 movetofrontarrayst。

public tvalue get(tkey key)
{
    int i;
    for (i = 0; i < this.n; i++)
        if (this.keys[i].equals(key))
            break;

    if (i == this.n)
        return default(tvalue);

    tkey tofrontkey = this.keys[i];
    tvalue tofrontvalue = this.values[i];

    for (int j = i; j > 0; j--)
        this.keys[j] = this.keys[j - 1];
    for (int j = i; j > 0; j--)
        this.values[j] = this.values[j - 1];

    this.keys[0] = tofrontkey;
    this.values[0] = tofrontvalue;

    return this.values[0];
}

另请参阅

symboltable 库

3.1.23

题目

二分查找的分析。
请证明对于大小为 n 的符号表，
一次二分查找所需的最大比较次数正好是 n 的二进制表示的位数，
因为右移一位的操作会将二进制的 n 变为二进制的 [n/2]。

解答

这里的右移操作可以理解为 「小数点前移一位」
即数字依次向右退一位，个位上的数字被舍弃。
对于十进制，小数点前移一位会使 $ n $ 变为 $ \lfloor n / 10 \rfloor $。
同样对于二进制就会使 $ n $ 变为 $ \lfloor n / 2 \rfloor $。
当需要除以 $ 2 $ 的 $ k $ 次幂的时候，可以用右移 $ k $ 位代替并减少时间开销。
同理可以用左移 $ k $ 位来代替乘以 $ 2 $ 的 $ k $ 次幂。
注：
这样会降低程序可读性，
并且某些语言（c / c++）的编译器已经可以自动执行这项优化了。
请充分考虑你的代码受众之后再决定是否采用这种写法。

二分查找的最大查找次数 = $ \lg n + 1$ （见 3.1.20 的证明）
一个数最多被左移的次数也正好等于 $ \lfloor \lg n \rfloor + 1 $
（任意正整数都能被表示为 $ 2 ^ k + m $ 的形式，即 $ k +1 $ 位二进制数）
因此一次二分查找所需的最大比较次数正好是 $ n $ 的二进制表示的位数。

3.1.24

题目

插值法查找。
假设符号表的键支持算术操作（例如，它们可能是 double 或者 integer 类型的值）。
编写一个二分查找来模拟查字典的行为，
例如当单词的首字母在字母表的开头时我们也会在字典的前半部分进行查找。
具体来说，设 klo 为符号表的第一个键，khi 为符号表的最后一个键，
当要查找 kx 时，先和 [(kx-klo)/(khi-klo)] 进行比较，而非取中间元素。
用 searchcompare 调用 frequencycounter 来比较你的实现和 binarysearchst 的性能。

解答

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.contains(s))
            st.put(s, st.get(s) + 1);
        else
            st.put(s, 1);
    }

    tkey max = keys[0];
    foreach (tkey s in st.keys())
        if (st.get(s) > st.get(max))
            max = s;

    return max;
}

另请参阅

symboltable 库

3.1.25

题目

缓存。因为默认的 contains() 的实现中调用了 get()，
所以 frequencycounter 的内循环会将同一个键查找两三遍：

if (!st.contains(word)) st.put(word, 1);
else st.put(word, st.get(word) + 1);

为了能够提高这样的用例代码的效率，我们可以用一种叫做缓存的技术手段，
即将访问最频繁的键的位置保存在一个变量中。
修改 sequentialsearchst 和 binarysearchst 来实现这个点子。

解答

英文原文指的是 most recently accessed key，因此指的是最近访问的键。

实现比较简单，先在类中定义一个新的成员 cache 作为缓存，
然后修改 get 方法，在实际查找之前先检查缓存，如果缓存未命中则在查找之后更新它。
要注意的是缓存指向内容的有效性，在数组中指的是下标是否有效，在链表中指的是结点是否为空。

利用《双城记》测试的结果：

代码

binarysearchst

cache 是一个 int 类型的变量，代表下标。
在二分查找前先检查缓存，要注意cache超出数组大小的情况。
如果缓存未命中，则进行二分查找，并在返回结果前更新缓存。

public tvalue get(tkey key)
{
    if (key == null)
        throw new argumentnullexception("argument to get() is null");
    if (isempty())
        return default(tvalue);
    if (this.cache < this.n && this.keys[this.cache].equals(key)) // 缓存检查
        return this.values[this.cache];
    int rank = rank(key);
    if (rank < this.n && this.keys[rank].equals(key))
    {
        this.cache = rank;                                        // 更新缓存
        return this.values[rank];
    }

    return default(tvalue);
}

sequentialsearchst

cache 是一个结点类型的变量，代表一个键值对。
类似的，在顺序查找前先检查缓存，如果缓存未命中则更新缓存。
要注意的是如果缓存的结点被删除，需要将缓存置为 null。

get() 方法

public tvalue get(tkey key)
{
    if (key == null)
        throw new argumentnullexception("key can't be null");

    if (this.cache != null && this.cache.key.equals(key)) // 检查缓存
        return this.cache.value;
    for (node pointer = this.first; pointer != null; pointer = pointer.next)
    {
        if (pointer.key.equals(key))
        {
            this.cache = pointer;                         // 更新缓存
            return pointer.value;
        }
    }
    return default(tvalue);
}

delete() 方法

public void delete(tkey key)
{
    if (key == null)
        throw new argumentnullexception("key can't be null");
    node before = null, target = this.first;
    while (target != null && !target.key.equals(key))
    {
        before = target;
        target = target.next;
    }
    if (target == this.cache)           // 删除缓存
        this.cache = null;
    if (target != null)
        delete(before, target);
}

另请参阅

symboltable 库

3.1.26

题目

基于字典的频率统计。
修改 frequencycounter，接受一个字典文件作为参数，
统计标准输入中出现在字典中的单词的频率，并将单词和频率打印为两张表格，
一张按照频率高低排序，一张按照字典顺序排序。

解答

字典文件：
《双城记》：
浏览器可能会直接打开 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)
{
    // 初始化字典
    streamreader sr = new streamreader(file.openread(dictionaryfile));
    string[] words = sr.readtoend().split(new char[] { ' ', '\r', '\n' }, stringsplitoptions.removeemptyentries);
    binarysearchst<string, int> dictionary = new binarysearchst<string, int>();
    for (int i = 0; i < words.length; i++)
    {
        if (words[i].length > minlength)
            dictionary.put(words[i], i);
    }
    sr.close();

    // 读入单词
    streamreader srfile = new streamreader(file.openread(filename));
    string[] inputs = srfile.readtoend().split(new char[] { ' ', '\r', '\n' }, stringsplitoptions.removeemptyentries);
    srfile.close();

    binarysearchst<int, string> stdictionary = new binarysearchst<int, string>();
    binarysearchst<string, int> stfrequency = new binarysearchst<string, int>();
    foreach (string 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 (int i in stdictionary.keys())
    {
        string s = stdictionary.get(i);
        console.writeline(s + "\t" + stfrequency.get(s));
    }

    // 频率序
    console.writeline("frequency");
    int n = stfrequency.size();
    for (int i = 0; i < n; i++)
    {
        string max = "";
        stfrequency.put(max, 0);
        foreach (string s in stfrequency.keys())
            if (stfrequency.get(s) > stfrequency.get(max))
                max = s;
        console.writeline(max + "\t" + stfrequency.get(max));
        stfrequency.delete(max);
    }
}

另请参阅

symboltable 库

3.1.27

题目

小符号表。
假设一段 binarysearchst 的用例插入了 n 个不同的键并会进行 s 次查找。
当构造表的成本和所有查找的总成本相同时，给出 s 的增长数量级。

解答

事实上就是说，先构造一个包含 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

题目

有序的插入。
修改 binarysearchst，使得插入一个比当前所有键都大的键只需要常数时间
（这样在构造符号表时有序的使用 put() 插入键值对就只需要线性时间了）。

解答

将重新分配数组空间的代码提前，然后添加判断语句即可。
binarysearchstorderedinsertion：

/* 省略 */

if (this.n == this.keys.length)
    resize(this.n * 2);

// 如果插入的键比所有键都大则直接插入末尾。
if (this.n == 0 || this.keys[this.n - 1].compareto(key) < 0)
{
    this.keys[this.n] = key;
    this.values[this.n] = value;
    this.n++;
    return;
}

int i = rank(key);

/* 省略 */

另请参阅

symboltable 库

3.1.29

题目

测试用例。
编写一段测试代码 testbinarysearch.java
用来测试正文中
min()、max()、floor()、ceiling()、select()、rank()、deletemin()、deletemax() 和 keys() 的实现。
可以参考 3.1.3.1 节的索引用例，添加代码使其在适当的情况下接受更多的命令行参数。

解答

官方实现：https://algs4.cs.princeton.edu/31elementary/testbinarysearchst.java.html

官方实现中有几处错误，需要做一些修改。

/* 省略 */

console.writeline("testing select()");
console.writeline("-----------------------------------");
for (int 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 (string s in st.keys())
        console.writeline(s + " " + st.get(s));
}
catch (exception ex)
{
    console.writeline("exception: " + ex.message);
}
console.writeline();

/* 省略 */

结果如下：

size = 10
min = a
max = x

testing keys()
-----------------------------------
a 8
c 4
e 12
h 5
l 11
m 9
p 10
r 3
s 0
x 7

testing select()
-----------------------------------
0 a
1 c
2 e
3 h
4 l
5 m
6 p
7 r
8 s
9 x

key rank floor ceil
-----------------------------------
a 0 a a
b 1 a c
c 1 c c
d 2 c e
e 2 e e
f 3 e h
g 3 e h
h 3 h h
i 4 h l
j 4 h l
k 4 h l
l 4 l l
m 5 m m
n 6 m p
o 6 m p
p 6 p p
q 7 p r
r 7 r r
s 8 s s
t 9 s x
u 9 s x
v 9 s x
w 9 s x
x 9 x x
y 10 x
z 10 x

after deleting the smallest 3 keys
-----------------------------------
h 5
l 11
m 9
p 10
r 3
s 0
x 7

after deleting the remaining keys
-----------------------------------
exception: called min() with empty table

after adding back n keys
-----------------------------------
a 8
c 4
e 12
h 5
l 11
m 9
p 10
r 3
s 0
x 7

另请参阅

symboltable 库

3.1.30

题目

验证。
向 binarysearchst 加入断言（assert）语句，
在每次插入和删除数据后检查算法的有效性和数据结构的完整性。
例如，对于每个索引必有 i==rank(select(i)) 且数组应该总是有序的。

解答

官方实现：https://algs4.cs.princeton.edu/31elementary/binarysearchst.java.html。

首先在 binarysearchst 中添加如下方法。

/// <summary> 检查符号表结构是否有效。 </summary>
private bool check() => issorted() && rankcheck();

/// <summary> 检查 <see cref="keys"/> 数组是否有序。 </summary>
private bool issorted()
{
    for (int i = 1; i < size(); i++)
        if (this.keys[i].compareto(this.keys[i - 1]) < 0)
            return false;
    return true;
}

/// <summary> 检查 rank(select(i)) = i 是否成立。 </summary>
private bool rankcheck()
{
    for (int i = 0; i < size(); i++)
        if (i != rank(select(i)))
            return false;
    for (int i = 0; i < size(); i++)
        if (keys[i].compareto(select(rank(this.keys[i]))) != 0)
            return false;
    return true;
}

然后在 put() 和 delete() 方法的末尾添加：debug.assert(check()); 即可。

另请参阅

symboltable 库

3.1.31

题目

性能测试。
编写一段性能测试程序，先用 put() 构造一张符号表，再用 get() 进行访问，
使得表中的每个键平均被命中 10 次，且有大致相同次数的未命中访问。
键为