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

Question

我在下面有这段代码可以从散列 table 中删除一个条目。当我运行代码时，程序没有崩溃，而是我需要删除元素的特定桶中的所有节点都被删除了。插入和删除元素的数量是应该的。

样本

删除之前。节点数 = 11

Bucket[0]
Node01, Node02, Node03

Bucket[1]
Node11, Node12, Node13, Node14

Bucket[2]
Node21, Node22

Bucket[3]
EMPTY

Bucket[4]
Node41, Node42

删除Node12

Hash Table 变成。节点数 = 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 << "Removed\n";
            }
        }
    }

我用这个函数插入到散列中table

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 nothing\n";
    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 << "Removed\n";
            }
            else if (curr->next!=NULL)            // change 1 !!!
                cout << "Not found in bucket\n";  // change 1 !!!
        }
    }

更改 2：仅当找到的元素是存储桶中的第一个时，您才应更新 table[索引]。在所有其他情况下，这是经典的元素删除，您将前一个元素的下一个指针更改为下一个元素（经典链表更新）。

编辑： 我之前的更改 1 被开头的 entry 误导了，对此深表歉意。我对其进行了更新，以明确说明在存储桶中找不到项目的情况。

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

Remove function removes all nodes in hash table

c++

hashtable