3.1.30

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

官方实现: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 库

上一题 下一题