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

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

我

猜我必须更改返回 true; 部分内容说："好吧，删除该值，但是该链表中的其他值呢？

如果调用代码要求删除列表中的值，则它可能希望验证是否已找到该元素，也可能不希望验证是否已找到该元素。 如果要为调用方提供该见解，则仍可以返回 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 yetn";

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