Remove函数删除哈希表中的所有节点

Question

下面这段代码用于从哈希表中删除一个条目。当我运行代码时，程序不会崩溃，而是需要删除元素的特定桶中的所有节点都被删除了。插入和删除元素的计数正常。

示例

删除之前。节点数= 11

Bucket[0]
Node01, Node02, Node03
Bucket[1]
Node11, Node12, Node13, Node14
Bucket[2]
Node21, Node22
Bucket[3]
EMPTY
Bucket[4]
Node41, Node42

删除Node12

哈希表变成。节点数= 10

Bucket[0]
Node01, Node02, Node03
Bucket[1]
EMPTY //This should be Node11, Node13, Node14
Bucket[2]
Node21, Node22
Bucket[3]
EMPTY
Bucket[4]
Node41, Node42

删除方法

 void HashT::Remove(string key)
    {
        size_t index = HashFunc(key);
        if (table[index] != NULL)
        {
            node* prev = NULL;
            node* curr = table[index];
            while (curr->next != NULL && entry->item.GetKey() != key)
            {
                prev = curr;
                curr = curr->next;
            }
            if (curr->item.GetKey() == key)
            {
                node* nextEntry = curr->next;
                table[index] = nextEntry;
                delete entry;
                size--;
                cout << "Removedn";
            }
        }
    }

我使用这个函数插入到哈希表

void HashT::Ins(Data& data)
{
    size_t index = HashFunc(data.GetKey());
    node * newData = new node(data);
    if(table[index] != NULL && table[index]->item.GetKey() == data.GetKey())
        cout << "Do nothingn";
    else
        newData->next = table[index];
        table[index] = newData;
        size++;
}

在main()中调用Remove看起来像这样

HashT ht(cout);
ht.Ins(Data(node1));
ht.Ins(Data(node2));
ht.Ins(Data(node3));
ht.Ins(Data(node4));
ht.Remove("string3"); //This does not work
ht.Ins(Data(node5));
ht.Ins(Data(node6));
ht.Ins(Data(node7));
ht.Ins(Data(node8));
ht.Remove("string2"); //This Works
ht.Remove("string5"); //This doesnt work

Answer 1

我建议如下修改:

void HashT::Remove(string key)
    {
        size_t index = HashFunc(key);
        if (table[index] != NULL)
        {
            node* prev = NULL;
            node* curr = table[index];
            while (curr->next != NULL && entry->item.GetKey() != key)
            {
                prev = curr;
                curr = curr->next;
            }
            if (curr->item.GetKey() == key) // change (1) !!!!
            {
                node* nextEntry = curr->next;
                if (prev)                      // change 2 !!!!
                   prev->next = nextEntry;     // change 2 !!!!
                else table[index] = nextEntry; // change 2 !!!
                delete entry;
                size--;
                cout << "Removedn";
            }
            else if (curr->next!=NULL)            // change 1 !!!
                cout << "Not found in bucketn";  // change 1 !!!
        }
    }

change 2:只有当发现的元素是桶中的第一个元素时，才更新表[index]。在所有其他情况下，这是经典的元素删除，您将前一个元素的下一个指针更改为下一个元素(经典链表更新)。

编辑:我以前的更改1被初始entry误导，对不起。我已经对它进行了更新，以明确在bucket中找不到项的情况。