为开放哈希动态分配的结构数组 table

Question

为了学习，我正在尝试用 C++ 实现一个简单的开放哈希。我对函数与数组指针的交互感到非常困惑，我已经无计可施了。

代码：

struct node{
    int data;
    node* next;
    node* prev;
    bool state;
    node(){
        prev = next = NULL;
        state = true;
    }
};

//state true means empty, state false  means full.
void insert(node *array,int value){
    node *current = array;
    if(array->state == true){
        array->data = value;
        array->state = false;
    } else {
        node* add = new node();
        add->data = value;
        add->state = false;
        while(current->next != NULL){
            current = current->next;
        }
        current->next =  add;
        add->prev = current;
        
    }
}

void display(node *array, int size){
    node *show = new node();
    for(int i = 0; i< size; i++){
        if(array->state == false){
            cout<<array->data;
            show = array;
            while(show->next != NULL){
                show = show->next;
                cout<<" --> "<<show->data;
            }
            
        } else {
            cout<<"Empty.";
        }
        cout<<"\n\n";
    }
}
int main(){
    int size;
    cout<<"Enter size of the hash table: ";
    cin>>size;
    node *array = new node[size];
    int value;
    cout<<"Enter Value: ";
    cin>>value;
    int index = value%size;
    //inserting single value
    insert(&array[index],value);
    //Hash table output.
    display(array,size);
    
    return 0;
}

当我运行这段代码时，在数组状态为空的地方没有显示“空”，似乎整个数组具有相同的值。问题出在insert函数上，我怎么也想不通

Answer 1

您可以通过使 Hashtable 成为指向 Node 的指针数组来简化此操作。 nullptr 表示插槽为空，并且您没有空节点和满节点。此外，节点只需要一个下一个指针，并且通常将新条目添加到桶的开头而不是末尾（允许重复条目“替换”旧条目）。使用 Node **.

在列表的开头插入变得非常容易

#include <cstddef>
#include <iostream>

struct Table {
    struct Node {
        Node * next;
        int data;
        Node(Node **prev, int data_) : next{*prev}, data{data_} {
            *prev = this;
        }
    };

    std::size_t size;
    Node **tbl;
    Table(std::size_t size_) : size{size_}, tbl{new Node*[size]} { }
    ~Table() {
        for (std::size_t i = 0; i < size; ++i) {
            Node *p = tbl[i];
            while(p) {
                Node *t = p->next;
                delete p;
                p = t;
            }
        }
        delete[] tbl;
    }
    void insert(int value) {
        Node **slot = &tbl[value % size];
        new Node(slot, value);
    }
    void display() const {
        for(std::size_t i = 0; i < size; i++) {
            std::cout << "Slot " << i << ":";
            for (const Node *node = tbl[i]; node; node = node->next) {
                std::cout << " " << node->data;
            }
            std::cout << std::endl;
        }
    }
};

int main(){
    std::size_t size;
    std::cout << "Enter size of the hash table: ";
    std::cin >> size;
    Table table{size};
    int value;
    std::cout << "Enter Value: ";
    std::cin >> value;
    //inserting single value
    table.insert(value);
    //Hash table output.
    table.display();
    
    return 0;
}

为开放哈希动态分配的结构数组 table

dynamically allocated struct array for open hash table

c++

dev-c++