c++ - 使用链接删除哈希表中的值

Question

我有一个在哈希表中搜索值的函数:

bool search(int n, Node* hashtable[]) {
    int x = n % 10;
    Node * temp;
    for (temp = hashtable[x]; temp != NULL; temp = temp->next) {
        if (temp->value == n) {
            return true;
        }
    }
    return false;
}

如何创建一个函数来删除 hashtable 中的值？
我猜我必须将 return true; 部分更改为如下内容:“好的，删除那个值，但是那个链表中的其他值呢？”

例如，我有 112 -> 1112 -> 111112，我想删除 1112。

Answer 1

要删除单链表中的某些内容，您必须获取它的链接以指向下一个元素或 NULL(如果删除最后一个元素)。当删除只有一个条目的列表时，您需要将hashtable[n] 更改为NULL。但是，我们无法判断此列表是单链接还是双链接。如果 Node 也有一个 prev 指针，您还需要以类似的方式更正它。我的建议是把你需要处理的案例写在纸上，想清楚指针的移动方式。

案例 1

hashtable[n] -> Node-to-delete -> NULL

案例 2

hashtable[n] -> Node -> Node-to-delete -> NULL

案例 3

hashtable[n] -> Node-to-delete -> Node -> NULL

案例 4

hashtable[n] -> Node -> Node-to-delete -> Node -> NULL

I'm guessing I have to change the return true; part to something that says: "ok, delete that value, but what about the other values in that linked list?"

如果调用代码要求删除列表中的值，它可能想要也可能不想验证是否找到了该元素。如果您想为调用者提供洞察力，那么您仍然可以返回 true 或 false。最好使用枚举来明确返回值的导入:

enum Result { Element_Found_And_Deleted, Element_Not_Found };

Result delete(int n, Node* hashtable[]);

// client usage:
if (delete(4, my_hashtable) != Element_Found_And_Deleted)
    FATAL("element not found - code must be broken");
...if applicable, or perhaps...
if (delete(4, my_hashtable) != Element_Found_And_Deleted)
    std::cout << "hey, you haven't added that value yet\n";

对于 search，如果 Node 包含的不仅仅是 value 键，那么调用者可能想要访问它并返回一个指向数据的指针比是否找到节点的 bool 指示符更有用。