用C++在用线性探测解决冲突的散列表中,设计算法实现闭散列表的懒惰删除操作

以下是C++实现的闭散列表懒惰删除操作的示例代码：

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class HashTable {
private:
    struct Node {
        string key;
        int value;
        bool deleted;
        Node() : key(""), value(0), deleted(false) {}
    };

    int size;
    vector<Node> table;

    int hash(string key) {
        int sum = 0;
        for (int i = 0; i < key.size(); i++) {
            sum += key[i] * (i + 1);
        }
        return sum % size;
    }

public:
    HashTable(int size) : size(size) {
        table.resize(size);
    }

    void put(string key, int value) {
        int index = hash(key);
        int i = index;
        while (table[i].deleted || !table[i].key.empty()) {
            if (!table[i].deleted && table[i].key == key) {
                table[i].value = value;
                return;
            }
            i = (i + 1) % size;
            if (i == index) {
                cout << "HashTable is full!" << endl;
                return;
            }
        }
        table[i].key = key;
        table[i].value = value;
        table[i].deleted = false;
    }

    int get(string key) {
        int index = hash(key);
        int i = index;
        while (!table[i].key.empty()) {
            if (!table[i].deleted && table[i].key == key) {
                return table[i].value;
            }
            i = (i + 1) % size;
            if (i == index) {
                return -1;
            }
        }
        return -1;
    }

    void remove(string key) {
        int index = hash(key);
        int i = index;
        while (!table[i].key.empty()) {
            if (!table[i].deleted && table[i].key == key) {
                table[i].deleted = true;
                return;
            }
            i = (i + 1) % size;
            if (i == index) {
                return;
            }
        }
    }
};

在上述代码中，我们使用了一个bool类型的deleted字段来表示元素是否被删除。在put方法中，如果遇到已经被删除的元素，我们会将其重新插入散列表，并将其deleted字段设置为false；在remove方法中，我们只是将要删除的元素的deleted字段设为true。在get方法中，我们忽略已经被删除的元素，直到找到与给定key匹配的元素或者遍历完整个散列表。