3.1.5

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.Next;
    else
        before.Next = target.Next;
    _n--;
}

/// <summary>
/// 获得所有的键。
/// </summary>
/// <returns>包含所有键的集合。</returns>
public IEnumerable<TKey> Keys()
{
    var keys = new TKey[_n];
    var pointer = _first;
    for (var i = 0; i < _n; i++)
    {
        keys[i] = pointer.Key;
        pointer = pointer.Next;
    }
    return keys;
}

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

另请参阅 #

SymbolTable 库